Эффективная подготовка к государственным междисциплинарным экзаменам для студентов технических специальностей (стр. 40 )

  VIII.  Функциональное и логическое программирование

1. Рекурсия и циклы в Лиспе

Циклические вычисления в Лиспе выполняются или с помощью итерационных (циклических) предложений или рекурсивно.

Рекурсия в Lisp основана на математической теории рекурсивных функций. Рекурсия хорошо подходит для работы со списками, так как сами списки могут состоять из подсписков. То есть иметь рекурсивное строение. Для обработки рекурсивных структур совершенно естественно использование рекурсивных процедур.

Списки можно определить с помощью следующих правил Бэкуса-Наура:

Список -> NIL	; список либо пуст, либо это точечная пара,
Список -> (голова. хвост)	; хвост, который является списком
Голова -> Атом	; рекурсия «в глубину»
Голова -> Список
Хвост -> Список	; рекурсия «в ширину»

LOOP реализует бесконечный цикл (LOOP форма1 форма2…), в котором формы вычисляются до тех пор, пока не встретится явный оператор завершения RETURN.

DO - это самое общее циклическое предложение. Общая форма

( DO (( var1 знач1 шаг1) ( var2 знач2 шаг2)....)

( условие - окончания форма11 форма12...)

форма21

форма22

...)

1) В начале локальным переменным var1 ..varN присваиваются начальные значения знач1..значn. Переменным, для которых не заданы начальные значения, присваивается nil.

2) Затем проверяется условие окончания, если оно выполняется то вычисляются форма11, форма12... В качестве значения берется значение последней формы.

3) Если условие не выполняется, то вычисляются форма21, форма22...

4) На следующем цикле переменным vari присваиваются одновременно новые значения определяемые формами шагi и все повторяется.

Примеры

* ( do (( x 1 ( + 1 x))) (( > x 10) ( print 'end)) ( print x))

Будет печатать последовательность чисел, в конце - end. Может одновременно изменяться значения нескольких переменных.

*(do ((x1(+1x))(y1(+2y))(z3));значение не меняется

((>x10)(print ‘end))(princ”x=”)(prin1x)(princ”y=”)(prin1y)(princ”z=”)(prin1z)(terpri))

Можно реализовать вложенные циклы.

*(do((x1(+1x))) ((>x10)) (do((y1(+2y)))((>y4)) (princ”x=”) (prin1x) (princ”y=”)(prin1y)(terpri)))

DOTIMES можно использовать вместо DO, если надо повторить вычисления заданное число раз. Общая форма: (DOTIMES(var num форма-return)(форма-тело)) здесь var- переменная цикла; num - форма, определяющая число циклов; форма-return результат, который должен быть возвращен.

РЕКУРСИЯ. Функция является рекурсивной, если в ее определении содержится вызов самой этой функции. Рекурсия основной и самый эффективный способ организации повторяющихся вычислений в функциональном программировании и в Лиспе. ПРИМЕР. Определим функцию MEMBER :

(defun member(i l) (cond ((null l) nil) ((eql (car l) i) l) (t (member i (cdr l)))))

Правила записи рекурсивной функции :

1. Терминальная ветвь необходима. Без терминальной ветви рекурсивный вызов был бы бесконечным. Терминальная ветвь возвращает результат, который является базой для вычисления результатов рекурсивных вызовов.

2. После каждого вызова функции самой себя, мы должны приближаться к терминальной ветви. Всегда должна быть уверенность, что рекурсивные вызовы ведут к терминальной ветви.

3. Проследить вычисления в рекурсии чрезвычайно сложно. Очень трудно мысленно проследить за действием рекурсивных функций. Это практически невозможно для сложных функций. Т. о. мы должны уметь писать рекурсивные функции, без того чтобы представлять точно порядок вычисления.

Как писать рекурсивные функции. При написании рекурсивных функций мы должны планировать терминальные и рекурсивные ветви.

1. Планирование терминальной ветви. При написании рекурсивной функции мы должны решить, когда функция может вернуть значение без рекурсивного вызова.

2. Планирование рекурсивной ветви. В этом случае мы вызываем функцию рекурсивно с упрощенным аргументом и используем результат для расчета значения при текущем аргументе. Таким образом, мы должны решить:

1) как упрощать аргумент, приближая его шаг за шагом к конечному значению.

2) Кроме этого необходимо построить форму, называемую рекурсивным отношением, которая связывает правильное значение текущего вызова со значением рекурсивного вызова. В нашем случае это (sumall n) и (sumall (- n 1)). Иногда просто найти это отношение, а если не получается надо выполнить следующую последовательность шагов.

a). Определить значение некоторого простого вызова функции и ее соответствующего рекурсивного вызова.

