Let Over Lambda - 50 Years of Lisp / Let Over Lambda - 50 лет Lisp-у: Глава 2 - Замыкания

2.1 Замыкание-Ориентированное Программирование

Charlz_Klug 07.06.13 в 05:24

Один из выводов к которому мы пришли был следующим: "объект" не должен быть примитивным понятием в языке программирования; объекты и их поведение должны строиться из значений ячеек и старых добрых лямбда выражений.
- Гай Стил во время разработки Scheme

Charlz_Klug 07.06.13 в 05:32

Иногда это называется замыканием (closure), в других случаях - сохранённым лексическим окружением. Или, как любят говорить некоторые из нас - let, окружающий lambda (let over lambda). Вне зависимости от используемой терминологии, усвоение концепции замыканий - это первый шаг в становлении профессионального Лисп программиста. По факту, это умение является жизненно необходимым для правильного использования многих современных языков программирования, кроме этого, сюда можно включить языки явно не поддерживающие let или lambda, например Perl или Javascript.

Charlz_Klug 07.06.13 в 05:52

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

Charlz_Klug 07.06.13 в 06:05

Тот факт, что мы можем строить объекты и классы с помощью примитивов замыканий не означает что объектные системы бесполезны для Лисп программистов. Это далеко не так. На самом деле COMMON LISP включает в себя одну из наиболее мощных объектных систем: CLOS, COMMON LISP Object System (Объектная Система COMMON LISP). Несмотря на то, что я очень восхищён гибкостью и функциональностью CLOS, его расширенные особенности мне редко бывают нужны (В COMMON LISP практически невозможно программировать без CLOS, поскольку CLOS занимает центральное место в COMMON LISP.), благодаря ячейкам с присваиваемыми значениями и старым добрым лямбда выражениям.

Charlz_Klug 07.06.13 в 09:39

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

Charlz_Klug 07.06.13 в 10:16

2.2 Среды и Пространство

Charlz_Klug 10.06.13 в 09:48

Под ячейками с присваиваемым значением Стил определяет среду для сохранения ссылок к данным, где среда - это субъект чего-либо, называемый неопределённым пространством (indefinite extent). Это причудливый способ определения возможности ссылаться на такую среду в любой момент времени. Будучи единожды определённой эта среда и её ссылки будут существовать столько, сколько нам нужно. Рассмотрим следующую C функцию:

Charlz_Klug 10.06.13 в 10:07

#include <stdlib.h>
int *environment_with_indefinite_extent(int input) {
int *a = malloc(sizeof(int));
*a = input;
return a;
}

Charlz_Klug 10.06.13 в 10:12

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

Charlz_Klug 10.06.13 в 10:33

Для контраста: ниже приведён бесполезный пример. C программисты рассматривают a как автоматически собираемую переменную, происходящее при возвращении функции поскольку среда выделяется в стеке. С точки зрения Лисп программистов a создаётся во временном пространстве.

Charlz_Klug 11.06.13 в 03:24

int *environment_with_temporary_extent(int input) {
int a = input;
return &a;
}

Charlz_Klug 11.06.13 в 03:25

Разница между средами C и Лисп в следующем: если вы явно не укажете что вам нужно, то Лисп будет предполагать что вы хотите использовать неопределённое пространство. Другими словами: Лисп всегда предполагает, что вы хотите вызвать malloc(), как в первом примере. Можно сказать, что это по своей природе менее эффективно, чем использование временного пространства, но преимущества почти всегда превышают незначительные издержки производительности. Более того, Лисп сам часто определяет, когда данные могут быть безопасно размещены в стеке и будет делать это автоматически. Вы даже можете использовать декларации для того, чтобы Лисп сам явно выполнял эту операцию. Более подробно мы будем обсуждать декларации в главе 7, Тема Макро Эффективности.

Charlz_Klug 11.06.13 в 04:05

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

Charlz_Klug 11.06.13 в 04:27

Переменные не имеют типов. Только значения имеют типы.

Charlz_Klug 11.06.13 в 04:29

Тем не менее, мы должны возвращать что-то для хранения указателей. В Лиспе существуют множество структур данных, которые могут хранить указатели. Одна из самых любимых Лисп программистами простейшей структурой является ячейка cons (cons cell). Каждая cons ячейка содержит ровно два указателя, ласково называемые как car и cdr. При вызове environment-with-indefinite-extent ячейка cons будет вызвана с car, указывающим на переданный аргумент input, и cdr, указывающий на nil. И что наиболее важно, эта cons ячейка (и ссылка на введённый аргумент input) обладает неопределённым пространством, таким образом, мы можем ссылаться на эту ячейку столько, сколько нам нужно:

Charlz_Klug 11.06.13 в 04:56

(defun environment-with-indefinite-extent (input)
(cons input nil))

Charlz_Klug 11.06.13 в 09:05

Эффективность недостатков неопределённого пространства достигает неуместности как состояние искусства улучшения технологии Лисп компилирования. Среды и пространства очень тесно связаны с замыканиями. Мы ещё не раз коснёмся темы сред и состояния в этой главе.

Charlz_Klug 11.06.13 в 09:19

