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

Функционалы 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) (a2 . t2) ... (an . tn))

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

В работе со списками пар нужно уметь строить списки, искать данные по ключу и обновлять их.

PAIRLIS.

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

(PAIRLIS ключи данные а-список)

_(SETQ спис ‘(один . Иванов)) ð (один . Иванов)

_(SETQ спис

(PAIRLIS ‘(три два) ‘(Петров Сидоров)

спис)) ð ((три . Петров) (два . Сидоров) (один . Иванов))

ASSOC.

Ассоциативный список можно считать отображением из множества ключей в множество значений. Данные можно получить с помощью функции

(ASSOC ключ а-список)

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

_(ASSOC ‘три спис) ð (три . Петров)

ACONS.

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

(ACONS x y а-список)

Поскольку ASSOC просматривает список слева направо и доходит лишь до первой пары с искомым ключом, то более старые пары как бы остаются в тени более новых.

Строки.

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

При вводе строки в интерпретаторе, в качестве результата получаем ту же строку.

CHAR.

Произвольный элемент строки можно прочитать (т. е. сослаться на него с помощью индекса) функцией CHAR:

(CHAR строка n)

(CHAR «строка» 0) ð \с ;индексация начинается с 0

Сравнение строк.

(STRING= строка1 строка2)

(STRING< строка1 строка2)

(STRING> строка1 строка2)

(STRING/= строка1 строка2)

Массивы.

Для работы с массивами в MuLisp необходимо загрузить файл ARRAY.LSP.

Массивы создаются формой:

(MAKE-ARRAY (n1 n2 ... nN) режимы)

Функция возвращает в качестве значения новый объект - массив. n1, n2, ... nN - целые числа, их количество N отражает размерность массива, а значения - размер по каждой размерности. Необязательными аргументами можно задать тип элементов массива, указать их начальные значения или придать самому массиву динамический размер. Общий размер массива в этом случае знать и закреплять не обязательно.

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

(ARREF массив n1 n2 ...nN)

n1, n2, ..., nN - координаты, или индексы, элемента, на который ссылаются. В качестве функции присваивания используется обобщенная функция присваивания SETF.

_(SETQ мас (MAKE-ARRAY ‘(5 4)

:ELEMENT-TYPE ‘ATOM

:INITIAL-ELEMENT A)) ð (ARRAY ((A A A A) ... (A A A A) (5 6)))

_(SETF (AREF мас 0 1) B) ð B

_мас ð (ARRAY ((A B A A) ... (A A A A )))

Структуры.

Для объединения основных типов данных (чисел, символов, строк, массивов) в комплексы, отображающие предметы, факты используется составной тип, который называется структурами.

Определение структурного типа осуществляется с помощью макроса DEFSTRUCT, формой которого является

(DEFSTRUCT класс-структур

поле1

поле2

...)

Определим структурный тип БАЗА состоящий из компонент ПРОФИЛЬ, ПЛОЩ и ВМЕСТИМ:

_(DEFSTRUCT база

профиль площ вместим) ð БАЗА

Для каждого нового типа данных генерируется начинающаяся с MAKE- функция создания структуры данного типа. Например объект типа БАЗА можно создать и присвоить переменной БАЗА1 следующим вызовом:

_(SETQ БАЗА1 (MAKE-БАЗА))

Полю с помощью ключевого слова, которым является имя поля с двоеточием перед ним, присвоить при создании начальное значение.

Вызов MAKE-БАЗА возвращает в качестве значения созданную структуру.

Для копирования структуры генерируется функция, начинающаяся с COPY- (COPY-БАЗА).

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

_(БАЗА-ПРОФИЛЬ x)

Вызов возвращает значение поля ПРОФИЛЬ для БАЗЫ, задаваемой структурой x.

Для присваивания значений полям структуры используется обобщенная функция присваивания SETF:

_(SETF (БАЗА-ПРОФИЛЬ БАЗА1) ОВОЩ) ð ОВОЩ

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

Продукционные системы