LABS1D (ЛИСП), страница 3

5. Передача управления.

6. Задание к лабораторной работе.

7. Вопросы.

1. Предложения LET и LET*.

Предложение LET создает локальную связь внутри формы:

(LET ((m1 знач1) (m2 знач2)...)

форма1 форма2 ...)

Вначале статические переменные m1, m2, ... связываются (одновременно) с соответствующими значениями знач1, знач2, ... . Затем слева на право вычисляются значения формы1, формы2, ... . Значение последней формы возвращается в качестве значения всей формы. После вычисления связи статических переменных ликвидируются.

Предложения LET можно делать вложенными одно в другое.

_(LET ((x ‘a) (y ‘b))

(LET ((z ‘c)) (LIST x y z))) ð (a b c)

_(LET ((x (LET ((z ‘a)) z)) (y ‘b))

(LIST x y)) ð (a b)

_(LET ((x 1) (y (+ x 1)))

(LIST x y)) ð ERROR

При вычислении у У и Х еще нет связи. Значения переменным присваиваются одновременно. Это означает, что значения всех переменных mi вычисляются до того, как осуществляется связывание с формальными параметрами.

Подобной ошибки можно избежать с помощью формы LET*:

_(LET* ((x 1) (y (+ x 1)))

(LIST x y)) ð (1 2)

2. Последовательные вычисления.

Предложения PROG1 и PROGN позволяют работать с несколькими вычисляемыми формами:

(PROG1 форма1 ... формаN)

(PROGN форма1 ... формаN)

Эти специальные формы последовательно вычисляют свои аргументы и в качестве значения возвращают значение первого (PROG1) или последнего (PROGN) аргумента.

_(PROG1 (SETQ x 1) (SETQ y 5)) ð 1

_(PROGN (SETQ j 8) (SETQ z (+x j))) ð 9

3. Разветвление вычислений.

Условное предложение COND:

(COND (p1 a1)

...

(pn an))

Предикатами pi и результирующими выражениями ai могут быть произвольные формы. Выражения pi вычисляются последовательно до тех пор, пока не встретится выражение, значением которого является T. Вычисляется результирующее выражение, соответствующее этому предикату, и полученное значение возвращается в качестве значения всего предложения COND. Если истинного предиката нет то значением COND будет NIL.

Рекомендуется в качестве последнего предиката использовать символ T. Тогда соответствующее ему an будет вычисляться в том случае, если другие условия не выполняются.

Если условию не ставится в соответствие результирующее выражение, то в качестве результата выдается само значение предиката. Если же условию соответствуют несколько форм, то при его истинности формы вычисляются последовательно слева на право и результатом предложения COND будет значение последней формы.

Предложения COND можно комбинировать.

(COND ((> x 0) (SETQ рез x))

((< x 0) (SETQ x -x) (SETQ рез х))

((= х 0))

(Т ‘ошибка))

Предложение IF.

(IF условие то-форма иначе-форма)

(IF (> x 0) (SETQ y (+ y x)) (SETQ y (- y x)))

Если выполняется условие (т. е. х>0), то к значению y прибавляется значение х, иначе (x<0) от y отнимается отрицательное значение х, т. е. прибавляется абсолютное его значение.

Можно использовать форму WHEN.

(WHEN условие форма1 форма2 ... )

Выбирающее предложение CASE^

(CASE ключ

(список-ключей1 m11 m12 ... )

(список-ключей2 m21 m22 ... )

....)

Сначала вычисляется значение ключевой формы - ключ. Затем его сравнивают с элементами списка-ключейi. Когда в списке найдено значение ключевой формы, начинают вычисляться соответствующие формы mi1, mi2, ... . Значение последней возвращается в качестве значения всего предложения CASE.

_(SETQ ключ 3) ð 3

_(CASE ключ

(1 ‘one)

(2 ‘(one + one) ‘two)

(3 ‘(two + one) ‘three) ð three

4. Циклические вычисления.

Предложение DO.

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

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

форма21 форма22 ...)

Первый аргумент описывает внутренние переменные var1, var2, ..., их начальные значения - знач1, знач2, ... и формы обновления - шаг1, шаг2, ....

Вначале вычисления предложения DOI внутренним переменным присваиваются начальные значения, если значения не присваиваются, то по умолчанию переменным присваивается NIL. Затем проверяется условие-окончания. Если оно действительно, то последовательно выполняются формы1i и значение последней возвращается в качестве значения всего предложения DO, иначе последовательно вычисляются формы2i.

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

