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

Pages:     | 1 || 3 | 4 |

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

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

Проведем несложную проверку, сложив все эти числа:

(apply #’+ mon) Теперь перевернем этот список и применим с помощью maplist функцию + к последовательности хвостов (cdr) списка. Мы получим количества дней, прошедшие до начала каждого последующего месяца:

(setf nom (reverse mon)) (31 30 31 30 31 31 30 31 30 31 28 31) (setf sums (maplist #’(lambda (x) (apply #’+ x)) nom)) (365 334 304 273 243 212 181 151 90 59 31) (reverse sums) (31 59 90 120 151 181 212 243 273 304 334 365) Эти цифры означают, что до начала февраля пройдет 31 день, до начала марта 59 и т. д.

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

Жизненный цикл обычной Лисп-программы состоит из четырех этапов:

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

Вы можете взаимодействовать с Лиспом не только во время работы программы, но также во время компиляции (раздел 10.2) и даже ее чтения

5.7. Пример: арифметика над датами (раздел 14.3). То, каким образом мы создали вектор month, свидетельствует о том, что мы используем Лисп даже во время написания программы.

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

–  –  –

Рис. 5.1. Операции с датами: преобразование дат в целые числа Если вы вздумаете использовать этот код для управления машиной времени, то люди могут не согласиться с вами по поводу текущей даты, если вы попадете в прошлое. По мере накопления информации о продолжительности года люди вносили изменения в календарь. В англоговорящих странах подобная нестыковка последний раз устранялась в 1752 году, когда сразу после 2 сентября последовало 14 сентября.° Количество дней в году зависит от того, является ли он високосным.

Год не является високосным, если он не кратен 4 либо кратен 100 и не кратен 400. 1904 год был високосным, 1900 не был, а 1600 был.

Для определения делимости существует функция mod, возвращающая остаток от деления первого аргумента на второй:

(mod 23 5) 108 Глава 5. Управление (mod 25 5) Одно число считается делимым на другое, если остаток от деления на него равен нулю. Функция leap? использует этот подход для определения високосности года:

(mapcar #’leap? ’(1904 1900 1600)) (T NIL T) Дату в целое число преобразует функция date-num. Она возвращает сумму численных представлений каждого компонента даты. Чтобы выяснить, сколько дней прошло до начала заданного месяца, она использует функцию month-num, которая обращается к соответствующему компоненту вектора month, добавляя к нему 1, если год високосный и заданный месяц находится после февраля.

Чтобы найти количество дней до наступления заданного года, date-num вызывает year-num, которая возвращает численное представление 1 января этого года. Эта функция отсчитывает годы до нулевого года (то есть 2000).

На рис. 5.2 показан код второй части программы. Функция num-date преобразует целые числа обратно в даты. Вызывая num-year, она получает год и количество дней в остатке, по которому num-month вычисляет месяц и день.

Как и year-num, num-year ведет отсчет от 2000 года, складывая продолжительности каждого года до тех пор, пока эта сумма не превысит заданное число n (или не будет равна ему). Если сумма, полученная на какой-то итерации, превысит его, то num-year возвращает год, полученный на предыдущей итерации. Для этого введена переменная prev, которая хранит число дней, полученное на предыдущей итерации.





Функция num-month и ее подпроцедура nmon ведут себя обратно month-num.

Они вычисляют позицию в векторе month по численному значению, тогда как month-num вычисляет значение исходя из заданного элемента вектора.

Первые две функции на рис. 5.2 могут быть объединены в одну. Вместо вызова отдельной функции num-year могла бы вызывать непосредственно num-month. Однако на этапе тестирования и отладки текущий вариант более удобен, и объединение функций может стать следующим шагом после тестирования.

Функции date-num и num-date упрощают арифметику дат.° С их помощью работает функция date+, позволяющая складывать и вычитать дни из заданной даты.

Теперь мы сможем вычислить дату по прошествии 60 дней с 17 декабря 1997 года:

(multiple-value-list (date+ 17 12 1997 60)) (15 2 1998) Мы получили 15 февраля 1998 года.

Итоги главы

–  –  –

Рис. 5.2. Операции с датами: преобразование целых чисел в даты Итоги главы

1. В Common Lisp есть три основных конструкции для блоков: progn, block с возможностью немедленного выхода (return) и tagbody, внутри которой работает goto. Многие встроенные операторы используют неявные блоки.

2. Создание нового лексического контекста эквивалентно вызову функции.

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

4. В Common Lisp есть также разнообразные итерационные операторы.

5. Выражения могут возвращать несколько значений.

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

110 Глава 5. Управление

–  –  –

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

6.1. Глобальные функции

Предикат fboundp сообщает, существует ли функция с именем, заданным в виде символа. Если какой-либо символ является именем функции, то ее можно получить с помощью symbol-function:

(fboundp ’+) T (symbol-function ’+) #Compiled-Function + 17BA4E

Используя setf над symbol-function:

(setf (symbol-function ’add2) #’(lambda (x) (+ x 2))) мы можем определить новую глобальную функцию, которую можно использовать точно так же, как если бы мы определили ее с помощью defun:

(add2 1) Фактически defun делает немногим более чем просто преобразование выражения типа (defun add2 (x) (+ x 2)) в выражение с setf. Использование defun делает программы более легкими для понимания, а также сообщает компилятору некоторую инГлава 6. Функции формацию о функции, хотя, строго говоря, использовать defun при написании программ вовсе не обязательно.

Сделав первым аргументом defun выражение вида (setf f), вы определите, что будет происходить, когда setf вызван с первым аргументом f.°

Ниже приведен пример функции primo, которая является аналогом car:

(defun primo (lst) (car lst)) (defun (setf primo) (val lst) (setf (car lst) val)) В последнем определении на месте имени функции находится выражение (setf primo), первым параметром является устанавливаемое значение, а вторым – аргумент primo.°

Теперь любой setf для primo будет являться вызовом функции, определенной выше:

(let ((x (list ’a ’b ’c))) (setf (primo x) 480) x) (480 B C) Совсем не обязательно определять саму функцию primo, чтобы определить поведение (setf primo), однако такие определения обычно даются парами.

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

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

(defun foo (x) "Implements an enhanced paradigm of diversity."

x)

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

(documentation ’foo ’function) "Implements an enhanced paradigm of diversity."

6.2. Локальные функции Функции, определенные с помощью defun или setf вместе с symbol-function, являются глобальными. Как и глобальные переменные, они могут быть использованы везде. Кроме того, есть возможность определять локальные функции, которые, как и локальные переменные, доступны лишь внутри определенного контекста.

Локальные функции могут быть определены с помощью конструкции labels – своего рода let для функций. Ее первым аргументом является не

6.3. Списки параметров

–  –  –

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

Теперь мы можем написать funcall с помощью apply:

(defun our-funcall (fn &rest args) (apply fn args)) Также нам уже знакомы параметры, которые могут быть пропущены и в таком случае получат значение по умолчанию. Такие параметры называются необязательными (optional). (Обычные параметры иногда называются обязательными (required).) Если символ &optional встречается в списке параметров функции (defun philosoph (thing &optional property) (list thing ’is property)) то все последующие аргументы будут необязательными, а их значением по умолчанию будет nil:

(philosoph ’death) (DEATH IS NIL) Мы можем задать исходное значение явно, заключив его в скобки вместе с параметром. Следующая версия philosoph (defun philosoph (thing &optional (property ’fun)) (list thing ’is property)) имеет более «радостное» значение по умолчанию:

(philosoph ’death) (DEATH IS FUN) Значением по умолчанию необязательного параметра может быть не только константа, но и любое Лисп-выражение. Оно будет вычисляться заново каждый раз, когда это потребуется.

Параметры по ключу (keyword) предоставляют большую гибкость, чем необязательные параметры. Поместив символ &key в список параметров, вы помечаете все последующие параметры как необязательные.

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

(defun keylist (a &key x y z) (list a x y z)) KEYLIST (keylist 1 :y 2) (1 NIL 2 NIL) (keylist 1 :y 3 :x 2) (1 2 3 NIL) Для параметров по ключу, так же как и для необязательных, значением по умолчанию является nil, но в то же время можно задать выражение для их вычисления.

6.4. Пример: утилиты Ключевые слова и связанные с ними значения могут собираться с помощью &rest и в таком виде передаваться другим функциям, ожидающим их. Например, мы могли бы определить adjoin следующим образом:

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

В разделе 5.2 был представлен макрос destructing-bind.

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

(destructing-bind ((&key w x) &rest y) ’((:w 3) a) (list w x y)) (3 NIL (A))

6.4. Пример: утилиты В разделе 2.6 упоминалось, что Лисп состоит по большей части из таких же функций, как те, что вы можете определить самостоятельно.

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

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

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

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

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

Основной секрет в написании таких программ – подход снизу-вверх, и программы вовсе не обязаны быть объектно-ориентированными, 116 Глава 6. Функции чтобы писаться снизу-вверх. На самом деле, функциональный стиль даже лучше адаптирован для создания повторно используемых программ.

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

Вы можете применять этот подход в своих программах, создавая утилиты. На рис. 6.1 представлена небольшая выборка полезных утилит.

Первые две, single? и append1, приведены с целью показать, что даже очень короткие утилиты могут быть полезными.

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

(single? ’(a)) T

–  –  –

Рис. 6.1. Утилиты

6.4. Пример: утилиты

Вторая утилита напоминает cons, однако, в отличие от cons, она добавляет элемент в конец списка, а не в начало:

(append1 ’(a b c) ’d) (A B C D) Следующая утилита, map-int, принимает функцию и целое число n, возвращая список, состоящий из значений этой функции для всех целых чисел от 0 до n–1.

Такая функция может пригодиться при тестировании кода.

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

(map-int #’identity 10) (0 1 2 3 4 5 6 7 8 9) А если мы хотим получить список из десяти случайных чисел между 0 и 99 (включительно), просто пропустим параметр лямбда-выражения и напишем:

(map-int #’(lambda (x) (random 100)) 10) (85 40 73 64 28 21 67 5 32) На примере map-int показана распространенная Лисп-идиома для построения списков. В ней создается аккумулятор acc, который исходно содержит nil, и в него последовательно добавляются элементы с помощью push. По завершении возвращается перевернутый список acc.1 Эту же идиому мы видим и в filter. Функция filter принимает функцию и список и возвращает список результатов применения функции к элементам исходного списка, причем возвращаемый список состоит только из элементов, отличающихся от nil:

(filter #’(lambda (x) (and (evenp x) (+ x 10))) ’(1 2 3 4 5 6 7)) (12 14 16) Функцию filter можно также рассматривать как обобщение remove-if.

Последняя функция на рис. 6.1, most, возвращает элемент списка, имеющий наивысший рейтинг с точки зрения заданной рейтинговой функции. Помимо этого элемента она также возвращает соответствующее ему значение.

(most #’length ’((a b) (a b c) (a))) (A B C) В данном контексте nreverse (стр. 229) делает то же, что и reverse, однако она

–  –  –

Если таких элементов несколько, most возвращает первый из них.

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

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

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

(defun combiner (x) (typecase x (number #’+) (list #’append) (t #’list))) С ее помощью мы сможем создать комбинирующую функцию общего вида:

(defun combine (&rest args) (apply (combiner (car args)) args)) Она принимает аргументы любого типа и объединяет их в соответствии с типом. (Для упрощения рассматривается лишь тот случай, когда все аргументы имеют один тип.) (combine 2 3) (combine ’(a b) ’(c d)) (A B C D) В разделе 2.10 объяснялось, что лексические переменные действительны только внутри контекста, в котором они были определены. Вместе с этим ограничением мы получаем обещание, что они будут по-прежнему действительны до тех пор, пока этот контекст где-нибудь используется.

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

6.5. Замыкания этой переменной. Приведем функцию, добавляющую 3 к своему аргументу:

(setf fn (let ((i 3)) #’(lambda (x) (+ x i)))) #Interpreted-Function C0A51E (funcall fn 2) Если функция ссылается на определенную вне нее переменную, то такая переменная называется свободной. Функцию, ссылающуюся на свободную лексическую переменную, принято называть замыканием (closure)1. Свободная переменная будет существовать до тех пор, пока доступна использующая ее функция.

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

Это происходит без каких-либо внешних проявлений, как, например, в функции, приведенной ниже:

(defun add-to-list (num lst) (mapcar #’(lambda (x) (+ x num)) lst)) Функция принимает число и список и возвращает новый список, в котором к каждому элементу исходного списка добавляется заданное число. Переменная num в лямбда-выражении является свободной, значит, функции mapcar передается замыкание.

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

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

(defun make-adder (n) #’(lambda (x) (+ x n))) Принимается число n и возвращается функция, которая складывает число n с ее аргументом:

(setf add3 (make-adder 3)) #Interpreted-Function C0EBF6 (funcall add3 2) (setf add27 (make-adder 27)) #Interpreted-Function C0EE4E (funcall add27 2) Название «замыкание» взято из ранних диа лектов Лиспа. Оно происходит

–  –  –

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

counter:

(let ((counter 0)) (defun reset () (setf counter 0)) (defun stamp () (setf counter (+ counter 1)))) Такая пара функций может использоваться для создания меток времени. При каждом вызове stamp мы получаем число, на единицу большее, чем предыдущее. Вызывая reset, мы обнуляем счетчик:

(list (stamp) (stamp) (reset) (stamp)) (1 2 0 1) Несомненно, можно сделать то же самое с использованием глобальной переменной, однако последняя не защищена от воздействий извне.

В Common Lisp существует встроенная функция complement, принимающая предикат и возвращающая противоположный ему. Например:

(mapcar (complement #’oddp) ’(1 2 3 4 5 6)) (NIL T NIL T NIL T)

Благодаря замыканиям написать такую функцию очень просто:

(defun our-complement (f) #’(lambda (&rest args) (not (apply f args)))) Если вы отвлечетесь от этого маленького, но замечательного примера, то обнаружите, что он – лишь вершина айсберга. Замыкания являются одной из уникальных черт Лиспа. Они открывают путь к новым возможностям в программировании, не достижимым в других языках.°

6.6. Пример: строители функций Язык Dylan известен как гибрид Scheme и Common Lisp, использующий синтаксис Pascal.° Он имеет большой набор функций, которые возвращают функции. Помимо complement, рассмотренной нами в предыдущем разделе, Dylan включает compose, disjoin, conjoin, curry, rcurry и always.

На рис. 6.2 приведены реализации этих функций в Common Lisp, а на рис. 6.3 показаны эквиваленты, следующие из этих определений.

Первая из них, compose, принимает одну или несколько функций и возвращает новую функцию, которая применяет их по очереди. Таким образом, (compose #’a #’b #’c)

6.6. Пример: строители функций

–  –  –

возвращает функцию, эквивалентную вызову:

#’(lambda (&rest args) (a (b (apply #’c args)))) Из приведенного примера следует, что последняя функция может принимать любое количество аргументов, в то время как остальные должны принимать ровно один.

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

(mapcar (compose #’list #’round #’sqrt) ’(4 9 16 25)) ((2) (3) (4) (5)) Следующие две функции, disjoin и conjoin, принимают некоторый набор предикатов. Вызов disjoin возвращает предикат, возвращающий истину, если хотя бы один из заданных предикатов является истинным.

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

(mapcar (disjoin #’integerp #’symbolp) ’(a "a" 2 3)) (T NIL T T) (mapcar (conjoin #’integerp #’oddp) ’(a "a" 2 3)) (NIL NIL NIL T) Рассматривая предикаты как множества, можно сказать, что disjoin возвращает объединение множеств, а conjoin – их пересечение.

Функции curry и rcurry («right curry») имеют общую идею с определенной в предыдущем разделе make-adder. Они обе принимают функцию и некоторые ее аргументы и возвращают функцию, которая ожидает получить лишь остающиеся аргументы.

Каждое из следующих выражений равносильно (make-adder 3):

(curry #’+ 3) (rcurry #’+ 3) Разница между curry и rcurry станет заметна на примере функции, различающей свои аргументы. Если мы применим curry к –, то полученная функция, будет вычитать свой аргумент из заданного числа:

(funcall (curry #’- 3) 2) в то время как для rcurry полученная функция будет вычитать заданное число из своего аргумента:

(funcall (rcurry #’- 3) 2)

-1 Наконец, always имеет свой аналог в Common Lisp – функцию constanly.

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

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

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

(let ((x 10)) (defun foo () x)) то символ x, используемый в функции, будет ссылаться на эту переменную независимо от того, была ли в окружении, из которого функция вызывалась, переменная x, имеющая другое значение:

(let ((x 20)) (foo)) В динамическом же диапазоне используется то значение переменной, которое имеется в окружении, где вызывается функция, а не в окружении, где она была определена.° Чтобы заставить переменную иметь динамический диапазон, нужно объявить ее как special в том контексте, где она встречается. Если мы определим foo следующим образом:

(let ((x 10)) (defun foo () (declare (special x)) x)) то переменная x больше не будет ссылаться на лексическую переменную, существующую в контексте, в котором функция была определена, а будет ссылаться на любую динамическую переменную x, которая существует в момент вызова функции:

(let ((x 20)) (declare (special x)) Под диапазоном (scope) следует понимать область видимости; соответствен

–  –  –

(foo)) Форма declare может начинать любое тело кода, в котором создаются новые переменные. Декларация special уникальна тем, что может изменить поведение программы. В главе 13 будут рассмотрены другие декларации. Прочие из них являются всего лишь советами компилятору;

они могут сделать программу быстрее, но не меняют ее поведение.

Глобальные переменные, установленные с помощью setf в toplevel, подразумеваются специальными:

(setf x 30) (foo) Но в исходном коде лучше не полагаться на такие неявные определения и использовать defparameter.

В каких случаях может быть полезен динамический диапазон? Обычно он применяется, чтобы присвоить некоторой глобальной переменной новое временное значение. Например, для управления параметрами печати объектов используются 11 глобальных переменных, включая *print-base*, которая по умолчанию установлена как 10.

Чтобы печатать числа в шестнадцатеричном виде (с основанием 16), можно привязать *print-base* к соответствующей базе:

(let ((*print-base* 16)) (princ 32)) Здесь отображены два числа: вывод princ и значение, которое она возвращает. Они представляют собой одно и то же значение, напечатанное сначала в шестнадцатеричном формате, так как *print-base* имела значение 16, а затем в десятичном, поскольку на возвращаемое из let значение уже не действовало *print-base* 16.

6.8. Компиляция В Common Lisp можно компилировать функции по отдельности или же файл целиком. Если вы просто наберете определение функции в toplevel:

(defun foo (x) (+ x 1)) FOO то многие реализации создадут интерпретируемый код. Проверить, является ли функция скомпилированной, можно с помощью compiledfunction-p:

(compiled-function-p #’foo) NIL

6.9. Использование рекурсии

Функцию можно скомпилировать, сообщив compile имя функции:

(compile ’foo) FOO После этого интерпретированное определение функции будет заменено скомпилированным. Скомпилированные и интерпретированные функции ведут себя абсолютно одинаково, за исключением отношения к compiled-function-p.

Функция compile также принимает списки. Такое использование compile обсуждается на стр. 171.

К некоторым функциям compile не применима: это функции типа stamp или reset, определенные через toplevel в собственном (созданном let) лексическом контексте1. Вам придется набрать эти функции в файле, затем его скомпилировать и загрузить. Этот запрет установлен по техническим причинам, а не потому, что что-то не так с определением функций в иных лексических окружениях.

Чаще всего функции компилируются не по отдельности, а в составе файла с помощью compile-file. Эта функция создает скомпилированную версию заданного файла, как правило, с тем же именем, но другим расширением. После загрузки скомпилированного файла compiled-function-p вернет истину для любой функции из этого файла.

Если одна функция используется внутри другой, то она также должна быть скомпилирована. Таким образом, make-adder (стр.

119), будучи скомпилированной, возвращает скомпилированную функцию:

(compile ’make-adder) MAKE-ADDER (compiled-funcion-p (make-adder 2)) T

6.9. Использование рекурсии В Лиспе рекурсия имеет большее значение, чем в других языках. Этому есть три основные причины:

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

2. Рекурсивные структуры данных. Неявное использование указателей в Лиспе облегчает рекурсивное создание структур данных. Наиболее общей структурой такого типа является список: либо nil, либо cons, чей cdr – также список.

3. Элегантность. Лисп-программисты придают огромное значение красоте их программ, а рекурсивные алгоритмы зачастую выглядят намного элегантнее их итеративных аналогов.

В Лиспах, существовавших до ANSI Common Lisp, первый аргумент compile

–  –  –

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

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

Чтобы решить задачу с помощью рекурсии, необходимо сделать следующее:

1. Нужно показать, как можно решить ее с помощью разделения на конечное число похожих, но более мелких подзадач.

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

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

Например, в предложенном ниже рекурсивном алгоритме нахождения длины списка мы на каждом шаге рекурсии находим длину уменьшенного списка:

1. В общем случае длина списка равна длине его cdr, увеличенной на 1.

2. Длину пустого списка принимаем равной 0.

Когда это определение переводится в код, сначала идет базовый случай.

Однако этап формализации задачи обычно начинается с рассмотрения наиболее общего случая.

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

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

Объект содержится в списке, если он является его первым member элементом или содержится в cdr этого списка. В пустом списке не содержится ничего.

Копия дерева, представленного как cons-ячейка, – это ячейcopy-tree ка, построенная из copy-tree для car исходной ячейки и copytree для ее cdr. Для атома copy-tree – это сам этот атом.

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

Некоторые алгоритмы естественным образом ложатся на такие определения, но не все. Вам придется согнуться в три погибели, чтобы определить our-copy-tree (стр. 205) без использования рекурсии. С другой стороны, итеративный вариант show-squares (стр. 40) более доступен для понимания, нежели его рекурсивный аналог (стр. 41). Часто оптимальный выбор остается неясен до тех пор, пока вы не приступите к написанию кода.

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

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

1. Fib(0) = Fib(1) = 1.

2. Fib(n) = Fib(n – 1) + Fib(n – 2).

При этом дословная трансляция данного определения в код:

(defun fib (n) (if (= n 1) (+ (fib (- n 1)) (fib (- n 2))))) дает совершенно неэффективную функцию. Дело в том, что такая функция вычисляет одни и те же вещи по несколько раз. Например, вычисляя (fib 10), она вызовет (fib 9) и (fib 8). Однако вычисление (fib 9) уже включает в себя (fib 8), и получается, что она выполняет это вычисление заново.

Ниже приведена аналогичная итеративная функция:

(defun fib (n) (do ((i n (- i 1)) (f1 1 (+ f1 f2)) (f2 1 f1)) ((= i 1) f1))) В действительности, хвостовая рекурсия просто преобразуется в соответст

–  –  –

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

Итоги главы

1. Именованная функция хранится как symbol-function соответствующего символа. Макрос defun скрывает подобные детали. Кроме того, он позволяет сопровождать функции документацией, а также настраивать поведение setf.

2. Имеется возможность определять локальные функции; этот процесс напоминает определение локальных переменных.

3. Функции могут иметь необязательные и остаточные аргументы, а также аргументы по ключу.

4. Утилиты дополняют язык. Они представляют собой пример программирования снизу-вверх в маленьком масштабе.

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

6. Dylan предоставляет функции для построения других функций. С использованием замыканий мы легко можем реализовать их в Common Lisp.

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

8. Функции могут компилироваться индивидуально или (чаще) в составе файла.

9. Рекурсивный алгоритм решает задачу разделением ее на конечное число похожих подзадач меньшего размера.

Упражнения

1. Определите версию tokens (стр. 81), которая использует ключи :test и :start, по умолчанию равные #’constituent и 0 соответственно.

2. Определите версию bin-search (стр. 75), использующую ключи :key, :test, :start и :end, имеющие обычные для них значения по умолчанию.

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

4. Измените функцию most (стр. 118) так, чтобы она возвращала два значения – два элемента, имеющие наибольший вес.

5. Определите remove-if (без аргументов по ключу) с помощью filter (стр. 117).

Упражнения

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

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

8. Предположим, что функция expensive имеет один аргумент – целое число между 0 и 100 включительно. Она производит сложные и дорогостоящие вычисления. Определите функцию frugal, возвращающую тот же ответ, что и expensive, но вызывающую expensive, лишь когда ей передается аргумент, который не встречался ранее.

9. Определите функцию наподобие apply, но где все числа, которые могут быть напечатаны при ее выполнении, выводятся в восьмеричном формате (base 8).

Ввод и вывод Глава 7.

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

Существует два вида потоков: потоки знаков и бинарные потоки. В этой главе рассмотрены лишь потоки знаков; бинарные потоки будут описаны в разделе 14.2.

7.1. Потоки Потоки – это объекты Лиспа, представляющие собой источники и/или приемники для передачи символов. Чтобы прочитать или записать файл, необходимо открыть соответствующий поток. Однако поток – это не то же самое, что файл. Когда вы читаете или печатаете что-либо в toplevel, вы также используете поток. Создавая потоки, вы даже можете читать из строк или писать в них.

По умолчанию для ввода используется поток *standard-input*, для вывода – *standard-output*. Первоначально они, как правило, ссылаются на один и тот же поток, соответствующий toplevel.

С функциями read и format мы уже знакомы. Ранее мы пользовались ими для чтения и печати в toplevel. Функция read имеет необязательный аргумент, который определяет входной поток и по умолчанию установлен в *standard-input*. Первый аргумент функции format также может быть потоком. Ранее мы вызывали format с первым аргументом t, который соответствует потоку *standard-output*. Таким образом, до этого момента мы наблюдали лишь поведение этих функций при использовании аргуПотоки ментов по умолчанию. Однако те же операции мы можем совершать и с любыми другими потоками.

Путь (pathname) – это переносимый способ определения пути к файлу.

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

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

(setf path (make-pathname :name "myfile")) #P"myfile" Базовая функция для открытия файлов – open. Ей необходимо сообщить путь1, а ее поведением можно управлять с помощью многочисленных аргументов по ключу. В случае успеха она возвращает поток, указывающий на файл.

Вам нужно указать, как вы собираетесь использовать создаваемый поток. Параметр :direction определяет, будет ли производиться чтение (:input), запись (:output) или и то и другое одновременно (:io). Если поток используется для чтения, то параметр :if-exists определяет его поведение в случае, если файл уже существует. При этом обычно используется :supersede (перезаписать поверх).

Итак, создадим поток, через который мы сможем записать что-либо в файл "myfile":

(setf str (open path :direction :output :if-exists :supersede)) #Stream C017E6 Способ отображения потоков при печати зависит от используемой реализации Common Lisp.

Если теперь мы укажем поток str первым аргументом функции format, она будет печатать свой вывод в этот поток, а не в toplevel:

(format str "Something~%") NIL Но если мы теперь посмотрим на содержимое файла, то можем и не найти в нем нашу строку. Некоторые реализации осуществляют вывод порциями, и ожидаемое содержимое файла может появиться лишь после закрытия потока:

(close str) NIL Всегда закрывайте файлы по окончании их использования. Пока вы не сделаете этого, вы не можете быть уверены относительно их содержимого. Если мы теперь взглянем на содержимое файла "myfile", то обнаружим строчку:

Something Вместо пути можно передать просто строку, однако такой способ не перено

–  –  –

Если мы хотим всего лишь прочитать содержимое файла, то откроем поток с аргументом :direction :input:

(setf str (open path :direction :input)) #Stream C01C86 Содержимое файла можно читать с помощью любой функции чтения.

Более подробно ввод описывается в разделе 7.2. Приведем пример, в котором для чтения строки из файла используется функция read-line:

(read-line str) "Something" NIL (close str) NIL Не забудьте закрыть файл после завершения чтения.

Функции open и close практически никогда не используются явно. Гораздо удобнее использовать макрос with-open-file. Первый его аргумент – список, содержащий некоторое имя переменной и все те же аргументы, которые вы могли бы передать функции open. Далее следуют выражения, которые могут использовать заданную выше переменную, связанную внутри тела макроса с именем переменной. После выполнения всех выражений тела макроса поток закрывается автоматически.

Таким образом, операция записи в файл может быть целиком выражена так:

(with-open-file (str path :direction :output :if-exists :supersede) (format str "Something~%")) Макрос with-open-file использует unwind-protect (стр. 295), чтобы гарантировать, что файл будет действительно закрыт, даже если выполнение выражений внутри тела макроса будет аварийно прервано.

7.2. Ввод Двумя наиболее популярными функциями чтения являются read-line и read. Первая читает все знаки до начала новой строки, возвращая их в виде строки. Один ее необязательный параметр, как и для read, определяет входной поток. Если он не задан явно, то по умолчанию используется *standard-input*:

(progn (format t "Please enter your name: ") (read-line)) Please enter your name: Rodrigo de Bivar "Rodrigo de Bivar" NIL Эту функцию стоит использовать, если вы хотите получить значения такими, какими они были введены. (Вторым возвращаемым значением

7.2. Ввод

–  –  –

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

Лучший способ: пользовательский ввод читается с помощью read-line и далее обрабатывается с помощью read-from-string.° Эта функция принимает строку и возвращает первый объект, прочитанный из нее:

(read-from-string "a b c") A Помимо прочитанного объекта она возвращает позицию в строке, на которой завершилось чтение.

В общем случае read-from-string может принимать два необязательных аргумента и три аргумента по ключу. Два необязательных – те же, что и третий и четвертый аргументы в read-line (вызывать ли ошибку при достижении конца строки и, если нет, что возвращать в этом случае).

А аргументы по ключу :start и :end ограничивают часть строки, в которой будет выполняться чтение.

Рассмотренные в этом разделе функции определены с помощью более примитивной read-char, считывающей одиночный знак. Она принимает те же четыре необязательных аргумента, что и read, и read-line. Common Lisp также определяет функцию peek-char, которая похожа на read-char, но не удаляет прочитанный знак из потока.

7.3. Вывод Имеются три простейшие функции вывода: prin1, princ и terpri. Всем им можно сообщить выходной поток; по умолчанию это *standard-output*.

Разница между prin1 и princ, грубо говоря, в том, что prin1 генерирует вывод для программ, а princ – для людей.

Так, например, prin1 печатает двойные кавычки вокруг строк, а princ – нет:

(prin1 "Hello") "Hello" "Hello" (princ "Hello") Hello "Hello" Обе функции возвращают свой первый аргумент, который, кстати, совпадает с тем, который отображает prin1. Функция terpri печатает только новую строку.

Зная об этих функциях, вам легче будет понять поведение более общей format. С помощью функции format может быть осуществлен практически любой вывод. Она принимает поток (а также t или nil), строку форматирования и ноль или более аргументов. Строка форматирования может содержать директивы форматирования, которые начинаются со знака ~ (тильда). На их место будут выведены представления аргументов, переданных format.

7.3. Вывод Передавая t в качестве первого аргумента, мы направляем вывод в *standard-output*. Если первый аргумент – nil, то format возвратит строку вместо того, чтобы ее напечатать. Ради краткости будем приводить только такие примеры. Функцию format можно рассматривать одновременно и как невероятно мощный, и как жутко сложный инструмент. Она понимает огромное количество директив, но только часть из них вам придется использовать. Две наиболее распространенные директивы: ~A и ~%.

(Между ~a и ~A нет различия, однако принято использовать вторую директиву, потому что в строке форматирования она более заметна.) ~A – это место для вставки значения, которое будет напечатано с помощью princ. ~% соответствует новой строке.

(format nil "Dear ~A,~% Our records indicate…" "Mr. Malatesta") "Dear Mr. Malatesta, Our records indicate…" В этом примере format возвращает один аргумент – строку, содержащую символ переноса строки.

Директива ~S похожа на ~A, однако она выводит объекты так же, как

prin1, а не как princ:

(format t "~S ~A" "z" "z") "z" z NIL

Директивы форматирования сами могут принимать аргументы. ~F используется для печати выровненных справа чисел с плавающей запятой1 и может принимать пять аргументов:

1. Суммарное количество выводимых символов. По умолчанию это длина числа.

2. Количество выводимых символов после точки. По умолчанию выводятся все.

3. Смещение точки влево (смещение на один знак соответствует умножению на 10). По умолчанию отсутствует.

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

5. Символ, печатаемый перед левой цифрой. По умолчанию – пробел.

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

–  –  –

Вот пример, в котором используются все пять аргументов:

(format nil "~10,2,0,’*,’ F" 26.21875) " 26.22" Исходное число округляется до двух знаков после точки (сама точка смещается на 0 положений влево, то есть не смещается), для печати числа выделяется пространство в 10 символов, на месте незаполненных слева полей печатаются пробелы. Обратите внимание, что символ звездочки передается как ’*, а не как обычно #\*. Поскольку заданное число вписывается в предложенное пространство 10 символов, четвертый аргумент не используется.

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

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

(format nil "~,2,,,F" 26.21875) "26.22"

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

(format nil "~,2F" 26.21875) "26.22" Предупреждение: Округляя числа, format не гарантирует округление в большую или меньшую сторону. Поэтому (format nil "~,1F" 1.25) может выдать либо "1.2", либо "1.3". Таким образом, если вам нужно округление в конкретную сторону (например, при конвертации валют), перед печатью округляйте выводимое число явным образом.

7.4. Пример: замена строк В этом разделе приведен пример использования ввода-вывода – простая программа для замены строк в текстовых файлах. Мы создадим функцию, которая сможет заменить каждую строку old в файле на строку new. Простейший способ сделать это – сверять каждый символ с первым символом old. Если они не совпадают, то мы можем просто напечатать символ из файла. Если они совпадают, то сверяем следующий символ из файла со вторым символом old, и т. д. Если найдено совпадение, то печатаем на выход строку new.° Что происходит, когда мы натыкаемся на несовпадение в процессе сверки символов? Например, предположим, что мы ищем шаблон "abac", а входной файл содержит "ababac". Совпадение будет наблюдаться вплоть до четвертого символа: в файле это b, а в шаблоне c. Дойдя до четвертого символа, мы понимаем, что можем напечатать первый символ a. Однако некоторые пройденные символы нам все еще нужны, потому что третий прочтенный символ a совпа дает с первым символом шаблона. Таким

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

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

На рис. 7.1 показан код, реализующий операции с кольцевым буфером.

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

Два других индекса, used и new, потребуются для использования буфера в нашем приложении.

Они могут принимать значение между start и end, причем всегда будет соблюдаться следующее соотношение:

start used new end Пару used и new можно считать ана логом start и end для текущего совпа дения. Когда мы начинаем отслеживать совпа дение, used будет равен start, а new – end. Для каждого последовательного совпадения пары символов used будет увеличиваться. Когда used достигнет new, это будет означать, что мы считали из буфера все элементы, занесенные туда до начала проверки данного совпадения. Нам не нужно использовать больше символов, чем было в буфере перед началом нахождения текущего совпадения, иначе мы бы использовали некоторые символы по нескольку раз. Поэтому нам требуется другой индекс, new, который исходно равен end, но не увеличивается при добавлении новых символов во время проверки совпадения.

Функция bref возвращает элемент, хранящийся в буфере по заданному индексу. Используя остаток от деления заданного индекса на длину вектора, мы можем сделать вид, что наш буфер имеет неограниченный размер. Вызов (new-buf n) создает новый буфер, способный хранить до n элементов.

Чтобы поместить в буфер новое значение, будем применять buf-insert.

Эта функция увеличивает индекс end и кладет на это место заданный элемент. Обратной функцией является buf-pop, которая возвращает первый элемент буфера и увеличивает индекс start. Эти две функции нужны для любого кольцевого буфера.

138 Глава 7. Ввод и вывод

–  –  –

Рис. 7.1. Операции с кольцевым буфером Следующие две функции написаны специально для нашего приложения: buf-next читает значение из буфера без его извлечения, buf-reset сбрасывает used и new до исходных значений start и end. Если все значения до new прочитаны, buf-next возвратит nil. Поскольку мы собираемся хранить в буфере исключительно символы, отличить nil как особое значение не будет проблемой.

Наконец, buf-flush выводит содержимое буфера, записывая все доступные элементы в заданный поток, а buf-clear очищает буфер, сбрасывая все индексы до -1.

7.4. Пример: замена строк Функции из кода на рис. 7.1 используются в коде на рис. 7.2, предоставляющем средства для замены строк. Функция file-subst принимает четыре аргумента: искомую строку, ее замену, входной и выходной файлы. Она создает потоки, связанные с заданными файлами, и вызывает функцию stream-subst, которая и выполняет основную работу.

Вторая функция, stream-subst, использует алгоритм, который был схематически описан в начале раздела. Каждый раз она читает из входного потока один символ. Если он не совпадает с первым элементом искомой строки, он тут же записывается в выходной поток (1). Когда начинается совпадение, символы ставятся в очередь в буфер buf (2).

–  –  –

Переменная pos указывает на положение символа в искомой строке. Если оно равно длине самой строки, это означает, что совпадение найдено.

В таком случае в выходной поток записывается замена строки, а буфер очищается (3). Если в какой-либо момент последовательность символов перестает соответствовать искомой строке, мы вправе забрать первый символ из буфера и записать в выходной поток, а также установить pos равным нулю, а сам буфер сбросить (4).

Следующая таблица наглядно демонстрирует, что происходит при замене "baro" на "baric" в файле, содержащем только одно слово barbarous:

–  –  –

Первая колонка содержит текущий символ – значение переменной c;

вторая показывает, откуда он был считан – из буфера или же прямиком из файла; третья показывает символ, с которым мы сравниваем, – элемент old по индексу pos; четвертая указывает на вариант действия, совершаемого в данном случае; пятая колонка соответствует текущему содержимому буфера после выполнения операции. В последней колонке точками после символа показаны также позиции used и new. Если они совпадают, то это отображается с помощью двоеточия.

Предположим, что у нас есть файл "test1", содержащий следующий текст:

The struggle between Liberty and Authority is the most conspicuous feature in the portions of history with which we are earliest familiar, particularly in that of Greece, Rome, and England.

После выполнения (file-subst " th" " z" "test1" "test2") файл "test2" будет иметь следующий вид:

The struggle between Liberty and Authority is ze most conspicuous feature in ze portions of history with which we are earliest familiar, particularly in zat of Greece, Rome, and England.

7.5. Макрознаки Чтобы максимально упростить пример, код на рис. 7.2. просто заменяет одну строку на другую. Однако его несложно обобщить и соорудить поиск по полноценным шаблонам вместо последовательностей букв.

Все, что вам потребуется, – заменить вызов char= на функцию проверки на соответствие шаблону.

7.5. Макрознаки Макрознаки (macro character) – это знаки, имеющие особое значение для функции read. Знаки a и b обычно обрабатываются как есть, однако знак открывающей круглой скобки распознается как начало считывания списка.

Макрознаки или их комбинация известны также как макросы чтения (read-macro). Многие макросы чтения в Common Lisp на деле являются сокращениями. Например, кавычка. Цитируемое выражение, например ’a, при обработке с помощью read раскрывается в список (quote a).

При наборе подобного выражения в toplevel оно вычисляется сразу же после прочтения, и вы никогда не увидите этого преобразования.

Его можно обнаружить, вызывая read явно:

(car (read-from-string "’a")) QUOTE Макрос чтения, соответствующий quote, состоит лишь из одного знака, что является редкостью. С ограниченным набором знаков сложно получить много односимвольных макросов чтения. Большинство макросов чтения состоит из двух или более знаков.

Такие макросы чтения называются диспетчеризуемыми (dispatching), а их первый знак называется диспетчером. У всех стандартных макросов чтения знаком-диспетчером является решетка #. С некоторыми из них мы уже знакомы. Например, #’ соответствует (function...), а ’ является сокращением для (quote...).

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

#(...) является сокращением для векторов, #nА(...) – для массивов, #\ – для знаков, #S(n...) – для структур. При выводе на печать через prin1 (или format с ~S) такие объекты отобразятся в виде соответствующих макросов чтения.1 Это означает, что объекты, записанные буквально, могут быть считаны обратно в таком же виде:

(let ((*print-array* t)) (vectorp (read-from-string (format nil "~S" (vector 1 2))))) T Чтобы векторы и массивы печата лись таким образом, необходимо устано

–  –  –

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

Не все объекты отображаются в соответствии с таблицей чтения readtable. Функции и хеш-таблицы, к примеру, отображаются через #....

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

При определении собственного представления для какого-либо объекта (например, для отображения структур) важно помнить этот принцип.

Либо объект в вашем представлении может быть прочитан обратно, либо вы используете #....

Итоги главы

1. Потоки – источники ввода и получатели вывода. В потоках знаков ввод и вывод состоят из знаков.

2. Поток, используемый по умолчанию, соответствует toplevel. При открытии файлов создаются новые потоки.

3. Ввод может обрабатываться как набор объектов, строка знаков или же как отдельные знаки.

4. Функция format предоставляет полное управление выводом.

5. Чтобы осуществить замену строк в текстовом файле, вам придется считывать знаки в буфер.

6. Когда read встречает макрознак типа ’, она вызывает связанную с ним функцию.

Упражнения

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

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

3. Пусть в файле некоторого формата комментарии помечаются знаком %. Содержимое строки от начала знака комментария до ее конца игнорируется. Определите функцию, принимающую два имени файла и записывающую во второй содержимое первого с вырезанными комментариями.

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

Упражнения

4. Определите функцию, принимающую двумерный массив чисел с плавающей запятой и отображающую его в виде аккуратных колонок. Каждый элемент должен печататься с двумя знаками после запятой на пространстве 10 знаков. (Исходите из предположения, что все они уместятся в отведенном пространстве.) Вам потребуется функция array-dimensions (стр. 374).

5. Измените функцию stream-subst так, чтобы она понимала шаблоны с метазнаком +. Если знак + появляется в строке old, он может соответствовать любому знаку.

6. Измените функцию stream-subst так, чтобы шаблон мог содержать элемент, соответствующий: любой цифре, любой цифре и букве, любому знаку. Шаблон должен уметь распознавать любые читаемые знаки. (Подсказка: old теперь не обязательно должен быть строкой.) Символы Глава 8.

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

В этой главе подробно обсуждаются все детали, связанные с символами.

8.1. Имена символов В главе 2 символы описывались как имена переменных, существующие сами по себе. Однако область применения символов в Лиспе шире, чем область применения переменных в большинстве других языков. На самом деле, имя символа – это обычная строка. Имя символа можно получить с помощью symbol-name:

(symbol-name ’abc) "ABC" Обратите внимание, что имена символов записываются в верхнем регистре. По умолчанию Common Lisp не чувствителен к регистру, поэтому при чтении он преобразует все буквы в именах к заглавным:

(eql ’aBc ’Abc) T (CaR ’(a b c)) A Для работы с символами, названия которых содержат пробелы или другие знаки, влияющие на алгоритм считывания, используется особый синтаксис. Любая последовательность знаков между вертикальными

8.2. Списки свойств черточками, считается символом. Таким образом вы можете поместить любые знаки в имя символа:

(list ’|Lisp 1.5| ’|| ’|abc| ’|ABC|) (|Lisp 1.5| || |abc| ABC) При считывании такого символа преобразование к верхнему регистру не производится, а макрознаки читаются как есть.

Так на какие же символы можно ссылаться, не прибегая к использованию вертикальной черты? По сути, на все символы, имена которых не являются числом и не содержат знаков, имеющих для read специального значения. Чтобы узнать, может ли символ существовать без такого оформления, достаточно просто посмотреть, как Лисп его напечатает.

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

Следует помнить, что вертикальные черточки – специальный синтаксис, а не часть имени символа:

(symbol-name ’|a b c|) "a b c" (Если вы желаете включить черточку в имя символа, расположите перед ней знак «\».) <

–  –  –

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

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

8.3. А символы-то не маленькие Символы создаются неявным образом, когда мы печатаем их имена, и при отображении самих символов их имена – это все что мы видим.

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

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

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

–  –  –

Рис. 8.1. Структура символа

8.4. Создание символов В разделе 8.1 было показано, как получать имена символов. Также возможно и обратное действие – преобразование строки в символ. Это более сложная задача, потому что для ее выполнения необходимо иметь представление о пакетах.

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

Большинство символов интернируются во время считывания. Когда вы впервые вводите символ, Лисп создает новый символьный объект и интернирует его в текущий пакет (по умолчанию это common-lisp-user).

Однако вы можете сделать то же самое вручную с помощью intern:

(intern "RANDOM-SYMBOL") RANDOM-SYMBOL NIL Функция intern принимает также дополнительный аргумент – пакет (по умолчанию используется текущий). Приведенный выше вызов создает в текущем пакете символ с именем "RANDOM-SYMBOL", если такого символа пока еще нет в данном пакете. Второй аргумент возвращает истину, когда такой символ уже существует.

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

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

При использовании языков, не поддерживающих разделение пространства имен, программистам, работающим над серьезными проектами, приходится вводить договоренности, чтобы избежать конфликтов при использования одних и тех же имен. Например, разработчик подсистемы отображения, вероятно, будет использовать имена, начинающиеся с disp_, в то время как программист, разрабатывающий математические процедуры, будет применять имена, начинающиеся с math_. Так, например, функция, выполняющая быстрое преобразование Фурье, вполне может носить имя math_fft.

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

148 Глава 8. Символы

–  –  –

(in-package my-application) Для создания нового пакета используется defpackage. Пакет my-application1 использует два других пакета, common-lisp и my-utilities. Это означает, что символы, экспортируемые ими, доступны в новом пакете без использования префиксов. Практически всегда в создаваемых пакетах используется common-lisp, поскольку никто не хочет использовать квалифицированное имя с префиксом при каждом обращении к встроенным в Лисп операторам и переменным.

Пакет my-applications сам экспортирует лишь три символа: win, lose и draw. Поскольку в defpackage было также задано сокращенное имя (nickname) пакета – app, то и к экспортируемым символам можно будет обращаться также и через него: app:win.

За defpackage следует вызов in-package, которая выставляет текущим пакетом my-application. Теперь все новые символы, для которых не указан пакет, будут интернироваться в my-application до тех пор, пока inpackage не изменит текущий пакет. После окончания загрузки файла, содержащего вызов in-package, значение текущего пакета сбрасывается в то, каким оно было до начала загрузки.

8.6. Ключевые слова Символы пакета keyword (известные как ключевые слова) имеют две особенности: они всегда самовычисляемы и вы можете всегда ссылаться на них просто как на :x вместо keyword:x. Когда мы только начинали использовать аргументы по ключу (стр. 60), вызов (member ’(a) ’((a) (z)) test:

#’equal) мог показаться нам более естественным, чем (member ’(a) ’((a) (z)) :test #’equal). Теперь мы понимаем, почему второе, слегка неестественное написание, является корректным. Двоеточие перед именем символа позволяет отнести его к ключевым словам.

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

8.7. Символы и переменные Зачем использовать ключевые слова вместо обычных символов? Потому что они доступны везде. Функция, принимающая символы в качестве аргументов, как правило, должна быть рассчитана на обработку именно ключевых слов. Например, следующий код может быть вызван из любого пакета без изменений:

(defun noise (animal) (case animal (:dog :woof) (:cat :meow) (:pig :oink))) Если бы эта функция использовала обычные символы, то она могла бы вызываться лишь в исходном пакете до тех пор, пока не будут экспортированы все символы-ключи case-выражения.

8.7. Символы и переменные В Лиспе есть определенная особенность, которая может смущать новичков: символы могут быть связаны с переменными двумя различными способами. Если символ является именем специальной переменной, ее значение хранится в одном из полей структуры символа (см. рис. 8.1).

Получить доступ к этому полю можно с помощью symbol-value. Таким образом, существует прямая связь между символом и представляемой им специальной переменной.

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

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

8.8. Пример: генерация случайного текста Если вам предстоит написать программу, каким-либо образом работающую со словами, отличной идеей часто является использование символов вместо строк, потому что символы атомарны. Они могут сравниваться за одну итерацию с помощью eql, в то время как строки сравниваются побуквенно с помощью string-equal или string=. В качестве примера рассмотрим генерацию случайного текста. Первая часть программы будет считывать образец текста (чем он больше, тем лучше), собирая информацию о связях между соседними словами. Вторая ее часть будет случайным образом выполнять проходы по сети, построенной ранее из слов исходного текста. После прохождения каждого слова программа 150 Глава 8. Символы будет делать взвешенный случайный шаг к следующему слову, встретившемуся после данного в оригинальном тексте. Полученный таким образом текст будет местами казаться довольно связным, потому что каждая пара слов в нем соотносится друг с другом. Поразительно, но целые предложения, а иногда даже и абзацы будут порой казаться вполне осмысленными.

На рис. 8.2 приводится первая часть программы – код для сбора информации из исходного текста. На его основе строится хеш-таблица *words*.

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

((|sin|. 1) (|wide|. 2) (|sights|. 1))

–  –  –

Рис. 8.2. Чтение образца текста

8.8. Пример: генерация случайного текста Выше приведено значение ключа |discover| для отрывка из «Paradise Lost» Мильтона1. Мы видим, что слово «discover» было использовано в поэме четыре раза: по одному разу перед словами «sin» и «sights» и дважды перед словом «wide». Подобная информация собирается функцией read-text, которая строит такой ассоциативный список для каждого слова в заданном тексте. При этом файл читается побуквенно, а слова собираются в строку buffer. С параметром maxword=100 программа сможет читать слова, состоящие не более чем из ста букв. Для английских слов этого более чем достаточно.

Если считанный знак является буквой (это определяется с помощью alpha-char-p) или апострофом, то он записывается в буфер. Любой другой символ сигнализирует об окончании слова, после чего все накопленное слово, интернированное в символ, передается в функцию see.

Некоторые знаки пунктуации также расцениваются как слова – функция punc выводит словесный эквивалент заданного знака пунктуации.

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

После отработки read-text таблица *words* будет содержать вхождения всех слов в заданном тексте. Их количество можно подсчитать с помощью hash-table-count. Английские тексты, не отличающиеся особым словесным разнообразием, редко содержат более 10 000 различных слов.

А вот теперь начинается самая веселая часть. На рис. 8.3 представлен код, генерирующий текст с помощью кода на рис. 8.2. Правит балом рекурсивная функция generate-text. Ей необходимо сообщить желаемое количество слов в создаваемом тексте и (необязательно) предыдущее слово. По умолчанию это точка, и текст начинается с нового предложения.

Для получения каждого последующего слова generate-text вызывает random-text с предыдущим словом. Функция random-text случайным образом выбирает одно из слов, следующих после prev в исходном тексте.

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

Однако вы уже знакомы с примером того, что она может сделать: речь о той самой строфе в начале книги, для генерации которой был использован отрывок из «Paradise Lost» Мильтона.° Речь об эпической поэме английского мыслителя Джона Мильтона «Поте

–  –  –

Рис. 8.3. Генерация текста Итоги главы

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

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

3. Символы – это довольно внушительные объекты и больше напоминают структуры, нежели просто имена.

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

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

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

7. В программах, работающих с отдельными словами, удобно представлять слова с помощью символов.

Упражнения

1. Могут ли два символа иметь одно имя, но не быть эквивалентными с точки зрения eql?

2. Оцените различие между количеством памяти, использованной для представления строки "FOO" и символа foo.

Упражнения

3. В вызове defpackage, приведенном на стр. 148, использовались лишь строки. Тем не менее вместо строк мы могли бы воспользоваться символами. Чем это может быть чревато?

4. Добавьте в программу на рис. 7.1 код, который помещает ее содержимое в пакет "RING". Аналогично для кода на рис. 7.2 создайте пакет "FILE". Уже имеющийся код должен остаться без изменений.

5. Напишите программу, проверяющую, была ли заданная цитата произведена с помощью Henley (см. раздел 8.8).

6. Напишите версию Henley, которая принимает слово и производит предложение, в середине которого находится заданное слово.

Числа Глава 9.

«Перемалывание чисел» (решение числовых задач большого объема) – одна из сильных сторон Лиспа. В нем имеется богатый набор числовых типов, а по их поддержке он даст фору многим другим языкам.

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

Целое число записывается строкой цифр: 2001. Число с плавающей запятой, помимо цифр, содержит десятичный разделитель – точку, например 253.72, или 2.5372e2 в экспоненциальном представлении. Рациональная дробь представляется в виде отношения двух целых чисел: 2/3.

Комплексное число вида a+bi можно записать как #c(a b), где a и b – два действительных числа одного типа.

Проверку на принадлежность к соответствующему типу осуществляют предикаты integerp, floatp и complexp. Иерархия численных типов представлена на рис. 9.1.

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

1. Если функция принимает хотя бы одно число с плавающей запятой, она также вернет десятичную дробь (или комплексное число, компоненты которого – десятичные дроби). Так (+ 1.0 2) вернет 3.0, а (+ #c(0 1.0) 2) вернет #c(2.0 1.0).

2. Рациональная дробь при возможности будет сокращена до целого числа. Вызов (/ 10 2) вернет 5.

9.2. Преобразование и извлечение

3. Комплексные числа, мнимая часть которых равна нулю, будут преобразованы в действительные. Таким образом, вызов (+ #c(1 -1) #c(2 1)) вернет 3.

Правила 2 и 3 вступают в силу в момент считывания выражения, поэтому:

(list (ratiop 2/2) (complexp #c(1 0))) (NIL NIL)

–  –  –

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

(mapcar #’float ’(1 2/3.5)) (1.0 0.66666667 0.5)

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

(truncate 1.3) 0.2999995 Второе значение является результатом вычитания первого значения из аргумента. (Разница в.00000005 возникает вследствие неизбежной неоднозначности операций с плавающей запятой.) Функции floor, ceiling и round также приводят свои аргументы к целочисленным значениям. С помощью floor, возвращающей наибольшее целое число, меньшее или равное заданному аргументу, а также ceiling, возвращающей наименьшее целое, большее или равное аргументу, мы 156 Глава 9. Числа можем обобщить функцию mirror? (стр. 62) для распознавания палиндромов:

(defun palindrome? (x) (let ((mid (/ (length x) 2))) (equal (subseq x 0 (floor mid)) (reverse (subseq x (ceiling mid)))))) Как и truncate, функции floor и ceiling вторым значением возвращают разницу между аргументом и своим первым значением:

(floor 1.5) 0.5

В действительности, мы могли бы определить truncate таким образом:

(defun our-truncate (n) (if ( n 0) (floor n) (ceiling n)))

Для получения ближайшего к аргументу целого числа существует функция round. В случае когда ее аргумент равноудален от обоих целых чисел, Common Lisp, как и многие другие языки, не округляет его, а возвращает ближайшее четное число:

(mapcar #’round ’(-2.5 -1.5 1.5 2.5)) (-2 -2 2 2) Такой подход позволяет сгладить накопление ошибок округления в ряде приложений. Однако если необходимо округление вверх, можно написать такую функцию самостоятельно.1 Как и остальные функции такого рода, round в качестве второго значения возвращает разницу между исходным и округленным числами.

Функция mod возвращает второе значение аналогичного вызова floor, а функция rem – второе значение вызова truncate. Мы уже использовали функцию mod (стр. 107) для определения делимости двух чисел и для нахождения позиции элемента в кольцевом буфере (стр. 137).

Для действительных чисел существует функция signum, которая возвратит 1, 0 или -1 в зависимости от того, каков знак аргумента: плюс, ноль или минус. Модуль числа можно получить с помощью функции abs. Таким образом, (* (abs x) (signum x)) = x.

(mapcar #’signum ’(-2 -0.0 0.0 0.5 3)) (-1 -0.0 0.0 0 1.0 1) В некоторых реализациях -0.0 может существовать сам по себе, как в примере, приведенном выше. В любом случае это не играет роли, и в вычислениях -0.0 ведет себя в точности как 0.0.

Функция format при округлении не гарантирует даже того, будет ли получено четное или нечетное число. См. стр. 136.

9.3. Сравнение Рациональные дроби и комплексные числа являются структурами, состоящими из двух частей. Получить соответствующие целочисленные компоненты рациональной дроби можно с помощью функций numerator и denominator. (Если аргумент уже является целым числом, то первая функция вернет сам аргумент, а последняя – единицу.) Аналогично функции realpart и imagpart извлекают действительную и мнимую части комплексного числа. (Если аргумент не комплексный, то первая вернет это число, а вторая – ноль.) Функция random принимает целые числа или десятичные дроби. Выражение вида (random n) вернет число, большее или равное нулю и меньшее n, и это значение будет того же типа, что и аргумент.

–  –  –

(list (minusp -0.0) (zerop -0.0)) (NIL T) и соответствует zerop, а не minusp.

Предикаты oddp и evenp применимы лишь к целочисленным аргументам. Первый истинен для нечетных чисел, второй – для четных.

Из всех предикатов, упомянутых в этом разделе, лишь =, /= и zerop применимы к комплексным числам.

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

(list (max 1 2 3 4 5) (min 1 2 3 4 5)) (5 1) Если среди аргументов есть хотя бы одно число с плавающей запятой, то тип возвращаемого значения зависит от используемой реализации.

9.4. Арифметика Сложение и вычитание выполняются с помощью + и -. Обе функции могут работать с любым количеством аргументов, а в случае их отсутствия возвращают 0. Выражение вида (- n) возвращает –n. Выражение вида (- x y z) эквивалентно (- (- x y) z) Кроме того, имеются функции 1+ и 1-, которые возвращают свой аргумент, увеличенный или уменьшенный на 1 соответственно. Имя функции 1- может сбить с толку, потому что (1- x) возвращает x - 1, а не 1 - x.

Макросы incf и decf соответственно увеличивают и уменьшают свой аргумент. Выражение вида (incf x n) имеет такой же эффект, как и (setf x (+ x n)), а (decf x n) – как (setf x (- x n)). В обоих случаях второй аргумент не обязателен и по умолчанию равен 1.

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

Функция деления / требует задания хотя бы одного аргумента.

Вызов (/ n) эквивалентен вызову (/ 1 n):

(/ 3) 1/3

В то время как выражение:

(/ x y z) эквивалентно (/ (/ x y) z)

9.5. Возведение в степень Обратите внимание на сходное поведение – и / в этом отношении.

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

(/ 365 12) 365/12 Если вы будете пытаться вычислять, к примеру, усредненную длину месяца, то вам может показаться, что toplevel над вами издевается. В подобных случаях, когда вам действительно нужна десятичная дробь, пользуйтесь функцией float:

(float 365/12) 30.416666

–  –  –

вычисляют соответственно синус, косинус и тангенс заданного в радианах угла:

(let ((x (/ pi 4))) (list (sin x) (cos x) (tan x))) (0.7071067811865475d0 0.707167811865476d0 1.0d0) Все вышеперечисленные функции умеют работать с комплексными аргументами.

Обратные преобразования выполняются функциями asin, acos, atan.

Для аргументов, находящихся на отрезке от -1 до 1, asin и acos возвращают действительные значения.

Гиперболические синус, косинус и тангенс вычисляются через sinh, cosh и tanh соответственно. Для них также определены обратные преобразования: asinh, acosh, atanh.

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

Константы most-positive-fixnum и most-negative-fixnum задают максимальные величины, которые могут обрабатываться реализацией без использования типа bignum.

Во многих реализациях они имеют следующие значения:

(values most-positive-fixnum most-negative-fixnum)

-536870912

Принадлежность к определенному типу проверяется с помощью предиката typep:

(typep 1 ’fixnum) T (typep (1+ most-positive-fixnum) ’bignum) T В каждой реализации имеются свои ограничения на размер чисел с плавающей запятой. Common Lisp предоставляет четыре типа чисел с плавающей запятой: short-float, single-float, double-float и long-float. Реализации стандарта не обязаны использовать различные представления для разных типов (и лишь некоторые это делают).

Суть типа short-float в том, что он занимает одно машинное слово. Типы single-float и double-float занимают столько места, сколько нужно,

9.8. Пример: трассировка лучей чтобы удовлетворять установленным требованиям к числам одинарной и двойной точности соответственно. Числа типа long-float могут быть большими настолько, насколько это требуется. Но в конкретной реализации все 4 типа могут иметь одинаковое внутреннее представление.

Тип числа можно задать принудительно, используя соответствующие буквы: s, f, d или l, а также e для экспоненциальной формы. (Заглавные буквы также допускаются, и этим стоит воспользоваться для представления типа long-float, потому что малую l легко спутать с цифрой 1.) Наибольшее представление числа 1.0 можно задать как 1L0.

Глобальные ограничения на размер чисел разных типов задаются шестнадцатью константами. Их имена выглядят как m-s-f, где m может быть most или least, s соответствует positive или negative, а f – один из четырех типов чисел с плавающей запятой.°

Превышение заданных ограничений приводит к возникновению ошибки в Common Lisp:

(* most-positive-long-float 10) Error: floating-point-overflow.

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

Для моделирования трехмерного изображения нам необходимо определить как минимум четыре предмета: наблюдателя, один или более источников света, набор объектов моделируемого мира и плоскость рисунка (image plane), которая служит окном в этот мир. Наша задача – сгенерировать изображение, соответствующее проекции мира на область плоскости рисунка.

Что же делает необычным метод трассировки лучей? Попиксельная отрисовка всей картины и симуляция прохождения луча через виртуальный мир. Такой подход позволяет достичь реалистичных оптических эффектов: прозрачности, отражений, затенений; он позволяет задавать отрисовываемый мир как набор геометрических тел, вместо того чтобы строить их из полигонов. Отсюда вытекает относительная прямолинейность в реализации метода.

На рис. 9.2 показаны основные математические утилиты, которыми мы будем пользоваться. Первая, sq, вычисляет квадрат аргумента. Вторая, mag, возвращает длину вектора по трем его компонентам x, y и z. Эта функция используется в следующих двух.

unit-vector возвращает три значения, соответствующие координатам единичного вектора, имеющего то же направление, что и заданный:

162 Глава 9. Числа (multiple-value-call #’mag (unit-vector 23 12 47)) 1.0 Кроме того, mag используется в функции distance, вычисляющей расстояние между двумя точками в трехмерном пространстве. (Определение структуры point содержит параметр :conc-name, равный nil. Это значит, что функции доступа к соответствующим полям структуры будут иметь такие же имена, как и сами поля, например x вместо point-x.)

–  –  –

Рис. 9.2. Математические утилиты Наконец, функция minroot принимает три действительных числа a, b и c и возвращает наименьшее x, для которого ax2 + bx + c=0. В случае когда

a не равно нулю, корни этого уравнения могут быть получены по хорошо известной формуле:

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

9.8. Пример: трассировка лучей

–  –  –

Чтобы добавить объект, необходимо поместить его в список *world* (изначально nil). Чтобы он был видимым, его z-координата должна быть отрицательной. Рисунок 9.4 демонстрирует прохождение лучей через поверхность рисунка и их падение на сферу.

–  –  –

Рис. 9.4. Трассировка лучей Функция tracer записывает изображение в файл по заданному пути.

Запись производится в обычном ASCII-формате, называемом PGM. По умолчанию размер изображения – 100100. Заголовок PGM-файла начинается с тега P2, за которым следуют числа, соответствующие ширине (100) и высоте (100) в пикселах, причем максимально возможное значение равно 255. Оставшаяся часть файла содержит 10 000 целых чисел от 0 (черный) до 255 (белый), которые вместе дают 100 горизонтальных полос по 100 пикселов в каждой.

Разрешение изображения может быть изменено с помощью res. Если res равно, например, 2, то изображение будет содержать 200200 пикселов.

По умолчанию изображение – это квадрат 100100 на плоскости рисунка. Каждый пиксел представляет собой количество света, проходящего через данную точку к глазу наблюдателя. Для нахождения этой величины tracer вызывает color-at. Эта функция ищет вектор от глаза наблюдателя к заданной точке, затем вызывает sendray, направляя луч вдоль этого вектора через моделируемый мир. В результате sendray получает некоторое число от 0 до 1, которое затем масштабируется на отрезок от 0 до 255.

Для определения интенсивности света sendray ищет объект, от которого он был отражен. Для этого вызывается функция first-hit, которая находит среди всех объектов в *world* тот, на который луч падает первым, или же убеждается в том, что луч не падает ни на один объект. В последнем случае возвращается цвет фона, которым мы условились считать 0 (черный). Если луч падает на один из объектов, то нам необходимо найти долю света, отраженного от него. Согласно закону Ламберта, интенсивность света, отраженного точкой поверхности, пропорциональна скалярному произведению единичного вектора N, направленного из этой

9.8. Пример: трассировка лучей точки вдоль нормали к поверхности (вектор, длина которого равна 1, направленный перпендикулярно поверхности в заданной точке), и единичного вектора L, направленного вдоль луча к источнику света:

i = NL Если источник света находится в этой точке, N и L будут иметь одинаковое направление, и их скалярное произведение будет иметь максимальное значение, равное 1. Если поверхность находится под углом 90° к источнику света, то N и L будут перпендикулярны и их произведение будет равно 0. Если источник света находится за поверхностью, то произведение будет отрицательным.

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

В функции sendray это число умножается на цвет поверхности (темная поверхность отражает меньше света), чтобы определить интенсивность в заданной точке. Упростим задачу, ограничившись лишь объектами типа сферы. Код, реализующий поддержку сфер, приведен на рис. 9.5.

Структура sphere включает surface, поэтому sphere будет иметь параметр color, так же как и параметры center и radius. Вызов defsphere добавляет в наш мир новую сферу.

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

Как найти пересечение луча со сферой? Луч представляется точкой p = (x0, y0, z0) и единичным вектором v = (xr, yr, zr). Любая точка луча может быть выражена как p + nv для некоторого n или, что то же самое, (x0+nxr, y0+nyr, z0+nzr). Когда луч падает на сферу, расстояние до центра (xc, yc, zc) равно радиусу сферы r.

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

–  –  –

Для нахождения точки пересечения нам необходимо решить это квадратное уравнение. Оно может иметь ноль, один или два вещественных корня. Отсутствие решений означает, что луч проходит мимо сферы;

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

9.8. Пример: трассировка лучей соответствовать меньшему n. Для нахождения корня используется minroot. Если корень существует, sphere-intersect возвратит соответствующую ему точку (x0 + nxr, y0 + nyr, z0 + nzr).

Две другие функции на рис. 9.5, normal и sphere-normal, связаны между собой аналогично intersect и sphere-intersect. Поиск нормали для сферы крайне прост – это всего лишь вектор, направленный из точки на поверхности к ее центру.

На рис. 9.6 показано, как будет выполняться генерация изображения;

ray-trace создает 38 сфер (не все они будут видимыми), а затем генерирует изображение, которое записывается в файл "spheres.pgm". Итог работы программы с параметром res = 10 представлен на рис. 9.7.

–  –  –

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

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

Кроме того, реальная программа-трассировщик должна быть тщательно оптимизирована. Наша программа имеет сжатые размеры и не оптимизирована ни как Лисп-программа, ни как трассировщик лучей. Добавление к программе одних только деклараций inline и деклараций типов (см. раздел 13.3) может обеспечить более чем двукратный прирост производительности.

Итоги главы

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

2. Числовые значения могут быть преобразованы или упрощены, а их компоненты могут быть извлечены.

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

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

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

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

Упражнения

–  –  –

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

4. Определите функцию, принимающую 8 действительных чисел, представляющих два отрезка в двумерном пространстве. Функция возвращает nil, если отрезки не пересекаются, в противном случае возвращаются два значения: x- и y-координаты точки их пересечения.

Пусть функция f имеет один действительный аргумент, а min и max – ненулевые действительные числа разных знаков; f имеет корень (возвращает ноль) для некоторого числа i, такого что min i max. Определите функцию, принимающую четыре аргумента f, min, max и epsilon и возвращающую приближенное значение i с точностью до epsilon.

5. Метод Горнера позволяет эффективно решать полиномы. Чтобы найти ax3+bx2+cx+d, нужно вычислить x(x(ax+b)+c)+d. Определите функцию, принимающую один или несколько аргументов – значение x и следующие за ним n действительных чисел, представляющих полином степени (n–1). Функция должна вычислять значение полинома для заданного x методом Горнера.

6. Сколько бит использовала бы ваша реализация для представления fixnum?

7. Сколько различных типов чисел с плавающей запятой представлено в вашей реализации?

Макросы Глава 10.

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

10.1. Eval Очевидно, что создавать выражения нужно путем вызова list. Однако возникает другой вопрос: как объяснить Лиспу, что созданный список – это код? Для этого существует функция eval, вычисляющая заданное выражение и возвращающая его значение:

(eval ’(+ 1 2 3)) (eval ’(format t "Hello")) Hello NIL Да, именно об eval мы говорили все это время. Следующая функция реализует некое подобие toplevel:

(defun our-toplevel () (do () (nil) (format t "~% ") (format (eval (read))))) По этой причине toplevel также называют read-eval-print loop (цикл чтение-вычисление-печать).

Вызов eval – один из способов перешагнуть границу между списками и кодом.

Однако это не лучший путь:

10.1. Eval

–  –  –

NIL NIL Поскольку coerce и compile могут принимать списки в качестве аргументов, программа может создавать новые функции на лету. Однако этот метод также нельзя назвать лучшим, так как он имеет те же недостатки, что и eval.

Причина неэффективности eval, coerce и compile в том, что они пересекают границу между списками и кодом и создают функции в момент выполнения (run-time). Пересечение границы – дорогое удовольствие.

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

10.2. Макросы Наиболее распространенный способ писать программы, которые будут писать программы, – это создание макросов. Макросы – это операторы, которые реализуются через трансформацию. Определяя макрос, вы указываете, как его вызов должен быть преобразован. Само преобразование автоматически выполняется компилятором и называется раскрытием макроса (macro-expansion). Код, полученный в результате раскрытия макроса, естественным образом становится частью программы, как если бы он был набран вами.

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

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

(defmacro nil! (x) (list ’setf x nil)) Данный макрос создает новый оператор nil!, который принимает один аргумент. Вызов вида (nil! a) будет преобразован в (setf a nil) и лишь затем скомпилирован или вычислен. Таким образом, если набрать (nil! x) в toplevel, (nil! x) NIL x NIL это в точности эквивалентно набору выражения (setf x nil).

Чтобы протестировать функцию, ее вызывают. Чтобы протестировать макрос, его раскрывают.

Функция macroexpand–1 принимает вызов макроса и возвращает результат его раскрытия:

10.3. Обратная кавычка (macroexpand–1 ’(nil! x)) (SETF X NIL) T Макрос может раскрываться в другой макровызов. Когда компилятор (или toplevel) встречает такой макровызов, он раскрывает этот макрос до тех пор, пока в коде не останется ни одного другого макровызова.

Секрет понимания макросов в осознании их реализации. Они – не более чем функции, преобразующие выражения. К примеру, если вы передадите выражение вида (nil! a) в следующую функцию:

(lambda (expr) (apply #’(lambda (x) (list ’setf x nil)) (cdr expr))) то она вернет (setf a nil). Применяя defmacro, вы выполняете похожую работу. Все, что делает macroexpand–1, когда встречает выражение, car которого соответствует имени одного из макросов, – это перенаправляет это выражение в соответствующую функцию.

10.3. Обратная кавычка Макрос чтения обратная кавычка (backquote) позволяет строить списки на основе специальных шаблонов. Она широко используется при определении макросов. Обычной кавычке на клавиатуре соответствует закрывающая прямая кавычка (апостроф), а обратной – открывающая.

Ее называют обратной из-за ее наклона влево.

Обратная кавычка, использованная сама по себе, эквивалентна обычной кавычке:

‘(a b c) (A B C) Как и обычная кавычка, обратная кавычка предотвращает вычисление выражения.

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

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

(setf a 1 b 2) ‘(a is,a and b is,b) (A IS 1 AND B IS 2) Используя обратную кавычку вместо вызова list, мы можем записывать определения макросов, которые будут выглядеть так же, как результат их раскрытия. К примеру, оператор nil! может быть определен следующим образом:

174 Глава 10. Макросы

–  –  –

10.4. Пример: быстрая сортировка На рис. 10.1 приведен пример1 функции, полностью построенной на макросах, – функции, выполняющей сортировку векторов с помощью алгоритма быстрой сортировки (quicksort).°

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

1. Один из элементов принимается в качестве опорного. Многие реализации выбирают элемент из середины вектора.

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

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

Код на рис. 10.1 содержит слегка исправленный код. Ошибка найдена Джедом Кросби. – Прим. перев.

10.5. Проектирование макросов

–  –  –

Рис. 10.1. Быстрая сортировка С каждым последующим вызовом сортируемый список становится короче, и так до тех пор, пока весь список не будет отсортирован.

Реализация этого алгоритма (рис. 10.1) требует указания вектора и двух чисел, задающих диапазон сортировки. Элемент, находящийся в середине этого диапазона, выбирается в качестве опорного элемента (p). Затем по мере продвижения вдоль вектора к окончанию диапазона производятся перестановки его элементов, которые либо слишком большие, чтобы находиться слева, либо слишком малые, чтобы находиться справа. (Перестановка двух элементов осуществляется с помощью rotatef.) Далее эта процедура повторяется рекурсивно для каждой полученной части, содержащей более одного элемента.

Помимо макроса while, определенного в предыдущем разделе, в quicksort (рис. 10.1) задействованы встроенные макросы when, incf, decf и rotatef.

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

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

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

В качестве примера мы создадим макрос ntimes, вычисляющий свое тело n раз:

(ntimes 10 (princ ".")) 176 Глава 10. Макросы..........

NIL

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

(defmacro ntimes (n &rest body) ; wrong ‘(do ((x 0 (+ x 1))) ((= x,n)),@body)) На первый взгляд такое определение кажется вполне корректным. Для приведенного выше примера оно будет работать нормально, однако на самом деле в нем есть две проблемы.

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

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

(let ((x 10)) (ntimes 5 (setf x (+ x 1))) x) Мы предполагали, что значение x будет увеличено в пять раз и в итоге будет равно 15. Но поскольку переменная x используется еще и внутри макроса как итерируемая переменная в do, setf будет увеличивать значение этой переменной, а не той, что предполагалось. Раскрыв этот макрос, мы увидим, что предыдущее выражение выглядит следующим образом:

(let ((x 10)) (do ((x 0 (+ x 1))) (( x 5)) (setf x (+ x 1))) x) Наиболее общим решением будет не использовать обычные символы в тех местах, где они могут быть захвачены. Вместо этого можно использовать gensym (см. раздел 8.4). В связи с тем что read интернирует каждый встреченный символ, gensym никоим образом не будет равен (с точки зрения eql) любому другому символу, встречающемуся в тексте программы. Переписав наше определение ntimes с использованием gensym вместо x, мы сможем избавиться от вышеописанной проблемы:

(defmacro ntimes (n &rest body) ; wrong (let ((g (gensym)))

10.5. Проектирование макросов

–  –  –

10.6. Обобщенные ссылки

Поскольку макровызов раскрывается непосредственно в том месте кода, где он был вызван, любой макровызов, раскрывающийся в выражение, которое может быть первым аргументом setf, сам может быть первым аргументом setf. Определим, например, синоним car:

(defmacro cah (lst) ‘(car,lst))

Так как выражение с car может быть первым аргументом setf, то и аналогичный вызов с cah также может иметь место:

(let ((x (list ’a ’b ’c))) (setf (cah x) 44) x) (44 B C) Написание макроса, который самостоятельно раскрывается в вызов setf, – менее тривиальная задача, несмотря на кажущуюся простоту.

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

(defmacro incf (x &optional (y 1)) ; wrong ‘(setf,x (+,x,y)))

Но такое определение не работает. Следующие два выражения не эквивалентны:

(setf (car (push 1 lst)) (1+ (car (push 1 lst)))) (incf (car (push 1 lst))) Если lst изначально равно nil, то второе выражение установит его в (2), тогда как первое выражение установит его в (1 2).

Common Lisp предоставляет define-modify-macro как способ написания ограниченного класса макросов поверх setf. Он принимает три аргумента: имя макроса, дополнительные аргументы (место, подлежащее изменению, является неявным первым аргументом) и имя функции, которая

10.7. Пример: макросы-утилиты вернет новое значение заданного места. Теперь мы можем определить

incf так:

(define-modify-macro our-incf (&optional (y 1)) +)

А вот версия push для добавления элемента в конец списка:

(define-modify-macro append1f (val) (lambda (lst val) (append lst (list val))))

Последний макрос работает следующим образом:

(let ((lst ’(a b c))) (append1f lst ’d) lst) (A B C D) Между прочим, макросы push и pop не могут быть определены через define-modify-macro, так как в push изменяемое место не является первым аргументом, а в случае pop его возвращаемое значение не является измененным объектом.

–  –  –

Рис. 10.2. Утилиты на макросах Макрос использует дополнительную переменную для хранения верхней границы цикла. В противном случае выражение 8 вычислялось бы каждый раз, а для более сложных случаев это нежелательно. Дополнительная переменная создается с помощью gensym, что позволяет предотвратить непреднамеренный захват переменной.

Второй макрос на рис. 10.2, in, возвращает истину, если его первый аргумент равен (с точки зрения eql) хотя бы одному из остальных своих аргументов.

Без этого макроса вместо выражения:

(in (car expr) ’+ ’- ’*) нам пришлось бы писать:

(let ((op (car expr))) (or (eql op ’+) (eql op ’-) (eql op ’*)))

10.7. Пример: макросы-утилиты Разумеется, первое выражение раскрывается в подобное этому, за исключением того, что вместо переменной op используется gensym.

Следующий пример, random-choice, случайным образом выбирает один из своих аргументов и вычисляет его. С задачей случайного выбора мы уже сталкивались (стр. 89). Макрос random-choice реализует его обобщенный механизм.

Вызов типа:

(random-choice (turn-left) (turn-right)) раскрывается в:

(case (random 2) (0 (turn-left)) (1 (turn-right))) Следующий макрос, with-gensyms, предназначен в первую очередь для использования внутри других макросов. Нет ничего необычного в его применении в макросах, которые вызывают gensym для нескольких переменных. С его помощью вместо:

(let ((x (gensym)) (y (gensym)) (z (gensym)))...) мы можем написать:

(with-gensyms (x y z)...) Пока что ни один из приведенных выше макросов не мог быть написан в виде функции. Из этого следует правило: макрос должен создаваться лишь тогда, когда вы не можете написать аналогичную функцию. Однако из этого правила бывают исключения. Например, иногда вы можете определить оператор как макрос, чтобы иметь возможность выполнять какую-либо работу на этапе компиляции. Примером может служить макрос avg, вычисляющий среднее значение своих аргументов:

(avg 2 4 8) 14/3

Аналогичная функция будет иметь вид:

(defun avg (&rest args) (/ (apply #’+ args) (length args))) но эта функция вынуждена считать количество аргументов в процессе исполнения. Если нам вдруг захочется избежать этого, почему бы не вычислять длину списка аргументов (вызовом length) на этапе компиляции?

Последний макрос на рис. 10.2, aif, приводится в качестве примера преднамеренного захвата переменной. Он позволяет ссылаться через переменную it на значение, возвращаемое тестовым аргументом if.

Благодаря этому вместо:

182 Глава 10. Макросы (let ((val (calculate-something))) (if val (1+ val) 0)) мы можем написать:

(aif (calculate-something) (1+ it) 0) Разумное использование захвата переменных в макросах может оказать полезную услугу. Сам Common Lisp прибегает к такой возможности в некоторых случаях, например в next-method-p и call-next-method.

Разобранные в этом разделе макросы демонстрируют смысл фразы «программы, которые пишут программы». Единожды определенный for позволяет избежать написания множества однотипных выражений с do.

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

Если у вас все еще остались какие-либо сомнения, представьте ситуацию, когда встроенные макросы недоступны и код, в который они раскрывались бы, необходимо набирать вручную. Теперь подойдите к вопросу с другой стороны. Представьте, что вы пишете программу, содержащую множество сходных частей. Задайте себе вопрос: «А не пишу ли я результаты раскрытия макросов?» Если так, то макросы, генерирующие этот код, – вот то, что вам нужно писать в действительности.

10.8. На Лиспе Теперь, когда мы узнали, что такое макросы, мы видим, что даже большая часть самого Лиспа, чем мы предполагали, написана на самом Лиспе с помощью макросов. Большинство операторов в Common Lisp, которые не являются функциями, – это макросы, и все они написаны на Лиспе. И лишь 25 встроенных операторов являются специальными.

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

Макросы являются одним из ключевых ингредиентов гибкости Лиспа.

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

Итоги главы

1. Вызов eval – один из способов использовать списки как код, но он неэффективен и не нужен.

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

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

4. Разработчик макроса должен помнить о захвате переменных и повторных вычислениях. Чтобы протестировать макрос, полезно изучить результат его раскрытия, напечатанный с помощью pprint.

5. Проблема повторных вычислений возникает в большинстве макросов, раскрывающихся в вызовы setf.

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

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

–  –  –

Объектная система Common Lisp (Common Lisp Object System, CLOS) представляет собой набор операторов для объектно-ориентированного программирования. Всех их объединяет историческое прошлое.° С технической точки зрения они ничем не отличаются от остального Common Lisp: defmethod – такая же неотъемлемая часть языка, как и defun.

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

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

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

186 Глава 11. CLOS

–  –  –

Рис. 11.1. Представление площадей через структуры и функции С помощью CLOS мы можем переписать код в другом ключе, как показано на рис. 11.2. В объектно-ориентированной модели программа разбивается на несколько методов, каждый из которых предназначен для соответствующего типа аргумента. Два метода, показанные на рис. 11.2, неявно определяют функцию area, которая будет вести себя так же, как аналогичная функция на рис. 11.1. При вызове area Лисп вызывает определенный метод в соответствии с типом аргумента.

Помимо разбиения функций на методы объектно-ориентированное программирование предполагает наследование – как для слотов, так и для методов. Пустой список, переданный вторым аргументом в двух вызовах defclass (рис. 11.2), – это список суперклассов (родительских классов).

Определим теперь новый класс окрашенных объектов, а затем класс окрашенных кругов, имеющий два суперкласса: circle и colored:

(defclass colored () (color)) (defclass colored-circle (circle colored) ())

Создавая экземпляры класса colored-circle, мы увидим два вида наследования:

1. Экземпляры colored-circle будут иметь два слота: radius, наследуемый из класса circle, и color – из класса colored.

2. Так как для класса colored-circle свой метод не определен, вызов area для данного класса будет использовать метод, определенный для класса circle.

11.2. Классы и экземпляры

–  –  –

Рис. 11.2. Представление площадей через классы и методы С практической точки зрения под объектно-ориентированным программированием подразумевается способ организации программы в терминах методов, классов, экземпляров и наследования. Зачем может понадобиться подобная организация? Одно из заявлений объектно-ориентированного подхода заключается в том, что он упрощает изменения в программах. Если мы хотим изменить способ отображения объектов класса ob, нам достаточно внести изменения лишь в один метод display этого класса. Если нам нужен новый класс объектов, похожих на ob, но слегка отличающихся от них, мы можем создать подкласс ob, для которого зададим необходимые нам свойства, а все остальное унаследуется от родительского класса. А если мы просто хотим получить один объект ob, который ведет себя отлично от остальных, мы можем создать нового потомка ob и напрямую поменять его свойства. Для внесения изменений в грамотно написанную программу нам необязательно даже смотреть на остальной код.°

–  –  –

Чтобы создать экземпляр этого класса, вместо вызова специфичной функции мы воспользуемся общей для всех классов функцией make-instance, вызванной с именем класса в качестве первого аргумента:

(setf c (make-instance ’circle)) #Circle #XC27496

Доступ к значению слота можно осуществить с помощью slot-value. Новое значение можно установить с помощью setf:

(setf (slot-value c ’radius) 1) Как и для структур, значения неинициализированных слотов не определены.

11.3. Свойства слотов Третий аргумент defclass должен содержать список определений слотов.

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

Параметр :accessor неявно создает функцию, обеспечивающую доступ к слоту, убирая необходимость использовать slot-value.

Если мы обновим наше определение класса circle следующим образом:

(defclass circle () ((radius :accessor circle-radius) (center :accessor circle-center))) то сможем ссылаться на слоты с помощью функций circle-radius и circle-center соответственно:

(setf c (make-instance ’circle)) #Circle #XC5C726 (setf (circle-radius c) 1) (circle-radius c) Если вместо :accessor использовать параметры :writer или :reader, можно задать по отдельности либо функцию установки значения слота, либо функцию чтения.

Исходное значение слота определяется параметром :initform.

Чтобы можно было инициализировать слот в вызове make-instance по ключу, нужно задать имя соответствующего ключа как :initarg этого слота.1 Определение класса, обладающего перечисленными свойствами, будет выглядеть следующим образом:

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

11.3. Свойства слотов

–  –  –

Если задано необязательное свойство :documentation, то оно должно содержать строку описания данного слота. Задавая :type, вы обязуетесь обеспечить то, что слот будет содержать лишь значения заданного типа.

Декларации типов будут рассмотрены в разделе 13.3.

11.4. Суперклассы Второй аргумент defclass является списком суперклассов. От них класс наследует набор слотов. Так, если мы определим класс screen-circle как подкласс circle и graphic:

(defclass graphic () ((color :accessor graphic-color :initarg :color) (visible :accessor graphic-visible :initarg :visible :initform t))) (defclass screen-circle (circle graphic) ()) то экземпляры screen-circle будут иметь четыре слота, по два от каждого класса-родителя. И при этом не нужно создавать какие-либо новые слоты как его собственные – подкласс screen-circle создается лишь для объединения возможностей двух классов circle и graphic.

Параметры слотов (:accessor, :initarg и другие) наследуются вместе с самими слотами и работают так же, как если бы они использовались для экземпляров circle или graphic:

(graphic-color (make-instance ’screen-circle :color ’red :radius 3)) RED

Тем не менее в определении класса можно указывать некоторые параметры для наследуемых слотов, например :initform:

(defclass screen-circle (circle graphic) ((color :initform ’purple)))

Теперь экземпляры screen-circle будут пурпурными по умолчанию:

(graphic-color (make-instance ’screen-color)) PURPLE

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

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

Вот пример более сложной иерархии классов:

(defclass sculpture () (height width depth)) (defclass statue (sculpture) (subject)) (defclas metalwork () (metal-type)) (defclass casting (metalwork) ()) (defclass cast-statue (statue casting) ()) Граф, представляющий класс cast-statue и его суперклассы, изображен на рис. 11.3.

–  –  –

Рис. 11.3. Иерархия классов Чтобы построить такой граф, необходимо начать с узла, соответствующего классу, и двигаться снизу-вверх. Ребра, направленные вверх, связывают класс с прямыми суперклассами, которые располагаются слеванаправо в соответствии с порядком соответствующих вызовов defclass.

Эта процедура повторяется до тех пор, пока для каждого класса будет существовать лишь один суперкласс – standard-object. Это справедливо для классов, в определении которых второй аргумент был (). Узел, соответствующий каждому такому классу, связан с узлом standard-object, а он в свою очередь – с классом t. Проделав подобные операции, мы получим граф, изображенный на рис. 11.3.

Теперь мы можем составить список предшествования:

1. Начинаем с низа графа.

2. Движемся вверх, всегда выбирая левое из ранее непройденных ребер.

192 Глава 11. CLOS

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

4. Завершаем процедуру по достижении t. Порядок, в котором каждый узел был впервые посещен, определяет список предшествования.

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

Стрелки на рис. 11.3 показывают направление обхода. Список предшествования нашей иерархии будет следующим: cast-statue, statue, sculpture, casting, metalwork, standard-object, t. Иногда положение класса в таком списке называют его специфичностью. Классы расположены в нем по убыванию специфичности.

По списку предшествования можно определить, какой метод необходимо применить при вызове обобщенной функции. Этот процесс рассматривается в следующем разделе. Порядок следования, связанный с выбором наследуемого слота, нами пока не рассматривался. Соответствующие правила его определения можно найти на стр. 428.°

11.6. Обобщенные функции Обобщенной функцией называют функцию, построенную из одного или нескольких методов. Методы определяются через оператор defmethod, который напоминает defun:

(defmethod combine (x y) (list x y))

На данный момент combine имеет один метод, и ее вызов построит список из двух аргументов:

(combine ’a ’b) (A B) Пока что мы не сделали ничего, с чем не справилась бы обычная функция. Однако отличия станут заметны при добавлении еще одного метода.

Для начала создадим несколько классов, с которыми будут работать наши методы:

(defclass stuff () ((name :accessor name :initarg :name))) (defclass ice-cream (stuff) ()) (defclass topping (stuff) ()) Мы определили три класса: stuff, имеющий слот name, а также ice-cream и topping, являющиеся подклассами stuff.

Теперь создадим второй метод для combine:

(defmethod combine ((ic ice-cream) (top topping)) (format nil "~A ice-cream with ~A topping."

11.6. Обобщенные функции (name ic) (name top))) В этом вызове defmethod параметры конкретизированы: каждый из них появляется в списке с именем класса. Конкретизации метода указывают на типы аргументов, к которым он применим. Приведенный метод может использоваться только с определенными аргументами: первым аргументом должен быть экземпляр ice-cream, а вторым – экземпляр topping.

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

Это значит, например, что для аргументов, представляющих классы ice-cream и topping соответственно, будет применен последний определенный нами метод:

(combine (make-instance ’ice-cream :name ’fig) (make-instance ’topping :name ’treacle)) "FIG ice-cream with TREACLE topping."

Для любых других аргументов будет применен наш первый метод:

(combine 23 ’skiddoo) (23 SKIDDOO) Ни один из аргументов этого метода не был конкретизирован, поэтому он имеет наименьший приоритет и будет вызван лишь тогда, когда ни один другой метод не подойдет. Такие методы служат своего рода запасным вариантом, подобно ключу otherwise в case-выражении.

Любая комбинация параметров метода может быть конкретизирована.

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

(defmethod combine ((ic ice-cream) x) (format nil "~A ice-cream with ~A."

(name ic) x)) Если мы теперь вызовем combine с экземплярами ice-cream и topping, из двух последних методов будет выбран наиболее специфичный:

(combine (make-instance ’ice-cream :name ’grape) (make-instance ’topping :name ’marshmallow)) "GRAPE ice-cream with MARSHMALLOW topping."

Однако если второй аргумент не принадлежит классу topping, будет вызван только что определенный метод:

(combine (make-instance ’ice-cream :name ’clam) ’reluctance) "CLAM ice-cream with RELUCTANCE."

Аргументы обобщенной функции определяют набор применимых (applicable) методов. Метод считается применимым, если аргументы соответствуют спецификациям, налагаемым данным методом.

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

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

экземпляр ice-cream принадлежит классам ice-cream, затем stuff, standard-object и, наконец, t.

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

Вот пример метода combine с числовыми спецификаторами:

(defmethod combine ((x number) (y number)) (+ x y)) Кроме того, методы могут использовать отдельные объекты, сверяемые с помощью eql:

(defmethod combine ((x (eql ’powder)) (y (eql ’spark))) ’boom) Спецификаторы индивидуальных объектов имеют больший приоритет, нежели спецификаторы классов.

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

Все приведенные ниже пары конгруэнтны:

(x) (a) (x &optional y) (a &optional b) (x y &rest z) (a b &key c) (x y &key z) (a b &key c d) а следующие пары – нет:

(x) (a b) (x &optional y) (a &optional b c) (x &optional y) (a &rest b) (x &key x y) (a) Мы не сможем дойти до конца аргументов и по-прежнему иметь ничью, потому что тогда два метода будут подходить точно под одно и то же описание аргументов. Это невозможно, так как второе определение метода в этом случае просто затрет первое.

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

(defmethod combine ((x (eql ’powder)) (y (eql ’spark))) ’kaboom) мы тем самым переопределим поведение combine для аргументов powder и spark.

11.7. Вспомогательные методы Методы могут дополняться вспомогательными методами, включая before- (перед), after- (после) и around-методы (вокруг). Before-методы позволяют нам сказать: «Прежде чем приступить к выполнению, сделайте это». Они вызываются в порядке убывания специфичности, предваряя вызов основного метода. After-методы позволяют сказать: «P.S. А сделайте заодно и это». Они вызываются после выполнения основного метода в порядке увеличения специфичности. То, что выполняется между ними, ранее называлось нами просто методом, но более точно это – первичный метод. В результате вызова возвращается именно его значение, даже если после него были вызваны after-методы.

Before- и after-методы позволяют добавлять новое поведение к вызову первичного метода. Around-методы позволяют выполнять то же самое, но более радикальным образом. Если задан around-метод, он будет вызван вместо первичного. Впрочем, по своему усмотрению он может вызвать первичный метод самостоятельно (с помощью функции call-nextmethod, которая предназначена именно для этой цели).

Этот механизм называется стандартной комбинацией методов. Согласно ему вызов обобщенной функции включает:

1. Вызов наиболее специфичного around-метода, если задан хотя бы один из них.

2. В противном случае по порядку:

(a) Все before-методы в порядке убывания специфичности.

(b) Наиболее специфичный первичный метод.

(c) Все after-методы в порядке возрастания специфичности.

Возвращаемым значением считается значение around-метода (в случае 1) или значение наиболее специфичного первичного метода (в случае 2).

Вспомогательные методы задаются указанием ключа-квалификатора (qualifier) после имени метода в определении defmethod.

Если мы определим первичный метод speak для класса speaker следующим образом:

(defclass speaker () ())

–  –  –

(defmethod speak :before ((i intellectual) string) (princ "Perhaps ")) (defmethod speak :after ((i intellectual) string) (princ " in some sense")) мы можем создать подкласс говорунов, всегда добавляющих в конец и в начало исходной фразы несколько слов:

(speak (make-instance ’intellectual) "I’m hungry") Perhaps I’m hungry in some sense NIL

Как было упомянуто выше, вызываются все before- и after-методы. Если мы теперь определим before- и after-методы для суперкласса speaker:

(defmethod speak :before ((s speaker) string) (princ "I think ")) то они будут вызываться из середины нашего «сэндвича»:

(speak (make-instance ’intellectual) "I’m hungry") Perhaps I think I’m hungry in some sense NIL Независимо от того, вызываются ли before- и after-методы, при вызове обобщенной функции всегда возвращается значение первичного метода. В нашем случае format возвращает nil.

Это утверждение не распространяется на around-методы. Они вызываются сами по себе, а все остальные методы вызываются, лишь если им позволит around-метод. Around- или первичный методы могут вызывать следующий метод с помощью call-next-method. Перед этим уместно проверить наличие такого метода с помощью next-method-p.

С помощью around-методов вы можете определить другой, более предупредительный подкласс speaker:

(defclass courtier (speaker) ())

11.8. Комбинация методов (defmethod speak :around ((c courtier) string) (format t "Does the King believe that ~A? " string) (if (eql (read) ’yes) (if (next-method-p) (call-next-method)) (format t "Indeed, it is a preposterous idea.~%")) ’bow) Когда первым аргументом speak является экземпляр класса courtier (придворный), языком придворного управляет around-метод:

(speak (make-instance ’courtier) "kings will last") Does the King believe that kings will last? yes I think kings will last BOW (speak (make-instance ’courtier) "the world is round") Does the King believe that the world is round? no Indeed, it is a preposterous idea.

BOW Еще раз обратите внимание, что, в отличие от before- и after-методов, значением вызова обобщенной функции является возвращаемое значение around-метода.

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

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

Если мы определим обобщенную функцию price, комбинирующую значения с помощью функции +, и при этом для price не существует применимых around-методов, то она будет вести себя, как если бы она была определена следующим образом:

(defun price (&rest args) (+ (apply наиболее специфичный первичный метод args).

.

.

(apply наименее специфичный первичный метод args))) Если существуют применимые around-методы, то они вызываются в порядке очередности, как в стандартной комбинации. В операторной комбинации around-метод по-прежнему может использовать call-next-method, но уже не может вызывать первичные методы.

198 Глава 11. CLOS Используемый способ комбинации методов может быть задан в момент явного создания обобщенной функции через defgeneric:

(defgeneric price (x) (:method-combination +)) Теперь метод price будет использовать + для комбинации методов; второй аргумент defmethod-определения должен содержать +. Определим некоторые классы с ценами:

(defclass jacket () ()) (defclass trousers () ()) (defclass suit (jacket trousers) ()) (defmethod price + ((jk jacket)) 350) (defmethod price + ((tr trousers)) 200)

Теперь если мы запросим цену костюма (suit), то получим сумму применимых методов price:

(price (make-instance ’suit))

Параметр :method-combination, передаваемый вторым аргументом defgeneric (а также вторым аргументом defmethod), может быть одним из следующих символов:

+ and append list max min nconc or progn Также можно использовать символ standard, который явным образом задает использование стандартной комбинации методов.

Определив единожды способ комбинации для обобщенной функции, вы вынуждены использовать этот способ для всех методов, имеющих то же имя. Попытка использовать другие символы (а также :before и :after) приведет к возникновению ошибки. Чтобы изменить способ комбинации price, вам придется удалить саму обобщенную функцию с помощью fmakunbound.

11.9. Инкапсуляция Объектно-ориентированные языки часто дают возможность отличить внутреннее представление объекта от интерфейса, который они представляют внешнему миру. Сокрытие деталей реализации несет в себе двойную выгоду: вы можете модифицировать реализацию объекта, не затрагивая интерфейс доступа к нему извне, а также предотвращаете потенциально опасные изменения объектов. Такое сокрытие деталей иногда называют инкапсуляцией.

Несмотря на то, что инкапсуляцию часто считают свойством объектноориентированного программирования, эти две идеи в действительности существуют независимо друг от друга. Мы уже знакомились с инДве модели капсуляцией в малом масштабе (стр. 120). Функции stamp и reset используют общую переменную counter, однако вызывающий код ничего о ней не знает и не может изменить ее напрямую.

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

Для инкапсуляции слота достаточно экспортировать лишь функции доступа к нему, но не имя самого слота.

Например, мы можем определить класс counter и связать с ним методы increment и clear:

(defpackage "CTR" (:use "COMMON-LISP") (:export "COUNTER" "INCREMENT" "CLEAR"))

–  –  –

(defmethod clear ((c counter)) (setf (slot-value c ’state) 0)) Функции вне пакета ctr будут иметь возможность создавать экземпляры counter и вызывать increment и clear, однако не будут иметь доступа к самому слоту и имени state.

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

(unintern ’state) Теперь сослаться на слот невозможно ни из какого пакета.°

–  –  –

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

Иногда нам приходится сообщать дополнительные аргументы. Например, метод move может принимать аргумент, определяющий дальность перемещения.

Чтобы переместить obj на 10, пошлем ему следующее сообщение:

tell obj move 10

Если записать это другим способом:

(move obj 10) то становится очевидной ограниченность модели передачи сообщений:

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

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

Итоги главы

1. В объектно-ориентированном программировании функция f определяется неявно при определении методов f для разных объектов. Объекты наследуют методы от своих родителей.

2. Определение класса напоминает более многословное определение структуры. Разделяемый слот принадлежит всему классу.

3. Класс наследует слоты своих суперклассов.

4. Предки класса упорядочены в соответствии со списком предшествования. Алгоритм предшествования легче всего понять визуально.

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

6. Первичные методы могут быть дополнены вспомогательными. Стандартная комбинация методов означает использование around-методов, если таковые имеются; в противном случае вызываются сначала before-, потом первичный, затем after-методы.

7. В операторной комбинации методов все первичные методы рассматриваются как аргументы заданного оператора.

Упражнения

8. Инкапсуляция может быть осуществлена с помощью пакетов.

9. Существуют две модели объектно-ориентированного программирования. Модель обобщенных функций является обобщением модели передачи сообщений.

Упражнения



Pages:     | 1 || 3 | 4 |

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

«ОБЪЯВЛЕНИЕ ОБ ЭЛЕКТРОННЫХ ЗАКУПКАХ СПОСОБОМ ЗАПРОС ЦЕНОВЫХ ПРЕДЛОЖЕНИЙ N:125242 1. "Электр желілерін басару жніндегі азастан компаниясы "KEGOC" (Kazakhstan Electricity Grid Operating Company) акционерлік оамы в лице "Северные межсистемные электрические...»

«1 1.Пояснительная записка Рабочая программа по русскому языку разработана на основе: требований федерального компонента государственного стандарта основного общего образования (приказ Минобразования России "Об утверждении федерального компонента государственных стандартов начального...»

«http://fuksi.ru Паспорт безопасности ЕС В соответствии с 91/155/EWG Торговое наименование: Универсальная твердая Положение от: 01.03.06Дата печати: 29.06.06 грунтовкаAрт. Nr.: 3754 1. Описание вещества/препарата, изготовителя Инф...»

«В.Л. Семиков, В.Д. Ушаков (Академия Государственной противопожарной службы МЧС России; e-mail: info@academygps.ru) СИСТЕМНЫЙ АНАЛИЗ В СОЦИАЛЬНЫХ СИСТЕМАХ Рассмотрены основные приёмы проведения системного анализа; представлен научный инструментарий системного анализ...»

«MИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ УТВЕРЖДАЮ Заместитель Министра образования Российской Федерации _ В.Д.ШАДРИКОВ 27.03.2000 г. Номер государственной регистрации _271гум/сп_ГОСУДАРСТВЕННЫЙ ОБРАЗОВАТЕЛЬНЫЙ СТА...»

«ИНСТРУКЦИЯ для АВТОРИЗОВАННЫХ ИНСТАЛЛЯТОРОВ ввода в эксплуатацию каминов на пеллетах серия BURNiT Comfort PM (с водяным контуром) и PM-B (с водяным контуром и металлической дверцей с изоляцией) НЕС Новые Энергийные Системы ООО Болгария г. Шумен 9700 бул. Мадара 12 тел: +359 54 874 536 факс: +359 54 87...»

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

«Муниципальное бюджетное общеобразовательное учреждение "Мегетская средняя общеобразовательная школа". _ 665854, Иркутская область, Ангарский городской округ, рабочий Мегет, переулок Школьный, д. 8. Тел/факс 8(3952) 49-20-40...»

«2 Современные гидролого-гидрогеологические условия и их фоновые характеристики в районе месторождения "Хотиславское"2.1 Гидрографическая сеть и гидрологические условия Изученность территории в гидрологич...»

«ДОРОЖНАЯ КАРТА РАЗВИТИЯ МАЛОГО И СРЕДНЕГО ПРЕДПРИНИМАТЕЛЬСТВА РЕСПУБЛИКИ ТАТАРСТАН НА ПЕРИОД 2014-2016 ГОДЫ (проект стратегического документа) Казань, 2013 Торгово-промышленная палата Республики Татарстан. Дорожная карта "Развитие МСБ в РТ на 2014 – 2016 годы"...»

«Михаил Петрович Лазарев Три кругосветных путешествия Серия "Великие путешествия" http://www.litres.ru/pages/biblio_book/?art=9363107 Три кругосветных путешествия: ЭКСМО; Москва; 2014 ISBN 978-5-699-61473-8 Аннотация Знаменитый русский путешественник и флотоводец Михаил Петрович Лазарев (1788 —1851) за св...»

«УВАЖАЕМЫЙ ПОКУПАТЕЛЬ! Благодарим Вас за то, что Вы отдали предпочтение нашему изделию. Вы приобрели "Бойлер газовый накопительный настенного исполнения (индекс W) с подключением к дымоходу (индекс F) или без подключения к дымоходу...»

«отчет участкового уполномоченного полиции Отдела МВД России по району Зябликово г. Москвы старшего лейтенанта полиции Д.М. Кнежевич, перед жителями административного участка Здравствуйте, уважаемые жители района! В п...»

«SUNVISION 200 series Вступление Вы сделали прекрасный выбор, приобретя SunVision200. SunVision222 XL и SunVision244 XL являются результатом многолетних исследований и тщательного исполнения. SunVision200 – серии сконструирован максимально удобным для пользователя и, конечно, соответствует всем...»

«ПИСАТЕЛЬ И ВРЕМЯ Г Юрий НАГИБИН МОСКВА. КАК МНОГО В ЭТОМ ЗВУКЕ.•СОВЕТСКАЯ РОССИЯ ПИСАТЕЛЬ И ВРЕМЯ Юрий НАГИБИН МОСКВА. КАК МНОГО В ЭТОМ ЗВУКЕ. МОСКВА "СОВЕТСКАЯ РОССИЯ" Р2 Н16 Писатель Юрий Нагибин широко известен ке только своими книгами, но и остропроблемн...»

«БЕЗДЕЙСТВИЕ КАК ФОРМА ПРЕСТУПНОГО ПОВЕДЕНИЯ. ОСОБЕННОСТИ БЕЗДЕЙСТВИЯ В НЕКОТОРЫХ ПРЕСТУПЛЕНИЯХ СО СПЕЦИАЛЬНЫМ СУБЪЕКТОМ Лосева А.В. Институт сферы обслуживания и предпринимательства (фили...»

«Практика рассмотрения дел, связанных с торговлей людьми Иванов Г.П. – судья Верховного Суда Российской Федерации, заслуженный юрист Российской Федерации В российском уголовном законодательстве норма, касающая...»

«1-2 Содержание РАЗДЕЛ 1. Общая характеристика образовательной программы 1.1. Цель (миссия) основной образовательной программы 1.2. Срок освоения основной образовательной программы 1.3. Трудоемкость основной образовательной программы Требования к абитуриенту 1.4. 3-5 РАЗДЕЛ 2. Характеристи...»

«zbek tilining izoli luati: 80000 dan orti sz va sz birikmasi; 5 ildli. E M. ild 2, 2006, Begmatov, T. Mirzaev, Alier Navoij Nomidagi Til va Adabit Instituti, 5898901329, 9785898901325,...»

«"Вестник Московского Университета. Управление государство и общество: серия 21".-2013.-№2.-С.32-43. СОВРЕМЕННЫЕ КОНЦЕПЦИИ ГОСУДАРСТВЕННОГО УПРАВЛЕНИЯ: ЭТИЧЕСКИЙ АСПЕКТ В.К. Борисов, Е.Ю. Бочарова В статье рассматриваются основные подходы к определению понятия этики государственной...»

«Мерси Шелли Текст предоставлен автором http://www.litres.ru/pages/biblio_book/?art=135326 Аннотация Если в "Паутине" рассматривалось достаточно близкое будущее, так сказать, следующий этап в развитии интернета, то название "2048" уже говорит само за себя. Это уже совсем другая эпоха и другой тип героев. Автор заглядывает в будущее даже дальше, чем в сво...»

«CF3000 Инструкция по установке Cooper Lighting and Security Ltd Wheatley Hall Road Doncaster South Yorkshire Прошел аттестацию по стандарту ISO 9001:2000 DN2 4NB Номер сертификата 714а/01 TEL: +44 (0) 1302 321541 Принят по EN54-2:1997 и EN54-4:1997 FA...»

«СВЯТОЙ ЕФРЕМ СИРИН ТВОРЕНИЯ Том VIII ОГЛАВЛЕНИЕ Толкование св. Ефрема на Четвероевангелие Предисловие Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Глава 7 Глава 8 Глава 9 Глава 10 Глава 11 Глава 12 Глава 13 Глава 14 Глава 15 Глава 16 Глава 17 Глава 18 Глава 19 Глава 20 Глава 21 Глава 22 Молитва Того же святого Ефрема (прибавлени...»

«Александр Зорич Карл, герцог Серия "Карл, герцог", книга 1 Текст предоставлен издательством "АСТ" http://www.litres.ru/pages/biblio_book/?art=120851 Карл, герцог: АСТ, АСТ Москва, Хранитель, Харвест; Москва; ISBN 978-5-17-0...»

«Инструкция для радиотелефона panasonic kx tg2248 25-03-2016 1 Похуистичное обслуживание заправится возмужалыми кораблестроителями. Рекламируемые папики прикуривают, в случае когда не испачканное умервщление бережн...»










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

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