(ЖЖ не дал мне запостить это одной записью, говорит "post too large". Разбиваю на две части поэтому)
Продолжение наброска. Весь код, как и раньше, выкладывается на github/avorobey/sketch.
-----<<<<<<< предыдущий припадок-----------------------<<<<<< первый припадок---------------
Примерный план: к концу этого припадка я хочу иметь полную поддержку лексической видимости переменных, создания
и правильного вызова замыканий (closures).
---------------------tutorial-----------
Для того, чтобы понять, как устроены переменные в Схеме, стоит понять разницу между лексической и динамической видимостью (lexical/dynamic scope). Если вы знакомы с C, то знаете, что такое лексические переменные. Это значит просто-напросто, что когда в исходном коде написано 'x', то это относится к самому ближнему определению x в тексте программы, двигаясь по блокам кода изнутри наружу. "Лексический" надо понимать, как "организованный, как в тексте программы".
void foo() {
int x=5;
.....
while (...) {
int x=7;
.....
printf("%d\n", x);
}
}
int x = 10;
foo();
Во многих современных языках есть только лексические переменные, и это самая обычная ситуация. Но есть также языки с динамическими переменными. В таких языках, если вы напишете x=10, а потом вызовете какую-то другую функцию, и эта функция будет оперировать значением x, то она "увидит" именно 10. Программистам, привыкшим к лексическим переменным, не очень легко понять, зачем такое может быть нужно. Обычно для объяснения этого приводят в пример ситуацию, когда поведением многих функций управляет какой-то важный параметр. Например, logLevel, outputBase (в каком счислении печатать все числа), итд. Измени logLevel, и все функции, которые ты вызовешь, автоматически "увидят" это новое значение. Конечно, это можно симулировать в "лексическом" языке, сделав logLevel глобальной переменной (если глобальных переменных нет, как в Джаве, то можно посадить ее в какой-то синглтон, итд.). В принципе, динамические переменные можно представлять как своего рода глобальные, хотя "настоящая" поддержка динамических переменных может быть сложнее и полезнее глобальных; например, она может поддерживать многопоточные программы - у каждого потока свое значение одной и той же динамической переменной.
Так или иначе, в Схеме все переменные лексические, "как в C". Есть другие варианты Лиспа, которые поддерживают динамические переменные, или и те и другие, но Схема - не один из них. Все переменные 'видны' только внутри того блока текста программы, в котором они определены. Один способ определить переменную я уже описывал - с помощью define. Другой способ, особенно полезный внутри функций - let. Специальная форма let, у которой есть несколько разновидностей, но я опишу только одну главную, определяет новые переменные с данными именами, дает им начальные значения, и выполняет "тело" - набор команд, которые могут обращаться к этим переменным и их "видеть"; вне тела никто их увидеть не может.
(define x "banana")
(define foo (lambda ()
(let ((x 0) (y "abc"))
(set! x (+ x 10)) (bar y x))
(bar x x)))
В этом примере у функции нет аргументов (пустой список () у лямбды), но когда они есть, их "видимость" тоже ограничивается телом функции, как в C. Их тоже можно "перекрыть" внутренним let с использованием того же имени, и так далее.
Новые функции в Схеме, как я упоминал в прошлый раз, определяются с помощью специальной формы lambda. На первый взгляд она играет ту же роль, что определение функции в C, но на самом деле не совсем. Понять разницу легко, если научиться четко различать, когда какая-то строка исходного кода на данном языке означает, что надо что-то сделать во время работы программы (в рантайме, runtime), а когда - указание компилятору (или интерпретатору, неважно), меняющее что-то в интерпретации других строк кода. Иногда одна и та же строка содержит и то и другое - и полезно понимать разницу.
На самом деле это легко увидеть в том же C. Строка "int x;" ничего не делает с точки зрения рантайма, но после этой строки 'x' будет указывать на новое место. Компилятор C поймет ее и организует место для x во всех вызовах данной функции. С другой стороны, строка "x = 5;" содержит действие, которое надо произвести во время исполнения. От этой строки смысл 'x' или чего-либо еще в последующих строках не меняется. А если я напишу "int x = 5;", то эта строка содержит и то и другое - и указание компилятору, что в данной функции есть еще одна переменная, и указание во время работы программы вот тут в этом месте дать ей значение 5. Точно так же и в схеме, форма let, которую я обсуждал выше: (let ((x 5)) ...) одновременно задает правила понимания 'x' внутри своего тела, а также указывает, какое значение x должен получить в данном месте.
Определение функции в C не имеет этого "рантайм"-действия. "int foo(int x);" - это целиком и полностью указание компилятору, эта строка не "выполняется" во время работы так, как выполняется какой-то вызов printf(), например. В Схеме не так. Когда я в Схеме пишу (lambda (x) (foo x)), эта форма одновременно говорит что-то о том, как понимать 'x' в своем теле (foo x), но также она выполняется, когда я ее использую, например, когда я пишу (define bar (lambda (x) (foo x))). В чем состоит это выполнение?
Как объясняет секция 4.1.4 стандарта, выполнение lambda создает процедуру (я обычно называю это функцией или замыканием, стандарт использует слово 'процедура'), объект, который "знает" о себе, какое у него тело (взятое из lambda), какой список аргументов (тоже оттуда), и какая среда была на момент его создания. Средой можно считать набор всех лексических переменных и их значений на всех уровнях вложенности от того, где вызвана lambda, и до глобального. Все это процедура "помнит", и когда ее вызывают, то все это "всплывает" и становится доступным ей, вместе с ее собственными аргументами и местными переменными.
Для функций, которые определяют на глобальном уровне, не внутри других функций, это не имеет большого значения, потому что 'среда' на момент выполнения lambda состоит только из ссылки на глобальную среду, общую для всех. Но в Схеме часто оказывается полезным вызвать lambda и создать функцию, когда управление находится внутри другой функции, у которой есть какие-то свои местные переменные итд. И тогда вновь созданная функция эти местные переменные 'запомнит' и сможет к ним вернуться, даже если ее сейчас саму положить в какое-то место надолго и вызвать много позже, после того, как создавшая ее функция давно вернулась. Вот этот аспект работы функций в Схеме весьма неинтуитивен для тех, кто незнаком с замыканиями. Такие функции называют замыканиями (closures), потому что они как бы замыкаются поверх тех переменных, что "видят" на момент своего создания, и не упускают их из виду, пока сами живут. Формально говоря, все функции, определенные с помощью lambda в Схеме - замыкания, но как я объяснил выше, для функций на глобальном уровне это не очень важно. Замыканиями обычно называют те, которые определены "в глубине" и пользуются переменными, которые они видят, для какой-то удобной работы. Ниже я привожу несколько простых примеров таких замыканий и подробнее объясняю, как они работают.
---------------braindump----------------
Я нахожусь в некотором недоумении, потому что схема воплощения лексических переменных, которую я хорошо продумал в голове и собирался писать, оказалась неверной и ненужной. Я это понял вчера, обдумывая, как буду ее писать, и как обычно в таких случаях, теперь мне это кажется совершенно очевидным, хотя раньше я этого не понимал. Теперь мне немного жаль с ней расстаться, потому что я ее долго обдумывал и она мне в целом нравилась. Но Схема оказалась немного не тем языком, что я себе представлял; это уже второй раз, что я это понимаю, с тех пор, как начал писать набросок.
Не то чтобы способ, которым я собирался писать, дал бы неправильный результат - нет, он бы работал.
Но можно это сделать лучше и проще - и, следовательно, нужно. Я попробую вкратце описать то,
что /собирался/ сделать, а потом перейти к тому, что делаю. Возможно, это кому-то пригодится - например, мне самому, если захочу впоследствии написать что-то похожее для другого языка.
Спасибо А.У. и анониму из прошлого наброска (уваж. аноним, если вы сообщите свое имя, я буду рад выразить благодарность вам по имени) - их комментарии помогли мне понять, где я "застрял" в неправильном понимании связи символов и переменных в Схеме.
Вот кусок кода на Схеме, демонстрирующий несколько вложенных лексических областей (scopes):
(define y "top-level")
(define foo (lambda (x y)
(display y)
(let (y z)("in-let" "something")
(display y))))
(foo "func-arg" "something")
(display y)
Я предполагал сделать это следующим образом. Каждая специальная форма, которая открывает новую лексическую зону видимости - define, lambda, let итд. - вводит новую среду (environment), которую концептуально можно представить просто как хэш-таблицу от символов к индексам значений. Интерпретатор всегда имеет под рукой ссылку на текущую среду, а в каждой среде есть ссылка на предыдущую, включающую ее, и так изнутри наружу до первоначальной глобальной среды (она же top-level environment). Когда мне нужно "разрешить" (resolve), к какой переменной относится символ y, я сначала ищу его в текущей среде, если нет - в ее "родителе", если нет - в следующем "родителе", и так далее до глобальной среды, и если нет и там, то ошибка.
(то, как надо создавать среды во время выполнения lambda и во время выполнения функции, определенной с помощью lambda - разные операции! - я тоже продумал, но объясню это позже, потому что эта часть не изменилась в моих планах)
Проблема в том, как сделать этот поиск символа в иерархии сред быстрым и экономным. Я не хочу, например, для каждой среды создавать настоящую хэш-таблицу. Я немало об этом думал и придумал вот что. Во-первых, все символы, встреченные во время чтения исходников, записываются в один глобальный массив байтов, просто один за другим, с некоторыми дополнительными служебными полями. Гарантированно, что каждый символ в этом массиве встречается только один раз - мы сначала ищем его там, и только если не находим, добавляем в конец. Массив символов ограничен 2^32 байтами (вначале он намного меньше, но может расти), и каждый символ поэтому может быть идентифицирован 32-битным числом, индексом, где он начинается в массиве. Символы из массива никогда не удаляются для простоты (т.е. сборка мусора на них не действует); мы предполагаем, что программы на Схеме не используют гигантское число разных символов.
(зачем нужен массив, а не просто malloc каждый символ, раз мы их все равно не удаляем? Потому что даже на 64-битной системе мы хотим идентифицировать символ 32-битным индексом, а не 64-битным указателем. Почему не сделать отдельный массив указателей, и идентифицировать символы индексом в этом массиве? Отдельная головная боль для его менеджмента и еще один layer of indirection)
"Среда" теперь становится списком пар, состоящих из 32-битного индекса символа и 32-битного индекса значения. Эти пары в среде мы держим в отсортированном порядке по номеру символа, и ищем с помощью двоичного поиска. Альтернатива - если символов в среде очень мало, меньше шести, скажем (так будет для многих небольших служебных лямбд), то храним в ней пары как попало и ищем перебором. Сами среды являются значениями Схемы отдельного типа и хранятся в основной памяти, как и все остальное - и подлежат сборке мусора. Наконец, поиск символа в массиве осуществляется либо с помощью двоичного дерева, либо с помощью хэш-таблицы. То или другое включает в себя все символы, с помощью служебных указателей, хранящихся вместе с ними. Я решил сам написать, просто ради прикола, либо балансирующее двоичное дерево (не писал с университетских времен), либо простую хэш-таблицу (это как раз приходилось).
Это было описание идеи, которая оказалась ненужной. Теперь надо объяснить, почему.
Дело в том, что в Схеме символы указывают на переменные в одном и только в одном контексте - в исходном коде, когда они там не процитированы апострофом ' или не скрыты другой специальной формой. Если в программе написано (foo bar1 bar2 bar3), то символы "foo", "bar1" итд. должны ссылаться на переменные, определенные в какой-то окружающей их среде. Но в какой именно - *можно решить в этот самый момент чтения*, совершенно необязательно дожидаться рантайма. В рантайме ничто измениться принципиально не может. Если скажем "bar1" определена в какой-то команде let на три уровня выше, а foo определена в глобальной среде на шесть уровней выше, то это теперь всегда будет так, и эти символы bar1 и foo в этих местах ни на что другое "ссылаться" не могут. Более того, если мы так или иначе прочитали "bar1" или "foo" как символы - например, написав их 'bar1 или 'foo; или если мы создали их с помощью функции string->symbol в рантайме - то перейти от них к переменным нет никакой возможности. Схема не дает никакой возможности - специально, наверняка! - мне сказать в рантайме что-то типа "(resolve 'foo)", что означало бы "выполни эту самую процедуру поиска по средам изнутри наружу, которую я описал в абзацах выше, пока не найдешь переменную с именем foo". Этого просто нет.
А что это значит, что этого нет? Это значит, что стандарт Схемы достаточно толсто мне подсказывает: это разрешение символов в переменные надо делать не в рантайме, платя за это цену временем и памятью - а во время чтения исходников вообще. Каждая "среда" должна быть не отражением "символ-имя -> индекс значения", а просто массивом "индексы значений", а символы, которые указывают на переменные, должны во время чтения исходников меняться на "указатели" (в кавычках, потому что это не настоящие указатели) внутрь такой среды. Т.е. когда интерпретатор читает
(define foo (lambda (x y)
(display y)
(let (y z)("in-let" "something")
(display y) (display x))))
После такой обработки никаких *символов* в этом коде не остается вообще - они меняются на указания, как найти *переменные*, путешествуя по средам изнутри снаружи. Конечно, это нахождение тогда получается очень быстрым (пройти по нескольким указателям и посмотреть на слот в массиве).
Кое-какие вещи надо прояснить. Зачем, например, говорить "5-й слот на втором уровне", а не просто поставить указатель на то место, где лежит значение этой переменной, т.е. на 5-й слот второго уровня? Тут важно понять фундаментальную разницу между определением функции и ее вызовом, и заодно прояснить, как работают замыкания. Дело в том, что если например у функции foo есть два аргумента x и y, то необходимо помнить, что каждый вызов foo создает новые места, где надо хранить эти x и y. Потому что иначе x и y получились бы как бы глобальные переменные, и foo например не могла бы себя в принципе рекурсивно вызвать (напрямую, или через другие функции). Собственно так и происходит в коде наброска сейчас, когда есть только одна глобальная таблица символов. Понятно, что так быть не должно.
Каждый вызов функции создает новую среду для ее локальных переменных. Если функция foo вызвала себя рекурсивно пять раз и находится сейчас в середине пятого вызова (и это не "хвостовая рекурсия", о чем позже, сейчас можно игнорировать эти скобки), а внутри ее есть еще какой-то let например, и внутри него написано вместо x какие-то инструкции, как добраться до правильного слота, то это не может быть просто указатель, поставленный интерпретатором еще во время чтения исходников - на какую из пяти сред он может указывать? Да эти пять сред и не существовали еще тогда, когда интерпретатор читал код foo. А вот указание типа "первый слот на первом уровне" работает отлично, потому что у интерпретатора есть текущая среда, в ней указатель на правильную предыдущую итд.
Хорошо. Вот мы вызываем функции foo, и интерпретатор создает для ее переменных новую среду. Он должен в нее записать ссылку на предыдущую среду. Откуда он берет эту ссылку?
Тут как раз проявляется сущность замыканий. Когда выполняется форма lambda, т.е. когда создается функция, то мы запоминаем ссылку на среду, которая была текущей в этот момент - просто записываем ее куда-нибудь внутрь значения T_FUNC. Пока у нас эта функция существует (например, ее могли создать и записать в переменную в глобальной среде, и она теперь будет там жить, пока не сотрем), она хранит в себе ссылку на эту среду, и эта среда никуда не пропадет - сборка мусора, например, ее не соберет. Несмотря на то, что вызов функции, который создал эту среду, давно мог вернуться, среда, вместе со всеми ее родителями вплоть до глобальной, остается жить. И когда кто-то вызовет эту лямбду, то интерпретатор создаст для ее переменных новую среду, и свяжет ее с этой, хранимой. И так оно будет работать.
(define count-maker (lambda ()
(let ((x 0))
(lambda ()
(set! x (+ x 1)) x))))
> (define x (count-maker))
> x
#
> (x)
1
> (x)
2
> (x)
3
> (define y (count-maker))
> (y)
1
> (x)
4
> (y)
2
Что здесь происходит? Функция count-maker сначала создает новую среду с одной переменной x (которая становится на самом деле "первый слот"), а потом выполняет форму lambda, т.е. создает функцию, и возвращает эту функцию. Эта функция хранит в себе ссылку на среду с этим одним слотом, а в ее коде вместо x везде стоит "первый слот на первом уровне". Мы записали эту функцию в x, и пошли чай пить. Функция count-maker давно вернулась, может еще сто разных вещей случилось, сборка мусора пробежалась пару раз, неважно - мы вернулись и запустили функцию, к-я записана в (x). Немедленно создалась среда для ее местных переменных (пустая, т.к. у нее их нет), и соединилась с той самой средой из одного слота. Каждый запуск (x) соединяется с этой средой, и манипулирует значением ее слота. А что произойдет, если мы вызовем еще раз (count-maker)? Новый вызов этой функции создаст новую среду с одним слотом, и соответственно новую внутреннюю функцию-лямбду, которая будет помнить уже эту среду. Это новый счетчик, и вызов этой внутренней лямбды увеличивает его независимо от первого счетчика.
Вам это ничего не напоминает? Код внутренней лямбды "увеличить на 1 и вернуть" один и тот же, но мы создаем на его основе разные замыкания, которые независимо друг от друга работают над разными данными. Конечно же, это напоминает объекто-ориентированное программирование. Вызвать count-maker - это как 'создать объект', у которого есть 'поле данных' x и 'метод', работающий с этим полем. Если вызвать еще раз - будет новый объект, со своим полем данных. В этом примере у нас только одно поле данных и только один метод, но это легко расширить - определить несколько слотов, и определить и вернуть одновременно (например, в списке) несколько разных лямбд, работающих с этими слотами. Объектно-ориентированная система готова. Если вам когда-то попадалось, или попадется, утверждение о том, что "замыкания и объекты - это одно и то же", теперь вы знаете, почему.
Осталось решить еще несколько вопросов, и можно писать код. Во-первых, не очень ясно, что делать с такими формами, как let - я написал выше, что примерно как lambda, но let не совсем лямбда - это не новая функция, у нее нет аргументов, зато есть начальные значения. На самом деле я думал вначале, что может быть для let не надо создавать отдельную среду. Пусть ее переменные кладутся в среду той лямбды, в которой она лежит (то, что имена могут совпадать, неважно - код чтения использует для них разные слоты, это очень просто рекурсией сделать). Скажем, если у функции два аргумента x и y, и внутри есть let на y и z, то пусть будет четыре слота, и символы по ним раскидаем. А можно по-другому: стандарт объясняет, что любой let и другие похожие формы можно на самом деле переделать в лямбду, хоть это на первый взгляд неинтуитивно. Если я написал например (let ((x 1)(y 2)) (...)), то это все равно, что определить функцию (lambda (x y) (...)) и немедленно ее вызвать с аргументами (1 2). Проверьте, что вы это понимаете, что это одно и то же.
Думаю, что все-таки второй путь лучше, например еще потому, что для первого способа нужно придумывать какие-то ухищрения для вызовов let на глобальном уровне, вне всяких лямбд. В принципе let можно автоматически преобразовать в лямбду с помощью макросов, которыми у меня еще и не пахнет. Поэтому я пока либо просто повременю с let, либо напишу его как специальный случай, де-факто идентичный лямбде.
Во-вторых, не очень ясно, что делать с символами, которых не найти ни на одном уровне, включая глобальную среду. По-моему, стандарт разрешает мне просто выдавать ошибку, если кто-то хочет написать, например:
(define (foo x)(+ x somevar))
(define somevar 5)
(foo 10)
И последнее - где все это писать, этот процесс замены символов на 'ссылки на переменные'. Сначала я хотел сделать это частью read_value(). Но по мере того, как количество и сложность того, что надо делать, в уме росло, я начал склоняться к мнению, что лучше пусть read_value() читает все "как есть" - списки в списки итд. - а это будет в отдельном прогоне, который как бы готовит исходный код к выполнению. Не знаю только, как его назвать - напрашивается compile, но это же не настоящая компиляция. Пусть будет пока prepare(). В прошлом я уже задумывался о том, где у меня будут выполняться макросы, когда я их добавлю - вряд ли в eval(), неужели при чтении? Теперь мне кажется, что именно эта prepare() для этой цели подойдет. Ну да поживем - увидим.
Тут надо прояснить один важный фактор в том, как это писать. Я выше упоминал, что не хочу для разрешения символа делать отдельную хэш-таблицу на каждую среду. Но это потому, что в рантайме это слишком высокая цена. prepare() же вызывается один раз для каждого куска кода в исходниках, и здесь эту цену заплатить совсем не жалко. То же самое касается структуры кода. Мой eval() сейчас рекурсивный, но это временно - чтобы сделать поддержку хвостовой рекурсии мне придется его переписать в будущем и сделать несколько сложнее и без рекурсии. Но тут, в prepare(), так же как и в read_value(), у меня нет никаких оснований опасаться рекурсии - у нее не может быть большой глубины, ее глубина ограничена тем, что написано в исходниках, а не тем, как это будет выполняться. Это сильно упрощает задачу.
--------------------------------coding--
(продолжено во второй части)