5. все, что осталось сделать, это добавить к списку [2, 3, 4], который получился на предыдущем шаге, голову 1, которая была отделена самой первой и получается объединенный список [1, 2, 3, 4]
Теперь, собственно, текст программы:
DOMAINS
intlist=integer*
PREDICATES
append (intlist, intlist)
CLAUSES
%объединение пустого и непустого списков
append ([ ], List, List):- !.
%объединение двух непустых списков
append ([H | T], List, [H | App_T]):- append (T, List, App_T).
GOAL
append ([1, 2], [3, 4], App_List), write(“App_List=”, App_List).
Результат работы программы:
App_List=[1, 2, 3, 4]
Деревья
Дерево, как и список, также является рекурсивным составным объектом, но, в отличие от списка, в дереве можно выделить три составные части (сразу же следует оговорить, что далее речь пойдет только о двоичных, или бинарных деревьях). Составные части двоичного (бинарного) дерева:
1. Левое поддерево, являющееся, в свою очередь деревом;
2. Корень дерева;
3. Правое поддерево, также являющееся деревом.
В графическом виде дерево может быть представлено, например, так:
На следующем рисунке обозначены три составные части дерева.
Каждый узел дерева, приведенного в качестве примера, содержит целое число. Если для всего дерева соблюдается определенное правило расположения значений в узлах дерева, то такое дерево называют упорядоченным. Правило формулируется следующим образом: дерево можно назвать упорядоченным, если все значения, находящиеся в узлах левого поддерева, меньше значения в корне дерева, а все значения, находящиеся в узлах правого поддерева, больше значения в корне дерева.
Это правило должно соблюдаться как для левого, так и для правого поддеревьев, и для их левых и правых поддеревьев (ведь дерево – это рекурсивная структура, и как левое, так и правое поддеревья также являются полноценными деревьями).
Для дерева, приведенного выше в качестве примера, это правило соблюдается, следовательно, это дерево упорядочено.
5 больше –1, 2 и 4, и 5 меньше 7 и 9 (для дерева в целом)
2 больше –1, и 2 меньше 4 (для левого поддерева)
9 больше чем 7 (для правого поддерева)
Узлы дерева, у которых нет левого и правого поддерева, называется листьевыми узлами или вершинами. В рассматриваемом дереве это узлы, которые содержат значения –1, 4 и 7. Отсутствующие у этих узлов левое и правое поддеревья можно назвать пустыми деревьями.
Пустое дерево – это дерево, в котором нет ни одного узла.
Если обозначить на рисунке пустые поддеревья, то это может выглядеть, например, так:
Заштрихованные кружочки как раз и обозначают пустые деревья, или, другими словами, отсутствующие левое и/или правое поддеревья у какого либо узла.
В Prolog’е для представления деревьев не существует отдельного домена, для того, чтобы работать с деревом, необходимо объявить новый нестандартный домен. При этом следует учитывать, что, во-первых, дерево – структура рекурсивная, во-вторых, дерево – структура, состоящая их трех частей, и, в-третьих, дерево может быть пустым или непустым. Все эти особенности учитываются в следующем объявлении домена:
DOMAINS
%домен_для_дерева=функтор_непустого_дерева(корень, левое_поддерево, правое_поддерево) ;
% функтор_пустого_дерева()
treetype=tree (integer, treetype, treetype) ; empty ()
Treetype – это имя нестандартного домена для представления дерева, рекурсивность структуры дерева обеспечивается использованием рекурсивного описания домена, treetype дважды используется справа от знака равенства и описывает, соответственно, домен левого и правого поддеревьев.
Integer – описание домена для значения, находящегося в корневом узле дерева. Объединить в единое дерево три его составные части позволяет использование функтора tree с тремя аргументами. Для описания двух возможных состояний, в которых может находиться дерево, пустого и непустого, используются, соответственно, два функтора – tree и empty. Так как у пустого дерева нет ни корня, ни левого и правого поддеревьев, то и функтор empty не имеет аргументов (используются пустые скобки после empty). В этом случае пустые скобки можно и не использовать.
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
При объявлении домена было использовано только одно зарезервированное слово – integer, все остальные имена выбраны произвольно. В следующем примере также описан домен для представления дерева, только использованы другие имена.
DOMAINS
a=b (integer, a, a) ; c
Такое определение позволяет записать следующую структуру данных (для дерева, приведенного на рисунке):
tree (5,
tree (2,
tree (-1, empty, empty),
tree (4, empty, empty)),
tree (9,
tree (7, empty, empty),
empty))
Вот пример программы, выводящей на экран дерево, как единый объект:
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
GOAL
OrderTree=tree (5, tree (2, tree (-1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty)), write (“Tree=”, OrderTree).
Результат работы программы:
Tree=tree(5,tree(2,tree(-1,empty, empty),tree(4,empty, empty)),
tree(9,tree(7,empty, empty),empty))
Одной из наиболее частых операций, выполняемых с деревом, является исследование всех узлов дерева и обработка их некоторым образом. Последовательная обработка всех узлов дерева называется обходом дерева. В зависимости от того, в какой очередности обрабатываются корень дерева и его поддеревья, различают несколько направлений обхода дерева:
1. Корень, левое поддерево, правое поддерево обход «сверху вниз»;
2. Левое поддерево, правое поддерево, корень обход «снизу вверх»;
3. Левое поддерево, корень, правое поддерево обход «слева направо»;
4. Правое поддерево, корень, левое поддерево обход «справа налево»;
Так как дерево является рекурсивной структурой данных, то для работы с деревьями используется рекурсия. Основной метод обработки дерева заключается в следующем: разделить дерево на корень, левое поддерево и правое поддерево, выполнить какие-либо действия с корнем дерева, и перейти к обработке левого поддерева, а затем правого поддерева, являющимися, в свою очередь, деревьями. Обработка каждого из поддеревьев заключается в разделении их на три части и последовательной обработке каждой из частей.
Деление деревьев продолжается до тех пор, пока очередное поддерево не станет пустым. В этом случае обработку дерева необходимо прекратить. Следовательно, предикаты для работы с деревьями должны иметь, по крайней мере, два предложения: для пустого дерева и для непустого дерева.
Пример: поэлементный вывод дерева, в узлах которого хранятся целые числа, на экран (нужно отметить, что этот пример приводится в учебных целях, дерево вполне может быть выведено на экран как единая структура (см. предыдущий пример)).
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
PREDICATES
printtree (treetype)
CLAUSES
%если дерево пустое, то выводить не экран нечего
printtree (empty):- !.
%если дерево непусто, то разделить дерево на корень, левое и правое поддеревья,
%напечатать корень и использовать тот же самый предикат для печати левого,
%а затем правого поддеревьев, то есть выполнить рекурсивные вызовы
%предиката printtree, передав в качестве аргумента сначала левое, а затем правое
%поддеревья
printtree (tree (Root, Left, Right)):- write (Root), write (“ ~ ”), printtree (Left),
printtree (Right).
GOAL
printtree (tree (5, tree (2, tree (–1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty))).
Результат работы программы обхода дерева «сверху вниз»:
5 ~ 2 ~ –1 ~ 4 ~ 9 ~ 7 ~
Если же второе предложение для предиката printlist переписать для выполнения обхода «слева направо»
printtree (tree (Root, Left, Right)):- printtree (Left), write (Root), write (“ – ”),
printtree (Right).
то результат работы будет следующим, так как дерево упорядочено:
–1 ~ 2 ~ 4 ~ 5 ~ 7 ~ 9 ~
Еще один пример работы с деревом – подсчет числа узлов дерева. Для того чтобы определить количество узлов дерева, вновь нужно рассмотреть два случая: для пустого и непустого деревьев. Если дерево пусто, то количество узлов в таком дереве равно 0. Если дерево не пусто, то определить количество узлов в дереве в целом можно следующим образом: разделить дерево на корень, левое и правое поддеревья, подсчитать число узлов в, левом поддереве, затем в правом поддереве. Зная количество узлов в каждом поддереве достаточно сложить эти значения и прибавить к получившей сумме единицу (учесть, таким образом, корень). Результат и будет общим числом узлов в дереве.
DOMAINS
treetype=tree (integer, treetype, treetype) ; empty
PREDICATES
counter (treetype, integer)
CLAUSES
%число узлов в пустом дереве равно 0
counter (empty, 0):- !.
%если дерево непусто, общее количество узлов дерева равно сумме узлов
%левого и правого поддеревьев, увеличенной на 1
counter (tree (Root, Left, Right), Count):- counter (Left, CountLeft), counter (Right, CountRight), Count=CountLeft+CountRight+1.
GOAL
counter (tree (5, tree (2, tree (–1, empty, empty), tree (4, empty, empty)), tree (9, tree(7, empty, empty), empty)), N), write(“N=”, N).
Результат работы программы:
N=6
Для того чтобы лучше понять, каким образом работает приведенный пример, рекомендуется самостоятельно построить дерево целей, в качестве основы можно взять деревья целей для примеров работы со списками.
И еще один пример по работе с деревьями – создание упорядоченного дерева. Пусть в узлах дерева содержатся символы, символы, добавляемые к дереву, не должны повторяться (программа не выполняет проверки на существование вводимых символов в дереве). Символы вводятся с клавиатуры, символ ‘#’ – признак конца ввода символов.
DOMAINS
treetype=tree (char, treetype, treetype) ; end
PREDICATES
insert (char, treetype, treetype)
create_tree (treetype, treetype)
CLAUSES
%предикат insert обеспечивает вставку введенного с клавиатуры символа в дерево,
%для предиката insert записывается три правила вывода, в которых рассматривается
%три случая: первый случай – вставка нового символа в пустое дерево,
%второй и третий случаи – вставка нового символа в непустое дерево,
%если новый символ меньше, чем символ в корне дерева, то новый символ добавляется
%в левое поддерево, если больше – в правое
%(для сравнения символов используются их ASCII-коды)
%вставка нового символа в пустое дерево, получается дерево с корнем и пустыми
%левым и правым поддеревьями
insert (New, end, tree (New, end, end)):- !.
%вставка нового символа по результатам проверки в левое поддерево,
%левое поддерево изменяется, а правое остается без изменений
insert (New, tree (Root, Left, Right), tree (Root, NewLeft, Right)):- New<Root, !,
insert (New, Left, NewLeft).
%вставка нового символа в правое поддерево, без проверки,
%правое поддерево изменяется, а левое остается без изменений
insert (New, tree (Root, Left, Right), tree (Root, Left, NewRight)):-
insert (New, Right, NewRight).
%предикат create_tree обеспечивает ввод символа с клавиатуры, и вызов предиката insert
create_tree (Tree, NewTree):- readchar(Ch), Ch<>’#’, !,
insert (Ch, Tree, TmpTree), create_tree (TmpTree, NewTree).
create_tree (Tree, Tree).
GOAL
create_tree (end, Tree), write(“Tree=”, Tree).
Результат работы программы:
Tree=tree('d',tree('a',end, tree('b',end, tree('c',end, end))),tree('f',tree('e',end, end),tree('g',end, end)))
С клавиатуры была введена последовательность:
‘d’ ‘a’ ‘f’ ‘b’ ‘e’ ‘g’ ‘c’ ‘#’
Строки
PDC Prolog поддерживает различные стандартные предикаты для обработки строк. Основными предикатами для работы со строками можно назвать предикат frontchar (String, Char, StringRest), позволяющий разделить строку String на первый символ Char и остаток строки StringRest и предикат fronttoken (String, Lexeme, StringRest), который работает аналогично предикату frontchar, но только отделяет от строки String лексему Lexeme. Лексемой называется последовательность символов, удовлетворяющая следующим условиям: имя в соответствии с синтаксисом Prolog’а, число или отличный от пробела символ.
Пример: преобразование строки в список символов (Два варианта. Варианты отличаются друг от друга граничным условием рекурсии. В первом варианте остановка рекурсии происходит, когда от строки будет отделен последний символ и строка станет пустой строкой. Во втором варианте остановка рекурсии происходит в момент попытки отделения от пустой строки очередного символа, что сделать не удается, и происходит откат ко второму предложению).
%1 вариант
DOMAINS
charlist=char*
PREDICATES
string2charlist (string, charlist)
CLAUSES
string2charlist (“”, [ ]):- !.
string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), string2charlist (Str_Rest, T).
GOAL
string2charlist (“abcde”, List), write (“List=”, List).
%2 вариант
DOMAINS
charlist=char*
PREDICATES
string2charlist (string, charlist)
CLAUSES
string2charlist (Str, [H|T]):- frontchar (Str, H, Str_Rest), !, string2charlist (Str_Rest, T).
string2charlist (_, [ ]).
GOAL
string2charlist (“abcde”, List), write (“List=”, List).
Результат работы программы:
List=[‘a’, ‘b’, ‘c’, ‘d’, ‘e’]
Более подробно стандартные предикаты для работы со строками можно посмотреть в файле Prolog.hlp в разделах “STRING HANDLING” и “CONVERSIONS”.
Основы функционального программирования
Введение
Язык Lisp является языком функционального программирования. В Lisp’е как программы, так и данные, представляются одинаково – в виде списков. Например, запись (+ 1 2) может толковаться, в зависимости от контекста, как список, состоящий из трех элементов (данные), или как вызов функции суммирования с двумя аргументами (программа).
О такой особенности Lisp’а говорит и название языка, ведь аббревиатура Lisp произведена от слов LISt Processing (обработка списков). То есть, программы, написанные на Lisp’е, могут обрабатывать и преобразовывать как другие программы, так и самих себя.
Символьные выражения
При написании программ на Lisp’е используются символы и создаваемые на основе символов символьные выражения. Символ в Lisp’е аналогичен переменной в традиционном языке программирования – это имя, состоящее из букв латиницы, цифр и некоторых специальных литер. Символ, как и переменная, может иметь какое-либо значение, то есть представлять какой-либо объект.
Наряду с символами, в Lisp’е используются также:
1. числа, целые и вещественные;
2. специальные константы t и nil, обозначающие логические значения true (истина) и false (ложь);
3. списки.
Символы, числа и специальные константы представляют простейшие объекты, на основе которых строятся все прочие объекты данных. Поэтому для них используется обобщающее название – атомы. Все вышеперечисленные объекты (атомы и списки) называют символьными выражениями. Отношения между различными символьными выражениями можно представить следующим образом:
Списки
Список – это основной тип данных в Lisp. Список заключается в круглые скобки, элементы списка разделяются пробелами. Пустой список обозначается парой скобок – (). Для обозначения пустого списка используется также специальная константа nil.
Примеры списков:
;пятиэлементный список
(
;четырехэлементный список
(
;одноэлементный список
Первый элемент списка называется головой списка, все прочие элементы, кроме первого, представленные как список, называются хвостом списка.
Примеры разделения списка на голову и хвост:
Список | Голова | Хвост |
( | 1 | ( |
( | 1 | (2 ( |
( | () | |
(1) | 1 | () |
Функции
В Lisp’е для вызова функции принята единообразная префиксная форма записи, при которой как имя функции, так и ее аргументы записываются в виде элементов списка, причем имя функции – это всегда первый элемент списка.
В Lisp’е передача параметров в функцию осуществляется по значению. Параметры используются для того, чтобы передать данные в функцию, а результат функции возвращается как ее значение, а не как значение параметра, передаваемого по ссылке.
Например:
;возвращаемое значение 8
(+ 3 5)
;возвращаемое значение 12
(* (+ 1 2) (+ 3 4))
;возвращаемое значение 0
(sin 3.14)
Список может рассматриваться и не как вызов функции, а как перечень равноправных элементов. Для блокирования вызова функции используется, в свою очередь, функция quote.
Например, список
(+ 3 5)
будет восприниматься как вызов функции суммирования с аргументами 3 и 5. Если же использовать данный список в качестве аргумента функции quote
(quote (+ 3 5))
то список воспринимается именно как список. То есть применение функции quote блокирует вызов функции и ее имя воспринимается как обычный элемент списка. Или, иначе говоря, если список является аргументом функции quote, то первый элемент списка не считается именем функции, а все прочие элементы не считаются аргументами функции.
Для функции quote существует сокращенная форма записи, вместо имени функции quote используется апостроф перед открывающейся скобкой списка. Например:
‘(+ 3 5)
Если предложить интерпретатору следующие примеры, он вернет соответствующие значения (значение, возвращаемое интерпретатором, написано прописными символами):
> (+ 3 5))
8
> (quote (+ 3 5))
(+ 3 5)
> ‘(+ 3 5)
(+ 3 5)
> (quote (quote (+ 3 5)))
(QUOTE (+ 3 5))
Для выполнения операции присваивания используется функция set. Формат функции (set variable value). Причем, если не требуется вычисления аргументов, их нужно предварить апострофами. Например:
> (set ‘x 5)
5
> x
5
> (set ‘y (+ 6 12))
18
> y
18
> (set 'a 'b)
B
> (set a 'c)
C
> a
B
> b
C
> c
error: unbound variable - C
Вместо функции set можно использовать функцию setq, также выполняющую присваивание, но при ее использовании нет необходимости предварять первый аргумент апострофом. Для первого аргумента блокировка вычисления выполняется автоматически.
> (setq x 5)
5
> x
5
> (setq y ())
18
> y
18
Функцию, которая в качестве значения возвращает только константы nil или t, называют предикатом.
Для определения собственной функции можно воспользоваться стандартной функцией defun (сокращение от DEfine FUNction). Эта стандартная функция позволяет создавать собственные функции, причем не запрещается переопределять стандартные функции, то есть в качестве имени собственной функции использовать имя стандартной функции. Функция defun выглядит следующим образом: (defun name (fp1 fp2 … fpN) (form1 form1 … formN)).
Name – это имя новой функции, (fp1 fp2 … fpN) – список формальных параметров, а (form1 form1 … formN) – тело функции, то есть последовательность действий, выполняемых при вызове функции.
Пример – функция для вычисления суммы квадратов:
(defun squaresum (x y) (+ (* x x) (* y y)))
Результат работы:
>(squaresum 3 4)
25
>(squaresum
20
Еще один пример: функция deftype, определяющая тип выражения (пустой список, атом или список).
(defun deftype(arg)
(cond
((null arg) ‘emptylist)
((atom arg) ‘atom)
(t ‘list)
)
)
Результат работы:
>(deftype ())
EMPTYLIST
>(deftype 'abc)
ATOM
>(deftype '(a b c))
LIST
Базовые функции
В Lisp’е существует пять основных функций, называемых базовыми:
1. (car list) – отделяет голову списка (первый элемент списка);
2. (cdr list) – отделяет хвост списка (все элементы, кроме первого, представленные в виде списка);
3. (cons head tail) – соединяет элемент и список в новый список, где присоединенный элемент становится головой нового списка;
4. (equal object1 object2) – проверяет объекты на равенство;
5. (atom object) – проверяет, является ли объект атомом.
Так как функции equal и atom возвращают значения nil или t, их можно назвать базовыми предикатами.
Рассмотрим примеры для перечисленных функций:
> (car ‘(one two three))
ONE
> (car ‘(one))
ONE
> (car ‘())
NIL
> (cdr ‘(first second third))
(SECOND THIRD)
> (cdr ‘(first))
NIL
> (cdr ‘())
NIL
> (cons 1 ‘(2 3))
(1 2 3)
> (cons 1 nil)
(1)
> (cons nil nil)
(NIL)
> (equal ‘(‘(
T
> (equal ‘(‘(
NIL
> (equal ‘one ‘two)
NIL
> (atom ‘one)
T
> (atom 1)
T
> (atom (1))
NIL
Управляющие структуры (предложения)
Для организации различных видов программ в Lisp’е служат разнообразные управляющие структуры, которые позволяют организовывать ветвление, циклы, последовательные вычисления. Перечислим их:
1. предложение let – служит для одновременного присваивания значений нескольким символам;
2. предложения prog1, prog2, prong – используются для организации последовательных вычислений;
3. предложение cond – используется для организации ветвления, и, следовательно, очень важно для организации рекурсии;
4. предложение do – традиционный цикл.
Рассмотрим перечисленные предложения подробнее.
Предложение let служит для одновременного присваивания значений нескольким переменным. Формат предложения let:
(let ((var_1 value_1) (var_2 value_2) … (var_n value_n)) form_1 form_2 … form_m)
Работает предложение следующим образом: переменным var_1, var_2, … var_n присваиваются (параллельно!) значения value_1, value_2, … value_n, а затем вычисляются (последовательно!) значения форм form_1 form_2 … form_m. В качестве значения всего предложения let возвращается значение последней вычисленной формы form_m.
> (let ((x 3) (y 4)) (sqrt (+ (* x x) (* y y))))
5.0
Так как присваивание значений переменным выполняется параллельно, то в следующем примере будет выдано сообщение об ошибке.
> (let ((x 3) (y (+ 1 x))) (sqrt (+ (* x x) (* y y))))
error: unbound variable - X
После завершения выполнения предложения let переменные var_1, var_2, … var_n получают значения, которые они имели до использования в этом предложении, то есть предложение let выполняет локальные присваивания.
> (setq x ‘three)
THREE
> (setq y ‘four)
FOUR
> (let ((x 3) (y 4)) (sqrt (+ (* x x) (* y y))))
5.0
> x
THREE
> y
FOUR
Для выполнения последовательных действий можно использовать предложения prog1, prog2, prong. Их общий формат:
(prog* form_1 form_2 … form_n)
Все три предложения работают одинаково, последовательно вычисляются значения форм form_1, form_2, …, form_n. Различие между предложениями проявляется только в тех значениях, которые они возвращают: предложение prog1 возвратит значение первой формы form_1, предложение prog2 возвратит значение второй формы form_2, а предложение progn возвратит значение последней формы form_n. Во всем остальном эти предложения ничем не отличаются.
> (prog1 (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2)))
2
> (prog2 (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2)))
4
> (progn (setq x 2) (setq x (* x 2)) (setq x (* x 2)) (setq x (* x 2)))
16
Предложение cond предназначено для организации ветвления (это предложение является аналогом оператора выбора – переключателя switch в языке C). Формат предложения cond выглядит следующим образом:
(cond
(predicate1 form1)
(predicate2 form21 form22 … form2M)
(predicate3)
…
(predicateN formN)
)
При выполнении предложения cond последовательно вычисляются значения предикатов, обозначенных как predicate. Если предикат возвращает значение t, тогда вычисляется значение вычислимой формы form и полученное значение возвращается в качестве значения всего предложения cond. Другими словами, идет последовательный перебор предикатов до тех пор, пока не встретиться предикат, который будет истинен.
Для некоторого предиката может отсутствовать вычислимая форма. В таком случае предложение cond возвратит значение самого предиката. Для некоторого предиката вычислимых форм может быть несколько. В таком случае формы будут вычислены последовательно, и значение последней формы будет возвращено как значение всего предложения cond.
Пример для предложения cond – определение отрицательного, равного нулю или положительного числа (в этом примере предложения cond вложены одно в другое):
(defun snumberp (num)
(cond
((numberp num)
(cond
((< num 0) ‘neg_number)
((= num 0) ‘zero)
((> num 0) ‘pos_number)
))
(t ‘not_number)
)
)
Результат работы программы:
> (snumberp 1)
POS_NUMBER
> (snumberp -1)
NEG_NUMBER
>(snumberp 0)
ZERO
> (snumberp 'a)
NOT_NUMBER
Как быть в случае, если ни один из предикатов predicate в предложении cond не вернет значение, отличное от nil? Тогда используется прием, как в последнем примере. В качестве последнего предиката predicate используется константа t, что гарантирует выход из предложения cond с помощью последней ветви (использование константы t в качестве предиката predicate аналогично использованию метки default в переключателе switch).
Предложение do, также как и предложение cond, является аналогом оператора цикла for в языке C. Формат предложения do:
(do
((var_1 value_1) (var_2 value_2) … (var_n value_n))
(condition form_yes_1 form_yes_2 … form_yes_m)
form_no_1 form_no_2 … form_yes_k
)
Предложение do работает следующим образом: первоначально переменным var_1, var_2, …, var_n присваиваются значения value_1, value_2, …, value_n (параллельно, как в предложении let). Затем проверяется условие выхода из цикла condition. Если условие выполняется, последовательно вычисляются формы form_yes_1, form_yes_2, …, form_yes_m, и значение последней вычисленной формы form_yes_m возвращается в качестве значения всего предложения do. Если же условие condition не выполняется, последовательно вычисляются формы form_no_1, form_no_2, …, form_yes_k, и вновь выполняется переход в проверке условия выхода из цикла condition.
Пример использования предложения do: для возведения x в степень n с помощью умножения определена функция power с двумя аргументами x и n: x – основание степени, n – показатель степени.
> (defun power (x n)
(do
;присваивание начального значения переменной result
((result 1))
;условие выхода их цикла
((= n 0) result)
;повторяющиеся действия
(setq result (* result x)) (setq n (- n 1))))
POWER
> (power 2 3)
8
Простая рекурсия
Несмотря на то, что в языке Lisp есть предложение для организации циклических действий, все же основным методом решения задач остается метод с использованием рекурсии, то есть с применением рекурсивных функций.
Функция является рекурсивной, если в ее определении содержится вызов этой же функции. Рекурсия является простой, если вызов функции встречается в некоторой ветви лишь один раз. Простой рекурсии в процедурном программировании соответствует обыкновенный цикл. Например, задача нахождения значения факториала n! сводится к нахождению значения факториала (n-1)! и умножения найденного значения на n.
Пример: нахождение значения факториала n!.
> (defun factorial (n)
(cond
;факториал 0! равен 1
((= n 0) 1)
;факториал n! равен (n-1)!*n
(t (* (factorial (- n 1)) n))))
FACTORIAL
>(factorial 3)
6
Для отладки программы можно использовать возможности трассировки. Трассировка позволяет проследить процесс нахождения решения.
Для того чтобы включить трассировку можно воспользоваться функцией trace:
Например:
> (trace factorial)
(FACTORIAL)
> (factorial 3)
Entering: FACTORIAL, Argument list: (3)
Entering: FACTORIAL, Argument list: (2)
Entering: FACTORIAL, Argument list: (1)
Entering: FACTORIAL, Argument list: (0)
Exiting: FACTORIAL, Value: 1
Exiting: FACTORIAL, Value: 1
Exiting: FACTORIAL, Value: 2
Exiting: FACTORIAL, Value: 6
6
Для отключения трассировки можно воспользоваться функцией untrace:
Например:
> (untrace factorial)
NIL
Можно говорить о двух видах рекурсии: рекурсии по значению и рекурсии по аргументу. Рекурсия по значению определяется в случае, если рекурсивный вызов является выражением, определяющим результат функции. Рекурсия по аргументу существует в функции, возвращаемое значение которой формирует некоторая нерекурсивная функция, в качестве аргумента которой используется рекурсивный вызов.
Приведенный выше пример рекурсивной функции вычисления факториала является примером рекурсии по аргументу, так как возвращаемый результат формирует функция умножения, в качестве аргумента которой используется рекурсивный вызов.
Вот несколько примеров простой рекурсии.
Возведение числа x в степень n с помощью умножения (рекурсия по аргументу):
> (defun power (x n)
(cond
;x0=1 (любое число в нулевой степени равно 1)
((= n 0) 1)
;xn=x(n-1)*n (значение x в степени n вычисляется возведением x в степень n-1
;и умножением результата на n)
(t (* (power (- n 1)) n))))
> (power 2 3)
8
> (power 10 0)
1
Копирование списка (рекурсия по аргументу):
> (defun copy_list (list)
(cond
;копией пустого списка является пустой список
((null list) nil)
;копией непустого списка является список, полученный из головы и копии
;хвоста исходного списка
(t (cons (car list) (copy_list (cdr list))))))
COPY_LIST
>(copy_list ‘(
(1 2 3)
>(copy_list ())
NIL
Определение принадлежности элемента списку (рекурсия по значению):
> (defun member (el list)
(cond
;список просмотрен до конца, элемент не найден
((null list) nil)
;очередная голова списка равна искомому элементу, элемент найден
((equal el (car list)) t)
;если элемент не найден, продолжить его поиск в хвосте списка
(t (member el (cdr list)))))
MEMBER
> (member 2 '(
T
> (member 22 '(
NIL
Соединение двух списков (рекурсия по аргументу):
> (defun append (list1 list2)
(cond
;соединение пустого списка и непустого дает непустой список
((null list1) list2)
;соединить голову первого списка и хвост первого списка,
;соединенный со вторым списком
(t (cons (car list1) (append (cdr list1) list2)))))
APPEND
> (append '(1 2) '(3 4))
(
> (append '(1
(1 2)
> (append () '(3 4))
(3 4)
> (append
NIL
Реверс списка (рекурсия по аргументу):
> (defun reverse (list)
(cond
;реверс пустого списка дает пустой список
((null list) nil)
;соединить реверсированный хвост списка и голову списка
(t (append (reverse (cdr list)) (cons (car list) nil)))))
REVERSE
> (reverse '(one two three))
(THREE TWO ONE)
> (reverse ())
NIL
Другие виды рекурсии
Рекурсию можно назвать простой, если в функции присутствует лишь один рекурсивный вызов. Такую рекурсию можно назвать еще рекурсией первого порядка. Но рекурсивный вызов может появляться в функции более, чем один раз. В таких случаях можно выделить следующие виды рекурсии:
1. параллельная рекурсия – тело определения функции function_1 содержит вызов некоторой функции function_2, несколько аргументов которой являются рекурсивными вызовами функции function_1.
(defun function_1 … (function_2 … (function_1 …) … (function_1 …) … ) … )
2. взаимная рекурсия – в теле определения функции function_1 вызывается некоторая функции function_2, которая, в свою очередь, содержит вызов функции function_1.
(defun function_1 … (function_2 … ) … )
(defun function_2 … (function_1 … ) … )
3. рекурсия более высокого порядка – в теле определения функции аргументом рекурсивного вызова является рекурсивный вызов.
(defun function_1 … (function_1 … (function_1 …) … ) … )
Рассмотрим примеры параллельной рекурсии. В разделе, посвященном простой рекурсии, уже рассматривался пример копирования списка (функция copy_list), но эта функция не выполняет копирования элементов списка в случае, если они являются, в свою очередь также списками. Для записи функции, которая будет копировать список в глубину, придется воспользоваться параллельной рекурсией.
> (defun full_copy_list (list)
(cond
;копией пустого списка является пустой список
((null list) nil)
;копией элемента-атома является элемент-атом
((atom list) list)
;копией непустого списка является список, полученный из копии головы
;и копии хвоста исходного списка
(t (cons (full_copy_list (car list)) (full_copy_list (cdr list))))))
FULL_COPY_LIST
> (full_copy_list '((
((
> (full_copy_list ())
NIL
Не обойтись без параллельной рекурсии при работе c бинарными деревьями. Бинарное дерево, как и все прочие данные, представляются в Lisp’е в виде списков. Например, упорядоченное бинарное дерево
можно представить в виде спискаnil nil) (3 nil nil)) (5 nil nil)). Константы nil представляют пустые деревья. В таком представлении первый элемент списка – это узел дерева, второй элемент списка – левое поддерево и третий элемент списка – правое поддерево. Другой вариант представления дерева– (((nil 1 nil) 2 (nil 3 nil)) 4 (nil 5 nil)). В таком представлении первый элемент списка – это левое поддерево, второй элемент списка – узел дерева и третий элемент списка – правое поддерево. Можно использовать и другие варианты представления деревьев. Рассмотрим простой пример работы с бинарным деревом – обход дерева и подсчет числа узлов дерева. Для работы с элементами дерева, которые являются, по сути, элементами списка, очень удобно использовать стандартные функции Lisp’а, для получения первого, второго и третьего элементов списка – fist, second и third, соответственно.
> (defun node_counter (tree)
(cond
;число узлов пустого дерева равно 0
((null tree) 0)
;число узлов непустого дерева складывается из: одного корня,
;числа узлов левого поддерева и числа узлов правого поддерева
(t (+ 1 (node_counter (second tree)) (node_counter (third tree))))))
NODE_COUNTER
> (node_counter '(4nil nil) (3 nil nil)) (5 nil nil)))
5
> (node_counter nil)
0
Пример взаимной рекурсии – реверс списка. Так как рекурсия взаимная, в примере определены две функции: reverse и rearrange. Функция rearrange рекурсивна сама по себе.
> (defun reverse (list)
(cond
((atom list) list)
(t (rearrange list nil)))))
REVERSE
> (defun rearrange (list result)
(cond
((null list) result)
(t (rearrange (cdr list) (cons (reverse (car list)) result)))))
REARRANGE
> (reverse '(7))
())
Пример рекурсии более высокого порядка – второго. Классический пример функции с рекурсией второго порядка – функция Аккермана.
Функция Аккермана определяется следующим образом:
B (0, n) = n+1
B (m, 0) = B (m-1, 0)
B (m, n) = B (m-1, B (m, n-1))
где m>=0 и n>=0.
> (defun ackerman
(cond
((= n 0) (+ n 1))
((= m 0) (ackerman (- m
(t (ackerman (- m 1) (ackerman m (- n 1))))))
ACKERMAN
> (ackerman 2 2)
7
> (ackerman 2 3)
9
> (ackerman 3 2)
29
Литература
1. Адаменко А. Н., Кучуков программирование и Visual Prolog. – СПб.: БХВ-Петербург, 2003. – 992 С.
2. Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: Мир, 1990. – 560 С.
3. Ин Ц., Соломон Д. Использование Турбо-Пролога. – М.: Мир, 1993. – 608 С.
4. Доорс Дж., Рейблейн А. Р., Вадера С. Пролог ‑ язык программирования будущего. – М.: ФиС, 1990. – 144 С.
5. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. – М.: Мир, 1990. – 235 С.
6. Клоксин У., Меллиш Д. Программирование на языке Пролог. – М.: Мир, 1987. – 336 С.
7. Стобо Дж. Язык программирования Пролог. – М.: Мир, 1993. – 368 С.
8. Хювёнен Э., Сеппянен Й. Мир Лиспа. ‑ М.: Мир, 1990. – 447 С.
9. Хендерсон П. Функциональное программирование: применение и реализация. ‑ М.: Мир, 1983. – 349 С.
10. Малпас Дж. Реляционный язык Пролог и его применение. – М.: Наука, 1990. – 463 С.
11. Янсон А. Турбо-Пролог в сжатом изложении. – М.: Мир, 1991. – 94 С.
12. Маурер У. Введение в программирование на языке ЛИСП. – М.: Мир, 1978. – 104 С.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
