WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 
s

Pages:     | 1 | 2 || 4 |

«По договору между издательством «Символ-Плюс» и Интернет-магазином «Books.Ru – Книги России» единственный легальный способ получения данного файла с книгой ISBN ...»

-- [ Страница 3 ] --

1. Определите параметры accessor, initform, initarg для классов, определенных на рис. 11.2. Внесите необходимые правки, чтобы код более не использовал slot-value.

2. Перепишите код на рис. 9.5 так, чтобы сферы и точки были классами, а introspect и normal – обобщенными функциями.

3. Имеется набор классов:

(defclass a (c d)...) (defclass e ()...) (defclass b (d c)...) (defclass f (h)...) (defclass c ()...) (defclass g (h)...) (defclass d (e f g)...) (defclass h ()...) (a) Нарисуйте граф, представляющий предков a, и составьте список классов, которым принадлежит экземпляр a в порядке убывания их специфичности.

(b) Повторите аналогичную процедуру для b.

4. Имеются следующие функции:

• precedence: принимает объект и возвращает для него список предшествования классов по убыванию специфичности.

• methods: принимает обобщенную функцию и возвращает список всех ее методов.

• specializations: принимает метод и возвращает список специа лизаций его параметров. Каждый элемент возвращаемого списка будет либо классом, либо списком вида (eql x), либо t (для неспециализированного параметра).

С помощью перечисленных функций (не пользуясь compute-applicable-methods или find-method) определите функцию most-spec-app-meth, принимающую обобщенную функцию и список аргументов, с которыми она будет вызвана, и возвращающую наиболее специфичный применимый метод, если таковые имеются.

5. Измените код на рис. 11.2 так, чтобы при каждом вызове обобщенной функции area увеличивался некий глобальный счетчик. Функция не должна менять свое поведение никаким иным образом.

6. Приведите пример задачи, трудноразрешимой в том случае, когда лишь первый аргумент обобщенной функции может быть специализирован.

Структура Глава 12.

В разделе 3.3 было объяснено, каким образом использование указателей позволяет поместить любое значение куда угодно. Это утверждение включает массу возможностей, но не все они могут принести пользу. Например, объект может быть элементом самого себя. Хорошо это или плохо, зависит от того, делается это намеренно или происходит случайно.

12.1. Разделяемая структура Списки могут совместно использовать одни и те же ячейки. В простейшем случае один список может быть частью другого. После выполнения (setf part (list ’b ’c)) (B C) (setf whole (cons ’a part)) (A B C) первая ячейка становится частью (а точнее, cdr) второй. В подобных случаях принято говорить, что два списка разделяют одну структуру.

Структура, лежащая в основе двух таких списков, представлена на рис. 12.1.

–  –  –

Рис. 12.2. Разделяемый хвост В случае вложенных списков важно отличать списки с разделяемой структурой от их элементов с разделяемой структурой. Структура списка верхнего уровня включает ячейки, из которых состоит сам список, но не включает какие-либо ячейки, из которых состоят отдельные элементы списка. Пример структуры верхнего уровня вложенного списка приведен на рис. 12.3.

Имеют ли две ячейки разделяемую структуру, зависит от того, считаем мы их списками или деревьями. Два вложенных списка могут разделять одну структуру как деревья, но не разделять ее как списки. СлеГлава 12. Структура

–  –  –

Рис. 12.4. Разделяемое поддерево Хотя второй элемент holds1 разделяет структуру с первым элементом holds2 (в действительности, он ему идентичен), holds1 и holds2 не делят между собой общую структуру как списки. Два списка разделяют структуру как списки, только если они делят общую структуру верхнего уровня, чего не делают holds1 и holds2.





Избежать использования разделяемой структуры можно с помощью копирования. Функция copy-list, определяемая как (defun our-copy-list (lst) (if (null lst) nil (cons (car lst) (our-copy-list (cdr lst)))))

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

(defun our-copy-tree (tr) (if (atom tr) tr (cons (our-copy-tree (car tr)) (our-copy-tree (cdr tr))))) возвратит список, который не разделяет структуру всего дерева с исходным списком. Рисунок 12.5 демонстрирует разницу между вызовом copy-list и copy-tree для вложенного списка.

–  –  –

Рис. 12.5. Два способа копирования

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

В предыдущем разделе мы видели, как сделать один список хвостом другого:

(setf whole (list ’a ’b ’c) tail (cdr whole)) Изменение списка tail повлечет симметричное изменение хвоста whole, и наоборот, так как по сути это одна и та же ячейка:

(setf (second tail) ’e) E tail (B E) 206 Глава 12. Структура whole (A B E) Разумеется, то же самое будет происходить и для двух списков, имеющих общий хвост.

Изменение двух объектов одновременно не всегда является ошибкой.

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

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

Чтобы гарантировать отсутствие подобных ошибок, просто избегайте использования setf (а также аналогичных операторов типа pop, rplaca и других) для списков. Если изменяемость списков все же требуется, то необходимо выяснить, откуда взялся изменяемый список, чтобы убедиться, что он не делит структуру с чем-то, что нельзя менять. Если же это не так или вам неизвестно происхождение списка, то модифицировать необходимо не сам список, а его копию.

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

Пока не установлено обратное, имейте в виду, что все, что передается функции:

1. Может быть передано деструктивным операторам.

2. Может быть сохранено где-либо, и изменение этого объекта приведет к изменению в других частях кода, использующего данный объект.1 В обоих случаях правильным решением является копирование аргументов.

В Common Lisp вызов любой функции, выполняющейся во время прохода по структуре (например, функции-аргумента mapcar или remove-if), не должен менять эту структуру. В противном случае последствия выполнения такого кода не определены.

12.3. Пример: очереди Разделяемые структуры – это не только повод для беспокойства. Иногда они могут быть полезны. В этом разделе показано, как с помощью разделяемых структур представить очереди. Очередь – это хранилище объектов, из которого они могут быть извлечены по одному в том же Например, в Common Lisp попытка изменения строки, используемой как имя символа, считается ошибкой. И поскольку нам неизвестно, копирует ли intern свой аргумент-строку перед созданием символа, мы должны предположить, что модификация любой строки, которая передава лась в intern, приведет к ошибке.

12.3. Пример: очереди порядке, в котором они были туда записаны. Такую модель принято именовать FIFO – сокращение от «первым пришел, первым ушел» («first in, first out»).

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

Одна из возможных стратегий приводится на рис. 12.6, где показана очередь из трех элементов: a, b и c. Очередью считаем точечную пару, состоящую из списка и последней ячейки этого же списка. Будем называть их начало и конец. Чтобы получить элемент из очереди, необходимо просто извлечь начало. Чтобы добавить новый элемент, необходимо создать новую ячейку, сделать ее cdr конца очереди и затем сделать ее же концом.

–  –  –

12.4. Деструктивные функции Common Lisp включает в себя несколько функций, которые могут изменять структуру списков и за счет этого работать быстрее. Они называются деструктивными. И хотя эти функции могут изменять ячейки, переданные им в качестве аргументов, они делают это не ради побочных эффектов.

Например, delete является деструктивным аналогом remove. Хотя ей и позволено портить переданный список, она не дает никаких обещаний, что так и будет делать.

Посмотрим, что происходит в большинстве реализаций:

(setf lst ’(a r a b i a)) (A R A B I A) (delete ’a lst) (R B I) lst (A R B I)

Как и в случае с remove, чтобы зафиксировать побочный эффект, необходимо использовать setf:

(setf lst (delete ’a lst)) Примером того, как деструктивные функции модифицируют списки, является nconc, деструктивная версия append.1 Приведем ее версию для двух аргументов, демонстрирующую, каким образом сшиваются списки:

