Готовый перевод Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 2 - Замыкания
2.1 Замыкание-Ориентированное Программирование
Один из выводов к которому мы пришли был следующим: "объект" не должен быть примитивным понятием в языке программирования; объекты и их поведение должны строиться из значений ячеек и старых добрых лямбда выражений.
- Гай Стил во время разработки Scheme
Иногда это называется замыканием (closure), в других случаях - сохранённым лексическим окружением. Или, как любят говорить некоторые из нас - let, окружающий lambda (let over lambda). Вне зависимости от используемой терминологии, усвоение концепции замыканий - это первый шаг в становлении профессионального Лисп программиста. По факту, это умение является жизненно необходимым для правильного использования многих современных языков программирования, кроме этого, сюда можно включить языки явно не поддерживающие let или lambda, например Perl или Javascript.
Замыкания входят в то небольшое число любопытных концепций, парадоксальная сложность которых связана с их чрезвычайной простотой. Когда программист начинает использовать сложные решения проблем, то простые решения начинают казаться ему незавершёнными и неудобными. Далее мы увидим что замыкания могут быть более простым решением нежели решение проблемы в лоб, например организация данных и кода через замыкания может оказаться более простой чем использование объектов. Но, в замыканиях есть ещё более важное свойство чем простота: абстракции, используемые для конструирования макросов - центральная тема этой книги.
Тот факт, что мы можем строить объекты и классы с помощью примитивов замыканий не означает что объектные системы бесполезны для Лисп программистов. Это далеко не так. На самом деле COMMON LISP включает в себя одну из наиболее мощных объектных систем: CLOS, COMMON LISP Object System (Объектная Система COMMON LISP). Несмотря на то, что я очень восхищён гибкостью и функциональностью CLOS, его расширенные особенности мне редко бывают нужны (В COMMON LISP практически невозможно программировать без CLOS, поскольку CLOS занимает центральное место в COMMON LISP.), благодаря ячейкам с присваиваемыми значениями и старым добрым лямбда выражениям.
В целом эта книга предназначена для программистов со средним уровнем знания Лиспа, но в этой главе мы попытаемся обучить вас с самых основ теории и использованию замыканий, для того, чтобы ознакомить вас с общей терминологией замыканий, используемой на протяжении всей книги. В этой главе рассматривается эффективность замыканий и как современные компиляторы оптимизируют замыкания.
2.2 Среды и Пространство
Под ячейками с присваиваемым значением Стил определяет среду для сохранения ссылок к данным, где среда - это субъект чего-либо, называемый неопределённым пространством (indefinite extent). Это причудливый способ определения возможности ссылаться на такую среду в любой момент времени. Будучи единожды определённой эта среда и её ссылки будут существовать столько, сколько нам нужно. Рассмотрим следующую C функцию:
#include <stdlib.h>
int *environment_with_indefinite_extent(int input) {
int *a = malloc(sizeof(int));
*a = input;
return a;
}
После вызова этой функции и получения возвращённого указателя, мы, в течении неопределённого срока, по прежнему можем ссылаться на выделенную память. В C новые среды создаются при вызове функции, но C программисты указывают в malloc() требуемую память при возвращении её для использования за пределами функции.
Для контраста: ниже приведён бесполезный пример. C программисты рассматривают a как автоматически собираемую переменную, происходящее при возвращении функции поскольку среда выделяется в стеке. С точки зрения Лисп программистов a создаётся во временном пространстве.
int *environment_with_temporary_extent(int input) {
int a = input;
return &a;
}
Разница между средами C и Лисп в следующем: если вы явно не укажете что вам нужно, то Лисп будет предполагать что вы хотите использовать неопределённое пространство. Другими словами: Лисп всегда предполагает, что вы хотите вызвать malloc(), как в первом примере. Можно сказать, что это по своей природе менее эффективно, чем использование временного пространства, но преимущества почти всегда превышают незначительные издержки производительности. Более того, Лисп сам часто определяет, когда данные могут быть безопасно размещены в стеке и будет делать это автоматически. Вы даже можете использовать декларации для того, чтобы Лисп сам явно выполнял эту операцию. Более подробно мы будем обсуждать декларации в главе 7, Тема Макро Эффективности.
Но из-за динамичного характера, Лисп не имеет явных значений указателя или типов, как в С. Это может ввести вас в заблуждение, если вы, как программист C, используете вызов указателей и значения для определения типов. Lisp думает обо всем этом немного по-другому. В Лиспе удобно применять следующую мантру:
Переменные не имеют типов. Только значения имеют типы.
Тем не менее, мы должны возвращать что-то для хранения указателей. В Лиспе существуют множество структур данных, которые могут хранить указатели. Одна из самых любимых Лисп программистами простейшей структурой является ячейка cons (cons cell). Каждая cons ячейка содержит ровно два указателя, ласково называемые как car и cdr. При вызове environment-with-indefinite-extent ячейка cons будет вызвана с car, указывающим на переданный аргумент input, и cdr, указывающий на nil. И что наиболее важно, эта cons ячейка (и ссылка на введённый аргумент input) обладает неопределённым пространством, таким образом, мы можем ссылаться на эту ячейку столько, сколько нам нужно:
(defun environment-with-indefinite-extent (input)
(cons input nil))
Эффективность недостатков неопределённого пространства достигает неуместности как состояние искусства улучшения технологии Лисп компилирования. Среды и пространства очень тесно связаны с замыканиями. Мы ещё не раз коснёмся темы сред и состояния в этой главе.
2.3 Лексическая и Динамическая Области Видимости
Технический термин, обозначающий доступность ссылки к переменной называется областью видимости (scope). Наиболее общий тип области видимости в современных языках программирования называется лексической (lexical) областью. Когда фрагмент кода окружён лексической привязкой к переменной, то говорят что переменная расположена в лексической области привязки. С помощью формы let, наиболее универсальная форма для создания привязок, можно создавать переменные в лексической области:
* (let ((x 2))
x)
2
Доступ к x внутри тела let осуществляется через лексическую область. Аналогичным образом аргументы в функциях, определённых с помощью lambda или defun являются лексически связанными переменными в тексте определения функции. Лексические переменные - это переменные, доступ к которым возможен только из внутреннего кода контекста, для примера выше, это форма let. Поскольку лексическая область - это чрезвычайно интуитивный способ ограничения доступа к переменной, то может показаться, что это единственный способ разграничения. Есть ли другие другие способы создания областей видимости?
Комбинация неопределённого пространства и лексической области довольно долгое время не использовались в широко распространённых языках программирования. Первая реализация была разработана Стивом Расселом (Steve Russell) для Lisp 1.5 [HISTORY-OF-LISP] и впоследствии спроектирована для таких языков, как Algol-60, Scheme, и COMMON LISP. В Блабах некоторые полезные элементы лексической области видимости стали медленно реализовываться только спустя некоторое время и это несмотря на долгую и познавательную историю лексической области видимости.
Хотя способы реализации областей видимости в C-подобных языках ограничены, C программистам тоже приходится программировать в различных средах. Для этого они используют неявно определённую область видимости, также известную как область указателя (pointer scope). Область указателя известна трудностью в отладке, многочисленными рисками безопасности и, несколько искусственной эффективностью. Идея, лежащая за областью указателей - это создание проблемно-ориентированного языка для контроля регистров и памяти машины фон Неймана, похожей на большинство современных процессоров [PAIP-PIX], с последующим использованием этого языка для доступа и манипулирования структурами данных с непосредственными командами процессора. Область указателей была необходима по причинам производительности во времена, когда Лисп компиляторы ещё не были изобретены, но, теперь, в современных языках программирования область указателей скорее рассматривается как проблема, а не как особенность.
И хотя Лисп программисты редко думают в терминах указателей, понимание областей указателей бывает весьма полезным при создании эффективного Лисп кода. В разделе 7.4, Область Указателя мы будем исследовать реализацию области видимости указателя для тех редких случаев, когда нам нужно уведомить компилятор о создании специфичного кода. Но, в данный момент нам нужно только обсудить механику области указателей. В C нам иногда нужно получать доступ к переменной, определённой за пределом создаваемой функции:
#include <stdio.h>
void pointer_scope_test() {
int a;
scanf("%d", &a);
}
В вышеприведённой функции мы использовали оператор & в языке C для того, чтобы передать адрес занимаемый в памяти переменной a в функцию scanf, после этого функция scanf знает куда записывать отсканированные данные. Лексическая область видимости в Лиспе запрещает нам напрямую реализовать это действие. В Лиспе нам придётся передать подобную анонимную функцию в гипотетическую Лисп функцию scanf, что позволит ей изменить нашу лексическую переменную a, несмотря на то, что scanf определена за пределами нашей лексической области:
(let (a)
(scanf "%d" (lambda (v) (setf a v))))
Лексическая область видимости - это благоприятная среда для замыканий. По факту, замыкания настолько связаны с концепцией лексической области, что часто их более точно называют как лексические замыкания (lexical closures), для того, чтобы отделить их от других видов замыканий. Если не указано что-то другое, то по-умолчанию все замыкания в этой книге являются лексическими.
В дополнение к лексической области в Common Lisp есть ещё и динамическая область (dynamic scope). Это сленг (slang) Лиспа обозначающий комбинацию временного пространства и глобальную область. Динамическая область видимости - это одна из разновидности областей видимости. Динамическая область видимости уникальна для Лиспа тем, что предполагает отличающееся поведение с аналогичным синтаксисом лексической области. В Common Lisp переменные, доступные через динамическую область видимости, называются специальными переменными. Сделано это для того, чтобы привлечь внимание к таким переменным. Специальные переменные могут быть объявлены с помощью defvar. Некоторые программисты придерживаются соглашения, по которому имена специальных переменных следует начинать и заканчивать символом астериска, например, *temp-special*. Это соглашение называется "наушник" (earmuff). По причинам описанным в разделе 3.7, Дуализм Синтаксиса, эта книга не использует наушники, поэтому наше объявление специальных переменных выглядит так:
(defvar temp-special)
При таком определении temp-special будет помечен как специальный, но не будет инициализирован каким-либо значением. (Также мы можем указать с помощью определений локальную особенность.) В этом состоянии специальная переменная называется несвязанной (unbound). Только специальные переменные могут быть несвязанными - лексические переменные всегда связаны и поэтому всегда имеют значения. На это можно взглянуть с другой точки зрения: по-умолчанию все символы представляют из себя лексически не связанные переменные. Также как и с лексическими переменными мы можем присвоить значение специальным переменным с помощью setq или setf. Некоторые Лиспы, такие как Scheme, не имеют динамической области видимости. Другие Лиспы, такие как EuLisp [SMALL-PIECES-P46], используют один синтаксис для доступа к лексическим переменным и другой синтаксис для доступа к специальным переменным. Но в Common Lisp синтаксис общий. Многие лисперы считают это особенностью языка. Так мы присваиваем значение к нашей специальной переменной temp-special:
(setq temp-special 1)
До сих пор мы не увидели ничего такого, что выделяло бы особенность специальной переменной. Она выглядит как обычная переменная, некоторым образом привязанная к глобальному пространству имени. Всё это потому, что мы только единожды выполнили привязку - специальная глобальная привязка по умолчанию. Специальные переменные интересны тем, что по отношению к ним возможно выполнение повторной привязки, или затенения (shadowed), с помощью новой среды. Мы определим функцию просто вычисляющую и возвращающую temp-special:
(defun temp-special-returner ()
temp-special)
Функция может быть использована для получения значения, в которое Лиспом вычисляется temp-special в момент вызова:
* (temp-special-returner)
1
Иногда это называют вычислением формы в нулевую лексическую среду (null lexical environment). Очевидно, что нулевая лексическая среда не содержит никаких лексических привязок. В данном примере значение temp-special возвращается из глобального специального значения, 1. Но, если мы вычислим его в не-нулевой лексической среде - в той, которая содержит привязку для нашей специальной переменной - то здесь проявится специальность temp-special (Поскольку мы создаём динамическую привязку, но не лексическую среду. Они просто похожи друг на друга.):
* (let ((temp-special 2))
(temp-special-returner))
2
Обратите внимание, что в качестве значения была возвращена 2, это означает, что значение для temp-special было получено из нашей среды let, а не из специального глобального окружения. Если вам это всё ещё не кажется интересным, то взгляните как это невозможно выразить в большинстве других традиционных языков программирования. Ниже показан пример из псевдокода на Блабе:
int global_var = 0;
function whatever() {
int global_var = 1;
do_stuff_that_uses_global_var();
}
function do_stuff_that_uses_global_var() {
// global_var is 0
}
Расположение в памяти или значения регистров для лексических привязок становятся известными при компиляции, (По тем же причинам лексическая область видимости называется как "статическая область видимости".) а привязки для специальных переменных определяются при работе программы. Вам может показаться что специальные переменные не эффективны, но это не так. Специальная переменная всегда ссылается на одно и тоже место в памяти. При использовании let, для привязки специальной переменной, вы на самом деле компилируете код, который сохраняет копию переменной, перезаписывает участок памяти новым значением, вычисляет формы в теле let и, наконец, восстанавливает оригинальное значение из копии.
Специальные переменные постоянно связаны с символом, применяемым для их обозначения. Место в памяти, на которое ссылается специальная переменная называется ячейкой символ-значение (symbol-value) символа. Это прямое противопоставление лексическим переменным. Лексические переменные указываются символами только в момент компилирования. Поскольку доступ к лексическим переменным возможен только изнутри лексической области видимости их привязок, то компилятору нет нужды помнить о символах, применяемых в качестве ссылки на лексические переменные, поэтому компилятор удаляет их из скомпилированного кода. Мы приукрасим истинность этого высказывания в разделе 6.7, Пандорические Макросы.
Хотя Common Lisp и предоставляет нам неоценимые возможности динамической области, но, лексические переменные являются более распространёнными. Раньше динамическая область использовалась для определения особенностей Лиспа, но сейчас, с появлением Common Lisp, почти полностью заменена лексической областью.Поскольку лексическая область позволяет использовать такие приёмы, как лексические замыкания (в дальнейшем мы кратко рассмотрим их), а также более эффективную оптимизацию компилятора, то замена динамической области оказывается хорошей идеей. Однако, архитекторы Common Lisp оставили нам очень прозрачное окно в мир динамической области, которая ныне используется в более узких целях.
Let - это Лямбда
Let - это специальная Лисп форма для создания среды с именами (привязками), инициализированными в результаты вычисления соответствующих форм. Эти имена доступны для кода внутри тела let, формы в теле let вычисляются последовательно, финальным результатом let является результат вычисления последней формы. Первоочередная задача let - это сам процесс преднамеренной неопределённости. Результат работы let отделён от самой работы let. Так или иначе let нужен для предоставления структуры данных для хранения указателей на значения.
Как мы уже увидели, cons ячейки, несомненно, удобны для хранения указателей, но кроме cons ячеек для хранения указателей можно использовать ещё и другие структуры. Один из лучших путей для хранения указателей в Лиспе - это дать Лиспу возможность самому позаботиться о хранении указателей с помощью формы let. С помощью let вы только указываете имя (привязку) этих указателей, а об остальном позаботится сам Лисп. Иногда мы можем помочь компилятору в создании более эффективного кода, через передачу некоторой информации, добавляемой в форму определения.
(defun register-allocated-fixnum ()
(declare (optimize (speed 3) (safety 0)))
(let ((acc 0))
(loop for i from 1 to 100 do
(incf (the fixnum acc)
(the fixnum i)))
acc))
В примере register-allocated-fixnum мы дали некоторые подсказки компилятору, что позволяет очень эффективно просуммировать целые числа с 1 до 100. При компиляции эта функция будет располагать данные в регистрах, в целом устраняя необходимость в указателях. Несмотря на то, что с нашей точки зрения мы попросили Лисп создать неопределённую среду для хранения acc и i, Лисп компилятор может оптимизировать эту функцию сохраняя значения прямо в регистрах процессора (CPU). Сгенерированный код может быть таким:
; 090CEB52: 31C9 XOR ECX, ECX
; 54: B804000000 MOV EAX, 4
; 59: EB05 JMP L1
; 5B: L0: 01C1 ADD ECX, EAX
; 5D: 83C004 ADD EAX, 4
; 60: L1: 3D90010000 CMP EAX, 400
; 65: 7EF4 JLE L0
Заметьте, что 4 обозначает 1, а 400 обозначает 100, причина - сдвиг целых чисел на два бита в скомпилированном коде. Это связано с маркировкой (tagging) - способ представления чего-либо указателем, а на самом деле использование этого чего-либо для хранения информации. Схема маркировки нашего Лисп компилятора обладает хорошими преимуществами, благодаря которым компилятор не использует сдвиг если индексное слово помещается в памяти [DESIGN-OF-CMUCL]. Подробнее разбор Лисп компилятора будет произведён в главе 7, Тема Эффективности Макросов.
Но, если Лисп определит что позже вы можете обратиться к этой среде, то в этом случае будет использоваться что-то менее непостоянное чем регистр. Общей структурой, используемой для хранения указателей в средах, является массив. Если каждая среда имеет массив и все переменные принадлежат этой среде и ссылаются в этот массив, то мы получаем эффективную среду с потенциально неопределённым пространством.
Как было замечено выше, let будет возвращать вычисление последней формы в своём теле. Эта черта объединяет многие специальные формы и макросы Лиспа, такое поведение является настолько общим, что этот шаблон часто называют неявным progn (implicit progn) поскольку специальная форма progn реализует именно это поведение (Progn используется для кластеризации форм и наделяет их высокоуровневым поведением.). Иногда весьма удобно использовать let форму через возвращение анонимной функции, пользующейся той-же лексической средой, что доступна из формы let. Для создания этих функций в Лиспе мы используем лямбду (lambda).
Лямбда - это простая концепция, способная напугать своей гибкостью и важностью. Лямбда, применяемая в Лиспе и Схеме, восходит к логической системе Алонзо Чёрча, но, лямбда получила развитие под спецификацией Лиспа. Лямбда - это короткий способ повторного присваивания временных имён (привязок) к значениям для определённого лексического контекста и лежит в основе концепции Лисп функции. Лисп функция очень отличается от Чёрчевского описания математической функции. Это произошло по причине того, что лямбда развивалась как мощный, практичный инструмент в руках многих поколений лисперов, совершенствующих и расширяющих лямбду до такой степени, предвидеть которую не могли ранние логики.
Несмотря на благоговение Лисп программистов по отношению к лямбде, в ней нет ничего особенного. В дальнейшем мы увидим, что лямбда всего лишь один из многих способов выражения этой разновидности именования переменных. В частности, мы увидим, что макросы позволяют нам изменять переименование переменных такими способами, которые абсолютно невозможны в других языках программирования. После изучения таких макросов мы вернёмся к лямбде и обнаружим что лямбда наиболее удобна для оптимального выражения такого рода именования. Это не случайно. С точки зрения программных сред нашего времени Чёрч может показаться устаревшим и неуместным, но на самом деле его вклад нельзя умалить. Его математическая нотация с многочисленными улучшениями в руках многих поколений Лисп профессионалов развилась в универсальный и гибкий инструмент (Классический пример макроса - это реализация let в лямбда форме. В этой книге я не буду утомлять вас этим примером.).
Лямбда, как и многие другие особенности Лиспа, очень удобна, самые современные языки начинают импортировать идеи из Лиспа в их собственные системы. Некоторым разработчикам языков кажется что "lambda" - это очень длинно, и они начинают использовать такие аббревиатуры как fn и другие. С другой стороны, концепция лямбды настолько фундаментальна, что скрытие этого названия менее длинным именем граничит с ересью. В этой книге мы будем описывать и изучать многие разновидности лямбды и по доброй традиции будем называть лямбду лямбдой так же, как и поколения Лисп программистов до нас.
Но как выглядит лямбда в Лиспе? Прежде всего, как и все имена в Лиспе, лямбда - это символ (symbol). Мы можем закавычивать его, сравнивать его и хранить его в списках. Лямбда обретает специальный смысл только когда появляется в виде первого элемента списка. Если это случится, то список называют лямбда формой (lambda form) или определением функции (function designator). Но эта форма - не функция. Эта форма - списковая структура данных, которая может быть преобразована в функцию с помощью специальной формы function:
* (function ’(lambda (x) (+ 1 x)))
#<Interpreted Function>
Для удобства работы с предыдущим выражением в Common Lisp есть сокращение в виде считывающего макроса #' (шарп-кавычка). Вместо того, чтобы писать function вы можете получить тот-же эффект с помощью этого сокращения:
* #’(lambda (x) (+ 1 x))
#<Interpreted Function>
Для дополнительного удобства, лямбда определяется как макрос, расширяющийся в специальную форму с вызовом function, как в примере выше. Стандарт Common Lisp ANSI требует [ANSI-CL-ISO-COMPATIBILITY] чтобы макрос lambda определялся примерно так:
(defmacro lambda (&whole form &rest body)
(declare (ignore body))
‘#’ ,form)
В данный момент не следует обращать внимание на определение игнорирования (7 Определение U-Языка) 7. Этот макрос всего лишь простой способ автоматического применения специальной формы function к вашему определению функции. Этот макрос позволяет нам вычислить определение функции для создания функций, поскольку они расширяются в формы шарп-кавычка:
* (lambda (x) (+ 1 x))
#<Interpreted Function>
Есть несколько веских причин, по которым нужно предварять лямбда формы шарп-кавычкой #'. Поскольку эта книга не ставит целью поддержку предыдущих сред ANSI Common Lisp, то обратная совместимость соблюдаться не будет. А как же стилистические возражения? Пол Грэм, в ANSI Common Lisp [GRAHAM-ANSI-CL], высказался что краткость этого макроса является "в лучшем случае показной элегантностью". Возражение Грэма сводится к тому, что пока вам приходится использовать шарп-кавычку для функций, на которые ссылаются символы, то система становится асимметричной. Однако, я считаю, что не шарп-закавыченные лямбда формы являются стилистическим улучшением, поскольку они подсвечивают асимметрию, присутствующую в спецификации второго пространства имён. Использование шарп-кавычки для символов - это способ сослаться ко второму пространству имён, в то время когда функции, созданные лямбда формами, конечно, являются безымянными.
Даже не ссылаясь на макрос lambda вы можете использовать лямбда формы в виде первого аргумента в вызове функции. Тут Лисп действует также, как и в случае с символом: если символ будет обнаружен первым элементом списка, то считается что мы ссылаемся на ячейку symbol-function (функция-символа), если же будет обнаружена лямбда, то предполагается подстановка анонимной функции:
* ((lambda (x) (+ 1 x)) 2)
3
Следует помнить, что также, как вы не можете вызывать функцию для динамического возвращения символа, используемого в обычном вызове функции, вы не можете вызывать функцию, возвращающую лямбда форму в позиции функции. Для обоих задач используйте или funcall или apply.
Большое превосходство лямбда выражений перед функциями в C и других языках в том, что Лисп компиляторы часто могут полностью оптимизировать их. Например, compiler-test выглядит так, как будто он применяет инкрементирующую функцию к числу 2 и возвращает результат, но тут хороший компилятор должен быть достаточно умным, чтобы определить, что функция всегда возвращает значение 3 и просто прямо возвращать это значение, не вызывая никаких функций в процессе работы. Это называется лямбда сворачиванием (lambda folding):
(defun compiler-test ()
(funcall
(lambda (x) (+ 1 x))
2))
При наблюдении можно выявить эффективность скомпилированной лямбда формы: скомпилированная лямбда форма является постоянной формой. Это означает что если ваша программа будет скомпилирована, все ссылки на эту функцию будут простыми указателями на некоторый кусок машинного кода. Этот указатель может быть возвращён из функций и встроен в новые среды без накладных расходов, связанных с созданием функции. Накладные расходы будут устранены в момент компилирования программы. Другими словами, функция, возвращающая другую функцию будет просто постоянным указателем, возвращающим функцию:
(defun lambda-returner ()
(lambda (x) (+ 1 x)))
Прямой противоположностью является форма let, спроектированная для создания новой среды во время выполнения программы, как правило let не постоянная операция, поскольку возникают накладные расходы из-за сборки мусора в лексических замыканиях, которые представляют неопределённое пространство.
(defun let-over-lambda-returner ()
(let ((y 1))
(lambda (x)
(incf y x))))
При каждом вызове let-over-lambda-returner необходимо создавать новую среду, вставлять указатель на константу в код лямбда формы в этой новой среде, затем вернуть результирующее замыкание. Для того, чтобы увидеть насколько мала эта среда вы можете использовать time.
* (progn
(compile ’let-over-lambda-returner)
(time (let-over-lambda-returner)))
; Evaluation took:
; ...
; 24 bytes consed.
; ...
#<Closure Over Function>
Если вы вызовите компиляцию замыкания, то получите сообщение об ошибке, гласящее о невозможности компилирования функций определённых в не нулевой лексической среде [CLTL2-P677]. Вы не можете компилировать замыкания, компилируются только функции, которые создают замыкания. Когда вы компилируете функцию, создающую замыкания, то эти замыкания также будут скомпилированы [ON-LISP-P25].
Использование let в купе с лямбдой является настолько важной идеей, что оставшуюся часть этой главы мы проведём обсуждая их шаблоны и вариации.
2.5 Лямбда окружённая Let'ом
Лямбда, окружённая Let'ом (Let over lambda), - это прозвище данное лексическому замыканию. Лямбда окружённая Let'ом, по сравнению с другими терминологиями, наиболее полно отражает Лисп код, используемый для создания замыканий. В сценарии лямбды, окружённой let'ом, последняя форма, возвращаемая let конструкцией - это lambda выражение. Буквально это можно представить как let находящийся над lambda:
* (let ((x 0))
(lambda () x))
#<Interpreted Function>
Напомним, что форма let возвращает результат вычисления его последней формы внутри своего тела, поэтому вычисление этой формы лямбды, окружённой let'ом приводит к созданию функции. Однако, в последней форме let есть нечто особенное. Это lambda форма с x в качестве свободной переменной (free variable). Лисп достаточно умён и сам определяет куда, в этой функции, должен ссылаться x: x из внешнего лексического окружения создан let формой. А поскольку в Лиспе, по умолчанию, всё является неопределённым пространством, то эта среда будет доступна функции так долго, сколько нам это будет необходимо.
Лексическая область видимости - это инструмент для точного определения действительности ссылок на переменные и указания куда именно ссылается каждая ссылка. Простым примером замыкания является счётчик (counter), замыкание, которые сохраняет целочисленное значение в среде, инкрементирует и возвращает значение при каждом обращении. Ниже представлена типичная реализация с помощью лямбды, окружённой let'ом:
(let ((counter 0))
(lambda () (incf counter)))
Это замыкание вернёт 1 при первом вызове, 2 при последующем вызове и так далее. Ещё один способ думать о замыканиях - это представить их в виде функций с состоянием. Эти функции нельзя назвать математическими функциями, это скорее процедуры, в каждой из которых есть своя маленькая память. Иногда структуры данных, объединяющих вместе код и данные называются объектами (objects). Объект - это коллекция процедур и некоторого связанного состояния. Поскольку объекты очень близки к замыканиям, то часто они могут рассматриваться как одно и тоже. Замыкание похоже на объект, имеющий только один метод: funcall. Объект похож на замыкание, к которому можно применить funcall несколькими способами.
Хотя замыкания являются единственной функцией, но, окружающая среда, множественные методы, внутренние классы и статические переменные объектной системы, все они обладают своими замыкающими двойниками. Один из возможных путей эмуляции множественных методов - это просто вернуть множественные lambda'ы изнутри той же лексической области видимости:
(let ((counter 0))
(values
(lambda () (incf counter))
(lambda () (decf counter))))
Этот шаблон, Let, окружающий две лямбды, возвращает две функции, они оба получают доступ к одной и той же окружающей их переменной-счётчик. Первая функция инкрементирует счётчик, а вторая функция декрементирует счётчик. Есть много других способов реализации такого поведения. Один из этих способов, dlambda, обсуждён в разделе 5.7, Dlambda. По причинам, которые будут разъяснены позже, код в этой книге будет структурировать данные с помощью замыканий, а не объектов. Подсказка: Это связано с макросами.
2.6 Лямбда, окружающая Let, окружающий Лямбду
В некоторых объектных системах есть чёткая граница между объектами, набором процедур со связанным состоянием и классами, структурами данных, используемыми для создания объектов. В замыканиях такой границы не существует. Мы увидим примеры форм, которые вы можете вычислять для создания замыканий, большинство из них следуют шаблону let, окружающий лямбду, но каким образом наши программы могут создавать эти объекты по мере надобности?
Ответ на этот вопрос чрезвычайно прост. Если мы можем вычислить что-то в REPL, то мы можем вычислить это что-то и в функции. Что если мы создадим функцию, единственным назначением которой будет вычисление let, окружающий лямбду, и возвращение получившегося результата? Поскольку для представления функции мы используем lambda, то у нас получится нечто, похожее на такой код:
(lambda ()
(let ((counter 0))
(lambda () (incf counter))))
При вызове лямбды, окружающей let, окружающий лямбду, (lambda over let over lambda) создаётся и возвращается новое замыкание, содержащее привязку счётчика. Помните, что lambda выражения являются константами: простыми указателями на машинный код. Это выражение - простой кусок кода, создающий новые среды, замыкающие внутреннее lambda выражение (само по себе являющееся константой, скомпилированной формой) - то-же самое, что мы выполняли в REPL'е.
В объектной системе, часть кода, создающего объекты называется классом. Но, лямбда, окружающая let, окружающий лямбду, немного отличается от классов во многих языках. В то время, когда во многих языках классам требуется давать имена, этот шаблон полностью избегает именования. Формы вида лямбды, окружающей let, окружающий лямбду, можно называть анонимными классами (anonymous classes).
Хотя анонимные классы часто бывают полезны, мы, обычно, даём имена классам. Самый лёгкий путь именования классов - это рассматривать классы как обычные функции. Как мы, обычно, именуем функции? Конечно, с помощью формы defun. После именования вышеприведённый анонимный класс приобретает следующий вид:
(defun counter-class ()
(let ((counter 0))
(lambda () (incf counter))))
Где начинается первая lambda? Defun создаёт неявную лямбду (implicit lambda) вокруг формы в своём теле. Когда вы пишете обычную функцию с помощью defun, то, внутренне, вы по прежнему используете те же лямбда формы, но, этот факт скрывается за поверхностью синтаксиса defun.
К несчастью большинство книг, посвящённых программированию на Лиспе, не приводят реалистичных примеров использования замыканий, и читатель заблуждается, считая, что замыкания - это такая идея, которую можно применять только для таких игрушечных приёмов, как счётчики. Ничто не может быть так далеко от истины, как это высказывание. Замыкания - это строительные блоки Лиспа. Среды, функции, определённые внутри этих сред и макросы как defun, упрощающие их использование - это всё, что нужно для моделирования любой проблемы. Цель этой книги - научить начинающих Лисп программистов, ранее работавших с объектно-ориентированными языками, не идти на поводу своей интуиции к таким системам, как CLOS. Не стоит использовать CLOS там, где достаточно лямбды, даже несмотря на то, что CLOS предлагает ряд преимуществ профессиональным Лисп программистам.
Для того, чтобы мотивировать использование замыканий, представляю вам реалистичный пример: block-scanner. Для какой задачи предназначен block-scanner? В некоторых формах передачи данных данные передаются в группах (блоках) неопределённых размеров. В основном, эти размеры удобны для нижележащей системы, но, неудобны для программиста приложения поскольку часто размеры определяются такими факторами как буферы операционной системы, блоки жёсткого диска или сетевые пакеты. При этом сканирование потока данных на определённую последовательность значительно усложняется по сравнению со сканированием отдельно взятого блока с помощью обычной процедурой без состояния. Нам приходится сохранять состояние между сканированием каждого блока, поскольку есть вероятность что искомая последовательность будет разделена между двумя (или более) блоками.
Листинг 2.1: BLOCK-SCANNER
(defun block-scanner (trigger-string)
(let* ((trig (coerce trigger-string 'list))
(curr trig))
(lambda (data-string)
(let ((data (coerce data-string 'list)))
(dolist (c data)
(if curr
(setq curr
(if (char= (car curr) c)
(cdr curr) ; следующий символ
trig)))) ; начать снова
(not curr))))) ; вернуть t при обнаружении последовательности
Самым простым и естественным способом реализации этого хранимого состояния в современных языках программирования является замыкание. Начальным эскизом сканера блоков, основанного на замыкании является вышеприведённый block-scanner. Так же, как и всё остальное в Лисп разработке, создание замыканий представляет из себя итеративный процесс. Мы должны начать с кода в block-scanner и постепенно улучшать его. Например: мы можем увеличить его эффективность отказавшись от преобразования строк в списки, или мы можем улучшить информативность, подсчитывая количество появления искомых последовательностей в блоках.
И хотя block-scanner является всего лишь начальной реализацией и её ещё предстоит улучшить, она вполне пригодна для демонстрации использования лямбды, окружающей let, окружающий лямбду. Вот демонстрация его использования, в роли коммуникативного фильтра, наблюдающего за определёнными словами, находящимися в чёрном списке, например jihad (джихад):
* (defvar scanner
(block-scanner "jihad"))
SCANNER
* (funcall scanner “We will start ")
NIL
# (funcall scanner "the ji")
NIL
* (funcall scanner "had tomorrow.")
T
2.7 Let, окружающий Лямбду, окружающая Let, окружающий Лямбду
Пользователи объектных систем сохраняют значения, предназначенные для общего использования всеми объектами определённого класса, в так называемые переменные класса (class variables) или статические переменные (static variables) 8. В Лиспе эта концепция разделения состояния между замыканиями обрабатывается средами тем же способом, каким замыкания сохраняют свои состояния. Поскольку доступность среды не ограничена и доступ к ней возможен до тех пор пока мы ссылаемся к ней, то наша среда будет доступна столько, сколько нам будет нужно.
8 Термин статический (static) - это один из наиболее перегруженных терминов в языках программирования. Значения, разделяемые всеми объектами класса называются статическими переменными в таких языках, как Java, что отдалённо связано со значениями статичности в C.
Если мы хотим реализовать глобальное изменение для всех счётчиков, up для инкрементирования счётчика каждого замыкания и down для декрементирования, то нам нужно использовать шаблон let, окружающий лямбду, окружающую let, окружающий лямбду:
(let ((direction ’up))
(defun toggle-counter-direction ()
(setq direction
(if (eq direction ’up)
’down
’up)))
(defun counter-class ()
(let ((counter 0))
(lambda ()
(if (eq direction ’up)
(incf counter)
(decf counter))))))
В вышеприведённом примере мы расширили counter-class из предыдущего раздела. Теперь вызов замыканий, созданных с counter-class либо инкрементирует значение счётчика привязки, либо декрементирует его в зависимости от значения привязки направления, общего для всех счётчиков. Заметьте, что мы также воспользовались другой lambda, внутри среды направления, создав функцию под названием toggle-counter-direction, которая изменяет текущее направление для всех счётчиков.
И хотя комбинация let и lambda оказываются настолько полезными, что другие языки адаптируют их в форме классовых или статических переменных, существуют другие комбинации let и lambda, позволяющие вам структурировать код и состояния такими способами, которые не имеют прямых аналогов в объектных системах 9. Объектные системы - это формализация подмножества комбинаций let и lambda, иногда в эту формализацию включаются такие трюки, как наследование 10. По этой причине Лисп программисты редко мыслят в рамках классов и объектов. Let и лямбда - фундаментальны; объекты и классы - производные. Как говорит Стил: "объекты" не должны быть примитивами в языках программирования. Если нам доступны ячейки с присваиваемыми значениями и старые добрые лямбда выражения, то объектные системы, в лучшем случае, иногда оказываются полезными, а в худшем случае, узко специализированы и избыточны.
9 Но, иногда, эти аналоги можно создавать на основе объектных систем.
10 Доступность макросов неизмеримо важнее доступности наследования.
Переведено на Нотабеноиде
http://notabenoid.org/book/40014/155038
Переводчики: Charlz_Klug
Настройки
Готово:
100.00%
КП = 1.0