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

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. Напишите функцию:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

c) (FUNCALL ‘APPLY ‘LIST ‘(a b));

d) (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))))))) ;* сопоставима с несколь ;кими атомами

Вопросы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вопросы.

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

В Лиспе существует понятие точечной пары. Название точечной пары происходит из использованной в ее записи точечной нотации, в которой для разделения полей 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 последнего элемента списка, символизирующий его окончание.

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