2.3 Лексическая и Динамическая Области Видимости

Charlz_Klug 12.06.13 в 04:44

Технический термин, обозначающий доступность ссылки к переменной называется областью видимости (scope). Наиболее общий тип области видимости в современных языках программирования называется лексической (lexical) областью. Когда фрагмент кода окружён лексической привязкой к переменной, то говорят что переменная расположена в лексической области привязки. С помощью формы let, наиболее универсальная форма для создания привязок, можно создавать переменные в лексической области:

Charlz_Klug 12.06.13 в 04:57

* (let ((x 2))
x)

2

Charlz_Klug 12.06.13 в 06:57

Доступ к x внутри тела let осуществляется через лексическую область. Аналогичным образом аргументы в функциях, определённых с помощью lambda или defun являются лексически связанными переменными в тексте определения функции. Лексические переменные - это переменные, доступ к которым возможен только из внутреннего кода контекста, для примера выше, это форма let. Поскольку лексическая область - это чрезвычайно интуитивный способ ограничения доступа к переменной, то может показаться, что это единственный способ разграничения. Есть ли другие другие способы создания областей видимости?

Charlz_Klug 12.06.13 в 07:12

Комбинация неопределённого пространства и лексической области довольно долгое время не использовались в широко распространённых языках программирования. Первая реализация была разработана Стивом Расселом (Steve Russell) для Lisp 1.5 [HISTORY-OF-LISP] и впоследствии спроектирована для таких языков, как Algol-60, Scheme, и COMMON LISP. В Блабах некоторые полезные элементы лексической области видимости стали медленно реализовываться только спустя некоторое время и это несмотря на долгую и познавательную историю лексической области видимости.

Charlz_Klug 12.06.13 в 09:36

Хотя способы реализации областей видимости в C-подобных языках ограничены, C программистам тоже приходится программировать в различных средах. Для этого они используют неявно определённую область видимости, также известную как область указателя (pointer scope). Область указателя известна трудностью в отладке, многочисленными рисками безопасности и, несколько искусственной эффективностью. Идея, лежащая за областью указателей - это создание проблемно-ориентированного языка для контроля регистров и памяти машины фон Неймана, похожей на большинство современных процессоров [PAIP-PIX], с последующим использованием этого языка для доступа и манипулирования структурами данных с непосредственными командами процессора. Область указателей была необходима по причинам производительности во времена, когда Лисп компиляторы ещё не были изобретены, но, теперь, в современных языках программирования область указателей скорее рассматривается как проблема, а не как особенность.

Charlz_Klug 12.06.13 в 10:35

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

Charlz_Klug 12.06.13 в 13:38

#include <stdio.h>
void pointer_scope_test() {
int a;
scanf("%d", &a);
}

Charlz_Klug 12.06.13 в 13:39

В вышеприведённой функции мы использовали оператор & в языке C для того, чтобы передать адрес занимаемый в памяти переменной a в функцию scanf, после этого функция scanf знает куда записывать отсканированные данные. Лексическая область видимости в Лиспе запрещает нам напрямую реализовать это действие. В Лиспе нам придётся передать подобную анонимную функцию в гипотетическую Лисп функцию scanf, что позволит ей изменить нашу лексическую переменную a, несмотря на то, что scanf определена за пределами нашей лексической области:

Charlz_Klug 13.06.13 в 03:51

(let (a)
(scanf "%d" (lambda (v) (setf a v))))

Charlz_Klug 13.06.13 в 03:52

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

Charlz_Klug 13.06.13 в 06:58

В дополнение к лексической области в Common Lisp есть ещё и динамическая область (dynamic scope). Это сленг (slang) Лиспа обозначающий комбинацию временного пространства и глобальную область. Динамическая область видимости - это одна из разновидности областей видимости. Динамическая область видимости уникальна для Лиспа тем, что предполагает отличающееся поведение с аналогичным синтаксисом лексической области. В Common Lisp переменные, доступные через динамическую область видимости, называются специальными переменными. Сделано это для того, чтобы привлечь внимание к таким переменным. Специальные переменные могут быть объявлены с помощью defvar. Некоторые программисты придерживаются соглашения, по которому имена специальных переменных следует начинать и заканчивать символом астериска, например, *temp-special*. Это соглашение называется "наушник" (earmuff). По причинам описанным в разделе 3.7, Дуализм Синтаксиса, эта книга не использует наушники, поэтому наше объявление специальных переменных выглядит так:

Charlz_Klug 13.06.13 в 09:33

(defvar temp-special)

Charlz_Klug 13.06.13 в 09:34

При таком определении temp-special будет помечен как специальный, но не будет инициализирован каким-либо значением. (Также мы можем указать с помощью определений локальную особенность.) В этом состоянии специальная переменная называется несвязанной (unbound). Только специальные переменные могут быть несвязанными - лексические переменные всегда связаны и поэтому всегда имеют значения. На это можно взглянуть с другой точки зрения: по-умолчанию все символы представляют из себя лексически не связанные переменные. Также как и с лексическими переменными мы можем присвоить значение специальным переменным с помощью setq или setf. Некоторые Лиспы, такие как Scheme, не имеют динамической области видимости. Другие Лиспы, такие как EuLisp [SMALL-PIECES-P46], используют один синтаксис для доступа к лексическим переменным и другой синтаксис для доступа к специальным переменным. Но в Common Lisp синтаксис общий. Многие лисперы считают это особенностью языка. Так мы присваиваем значение к нашей специальной переменной temp-special:

