Lr_2_LISP
.doc2) Функция MAPLIST - применяет функцию, заданную в качестве ее второго аргумента (функционального), последовательно ко всему списку, заданному в качестве значения первого аргумента, и ко всем спискам, поочередно получаемым отбрасыванием первого элемента от предыдущего списка. Значением функции MAPLIST является список полученных результатов.
3) Функция MAPCAR - подобна функции MAPLIST и отличается от нее тем, что заданная функция применяется к первым элементам тех списков, к которым она применялась бы в случае обращения к MAPLIST.
4) Функция MAP - имеет смысл, если функция F, заданная в качестве ее второго аргумента, обладает каким-либо побочным эффектом. Эта функция последовательно применяется к тем же аргументам, что и в случае функции MAPLIST, но выработанные значения никак не используются и не сохраняются. Значение функции MAP равно NIL (а если очередной аргумент, подготовленный для обращении к функции F, окажется атомом, то этому атому).
I) Списки свойств
1) Функция PUTPROP - помещает в список свойств атома, указанного в качестве ее первого аргумента, свойство, представленное значением третьего аргумента, с индикатором, заданным в виде значения второго аргумента. В качестве результата функция PUTPROP вырабатывает атом, список свойств которого подвергся изменению. Если в списке свойств этого атома уже было свойство с данным индикатором, то это свойство замещается новым, индикатор не дублируется.
2) Функция GETPROP - извлекает из списка свойств данного атома (значения первого аргумента) свойство с данным индикатором(значением второго аргумента). Если такого индикатора в списке свойств нет, то вырабатывается значение NIL.
3) Функция PROP - отличается от функции GETPROP тем, что она выдает в качестве результата не свойство, связанное с данным индикатором (если оно есть в списке), а весь хвост списка свойств, следующий за найденным индикатором. Если же индикатор в списке свойств не обнаруживается, то производится обращение к функции без аргументов, наименование или определяющее выражение которой должно быть задано в качестве третьего аргумента PROP. Результат этого обращения выдается в этом случае в качестве результата обращения к PROP.
4) Функция REMPROP - удаляет из списка свойств данного атома (значения первого аргумента в обращении к ней) свойство, снабженное данным индикатором (значение второго аргумента), вместе с этим индикатором. Если такого индикатора не было, то список свойств не меняется. Значение функции совпадает со значением первого аргумента.
5) Функция REMPROPS - удаляет все свойства символа.
6) Предикат HASPROP - проверяет, обладает ли символ (первый аргумент) данным индикатором (второй аргумент).
J) Работа с упорядоченными бинарными деревьями
Упорядоченное бинарное дерево состоит из узлов вида:
(<элемент> <левое поддерево> <правое поддерево>).
В каждом узле выполнено следующее условие: все элементы из узлов его левого поддерева в некотором урорядочении (например, по числовой величине или в алфавитном порядке) предшествуют элементу из узла и соответственно элементы из узлов правого поддерева следуют за ним. Пример:
(5 (3 (1 NIL NIL)
(4 NIL NIL)
(7 (6 NIL NIL)
(13 (11 NIL NIL)
(15 NIL NIL))))
1) Функция FINDBT - ищет в дереве данный элемент.
2) Функция ADDBT - добавляет в дерево данный элемент. (Замечание: копируйте дерево по пути поиска и подправляйте нужное поддерево).
3) Функция PREDBT - выделяет в отдельное (упорядоченное) дерево из первоначального дерева все узлы, предшествующие данному элементу.
4) Функция POSTBT - выделяет в отдельное (упорядоченное) дерево из первоначального дерева все узлы, следующие за данным элементом.
5) Функция UNIONBT - объединяет два упорядоченных дерева в одно общее упорядоченное дерево (Замечание: используйте функции PREDBT и POSTBT).
K) Разные процедуры формирования списков
1) Функция BULB (ЛУКОВИЦА) - строит N-уровневый вложенный список, элементом которого на самом глубоком уровне является N.
2) Функция FACT - результатом является выражение, являющееся факториалом числа, в котором числа (сомножители) упорядочены в порядке возрастания.
3) Функция FIBON - порождает последовательность чисел Фибоначчи. Числа Фибоначчи определяются следающим рекуррентным соотношением: F(n+1)=F(n)+F(n-1), при F(0)=1, F(1)=2.
4) Функция INTERPR - преобразует инфиксную запись операций выражения в префиксную и возвращает значение выражения.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Чем отличаются символы от атомов в языке Лисп ?
2. В каких случаях выдается ошибка при попытке интерпретировать S-выражение ?
3. Перечислите базовые функции языка Лисп. Каковы типы их аргументов, и какие значения они возвращают в качестве результата ?
4. Вычислите значения следующих выражений:
a) '(CAR '(A B C))
б) (EVAL '(CAR '(A B C)))
с) (EVAL (CAR '(A B C)))
д) (EVAL (QUOTE (QUOTE QUOTE)))
е) (QUOTE (EVAL (QUOTE (QUOTE QUOTE))))
5. Каково будет значение атома A после следующих вызовов:
a) (SET (SETQ A 'A) 'B)
б) (SET (SETQ B 'A)(SETQ A 'C))
(SET B A)
6. Какое значение возвращает функция COND ?
7. Какое условие должно стоять первым в определении рекурсивной функции ?
8. Назовите функции с побочными эффектами. В чем заключается этот эффект ?