(defun nconc2 (x y) (if (consp x) Буква n в имени nconc соответствует «non-consing». Имена многих деструктивных функций начинаются с n.

12.5. Пример: двоичные деревья поиска

–  –  –

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

На рис. 12.8 приведена деструктивная версия bst-insert (стр. 86). Она принимает точно такие же аргументы и возвращает точно такое же значение, как и исходная версия. Единственным отличием является то, что она может изменять дерево, передаваемое вторым аргументом.

–  –  –

Рис. 12.8. Двоичные деревья поиска: деструктивная вставка В разделе 2.12 было предупреждение о том, что деструктивные функции вызываются не ради побочных эффектов.

Поэтому если вы хотите построить дерево с помощью bst-insert!, вам нужно вызывать ее так же, как если бы вы вызывали настоящую bst-insert:

(setf *bst* nil) NIL (dolist (x ’(7 2 9 8 4 1 5 12)) (setf *bst* (bst-insert! x *bst* #’))) NIL Вы могли бы также определить аналог push для BST, но это довольно сложно и выходит за рамки данной книги. (Для любопытных такой макрос определяется на стр. 429.°)

12.5. Пример: двоичные деревья поиска На рис. 12.91 представлен деструктивный вариант функции bst-delete, которая связана с bst-remove (стр. 89) так же, как delete связана с remove.

Как и delete, она не подразумевает вызов ради побочных эффектов. Использовать bst-delete необходимо так же, как и bst-remove:

(setf *bst* (bst-delete 2 *bst* #’)) #7 (bst-find 2 *bst* #’) NIL

–  –  –

Рис. 12.9. Двоичные деревья поиска: деструктивное удаление

12.6. Пример: двусвязные списки Обычные списки в Лиспе являются односвязными. Это означает, что движение по указателям происходит только в одном направлении: вы можете перейти к следующему элементу, но не можете вернуться к предыдущему. Двусвязные списки имеют также и обратный указатель, поэтому можно перемещаться в обе стороны. В этом разделе показано, как создавать и использовать двусвязные списки.

На рис. 12.10 показана их возможная реализация. cons-ячейки имеют два поля: car, указывающий на данные, и cdr, указывающий на следующий элемент. Элемент двусвязного списка должен иметь еще одно поле, указывающее на предыдущий элемент. Вызов defstruct (рис. 12.10) создает объект из трех частей, названный dl (от «doubly linked»), который мы будем использовать для создания двусвязных списков. Поле data в dl соответствует car в cons-ячейке, а поле next соответствует cdr. Поле

12.6. Пример: двусвязные списки prev похоже на cdr, но указывает в обратном направлении. (Пример такой структуры приведен на рис. 12.11.) Пустому двусвязному списку, как и обычному, соответствует nil.

Вызов defstruct также определяет функции для двусвязных списков, ана логичные car, cdr и consp: dl-data, dl-next и dl-p. Функция печати dl-list возвращает обычный список с теми же значениями, что и двусвязный.

Функция dl-insert похожа на cons. По крайней мере, она, как и cons, является основной функцией-конструктором. В отличие от cons, она изменяет двусвязный список, переданный вторым аргументом. В данной ситуации это совершенно нормально. Чтобы поместить новый объект в начало обычного списка, вам не требуется его изменять, однако чтобы поместить объект в начало двусвязного списка, необходимо присвоить полю prev указатель на новый объект.

–  –  –

Рис. 12.11. Двусвязный список Другими словами, несколько обычных списков могут иметь общий хвост. Но для пары двусвязных списков это невозможно, так как хвост каждого из них имеет разные указатели на голову. Если бы функция dl-insert не была деструктивна, ей бы приходилось всегда копировать свой второй аргумент.

Другое интересное различие между одно- и двусвязными списками заключается в способе доступа к их элементам. Работая с односвязным списком, вы храните указатель на его начало. При работе с двусвязным списком, поскольку в нем элементы соединены с обоих концов, вы можете использовать указатель на любой из элементов. Поэтому dl-insert, в отличие от cons, может добавлять новый элемент в любое место двусвязного списка, а не только в начало.

Функция dl-list является dl-аналогом list.

Она получает произвольное количество аргументов и возвращает состоящий из них dl:

(dl-list ’a ’b ’c) #DL (A B C) В ней используется reduce с параметрами: :from-end, установленным в t, и :initial-value, установленным в nil, что делает приведенный выше вызов эквивалентным следующей последовательности:

(dl-insert ’a (dl-insert ’b (dl-insert ’c nil))) Заменив #’dl-insert на #’cons в определении dl-list, эта функция будет вести себя аналогично list:

(setf dl (dl-list ’a ’b)) #DL (A B) (setf dl (dl-insert ’c dl)) #DL (C A B) (dl-insert ’r (dl-next dl)) #DL (R A B) dl #DL (C R A B) Наконец, для уда ления элемента из двусвязного списка определена dl-remove. Как и dl-insert, она сделана деструктивной.

12.7. Циклическая структура

12.7. Циклическая структура Изменяя структуру списков, можно создавать циклические списки. Они бывают двух видов. Наиболее полезными являются те, которые имеют замкнутую структуру верхнего уровня. Такие списки называются циклическими по хвосту (cdr-circular), так как цикл создается cdr-частями ячеек.

Чтобы создать такой список, содержащий один элемент, необходимо установить указатель cdr на самого себя:

(setf x (list ’a)) (A) (progn (setf (cdr x) x) nil) NIL Теперь x – циклический список. Его структура изображена на рис. 12.12.

–  –  –

Рис. 12.12. Циклические списки При попытке напечатать такой список символ a будет выводиться до бесконечности.

Этого можно избежать, установив значение *print-circle* в t:

(setf *print-circle* t) T x #1=(A. #1#) При необходимости можно использовать макросы чтения #n= и #n# для представления такой структуры.

Списки с циклическим хвостом могут быть полезны для представления, например, буферов или ограниченных наборов каких-то объектов (пулов1).

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

(defun circular (lst) (setf (cdr (last lst)) lst)) Пул – это набор инициа лизированных ресурсов, которые поддерживаются

–  –  –

Другой тип циклических списков – циклические по голове (car-circular).

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

Ниже мы создадим циклический по голове список, второй элемент которого является им самим:

(let ((y (list ’a))) (setf (car y) y) y) #1=(#1#) Результат изображен на рис. 12.12. Несмотря на цикличность, этот циклический по голове список (car-circular) по-прежнему является правильным списком, в отличие от циклических по хвосту (cdr-circular), которые правильными быть не могут.

Список может быть циклическим по голове и хвосту одновременно.

car и cdr такой ячейки будут указывать на нее саму:

(let ((c (cons 1 1))) (setf (car c) c (cdr c) c) c) #1=(#1#. #1#) Сложно представить, для чего могут использоваться подобные объекты. На самом деле, главное, что нужно вынести из этого, – необходимо избегать непреднамеренного создания циклических списков, так как большинство функций, работающих со списками, будут уходить в бесконечный цикл, если получат в качестве аргумента список, циклический по тому направлению, по которому они совершают проход.

Циклическая структура может быть проблемой не только для списков, но и для других типов объектов, например для массивов:

(setf *print-array* t) T (let ((a (make-array 1))) (setf (aref a 0) a) a) #1=#(#1#) И действительно, практически любой объект, состоящий из элементов, может включать себя в качестве одного из них.

Разумеется, структуры, создаваемые defstruct, также могут быть циклическими. Например, структура c, представляющая элемент дерева, может иметь поле parent, содержащее другую структуру p, чье поле

child ссылается обратно на c:

(progn (defstruct elt (parent nil) (child nil)) (let ((c (make-elt)) (p (make-elt)))

12.8. Неизменяемая структура

–  –  –

12.8. Неизменяемая структура Неизменяемые объекты также являются частью кода, и наша задача не допускать их модификации, потому что в противном случае мы случайно можем создать программу, которая пишет сама себя. Цитируемый список является константой, поэтому следует проявлять аккуратность при работе с отдельными его ячейками. Например, если мы используем следующий предикат для проверки на принадлежность к арифметическим операторам, (defun arith-op (x) (member x ’(+ - * /))) то в случае истинного значения он будет возвращать часть цитируемого списка. Изменяя возвращаемое значение:

(nconc (arith-op ’*) ’(as it were)) (* / AS IT WERE) мы изменяем и сам исходный список внутри arith-op, что приведет к изменению работы этой функции:

(arith-op ’as) (AS IT WERE) Возврат константы из функции не всегда является ошибкой. Однако нужно учитывать подобные случаи при принятии решения о безопасности выполнения деструктивных операций над чем-либо.

Избежать возврата части неизменной структуры в случае arith-op можно несколькими способами.

В общем случае замена цитирования на явный вызов функции list решит проблему и приведет к созданию нового списка при каждом вызове:

(defun arith-op (x) (member x (list ’+ ’- ’* ’/)))

Однако в данном случае вызов list ударит по производительности, поэтому здесь лучше вместо member использовать find:

(defun arith-op (x) (find x ’(+ - * /)))

Проблема, рассмотренная в этом разделе, чаще всего возникает при работе со списками, однако она актуальна и для других типов данных:

218 Глава 12. Структура массивов, строк, структур, экземпляров и т. д. Не следует модифицировать что-либо, заданное в тексте программы буквально.

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

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

Итоги главы

1. Два списка могут разделять общий хвост. Списки могут разделять структуры как деревья, без разделения структуры верхнего уровня.

Разделения структур можно избежать с помощью копирования.

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

3. Очереди могут быть представлены как cons-ячейки, car которых указывает на первую ячейку списка, а cdr – на последнюю.

4. Из соображений производительности деструктивным операторам разрешается модифицировать свои аргументы.

5. В некоторых приложениях использование деструктивных операторов более естественно.

6. Списки могут быть циклическими по голове и хвосту. Лисп умеет работать с циклическими и разделяемыми структурами.

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

–  –  –

3. Определите функцию copy-queue, возвращающую копию очереди.

4. Определите функцию, принимающую в качестве аргументов объект и очередь и помещающую этот объект в начало очереди.

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

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

7. Определите функцию, проверяющую, является ли ее аргумент циклическим по хвосту списком.

8. Определите функцию, проверяющую, является ли ее аргумент циклическим по голове списком.

Скорость Глава 13.

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

Довольно сложно давать общие рекомендации по поводу оптимизации из-за внушительного разнообразия реализаций Common Lisp. Действие, ускоряющее выполнение вашей программы в одной из них, может замедлить работу в другой. Чем мощнее язык, тем дальше он отстоит от аппаратной части, а чем дальше вы от аппаратной части, тем выше шансы, что разные реализации по-разному будут возвращаться к ней при генерации программного кода. Поэтому, несмотря на то что некоторые методики, описанные ниже, почти наверняка ускорят выполнение кода в любой реализации, все же не стоит забывать о рекомендательном характере содержимого этой главы.

13.1. Правило бутылочного горлышка Независимо от реализации есть три момента, касающиеся оптимизации: она должна быть сосредоточена на бутылочных горлышках, она не должна начинаться слишком рано и она должна начинаться с алгоритмов. Пожалуй, по поводу оптимизации важнее всего понять, что в любой программе, как правило, есть несколько узких мест, выполнение которых занимает большую часть времени. По мнению Кнута, «подавляющая часть времени выполнения программы, не связанной с вводомвыводом, сосредоточена в примерно 3% исходного кода».° Оптимизация таких участков даст существенно большее увеличение скорости, чем оптимизация остальных частей, которая будет пустой тратой времени.

13.2. Компиляция Поэтому исключительно важный первый шаг оптимизации любой программы – поиск подобных узких мест, или бутылочных горлышек. Многие реализации Лиспа включают собственные профилировщики, которые наблюдают за выполнением программы и предоставляют отчет о времени, затраченном на каждую из ее частей, выявляя тем самым узкие места. Профилировщик – ценный инструмент, совершенно необходимый для создания действительно эффективного кода. Если ваша реализация Лиспа включает профилировщик, то наверняка предоставляет и документацию на него, которую следует изучить. Если же такого инструмента у вас нет, то узкие места придется угадывать самостоятельно, и вы будете удивлены, когда узнаете, как часто подобные догадки бывают ошибочными.

Следствие правила бутылочных горлышек: не стоит вкладывать слишком много усилий в оптимизацию на ранних стадиях написания программы. Кнут предлагает еще более жесткую формулировку: «Преждевременная оптимизация является корнем всех зол (или, по крайней мере, большей части) в программировании».° Пока программа не написана, сложно сказать, где возникнет узкое место, поэтому не тратьте свое время зря. Кроме того, оптимизация затрудняет модификацию, и попытка оптимизировать программу в момент ее написания сродни попытке писать картину быстросохнущими красками.

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

Приступая к оптимизации, начинайте с самого верху. Для начала убедитесь, что используете наиболее оптимальный алгоритм, и лишь потом переходите к низкоуровневым трюкам при написании кода. Потенциальная выгода велика – возможно даже настолько, что вам, может быть, вообще не придется прибегать к каким-либо трюкам. Это утверждение нужно сочетать с предыдущим правилом: часто решение об алгоритме нужно принимать на ранней стадии написания программы.

–  –  –

Старые реа лизации могут не предоставлять declaim. В этом случае используйте proclaim с цитируемым аргументом.

13.2. Компиляция acc (len (cdr lst) (1+ acc))))) (len lst 0))) Вообще говоря, хвостовая рекурсия имеет здесь место в локальной функции len, поскольку рекурсивный вызов является последним действием в функции. Вместо того чтобы вычислять результирующее значение на обратном пути рекурсии, как это делает length/r, она аккумулирует его на пути вперед. Для этого и нужен аргумент acc, значение которого возвращается в конце рекурсивного вызова.

Хороший компилятор может преобразовывать хвостовой вызов в goto, и таким образом хвостовая рекурсия скомпилируется в обычный цикл.° В машинном коде, когда управление впервые передается той его части, которая реализует функцию len, на стек кладется информация, указывающая, что нужно сделать для завершения вызова. Но, поскольку после самого рекурсивного вызова делать ничего не надо, эти инструкции остаются действительными также и для второго вызова: для возврата из второго вызова нужно сделать то же самое, что и для возврата из первого. Таким образом, мы можем просто заменить старые аргументы функции новыми значениями, а после этого прыгнуть назад к началу функции и действовать так, как если бы это был второй вызов. При этом нет необходимости делать реальный вызов функции.

Другой способ уйти от затрат на полноценный вызов функции – заставить компилятор встраивать функции построчно (inline). Это особенно ценно для небольших функций, затраты на выполнение которых сопоставимы с затратами на сам вызов.

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

(declaim (inline single?))

–  –  –

Так как до определения single? была сделана глобальная inline-декларация1, использование single? не будет приводить к реальному вызову функции.

Если мы определим вызывающую ее функцию так:

(defun foo (x) (single? (bar x))) то при компиляции foo код single? будет встроен в код foo так, как если бы мы написали:

(defun foo (x) (let ((lst (bar x))) (and (consp lst) (null (cdr lst))))) Существует два ограничения на inline-встраиваемость функции. Рекурсивные функции не могут быть встроены. И если inline-функция переопределяется, должны быть перекомпилированы все другие функции, вызывающие ее, иначе в них останется ее старое определение.

Для того чтобы избежать вызовов функций, в некоторых более ранних диалектах Лиспа использовались макросы (см. раздел 10.2). В Common Lisp делать это необязательно.

Различные компиляторы Лиспа отличаются друг от друга возможностями оптимизации. Чтобы узнать, какая работа реально проделана компилятором, полезно изучить скомпилированный код, который вы можете получить с помощью disassemble. Эта функция принимает функцию или имя функции и отображает результат ее компиляции, то есть набор машинных инструкций, которые реализуют эту функцию. Даже если дизассемблерный листинг является для вас китайской грамотой, вы можете хотя бы визуально оценить количество сделанных оптимизаций: скомпилируйте две версии – с оптимизирующими декларациями и без них – и просто оцените разницу. С помощью аналогичной методики можно выяснить, были ли функции встроены построчно. В любом случае, перед подобными экспериментами убедитесь, что установлены необходимые параметры компиляции для получения максимально быстрого кода.°

13.3. Декларации типов Если Лисп – не первый язык программирования, с которым вы сталкиваетесь, то вас может удивить, что до сих пор мы ни разу не использовали то, что совершенно необходимо во многих других языках: декларации типов.

В большинстве языков для каждой переменной необходимо определить свой тип, и в дальнейшем переменная может содержать лишь значения этого типа. Такие языки называют языками с сильной типизацией.

Чтобы inline-декларации были учтены, возможно, понадобится также установить параметры компиляции для генерации быстрого кода.

13.3. Декларации типов Такой подход заставляет программиста выполнять лишнюю работу и ограничивает его возможности: вы не можете писать функции, применимые к различным типам аргументов, а также хранить в структурах данных разные типы.° Однако преимуществом данного подхода является упрощение задачи компилятора: если он видит функцию, то знает заранее, какие действия нужно совершить.

В разделе 2.15 упоминалось, что Common Lisp использует более гибкий подход, называемый декларативной типизацией (manifest typing).1 Типы имеют значения, а не переменные. Последние могут содержать объекты любых типов.

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

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

Подход к решению данной проблемы в Common Lisp таков: сообщите все, что вам известно. Если вам заранее известно, что вы складываете два числа типа fixnum, то можно объявить их таковыми, и компилятор сгенерирует код целочисленного сложения такой же, как в С.

Таким образом, различие в подходе к оптимизации не приводит к разнице в плане скорости. Просто первый подход требует всех деклараций типов, а второй – нет. В Common Lisp объявления типов совершенно не обязательны. Они могут ускорить работу программы, но (если, конечно, они сами корректны) не способны изменить ее поведение.

Глобальные декларации выполняются с помощью declaim, за которой должна следовать хотя бы одна декларационная форма. Декларация типа – это список, содержащий тип символа, сопровождаемый именем типа и именами одной или более переменных.

Таким образом, для объявления типа глобальной переменной достаточно сказать:

(declaim (type fixnum *count*))

ANSI Common Lisp допускает декларации без использования слова type:

(declaim (fixnum *count*)) Локальные декларации выполняются с помощью declare, которая принимает те же аргументы, что и declaim. Декларации могут начинать любое тело кода, в котором появляются новые переменные: defun, lambda, Применяемый в Лиспе подход к типизации можно описать двумя способа

–  –  –

let, do и другие. К примеру, чтобы сообщить компилятору, что параметры функции принадлежат типу fixnum, нужно сказать:

(defun poly (a b x) (declare (fixnum a b x)) (+ (* a (expt x 2)) (* b x))) Имя переменной в декларации ссылается на переменную, действительную в том же контексте, где встречается сама декларация.

Вы можете также задать тип любого выражения в коде с помощью the.

Например, если нам известно, что значения a, b и x не только принадлежат типу fixnum, но и достаточно малы, чтобы промежуточные выражения также принадлежали типу fixnum, вы можете указать это явно:

(defun poly (a b x) (declare (fixnum a b x)) (the fixnum (+ (the fixnum (* a (the fixnum (expt x 2)))) (the fixnum (* b x))))) Выглядит довольно неуклюже, не так ли? К счастью, есть две причины, по которым вам редко понадобится шпиговать численный код объявлениями the. Во-первых, это лучше поручить макросам.° Во-вторых, многие реализации используют особые трюки, чтобы ускорить целочисленную арифметику независимо от деклараций.

В Common Lisp существует невероятное многообразие типов; их набор практически не ограничен, ведь вы можете самостоятельно объявлять собственные типы. Однако явно объявлять типы имеет смысл только в некоторых случаях.

Вот два основных правила, когда это стоит делать:

1. Имеет смысл декларировать типы в тех функциях, которые могут работать с аргументами некоторых разных типов (но не всех). Если вам известно, что аргументы вызова функции + всегда будут fixnum или первый аргумент aref всегда будет массивом одного типа, декларация будет полезной.

2. Обычно имеет смысл декларировать лишь те типы, которые находятся внизу иерархии типов: объявления с fixnum или simple-array будут полезными, а вот декларации integer или sequence не принесут ощутимого результата.

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

Если о типе элементов массива ничего неизвестно, то он представляется в памяти как набор указателей. Однако если тип известен и все элементы принадлежат к одному типу, скажем double-float, тогда массив может быть представлен как набор чисел в формате double-float. Во-первых, такой массив будет более экономно использовать память. Во-вторых, отсутствие необходимости переходить по указателям приведет к более быстрому чтению и записи элементов.

13.3. Декларации типов

–  –  –

Рис. 13.1. Результат задания типа элементов массива

Тип массива можно задать с помощью аргумента :element-type в makearray. Такой массив называется специализированным. На рис. 13.1 показано, что будет происходить в большинстве реализаций при выполнении следующего кода:

(setf x (vector 1.234d0 2.345d0 3.456d0) y (make-array 3 :element-type ’double-float) (aref y 0) 1.234d0 (aref y 1) 2.345d0 (aref y 2) 3.456d0) Каждый прямоугольник на рисунке соответствует машинному слову в памяти. Каждый из двух массивов содержит заголовок неопределенной длины, за которым следует представление трех элементов. В массиве x каждый элемент – указатель. В нашем случае все три указателя одновременно ссылаются на элементы double-float, но могут ссылаться на произвольные объекты. В массиве y элементы действительно являются числами double-float. Второй вариант работает быстрее и занимает меньше места, но мы вынуждены платить за это ограничением на однородность массива.

Заметьте, что для доступа к элементам y мы пользовались aref. Специализированный вектор больше не принадлежит типу simple-vector, поэтому мы не можем ссылаться на его элементы с помощью svref.

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

(declare (type (vector fixnum 20) v)) Эта запись говорит о том, что вектор v имеет размерность 20 и специализирован для целых чисел типа fixnum.

Наиболее общая декларация включает тип массива, тип элементов и список размерностей:

(declare (type (simple-array fixnum (4 4)) ar)) 228 Глава 13. Скорость Массив ar теперь считается простым массивом 44, специализированным для fixnum.

На рис. 13.2 показано, как создать массив 1 0001 000 элементов типа single-float и как написать функцию, суммирующую все его элементы.

Массивы располагаются в памяти в построчном порядке (row-major order). Рекомендуется по возможности проходить по элементам массивов в таком же порядке.

–  –  –

Рис. 13.2. Суммирование по массиву Чтобы сравнить производительность sum-elts с декларациями и без них, воспользуемся макросом time. Он измеряет время, необходимое для вычисления выражения, причем в разных реализациях результаты его работы отличаются. Его применение имеет смысл только для скомпилированных функций.

Если мы скомпилируем sum-elts с параметрами, обеспечивающими максимально быстрый код, time вернет менее полсекунды:

(time (sum-elts a)) User Run Time = 0.43 seconds 1000000.0 Если же мы теперь уберем все декларации и перекомпилируем sum-elts, то те же вычисления займут больше пяти секунд:

(time (sun-elts a)) User Run Time = 5.17 seconds 1000000.0 Важность деклараций типов, особенно при работе с массивами и отдельными числами, сложно переоценить. В данном случае две строчки кода обеспечили нам двенадцатикратный прирост производительности.

13.4. Обходимся без мусора

–  –  –

и ее последующего сбора. Общим решением является заблаговременное выделение блоков памяти и их дальнейшее повторное использование «вручную». Заблаговременно означает в момент компиляции или некоторой процедуры инициализации. Когда скорость начинает играть роль, зависит от приложения.

Например, если обстоятельства позволяют нам ограничить размер стопки, то вместо ее создания из отдельных ячеек можно сделать так, что стопка будет расти и уменьшаться в рамках заранее выделенного вектора. Common Lisp имеет встроенную поддержку использования вектора в качестве стопки. Для этого есть необязательный параметр fill-pointer в make-array.

Первый аргумент make-array задает количество памяти, выделяемой под вектор, а fill-pointer, если задан, определяет его исходную фактическую длину:

(setf *print-array* t) T (setf vec (make-array 10 :fill-pointer 2 :initial-element nil)) #(NIL NIL) Функции работы с последовательностями будут рассматривать его как вектор из двух элементов:

(length vec) но его размер может вырасти до 10. Поскольку этот вектор имеет указатель заполнения, к нему можно применять функции vector-push и vectorpop, аналогичные push и pop для списков:

(vector-push ’a vec) vec #(NIL NIL A) (vector-pop vec) A vec #(NIL NIL) Вызов vector-push увеличил указатель заполнения и вернул его старое значение. Мы можем записывать в такой вектор новые значения до тех пор, пока указатель заполнения меньше начального размера вектора, заданного первым аргументом make-array. Когда свободное место закончится, vector-push вернет nil. В наш вектор vec мы можем поместить до 8 новых элементов.

Векторы с указателем заполнения имеют один недостаток – они более не принадлежат типу simple-vector, и вместо svref нам приходится использовать aref. Эти дополнительные затраты стоит учесть при выборе подходящего решения.

13.4. Обходимся без мусора Некоторые приложения могут производить очень длинные последовательности. В таком случае вам поможет использование map-into вместо map. В качестве первого аргумента она получает не тип новой последовательности, а саму последовательность, в которую будут записаны результаты. Из этой же последовательности могут браться и аргументы для функции, которая производит отображение. Для примера увеличим на единицу все элементы вектора:

(setf v (map-into v #’1+ v)) На рис. 13.3 показан пример приложения, работающего с длинными векторами. Это программа, генерирующая несложный словарь рифм (точнее, словарь ранее увиденных рифм).

–  –  –

В расчетных приложениях будьте аккуратны с типами bignum. Операции с bignum требуют выделения памяти и работают существенно медленнее. Но даже если ваша программа должна в конце возвращать значения bignum, ее можно сделать эффективнее, организовав промежуточные результаты как значения fixnum.

Другой способ избежать выделения памяти – заставить компилятор размещать объекты не в куче, а на стеке. Если вам известно, что какойлибо объект будет использоваться временно, вы можете избежать выделения для него памяти в куче с помощью декларации dynamic extent.

Декларируя dynamic-extent для переменной, вы утверждаете, что ее значение не будет жить дольше, чем сама переменная.

Как может значение существовать дольше переменной? Вот пример:

(defun our-reverse (lst) (let ((rev nil)) (dolist (x lst) (push x rev)) rev)) Функция our-reverse аккумулирует переданный ей список в обратном порядке в rev и по завершении возвращает ее значение. Сама переменная исчезает, а список, который в ней находился, продолжает существовать и возвращается назад вызвавшей функции. Дальнейшая его судьба непредсказуема.

Для контраста рассмотрим следующую реализацию adjoin:

(defun our-adjoin (obj lst &rest args) (if (apply #’member obj lst args) lst (cons obj lst)))

Из этого определения функции видно, что список args никуда не передается. Он нужен не дольше, чем сама переменная. Значит, в этой ситуации имеет смысл сделать декларацию dynamic-extent:

(defun our-adjoin (obj lst &rest args) (declare (dynamic-extent args)) (if (apply #’member obj lst args) lst (cons obj lst))) Теперь компилятор может (но не обязан) размещать args на стеке, то есть это значение будет автоматически отброшено по выходу из our-adjoin.

13.5. Пример: заранее выделенные наборы Чтобы избежать динамического выделения памяти в приложении, которое использует структуры данных, вы можете заранее разместить конкретное их количество в пуле (pool). Когда вам необходима структура,

13.5. Пример: заранее выделенные наборы вы берете ее из пула, а по завершении работы с ней возвращаете структуру назад в пул.° Чтобы проиллюстрировать эту идею, напишем прототип программы, контролирующей перемещение кораблей в гавани, а затем перепишем этот прототип с использованием пула.

На рис. 13.4 показана первая версия. Глобальная переменная *harbour* содержит список кораблей, каждый из которых представлен в виде структуры ship. Функция enter вызывается при заходе корабля в порт;

find-ship находит корабль с заданным именем (если он существует); leave вызывается, когда корабль покидает гавань.

–  –  –

Отличный подход для написания первой версии программы, но такая реализация производит достаточно много мусора. При выполнении программы память выделяется двумя путями: при заходе кораблей в гавань будут производиться новые структуры, а с ростом списка *harbour* будут выделяться новые ячейки.

Мы можем избавиться от обоих источников мусора, выделяя память в момент компиляции. На рис. 13.5 приведена вторая версия программы, которая не производит никакого мусора.

Строго говоря, выделение памяти все же происходит, но не в момент выполнения. Во второй версии *harbour* является хеш-таблицей, а не списком, и пространство под нее выделяется при компиляции. Тысяча структур ship также создается во время компиляции и сохраняется в векторе pool. (Если параметр :fill-pointer имеет значение t, указатель заполнения размещается в конце вектора.) Теперь при вызове enter нам не нужно создавать новую структуру, достаточно получить одну из уже существующих в пуле с помощью make-ship. А когда leave удаляет корабль из гавани, соответствующая структура не становится мусором, а возвращается назад в пул.

234 Глава 13. Скорость

–  –  –

Используя пулы, мы собственноручно выполняем часть работы по управлению памятью. Сделает ли это нашу программу быстрее, зависит от того, как конкретная реализация управляет памятью. Грубо говоря, использование пулов оправдано лишь в реализациях с примитивными сборщиками мусора, а также в приложениях реального времени, где непредсказуемый запуск сборщика мусора может вызвать проблемы.

13.6. Быстрые операторы В начале главы было сказано, что Лисп – это, по сути, два разных языка.

Если вы приглядитесь к дизайну Common Lisp, то увидите, что часть его операторов предназначена для ускорения выполнения, а другая часть – для удобства разработки.

Например, для доступа к элементу вектора существуют три оператора:

elt, aref, svref. Такое разнообразие позволяет выжать из программы максимум производительности. На тех участках, где важна скорость, используйте svref вместо elt, которая работает и с массивами, и со списками.

Для работы со списками эффективнее использовать специализированную функцию nth, нежели elt. Лишь одна функция, length, не имеет аналогов для разных типов. Почему в Common Lisp нет отдельной версии этой функции для списков? Потому что программа, выполняющая

13.6. Быстрые операторы подсчет длины списка, уже безнадежна в плане производительности.

В этом случае, как и во многих других, сам дизайн языка объясняет, что является эффективным, а что – нет.

Другая пара похожих функций – eql и eq. Первый предикат проверяет на идентичность, второй – на одинаковое размещение в памяти. Второй предикат обеспечивает большую эффективность, однако его стоит использовать, если только вам заранее известно, что аргументы не являются числами или знаками. Два объекта равны с точки зрения eq, если они имеют одинаковое размещение в памяти. Числа и знаки не обязаны располагаться в каком-либо определенном месте в памяти, поэтому eq к ним неприменима (хотя во многих реализациях eq работает с типом fixnum). Для любых других аргументов eq будет работать аналогично eql.

Разумеется, быстрее всего выполнять сравнение объектов с помощью eq, так как при этом Лиспу достаточно сравнить лишь два указателя.

Это значит, что хеш-таблицы с тестовой функцией eq (см. рис. 13.5) обеспечивают самый быстрый доступ. В таких таблицах gethash хеширует лишь указатели и даже не смотрит, на что они указывают. Помимо скорости доступа с хеш-таблицами связан еще один момент. Использование eq- и eql-таблиц приводит к дополнительным издержкам в случае применения копирующей сборки мусора, поскольку после каждой сборки хеши таких таблиц должны быть пересчитаны. Если это вызывает проблемы, лучше использовать eql-таблицы и числа типа fixnum в качестве ключей.

Вызов reduce может быть эффективнее вызова apply,1 когда функция принимает остаточный параметр.

Например, вместо выражения (apply #’+ ’(1 2 3)) эффективнее использовать следующее выражение:

(reduce #’+ ’(1 2 3)) Кроме того, важно не только вызывать правильные функции, но и вызывать их правильно. Необязательные аргументы, аргументы по ключу и остаточные аргументы дорогостоящи. В случае обычных аргументов вызывающая сторона кладет их в заранее известное вызванной функции место, в то время как для других аргументов требуется дополнительная обработка на этапе выполнения. Хуже всего в этом отношении дело обстоит с аргументами по ключу. Для встроенных функций, использующих эти аргументы, хорошие компиляторы используют особые подходы, чтобы получить быстрый код2. Но в ваших собственных функциях рекомендуется избегать использования аргументов по ключу на Это утверждение автора является довольно сомнительным. По крайней мере, для ряда современных реа лизаций на приведенном примере наблюдается выраженный противоположный эффект. – Прим. перев.

Речь идет о таких техниках, как, например, прямое кодирование (open co

–  –  –

критических в плане скорости участках программы. Также разумно не передавать много значений через остаточный аргумент там, где этого можно избежать.

Индивидуальные компиляторы иногда применяют особые оптимизации. Например, некоторые могут оптимизировать вызов case с целочисленными ключами в небольшом диапазоне их значений. Как правило, узнать подробнее о специфических оптимизациях в вашей реализации вы можете из документации к ней.

13.7. Две фазы разработки Если в вашем приложении производительность имеет первостепенное значение, в качестве одного из решений попробуйте переписать критические участки на низкоуровневом языке, например на С или ассемблере. Такой подход применим не только к Лиспу, но и к любому высокоуровневому языку – критические участки программы на С часто переписываются на ассемблере, – но чем абстрактнее язык, тем больше преимуществ дает разбиение разработки на две фазы.

Стандарт Common Lisp не описывает механизм интеграции кода, написанного на других языках. Эта задача полностью ложится на плечи разработчиков конкретной реализации, и почти все из них так или иначе решают ее.1 Вам может показаться напрасной тратой времени написание части кода на одном языке с последующим переписыванием ее на другом. Тем не менее практика показала, что это отличный способ написания приложений. Оказалось, что проще сначала разработать функциональность программы, а затем ее оптимизировать, чем делать это одновременно.

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

Независимо от проработанности спецификаций исследовательский компонент в написании программ очень важен, и часто намного важнее, чем этого ожидают.

Казалось бы, если спецификации были хорошими, то программирование заключалось бы лишь в кодировании. Это порочная идея, хотя и распространенная. Исследовательская компонента важна уже хотя бы потому, что любая спецификация по определению содержит недостатки. Иначе она не была бы спецификацией.

В других областях точность спецификации может иметь первостепенное значение. Если вы просите выточить из куска металла определенБиблиотеки CFFI и UFFI предоставляют обобщенный механизм использования интерфейса с внешним кодом (foreign function interface), доступный в разных реа лизациях. – Прим. перев.

Итоги главы ную форму, необходимо как можно точнее описать, что вы хотите получить. Но это правило не распространяется на программы, поскольку и спецификации, и программный код делаются из одного и того же материала: текста. Вы не можете разработать спецификацию, которая в точности описывает все требования задачи. В противном случае это была бы уже готовая программа.° В приложениях, подразумевающих значительное количество исследований (объем которых опять же превзойдет ожидания), имеет смысл разделять реализацию программы на две фазы. Промежуточный результат после первой фазы не будет окончательным. Например, при ваянии бронзовой скульптуры принято делать первый набросок из глины, который затем используется для создания формы, в которую будет отлита скульптура из бронзы.° И хотя в завершенной скульптуре глины не остается, эффект от ее использования все равно заметен. Теперь вообразите, насколько сложней была бы та же задача при наличии лишь слитка бронзы и зубила. По тем же причинам удобнее написать программу на Лиспе, а затем переписать на С, чем писать ее на С с самого начала.

Итоги главы

1. К оптимизации не следует приступать раньше времени. Основное внимание нужно уделять узким местам и начинать следует с выбора оптимального алгоритма.

2. Доступно пять параметров управления компиляцией. Они могут устанавливаться как глобальными, так и локальными декларациями.

3. Хорошие компиляторы могут оптимизировать хвостовую рекурсию, превращая ее в циклы. Встраивание кода позволяет избежать вызова функций.

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

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

6. В ряде ситуаций полезно брать объекты из предварительно созданного пула.

7. Некоторые части Лиспа предназначены для быстрой работы, некоторые – для гибкой.

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

238 Глава 13. Скорость

–  –  –

Эта глава необязательна. В ней описывается ряд эзотерических особенностей языка. Common Lisp похож на айсберг: огромная часть его возможностей не видна для большинства пользователей. Быть может, вам никогда не придется определять пакеты или макросы чтения самостоятельно, но знание подобных моментов может сильно облегчить жизнь.

14.1. Спецификаторы типов В Common Lisp типы не являются объектами. Так, к примеру, нет объекта, соответствующего типу integer. То, что мы получаем при вызове type-of и передаем в качестве аргумента функции typep, является не типом, а спецификатором типа.

Спецификатор типа – это его имя. Простейшими спецификаторами типов являются символы типа integer. Они формируют иерархию типов во главе с типом t, к которому принадлежат все объекты. Иерархия типов не является деревом. Например, от nil наверх ведут два пути: один через atom, а второй через list и sequence.

На самом деле, тип – это просто множество объектов. Это означает, что количество типов, как и количество множеств объектов, может быть бесконечным. Некоторые типы обозначаются атомарно, например integer определяет множество целых чисел. Но мы можем также конструировать составные спецификаторы типов, которые ссылаются на любые множества объектов.

Например, пусть a и b – спецификаторы некоторых типов, тогда (or a b) обозначает объединение множеств объектов, соответствующих типам a и b. Таким образом, объект будет принадлежать типу (or a b), если он принадлежит типу a или типу b.

240 Глава 14. Более сложные вопросы

Если бы circular? была функцией, возвращающей истину для циклических по хвосту списков, то для определения набора правильных последовательностей можно было бы использовать следующий спецификатор:1

(or vector (and list (not (satisfies circular?))))

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

(integer 1 100) В таких случаях говорят, что спецификатор определяет конечный тип.

В составном спецификаторе типа некоторые поля могут оставаться неопределенными. Такое поле помечается * вместо параметра. Так, (simple-array fixnum (* *)) описывает набор двумерных простых массивов, специализированных для fixnum, а (simple-array fixnum *) описывает множество (надтип предыдущего) простых массивов, специализированных для fixnum.

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

(simple-array fixnum) Если составной тип не содержит аргументов, то он эквивалентен атомарному. Таким образом, тип simple-array описывает множество всех простых массивов.

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

defmacro, только он раскрывается не в выражение, а в спецификатор типа. С помощью следующего определения:

(deftype proseq () ’(or vector (and list (not (satisfies circular?))))) мы создаем новый атомарный спецификатор proseq:

(typep #(1 2) ’proseq) T Если вы определите составной спецификатор с аргументами, то они не будут вычисляться, как и в случае defmacro. Так, (deftype multiple-of (n) ‘(and integer (satisfies (lambda (x) (zerop (mod x,n)))))) Несмотря на то, что этот факт обычно не упоминается в стандарте, вы можете использовать в спецификаторах типов выражения and и or с любым количеством аргументов, подобно макросам and и or.

14.2. Бинарные потоки определяет (multiple-of n) как спецификатор для всех множителей n:

(typep 12 ’(multiple-of 4)) T Спецификаторы типов интерпретируются и поэтому работают медленно, так что в общем случае для подобных проверок лучше определить функцию.

–  –  –

14.3. Макросы чтения В разделе 7.5 была представлена концепция макрознаков – знаков, имеющих особое значение для read. С каждым из них связана функция, указывающая read, что делать при встрече этого знака. Вы можете изменять определения функций, связанных с уже существующими макрознаками, а также определять собственные макросы чтения.

Функция set-macro-character предоставляет один из способов определения макросов чтения. Она принимает знак и функцию, вызываемую read при встрече этого знака.

242 Глава 14. Более сложные вопросы Одним из старейших макросов чтения в Лиспе является ’, quote. Мы могли бы определить его следующим образом:

(set-macro-character #\’ #’(lambda (stream char) (list (quote quote) (read stream t nil t)))) Когда read встречает ’ в обычном контексте, она возвращает результат вызова данной функции для текущего состояния потока и знака. (В данном случае функция игнорирует свой второй аргумент, так как он всегда является кавычкой.) Поэтому когда read увидит ’a, она вернет (quote a).

Теперь можно понять смысл последнего аргумента read. Он сообщает, произведен ли вызов read внутри другого вызова read.

Следующие аргументы read будут одинаковыми практически для всех макросов чтения:

первый аргумент – поток; второй аргумент, t, сообщает, что при достижении конца файла read будет сигнализировать об ошибке; третий аргумент задает значение, возвращаемое вместо данной ошибки в случае истинности второго аргумента (в нашем примере он не применяется);

четвертый аргумент, t, сообщает о рекурсивности вызова read.

Вы можете определять (с помощью make-dispatch-macro-character) свои собственные диспетчеризирующие макрознаки, но раз # уже определен для этой цели, можно пользоваться и им. Шесть комбинаций, начинающихся с #, явным образом зарезервированы для ваших нужд: #!, #?, #[, #], #{ и #}.

Новую комбинацию с управляющим макрознаком можно определить с помощью вызова функции set-dispatch-macro-character, которая схожа с set-macro-character, но set-dispatch-macro-character принимает не один, а два знака.

Следующий код определяет #? в качестве макроса чтения, возвращающего список целых чисел:

(setf-dispatch-macro-character #\# #\?

#’(lambda (stream char1 char2) (list ’quote (let ((lst nil)) (dotimes (i (+ (read stream t nil t) 1)) (push i lst)) (nreverse lst)))))

Теперь #?n будет прочитан как список всех целых чисел от 0 до n. Например:

#?7 (0 1 2 3 4 5 6 7)

Второе место по распространенности после простых макрознаков занимают знаки-ограничители списков. Еще одна комбинация, зарезервированная для пользователя, – #{. Вот пример определения более продвинутых скобок:

(set-macro-character #\} (get-macro-character #\)))

14.4. Пакеты

–  –  –

14.4. Пакеты Пакет – это объект Лиспа, сопоставляющий именам символы. Текущий пакет всегда хранится в глобальной переменной *package*. При запуске Common Lisp стартовым пакетом является common-lisp-user, неформально известный также как пользовательский пакет. Функция packagename возвращает имя текущего пакета, а find-package возвращает пакет с заданным именем:

(package-name *package*) "COMMON-LISP-USER" (find-package "COMMON-LISP-USER") #Package "COMMON-LISP-USER" 4CD15E Обычно символ интернируется в пакет, являющийся текущим на момент его чтения. Функция symbol-package принимает символ и возвращает пакет, в который он был интернирован.

(symbol-package ’sym) #Package "COMMON-LISP-USER" 4CD15E Интересно, что это выражение вернуло именно такое значение, поскольку оно должно было быть считано перед вычислением, а само считывание привело к интернированию sym. Для последующего применения присвоим sym некоторое значение:

244 Глава 14. Более сложные вопросы (setf sym 99)

Теперь мы создадим новый пакет и переключимся в него:

(setf *package* (make-package ’mine :use ’(common-lisp))) #Package "MINE" 63390E В этот момент должна зазвучать зловещая музыка, ибо теперь мы в ином мире, где sym перестал быть тем, чем был раньше:

MINE sym Error: SYM has no value.

Почему это произошло? Чуть раньше мы установили sym в 99, но сделали это в другом пакете, а значит, для другого символа, нежели sym в пакете mine.1 Чтобы сослаться на исходный sym из другого пакета, необходимо его предварить именем его родного пакета и парой двоеточий:

MINE common-lisp-user::sym Итак, несколько символов с одинаковыми именами могут сосуществовать, если находятся в разных пакетах. Один символ находится в пакете common-lisp-user, другой – в mine, и это разные символы. В этом заключается весь смысл пакетов. Поместив свою программу в отдельный пакет, вы можете не переживать, что кто-то использует выбранные вами имена функций и переменных где-то еще. Даже если где-либо будет использовано такое же имя, как у вас, это будет уже другой символ.

Пакеты также предоставляют возможность сокрытия информации.

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

Использование пары двоеточий для обозначения символа не из текущего пакета считается плохим стилем. Фактически вы нарушаете модульность, которая устанавливается пакетами. Если вам приходится использовать двойное двоеточие для ссылки на символ, это означает, что кто-то не хочет, чтобы вы на него ссылались.

Обычно следует ссылаться лишь на экспортированные символы. Если мы вернемся назад в пользовательский пакет (in-package устанавливает *package*) и экспортируем символ, интернированный в нем, MINE (in-package common-lisp-user) #Package "COMMON-LISP-USER" 4CD15E (export ’bar) T Некоторые реа лизации Common Lisp печатают имя пакета перед приглашением toplevel, когда вы находитесь не в пользовательском пакете.

14.4. Пакеты (setf bar 5) то сделаем его видимым и в других пакетах. Теперь, вернувшись в пакет mine, мы сможем ссылаться на bar через одинарное двоеточие, поскольку отныне это публично доступное имя:

(in-package mine) #Package "MINE" 63390E MINE common-lisp-user:bar Кроме того, мы можем сделать еще один шаг и импортировать символ

bar в текущий пакет, и тогда пакет mine будет делить его с пользовательским пакетом:

MINE (import ’common-lisp-user:bar) T MINE bar На импортированный символ можно ссылаться без какого-либо префикса. Оба пакета теперь делят этот символ, а значит, уже не может быть отдельного символа mine:bar.

А что произойдет, если такой символ уже был? В таком случае импорт вызовет ошибку, подобную той, которую мы увидим, попытавшись импортировать sym:

MINE (import ’common-lisp-user::sym) Error: SYM is already present in MINE.

Ранее мы предпринимали неудачную попытку вычислить sym в mine, которая привела к тому, что этот символ был интернирован в mine. У него не было значения, и это вызвало ошибку, но интернирование все равно произошло, просто потому, что он был набран и считан, когда текущим пакетом был mine. Поэтому теперь, когда мы пытаемся импортировать sym в mine, символ с таким именем уже есть в этом пакете.

Другой способ получить доступ к символам другого пакета – использовать сам пакет:

MINE (use-package ’common-lisp-user) T Теперь все символы, экспортированные пользовательским пакетом, принадлежат mine. (Если sym экспортировался пользовательским пакетом, то этот вызов приведет к ошибке.) common-lisp – это пакет, содержащий имена всех встроенных операторов и функций.

Так как мы передали имя этого пакета аргументу :use вызова make-package, который создал пакет mine, в нем будут видимы все имена Common Lisp:

246 Глава 14. Более сложные вопросы MINE #’cons #Compiled-Function CONS 462A3E Как и компиляция, операции с пакетами редко выполняются непосредственно в toplevel. Гораздо чаще их вызовы содержатся в файлах с исходным кодом. Обычно достаточно поместить в начале файла defpackage и in-package, как на стр. 148.

Модульность, создаваемая пакетами, несколько своеобразна. Она дает нам модули не объектов, а имен. Каждый пакет, использующий commonlisp, имеет доступ к символу cons, поскольку в пакете common-lisp задана функция с таким именем. Но как следствие этого и переменная с именем cons будет видима во всех пакетах, использующих common-lisp.

Если пакеты сбивают вас с толку, то основная причина этого в том, что они основываются не на объектах, а на их именах.°

14.5. Loop Макрос loop первоначально был разработан в помощь начинающим Лисп-программистам для написания итеративного кода, позволяя использовать для этого выражения, напоминающие обычные английские фразы, которые затем транслируются в Лисп-код. К несчастью, loop оказался похож на английский язык в большей степени, чем предполагали его создатели: в несложных случаях вы можете использовать его, совершенно не задумываясь о том, как это работает, но понять общий принцип его действия практически невозможно.

Если вы желаете ознакомиться с loop за один день, то для вас есть две новости: хорошая и плохая. Хорошая заключается в том, что вы не одиноки: мало кто в действительности понимает, как он работает. Плохая же состоит в том, что вы, вероятно, никогда этого не поймете, хотя бы потому, что стандарт ANSI фактически не предоставляет формального описания его поведения.

Единственным определением loop является его реализация, а единственным способом изучить его (насколько это возможно) являются примеры. В стандарте ANSI в главе, описывающей loop, имеется большой набор примеров, и мы применим здесь такой же подход, чтобы познакомить вас с основными концепциями этого макроса.

Первое, что люди замечают в макросе loop, – это наличие у него синтаксиса. Его тело состоит не из подвыражений, а из предложений, которые не разделяются скобками. Каждое предложение имеет свой синтаксис. В целом, loop-выражения напоминают Алгол-подобные языки.

Но есть одно серьезное отличие, сильно отдаляющее loop от Алгола: порядок, в котором следуют предложения, весьма слабо определяет порядок, в котором они будут исполняться.

Вычисление loop-выражения осуществляется в три этапа, причем каждое предложение может вносить свой вклад более чем в один из них.

Вот эти этапы:

14.5. Loop

–  –  –

(loop for x in ’(1 2 3 4) collect (1+ x)) (2 3 4 5) При использовании in вместо from в for-предложении переменная по очереди принимает значения каждого из элементов списка, а не последовательных целых чисел.

В приведенном примере collect оказывает влияние на все три этапа.

В прологе создается анонимный аккумулятор, имеющий значение nil;

в теле (1+ x) к аккумулятору прибавляется 1, а в эпилоге возвращается значение аккумулятора.

Это наш первый пример, возвращающий какое-то конкретное значение. Существуют предложения для явного задания возвращаемого значения, но в их отсутствие этим занимается collect. Фактически эту же работу мы могли бы выполнить через mapcar.

Наиболее часто loop используется для сбора результатов вызова некоторой функции определенное количество раз:

(loop for x from 1 to 5 collect (random 10)) (3 8 6 5 0) В данном примере мы получили список из пяти случайных чисел.

Именно для этой цели мы уже определяли функцию map-int (стр. 117).

Тогда зачем же мы это делали, если у нас есть loop? Но точно так же можно спросить: зачем нам нужен loop, когда у нас есть map-int?°

С помощью collect можно также аккумулировать значения в именованную переменную. Следующая функция принимает список чисел и возвращает списки его четных и нечетных элементов:

(defun even/odd (ns) (loop for n in ns if (evenp n) collect n into evens else collect n into odds finally (return (values evens odds)))) Предложение finally добавляет код в эпилог. В данном случае оно определяет возвращаемое выражение.

Предложение sum похоже на collect, но накапливает значения в виде числа, а не списка.

Сумму всех чисел от 1 до n мы можем получить так:

(defun sum (n) (loop for x from 1 to n sum x)) Более детальное рассмотрение loop содержится в приложении D, начиная со стр. 331. Приведем несколько примеров: рис. 14.1 содержит две итеративные функции из предыдущих глав, а на рис. 14.2 показана аналогичная их реализация с помощью loop.

14.5. Loop

–  –  –

Рис. 14.2. Итерация с помощью loop

14.6. Особые условия В Common Lisp особые условия (conditions) включают ошибки и другие ситуации, которые могут возникать в процессе выполнения. Когда сигнализируется какое-либо условие, вызывается соответствующий обработчик. Обработчик по умолчанию для условий-ошибок обычно вызывает цикл прерывания. Но Common Lisp предоставляет и разнообразные операторы для сигнализации и обработки условий. Вы можете переопределять уже существующие обработчики и даже писать собственные.

Большинству программистов не придется работать с особыми условиями непосредственно. Однако есть несколько уровней более абстрактных операторов, которые используют условия, поэтому для их понимания все же полезно иметь представление о механизме, изложенном ниже.

14.6. Особые условия

–  –  –

Error: I wanted a CHICHEN sandwich.

Options: :abort, :backtrace, :continue :continue New value of (CAR SANDWICH)? ’chicken (CHICKEN ON RYE) Также имеется возможность создавать собственные обработчики, но этим редко кто пользуется. Обычно обходятся уже имеющимися средствами, например ignore-errors. Этот макрос ведет себя аналогично progn, если ни один из его аргументов не приводит к ошибке. Если же во время выполнения одного из выражений сигнализируется ошибка, то работа не прерывается, а выражение ignore-errors немедленно завершается с возвратом двух значений: nil и условия, которое было просигнализировано.

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

(defun user-input (prompt) (format t prompt) (let ((str (read-line))) (or (ignore-errors (read-from-string str)) nil)))

Функция вернет nil, если считанное выражение содержит синтаксическую ошибку:

(user-input "Please type an expression ") Please type an expression #%@#+!!

NIL Пример: логический вывод Глава 15.

В следующих трех главах вашему вниманию предлагаются три самостоятельные программы. Они были выбраны, чтобы показать, какой вид могут принимать программы на Лиспе, и продемонстрировать задачи, для решения которых этот язык особенно хорошо подходит.

В этой главе мы напишем программу, совершающую логические «умозаключения», основанные на наборе правил «если-то». Это классический пример, который не только часто встречается в учебниках, но и отражает изначальную концепцию Лиспа как языка «символьных вычислений». Многие ранние программы на Лиспе имеют черты той, которая описана ниже.

15.1. Цель В данной программе мы собираемся представлять информацию в знакомой нам форме: списком из предиката и его аргументов. Представим факт отцовства Дональда по отношению к Нэнси таким образом:

(parent donald nancy) Помимо фактов наша программа будет использовать правила, которые сообщают, что может быть выведено из имеющихся фактов. Мы будем представлять эти правила так:

(- заголовок тело) где заголовок соответствует следствию, а тело – условию. Переменные внутри них мы будем представлять символами, начинающимися со знака вопроса. Таким образом, следующее правило:

(- (child ?x ?y) (parent ?y ?x)) 254 Глава 15. Пример: логический вывод сообщает, что если y является родителем x, то x является ребенком y, или, говоря более точно, мы можем доказать любой факт вида (child x y) через доказательство (parent y x).

Тело (условная часть правила) может быть составным выражением, включающим логические операторы and, or, not.

Так, правило, согласно которому, если x является мужчиной и родителем y, то x – отец y, выглядит следующим образом:

(- (father ?x ?y) (and (parent ?x ?y) (male ?x)))

Одни правила могут опираться на другие. К примеру, правило, определяющее, является ли x дочерью y, опирается на уже определенное правило родительства:

(- (daughter ?x ?y) (and (child ?x ?y) (female ?x))) При доказательстве выражений может применяться любое количество правил, необходимых для достижения твердой почвы фактов. Этот процесс иногда называют обратной цепочкой логического вывода (backward chaining). Обратной потому, что вывод сперва рассматривает часть-следствие, чтобы увидеть, будет ли правило полезным, прежде чем продолжать доказательство части-условия. А цепочкой он называется потому, что правила зависят друг от друга, формируя цепочку (скорее даже дерево) правил, которая ведет от того, что мы хотим доказать, к тому, что мы уже знаем.°

15.2. Сопоставление Чтобы написать нашу программу для обратной цепочки логического вывода, нам понадобится функция, выполняющая сопоставление с образцом (pattern-matching). Эта функция должна сравнивать два списка, возможно, содержащие переменные, и проверять, есть ли такая комбинация значений переменных, при которой списки стали бы равными.

Например, если ?x и ?y – переменные, то два списка:

(p ?x ?y c ?x) (p a b c a) сопоставляются, если ?x = a и ?y = b, а списки (p ?x b ?y a) (p ?y b c a) сопоставляются при ?x = ?y = c.

На рис. 15.1 показана функция match, сопоставляющая два дерева.

Если они могут совпадать, то она возвращает ассоциативный список, показывающий, каким образом они совпадают:

(match ’(p a b c a) ’(p ?x ?y c ?x)) ((?Y. B) (?X. A)) T

15.2. Сопоставление (match ’(p ?x b ?y a) ’(p ?y b c a)) ((?Y. C) (?X. ?Y)) T (match ’(a b c) ’(a a a) NIL По мере поэлементного сравнения match накапливает присваивания переменным значений, которые мы называем связями (bindings), в переменной binds. Если сопоставление завершилось успешно, то match возвращает сгенерированные связи, в противном случае возвращает nil.

Так как не все успешные сопоставления генерируют хоть какие-то связи, match, по тому же принципу, что и gethash, возвращает второе значение, указывающее на успешность сопоставления.

(match ’(p ?x) ’(p ?x)) NIL T

–  –  –

Рис. 15.1. Функции для сопоставления Когда match возвращает nil и t, как произошло выше, это означает, что имеет место успешное сопоставление, не создавшее связей для переменных.

Алгоритм действия match можно описать следующим образом:

1. Если x и y равны с точки зрения eql, то они сопоставляются; иначе:

2. Если x – это переменная, уже ассоциированная со значением, то она сопоставляется с y, если значения совпадают; иначе:

256 Глава 15. Пример: логический вывод

3. Если y – это переменная, уже ассоциированная со значением, то она сопоставляется с x, если значения совпадают; иначе:

4. Если переменная x не ассоциирована со значением, то с ней связывается текущее значение; иначе:

5. Если переменная y не ассоциирована со значением, то с ней связывается текущее значение; иначе:

6. Два значения сопоставляются, если они оба – cons-ячейки, их carэлементы сопоставляются, а cdr сопоставляются с учетом полученных связей.

Вот два примера, демонстрирующие по порядку все шесть случаев:

(match ’(p ?v b ?x d (?z ?z)) ’(p a ?w c ?y ( e e)) ’((?v. a) (?w. b))) ((?Z. E) (?Y. D) (?X. C) (?V. A) (?W. B)) T Чтобы найти ассоциированное значение (если оно имеется), match вызывает binding. Эта функция должна быть рекурсивной, так как в результате сопоставления могут получиться пары, в которых переменная связана со значением косвенно, например ?x может быть связан с a через список, содержащий (?x. ?y) и (?y. a).

(match ’(?x a) ’(?y ?y)) ((?Y. A) (?X. ?Y)) T Сопоставив ?x с ?y, а ?y с a, мы видим косвенную связь переменной ?x со значением.

15.3. Отвечая на запросы Теперь, когда введены основные концепции сопоставления, мы можем перейти непосредственно к назначению нашей программы: если мы имеем выражение, вероятно, содержащее переменные, то исходя из имеющихся фактов и правил мы можем найти все ассоциации, делающие это выражение истинным. Например, если у нас есть только тот факт, что (parent donald nancy) и мы просим программу доказать (parent ?x ?y) то она вернет нечто, похожее на (((?x. donald) (?y. nancy))) Это означает, что наше выражение может быть истинным лишь в одном случае: ?x – это donald, а ?y – nancy.

15.3. Отвечая на запросы Поскольку у нас есть функция сопоставления, можно утверждать, что мы на правильном пути. Теперь нам нужно научиться определять правила. Соответствующий код приведен на рис. 15.2. Правила содержатся в хеш-таблице *rules* в соответствии с предикатами в заголовках. Это вводит ограничение, что переменные не могут находиться на месте предикатов. От него можно избавиться, если хранить такие правила в отдельном списке, но тогда для доказательства чего-либо нам пришлось бы сопоставлять друг другу каждое правило из этого списка.

–  –  –

Рис. 15.2. Определение правил Мы будем использовать макрос - для определения и правил, и фактов.

Факт представляется в виде правила, содержащего только заголовок.

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

Вот два уже знакомых нам примера:

(- (parent donald nancy)) (- (child ?x ?y) (parent ?y ?x)) Вызов - возвращает номер нового правила для заданного предиката;

оборачивание length вокруг push позволяет избежать большого объема информации, выводимой в toplevel.

На рис. 15.3 содержится большая часть кода, нужного нам для вывода.

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

Если выражение не содержит логических операторов, то вызывается prove-simple. Именно здесь происходит сам обратный вывод. Эта функция ищет все правила с истинным предикатом и пытается сопоставить заголовок каждого из них с фактом, который мы хотим доказать. Затем для каждого совпавшего заголовка доказывается его тело с учетом новых связей, созданных match.

Вызовы prove возвращают списки связей, которые затем собираются mapcan:

(prove-simple ’parent ’(donald nancy) nil) (NIL) (prove-simple ’child ’(?x ?y) nil) (((#:?6. NANCY) (#:?5. DONALD) (?Y. #:?5) (?X. #:?6))) 258 Глава 15. Пример: логический вывод

–  –  –

Оба полученных значения подтверждают, что есть лишь один путь доказательства. (Если доказать утверждение не получилось, возвращается nil.) Первый пример был выполнен без создания каких-либо связей, в то время как во втором примере переменные ?x и ?y были связаны (косвенно) с nancy и donald.

Между прочим, мы видим здесь хороший пример высказанной ранее (стр. 39) идеи: поскольку наша программа написана в функциональном стиле, мы можем тестировать каждую функцию отдельно.

Теперь пара слов о том, зачем нужен gensym. Раз мы собираемся использовать правила, содержащие переменные, то нам нужно избегать наличия двух правил с одной и той же переменной. Рассмотрим два правила:

(- (child ?x ?y) (parent ?y ?x)) (- (daughter ?y ?x) (and (child ?y ?x) (female ?y))) В них утверждается, что для любого x и y 1) x является ребенком y, если y является родителем x; 2) y является дочкой x, если y является ребенком x и y – женщина. Связь между переменными в рамках одного праОтвечая на запросы вила имеет большое значение, а вот факт, что два правила используют одинаковые имена для определения переменных, совершенно случаен.

Если мы воспользуемся этими правилами в том виде, в каком только что их записали, то они не будут работать. Если мы попытаемся доказать, что a – дочь b, то сопоставление с заголовком второго правила даст связи ?y = a и ?x = b.

Имея такие связи, мы не сможем воспользоваться первым правилом:

(match ’(child ?y ?x) ’(child ?x ?y) ’((?y. a) (?x. b))) NIL Для гарантии того, что переменные будут действовать лишь в пределах одного правила, мы заменяем все переменные внутри правила на gensym.

Для этой цели определена функция change-vars. Так мы приобретаем защиту от совпадений с другими переменными в определениях других правил. Но, поскольку правила могут применяться рекурсивно, нам также нужна защита при сопоставлении с этим же правилом. Для этого change-vars должна вызываться не только при определении правил, но и при каждом их использовании.

Теперь остается лишь определить функции для доказательства составных утверждений. Соответствующий код приведен на рис. 15.4. Обработка выражений or или not предельно проста. В первом случае мы собираем все связи, полученные из каждого выражения в or. Во втором случае мы просто возвращаем имеющиеся связи, если выражение внутри not возвратило nil.

–  –  –

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

Теперь у нас есть рабочая программа, но она не очень удобна для конечного пользователя. Разбирать списки связей, возвращаемых prove, довольно сложно, а ведь с усложнением выражений они будут только расти. Эту проблему решает макрос with-answer, изображенный на рис. 15.5.

Он принимает запрос (не вычисленный) и вычисляет свое тело для каждого набора связей, полученных при обработке запроса, связывая каждую переменную запроса со значением, которое она имеет в текущем экземпляре связей:

(with-answer (parent ?x ?y) (format t "~A is the parent of ~A.~%" ?x ?y)) DONALD is the parent of NANCY.

NIL Этот макрос расшифровывает полученные связи и предоставляет удобный способ использования prove в наших программах. На рис. 15.6 показан результат его раскрытия, а рис. 15.7 демонстрирует некоторые примеры использования этого макроса.

–  –  –

Рис. 15.7. Программа в работе

15.4. Анализ Может показаться, что написанный нами код является простым и естественным решением поставленной задачи. На самом деле, он крайне неэффективен. В действительности, мы написали, по сути, интерпретатор, в то время как могли создать компилятор.

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

В таком случае основная часть работы будет выполняться на этапе компиляции, тогда как сейчас она выполняется непосредственно во время запуска. (Зародыш этой идеи можно увидеть в avg на стр. 181.) Будем представлять правила как функции, а не как списки. Вместо функций типа prove и prove-and, интерпретирующих выражения в процессе работы, у нас будут функции для преобразования выражений в код. Выражения становятся доступны в момент определения правила. Зачем ждать, пока выражение будет использовано, чтобы его проанализировать? Это относится и к with-answer, который будет вызывать функции типа - для генерации своего раскрытия.

262 Глава 15. Пример: логический вывод Кажется, что подобная программа будет значительно сложнее написанной в этой главе, но на деле реализация предложенной идеи займет всего в два-три раза больше времени. Читателям, желающим узнать больше о подобных методиках, рекомендуется посмотреть книги «On Lisp»

и «Paradigms of Artificial Intelligence Programming»1, которые содержат примеры программ, написанных в таком стиле.

Peter Norvig «Paradigms of Artificial Intelligence Programming», Morgan

–  –  –

В этой главе мы напишем небольшой HTML-генератор – программу, автоматически производящую набор связанных веб-страниц. Она не только демонстрирует различные концепции Лиспа, но и является хорошим примером разработки «снизу-вверх». Мы начнем с создания HTML-утилит общего назначения, которые затем будем рассматривать как язык, на котором и будем писать собственно генератор.

16.1. HTML HTML (HyperText Markup Language, язык разметки гипертекста) – это то, из чего состоят веб-страницы. Это очень простой язык, не имеющий продвинутых возможностей, но зато он легок в изучении. В этом разделе представлен обзор HTML.

Веб-страницы просматриваются с помощью веб-браузера, который получает код страницы (как правило, с удаленного компьютера), преобразовывает его в читаемый вид и выводит на экран. HTML-файл – это текстовый файл, содержащий разметку, воспринимаемую браузером как инструкции.

На рис. 16.1 приведен пример простого HTML-файла, а на рис. 16.2 показано, как он будет отображаться в браузере. Обратите внимание, что текст между угловыми скобками не отображается. Это и есть разметка.

HTML имеет два вида меток. Одни используются попарно:

метка... /метка Первая метка обозначает начало некоторого окружения, вторая помечает его окончание. Одной из меток такого рода является h2. Весь текст, находящийся между h2 и /h2, отображается увеличенным шрифтом.

(Наибольший шрифт задается h1.) 264 Глава 16. Пример: генерация HTML

–  –  –

Рис. 16.2. Внешний вид веб-страницы Другие парные метки: ol («ordered list», упорядоченный список) для создания нумерованного списка; center для центрирования текста;

a... («anchor», якорь) для создания ссылки.

Именно ссылки превращают текст в гипертекст. Текст, находящийся между a... и /a, отображается браузерами особым образом, как правило, с подчеркиванием. При нажатии на ссылку осуществляется переход на другую страницу, адрес которой содержится внутри метки. Следующая метка

16.2. Утилиты HTML a href="foo.html" означает ссылку на другой HTML-файл, находящийся в том же каталоге. Таким образом, при нажатии на ссылку на рис. 16.2 браузер загрузит и отобразит файл "research.html".

Ссылки не обязаны указывать на файлы в одном и том же каталоге, но могут указывать и на любой адрес в Интернете (хотя в нашем примере это не используется).

Другая разновидность меток не имеет маркера окончания. В нашем примере (см. рис. 16.1) используются метки br («break», разрыв) для перехода на новую строку и li («list item», элемент списка) для обозначения элемента внутри окружения списка. Разумеется, HTML содержит и другие метки, но в этой главе нам понадобятся лишь те, которые упомянуты на рис. 16.1.

16.2. Утилиты HTML В этом разделе мы определим некоторые утилиты для генерации HTML.

На рис. 16.3 показаны базовые утилиты для генерации разметки. Все они направляют вывод в *standard-output*, но мы всегда сможем перенаправить его, переназначив эту переменную.

–  –  –

Второй принимает тело кода и выводит результат его выполнения между метками:

(with center (princ "The Unbalanced Parenthesis")) center The Unbalanced Parenthesis /center NIL Оба эти макроса используют управляющие директивы ~( и ~) для печати меток в нижнем регистре. На самом деле, HTML не чувствителен к регистру, но метки в нижнем регистре легче воспринимаются, особенно если их много.

В то время как макрос as пытается разместить весь вывод на одной строке, макрос with располагает метки на отдельных строках. (Директива ~& обеспечивает начало вывода с новой строки.) Это делается лишь для того, чтобы HTML-файлы лучше читались. При отображении страниц пробельные символы вокруг меток не показываются.

Последняя утилита на рис. 16.3, brs, генерирует множественные разрывы строк. Во многих браузерах они могут использоваться для управления вертикальными отступами.

Рисунок 16.4 содержит утилиты для непосредственной генерации HTML.

Первая возвращает имя файла по заданному символу. В реальном приложении она могла бы вернуть полный путь к файлу в указанном каталоге. Здесь же она просто присоединяет к имени расширение ".html".

Макрос page служит для генерации всей страницы. Он схож с with-openfile, на основе которого построен. Выражения в его теле будут выполнены с привязкой *standard-output* к потоку, созданному при открытии файла, соответствующего символу name.

–  –  –

Рис. 16.4. Утилиты создания файлов

16.2. Утилиты HTML В разделе 6.7 было показано, как присваивать временные значения специальным переменным. В примере на стр. 124 мы устанавливали значение *print-base* в 16 в теле let. Раскрытие page похожим образом связывает *standard-output* с потоком, указывающим на HTML-файл. Если мы вызовем as или princ в теле page, то вывод будет перенаправлен в соответствующий файл.

Заголовок title будет напечатан в самом верху страницы. За ним следует весь остальной вывод. Таким образом, вызов:

(page ’paren "The Unbalanced Parenthesis" (princ "Something in his expression told her...")) приведет к тому, что файл "paren.html" будет иметь (поскольку html-file уже определен) следующее содержание:

titleThe Unbalanced Parenthesis/title center h2THE UNBALANCED PARENTHESIS/h2 /center brbrbr Something in his expression told her...

Здесь нам знакомы все метки, кроме title. Текст, заключенный в метку title, не будет появляться нигде на странице, но зато он будет отображаться браузером в заголовке окна.

–  –  –

16.3. Утилита для итерации В данном разделе мы определим утилиты общего назначения, которые нам понадобятся в дальнейшем. Можем ли мы заранее знать, что в процессе разработки нам понадобится та или иная утилита? Нет, не можем.

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

Наша новая утилита (рис. 16.6) будет разновидностью mapc. Она принимает функцию трех аргументов и список. Для каждого элемента списка функция применяется как для самого элемента, так и для предшествующего и последующего элементов. (Если предшествующего или последующего элемента нет, то вместо них используется nil.) (map3 #’(lambda (&rest args) (princ args)) ’(a b c d)) (A NIL B) (B A C) (C B D) (D C NIL) NIL Как и mapc, она всегда возвращает nil.1 Ситуации, в которых требуется подобная утилита, возникают довольно часто. С одной из них мы столкНа самом деле, mapc возвращает значение своего второго аргумента. – Прим.

–  –  –

16.4. Генерация страниц Подобно книгам и журналам, наборы веб-страниц часто имеют древовидную организацию. Книга может состоять из глав, которые содержат разделы, которые, в свою очередь, состоят из подразделов, и т. д. Вебстраницы часто имеют подобную структуру, хотя и не используют подобные термины.

В этом разделе мы напишем программу, генерирующую набор веб-страниц, имеющих следующую структуру. Первая страница представляет собой оглавление, содержащее ссылки на разделы, которые, в свою очередь, содержат ссылки на пункты, являющиеся отдельными страницами с обычным текстом. Каждая страница должна иметь ссылки для перемещения назад, вперед и наверх по древовидной структуре. Ссылки вперед и назад осуществляют переход в пределах одного уровня вложенности. Например, ссылка вперед на странице, представляющей пункт, будет указывать на следующий пункт данного раздела. По ссылке вверх 270 Глава 16. Пример: генерация HTML осуществляется переход от пункта к разделу, а от раздела к оглавлению. Кроме того, должен быть индекс – отдельная страница со ссылками, на которой перечисляются все пункты в алфавитном порядке. Описанная иерархия изображена на рис. 16.7.

–  –  –

Рис. 16.7. Структура сайта Операторы и структуры данных, необходимые для создания страниц, представлены на рис. 16.8. Наша программа будет работать с двумя типами объектов: пунктами, содержащими блоки текста, и разделами, содержащими списки ссылок на пункты.

–  –  –

Рис. 16.8. Создание сайта И разделы, и пункты содержат поле id. В качестве содержимого этого поля будут передаваться символы, имеющие два применения. Первое заключается в определениях defitem и defsection; здесь id – это уникальное имя, по которому мы будем ссылаться на пункт или раздел. Второе

16.4. Генерация страниц применение: мы будем использовать id в имени файла, представляющего пункт или раздел. К примеру, страница, представляющая пункт foo, будет записана в файл "foo.html".

Кроме того, разделы и пункты имеют поля title, которые должны быть строками и будут использоваться в качестве заголовков соответствующих страниц.

Порядок следования пунктов в разделе определяется из аргументов defsection, порядок следования разделов в оглавлении – из аргументов defsite.

На рис. 16.9. представлены функции, генерирующие оглавление и индекс. Константы contents и index являются строками, служащими заголовками этих страниц и именами соответствующих файлов.

–  –  –

Рис. 16.9. Генерация индекса и оглавления Функции gen-contents и gen-index в целом похожи друг на друга. Каждая из них открывает HTML-файл, генерирует заголовок и список ссылок. Разница лишь в том, что список пунктов в индексе должен быть отсортирован. Он строится с помощью функции all-items, которая использует функцию упорядочения title. Важно, что все заголовки сравГлава 16. Пример: генерация HTML ниваются функцией string-lessp, которая, в отличие от string, игнорирует регистр знаков.

В реальном приложении сравнение может быть более утонченным, например, оно может игнорировать начальные артикли «a» и «the».

Оставшийся код показан на рис. 16.10: gen-site генерирует весь набор веб-страниц, остальные функции генерируют разделы и пункты.

–  –  –

Рис. 16.10. Генерация сайта, разделов и пунктов Под полным набором страниц понимается оглавление, индекс, страницы, представляющие каждый из разделов, и страницы, представляющие каждый из пунктов. Оглавление и индекс создаются с помощью функций, представленных на рис. 16.9. Разделы и пункты генерируются gen-section, которая создает страницу раздела и вызывает gen-item для генерации страниц, представляющих каждый пункт в данном разделе.

16.4. Генерация страниц Эти две функции начинаются и заканчиваются похожим образом: обе принимают аргументы, представляющие сам объект, а также предыдущий и последующий объекты того же уровня вложенности; обе заканчиваются вызовом gen-move-buttons с целью сгенерировать кнопки для перемещения вперед, назад и вверх. Разница в середине: в отличие от gen-section, которая производит упорядоченный список ссылок на пункты, gen-item просто отправляет текст в выходной файл.

Каким будет текст каждого из пунктов – личное дело пользователя.

Этот текст, к примеру, вполне может содержать HTML-разметку. Или же он может быть сгенерирован другой программой.

Пример ручного создания небольшого набора страниц приведен на рис. 16.11. В нем приводится перечень недавних публикаций в Институте Печенюшек Судьбы.

(defitem des "Fortune Cookies: Dessert or Fraud?" "...") (defitem case "The Case for Pessimism" "...") (defsection position "Position Papers" des case) (defitem luck "Distribution of Bad Luck" "...") (defitem haz "Health Hazards of Optimism" "...") (defsection

Abstract

"Research Abstracts" luck haz) (defsite position abstract)

Рис. 16.11. Небольшой сайт Пример: объектыГлава 17.

В этой главе мы собираемся реализовать внутри Лиспа свой собственный объектно-ориентированный язык. Такие программы называют встроенными языками (embedded language). Встраивание объектно-ориентированного языка в Лисп – это идеальный пример. Он не только демонстрирует типичное использование Лиспа, но еще и показывает, как естественно ложатся основные понятия объектно-ориентированного программирования на фундаментальные абстракции Лиспа.

17.1. Наследование В разделе 11.10 объяснялось, чем обобщенные функции отличаются от передачи сообщений. В модели передачи сообщений объекты:

1. Имеют свойства.

2. Реагируют на сообщения.

3. Наследуют свойства и методы от предков.

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

Лисп предоставляет несколько способов хранения наборов свойств. Первый способ – представление объекта как хеш-таблицы и хранение его свойств в качестве ее элементов.

В этом случае мы можем получить доступ к конкретным свойствам с помощью gethash:

(gethash ’color obj) Поскольку функции – это объекты данных, мы также можем хранить их как свойства. Это означает, что мы также можем хранить и методы.

17.1. Наследование Чтобы вызвать определенный метод объекта, необходимо применить

funcall к свойству с именем метода:

(funcall (gethash ’move obj) obj 10)

Используя такой подход, можно определить синтаксис передачи сообщений в стиле Smalltalk:

(defun tell (obj message &rest args) (apply (gethash message obj) obj args))

Теперь, чтобы приказать объекту передвинуться на 10, мы можем сказать:

(tell obj ’move 10) По сути, единственный ингредиент, которого не хватает голому Лиспу, – это поддержка наследования. Мы можем реализовать простейший ее вариант с помощью определения рекурсивной версии gethash, как показано на рис. 17.1. (Имя rget – это сокращение от «recursive get», рекурсивное получение.) Теперь с помощью восьми строк кода мы получаем все три вышеперечисленные элемента объектной ориентированности.

–  –  –

Теперь можно запросить площадь our-circle.

Она будет вычисляться в соответствии с только что определенным для класса методом: rget считывает свойство, а tell применяет метод:

(rget ’radius our-circle) T (tell our-circle ’area) 12.566370614359173 Прежде чем браться за усовершенствование данной программы, разберемся с тем, что мы уже сделали. Те самые восемь строчек кода превратили голую версию Лиспа без CLOS в объектно-ориентированный язык.

Как нам удалось решить столь непростую задачу? Должно быть, тут скрыт какой-то трюк: реализовать объектную ориентированность восемью строчками кода!

Да, трюк здесь определенно присутствует, но он скрыт не в нашей программе. Дело в том, что Лисп в некотором смысле уже был объектноориентированным или скорее даже более общим языком. Все, что нам понадобилось, – это добавить новый фасад вокруг абстракций, которые в нем уже имелись.

17.2. Множественное наследование Пока что мы умеем осуществлять лишь одиночное наследование, при котором объект может иметь только одного родителя. Но можно реализовать и множественное наследование, сделав parent списком и переопределив rget, как показано на рис. 17.2.

–  –  –

Рис. 17.2. Множественное наследование При одиночном наследовании, если мы хотим получить некоторое свойство объекта, нам достаточно рекурсивно пройтись по всем его предшественникам. Если сам объект не содержит достаточной информации об интересующем нас свойстве, мы переходим к его родителю, и т. д. При

17.2. Множественное наследование подобном поиске в случае множественного наследования наша работа несколько усложняется, потому что предшественники объекта образуют не простое дерево, а граф, и обычный поиск в глубину здесь не поможет. Множественное наследование позволяет реализовать, например, такую иерархию, как на рис. 17.3: к a мы можем спуститься от b и c, а к ним – от d. Поиск в глубину (здесь скорее в высоту) даст следующий порядок обхода: a, b, d, c, d. Если желаемое свойство имеется в d и c, мы получим значение из d, а не из c, что не будет соответствовать правилу, по которому значение из подкласса приоритетнее, чем из его родителей.

–  –  –

Рис. 17.3. Несколько путей к одному суперклассу Чтобы соблюсти это правило, нам необходимо четко следить, чтобы никакой объект не обрабатывался раньше всех его потомков. В нашем случае порядок обхода должен быть таким: a, b, c, d. Как это гарантировать? Простейший способ – собрать список из объекта и всех его предков, следующих в правильном порядке, а затем проверять по очереди каждый элемент этого списка.

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

(Удаление всех повторений, кроме последнего, соответствует правилу 3 на стр. 192.) Такое поведение закреплено за встроенной в Common Lisp функцией delete-duplicates. Поэтому если мы передадим ей результат поиска в глубину, она вернет корректный список предшествования. После того как этот список создан, rget ищет в нем первый объект с заданным свойством.

Используя идею предшествования, мы можем сказать, например, что патриотичный негодяй является прежде всего негодяем и лишь потом патриотом:1 То есть служит (serves) снача ла себе (self) и лишь затем стране (country),

–  –  –

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

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

Кроме того, это нисколько не уменьшит гибкость нашей программы;

мы просто переносим затраты с часто используемой операции на редко используемую.

На рис. 17.4. показан новый код.° Глобальная переменная *objs* является списком всех объектов. Функция parents получает предков заданного объекта; (setf parents) не только назначает новых предков, но и вызывает make-precedence для перестройки любого списка предшествования, который также мог поменяться. Списки, как и прежде, строятся с помощью precedence.

Теперь для создания объектов вместо make-hash-table пользователи могут вызывать obj, которая создает новый объект и определяет всех его предков за один шаг. Мы также переопределили rget, чтобы воспользоваться преимуществом хранимых списков предшествования.

17.4. Функциональный синтаксис

–  –  –

Рис. 17.4. Создание объектов

17.4. Функциональный синтаксис

Усовершенствовать стоит и синтаксис передачи сообщений. Использование tell не только загромождает запись, но и лишает нас возможности читать программу в обычной для Лиспа префиксной нотации:

(tell (tell obj ’find-owner) ’find-owner) Мы можем избавиться от tell, определяя имена свойств как функции.

Определим для этого макрос defprop (рис. 17.5). Необязательный аргумент meth?, будучи истинным, сигнализирует, что свойство должно считаться методом. В противном случае оно будет считаться слотом, и значение, получаемое rget, будет просто возвращаться.

Теперь, когда мы определили имя свойства, (defprop find-owner t) можно сослаться на него через вызов функции, и наш код снова станет читаться как Лисп:

(find-owner (find-owner obj)) 280 Глава 17. Пример: объекты

–  –  –

(setf (aref circle-class) #’(lambda (c) (* pi (expt (radius c) 2)))) Вызывая первый метод из cdr списка предшествования, мы можем получить внутри метода эффект встроенного оператора call-next-method.

К примеру, если мы захотим печатать что-либо во время вычисления площади круга, мы скажем:

(setf grumpy-circle (obj circle-class))

–  –  –

Рис. 17.6. Определение методов Вызов defmeth раскрывается в setf, внутри которого находится labels-выражение, задающее функцию next для получения следующего метода.

Она работает наподобие next-method-p (стр. 182), но возвращает объект, который может быть вызван, то есть служит еще и как call-next-method.°

Теперь предыдущие два метода можно определить следующим образом:

(defmeth area circle-class (c) (* pi (expt (radius c) 2))) (defmeth area grumpy-circle (c) (format t "How dare you stereotype me!~%") (funcall (next) c)) Обратите внимание, каким образом в определении defmeth используется захват символов. Тело метода вставляется в контекст, в котором локально определена функция next.

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

В большинстве объектно-ориентированных приложений граф наследования тяготеет к низу. Например, в задаче симуляции трафика типы транспортных средств представляются менее чем десятью классами, а вот объектов, представляющих отдельные автомобили, сотни. ПоскольГлава 17. Пример: объекты ку у всех них будут одинаковые списки предшествования, создавать и хранить их по отдельности – пустая трата ресурсов времени и памяти.

На рис. 17.7 представлен макрос inst, производящий экземпляры. Экземпляры подобны объектам (которые мы теперь можем называть классами), но имеют лишь одного предка и не содержат списка предшествования. Кроме того, они не включаются в список *objs*. Теперь наш предыдущий пример может быть несколько изменен:

(setf grumpy-circle (inst circle-class)) Поскольку некоторые объекты отныне не содержат списков предшествования, мы переопределили rget и get-next, чтобы они могли сразу получать доступ к единственному предку. Прирост производительности никак не сказался на гибкости. Мы можем делать с экземплярами все, что могли делать с любыми объектами, в том числе создавать их экземпляры и переназначать предков. В последнем случае (setf parents) будет эффективно преобразовывать объект в «класс».

–  –  –

Рис. 17.7. Создание экземпляров

17.7. Новая реализация Пока что ни одно из наших улучшений не сказалось отрицательно на гибкости программы. Обычно на последних этапах разработки Лисп-программа жертвует частью своей гибкости ради эффективности. И наша

17.7. Новая реализация программа не исключение. Представив все объекты в виде хеш-таблиц, мы не только получаем избыточную гибкость, но платим за это слишком высокую цену. В этом разделе мы перепишем нашу программу, чтобы представить объекты в виде простых векторов.

Да, мы отказываемся от возможности добавлять новые свойства на лету – до сих пор мы могли определить новое свойство любого объекта, просто сославшись на него. Но мы по-прежнему сможем делать это с помощью переопределения объектов. При создании класса нам потребуется передать ему список новых свойств, а при создании экземпляров они будут получать свойства через наследование.

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

В новой реализации у нас будет полноценное деление между этими двумя типами объектов, но мы больше не сможем преобразовывать экземпляры в классы.

Код на рис. 17.8–17.10 полностью представляет новую реализацию. Рисунок 17.8 содержит новые операторы для определения классов и экземпляров. Классы и экземпляры представляются в виде векторов. Первые три элемента содержат информацию, необходимую самой программе, а первые три макроса на рис.

17.8 позволяют ссылаться на нее:

1. Поле parents аналогично записи :parents в ранее использовавшихся хеш-таблицах. Для класса оно будет содержать список родительских классов, для экземпляра – один родительский класс.

2. Поле layout (размещение) будет содержать вектор с именами свойств, который определяет их размещение в векторе самого класса или экземпляра, начиная с его четвертого элемента1.

3. Поле preclist аналогично записи :preclist в ранее использовавшихся хеш-таблицах. Для класса оно будет содержать список предшествования, для экземпляра – nil.

Так как эти операторы – макросы, то они могут быть первыми аргументами setf (см. раздел 10.6).

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

(setf *print-array* nil geom-class (class nil area) circle-class (class (geom-class) radius)) #Simple-Vector T 5 C6205E Первые 3 элемента одинаковы для всех объектов. Это родители, собственно

–  –  –

Рис. 17.8. Реализация с помощью векторов: создание объектов Здесь мы созда ли два класса: geom-class не имеет суперклассов и содержит только одно свойство area; circle-class является подклассом

geom-class и имеет дополнительное свойство radius.1 Функция layout позволяет увидеть имена последних двух из пяти его полей:2

(coerce (layout circle-class) ’list) (AREA RADIUS) При отображении классов *print-array* должен быть nil. Первый элемент в списке preclist любого класса сам является классом, поэтому попытка отображения такой структуры приведет к попа данию в бесконечный цикл.

Вектор приводится к списку для просмотра его содержимого. Если *printarray* установлен в nil, содержимое вектора не отображается.

17.7. Новая реализация Макрос class – это просто интерфейс к функции class-fn, которая выполняет основную работу. Она вызывает inherit-props для сборки списка свойств всех предков нового объекта, создает вектор необходимой длины и устанавливает три первых его элемента. (preclist строится с помощью функции precedence, которую мы практически не изменили.) Остальные поля класса устанавливаются в :nil, указывая на то, что они не инициализированы. Чтобы получить свойство area класса circle-class, мы можем сказать:

(svref circle-class (+ (position ’area (layout circle-class)) 3)) :NIL Позже мы определим функции доступа, которые будут делать это автоматически.

Наконец, функция inst используется для создания экземпляров.

Она не обязана быть макросом, так как принимает лишь один аргумент:

(setf our-circle (inst circle-class)) #Simple-Vector T 5 C6464E Полезно сравнить inst и class-fn, которые выполняют похожие задачи.

Так как экземпляры имеют лишь одного родителя, то нет необходимости определять, какие свойства наследуются. Экземпляр может просто скопировать размещение родительского класса. Кроме того, нет необходимости строить список предшествования, поскольку у экземпляра его попросту нет. Таким образом, создание экземпляров намного быстрее создания классов. Но так и должно быть, ведь, как правило, новые экземпляры создаются намного чаще, чем новые классы.

Теперь, чтобы построить иерархию классов и экземпляров, нам потребуются функции чтения и записи свойств. Первой функцией на рис. 17.9 является новая версия rget. По форме она напоминает rget с рис. 17.7.

Она имеет две ветки – для классов и экземпляров соответственно.

1. Если объект является классом, мы обходим его список предшествования до тех пор, пока не найдем объект, имеющий значение искомого свойства, не равное :nil. Если такой объект не найден, возвращаем :nil.

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

У rget появился новый третий аргумент – next?, предназначение которого будет объяснено позже. Сейчас достаточно сказать, что если он nil, то rget ведет себя как обычно.

Функция lookup и обратная ей играют роль gethash в старой версии rget.

Они ищут в объекте свойство с заданным именем или устанавливают новое.

Этот вызов функции эквивалентен предыдущей версии с svref:

(lookup ’area circle-class) :NIL 286 Глава 17. Пример: объекты

–  –  –

Рис. 17.9. Реализация с помощью векторов: доступ

Поскольку setf для lookup также определено, мы можем определить метод area для circle-class:

(setf (lookup ’area circle-class) #’(lambda (c) (* pi (expt (rget ’radius c nil) 2)))) В этой программе, как и в ее предыдущей версии, нет четкого разделения между классами и экземплярами, а «метод» – это просто функция в поле объекта. Но вскоре это будет скрыто за более удобным фасадом.

Рисунок 17.10 содержит оставшуюся часть нашей новой реализации.1 Этот код не добавляет программе никаких новых возможностей, но делает ее более простой в использовании. Макрос defprop, по сути, остался тем же, просто теперь он вызывает lookup вместо gethash.

Как и раньше, он позволяет ссылаться на свойства в функциональном стиле:

(defprop radius) (SETF RADIUS) (radius our-circle) :NIL Данный листинг содержит исправление авторской опечатки, которая была обнаружена Тимом Мензисом (Tim Menzies) и опубликована в новостной группе comp.lang.lisp (19.12.2010). Эта опечатка не внесена автором в официальный список опечаток книги. – Прим. перев.

17.7. Новая реализация (setf (radius our-circle) 2) Если необязательный второй аргумент макроса defprop истинен, его вызов раскрывается в run-methods, который сохранился практически без изменений.

Наконец, функция defmeth предоставляет удобный способ определения методов. В этой версии есть три новых момента: она неявно вызывает defprop, использует lookup вместо gethash и вызывает rget вместо get-next (стр. 282) для получения следующего метода. Теперь мы видим причину добавления необязательного аргумента в rget: эта функция так похожа на get-next, что мы можем объединить их в одну за счет добавления дополнительного аргумента. Если этот аргумент истинен, rget выполняет роль get-next.

<

–  –  –

Благодаря неявному вызову defprop внутри defmeth мы можем аналогичным образом вызвать area, чтобы найти площадь our-circle:

(area our-circle) 12.566370614359173

17.8. Анализ Теперь у нас есть встроенный язык, приспособленный для написания реальных объектно-ориентированных приложений. Он простой, но для своего размера достаточно мощный. Кроме того, он будет достаточно быстрым для типичных приложений, в которых операции с экземплярами обычно выполняются намного чаще, чем с классами. Основной задачей усовершенствования кода было именно повышение производительности при работе с экземплярами.

В нашей программе создание новых классов происходит медленно и производит большое количество мусора. Но если классы не создаются в те моменты, когда критична скорость, это вполне приемлемо. Что действительно должно происходить быстро, так это доступ и создание экземпляров. В плане скорости доступа к экземплярам наша программа достигла предела, и дальнейшие усовершенствования могут быть связаны с оптимизацией при компиляции.° То же самое касается и создания экземпляров. И никакие операции с экземплярами не требуют выделения памяти, за исключением, разумеется, создания вектора, представляющего сам экземпляр. Сейчас такие векторы размещаются в памяти динамически, что вполне естественно, но при желании можно избежать динамического выделения памяти, применив стратегию, описанную в разделе 13.4.

Наш встроенный язык является характерным примером программирования на Лиспе. Уже тот факт, что он встроенный, говорит об этом. Но показательно и то, как Лисп позволил нам развивать программу от небольшой ограниченной версии к мощной, но неэффективной, а затем к эффективной, но слегка ограниченной.

Репутация Лиспа как медленного языка происходит не из его природы (еще с 1980-х годов компиляторы Лиспа способны генерировать не менее быстрый код, чем компиляторы С), а из того, что многие программисты останавливаются на втором этапе развития программы.

Как писал Ричард Гэбриел:

«В Лиспе очень легко написать программу с плохой производительностью; в С это практически невозможно».°

Да, это так, но это высказывание может пониматься как за, так и против Лиспа:

17.8. Анализ

1. Приобретая гибкость ценой скорости, вы облегчаете процесс написания программ в Лиспе; в С вы не имеете такой возможности.

2. Если не оптимизировать ваш Лисп-код, очень легко получить медленную программу.

Какая из интерпретаций описывает вашу программу, зависит всецело от вас. Но в Лиспе у вас как минимум есть возможность пожертвовать скоростью выполнения ради экономии вашего времени на ранних этапах создания программы. Для чего наш пример точно не подходит, так это для демонстрации модели работы CLOS (за исключением, пожалуй, прояснения механизма работы call-next-method). Да и как можно говорить о сходстве слонопотамного CLOS и нашего 70-строчного комарика.

Действительно, различия между этими двумя программами более показательны, чем сходства. Во-первых, мы увидели, насколько широким понятием может быть объектная ориентированность. Наша программа будет помощнее, чем некоторые другие реализации объектно-ориентированного программирования, но тем не менее она обладает лишь частью мощи CLOS.

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

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

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

А теперь более интересный вопрос: на что еще он способен?

A Отладка Приложение A.

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

Циклы прерывания Если вы просите Лисп сделать то, чего он не может, вычисление будет прервано сообщением об ошибке, и вы попадете в то, что называется циклом прерывания (break loop). Поведение этого цикла зависит от используемой реализации, но во всех случаях, как правило, отображаются следующие вещи: сообщение об ошибке, список опций и специальное приглашение.

Внутри цикла прерывания вы по-прежнему можете вычислять выражения так же, как и в toplevel. Находясь внутри этого цикла, вы можете выяснить причину ошибки и даже исправить ее на лету, после чего программа продолжит выполнение. Тем не менее наиболее частое действие, которое вы захотите произвести внутри цикла прерывания, – это выбраться из него. В большинстве ошибок, как правило, виноваты опечатки или мелкие оплошности, так что обычно вы просто прервете выполнение и вернетесь в toplevel.

В гипотетической реализации для этого нужно набрать :abort:

(/ 1 0) Error: Division by zero.

Options: :abort, :backtrace :abort Что вы будете вводить в своей реализации, зависит от нее.

Отладка Если вы находитесь в цикле прерывания и происходит еще одна ошибка, то вы попадаете в еще один цикл прерывания.1 Большинство реализаций Лиспа показывает уровень цикла, на котором вы находитесь, с помощью нескольких приглашений или числа перед приглашением:

(/ 2 0) Error: Division by zero.

Options: :abort, :backtrace, :previous Теперь глубина вложенности отладчиков равна двум, и мы можем вернуться в предыдущий отладчик или же сразу попасть в toplevel.

–  –  –

2 Exit TREE1+ (6. 8) 1 Exit TREE1+ ((2. 4) 6. 8) ((2. 4) 6. 8) Для отключения трассировки foo введите (untrace foo); для отключения трассировки всех функций введите (untrace).

Более гибкой альтернативой трассировки является добавление в код диагностической печати. Пожалуй, этот метод, ставший классическим, применяется в десять раз чаще, чем изощренные отладочные утилиты.

Это еще одна причина, по которой полезно интерактивное переопределение функций.

Обратная трасса (backtrace) – это список всех вызовов, находящихся на стеке, который создается из цикла прерывания после того, как произошла ошибка. Если при трассировке мы как бы говорим: «Покажи, что ты делаешь», то при обратной трассировке мы задаем вопрос: «Как мы сюда попали?». Эти две операции дополняют друг друга. Трассировка покажет каждый вызов заданных функций во всем дереве вызовов, а обратная трассировка – вызовы всех функций в выбранной части кода (на пути от toplevel к месту возникновения ошибки).

В типичной реализации мы получим обратную трассу, введя :backtrace в отладчике:

(tree1+ ‘((1. 3) 5. A)) Error: A is not a valid argument to 1+.

Options: :abort, :backtrace :backtrace (1+ A) (TREE1+ A) (TREE1+ (5. A)) (TREE1+ ((1. 3) 5. A)) С помощью обратной трассировки поймать ошибку иногда довольно легко. Для этого достаточно посмотреть на цепочку вызовов. Еще одним преимуществом функционального программирования (раздел 2.12) является то, что все баги проявятся при обратной трассировке. В полностью функциональном коде все, что могло повлиять на возникновение ошибки, при ее появлении находится на стеке вызовов функции.

Количество информации, содержащееся в обратной трассе, зависит от используемой реализации. Одна реализация может выводить полную историю всех незавершенных вызовов с их аргументами, а другая может не выводить практически ничего. Имейте в виду, что обычно трассировка (и обратная трассировка) более информативна для интерпретируемого кода, нежели для скомпилированного. Это еще одна причина отложить компиляцию вашей программы до тех пор, пока вы не будете полностью уверены, что она работает. Исторически отладку вели в режиме интерпретации и лишь затем компилировали отлаженную версию. Однако взгляды на этот вопрос постепенно меняются: по меньшей мере две реализации Common Lisp вовсе не содержат интерпретатор.

Отладка Когда ничего не происходит Не все баги приводят к прерыванию вычислений. Даже более неприятной является ситуация, когда Лисп полностью игнорирует все ваши действия. Обычно это означает, что вы попали в бесконечный цикл. Если это происходит в процессе итерации, то Лисп со счастливой улыбкой будет выполнять ее бесконечно.

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

(defun blow-stack () (1+ (blow-stack))) BLOW-STACK (blow-stack) Error: Stack overflow.

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

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

При создании рекурсивных функций и словесном описании рекурсивного алгоритма часто забывают базовый случай. Например, мы можем сказать, что obj принадлежит списку lst, если он является его первым элементом либо принадлежит к остатку lst. Строго говоря, это не так.

Мы должны добавить еще одно условие: obj не принадлежит lst, если lst пуст. В противном случае наше описание будет соответствовать бесконечной рекурсии.

В Common Lisp car и cdr возвращают nil, если их аргументом является

nil:

(car nil) NIL (cdr nil) NIL Поэтому если мы пропустим базовое условие в определении member, (defun our-member (obj lst) ; wrong (if (eql (car lst) obj) lst (our-member obj (cdr lst)))) то получим бесконечную рекурсию, если искомый объект будет отсутствовать в списке. Когда мы достигнем конца списка, так и не найдя элемент, рекурсивный вызов будет иметь следующий вид:

(our-member obj nil) 294 Приложение A В корректном определении (стр. 33) базовое условие приведет к остановке рекурсии, возвращая nil. В нашем ошибочном случае функция будет покорно искать car и cdr от nil, которые также равны nil, поэтому процесс будет повторяться снова и снова.

Если причина бесконечного процесса неочевидна, как в нашем случае, вам поможет трассировка. Бесконечные циклы бывают двух видов. Вам повезло, если источником бесконечного повторения является структура программы. Например, в случае our-member трассировка тут же покажет, где проблема.

Более сложным случаем являются бесконечные циклы, причина которых – некорректно сформированные структуры данных. Например, попытка обхода циклического списка (стр. 215) приводит к бесконечному циклу. Подобные проблемы трудно обнаружить, так как они проявляют себя не сразу и возникают уже в коде, который не является их непосредственной причиной. Правильным решением является предупреждение подобных проблем (стр. 205): избегайте деструктивных операторов до тех пор, пока не убедитесь в корректности работы программы.

Если Лисп игнорирует ваши действия, причиной этого может быть ожидание ввода. Во многих системах нажатие Enter не приводит к каким-либо эффектам, если ввод выражения не завершен. Преимущество такого подхода заключается в том, что это дает возможность введения многострочных выражений.

Но есть и недостаток: если вы забудете ввести закрывающую скобку или кавычку, Лисп будет ожидать завершения ввода выражения, в то время как вы будете думать, что ввели его полностью:

(format t "for example ~A~% ’this) Здесь мы пропустили закрывающую кавычку в конце строки форматирования. Нажатие на Enter не приведет к чему-либо, так как Лисп думает, что мы продолжаем набирать строку.

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

Переменные без значения/ несвязанные переменные Частой причиной жалоб со стороны Лиспа являются символы без значения или же несвязанные символы. Они могут вызвать несколько различных проблем.

Локальные переменные, подобные устанавливаемым в let или defun, действительны только внутри тела выражения, в котором они были созОтладка даны.

Попытка сослаться на такие переменные откуда-либо извне приведет к ошибке:

(progn (let ((x 10)) (format t "Here x = ~A.~%" x)) (format t "But now it’s gone...~%") x) Here x = 10.

But now it’s gone...

Error: X has no value.

Когда Лисп жалуется подобным образом, это значит, что вы случайно сослались на переменную, которая не существует. Поскольку в текущем окружении не существует локальной переменной x, Лисп думает, что мы ссылаемся на глобальную переменную или константу с тем же именем. Когда он не находит никакого значения, возникает ошибка.

К такому же результату приведут опечатки в именах переменных.

Похожая проблема возникает, если мы пытаемся сослаться на функцию как на переменную:

defun foo (x) (+ x 1)) Error: DEFUN has no value.

Поначалу это может озадачить: как это defun не имеет значения? Просто мы забыли открывающую скобку, и поэтому Лисп воспринимает символ defun (а это все, что он пока что считал) как глобальную переменную.

Иногда программисты забывают инициализировать глобальные переменные. Если вы не передаете второй аргумент defvar, глобальная переменная будет определена, но не инициализирована, и это может быть корнем проблемы.

–  –  –

Кроме того, мы имеем функцию для вычисления количества недель в месяце:

(defun month-weeks (mon) (/ (month-length mon) 7.0))

В таком случае при вызове month-weeks может произойти следующее:

(month-weeks ’oct) Error: NIL is not a valid argument to /.

Ни одно из заданных условий в case-выражении не было выполнено, и case вернул nil. Затем month-weeks, которая ожидает число, передает это значение функции /, но та получает nil, что и приводит к ошибке.

В нашем примере источник и место проявления бага находятся рядом.

Чем дальше они друг от друга, тем сложнее найти подобные баги. Для предотвращения подобных ситуаций в некоторых диалектах Лиспа прохождение cond и case без выполнения одного из вариантов вызывает ошибку. В Common Lisp в этой ситуации следует использовать ecase (см.

раздел 14.6).

Переименование Особенно зловредный баг появляется при переименовании функции или переменной в некоторых, но не во всех местах использования.

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

(defun depth (x) (if (atom x) (1+ (apply #’max (mapcar #’depth x)))))

При первом же тестировании мы обнаружим, что она дает значение, завышенное на 1:

(depth ’((a))) Исходное значение должно быть равно 0, а не 1. Исправим этот недочет, а заодно дадим функции более конкретное имя:

(defun nesting-depth (x) (if (atom x) (1+ (apply #’max (mapcar #’depth x)))))

Теперь снова протестируем:

(nesting-depth ’((a))) Мы получили тот же результат. В чем же дело? Да, ошибку мы исправили, но этот результат получается не из исправленного кода. ПриглядиОтладка тесь внимательно, ведь мы забыли поменять имя в рекурсивном вызове, и наша новая функция по-прежнему вызывает некорректную функцию depth.

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

Например, функция read-from-string имеет следующий список аргументов:

(read-from-string string &optional eof-error eof-value &key start end preserve-whitespace) Чтобы передать такой функции аргументы по ключу, нужно сначала передать ей все необязательные аргументы. Если мы забудем об этом, как в данном примере, (read-from-string "abcd" :start 2) ABCD то :start и 2 будут расценены как необязательные аргументы. Корректный вызов будет выглядеть следующим образом:

(read-from-string "abcd" nil nil :start 2) CD Некорректные декларации В главе 13 объяснялось, как определять декларации переменных и структур данных. Декларируя что-либо, мы даем обещание в дальнейшем следовать этой декларации, и компилятор полностью полагается на это допущение. Например, оба аргумента следующей функции обозначены как double-float, (defun df* (a b) (declare (double-float a b)) (* a b)) и поэтому компилятор сгенерировал код, предназначенный для умножения только чисел double-float.

Если df* вызывается с аргументами, не соответствующими задекларированному типу, то это вызовет ошибку или вовсе вернет мусор.

А в одной из реализаций при передаче в эту функцию двух фиксированных целых происходит аппаратное прерывание:

298 Приложение A (df* 2 3) Error: Interrupt.

Если у вас возникает подобная серьезная ошибка, с большой вероятностью ее причиной является неверная декларация типа.

–  –  –

Это приложение содержит определения 58 наиболее используемых операторов Common Lisp. Так как большая часть Лиспа написана (или может быть написана) на нем самом и при этом Лисп-программы невелики (или могут быть такими), это удобный способ объяснения самого языка.

Кроме того, данное упражнение демонстрирует, что концептуально Common Lisp не такой уж и большой язык, как может показаться. Большинство операторов Common Lisp являются, по сути, библиотечными функциями. Набор операторов, необходимых для определения остальных, довольно мал.

Для определения тех операторов, которые мы рассмотрим в этой главе, достаточно наличия лишь следующих операторов:

apply aref backquote block car cdr ceiling char= cons defmacro documentation eq error expt fdefinition function floor gensym get-setf-expansion if imagpart labels length multiple-value-bind nth-value quote realpart symbol-function tagbody type-of typep = + - / Код, представленный здесь, написан таким образом, чтобы объяснять Common Lisp, но не реа лизовывать его. В полноценных реализациях эти операторы могут быть более производительными и лучше проводить проверку на наличие ошибок. Операторы определены в алфавитном порядке для упрощения их поиска. Если вы действительно хотите использовать эту реализацию Лиспа, определения макросов должны находиться перед любым кодом, который их использует.

(defun -abs (n) (if (typep n ’complex) (sqrt (+ (expt (realpart n) 2) (expt (imagpart n) 2))) (if ( n 0) (- n) n)))

–  –  –

(defun -list (&rest elts) (copy-list elts)) (defun -listp (x) (or (consp x) (null x))) (defun -mapcan (fn &rest lsts) (apply #’nconc (apply #’mapcar fn lsts)))

–  –  –

(defun -pairlis (keys vals &optional alist) (unless (= (length keys) (length vals)) (error "mismatched lengths")) (nconc (mapcar #’cons keys vals) alist))

–  –  –

ANSI Common Lisp существенно отличается от Common Lisp, описанного в 1984 году в первом издании «Common Lisp: the Language» Гая Стила. Он также отличается (хотя и в меньшей степени) от описания языка во втором издании 1990 года. Это приложение описывает наиболее существенные различия. Изменения, внесенные с 1990 года, перечислены отдельно в последнем разделе.

Основные дополнения

1. Объектная система Common Lisp (CLOS) ста ла частью языка.

2. Макрос loop теперь реализует встроенный язык с инфиксным синтаксисом.

3. Common Lisp теперь включает набор новых операторов, которые в общем называются системой особых условий и предназначены для сигнализации и обработки ошибок и других условий.

4. Common Lisp теперь предоставляет специальную поддержку и управление процессом красивой печати (pretty printing).

–  –  –

Функции

1. Идея имени функции была обобщена и теперь включает выражения вида (setf f). Подобные выражения теперь принимаются любыми операторами или декларациями, которые ожидают имя функции.

Новая функция fdefinition действует подобно symbol-function, но принимает имя функции в новом более общем смысле.

2. Тип function больше не включает fboundp-символы и лямбда-выражения. Символы (но не лямбда-выражения) по-прежнему могут использоваться там, где ожидается функциональный объект. Лямбдавыражения могут быть преобразованы в функции с помощью coerce.

3. Символы, используемые как имена аргументов по ключу, больше не обязаны быть ключевыми словами. (Обратите внимание, что символы не из пакета keyword при таком использовании должны выделяться кавычками.)

4. Для остаточных аргументов (&rest) не гарантируется новое выделение памяти, поэтому изменять их деструктивно небезопасно.

5. Локальные функции, определенные через flet или labels, а также результаты раскрытия defmacro, macrolet или defsetf неявно заключены в блок block, имя которого соответствует имени определяемого объекта.

6. Функция, имеющая интерпретируемое определение в ненулевом лексическом окружении (то есть определенная в toplevel через defun внутри let) не может быть скомпилирована.

Макросы

1. Были введены макросы компиляции и символы-макросы, а также соответствующие операторы.

2. Теперь раскрытие макроса определяется в том окружении, где был совершен вызов defmacro. По этой причине в ANSI Common Lisp код раскрытия макроса может ссылаться на локальные переменные:

(let ((op ’car)) (defmacro pseudocar (lst) ‘(,op,lst))) В 1984 году раскрытие макроса определялось в нулевом окружении (то есть в toplevel).

Изменения в Common Lisp

3. Гарантируется, что макровызовы не будут перераскрываться в скомпилированном коде.

4. Макровызовы теперь могут быть точечными списками.

5. Макросы теперь не могут раскрываться как declare.

Вычисление и компиляция

1. Переопределен специальный оператор eval-when, все его оригинальные ключи объявлены нежелательными.

2. Функция compile-file теперь принимает аргументы :print и :verbose.

Их значения по умолчанию хранятся в новых глобальных переменных *compile-print* и *compile-verbose*.

3. Новые переменные *compile-file-pathname* и *compile-file-truename* связываются на время вызова compile-file, как и *load-pathname* и *load-truename* в процессе load.

4. Добавлена декларация dynamic-extent.

5. Добавлен параметр компиляции debug.

6. Удален специальный оператор compiler-let.

7. Удален макрос чтения #,.

8. Удалена глобальная переменная *break-on-warnings*; на замену ей введена более общая *break-on-signals*.

Побочные эффекты

1. Метод setf теперь может выполнять несколько присваиваний.

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

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

–  –  –

2. Модификация строки, используемой как имя символа, теперь считается ошибкой.

3. Функция documentation стала обобщенной функцией.

Списки

1. Функции assoc-if, assoc-if-not, rassoc-if, rassoc-if-not и reduce теперь принимают аргумент :key.

2. Функция last теперь имеет второй необязательный параметр, задающий длину возвращаемого хвоста.

3. С добавлением complement использование функций -if-not и аргумента по ключу :test-not признано нежелательным.

Массивы

1. Добавлены новые функции, позволяющие программам запрашивать информацию об обновлении типов (type-upgrading) элементов массивов и комплексных чисел.

2. Индексы массивов теперь определены как fixnum.

Строки и знаки

1. Удален тип string-char. Тип string больше не идентичен типу (vector string-char). Тип character разделен на два новых подтипа: base-char и extended-char. Тип string получил новый подтип base-string, который, в свою очередь, имеет новый подтип simple-base-string.

2. Некоторые функции для создания строк теперь могут принимать аргумент :element-type.

3. Упразднены атрибуты знаков font и bits, а также все связанные с ними функции и константы. Единственным атрибутом знака, определенным в Common Lisp, теперь является code.

4. Большинство строковых функций могут преобразовывать аргументы одинаковых типов в строки. Так, (string= ’x ’x) теперь вернет t.

Структуры

1. Отныне не обязательно задавать какие-либо слоты в теле вызова defstruct.

2. Последствия переопределения структуры, то есть двукратного вызова defstruct с одним именем, не определены.

Изменения в Common Lisp Хеш-таблицы

1. Функция equalp теперь может использоваться в хеш-таблицах.

2. Добавлены новые функции доступа, позволяющие программам обращаться к свойствам хеш-таблиц: hash-table-rehash-size, hash-tablerehash-threshold, hash-table-size и hash-table-test.

Ввод-вывод

1. Введена концепция логических путей, а также соответствующие операторы.

2. Введены несколько новых типов потоков, а также соответствующие предикаты и функции доступа.

3. Введены директивы форматирования ~_, ~W и ~I. Директивы ~D, ~B, ~O, ~X и ~R теперь принимают дополнительный аргумент.

4. Функции write и write-to-string принимают пять новых аргументов по ключу.

5. Для ввода путей добавлен новый макрос чтения #P.

6. Новая переменная *print-readably* может использоваться для принудительного вывода в читаемом виде.

Числа



Pages:     | 1 | 2 || 4 |

Похожие работы:

«Согласовано Утверждаю Начальник Директор ОО Адмиралтейского района Санкт-Петербурга ГБОУ гимназии № 278 имени Б.Б. Голицына _С.И. Петрова Адмиралтейского района Санкт-Петербурга "_" мая 2016 г. _В.М. Шутова Согласовано "_" мая 2016 г. Глава внутригородско...»

«ISSN 0536 – 1036. ИВУЗ. "Лесной журнал". 2015. № 1 УДК 630*231.1 КОЛИЧЕСТВЕННЫЕ И КАЧЕСТВЕННЫЕ ПАРАМЕТРЫ ВОЗОБНОВЛЕНИЯ ПОД ПОЛОГОМ ДРЕВОСТОЕВ, СФОРМИРОВАВШИХСЯ ИЗ ПРЕДВАРИТЕЛЬНЫХ ГЕНЕРАЦИЙ...»

«СИНТАКСИС ПУБЛИЦИСТИКА КРИТИКА ПОЛЕМИКА ПАРИЖ Журнал редактируют : M. РОЗАНОВА А. СИНЯВСКИЙ The League of Supporters : Ю. Вишневская, И. Голомшток, А. Есенин -Вольпин, Ю. Меклер, М. Окутюрье, А. Пятигорский, Е. Э...»

«Підводна техніка і технологія Всеукраїнська науково-технічна конференція з міжнародною участю УДК 629.585: 623.983 Современное состояние обитаемой привязной подводной техники Авторы: В.С. Блинцов, д.т.н., проф.; А.В. Блинцов, к.т.н., доц.; А.Н. Войтасик, Нац...»

«Цифровой шумомер MASTECH MS6701 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ І. Вступление Благодарим Вас за решение воспользоваться нашим изделием. Пожалуйста, внимательно ознакомьтесь со следующей информацией перед тем, как начать измерения. Шумомер предназначен для измерения уровня зв...»

«1. Цели освоения дисциплины. Целью освоения дисциплины "Научно-исследовательская работа в семестре" является формирование у магистрантов способностей к самостоятельной научно-исследовательской работе, выработки практических навыков проведения собственных научных исследовани...»

«©Т.В. Гавриленко, сайт http://www.road-project.okis.ru 2016-03-18 7.1 ПРОЕКТИРОВАНИЕ ВИРАЖА 7.1.1 Общие положения Материал излагается по учебному пособию [1]. Для уменьшения центробежной силы, возникающей при движении автомобиля по кривой, необходимо сместить центр тяжести автомобиля в сторону д...»

«ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Для составления рабочей программы были использованы следующие нормативные документы: 1. Закон "Об образовании Российской Федерации" № 273-ФЗ от 29.12.2012г;2. Приказ Министерства образования и науки Российской Федерации "Об утверждении и введении в действие ФГОС ООО"...»

«: (4012)72-03-81 (4812)29-41-54 (8182)63-90-72 (831)429-08-12 (4842)92-23-67 (862)225-72-31 +7(7172)727-132 (3843)20-46-81 (3842)65-04-62 (8652)20-65-13 (4722)40-23-64 (383)227-86-73 (8332)68-02...»

«К.т.н. Малиновский В.С.; Власова И.Б.(ООО "НТФ "ЭКТА"). Решена ли сегодня задача эффективного переплава лома в качественную сталь 1. Введение. В настоящее время задача переработки металлолома в массовом порядке с целью производства качественной стали,...»

«УПРАВЛЕНИЕ ПО ТАРИФНОМУ РЕГУЛИРОВАНИЮ Мурманской области ПРОТОКОЛ ЗАСЕДАНИЯ КОЛЛЕГИИ г. Мурманск 26.03.2014 УТВЕРЖДАЮ Начальник Управления по тарифному регулированию Мурманской области _ В.А. Губинский "26" марта 2014 г.Председатель заседания:...»

«ЛИСТ БЕЗОПАСНОСТИ PC010 1. ИНДИФИКАЦИЯ ПРОДУКТА / РАЗРАБОТАННО КОМПАНИЕЙ. Название по артикулу: Порошковое покрытие Код по артикулу: Продукта группы PC010 Коммерческий отдел: Порошковые покрытия Ад...»

«Предложения о внесении изменений в Генеральный план и Правила землепользования и застройки Петрозаводского городского округа, разработанные МРОО "СПОК" Пояснительная записка к предложениям МРОО "СПОК" о внесении изменений в Генеральный план...»

«Автоматизация логистики 1С-WMS/1С-TMS Комплексная автоматизация логистики Кондрашев Сергей AXELOT 1C:WMS Автоматизация логистики 1С-WMS/1С-TMS Как развивалась 1С:WMS 2004 – 1-ая редакция системы 2005 – 2-ая редакция системы 2008 – 3-ая редакция сис...»

«Андрей Пархоменко (идея Алексея Пархоменко) ТРИ ПОРОСЁНКА (ТРАГИФАРС) * * * Действующие лица: Наф-Наф – самый умный и расчётливый из трёх братьев-поросят. Умеет "загребать жар" чужими рукаими. Ниф-Ниф – средний брат-поросёнок, предпочитающий жить одним днём. Н...»

«Информация о ходе выполнения плана мероприятий по выполнению указов Президента Российской Федерации от 07 мая 2012 года за 9 месяцев 2016 года (постановление администрации Магаданской области № 87-п от 21.08.20...»

«РЕДАКЦИОННЫЙ СОВЕТ: Н. Ангерман, д. н., проф. (Гамбургский университет, Германия) Д. Бэкман, д. н. (Хельсинкский университет, Финляндия) С. Г. Веригин, к. и. н., доцент (декан Петрозаводского государственного университета) Н. А. Копанев, к. и. н. (зав. Центром изучения эпохи Просвещения "Библиотека Вольтера" РНБ) Н. Кент, д....»

«А. Шубин Конституционное совещание 1993 г.: впечатления участника Решение о принятии новой российской конституции было принято еще 16 июня 1990 г. I съездом народных депутатов РСФСР. Тогда была создана Конституционная комиссия съезда во главе со спикером Б. Ельциным и секретарем О. Румянцевым. Реальной работой по сбору предложений...»

«0603481 МЭИ К маммограф электроимпедансныи компьютерный • ПРИМЕНЕНИЕ Онкология, маммология, акушерство, гинекология • ПАТЕНТЫ НА ИЗОБРЕТЕНИЕ Электроимпедансный маммограф "МЭИК" защищен патентами РФ на изобретение №2153285 и №2127075, а также патентами США № 6,167,300 и № 6, 2 3...»

«HEINE mini 3000 HEINE Optotechnik GmbH & Co. KG Kientalstr. 7 · 82211 Herrsching · Germany Tel. +49 (0) 81 52 / 38 0 Fax +49 (0) 81 52 / 38 2 02 E-Mail: info@heine.com · www.heine.com med 1012 1/8.12 HEINE mini 3000® Основные условия гарантии Вместо определенного законодательством гарантийного срока в 2 года, HEINE предостав...»

«АКАДЕМИЯ НАУК СССР ЛИТЕРАТУРНЫЕ ПАМЯТНИКИ JEAN RACINE TRAGEDIES ЖЯ о Ж А Н РАСИН ТРАГЕДИИ: ИЗДАНИЕ ПОДГОТОВИЛИ Н.А.ЖИРМУНСКАЯ, Ю. Б. КОРНЕЕВ ИЗДАТЕЛЬСТВО "НАУКА" Ленинградское отделение ЛЕНИНГРАД. 1977...»

«ШКОЛА УСПЕШНОГО ТРЕЙДЕРА. КУРС ЛЕКЦИЙ 3 КУРС 3 КУРС – УМЕЛЫЙ ТРЕЙДЕР ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 7. ТЕОРИЯ ХАОСА – НОВОЕ ИЗМЕРЕНИЕ В ТОРГОВЛЕ 8. ТЕОРИЯ И ПРАКТИКА МЕТОДА PROFITUNITY БИЛЛА ВИЛЬЯМСА. 10 8.1. Уровень первый: трейдер-новичок ДОЛГОСРОЧНОЕ ДВИЖЕНИЕ Тренды ИНДЕКС ОБЛЕГЧЕНИЯ РЫНКА (MFI) ОКНА PROFITUNITY Тиковый Объем / MFI Зеленый ( + Тиковый О...»

«ВОЛОГОДСКІ Я ЕПАРХІАЛЬНЫЯ ВДОМОСТИ. (Годъ т р и д ц а т ь первый). ЦНА годовому изданію ТРИ рубля съ пересылкою и безъ пересылки. Выходятъ 1 и 15 чиселъ каждаго мсяца. За напечатаніе объявленій за каждую строчку или мсто строчки...»

«МАРКЕТИНГ ВЗАИМОДЕЙСТВИЯ: АДАПТАЦИОННЫЕ РЕ. http://www.economy.nayka.com.ua/?op=1&z=2874 Електронне наукове фахове видання Ефективна економіка включено до переліку наукових фахових видань України з питань еко...»

«УТВЕРЖДЕНО Решением годового Общего собрания акционеров ОАО "Красногорская электрическая сеть" протокол № 18 от " 13 " мая 2015 года Предварительно УТВЕРЖДЕНО Решением Совета директоров ОАО "Красногорская электрическая сеть" протокол №_[_ от " 13...»










 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.