b). Определить соотношение между парой этих функций,

Общая форма определения рекурсивной функции

(defun <имя> <параметры>

(cond (терминальная ветвь 1)

(терминальная ветвь 2)

..........................................................

(терминальная ветвь n)

(рекурсивная ветвь 1)

(рекурсивная ветвь 2)

.........................................................

(рекурсивная ветвь n)))

2. Внутpеннее пpедставление списков в Лиспе

Структура памяти. Каждый атом занимает ячейку.

Списки, являются совокупностью атомов, и связываются вместе специальными элементами памяти, называемыми списочными ячейками или cons-ячейки. Каждая списочная ячейка состоит из двух частей, полей. Первое поле - CAR, второе CDR. Поля типа списочная ячейка содержат указатели на другие ячейки, или nil. Если обе ячейки содержат указатели на атомы, то можно записать проще

Этому случаю соответствует структура (a. b) и называется точечная пара.

Представление списков через списочную ячейка Список из одного атома, представляется, как

Nil указывает на конец списка. Вместо nil пишут-\.

Список получается как операция(cons 'a nil). Список из двух элементов (b a)

Правое поле указыват на cdr списка (хвост). Левое поле, на саr списка (голову).

Каждому элементу списка соответствует списочная ячейка.

Представление списков через точечные пары. Любой список можно записать в точечной нотации.(a)ó(a. nill)

(a b c)ó(a.(b.(c. nil)))

Выражение представленное в точечной нотации можно привести к списочной если cdr поле является списком.

(a.(b c))ó(a b c)

(a.(b. c))ó(a b. c)

Списочная ячейка

CONS создает новую списочную ячейку, car поле которой указывает на первый элемент, а cdr на второй (cons’x’(a b c))

*(list’a’(b c)) (a(b c)) этот список представляется

3. Декларативная и процедурная семантика Пролог-программ

В Прологе наиболее часто используются две семантические модели: декларативная и процедурная. Семантические модели предназначены для объяснения смысла программы.

В декларативной модели рассматриваются отношения, определенные в программе. Она определяет, является ли целевое утверждение истинным, исходя из данной программы, и если оно истинно, то для какой конкретизации переменных. Для этой модели порядок следования предложений в программе и условий в правиле не важен.

Декларативная семантика определяет, что должно быть результатом работы программы, не вдаваясь в подробности, как это достигается. Пусть задано

P:-Q, R. где P, Q, R - термы.

Тогда с точки зрения декларативного смысла это предложение читается: " P-истинно, если Q R истинны. " Или " Из Q и R следует Р." Т. е. определяются логические связи между головой предложения и целями в его теле. Таким образом, декларативный смысл программы определяет, является ли данная цель истинной (достижимой), и если - да, то при каких значениях переменных она достигается.

Конкретизацией I предложения С называется результат подстановки в него на место каждой переменной некоторого терма. Заметим, что это отличается от конкретизации переменной. Пример:

haschild( X ):-parent( X, Y).

| |

haschild(tom):-parent(tom, Y). Конкретизация I. Вариант 1. (X=tom)

haschild(bob):-parent(bob, ann). Конкретизация I. Вариант 2. (X=bob, Y=ann)

Пусть дана некоторая программа и цель G, тогда в соответствии с декларативной семантикой, можно утверждать, что: цель G истинна (т, е. достижима или логически следует из программы) тогда и только тогда, когда в программе существует предложение С, такое, что существует такая его (С) конкретизация I, что голова I совпадает с G и все цели в теле I истинны.

Пример

female(ann).

C(I) parent(ann, bob).

C:

mother(ann):-parent(ann, Y), female(ann).

mother(X) :-parent(X, Y), female(X).

?- mother(ann).

Это определение можно распространить на вопросы следующим образом. В общем случае вопрос - список целей, разделенных запятыми. Список целей называется истинным (достижимым), если все цели в этом списке истинны, достижимы, при одинаковых конкретизациях переменных. Запятая между целями означает конъюнкцию целей, и они должны быть все истинны.

Процедурная модель рассматривает правила как последовательность шагов, которые необходимо успешно выполнить для того, чтобы соблюдалось отношение, приведенное в заголовке правила. Это процедура достижения списка целей в контексте дан­ной программы. Процедура выдает истинность или ложность списка целей и соответствующую конкретизацию переменных. Процедура осуществляет автоматический возврат для перебора различных вариантов.

Процедурная семантика (процедурный смысл) пролог - программы определяет, как пролог-программа отвечает на вопросы. Ответить на вопрос это значит удовлетворить цели. Поэтому процедурная семантика пролога - это процедура вычисления списка целей с учетом программы. Рассмотрим программу и на ее примере процедуру вычисления списка целей.