Поиск на лиспе. Функционалы. Свойства символов

ЛЕКЦИЯ 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)
(nth 1 state))

(defun goat-side (state)
(nth 2 state))

(defun cabbage-side (state)
(nth 3 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))

Эта версия функции path является простым переводом и содержит несколько ошибок, которые надо исправить. В частности, отметим использование формы OR для управления выполнением ее аргументов.

Напомним,что OR выполняет свои аргументы до тех пор, пока один из них не вернет не-nil величину. Когда это случается, OR завершается без выполнения других аргументов и возвращает это не-nil, как результат.

Таким образом, OR используется не только как логический оператор, но также обеспечивает способ управления поиском пути. OR используется здесь вместо cond, потому что величина, которая тестируется, и величина, которая возвращается в случае не-nil, одна и та же.

Одна проблема с этим определением заключается в том,что функция перемещения может вернуть значение nil, если перемещение не может быть сделано, когда оно ведет не к безопасному состоянию, чтобы предотвратить

path от попытки генерировать дочерние состояния от состояния

nil, она ( path), должна сначала проверять, является ли текущее состояние nil, если да, то path должна вернуть nil.

Другая проблема,которая возникает в реализации path, заключается в возможности возникновения петель в пространстве состояний. Если данную реализацию path запустить, фермер будет ездить взад-вперед между двумя берегами бесконечно, то есть алгоритм приведет к бесконечным переходам между двумя одинаковыми состояниями.

Чтобы предотвратить это, в path надо ввести третий параметр, been-list, список всех состояний, которые уже были достигнуты.

Аргумент, значением которого является функция, называют

функциональным аргументом , а функцию, имеющую функциональный аргумент -

функционалом.

Различие между понятиями

"данные" и

" функция", определяются не на основе их структуры, а в зависимости от использования.

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

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

Отображающий функционал MAPCAR

Важный класс функционалов используемых в лиспе -

отображающие функционалы (МАР функционалы)

МАР функционалы - функции, которые некоторым образом отображают (map) список в новый список.

MAPCAR один из основных отображающих функционалов.

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

В качестве аргумента для MAPCAR

может быть использовано значение символа

* (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
свойство	значение

Список свойств в этом случае выглядит

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