_(DO ((x 5 (+ x 1)) (y 8 (+ y 2)) (рез 0))

((< x 10) рез)

(SETQ рез (+ рез x y))

5. Передача управления.

На Лиспе можно писать программы и в обычном операторном стиле с использованием передачи управления. Однако во многих системах не рекомендуется использовать эти предложения, так как их можно заменить другими предложениями (например DO) и, как правило, в более понятной форме. Но мы рассмотрим предложения передачи управления, хотя использовать их не следует.

(PROG (m1 m2 ... mn)

оператор1

оператор2

...

операторm)

Перечисленные в начале формы переменные mi являются локальными статическими переменными формы, которые можно использовать для хранения промежуточных результатов. Если переменных нет, то на месте списка переменных нужно ставить NIL. Если какая-нибудь форма операторi является символом или целым числом, то это метка перехода. На такую метку можно передать управление оператором GO:

(GO метка)

GO не вычисляет значение своего «аргумента».

Кроме этого, в PROG-механизм входит оператор окончания вычисления и возврата значения:

(RETURN результат)

Операторы предложения PROG вычисляются слева направо (сверху вниз), пропуская метки перехода. Оператор RETURN прекращает выполнение предложения PROG; в качестве значения всего предложения возвращается значение аргумента оператора PROG. Если во время вычисления оператор RETURN не встретился, то значением PROG после вычисления его последнего оператора станет NIL .

После вычисления значения формы связи программных переменных исчезают.

6. Задания к лабораторной работе.

1. Запишите следующие лямбда-вызовы с использованием формы LET и вычислите их на машине:

a) ((LAMBDA (x y) (LIST x y)

‘(+ 1 2) ‘c);

b) ((LAMBDA (x y) ((LAMBDA (z) (LIST x y z)) ‘c)

‘a ‘b);

c) ((LAMBDA (x y) (LIST x y))

((LAMBDA (z) z) ‘a)

‘b).

2. Напишите с помощью композиции условных выражений функции от четырех аргументов AND4(x1 x2 x3 x4) и OR4(x1 x2 x3 x4), совпадающие с функциями AND и OR от четырех аргументов.

3. Пусть L1 и L2 - списки. Напишите функцию, которая возвращала бы T, если N-ые два элемента этих функций соответственно равны друг другу, и NIL в противном случае.

4. Написать условное выражение (используя COND), которое:

1. дает NIL, если L атом, и T в противном случае;

2. выдает для списка L ,состоящего из трех элементов, первый из этих трех, который является атомом, или список, если в списке нет элементов атомов.

5. С помощью предложений COND или CASE определите функцию, которая возвращает в качестве значения столицу заданного аргументом государства.

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

7. Запрограммируйте с помощью предложения DO функцию факториал.

8. Запишите с помощью предложения PROG функцию (аналог встроенной функции LENGTH), которая возвращает в качестве значения длину списка (количество элементов на верхнем уровне).

9. Используя функцию COND, напишите функцию, которая спрашивает у пользователя ФИО двух студентов из группы (список группы составлен раньше) для которых:

а) сравнивает год рождения и выдает результат (кто старше или что они ровесники);

б) сравнивает средний бал и выдает сообщение о результатах сравнения;

с) проверяет родственные связи (если одни и те же родители, то они родственники) и выдает об этом сообщение.

10. Напишите подобные функции, но уже используя функцию IF.

Для двух последних заданий вывод информации осуществить при помощью функций PRINT, PRIN1, PRINC.

Center - находит среднее из трех чисел:

(DEFUN center (x y z)

(COND ((> x y) (IF (< x z) (PROGN (PRINT x)

(PRINT «среднее (1)»))

(IF (> y z) (PROGN (PRINT y)

(TERPRI)

(PRINT «среднее (2)»))

(PROGN (PRIN1 z)

(PRIN1«среднее (3)»)))))

((< x y) (IF (< y z) (PROGN (PRIN1 y)

(TERPRI)

(PRIN1 «среднее (4)»))

(IF (> x z) (PROGN (PRINC x)

(PRINC «среднее (5)»))

(PROGN (PRINC z)

(TERPRI)

(PRINC «среднее (6)»)))))

(T (PRINC «ошибка ввода»))))

7. Вопросы.

1. Для чего используется предложение LET?

2. В чем его отличие от предложения LET*?

3. Чем различаются функции COND и IF?

4. Каковы возвращаемые ими значения?

5. Чем различаются функции PROG1 и PROGN?

6. Почему не желательно использовать операторы передачи управления? Чем их можно заменить?

Лабораторная работа №4.

Тема: Рекурсия в Лиспе. Функционалы и макросы.

Цель: Изучить основы программирования с применением рекурсии. Научиться работать с функционалами и макросами.

1. Рекурсия. Различные формы рекурсии.

2. Применяющие функционалы.

3. Отображающие функционалы.

4. Макросы.

5. Задание к лабораторной работе.

6. Вопросы.

1. Рекурсия. Различные формы рекурсии.

Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекуррентных формул свести к некоторым начальным значениям, к ранее определенным функциям или к самой определяемой функции, но с более «простыми» аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям.

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

