Точно Не проект 2 / Не books / Источник_1
.pdf280 |
Глава 5 |
|
|
Однако макрос имеет существенные отличия от функций. Вопервых, вычисление вызова макроса состоит из двух этапов. На первом этапе осуществляется вычисление тела макроопределения с аргументами, заданными при вызове. В отличие от функций аргументы макровызова не вычисляются, а подставляются в тело макроопределения в той форме, в которой они были заданы. Благодаря этому на первом этапе выполняется построение некоторой формы, соответствующей определению макроса. Этот этап называют макрорасширением, или раскрытием макроса. На втором этапе происходит вычисление раскрытой формы макроса, и в качестве результата возвращается значение этой формы. Во-вторых, на этапе макрорасширения действуют связи, соответствующие текстуальному окружению макроопределения, т.е. макрорасширение аналогично вычислению функции в отношении связей аргументов и переменных. Однако во время вычисления расширенной формы макроса лексические связи, устанавливаемые в макроопределении, уже не действуют.
Рассмотрим пример, демонстрирующий отличие макроса от функции. Пусть требуется запрограммировать операцию добавления элемента в стек. Решим эту задачу, определив сначала функцию, а затем макрос. Функцию, добавляющую элемент в стек, можно определить следующим образом:
(defun our-push (element stack)
(setf stack (cons element stack)))
Следующий вызов функции OUR-PUSH
(setf w ’(a b c)) (A B C) (our-push 11 w) (11 A B C)
показывает, что она возвращает необходимый результат. Вместе с тем, если попытаться вычислить значение переменной W, то получим:
w (A B C)
Это объясняется тем, что фактический параметр W передается в функцию OUR-PUSH по значению. Переменная STACK является локальной, и ее значение недоступно вне функции OUR-PUSH.
Решим поставленную выше задачу посредством макроса:
(defmacro our-push (element stack)
(list ’setf stack (list ’cons element stack)))
На этапе расширения данного макроса возникает форма
(setf stack (cons element stack))
Язык Лисп |
281 |
|
|
С целью облегчения чтения макрорасширений и упрощения написания макросов, применяют обратную блокировку. Например, приведенное выше макроопределение можно также записать в виде:
(defmacro our-push (element stack)
‘(setf ,stack (cons ,element ,stack)))
Здесь обратно-блокированный список задает прежнее макрорасширение, которое, безусловно, воспринимается легче, чем в первом случае.
Теперь макровызов OUR-PUSH не только вернет правильный результат, но и изменит глобальное значение W:
(setf w ’(a b c)) ( a b c)
(our-push 11 w) (11 a b c) w (11 a b c)
Это происходит потому, что локальные связи формальных параметров ELEMENT и STACK действуют только на первом этапе вычисления макроса, т.е. на этапе макрорасширения. На этапе вычисления раскрытой формы макроса действуют внешние связи указанных параметров.
Макросы представляют мощный инструмент вычислений, который позволяет определять новые синтаксические формы, новые типы данных, программы, формирующие другие программы, и др. Однако при написании макросов могут возникать неожиданные макрорасширения, которые приводят к ошибкам. Поиск ошибок в определении макроса намного сложнее, чем поиск ошибки в функции. Для тестирования макросов существуют специальные функции MACROEXPAND-1 и MACROEXPAND, которые строят расширения макровызова:
(macroexpand-1 макровызов)
Например,
(macroexpand-1 ’(our-push 11 W))(setf w (cons 11 w))
T
Функция MACROEXPAND-1 выполняет макрорасширения один раз, а функция MACROEXPAND – многократно, т.е. она позволяет раскрывать вложенные макроформы.
При написании макросов полезно соблюдать следующую последовательность действий. Во-первых, записать макровызов в желаемой форме. Например,
(our-pop stack)
282 |
Глава 5 |
|
|
Во-вторых, определить выражение, выполняющее необходимые операции по преобразованию данных. Например,
(prog1 (car stack) (setf stack (cdr stack))
В данном случае выполняются два действия. Сначала выделяется первый элемент списка, представленного переменной STACK, а затем в ней сохраняется хвост списка. В качестве результата форма PROG1 возвратит значение первого элемента списка, т.е. в данном случае извлекается элемент из стека. В-третьих, записать макроопределение в соответствии с определенным выше выражением. Например,
(defmacro our-pop (stack)
’(prog1 (car ,stack)(setf ,stack (cdr ,stack))))
Здесь для записи выражения использовалась обратная блокировка. Это позволяет определить макрос в форме, близкой к его раскрытому виду.
5.23. Пакеты
Для контроля доступа к различным объектам программ в языке Коммон Лисп используются пакеты. Пакет представляет собой пространство имен, в котором устанавливается соответствие между именами и символами. В Коммон Лиспе определенно несколько стандартных пакетов. Однако в каждый момент времени только один пакет является текущим. Текущий пакет определяется значением специальной переменной *package*. При чтении имен поиск символов выполняется в пакетах. В программах можно использовать символы, которые определенны не в текущем пакете. В этом случае перед символом через двоеточие записывают префикс, представляющий имя пакета, например:
my-package: list-of-date
Здесь LIST-OF-DATE представляет символ, определенный в пакете MY-PACKAGE. Наряду с полным именем, каждый пакет может иметь сокращенное мнемониче-
ское имя, которое приписываются пакету в момент его создания.
Символы, содержащиеся в пакете, подразделяются на два класса: внешние и внутренние. Внешние символы представляют интерфейсную часть пакета и видимы со стороны других пакетов. Символы становятся внешними, если они экспортируются за пределы пакета. Внутренние символы – это те символы, которые доступны внутри пакета и невидимы за его пределами.
Ранее было отмечено, что с символом в языке Коммон Лисп связаны различные атрибуты: имя, значение, функция, список свойств и пакет, в котором этот символ введен. Для того чтобы выяснить значение атрибута пакета, применяется функция
SYMBOL-PACKAGE. Например,
(symbol-name ’A) ”A”
(symbol-package ’A) #<PACKAGE "USER"…>
Язык Лисп |
283 |
|
|
В состав языка Коммон Лисп входят четыре стандартных пакета. COMMON-LISP-USER − (мнемоническое имя CL-USER) пакет, который ста-
новится текущим в момент запуска Лисп-системы.
COMMON-LISP − (мнемоническое имя CL) содержит примитивы системы Коммон Лисп (за исключением ключевых слов), в нем определены такие внешние сим-
волы, как : CAR, CDR, *PACKAGE* и др.
SYSTEM − (мнемоническое имя SYS) содержит символы, зависящие от реализации языка.
KEYWORD − (мнемонического имени не имеет) содержит символы, представляющие ключевые слова. Например, ключевые параметры лямбда-списка. Символы, введенные в этот пакет, автоматически становятся внешними и представляют собой константные значения. Поэтому при записи ключевых слов в вызовах функций не требуется блокировки вычислений, т.е. вместо
’:some-symbol
следует писать
:some-symbol
Для того чтобы создать и внести некоторый символ в пакет, применяется функ-
ция INTERN:
(intern строка &OPTIONAL пакет)
Функция вносит символ, имя которого представляется аргументом строка, в указанный пакет (по умолчанию символ вносится в текущий пакет). Введенный символ рассматривается как внутренний символ пакета. Если символ вносится в пакет KEYWORD, то он рассматривается как внешний символ. В качестве результата функция возвращает два значения: первое значение представляет имя символа, а второе – свойства добавленного символа. Если добавленный символ отсутствовал в пакете, то в качестве второго значения возвращается NIL. Если добавленный символ уже имелся в пакете, то второе значение может быть равно:
-:internal – добавляемый символ имеется в пакете, и он определен как внутренний;
-:external – добавляемый символ уже имеется в пакете, и он определен как внешний;
-:inherited – добавляемый символ уже имеется в пакете, и он унаследован из дру-
гого пакета. Например,
(intern ”NEW-SYMBOL” ”KEYWORD”) :| NEW-SYMBOL |, NIL (intern ”NEW-SYMBOL” ”KEYWORD”) :|NEW-SYMBOL|, EXTERNAL
Символ можно создать, не включая его в какой-либо пакет. Для этого применяется функция MAKE-SYMBOL. Символ, созданный таким образом, не имеет ни значения, ни списка свойств. С ним не связано определение какой-либо функции. При выводе такой символ помечается знаком “ # ”. Например,
(setf x ( intern ”FOOL”)) FOOL
(setf y ( make-symbol ”FOOL”)) #:FOOL
284 |
Глава 5 |
|
|
Здесь значениями символов X и Y является символ с именем FOOL. Но на этом сходство указанных символов заканчивается. X представляет символ, включенный в систему, а Y – нет.
Генерировать новые неповторяющиеся имена символов можно с помощью функции GENSYM. Если эта функция вызывается без параметров, то формируемые имена символов представляются в виде: #:G5, #:G6 и т.д. Буквенными обозначениями и номером символа можно управлять через параметры функции GENSYM:
(setq symbol1 (gensym)) #:G324
(symbol-package symbol1) NIL
(setq symbol2 (gensym “T“)) #:T325
(setq symbol3 (gensym 10)) #:G10
Исключить символ из системы можно с помощью функции UNINTERN:
(setf fool 11.1) 11.1
(setf x ’fool) FOOL (unintern ’fool) T x #:FOOL
Если один из пакетов использует другой пакет, то все внешние символы наследуются первым пакетом. При этом они рассматриваются как внутренние.
Символы можно экспортировать из пакета и импортировать в пакет. Для этого применяются функции EXPORT и IMPORT. Формат вызова функции EXPORT:
(export список_символов имя_пакета)
Символы, заданные в списке и доступные в указанном пакете, становятся внешними. Следовательно, данные символы становятся доступными во всех пакетах, использующих пакет, указанный в вызове функции EXPORT.
Функция IMPORT добавляет в заданный пакет символ или символы:
(import список_символов имя_пакета)
Пакеты могут наследовать внешние символы других пакетов. Достигается это с помощью вызова
(use-package имя_пакета)
Создание пакета можно выполнить с помощью функции MAKE-PACKAGE или
спомощью функции DEFPACKAGE. Функция MAKE-PACKAGE создает новый пакет
сзаданным именем и, если необходимо, с дополнительными символическими именами
(nicknames):
(make-package ”temporal” :nicknames (”TEMP”, ”temp”))
#<PACKAGE ”TEMPORAL”>
Язык Лисп |
285 |
|
|
Введение пакетов в Коммон Лиспе позволяет использовать модульный подход программирования. Для внесения в память системы определений из соответствующего пакета можно переопределить значения переменной *PACKAGE*:
(setf *package* (make-package ’new-package))
#<PACKAGE ”NEW-PACKAGE”
Вэтом случае становятся доступными все определения, сделанные в модуле NEWPACKAGE. Если необходимо обратиться к содержимому уже имеющегося пакета, то следует воспользоваться функцией FIND-PACKAGE:
(setf *package* (find-package ’old-package))
#<PACKAGE ”old-package”>
Врезультате последнего вызова текущим пакетом, используемым системой, будет па-
кет OLD-PACKAGE.
5.24.Множественные значения
ВКоммон Лиспе имеются функции, которые возвращают несколько значений. При выводе на терминал множественные значения располагаются в нескольких строках. Например,
(truncate 5 3)
1
2
Если данный результат использовать в качестве аргумента других функций, то второе значение будет просто игнорироваться. Для того чтобы воспользоваться вторым значением, необходимо объединить получаемые значения в список. Добиться этого можно с помощью макроса MULTIPLE-VALUE-LIST:
(multiple-value-list (truncate 5 3)) (1 2)
Для доступа к первому и второму значению следует использовать функции CAR
и CADR.
Можно использовать макрос MULTIPLE-VALUE-SETQ, выполняющий множественные присвоения:
(multiple-value-setq (div rest) (truncate 5 3)) 2 div 1
rest 2
Данный макрос обобщает действия, выполняемые специальной формой SETQ. Локальное связывание множественных значений можно выполнить с помощью
макроса MULTIPLE-VALUE-BIND, который обобщает LET-вызов:
(multiple-value-bind (div rest) (truncate 5 3) (+ div rest ))
3
286 |
Глава 5 |
|
|
Макрос возвращает результат, вычисляемый последней формой его вызова.
Для работы с множественными значениями полезной может оказаться специальная форма MULTIPLE-VALUE-CALL, которая обобщает функционал FUNCALL:
(multiple-value-call #’list (truncate 5 3)) (1 2)
Также в Коммон Лиспе имеется форма, которая формирует множественные значения из своих аргументов:
(values 4 8)
4
8
Если в ходе обработки вызова
(values (read) (read))
ввести следующие s-выражения (+ 1 1) и (+ 2 2), которые читаются с помощью функции READ, то результатом вызова формы VALUES будет множественное значение: (+ 1 1), (+ 2 2).
5.25. Программирование задач ИИ на языке ЛИСП
5.25.1. Случайный поиск
Общий алгоритм случайного поиска решений в пространстве состояний описан в главе 2. Стратегия поиска заключается в случайном выборе оператора, обеспечивающего переход к следующему состоянию задачи. Поиск заканчивается, когда будет выполнен переход в целевое состояние.
Воспользуемся для представления графа состояний списком свойств символа. Представим граф состояний, изображенный на рисунке 5.13, в виде множества символов, соответствующих вершинам графа. С каждым символом свяжем свойство “соединение” (connection), значением которого будет являться список дочерних вершин:
(setf (get ’a ’connection) ’(b e)) (setf (get ’b ’connection) ’(a c f)) (setf (get ’c ’connection) ’(b f)) (setf (get ’d ’connection) ’(e g)) (setf (get ’e ’connection) ’(a d f))
(setf (get ’f ’connection) ’(b c e h))
(setf (get ’g ’connection) ’(d h))
(setf (get ’h ’connection) ’ (f g))
Язык Лисп |
287 |
|
|
Рисунок 5.13 – Граф состояний
Случайный поиск можно организовать с помощью одного из двух алгоритмов – итерационного или рекурсивного. Определим для этого две функции random-search-i и random-search-r :
;итерационная версия
(defun random-search-i (start goal)
(do ((current start (next current)))
((eq goal current)(print goal)(values))
(print current)))
;рекурсивная версия
(defun random-search-r (start goal) (cond ((eq start goal)(list goal))
(t (cons start (random-search-r (next start) goal)))))
В приведенных определениях выбор следующего состояния выполняется с помощью функции next:
(defun next (point)
(nth (random (length (get point 'connection))) (get point 'connection)))
Здесь функция random генерирует случайное целое число, значение которого не превышает количества вершин, связанных с текущей вершиной (point). Это число определяет номер следующей вершины, извлекаемой из списка свойств текущей вершины. Таким образом, каждый раз следующая вершина выбирается случайно.
Вызов функции random-search-i обеспечивает простую печать пройденных вершин, а вызов функции random-search-r – списка, представляющего путь от стартовой вершины (start) до целевой вершины (goal):
(random-search-r 'a 'h) ( a e a b c b f h )
288 |
Глава 5 |
|
|
(random-search-i 'a 'h) a e f b c b a e d g h
(random-search-r 'a 'h) ( a e f h )
(random-search-i 'a 'h) a e f b c f c f h
Из примера видно, что в ходе случайного поиска возможен многократный возврат к одним и тем же вершинам (состояниям). Кроме того, каждый новый вызов функции поиска возвращает различные пути от исходной до целевой вершины.
5.25.2. Поиск в глубину и ширину
Воспользуемся представлением графа состояний в виде а-списка, каждый подсписок которого будет представлять возможный переход на графе состояний. Так, граф состояний, изображенный на рисунке 5.13, можно задать в виде следующего а-списка:
(setq graph ’((a b)(a e)(b a)(b f)(b c) (c b)(c f)(d e)(d g)(e a)(e d)(e f) (f b)(f c)(f e)(f h)(g d)(g h)(h g)(h f)))
Определим функцию depth-first в соответствии с алгоритмом поиска в глубину, описанном в главе 2. При этом списки OPEN и CLOSED будем также представлять в виде а-списков, в которых на первом месте любого подсписка располагается “дочерняя” вершина, а на втором – соответствующая “родительская” вершина. Это позволит после завершения поиска восстановить по списку CLOSED путь из начальной вершины в целевую вершину.
(defun depth-first(start goal)
;поместить подсписок (start start) в open
(setq open (list (list start start)))
;инициализировать список closed (setq closed nil)
(loop ; цикл
(cond ((null open)(return ’неудача)) ; на графе нет пути (t
;запомнить первый подсписок списка open
(setq n (first open))
;внести n в начало closed
(setq closed (cons n closed))
;проверить, является ли (first n) целевой вершиной
(if (eq (first n) goal) (return ’удача))
;добавить в начало open дочерние вершины
Язык Лисп |
289 |
|
|
(setq open (append (list-children (first n))(rest open)))
; печать промежуточных результатов
(terpri)
(princ ”closed=”)(prin1 closed)
(terpri)
(princ ”open=”) (prin1 open)))))
Здесь функция list-children возвращает для текущей вершины n а-список дочерних вершин, которые не входят в списки OPEN и CLOSED:
(defun list-children(n)
(setq L nil)
(dolist (temp graph L) ;выполнить действия для каждого
;подсписка из graph
;инвертировать подсписок temp (setq rtemp (rev temp))
;выясняем, содержит ли temp дочернюю вершину
(if (and (eq n (first temp))
;проверяем, входят ли дочерние вершины
;в списки OPEN и CLOSED
(not (assoc (first rtemp) open)) (not (assoc (first rtemp) closed)))
;добавляем дочернюю вершину вместе с родительской
;к результирующему списку L
(setq L (cons rtemp L)))))
; функция, инвертирующая подсписок temp
(defun rev(temp)
(setq a (first temp)) (setq b (second temp)) (list b a))
Путь от стартовой до целевой вершины можно получить с помощью функции BACK-WAY, которая анализирует список CLOSED. В списке CLOSED содержатся “закрытые” вершины графа с указанием их родительских вершин. Используя ссылки на родительские вершины, функция BACKWAY восстанавливает искомый путь:
(defun back-way (goal start) (setq g goal)
(setq L nil)
(dolist (temp closed L) (if (eq (first temp)g)
(prog1 (setq L (cons (rev temp) L)) (setq g (second temp))))))