ЛИСП

(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))


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

Функции MAPCAN и MAPCON являются аналогами функций MAPCAR и MAPLIST. Отличие состоит в том, что MAPCAN и MAPCON не строят, используя LIST, новый список из результатов, а объединяют списки, являющиеся результатами, в один список.


4. Макросы.

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

Синтаксис определения макроса выглядит так же, как синтаксис используемой при определении функций формы DEFUN:

(DEFMACRO имя лямбда-список тело)

Вызов макроса совпадает по форме с вызовом функции, но его вычисление отличается от вычисления вызова функции. Первое отличие состоит в том, что в макросе не вычисляются аргументы. Тело макроса вычисляется с аргументами в том виде, как они записаны.

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


_(DEFMACRO setqq (x y)

(LIST ‘SETQ x (LIST ‘QUOTE y))) р setqq

_(setqq a (b c)) р (b c)

_a р (b c)


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


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

1. Напишите рекурсивную функцию, определяющую сколько раз функция FIB вызывает саму себя. Очевидно, что FIB(1) и FIB(2) не вызывают функцию FIB.

2. Напишите функцию для вычисления полиномов Лежандра (P0(x)=1, P1(x)=x, Pn+1(x)= ((2*n+1)*x*Pn(x)-n*Pn-1(x))/(n+1) при n>1).

3. Напишите функцию:

  1. вычисляющую число атомов на верхнем уровне списка (Для списка (а в ((а) с) е) оно равно трем.);

  2. определяющую число подсписков на верхнем уровне списка;

  3. вычисляющую полное число подсписков, входящих в данный список на любом уровне.

4. Напишите функцию:

  1. от двух аргументов X и N, которая создает список из N раз повторенных элементов X;

  2. удаляющую повторные вхождения элементов в список;

  3. которая из данного списка строит список списков его элементов, например, (a b) р ((a) (b));

  4. вычисляющую максимальный уровень вложения подсписков в списке;

  5. единственным аргументом которой являлся бы список списков, объединяющую все эти списки в один;

  6. зависящую от трех аргументов X, N и V, добавляющую X на N-е место в список V.

5. Напишите функцию:

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

  2. которая должна производить замены X на Y только на верхнем уровне W;

  3. заменяющую Y на число, равное глубине вложения Y в W, например Y=A, W=((A B) A (C (A (A D)))) р ((2 B) 1 (C (3 (4 D))));

  4. аналогичную функции SUBST, но производящую взаимную замену X на Y, т. е. X р Y, Y р X.

6. Вычислите значения следующих вызовов:

  1. (APPLY ‘LIST ‘(a b));

  2. (FUNCALL ‘LIST ‘(a b));

  3. (FUNCALL ‘APPLY ‘LIST ‘(a b));

  4. (FUNCALL ‘LIST ‘APPLY ‘(a b);

7. Определите функционал (A-APPLY f x), который применяет каждую функцию fi списка

f = (f1 f2 ... fn)

к соответствующему элементу xi списка

x = (x1 x2 ... xn)

и возвращает список, сформированный из результатов.

8. Определите функциональный предикат (КАЖДЫЙ пред список), который истинен в том и только в том случае, когда, являющийся функциональным аргументом предикат пред истинен для всех элементов списка список.

9. Определите функциональный предикат (НЕКОТОРЫЙ пред список), который истинен, когда предикат истинен хотя бы для одного элемента списка.

10. Определите FUNCALL через функционал APPLY.

11. Определите функционал (MAPLIST fn список) для одного списочного аргумента.

12. Определите макрос, который возвращает свой вызов.

13. Определите лисповскую форму (IF условие p q) в виде макроса.


Примеры написания функций.

;Subst - заменяет все вхождения Y в W на X.

(DEFUN subst (x y w)

(COND ((NULL w) NIL) ;проверка на окончание списка

((EQUAL ‘y ‘w) x)

((ATOM ‘w) w) ;

(t (CONS (subst x y (car w)) ;поиск в глубину

(subst x y (cdr w)))))) ;поиск в ширину


;COMPARE1 - сравнение с образцом

(defun compare1 (p d)

(cond ((and (null p) (null d)) t) ;исчерпались списки?

((or (null p) (null d)) nil) ;одинакова длина списков?

((or (equal1 (car p) '&) ;присутствует в образце атом &

(equal1 (car p) (car d))) ;или головы списков равны

(compare1 (cdr p) (cdr d))) ;& сопоставим с любым атомом

((equal1 (car p) '*) ;присутствует в образце атом *

(cond ((compare1 (cdr p) d)) ;* ни с чем не сопоставима

((compare1 (cdr p) (cdr d))) ;* сопоставима с одним атомом

((compare1 p (cdr d))))))) ;* сопоставима с несколь ;кими атомами


6. Вопросы.

1. Что такое рекурсия?

2. Назовите достоинства ее использования?

3. Что такое функционал?

4. Назовите особенности применяющих и отображающих функционалов?

5. Для чего они используются?

6. Что такое макрос?

7. Когда их используют?

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

Тема: Типы данных и средства работы с ними. Представление знаний.

Цель: Изучить типы данных, используемые в MuLisp, а так же научиться применять их в программах.


  1. Точечная нотация.

  2. Структурированные типы данных.

  3. Представление знаний.

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

  5. Вопросы.

1. Точечная нотация.

В Лиспе существует понятие точечной пары. Название точечной пары происходит из использованной в ее записи точечной нотации, в которой для разделения полей CAR и CDR используется выделенная пробелами точка. Базовые функции CAR и CDR действуют совершенно симметрично.


_(CONS ‘a ‘d) р (a . d)

_(CAR ‘(a . b)) р a

_(CDR ‘(a . (b . c))) р (b . c)


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

(a1 a2 ... an) у (a1 . (a2 . ...(an . nil)... ))


_(a b c (d e)) у (a . (b . (c . ((d . (e . nil)) . nil))))


Признаком списка здесь служит NIL в поле CDR последнего элемента списка, символизирующий его окончание.

Использование точечных пар в программировании на Лиспе в общем-то излишне. Точечные пары применяются в теории, книгах и справочниках по Лиспу. Кроме того они используются совместно с некоторыми типами данных и с ассоциативными списками, а также в системном программировании.


2. Структурированные типы данных.

Списки (ассоциативные).

Ассоциативный список или просто а-список - состоит из точечных пар, поэтому его также называют списком пар.

((a1 . t1)

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: