Готовый перевод Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 5 - Программирующие Программы

5.1 Лисп - Не Функциональный Язык

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

Функциональный язык - это язык программирования, состоящий из функций.

Итак, что же такое функция? Функция - это математическая концепция существующая на протяжении веков:

Функция - это статичное, точно определённое преобразование исходных значений в результирующие значения.

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

(defun adder (x)
(+ x 1))

Очевидно мы можем применить этот объект к любому числу и получить результат, но является ли adder настоящей функцией? Лисп утверждает что adder - это функция 1:

1 Если вы до сих пор не знакомы с функцией COMMON LISP describe то вам нужно немедленно с ней ознакомиться. Примените describe к функции, специальной форме, макросу, переменной, символу и замыканию.

* (describe #’adder)
#<Interpreted Function> is a function.

Но, именование этих объектов функциями является некорректным использованием термина с глубокими корнями в истории лиспа. Defun и лямбда формы на самом деле создают процедуры, или если говорить более точно, экземпляры, вызываемые как функции (funcallable instances) [AMOP]. В чём различие? Процедуры не обязательно должны содержать в себе работу с преобразованием значений, но процедуры являются участками кода, возможно содержащим сохраняемую среду, которую можно выполнить (funcall). Когда лисп программисты пишут программы в определённом стиле, называемом функциональным стилем, то получающиеся процедуры можно рассматривать и комбинировать в математическом стиле функциональных преобразований.

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

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

И наконец, обычно многие языки делают бессмысленное различие между выражением и оператором, для того, чтобы поддерживать ужасный Блаб синтаксис, например: инфиксный. В лиспе всё возвращает что-либо 2 и нет (синтаксических) ограничений для вложения или комбинации. Это простой вопрос с очевидным ответом: что более важно в языке, синтаксис, дружественный к новичкам, или настоящая гибкость? Все языки, которые используют инфиксный синтаксис уменьшают возможности абстракции многими способами. К счастью большинство современных языков доверяют своим пользователям пользователям и дают им возможность комбинировать выражения так, как они считают нужным. В сравнении с языками, которые принимают подобные мозгоубивающие синтаксические решения, лисп выглядит более функциональным.

2 Исключением является ничего не возвращающий (values). Но, это сводится к nil и по этой причине может использоваться в выражениях.

После того, как программисты привыкли к этой вездесущей и достаточно ошибочной терминологии, пришло понимание что понятие функции, использованной в больших дебатах посвящённым функциональным и не функциональным языкам не только запутывает, но и является фундаментальным шагом назад. Чтобы исправить это программисты и учёные вернулись к меловой доске и математическому определению функции: преобразование входных значений в выходные значения. Если лисп является функциональным языком, то он настолько же функционален, насколько функциональны такие современные языки программирования как Perl и JavaScript.

Очевидно что лисп процедуры не являются функциями. Лисп процедуры могут возвращать не-статичные значения, эти процедуры вы можете вызывать несколько раз с одними и теми же аргументами и каждый раз можете получать разные значения. В наших примерах из предыдущих глав, лисп процедуры могут хранить состояния. Процедуры подобные rplaca могут изменять значения не только в памяти, но и в других местах (таких как регистры). Такие лисп процедуры как terpri и format создают вывод (новые строки в случае terpri) направляемые в терминал или файлы 3. Лисп процедуры подобные yes-or-no-p могут читать ввод из терминала и возвращать значения в зависимости от ввода пользователя. Являются ли эти процедуры статичными, точно определёнными преобразованиями?

3 Terpri и rplaca - они были названы не просто так.

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

Выяснилось что большинство языков на самом деле не являются функциональными, после этого некоторые разработчики языков решили узнать как будет выглядеть программирование на настоящих функциональных языках. Как вы можете ожидать программирование на функциональных языках в основном раздражает и бывает непрактичным. Почти нет проблем относящихся к реальному миру и которые можно было бы выразить через статичные, чётко определённые преобразования из исходных значений в результирующие значения. Но это не значит что функциональное программирование не имеет плюсов и многие языки были спроектированы так, чтобы получить преимущества от функционального стиля программирования. Это означает нахождение удобного способа изоляции функциональных частей программ от (на самом деле интересных) не-функциональных частей. Такие языки как Haskell и OCaml используют эту изоляцию как средство создания агрессивных оптимизационных допущений.

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

5.2 Программирование Сверху-Вниз

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

В разделе 3.2, Предметно Ориентированные Языки при первом знакомстве с предметно-ориентированными языками мы создали простой макрос unit-of-time. Этот макрос дал нам удобный способ определения периодов времени в различных величинах с помощью основанного на символах, интуитивно-понятного синтаксиса:

* (unit-of-time 1 d)
86400

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

Важным принципом в проектировании макросов является программирование сверху-вниз (top-down). Проектирование лисп макроса следует начать с создания абстракции.Вам нужно писать программы, использующие макросы ещё до того, как вы написали сам макрос. Что парадоксально, вам нужно знать как писать на языке ещё до того, как вы сможете написать краткое определение/реализацию этого языка.

Таким образом первым шагом в конструировании серьёзного макроса является написание вариантов использования (use cases) макроса, даже если нет никакого способа с помощью которых вы смогли бы проверить или использовать эти макросы. Если программы, написанные в этом новом языке окажутся достаточно объемлющими, то идея о том, что лучше реализовать: компилятор или интерпретатор последует сама собой.

Рассмотрим наш макрос unit-of-time, существует ли способ перевести этот макрос на ещё больший уровень спецификации и создать язык, предназначенный для создания макросов, создающих удобные единицы измерения? Что же, unit-of-time - это макрос, и чтобы выполнить задуманное, нам нужен макрос, определяющий другой макрос...

Стоп! Этот низ является верхом.

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

(defunits% time s
m 60
h 3600
d 86400
ms 1/1000
us 1/ 1000000)

Defunits% может расшириться в код, определяющий макрос, подобный unit-of-time, написанный нами в разделе 3.2, Предметно-Ориентированные Языки, что позволяет нам преобразовывать произвольные единицы времени в секунды. Можно ли ещё более улучшить этот код?

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

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

(defunits%% time s
m 60
h (60 m)
d (24 h)
ms (1/1000 s)
us (1/1000 ms))

Связывание (chaining) единиц измерений выглядит естественной операцией. Минуты определены в терминах наших базовых единиц, секунд, часы - в терминах минут, и дни - в терминах часов. Реализуя наш макрос в итеративном стиле мы, для начала, реализуем несвязываемое поведение с defunits%, после этого мы реализуем связывание с defunits%% ещё до добавления соответствующих проверок на ошибки и переходу к реализации финальной версии, defunits.

Заметьте, что этот новый язык может больше, чем просто предоставление удобного синтаксиса для добавления новых типов единиц. Этот язык также позволяет нам уменьшить воздействие округления (rounding) в наших вычислениях и позволяет лиспу использовать настолько точную арифметику насколько это возможно. Например, фарлонг - это 1/8 мили, и если мы закодируем это значение с использованием очередизации взамен, скажем, метрического приближения, то в конечном итоге мы можем получить более точные результаты или, что ещё более важно, результаты, максимально соответствующие вычислениям, произведёнными с помощью миль. Поскольку нам достаточно всего лишь добавить самый точный коэффициент преобразования не прибегая к каким-либо другим преобразованиям, то этот макрос даёт нам возможность создавать правила на уровне выражений, невозможных в других языках.

Используя поведение автоматических gensym-ов, описанное в разделе 3.5, Нежелательный Захват, написание defunits% оказывается чрезвычайно простым делом. Функция Грэма symb сгенерирует новое имя для макроса конвертации. Например, если символ time - это тип уже существующей единицы, то новый макрос конвертации будет называться unit-of-time. Defunits% был сконструирован исходя из описания unit-of-time, описанном в разделе 3.2, Предметно-Ориентированные Языки, но, этот код окружён defmacro! и обратной кавычкой, и замещены части, нуждающиеся в повторном создании при каждом вызове макроса.

Листинг 5.1: DEFUNITS-1
(defmacro! defunits% (quantity base-unit &rest units)
`(defmacro ,(symb 'unit-of- quantity) (,g!val ,g!un)
`(* ,,g!val
,(case ,g!un
((,base-unit) 1)
,@(mapcar (lambda (x)
`((,(car x)) ,(cadr x)))
(group units 2))))))

Defunits% использует вложенные обратные кавычки - чрезвычайно сложную для понимания конструкцию. Программирование с обратными кавычками - это тоже самое, что и обладание ещё одним смысловым измерением в коде. В других языках, определённый программный оператор обычно обладает очень простой вычислительной семантикой. Вы знаете когда буден запущен каждый бит кода, поскольку каждый бит кода вынужден выполняться в одно и тоже время: во время выполнения. Но в лиспе с помощью вложенных обратных кавычек мы можем масштабироваться вверх и вниз по лестнице закавычивания (ladder of quotation). Каждая написанная нами обратная кавычка - это один шаг по этой лестнице: наш код - это список, вычисление которого зависит от нашего желания. Но внутри обычного списка каждая встреченная запятая переносит нас на шаг вниз по лестнице закавычивания и исполняет код из соответствующего шага лестницы [CLTL2-P967].

Таким образом это простой алгоритм для определения времени вычисления каждого бита из лисп формы. Просто начните с корня выражения и после встречи с каждой обратной кавычкой пометьте переход на ещё один уровень закавычивания. Для каждой встреченной запятой пометьте переход на уровень ниже. Как заметил Стил [CLTL2-P530], следование этому уровню закавычивания может быть трудной задачей. Эта трудность - потребность отслеживать вашу текущую глубину вложения - это то, что заставляет ощущать использование обратных кавычек другим измерением добавленным в обычное программирование. В других языках вы можете пойти на север, юг, восток и запад, но лисп вдобавок даёт вам возможность перемещаться вверх.

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

Листинг 5.2: DEFUNITS-CHAINING-1
(defun defunits-chaining% (u units)
(let ((spec (find u units :key #'car)))
(if (null spec)
(error "Unknown unit ~a" u)
(let ((chain (cadr spec)))
(if (listp chain)
(* (car chain)
(defunits-chaining%
(cadr chain)
units))
chain)))))

Следует помнить, что макросы - это на самом деле просто функции, мы создали функцию-утилиту для использования её в определении макроса, defunits-chaining%. Эта функция-утилита получает единицу, определённую символами, подобными S, M или H, и список определений единиц. Мы разрешаем работу с определениями единиц до получения числа, которое будет интерпретироваться базовой единицей, например (M 60) или списком, содержащим неявную отсылку к другой единице в очереди, например (H (60 M)).

Это рекурсивная функция-утилита. Для нахождения множителя, применяемого для базовой единицы мы перемножаем каждое звено очереди с другим вызовом функции-утилиты используемой для обработки остальной части очереди. После возврата из стека вызовов мы получим множитель, применяемый для конвертации значения единицы в значение базовой единицы. Например, когда мы конструируем множители для часов, мы находим что в одном часе 60 минут. Мы переходим в рекурсию и находим что в одной минуте 60 секунд. Мы опять переходим в рекурсию и находим что секунда - это конец очереди - минуты были определены непосредственно в терминах базовых единиц. Итак, вернувшись из рекурсии мы вычисляем (* 60 (* 60 1)), что равняется 3600: то есть, в одном часе 3600 секунд.

Листинг 5.3: DEFUNITS-2
(defmacro! defunits%% (quantity base-unit &rest units)
`(defmacro ,(symb 'unit-of- quantity) (,g!val ,g!un)
`(* ,,g!val
,(case ,g!un
((,base-unit) 1)
,@(mapcar (lambda (x)
`((,(car x))
,(defunits-chaining%
(car x)
(cons `(,base-unit 1)
(group units 2)))))
(group units 2))))))

После определения этой функции-утилиты, для работы с множителем для каждой единицы требуется простая модификация defunits%, которую мы выполнили в defunits%%. Вместо объединения в значение прямо из определения единицы мы передаём каждую единицу и целое определение единицы в утилиту defunits-chaining%. Как было описано выше, эта функция рекурсивно преобразует множитель, требуемый для каждой единицы, в базовую единицу. С этим множителем defunits%% может объединять значение в case операторы, также, как это выполняет defunits%.

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

Проблема связанная с defunits%% является частью создаваемого нами языка: в этом языке возможны программы, содержащие циклы. Например:

(defunits time s
m (1/60 h)
h (60 m))

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

Листинг 5.4: DEFUNITS
(defun defunits-chaining (u units prev)
(if (member u prev)
(error "~{ ~a~^ depends on~}"
(cons u prev)))
(let ((spec (find u units :key #'car)))
(if (null spec)
(error "Unknown unit ~a" u)
(let ((chain (cadr spec)))
(if (listp chain)
(* (car chain)
(defunits-chaining
(cadr chain)
units
(cons u prev)))
chain)))))

(defmacro! defunits (quantity base-unit &rest units)
`(defmacro ,(symb 'unit-of- quantity)
(,g!val ,g!un)
`(* ,,g!val
,(case ,g!un
((,base-unit) 1)
,@(mapcar (lambda (x)
`((,(car x))
,(defunits-chaining
(car x)
(cons
`(,base-unit 1)
(group units 2))
nil)))
(group units 2))))))

* (defunits time s
m (1/60 h)
h (60 m))
Error in function DEFUNITS-CHAINING:
M depends on H depends on M

Макрос defunits идентичен defunits%% за исключением того, что он передаёт дополнительный аргумент nil функции defunits-chaining, являющийся концом списка, отображающего историю уже посещённых единиц. Если при поиске новой единицы мы обнаружим что уже встречали её, то это обозначает обнаружение цикла. Мы можем использовать эту историю посещённых единиц для печати вспомогательных сообщений пользователям макросов, написавших циклы.

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

Примером использования defunits является unit-of-distance (единицы-расстояния). В 1970 году морская сажень сократилась, по крайней мере для британских моряков, на 1/76 часть:

* (/ (unit-of-distance 1 fathom)
(unit-of-distance 1 old-brit-fathom))
75/76

Листинг 5.5: UNIT-OF-DISTANCE
(defunits distance m
km 1000
cm 1/100
mm (1/10 cm)
nm (1/1000 mm)

yard 9144/10000 ; Принято в 1956
foot (1/3 yard)
inch (1/12 foot)
mile (1760 yard)
furlong (1/8 mile)

fathom (2 yard) ; Принято в 1929
nautical-mile 1852
cable (1/10 nautical-mile)

old-brit-nautical-mile ; Отменено в 1970
(6080/3 yard)
old-brit-cable
(1/10 old-brit-nautical-mile)
old-brit-fathom
(1/100 old-brit-cable))

Что чуть больше 2-х сантиметров:

* (coerce
(unit-of-distance 1/76 old-brit-fathom)
’float)
0.024384

5.3 Неявные Контексты

Макросы могут использовать технику под названием неявный контекст (implicit context). Иногда мы решаем неявно добавить лисп код в некоторые выражения, которые мы не хотим часто писать и хотим использовать как абстракцию, нередко это применяется в многократно используемом коде или в коде, который должен быть краток и задействуется в других частях программы. До этого момента мы уже беседовали о неявных контекстах и вам уже должно быть ясно, что неявные контексты даже безотносительно программирования макросов являются фундаментальной частью лисп программирования: формы let и lambda обладают неявным progn-ом, поскольку они вычисляют, поочерёдно, формы их тела и возвращают последний результат. Defun добавляет неявную lambda вокруг форм, и поэтому вам не нужно использовать лямбда формы для именованных функций.

В этом разделе описывается создание и конструкция макроса tree-leaves 4, предназначенного для прохода по коду (code-walking), который позже будет использоваться в этой книге. Подобно flatten этот макрос исследует переданный ему лисп код, рассматривая его как дерево, затем производит некоторые модификации и возвращает новое дерево. Списковая структура исходного выражения не модифицируется: flatten и tree-leaves оба создают новую структуру. Разница между ними заключается в том, что основная цель flatten в удалении вложенных списков и в возвращении плоского списка, уже не являющегося лисп кодом, а tree-leaves сохраняет структуру выражения, но изменяет значения отдельных атомов.

4 Также стоит посмотреть функцию COMMON LISP subst.

Начнём с простого эскиза. Tree-leaves% - это функция, рекурсивно проходящая по предоставленному выражению tree, cons-я новую списковую структуру с той же формой 5. Когда она обнаруживает атом, то вместо того, чтобы вернуть этот атом она возвращает значение аргумента result:

5 Пустой else случай в форме if возвращает nil, также являющийся пустым списком.

Листинг 5.6: TREE-LEAVES-1
(defun tree-leaves% (tree result)
(if tree
(if (listp tree)
(cons
(tree-leaves% (car tree)
result)
(tree-leaves% (cdr tree)
result))
result)))

* (tree-leaves%
’(2 (nil t (a . b)))
’leaf)
(LEAF (NIL LEAF (LEAF . LEAF)))

Итак tree-leaves% возвращают новое дерево, в котором все атомы преобразуются в предоставленный нами символ, leaf. Заметьте, что атом nil в car позиции cons ячейки не изменился поскольку он не изменится при перемещении его в cdr позицию (и представляет из себя пустой список).

Конечно, изменение каждого элемента это весьма бесполезно. То что нам нужно на самом деле - так это возможность выбора определённых атомов и возможность избирательной трансформации их в новые атомы для последующей вставки в новую списковую структуру, оставляя неинтересные нам атомы без изменений. В лиспе самым лёгким способом является написание изменяемой функции-утилиты, дающей возможность применять плагины (plug-ins) где пользователь может использовать произвольный код для контроля поведения утилиты. Примером этому может служить функция sort, включённая в COMMON LISP. В этом примере в функцию sort подключена в виде плагина функция меньше чем:

*(sort ’(512438967) #’<)
(123456789)

Листинг 5.7: PREDICATE-SPLITTER
(defun predicate-splitter (orderp splitp)
(lambda (a b)
(let ((s (funcall splitp a)))
(if (eq s (funcall splitp b))
(funcall orderp a b)
s))))

Эта концепция получения функции, предназначенной для контроля поведения особенно удобна, поскольку мы можем создавать анонимные функции, специально предназначенные для наших задач. Или, с целью получения ещё большей мощи, мы можем создать функции, которые будут порождать эти анонимные функции для нас. Также это известно как комбинирование функций (function composition) 6. И хотя комбинирование функций не так интересно как комбинирование макросов, оно по прежнему остаётся чрезвычайно полезной техникой, которой должны овладеть все профессиональные лисп программисты.

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

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

* (sort ’(5 1 2 4 3 8 9 6 7)
(predicate-splitter #’< #’evenp))
(246813579)

Листинг 5.8: TREE-LEAVES-2
(defun tree-leaves%% (tree test result)
(if tree
(if (listp tree)
(cons
(tree-leaves%% (car tree) test result)
(tree-leaves%% (cdr tree) test result))
(if (funcall test tree)
(funcall result tree)
tree))))

Итак, как использовать функции в роли плагина для управления работой tree-leaves%? В обновлённой версии tree-leaves%, tree-leaves%% мы добавили две отличающихся функции-плагина, из которых одна предназначена для определения изменяемых листьев, а другая определяет как преобразовывать старый лист в новый лист, соответственно, эти плагины названы как test и result.

Мы можем использовать tree-leaves%% передавая ему два лямбда выражения, каждое из которых должно получать единственный аргумент, x. В данном случае нам нужно получить новое дерево: с той же самой списковой структурой что и наш аргумент tree, за исключением того, что все чётные числа заменены на символ even-number:

* (tree-leaves%%
’(1 2 (3 4 (5 6)))
(lambda (x)
(and (numberp x) (evenp x)))
(lambda (x)
’even-number))
; Note: Variable X defined but never used.
(1 EVEN-NUMBER (3 EVEN-NUMBER (5 EVEN-NUMBER)))

Вроде бы всё работает за исключением того, что лисп корректно вызывает предупреждение по факту не использования переменной x во второй функции - плагине. Если мы не используем переменную, то часто это является признаком наличия проблем в коде. Даже если мы умышленно не используем переменную, как в нашем случае, компилятор выдаст информацию о том, какая переменная будет игнорироваться. Обычно мы используем эту переменную, но есть случаи, подобные нашему, когда нам не нужно использование переменной. Очень плохо если мы получаем аргумент для функции - и после всего этого просто игнорируем этот аргумент. Такая ситуация часто возникает при написании гибких макросов. Решением является передача компилятору информации о том, что переменная x может быть проигнорирована. Поскольку нет ничего болезненного в объявлении игнорируемой какую-либо переменную и последующем её использовании 7, то мы можем декларировать информацию о том, что обе переменные x должны быть игнорируемыми:

7 Лисп выяснит что на самом деле не может игнорироваться.

* (tree-leaves%%
’(1 2 (3 4 (5 6)))
(lambda (x)
(declare (ignorable x))
(and (numberp x) (evenp x)))
(lambda (x)
(declare (ignorable x))
’even-number))
(1 EVEN-NUMBER (3 EVEN-NUMBER (5 EVEN-NUMBER)))

Теперь мы подошли к интересному месту этого урока. Похоже что tree-leaves%% прекрасно работает и выполняет то, что нам требуется. Мы можем изменить любые листья в дереве передав функции-плагины, которые будут выяснять какой лист нужно изменить и на что изменить. На этом месте улучшение утилиты было бы остановлено в языках программирования отличающихся от лиспа. Но не в лиспе. В лиспе мы можем ещё больше улучшить нашу утилиту.

И хотя tree-leaves%% предоставляет нам всю требуемую функциональность, его интерфейс остаётся неудобным и избыточным. Чем проще использование утилиты, тем выше вероятность нахождения интересного применения этой функции. С целью уменьшения беспорядка, окружающего нашу утилиту, мы создадим макрос, предоставляющий неявный контекст его пользователям (ну и конечно, нам самим).

Но вместо применения таких простых приёмов как неявный progn или неявную лямбду, мы используем весь неявный лексический контекст, избавляющий нас от накладных расходов при создании этих функций-плагинов и требующий минимального ввода кода при выполнении таких общих задач, как трансляция деревьев. Этот неявный лексический контекст не похож на простые неявности в том смысле, что в нём мы найдём не только другие способы применения общих неявных шаблонов. Вместо этого мы шаг за шагом разработали не-столь-общий шаблон при работе над нашим интерфейсом прохода по коду tree-leaves%%.

Листинг 5.9: TREE-LEAVES
(defmacro tree-leaves (tree test result)
`(tree-leaves%%
,tree
(lambda (x)
(declare (ignorable x))
,test)
(lambda (x)
(declare (ignorable x))
,result)))

При конструировании нашего неявного макроса, мы просто скопировали использование tree-leaves%% из REPL-а прямо в определение tree-leaves, а части, которые должны изменяться в различных применениях макроса были параметризованы при помощи обратных кавычек. Теперь, благодаря этому макросу у нас есть менее многословный интерфейс использования утилиты tree-leaves%%. Конечно, этот интерфейс обособлен, поскольку есть множество путей, с помощью которых мы можем добиться подобного поведения. Однако, созданный нами макрос более интуитивен и более лёгок в применении, по крайней мере, в наших случаях. Макросы позволили нам создать эффективный программный интерфейс простым и лёгким способом, недоступным в других языках. Вот как мы можем применить наш макрос:

* (tree-leaves
’(1 2 (3 4 (5 . 6)))
(and (numberp x) (evenp x))
’even-number)
(1 EVEN-NUMBER (3 EVEN-NUMBER (5 . EVEN-NUMBER)))

Заметьте, что переменная x используется без определения переменной. Причиной этому является неявная лексическая переменная (implicit lexical variable), привязанная к каждому из двух последних переменных. Появление переменной без её объявления называют нарушением лексической прозрачности (lexical transparency). Другими словами можно сказать что анафора (anaphor) под названием x, введена в эти формы для дальнейшего использования из этих форм. В дальнейшем мы очень, очень сильно разовьём эту идею в главе 6, Анафорические Макросы.

5.4 Проход по Коду с Macrolet

Лисп - это не язык, это строительный материал
- Алан Кэй

Такие редко выговариваемые формы выражений, как компьютерный код, часто получают разнообразные произношения. Большинство программистов выполняют код в голове, размышляя над выражениями и проговаривают операторы чаще неосознанно, а иногда осознанно. Например, наиболее очевидный способ произношения специальной лисп формы macrolet - это звуковое объединение двух лисповских компонентов: macro и let. Но после прочтения Стила [CLTL2-P153] некоторые лисп программисты начинают произносить macrolet так, что это слово рифмуется с Шевроле (Chevrolet), такое забавное произношение крайне трудно выкинуть из головы.

В не зависимости от произношения macrolet остаётся жизненно важной частью грамотного лисп программирования. Macrolet - это специальная форма Common Lisp, которая вводит новые макросы в его закрытую лексическую область видимости. Создание синтаксических трансформаций macrolet выполняется в том же стиле, что и определение глобальных макросов с defmacro. Макросы, определённые с помощью macrolet, раскрываются лисп системой при проходе-по-коду (code-walk) ваших выражений также, как и раскрытие макросов, определённых с помощью defmacro.

Но macrolet предназначен не только для удобства. У macrolet есть свои преимущества перед defmacro, используемого для определения макросов. Во-первых, если вы хотите чтобы макрос расширялся по разному в зависимости от лексических контекстов в выражении, то придётся прибегнуть к созданию контекстов с помощью macrolet. Здесь defmacro попросту не будет работать.

Самое главное преимущество заключается в том, что с помощью macrolet можно решать трудную задачу прохода по коду COMMON LISP выражений. Часто мы получаем какое-либо произвольно взятое дерево лисп кода, например, для его макро-обработки и в этом дереве нам нужно изменить значения переменных или значения различных ветвей дерева. Проход по коду нужен для реализации временных значений некоторых форм и временного переназначения определённых макросов в отдельных частях лексического контекста в выражении. В частности, нам нужно рекурсивно пройти через код, найти место в котором вычисляется нужный макрос или функция и произвести замену на наше выражение.

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

(blah t)

В данном списке blah находится на месте функции и вычислении этого выражения будет вычисляться blah. В данном случае весьма очевидно где следует выполнять подстановку. Пока всё хорошо. А что будет если мы передадим вот эту форму:

’(blah t)

Поскольку выражение закавычено, то этот кусок кода не должен изменяться. В данном случае замена не допустима. Поэтому наша реализация прохода-по-коду должна знать когда ей следует остановиться и не выполнять замены в закавыченных формах. Что же, это достаточно просто реализовать. Задумаемся: существуют ли ещё ситуации, где раскрытие blah будет некорректным. Что если нам встретится код, использующий blah в качестве имени лексической переменной?

(let ((blah t))
blah)

Даже несмотря на то, что blah появляется в роли первого элемента списка, он является локальной привязкой для let формы, поэтому эта привязка не должна расширяться. Всё не так уж и плохо. Мы можем добавить логику обработки специального случая для нашего прохода-по-коду, благодаря чему он будет знать что делать при встрече let формы. К несчастью, у нас по прежнему остаются ещё 23 специальные формы 8 ANSI COMMON LISP которые тоже требуют добавления логики обработки специальных случаев. Усложняет дело ещё то, что многие специальные формы сложны для корректного прохода. Как мы уже видели, let может быть хитрым, но могут быть случаи, когда let становится ещё более запутанным. Следующая потенциально правильная COMMON LISP форма содержит одно blah, которое должно быть раскрыто. Какое именно?

8 В ANSI CL есть 25 специальных форм, 23 без учёта let и quote.

(let (blah (blah (blah blah)))
blah)

Проход-по-коду сложен по причине трудностей, возникающих при обработке всех специальных форм (также смотрите [SPECIAL-FORMS] и [USEFUL-LISP-ALGOS2]. Заметьте, что нам не нужна логика обработки специального случая для форм, определённых как макрос. При встрече макроса мы можем его просто расширить до тех пор, пока макрос не перейдёт в вызов функции или в специальную форму. Если это функция, то мы знаем что она следует once-only лямбды, семантике вычисления слева-на-право. Это специальные формы, для которых нам нужно разработать логику обработки.

Похоже предстоит выполнить много работы, не так ли? Так и есть. Завершённый проход-по-коду COMMON LISP, особенно с расчётом на переносимость - это большой, сложный код. Так почему же COMMON LISP не предоставляет нам интерфейс для прохода-по-коду? Что же, оказывается, нечто подобное у нас уже есть и называется macrolet. Проход-по-коду - это то, что нужно выполнить вашей COMMON LISP системой перед тем как вычислить или скомпилировать выражение. Также, как и наш гипотетический проход-по-коду COMMON LISP-у нужно понимать и обрабатывать специальные семантики let и других специальных форм.

Поскольку COMMON LISP может проходить по коду для его вычисления, то необходимость в отдельной программе прохода-по-коду возникает очень редко. Если мы хотим выполнить избирательные трансформации в выражения таким умным способом, который будет в состоянии определить что именно следует изменять, то мы можем просто зашифровать нашу трансформацию в виде макроса и обернуть выражение macrolet формой. COMMON LISP осуществит проход-по-коду для этого выражения, и при вычислении или компиляции будет применять макро трансформации, определённые macrolet-ом. И конечно, поскольку macrolet определяет макросы, то не будут возникать никакие дополнительные затраты во время выполнения. Macrolet предназначен для коммуникации с COMMON LISP-овским проходом-по-коду и гарантирует только то, что COMMON LISP произведёт раскрытие макроса до того как будет запущена скомпилированная функция [CLTL2-P685][ON-LISP-P25].

Один из наиболее распространённых сценариев использования macrolet следующий: считать функцию привязанной к определённому лексическому контексту и использовать форму функции не только для вызова функции. Мы не рассматриваем flet и labels - они могут только определять функции. Таким образом у нас остаются несколько вариантов: написать программу для прохода-по-коду, находящую вызовы этой функции и заменяющую их на что-нибудь ещё, определение глобального макроса, предназначенного для расширения "функции" во что-нибудь ещё или оборачивание формы macrolet-ом, используя системный проход-по-коду для наших целей.

Как было замечено выше: написание прохода-по-коду - трудная задача. По возможности мы должны избегать этот способ. Использование глобального defmacro временами возможно, но часто довольно проблематично. Главная проблема заключается в том, что в COMMON LISP существуют несколько правил определяющие когда - или как часто - будет расширяться макрос, поэтому мы не можем полагаться на одно и то же имя в различных значениях и в различных лексических контекстах. Если мы переопределим глобальный макрос, то в этом случае мы ничего не знаем о факте расширения COMMON LISP-ом - или о возможном расширении в будущем - старого варианта макроса.

Мы вернёмся к разделу 3.3, Контрольные Структуры и в качестве примера, показывающего пользу от применение прохода-по-коду, мы обратимся к положенной под сукно проблеме. Наша первоначальная версия макроса, реализующего Scheme-овский именованный let, nlet, использовал специальную форму labels для создания новых типов управляющих структур. Использование labels позволяет нам временно определить функцию для внутреннего применения в теле именованного let, что позволяет нам применить рекурсию, и мы как-будто запускаем let заново с новыми значениями для let привязок. Когда мы определяли эту функцию, мы упомянули, что COMMON LISP не гарантирует осуществление оптимизации хвостовых вызовов, это может привести к тому, что каждая итерация именованного let может использовать избыточное стековое пространство. Другими словами, в отличие от Scheme, вызов функций в COMMON LISP не гарантируют оптимизацию хвостовых вызовов.

Листинг 5.10: NLET-TAIL
(defmacro! nlet-tail (n letargs &rest body)
(let ((gs (loop for i in letargs
collect (gensym))))
‘(macrolet
((,n ,gs
‘(progn
(psetq
,@(app1y #’nconc
(mapcar
#’1ist
’,(mapcar #’car letargs)
(list ,@gs))))
(go .’.g!n))))
(block ,g!b
(let ,1etargs
(tagbody
,g!n (return-from
,g!b (progn ,@body))))))))

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

В nlet-tail мы окружили переданное тело макросом и завернули его в несколько форм. Для возвращения значения финального выражения мы использовали операторы block и return-from, поскольку мы хотим имитировать поведение формы let и связанный с этой формой неявный progn. Заметьте, для того, чтобы избежать нежелательный захват мы используем gensym для имени этого блока и gensym для каждого параметра let, а макрос loop 9 задействован для сбора этих gensym-ов.

9 Loop - это, как ни странно, наиболее спорный вопрос в COMMON LISP. Однако, большинство обвинений выдвигаемых против loop беспочвенны. Loop - это очень удобный предметно-ориентированный язык для работы с циклами.

Nlet-tail используется также, как и исходный nlet, за исключением того, что здесь запрещены вызовы именованного let в не-хвостовой позиции поскольку они будут расширены в хвостовые вызовы. Ниже представлен всё тот-же прозаический пример, который мы использовали при демонстрации nlet, но этот пример гарантированно не будет потреблять избыточного стекового пространства даже если лисп не будет поддерживать оптимизацию хвостовых вызовов:

(defun nlet-tail-fact (n)
(nlet-tail fact ((n n) (ace 1))
(if (zerop n)
acc
(fact (- n 1) (* acc n)))))

Рассматривая мотивирующий пример из этой секции, заметьте, для того, чтобы найти fact мы используем macrolet для прохода по коду. Мы хотели бы чтобы наш исходный nlet, использующий специальную форму label для привязки функции, работал без потребления дополнительного стекового пространства при вызове именованного let. Технически мы бы хотели изменить некоторые привязки в нашем лексическом окружении и выполнить прыжок назад в верх именованного let. Таким образом nlet-tail получает переданное let имя, в нашем примере fact, и создаёт локальный макрос (local macro), являющийся актуальным только внутри переданного тела. Этот макрос раскрывается в код, который использует psetq для создания let привязок к новым предоставленным значениям и затем прыгает обратно в верх, не требуя стекового пространства. И что наиболее важно, мы можем использовать имя fact для других макросов в нашей программе 10.

10 Какая книга о программировании не содержит так или иначе несколько реализаций факториала?

Для реализации таких прыжков nlet-tail использует комбинацию специальных форм tagbody и go. Эти две формы могут реализовывать goto систему. И хотя проблемы, связанные с goto, широко обсуждаются в структурном программировании (structured programming), COMMON LISP предоставляет эти специальные формы по причинам, с которыми мы уже столкнулись. Контролируя программный счётчик (program counter) - исполняемый в данный момент участок кода - мы можем создавать очень эффективные макро расширения. В то время когда goto не приветствуется в языках высокого (high-level) уровня, один взгляд на любой код на ассемблере покажет что goto очень даже жив и здоров в низкоуровневом программном обеспечении. Даже самые непримиримые сторонники анти-goto не предлагают избавлять такие низкоуровневые языки как C и ассемблер от инструкций jump и goto. Оказывается, что в низкоуровневом программировании мы всё же испытываем некую потребность в goto, хотя бы для написания эффективного кода.

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

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

5.5 Рекурсивные Расширения

При обучении новичков лиспу с помощью примеров, неизбежно возникает один вопрос

Cadr - что это за хрень?

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

Второй подход заключается в ознакомлении студентов с функцией COMMON LISP second и в полном игнорировании cadr. И cadr и second выполняют одну и ту же задачу: возвращают второй элемент списка. Разница в том, что название second выражает выполняемую операцию, а cadr выражает то, как выполняется операция. Cadr определён прозрачно (transparently specified). И хотя second прост для запоминания, эта функция нежелательным образом скрывает смысл операции 11. Часто прозрачные определения являются более лучшим выбором, поскольку мы более глубже думаем об использовании функции cadr, чем просто о получении второго элемента списка. Например, мы можем прозрачно думать об использовании cadr как о концепции получения аргумента из разрушаемого списка лямбда формы. Cadr и second выполняют похожие операции, но концептуально могут представлять различные операции [CLTL2-P530].

11 Частично поскольку second - это то же что и cadr: вы не сможете использовать его для получения второго элемента из таких последовательностей, как, например, векторы.

Ещё более важно чем философские предпочтения прозрачных спецификаций, это возможность создания большого количества операций для получения элементов списка с помощью car и cdr, в отличие от получения доступа с помощью кучки английских слов. Car и cdr удобны тем, что комбинируя их мы создаём новые, независимые функции. Например, (cadadr x) - это тоже, что и (car (cdr (car (cdr x)))). COMMON LISP определяет, что длина всей комбинации car и cdr должна быть меньшей либо равной четырём. И хотя функция second-of-second получающая второй элемент списка и рассматривающая этот элемент как лист и извлекающая из этого списка второй элемент не существует, мы всё же можем использовать для этих целей cadadr.

Особенно удобно иметь эти предварительно определённые комбинации car и cdr доступными для функций, получающих аргумент доступа :key, в качестве такой функции можно привести find:

* (find ’a
’(((a b) (c d)) ((c d) (b a)))
:key #’cadadr)
((c D) (B A))

Использование предварительно определённого cadadr является более коротким чем создание эквивалентного лямбда выражения из комбинаций англоязычных операторов получения доступа:

* (find ’a
’(((a b) (c d)) ((c d) (b a)))
:key (lambda (e)
(second (second e))))
((C D) (B A))

Кроме того COMMON LISP предоставляет функции nth и nthcdr которые могут использоваться как универсальные получатели если, например, мы не не знаем какой именно элемент понадобиться нам во время компиляции. Nth определён очень просто: получить n-ый cdr из списка и после этого применить car. Таким образом (nth 2 list) 11 это то же самое что и (caddr list) и (third list). Nthcdr - это то же самое что и nth за тем исключением что финальный car не выполняется: (nthcdr 2 list) - это то же что и (cddr list).

12 Мы можем без каких-либо проблем использовать list в роли имени переменной поскольку в COMMON LISP-е есть второе пространство имени. Подобный пример было бы проблемно использовать в диалектах с единым пространством имён, например Scheme.

Но, если место в cons структуре не доступно из всех вышеприведённых шаблонов, таких как nth или nthcdr, то нам придётся их комбинировать. Часто комбинирование неоднородных абстракций является признаком незавершённости. Можем ли мы определить предметно-ориентированный язык решающий задачу получения участков списка и объединяющий в себе функции car и cdr, англоязычные функции доступа и такие функции как nth и nthcdr?

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

Листинг 5.11: CXR-1
(defmacro cxr% (x tree)
(if (null x)
tree
`(,(cond
((eq 'a (cadr x)) 'car)
((eq 'd (cadr x)) 'cdr)
(t (error "Non A/D symbol")))
,(if (= 1 (car x))
`(cxr% ,(cddr x) ,tree)
`(cxr% ,(cons (- (car x) 1) (cdr x))
,tree)))))

Синтаксис именования функции доступа к элементу списка в котором название начинается с C, с последующими одним или более символами A или D и заканчивающееся на R является очень интуитивным и примерно соответствует тому, что мы хотели бы скопировать в наш язык. Макрос cxr% - каламбур, обозначающий что один или более символов A или D замещены символом x 13. В cxr% символы A и D определены в списке переданному в качестве первого аргумента макроса. В этом списке задаётся комбинация символов a и/или d и их количество.

13 За исключением названия cxr никак не связан с cxr в Maclisp-e. В Maclisp cxr используется для получения доступа к hunk слотам.

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

(defun eleventh (x)
(cxr% (1 a 10 d) x))

Цель этого раздела - проиллюстрировать жизненное использование рекурсивных расширений (recursive expansions). Рекурсивное расширение происходит тогда, когда макрос расширяет форму в новую форму, которая в свою очередь содержит использование макроса. Как и все рекурсии этот процесс должен завершиться при достижении базового случая (base case). К счастью в конце концов макрос раскроется в форму, которая не будет содержать использования макроса и раскрытие будет завершено.

Здесь мы применяем macroexpand к примеру с макросом cxr% и получаем форму, которая также использует cxr%:

* (macroexpand
'(cxr% (1 a 2 d) some-list))

(CAR (CXR% (2 D) SOME-LIST))
T

После применения macroexpand к новой рекурсивной форме мы получим ещё одну рекурсию:

* (macroexpand
'(CXR% (2 D) SOME-LIST))

(CDR (CXR% (1 D) SOME-LIST))
T

Результаты следующей рекурсии иллюстрируют другое возможное использование cxr%: нулевой список операторов получения доступа 14:

14 Если когда нибудь этот макрос будет включён в COMMON LISP, то его название должно быть cr.

* (macroexpand
'(CXR% (1 D) SOME-LIST))

(CDR (CXR% NIL SOME-LIST))
T

Оператор получения доступа в виде пустого списка - это наш базовый случай и он расширяется непосредственно в список над которым мы производим наши операции:

* (macroexpand
'(CXR% NIL SOME-LIST))

SOME-LIST
T

Используя расширение CMUCL-а macroexpand-all, компонент проходчика-по-коду, мы можем увидеть всё расширение нашей исходной cxr% формы:

* (walker:macroexpand-all
'(cxr% (1 a 2 d) some-list))

(CAR (CDR (CDR SOME-LIST)))

Благодаря нашим замечательным лисп компиляторам, использование cxr% будет идентично функциям caddr и third.

Но, как следует из названия cxr% не завершён. Это всего лишь первый набросок нашего завершённого макроса cxr. Первая проблема нашего наброска в том, что в качестве счётчика для символов A и D принимаются только целые числа. Поэтому nth и nthcdr могут делать то, что не может cxr%.

Нам нужно добавить проверку для случая, когда в качестве префикса для символов A и D передаётся не-целое число. В этом случае наш расширяющийся код должен вычислить то, что ему передано и использовать это значение 15 в качестве количества car-ов или cdr-ов.

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

Вторая проблема связанная с cxr% заключается во встраивании всех комбинаций car и cdr. При малых префиксных числах для символов A и D результат встраивания почти не заметен, но при огромных количествах car и cdr всё становится заметным на глаз; вместо этого мы должны использовать такие циклирующие функции как nth или nthcdr.

Для исправления этих случаев мы добавим альтернативное расширение. Новое поведение будет применяться в тех случаях, если параметр, предшествующий символам A и/или D, не является целочисленным и если мы не встраиваем большое количество car-ов или cdr-ов. Порог встраивания (inline threshold) по которому будет выбираться поведение установлен в 10, а новое поведение мы реализуем в макросе cxr.

С cxr мы можем определить nthcdr непосредственно в терминах его прозрачной car и cdr спецификации:

Листинг 5.12: CXR
(defvar cxr-inline-thresh 10)

(defmacro! cxr (x tree)
(if (null x)
tree
(let ((op (cond
((eq 'a (cadr x)) 'car)
((eq 'd (cadr x)) 'cdr)
(t (error "Non A/D symbol")))))
(if (and (integerp (car x))
(<= 1 (car x) cxr-inline-thresh))
(if (= 1 (car x))
`(,op (cxr ,(cddr x) ,tree))
`(,op (cxr ,(cons (- (car x) 1) (cdr x))
,tree)))
`(nlet-tail
,g!name ((,g!count ,(car x))
(,g!val (cxr ,(cddr x) ,tree)))
(if (>= 0 ,g!count)
,g!val
;; Будет хвостом:
(,g!name (- ,g!count 1)
(,op ,g!val))))))))

(defun nthcdr% (n list)
(cxr (n d) list))

И, аналогично, nth:

(defun nth% (n list)
(cxr (1 a n d) list))

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

Вот как расширяется cxr в nthcdr%:

* (macroexpand
'(cxr (n d) list))

(LET ()
(NLET-TAIL #:NAME1632
((#:COUNT1633 N)
(#:VAL1634 (CXR NIL LIST)))
(IF (>= 0 #:COUNT1633)
#:VAL1634
(#:NAME1632 (- #:COUNT1633 1)
(CDR #:VAL1634)))))
T

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

Макросы могут создавать гибкие расширения видимые пользователем макроса, поэтому нам доступны такие способы прозрачных спецификаций, которые не возможны в других языках. Например, из архитектуры cxr следует что параметры предшествующие символам A и D, являющиеся целочисленными и меньшими чем cxr-inline-thresh будут встроены как вызовы car и cdr:

* (macroexpand '(cxr (9 d) list))

(LET ()
(CDR (CXR (8 D) LIST)))
T

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

* (macroexpand '(cxr ('9 d) list))

(LET ()
(NLET-TAIL #:NAME1638
((#:COUNT1639 '9)
(#:VAL1640 (CXR NIL LIST)))
(IF (>= 0 #:COUNT1639)
#:VAL1640
(#:NAME1638 (- #:COUNT1639 1)
(CDR #:VAL1640)))))
T

Часто мы можем обнаружить что комбинирование макросов является весьма удобным приёмом: cxr может расширяться в ранее написанный макрос nlet-tail. Аналогично иногда оказывается полезным комбинировать макрос с самим собой, тем самым прибегая к рекурсивному расширению.

5.6 Рекурсивные Решения

Кажется что макрос cxr, определённый в предыдущем разделе, можно отнести к комбинированию функций car и cdr, также, как и общие функции получения доступа к элементу плоского списка nth и nthcdr. Ну а что-же насчёт англоязычных методов получения доступа, таких как first, second и tenth? Эти функции бесполезны? Определённо нет. Операция получения четвёртого элемента списка выраженная через fourth определённо лучше вычисления трёх D в caddr как в плане написания, так и в плане чтения.

Листинг 5.13: DEF-ENGLISH-LIST-ACCESSORS
(defmacro def-english-list-accessors (start end)
(if (not (<= 1 start end))
(error "Bad start/end range"))
`(progn
,@(loop for i from start to end collect
`(defun
,(symb
(map 'string
(lambda (c)
(if (alpha-char-p c)
(char-upcase c)
#\-))
(format nil "~:r" i)))
(arg)
(cxr (1 a ,(- i 1) d) arg)))))

На деле самая большая проблема с англоязычными методами доступа к элементам списка в том, что в COMMON LISP-е их только 10, начиная с first и заканчивая tenth. Но, одна из тем этого раздела, да и в целом всей книги, в том, что каждый слой лисп луковицы может использовать нижележащий слой. В лиспе нет примитивов. Если мы хотим определить больше англоязычных методов доступа, например eleventh, то мы легко можем это реализовать это как показано выше. Функция eleventh, определённая с помощью defun не будет отличаться от таких методов доступа определённых в ANSI, как например first и tenth. Поскольку примитивов не существует и мы можем использовать весь лисп в наших определениях макросов, то в наших макросах нам доступна вся мощь лиспа, например loop и format 16.

16 Format - это несколько спорная особенность COMMON LISP. Однако неприятие format, как и обвинения выдвигаемые против loop, основано на не полном понимании концепции и области использования предметно-ориентированных языков.

Макрос def-english-list-accessors использует формат строки "~:r" для конвертирования числа, i, в строку, содержащую соответствующее английское слово. Как принято в лиспе, мы сменили все не-алфавитные символы на дефисы. Затем мы конвертировали эту строку в символ и использовали её в форме defun, которая реализует соответствующую функциональность получения элемента списка с помощью макроса cxr.

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

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

* (macroexpand
'(def-english-list-accessors 11 20))

(PROGN
(DEFUN ELEVENTH (ARG) (CXR (1 A 10 D) ARG))
(DEFUN TWELFTH (ARG) (CXR (1 A 11 D) ARG))
(DEFUN THIRTEENTH (ARG) (CXR (1 A 12 D) ARG))
(DEFUN FOURTEENTH (ARG) (CXR (1 A 13 D) ARG))
(DEFUN FIFTEENTH (ARG) (CXR (1 A 14 D) ARG))
(DEFUN SIXTEENTH (ARG) (CXR (1 A 15 D) ARG))
(DEFUN SEVENTEENTH (ARG) (CXR (1 A 16 D) ARG))
(DEFUN EIGHTEENTH (ARG) (CXR (1 A 17 D) ARG))
(DEFUN NINETEENTH (ARG) (CXR (1 A 18 D) ARG))
(DEFUN TWENTIETH (ARG) (CXR (1 A 19 D) ARG)))
T

Возможность создания этих англоязычных операторов снимает ограничение в десять операторов в ANSI COMMON LISP. Если нам понадобится больше англоязычных операторов доступа, то мы можем создать их с помощью макроса def-english-list-accessors.

Ограничение ANSI накладываемое на глубину комбинации car и cdr равняется четырём. Что можно с этим сделать? Иногда при создании программ обрабатывающих сложные списки, мы можем захотеть изменить функции, получающие доступ к элементу списка и определить их по другому. Например, если мы используем функцию cadadr, second-of-second, для получения доступа к списку и мы изменили наше отображение данных и теперь нам нужно использовать second-of-third, или cadaddr, то здесь мы столкнёмся с ограничениями, налагаемыми COMMON LISP-ом.

Листинг 5.14: CXR-CALCULATOR
(defun cxr-calculator (n)
(loop for i from 1 to n
sum (expt 2 i)))

Также, как и при работе с англоязычными операторами получения доступа, мы можем написать программу, определяющую дополнительные комбинации car и cdr. Проблема в том, что в отличие от англоязычных операторов получения доступа, увеличение глубины комбинаций в такой функции как caddr приводит к экспоненциальному увеличению числа функций, которые должны быть определены. В частности, число операторов получения доступа, которые должны быть определены для покрытия глубины равной n можно определить с помощью функции cxr-calculator.

Мы видим что ANSI определяет 30 комбинаций:

* (cxr-calculator 4)

30

А теперь покажем вам насколько быстро растёт число покрывающих функций:

* (loop for i from 1 to 16
collect (cxr-calculator i))

(2 6 14 30 62 126 254 510 1022 2046
4094 8190 16382 32766 65534 131070)

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

Листинг 5.15: CXR-SYMBOL-P
(defun cxr-symbol-p (s)
(if (symbolp s)
(let ((chars (coerce
(symbol-name s)
'list)))
(and
(< 6 (length chars))
(char= #\C (car chars))
(char= #\R (car (last chars)))
(null (remove-if
(lambda (c)
(or (char= c #\A)
(char= c #\D)))
(cdr (butlast chars))))))))

Для начала нам нужно разработать точную спецификацию cxr символа. Cxr-symbol-p можно описать очень просто: все символы, начинающиеся с C и заканчивающиеся на R, а между ними 5 и более символов A и/или D. Нам не нужно рассматривать cxr символы в которых количество A и/или D меньше 5, поскольку эти функции гарантированно определены в COMMON LISP 17.

17 Повторная привязка функций, определённых в COMMON LISP запрещена.

Поскольку мы планируем использовать cxr для реализации функциональности независимых комбинаций car и cdr, то мы создали функцию cxr-symbol-to-cxr-list конвертирующую cxr символ, как определено в cxr-symbol-p в список, который можно использовать в качестве первого аргумента cxr 18. Пример его использования:

18 Забавно, но нам здесь пригодилась бы устаревшая функция explode, но она не вошла в COMMON LISP, поскольку никто не смог придумать полезное применение этой функции.

* (cxr-symbol-to-cxr-list
'caddadr)

(1 A 1 D 1 D 1 A 1 D)

Заметьте, использование функции list* в cxr-symbol-to-cxr-list. List* - это почти тот же list, за исключением того, что его последний аргумент вставлен в cdr позицию последней cons ячейки в созданном списке. List* удобно применять при написании рекурсивных функций, строящих список, и где каждый фрейм стека может добавлять более одного элемента в список. В нашем случае каждый фрейм будет добавлять два элемента в список: число 1 и один из символов A или D.

Листинг 5.16: CXR-SYMBOL-TO-CXR-LIST
(defun cxr-symbol-to-cxr-list (s)
(labels ((collect (l)
(if l
(list*
1
(if (char= (car l) #\A)
'A
'D)
(collect (cdr l))))))
(collect
(cdr ; chop off C
(butlast ; chop off R
(coerce
(symbol-name s)
'list))))))

И наконец, мы решили что единственный способ эффективного предоставления cxr функций с произвольной глубиной - это проход по коду, предоставляющий выражения и определяющий только необходимые функции. Макрос with-all-cxrs использует утилиту Грэма flatten для прохода по коду в переданных выражениях таким же способом, который был использован в макросе defmacro/g! из раздела 3.5, Нежелательный Захват. With-all-cxrs находит все символы удовлетворяющие предикату cxr-symbol-p, создаёт функции, относящиеся к использованию макроса cxr, и привязывает эти функции вокруг предоставленного кода с помощью формы labels 19.

19 Единственная проблема, возникающая при работе с этим подходом, заключается в том, что такие методы получения доступа не set-абельны.

Теперь мы можем заключить выражения в формах, переданных в with-all-cxrs и считать что эти выражения имеют доступ ко всем возможным cxr функциям. При желании мы можем просто вернуть эти функции и использовать их где угодно:

Листинг 5.17: WITH-ALL-CXRS
(defmacro with-all-cxrs (&rest forms)
`(labels
(,@(mapcar
(lambda (s)
`(,s (l)
(cxr ,(cxr-symbol-to-cxr-list s)
l)))
(remove-duplicates
(remove-if-not
#'cxr-symbol-p
(flatten forms)))))
,@forms))

* (with-all-cxrs #'cadadadadadr)

#<Interpreted Function>

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

* (macroexpand
'(with-all-cxrs
(cons
(cadadadr list)
(caaaaaaaar list))))

(LABELS
((CADADADR (L)
(CXR (1 A 1 D 1 A 1 D 1 A 1 D) L))
(CAAAAAAAAR (L)
(CXR (1 A 1 A 1 A 1 A 1 A 1 A 1 A 1 A) L)))
(CONS
(CADADADR LIST)
(CAAAAAAAAR LIST)))
T

Часто сложно выглядящая задача - такая как определение бесконечных классов англоязычных операторов доступа к элементу списка и комбинации car-cdr - на самом деле просто набор из более простых задач. В отличие от единой задачи, которая может быть сложной, наборы простых проблем могут быть решены через рекурсивный подход. Думая о способах преобразования сложной задачи в набор из более простых задач, мы используем проверенный подход к решению проблем: "раделяй и властвуй" ("divide and conquer").

5.7 Dlambda

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

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

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

(let ((count 0))
(lambda (msg)
(case msg
((:inc)
(incf count))
((:dec)
(decf count)))))

Заметьте, что для обозначения сообщений мы выбрали символы ключевых слов (keyword symbols), это символы, начинаются с : и всегда вычисляются в самих себя. Ключевые слова удобны, поскольку нам не надо их закавычивать или экспортировать их из других пакетов, а ещё они интуитивны, поскольку они спроектированы для выполнения этих и других видов деструктуризации (destructuring). Часто в lambda или defmacro формах ключевые слова не разрушаются во время выполнения. Но, поскольку мы реализуем систему передачи сообщений, которая является одним из видов деструктуризации времени выполнения, то операция обработки ключевых слов будет выполняться во время выполнения. Как мы уже обсуждали, деструктуризация символов - это эффективная операция: простое сравнение указателей. При компиляции нашего примера счётчика он может преобразоваться в следующий машинный код:

Листинг 5.18: DLAMBDA
(defmacro! dlambda (&rest ds)
`(lambda (&rest ,g!args)
(case (car ,g!args)
,@(mapcar
(lambda (d)
`(,(if (eq t (car d))
t
(list (car d)))
(apply (lambda ,@(cdr d))
,(if (eq t (car d))
g!args
`(cdr ,g!args)))))
ds))))

2FC: MOV EAX, [#x582701E4] ; :INC
302: CMP [EBP-12], EAX
305: JEQ L3
307: MOV EAX, [#x582701E8] ; :DEC
30D: CMP [EBP-12], EAX
310: JEQ L2

Но, для того, чтобы создать удобные условия нам нужно избежать необходимости писать case оператор для каждого создаваемого объекта или класса. Похоже что в этой ситуации нужно прибегнуть к макросам. Макрос, который я хочу использовать, называется dlambda, и этот макрос расширяется в lambda форму. Это расширение включает в себя код с большим количеством ветвлений, которые выполняются в зависимости от применённых аргументов. Название dlambda произошло из данной разновидности деструктуризации во время исполнения: это версия lambda с поддержкой деструктуризации или, выражаясь по-другому, деспетчиризации.

Dlambda спроектирована так, чтобы получать в качестве первого аргумента символ ключевого слова. В зависимости от использованного символа ключевого слова dlambda будет выполнять соответствующий кусок кода. Например, наш любимый пример замыканий - простой счётчик - может быть расширен так, что инкрементирование и декрементирование счётчика будет происходить на основе первого элемента с использованием dlambda. Этот шаблон известен как let, окружающий dlambda (let over dlambda):

* (setf (symbol-function 'count-test)
(let ((count 0))
(dlambda
(:inc () (incf count))
(:dec () (decf count)))))

#<Interpreted Function>

Мы можем инкрементировать

* (count-test :inc)

1

и декрементировать

* (count-test :dec)

0

замыкание зависит от первого переданного аргумента. И хотя в вышеприведённом счётчике let, окружающий dlambda, оставлен пустым, списки следующие за символами ключевых слов на самом деле являются списками лямбда деструктуризации (lambda destructuring). Каждый диспетчеризующий вариант, или другими словами каждый аргумент-ключевое-слово, могут обладать собственным лямбда деструктирующим списком, как это показано в следующем расширении замыкания-счётчика:

* (setf (symbol-function 'count-test)
(let ((count 0))
(dlambda
(:reset () (setf count 0))
(:inc (n) (incf count n))
(:dec (n) (decf count n))
(:bound (lo hi)
(setf count
(min hi
(max lo
count)))))))

#<Interpreted Function>

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

* (count-test :reset)

0

:inc и :dec оба получают числовой аргумент, n:

* (count-test :inc 100)

100

:bound проверяет находится ли значение count между двумя граничными значениями, lo и hi. Если же значение count окажется за указанными пределами, то значение count будет установлено в ближайшее граничное значение:

* (count-test :bound -10 10)

10

Важная особенность dlambda заключается в использовании лямбды для всех деструктуризаций так, чтобы сохранить полноценную проверку ошибок и поддержку отладки, предоставляемую нашей COMMON LISP средой. Например, если мы зададим count-test только один аргумент, то мы получим ошибку непосредственно относящуюся к неверному числу аргументов (arity) лямбда приложения:

* (count-test :bound -10)

ERROR: Wrong argument count, wanted 2 and got 1.

Особенно когда dlambda встроена в лексическое окружение, формирующее замыкание, dlambda позволяет нам программировать - на объектно-ориентированном жаргоне - как бы создание объектов с несколькими методами (methods). Dlambda предназначена для простого создания такой функциональности без необходимости отступления от синтаксиса и применения лямбды. Dlambda по прежнему расширяется в единственную лямбда форму и, таким образом, результат вычисления dlambda является тем же, что и результат вычисления lambda: анонимная функция (anonymous function), которая может быть сохранена, применена и что самое главное - использована как лямбда компонент лексического замыкания.

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

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

* (setf (symbol-function 'dlambda-test)
(dlambda
(:something-special ()
(format t "SPECIAL~%"))
(t (&rest args)
(format t "DEFAULT: ~a~%" args))))

#<Interpreted Function>

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

* (dlambda-test 1 2 3)
DEFAULT: (1 2 3)
NIL
* (dlambda-test)
DEFAULT: NIL
NIL

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

* (dlambda-test :something-special)
SPECIAL
NIL

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

Переведено на Нотабеноиде
http://notabenoid.org/book/40014/187614

Переводчики: Charlz_Klug