Будем говорить о рекурсии по значению и рекурсии по аргументам. В первом случае вызов является выражением, определяющим результат функции. Во втором - в качестве результата функции возвращается значение некоторой другой функции и рекурсивный вызов участвует в вычислении аргументов этой функции. Аргументом рекурсивного вызова может быть вновь рекурсивный вызов и таких вызовов может быть много.

Рассмотрим следующие формы рекурсии:

• простая рекурсия;

• параллельная рекурсия;

• взаимная рекурсия.

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

Для примера напишем функцию вычисления чисел Фибоначчи (F(1)=1; F(2)=1; F(n)=F(n-1)+F(n-2) при n>2):

(DEFUN FIB (N)

(IF (> N 0)

(IF (OR N=1 N=2) 1

(+ (FIB (- N 1)) (FIB (- N 2))))

‘ОШИБКА_ВВОДА))

Рекурсию называют параллельной, если она встречается одновременно в нескольких аргументах функции:

(DEFUN f ...

...(g ... (f ...) (f ...) ...)

...)

Рассмотрим использование параллельной рекурсии на примере преобразования списочной структуры в одноуровневый список:

(DEFUN PREOBR (L)

(COND

((NULL L) NIL)

((ATOM L) (CONS (CAR L) NIL))

(T (APPEND

(PREOBR (CAR L))

(PREOBR (CDR L))))))

Рекурсия является взаимной между двумя и более функциями, если они вызывают друг друга:

(DEFUN f ...

...(g ...) ...)

(DEFUN g ...

...(f ...) ...)

Для примера напишем функцию обращения или зеркального отражения в виде двух взаимно рекурсивных функций следующим образом:

(DEFUN obr (l)

(COND ((ATOM l) l)

(T (per l nil))))

(DEFUN per (l res)

(COND ((NULL l) res)

(T (per (CDR l)

(CONS (obr (CAR l)) res)))))

2. Применяющие функционалы.

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

APPLY

APPLY является функцией двух аргументов, из которых первый аргумент представляет собой функцию, которая применяется к элементам списка, составляющим второй аргумент функции APPLY:

(APPLY fn список)

_(SETQ a ‘+) ð +

_(APPLY a ‘(1 2 3)) ð 6

_(APPLY ‘+ ‘(4 5 6)) ð 15

FUNCALL.

Функционал FUNCALL по своему действию аналогичен APPLY, но аргументы для вызываемой он принимает не списком, а по отдельности:

(FUNCALL fn x1 x2 ... xn)

_(FUNCALL ‘+ 4 5 6) ð 15

FUNCALL и APPLY позволяют задавать вычисления (функцию) произвольной формой, например, как в вызове функции, или символом, значением которого является функциональный объект. Таким образом появляется возможность использовать синонимы имени функции. С другой стороны, имя функции можно использовать как обыкновенную переменную, например для хранения другой функции (имени или лямбда-выражения), и эти два смысла (значение и определение) не будут мешать друг другу:

_(SETQ list ‘+) ð +

_(FUNCALL list 1 2) ð 3

_(LIST 1 2) ð (1 2)

3. Отображающие функционалы.

Отображающие или MAP-функционалы являются функциями, которые являются функциями, которые некоторым образом отображают список (последовательность) в новую последовательность или порождают побочный эффект, связанный с этой последовательностью. Каждая из них имеет более двух аргументов, значением первого должно быть имя определенной ранее или базовой функции, или лямбда-выражение, вызываемое MAP-функцией итерационно, а остальные аргументы служат для задания аргументов на каждой итерации. Естественно, что количество аргументов в обращении к MAP-функции должно быть согласовано с предусмотренным количеством аргументов у аргумента-функции. Различие между всеми MAP-функциями состоит в правилах формирования возвращаемого значения и механизме выбора аргументов итерирующей функции на каждом шаге.

Рассмотрим основные типы MAP-функций.

MAPCAR.

Значение этой функции вычисляется путем применения функции fn к последовательным элементам xi списка, являющегося вторым аргументом функции. Например в случае одного списка получается следующее выражение:

(MAPCAR fn ‘(x1 x2 ... xn))

В качестве значения функционала возвращается список, построенный из результатов вызовов функционального аргумента MAPCAR.

_(MAPCAR ‘LISTP ‘((f) h k (i u)) ð (T NIL NIL T)

_(SETQ x ‘(a b c)) ð (a b c)

_(MAPCAR ‘CONS x ‘(1 2 3)) ð ((a . 1) (b . 2) (c . 3))

MAPLIST.

MAPLIST действует подобно MAPCAR, но действия осуществляет не над элементами списка, а над последовательными CDR этого списка.

_(MAPLIST ‘LIST ‘((f) h k (i u)) ð (T T T T)

_(MAPLIST ‘CONS ‘(a b c) ‘(1 2 3)) ð (((a b c) 1 2 3) ((b c) 2 3) ((c ) 3))