Charlz_Klug 13.06.13 в 10:31

(setq temp-special 1)

Charlz_Klug 13.06.13 в 10:31

До сих пор мы не увидели ничего такого, что выделяло бы особенность специальной переменной. Она выглядит как обычная переменная, некоторым образом привязанная к глобальному пространству имени. Всё это потому, что мы только единожды выполнили привязку - специальная глобальная привязка по умолчанию. Специальные переменные интересны тем, что по отношению к ним возможно выполнение повторной привязки, или затенения (shadowed), с помощью новой среды. Мы определим функцию просто вычисляющую и возвращающую temp-special:

Charlz_Klug 14.06.13 в 06:56

(defun temp-special-returner ()
temp-special)

Charlz_Klug 14.06.13 в 06:56

Функция может быть использована для получения значения, в которое Лиспом вычисляется temp-special в момент вызова:

Charlz_Klug 14.06.13 в 09:27

* (temp-special-returner)

1

Charlz_Klug 14.06.13 в 09:27

Иногда это называют вычислением формы в нулевую лексическую среду (null lexical environment). Очевидно, что нулевая лексическая среда не содержит никаких лексических привязок. В данном примере значение temp-special возвращается из глобального специального значения, 1. Но, если мы вычислим его в не-нулевой лексической среде - в той, которая содержит привязку для нашей специальной переменной - то здесь проявится специальность temp-special (Поскольку мы создаём динамическую привязку, но не лексическую среду. Они просто похожи друг на друга.):

Charlz_Klug 14.06.13 в 09:59

* (let ((temp-special 2))
(temp-special-returner))

2

Charlz_Klug 14.06.13 в 10:00

Обратите внимание, что в качестве значения была возвращена 2, это означает, что значение для temp-special было получено из нашей среды let, а не из специального глобального окружения. Если вам это всё ещё не кажется интересным, то взгляните как это невозможно выразить в большинстве других традиционных языков программирования. Ниже показан пример из псевдокода на Блабе:

Charlz_Klug 14.06.13 в 11:01

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
}

Charlz_Klug 14.06.13 в 11:03

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

Charlz_Klug 14.06.13 в 11:29

Специальные переменные постоянно связаны с символом, применяемым для их обозначения. Место в памяти, на которое ссылается специальная переменная называется ячейкой символ-значение (symbol-value) символа. Это прямое противопоставление лексическим переменным. Лексические переменные указываются символами только в момент компилирования. Поскольку доступ к лексическим переменным возможен только изнутри лексической области видимости их привязок, то компилятору нет нужды помнить о символах, применяемых в качестве ссылки на лексические переменные, поэтому компилятор удаляет их из скомпилированного кода. Мы приукрасим истинность этого высказывания в разделе 6.7, Пандорические Макросы.

Charlz_Klug 14.06.13 в 13:57

Хотя Common Lisp и предоставляет нам неоценимые возможности динамической области, но, лексические переменные являются более распространёнными. Раньше динамическая область использовалась для определения особенностей Лиспа, но сейчас, с появлением Common Lisp, почти полностью заменена лексической областью.Поскольку лексическая область позволяет использовать такие приёмы, как лексические замыкания (в дальнейшем мы кратко рассмотрим их), а также более эффективную оптимизацию компилятора, то замена динамической области оказывается хорошей идеей. Однако, архитекторы Common Lisp оставили нам очень прозрачное окно в мир динамической области, которая ныне используется в более узких целях.

Charlz_Klug 14.06.13 в 14:18

Let - это Лямбда

Charlz_Klug 26.06.13 в 09:22

Let - это специальная Лисп форма для создания среды с именами (привязками), инициализированными в результаты вычисления соответствующих форм. Эти имена доступны для кода внутри тела let, формы в теле let вычисляются последовательно, финальным результатом let является результат вычисления последней формы. Первоочередная задача let - это сам процесс преднамеренной неопределённости. Результат работы let отделён от самой работы let. Так или иначе let нужен для предоставления структуры данных для хранения указателей на значения.

Charlz_Klug 17.06.13 в 10:57

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

Charlz_Klug 17.06.13 в 11:26

(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))

Charlz_Klug 18.06.13 в 03:19

В примере register-allocated-fixnum мы дали некоторые подсказки компилятору, что позволяет очень эффективно просуммировать целые числа с 1 до 100. При компиляции эта функция будет располагать данные в регистрах, в целом устраняя необходимость в указателях. Несмотря на то, что с нашей точки зрения мы попросили Лисп создать неопределённую среду для хранения acc и i, Лисп компилятор может оптимизировать эту функцию сохраняя значения прямо в регистрах процессора (CPU). Сгенерированный код может быть таким:

Charlz_Klug 18.06.13 в 04:16

; 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

Charlz_Klug 18.06.13 в 04:20