Поиск на лиспе. Функционалы. Свойства символов
ЛЕКЦИЯ 7.
ПОИСК НА ЛИСПЕ. ФУНКЦИОНАЛЫ. СВОЙСТВА СИМВОЛОВ
Содержание
7.1 Алгоритм поиска на Лиспе.
( Функциональный подход к задаче о фермере,волке,козе и капусте.)
Фермер (Farmer), волк (Wolf), козел (Goat) и капуста (Cabbidge) находятся на одном берегу. Надо перебраться на другой берег на лодке.
 |
- Лодка перевозит только двоих.
- Нельзя оставлять на одном берегу козу и капусту, козу и волка.
 |
Главная проблема в формировании алгоритма - найти эффективное представление структурой данных Лиспа информации о задаче.
Процесс перевозки может быть представлен последовательностью состояний. Состояние представляется списком из четырех элементов, каждый из которых отражает размещение объектов F, W, G, C:
(e w e w) - F, G на восточном берегу (e - east);
F W G C - W, C на западном берегу (w - west).
 |
Определим две функции:
конструктор - make-state, которая берет в качестве аргументов размещение F, W, G, C
и возвращает состояние
 |
(defun make-state (f w g c) (list f w g c)) |
 |
и четыре функции доступа, каждая из которых берет состояние и возвращает размещение.
| |
(defun farmer-side (state) (nth 0 state)) (defun wolf-side (state) (defun goat-side (state) (defun cabbage-side (state) |
 |
Оставшаяся программа основывается на этих функциях доступа и конструкторах. В частности, они используются для реализации четырех возможных действий фермера:
- перевоз через реку или самого себя или W, G, C.
Эти функции используют четыре функции доступа для разбиения состояния на его компоненты.
Функция opposite ( определена позже ) определяет новое размещение объектов, которые пересекли реку, а make-state собирает их в новое состояние.
Например, функция farmer-takes-self может быть определена:
| |
(defun farmer-take-self (state) (safe (make-state (opposite (farmer-side state)) (wolf-side state) (goat-side state) (cabbage-side state)))) |
Отметим, что эта функция возвращает новое состояние, независимо от того, безопасно оно или нет.
Если состояние безопасно, оно будет возвращено без изменений.
| |
(defun safe (state) (cond ((and (equal (goat-side state) (wolf-side state)) (not (equal (farmer-side state) (wolf-side state)))) nil) ((and (equal (goat-side state) (cabbage-side state)) (not (equal (farmer-side state) (goat-side state)))) nil) (t state))) |
| |
(defun path (state goal) (cond ((equal state goal)) (t (or (path (farmer-takes-self state) goal))) (path (farmer-take-wolf state) goal) (path (farmer-take-goat state) goal) (path (farmer-take-cabbage state) goal)) |
Напомним,что OR выполняет свои аргументы до тех пор, пока один из них не вернет не-nil величину. Когда это случается, OR завершается без выполнения других аргументов и возвращает это не-nil, как результат.
Таким образом, OR используется не только как логический оператор, но также обеспечивает способ управления поиском пути. OR используется здесь вместо cond, потому что величина, которая тестируется, и величина, которая возвращается в случае не-nil, одна и та же.
Одна проблема с этим определением заключается в том,что функция перемещения может вернуть значение nil, если перемещение не может быть сделано, когда оно ведет не к безопасному состоянию, чтобы предотвратить
path от попытки генерировать дочерние состояния от состояния
nil, она ( path), должна сначала проверять, является ли текущее состояние nil, если да, то path должна вернуть nil.
Другая проблема,которая возникает в реализации path, заключается в возможности возникновения петель в пространстве состояний. Если данную реализацию path запустить, фермер будет ездить взад-вперед между двумя берегами бесконечно, то есть алгоритм приведет к бесконечным переходам между двумя одинаковыми состояниями.
Чтобы предотвратить это, в path надо ввести третий параметр, been-list, список всех состояний, которые уже были достигнуты.
Аргумент, значением которого является функция, называют
функциональным аргументом , а функцию, имеющую функциональный аргумент -
функционалом.
Различие между понятиями
"данные" и
" функция", определяются не на основе их структуры, а в зависимости от использования.
Если аргумент используется в функции, как объект участвующий в вычислениях, то это данные..
Если аргумент используется как средство, определяющее вычисления, то это функция.
Отображающий функционал MAPCAR
Важный класс функционалов используемых в лиспе -
отображающие функционалы (МАР функционалы)
МАР функционалы - функции, которые некоторым образом отображают (map) список в новый список.
 |
(MAPCAR f '(x1 x2 x3 ... xN))
MAPCAR функционал имеет два аргумента.
Первый аргумент - функция,
а второй - аргумент список.
| Когда MAPCAR выполняется , функция определенная первым аргументом применяется к каждому элементу, списка, определенному вторым аргументом и результат помещает (отображает) в новый список. |
| |
* (mapcar 'add1 '( 1 2 3)) (2 3 4) (MAPCAR f '(x1 x2 x3 ... xN)) эквивалентно (list (f 'x1) (f 'x2) .... (f 'xN)) |
| |
(defun list-add1 (lis) (mapcar 'add1 lis)) * (list-add1 '(1 2 3)) (2 3 4) |
может быть использовано значение символа
| |
* (setq x '(a b (d))) * (setq y 'atom) * (mapcar y x) (t t nil) |
MAPCAR для нескольких списков
MAPCAR может обрабатывать больше списков, если в функциональном аргументе несколько аргументов.
 |
| |
* (defun addlist (l1 l2) (mapcar '+ l1 L2)) * (addlist '( 1 2 3) '(1 2 3)) (2 4 6) т.е. (list (+ 1 1) (+ 2 2) (+ 3 3)) |
Лямбда выражения
Структура МАР функций ограничивает формы отображаемых функций.
Так, если мы желаем получить список с элементами
| |
x * x + 1 Мы должны определить функцию (defun f1 (x) (+ 1 (* x x))) * (mapcar 'f1 '(1 2 3)) |
/p>
Таким образом определяется специальная функция, которая используется только в MAPCAR.
Аналогично происходит с add1.
Более эффективно в этом случае использовать, т.н.
лямбда выражения:
| |
(mapcar '(lambda (x) (+ 1 (* x x))) '(1 2 3)) сравни (defun f1 (x) (+ 1 (* x x))) (mapcar '(lambda (x) (+ 1 x)) '(1 2 3)) |
Лямбда-выражения определяют функцию не имеющую имени.
Общая форма:
(lambda (параметры) )
Cвойства символов
В лиспе с символом можно связывать, не только
значение, но и информацию, называемую списком
свойств (property list).
Например, рассмотрим информацию o Mary:
| |
|
(aqe 28 occupation lawyer salary 90 children ( Bill Alice Susan))
Чтение свойства
Узнать свойство атома можно используя функцию:
(GET <cимвол> <свойство>) возвращает значение
| |
* ( get 'Mary 'age) 28 * ( get 'Mary 'children) ( Bill Alice Susan)) * ( get 'Mary 'hobby) nil |
Присвоение свойства
Чтобы задать свойство необходимо использовать обобщенную функцию присвоения
setf
( setf ( get <символ> <свойство>) <значение>)
| |
* ( setf ( get 'Mary 'salary) 90) 90 |
putprop:
( putprop <символ> <значение> <свойство>)
<свойство> - нечисловой атом;
<значение> - любое выражение ;
Можно определить
| |
(defun putprop ( atom value property) (setf (get atom property) value)) |
Свойств у атома может быть много, но у каждого только одно значение.
При внесении нового свойства, оно помещается вначале списка свойств.
| |
* (putprop 'Mary 'cinema 'hobby) ( hobby cinema .....) |
Замена свойства
Замена значения свойства производится
повторным присвоением.
Например,
| |
(putprop 'mary 29 'age) (get 'mary 'age) |
| |
(putprop 'mary (+ 1 (get 'mary 'age)) 'age) |
Удаление свойства
Удаление свойства и его значения производится функцией
(remprop <символ> <свойство>)
| |
*(remprop 'Mary 'age) T |
SYMBOL-PLIST
SYMBOL-PLIST даст информацию о списке свойств
| |
* ( SYMBOL-PLIST 'Mary) (aqe 28 occupation lawyer salary 90 children ( Bill Alice Susan)) |
