eval @ apply. Операционная семантика Microlisp.

[love5an]

Ну и небольшой драфт языка, вообще.

Репозиторий на гитхабе тут(если кто прошлый постинг еще не читал):
https://github.com/Lovesan/Microlisp


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

Объект лиспа это любая сущность, к которой можно применить некоторый набор операций, доступных пользователю реализации лиспа. Если еще короче - объект это то, что может быть вычислено(eval). Так как современные диалекты лиспа, и Microlisp, в частности - глубоко объектно-ориентированные языки, у каждого объекта есть еще два свойства - каждый объект имеет идентичность(то есть, в каждой программе он присутствует в единственном числе), состояние, и принадлежит к некоторому классу(и классы это тоже объекты).
То, что я называю объектом, еще называется "first-class object".

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

Как я уже сказал, в лиспе любой объект языка может быть вычислен. Поэтому, говоря о семантике лиспов, вводят понятие "формы"(form). Форма это любой объект, который мы намереваемся вычислить, в противоположность "данным"(datum). Далее, формы подразделяются на три вида - объекты, вычисляющиеся сами в себя(1), cons-ячейки(2) и символы(3). Объекты первого типа это, например, числа, буквы и вообще любые объекты, кроме символов и cons-ячеек; при их вычислении мы получаем их же. Символы и cons-ячейки в лиспе вычисляются особым образом. Но, чтобы объяснить, как они вычисляются, надо сначала ввести понятия "окружения"(environment), "области видимости"("scope"), "срока действия"("extent") и "связи"("binding", также в русском встречаются термины "биндинг", "привязка").

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

Срок действия[чего-либо] это временной интервал, на протяжении которого доступны ссылки на некоторые связи или объекты.

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

Говорят, что срок действия динамический("dynamic extent"), если он ограничен конкретными точками начала(установки, establishment) и окончания(выхода, disestablishment) во время вычисления некоторой формы.

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

Говорят, что область видимости - статическая("static scope")(или, по-другому, лексическая, "lexical scope") если она ограничена некоторым конкретным и жестко заданным регионом структурного представления программы, динамическая("dynamic scope") - если она не ограничена структурным представлением программы, но ограничена динамическим сроком действия, и глобальная - если она не ограничена никак(и привязки имен в ней видны всей программе в любой момент времени).

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

Привязки в Microlisp бывают четырех видов: переменные, блоки, go-теги и catch-теги.
В Common Lisp, в отличие от микролиспа, существуют еще привязки функций, но в микролиспе они объединены с переменными.

Переменная это связь символа со значением. В микролиспе, как и в CL, они делятся на четыре вида:

1. Статические(или, лексические) переменные - переменные, имеющие статическую область видимости и неограниченный срок действия.


2. Динамические - переменные, ограниченные динамической областью видимости, и, соответственно, динамическим сроком действия.


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


4. Макро-переменные - имеют лексическую область видимости, как и статические переменные, но существенно отличаются семантикой вычисления значения. Как и константы, связываются во время раскрытия макросов.

go-тег это связь символа или целого числа с точкой выхода, установленной в операторе tagbody.
Про то, что такое точки выхода, и как происходит вычисление - ниже.

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

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

Так вот, лексическое окружение это коллекция статических переменных, констант, макросов, go-тегов и блоков, а также деклараций(про них ниже). Лексическое окружение, кроме прочего, хранит ссылку на предыдущее по отношению к себе лексическое окружение, или же, на глобальное окружение(которое в CL еще именуется нулевым лексическим окружением("null lexical environment")), и скрывает(shadow) все связи в нем(конкретнее про это - ниже) своими если их имена совпадают.

Лексическое окружение имеет лексическую область видимости, и неограниченный срок действия. Это значит, что связи в нем могут захватываться в "замыкания". Замыкание(closure) это функция, которая ссылается на внешнее, по отношению к своему определению, лексическое окружение. Несмотря на то, что само окружение имеет неограниченное время жизни, не все связи в нем так же неограниченны динамически - go-теги и блоки имеют динамический срок действия.

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

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

Глобальное окружение, или, что то же самое, "нулевое лексическое окружение", хранит глобальные декларации и глобальные переменные всех четырех видов.

Концепция "окружения", которую я выше описал, по-другому называется "запись активации"(activation record), или "кадр активации"(activation frame). Это представление блока исполняемого кода с некоторой информацией.

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

Каждый кадр активации хранит ссылку на предыдущий затем, кроме прочего, чтобы знать, куда передавать управление после завершения исполнения всего кода, расположенного в кадре. Такая форма передачи управления в Common Lisp, и в Microlisp, называется "normal return".

Но, кроме обычного выхода из кадра, и CL и микролисп позволяют произвести так называемый "нелокальный выход"(non-local exit, сокращенно NLX). NLX это передача управления в установленную в одном из родительских кадров активации "точку выхода".

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

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

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

NLX в CL и микролиспе совершается операторами go, throw и return-from, которые ищут привязку точки выхода, установленной tagbody, catch и block соответственно. В других языках, в частности, в большинстве мейнстримных, NLX можно произвести выкинув исключение.

Кстати, операторы throw и catch из CL к системе обработки исключений отношения не имеет совершенно никакого. Это "динамические"(в том плане что имеют динамическую область видимости) аналоги пары return-from и block.

Так вот, при выходе из текущего кадра, обычным ли образом, или используя операторы, совершающие NLX, производится так называемая "раскрутка стека"(stack unwinding)
А конкретнее: для каждого кадра, включая текущий, до кадра, в который производится выход, исключая, естественно, его, производится:

1. Отмена всех привязок точек выхода кадра, имеющих динамический срок действия(go-теги, блоки, catch-теги).


2. Проход через точку выхода unwind-protect, то есть вычисление всех "защищенных" форм.


3. Отмена всех привязок динамических переменных.


4. Передача вычисленных значений выше.

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

Замыкания, создаваемые в стековом кадре, обычно заставляют выделять под его лексические переменные некоторый отдельный объект, за исключением случая когда компилятор может доказать что замыкание пойдет только вниз по стеку. Все метки точек выхода в замыканиях, после выхода из кадра, становятся невалидными, и соответственно попытка выхода в точку, которая уже не существует это ошибка. В реализациях CL в таких случаях обычно сигнализируется исключение класса CONTROL-ERROR; в микролиспе аналогично.

Кстати, существуют языки, в которых точка выхода может быть и точкой входа, и в них можно снова войти в уже завершившийся кадр активации.
Это Очень Плохой паттерн проектирования языка, который называется "продолжения"(first-class continuations). Кроме значительного оверхеда по памяти и производительности, превращения кода в лапшу похуже стандартной javascript-каши из коллбеков в вебе, они несут с собой один Очень Неприятный момент - а именно, невозможность реализации аналога unwind-protect, то есть гарантированных и единожды исполняемых сайд-эффектов во время выхода из кадра. UWP невозможно реализовать в языках с продолжениями по той причине, что в таких языках никакого понятия стека нету, соответственно, нет никакого unwinding, а есть просто цепочка фреймов активации, по которой можно свободно гулять, а это, в свою очередь, значит, что гарантировать невозможность повторного входа в кадр нельзя совершенно никак.
Более подробно про этот момент здесь: http://www.nhplace.com/kent/PFAQ/unwind-protect-vs-continuations-original.html

Так вот, как вычисляются символы и cons-ячейки в Microlisp:

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

Если переменная не объявлена, взять значение из слота значения символа.

Если переменная, или значение символа, не связана, сигнализировать unbound-variable(механизм исключений в микролиспе будет примерно как в CL. Необработанное condition, сигнализированное через signal-error это вызов дебаггера в текущем динамическом окружении, либо, если тот не установлен - выход в операционную систему с некоторым кодом ошибки(либо, если это реализация на голом железе, какой-нибудь аналог bsod)).

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

Несвязанными переменными, если они объявлены, могут быть только динамические. В microlisp будет функция proclaim, которая принимает декларации(см. ниже про декларации), и соответствующим образом объявляет что-либо в глобальном окружении, например глобальные переменные - в таком случае, любой символ, кроме dynamic обязан будет быть уже связан со значением. Переобъявлять переменные на предмет принадлежности другому виду будет нельзя.

Если форма - cons-ячейка, то:

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

Если car формы - символ - то, если это имя макроса, вызвать его, передав ему два аргумента - всю форму, и текущее лексическое окружение. В таком случае, макро-переменная должна содержать функцию. Если это не функция - сигнализировать ошибку class-error(аналог type-error из CL; я не стал вводить систему типов CL в микролисп, только классы). Получившееся раскрытие макроса обработать снова.

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

"Функцией" может быть либо обычная функция, то есть такая, в которую вычисляется спецформа lambda, либо instance(аналог funcallable-standard-instance из CLOS MOP).

Применение функции допускает dotted list, то есть последний cdr которого не nil, но форма, вычисляющаяся в список. Тогда это аналог apply.

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

• (class class-name* var-name*) - специфицирует что значение переменных принадлежит некоторому классу.


• (static var-name*) - указывает, что определенные переменные - статические. Статические переменные это дефолтный вид переменных, так что декларация не совсем обязательна.


• (dynamic var-name*) - определяет что указанные переменные в текущем окружении - динамические.


• (constant var-name*) - определяет константы.


• (macro var-name*) - определяет что символы указывают на макро-переменные.


• (optimize optimization-declaration*) - аналогично CL:OPTIMIZE. При safety >= 1 в коде обязательны проверки типов. При safety = 0 возможны операции с указателями(украл фичу из дотнета, да. Абстрактный "void*" будет встроенным типом лиспа).


• Декларации переменных, кроме dynamic, могут появляться только в формах, в которых данные символы связываются(т.е. это let и друзья). В lambda могут появляться только static и dynamic декларации переменных. dynamic, если переменная не связывается, но только декларируется, означает что setq или {обращение к переменной} будут трактовать переменную как динамическую.

Вообще, в будущем планирую сделать декларации first-class объектами, и сделать, соответственно, возможность пользователям доставать их из объектов лексических окружений.

Специальные операторы:

• lambda ::= {{name lambda-ags}| lambda-args} [[declaration*|documentation]] forms*
  lambda-args ::= ( arg* | arg+ . rest-arg )
  Фактически, аналогична CL:LAMBDA, за исключением того, что может быть именованной. В таком случае, это эквивалентно введению именованного блока и возможности рекурсивного вызова, как в CL:LABELS или SB-INT:NAMED-LAMBDA.


• body ::= declaration* forms*
  Вычисляет все формы forms, в лексическом и динамическом окружении, установленном согласно декларациям. Возвращает значения последней вычисленной формы, либо nil. Аналог CL:LOCALLY


• body1 - синтаксис такой же, как и у body, но возвращает значения первой вычисленной формы(либо nil). Комбинация CL:LOCALLY и CL:MULTIPLE-VALUE-PROG1


• let, let* и letr аналогичны CL:LET, CL:LET* и CL:LABELS за исключением того, что:
  1) Если вторая форма оператора - символ, тогда это означает введение именованного блока(как с block).
  2) Вычисление привязок констант и макросов осуществляется в compile-time, в текущем лексическом окружении, в котором видны только привязки констант и макросов, и в текущем динамическом окружении.


• bind = CL:PROGV


• quote - аналог CL:QUOTE


• if - аналог CL:IF


• setq = CL:SETQ


• toplevel-expansion-too
  toplevel-expansion-only
  Cинтаксис как и у body, семантика тоже, но за исключением того, что работает как
  (eval-when (:compile-toplevel :load-toplevel :execute) ...)
  и соответственно (eval-when (:compile-toplevel :execute) ...) из CL
  В интерпретируемом коде эти формы и body - аналогичны.


• block = CL:BLOCK


• return-from = CL:RETURN-FROM


• catch = CL:CATCH


• throw = CL:THROW


• tagbody = CL:TAGBODY


• go = CL:GO


• mvcall = CL:MULTIPLE-VALUE-CALL


• unwind-protect = CL:UNWIND-PROTECT


• the - фактически, примерно эквивалентно CL:THE. Но, первый аргумент - имя глобально определенного класса, либо список из имен классов(тогда последний cdr может быть не nil, и это означает что все оставшиеся значения должны быть указанного класса). С высоким уровнем safety транслятор обязан проводить проверку на принадлежность классу. С низким safety и высоким optimize, может опускать ее, и, соответственно, наоборот, полностью доверять декларации.

Comments

[nponeccop.livejournal.com]

прочитал evil @ apple

[maxim.livejournal.com]

С таким ядром это не Микролисп, а Мегалисп.

    ([lambda] (eval-lambda form env))
    ([quote] (eval-quote form env))
    ([setq] (eval-setq form env))
    ([if] (eval-if form env))
    (([toplevel-expansion-too]
      [toplevel-expansion-only]
      [body])
     (eval-body form env))
    ([body1] (eval-body1 form env))
    ([let] (eval-let form env))
    ([let*] (eval-let* form env))
    ([letr] (eval-letr form env))
    ([bind] (eval-bind form env))
    ([catch] (eval-catch form env))
    ([throw] (eval-throw form env))
    ([block] (eval-block form env))
    ([return-from] (eval-return-from env))
    ([tagbody] (eval-tagbody form env))
    ([go] (eval-go form env))
    ([unwind-protect] (eval-unwind-protect form env))
    ([mvcall] (eval-mvcall form env))
    ([the] (eval-the form env))

[(Anonymous)]

> Очень Неприятный момент - а именно, невозможность реализации аналога unwind-protect, то есть гарантированных и единожды исполняемых сайд-эффектов во время выхода из кадра. UWP невозможно реализовать в языках с продолжениями

Ну сколько можно повторять этот бред? Давным-давно уже эту проблему решили.

[love5an.livejournal.com]

Каким образом? Континуации урезали?

[wizzard]

кхе. а мы говорим про first-class, delimited или one-shot continuations?

[love5an.livejournal.com]

Которые в схеме, естествнно, то есть first-class

[shmat-razum.blogspot.com (from livejournal.com)]

Реплика новичка: барьеры континуаций в Racket -- это разве не оно?

Вот суть проблемы:

> (define saved-cont #f)
> (call-with-output-file* "file.txt" (lambda (out)
                                       (let/cc cont (set! saved-cont cont))
                                       (fprintf out "hello\n")) #:exists 'append)
    
> (saved-cont)
fprintf: output port is closed

А вот как она решается с помощью барьера:

> (call-with-continuation-barrier
   (lambda ()
     (call-with-output-file* "file.txt" (lambda (out) (let/cc cont (set! saved-cont cont))
                                         (fprintf out "hello\n")) #:exists 'append)))                                 
> (saved-cont)
continuation application: attempt to cross a continuation barrier

[(Anonymous)]

Оно и есть. Кроме того, в dynamic-wind (аналог unwind-protect) специально для этих целей добавлен in-guard.

[love5an.livejournal.com]

dynamic-wind это не unwind-protect, он вызывается каждый раз, и существует не для cleaup'а, в отличие от

[(Anonymous)]

Для клинапа dynamic-wind и существует.

[love5an.livejournal.com]

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

[(Anonymous)]

Ну не надо отсебятину городить. Для динамического окружения есть параметры, а на dynamic-wind ты окружение все равно не сделаешь. И специально для восстановления того, что заклинапили, есть in-guard.

[love5an.livejournal.com]

Весело. Ну это одна из вещей, которые предлагал Kent Pitman - урезать продолжения(#2).

[(Anonymous)]

Ну только это не урезание, а наоборот - расширение. Вот ты говорил о фреймах - обычные продолжения позволяют прыгать по фреймам туда/сюда, а теперь представь, что с каждым фреймом ассоциирован некоторый набор данных, с которым мы можем работать (устанавливать, изменять) и использовать эти данные при переходах между фреймами (при помощи этого можно захватывать продолжения до фреймов с определенной меткой, собирать какую-то отладочную инфу для стектрейса и т.п.). Вот, собственно, барьер - это просто такой фрейм, на котором написано "внутрь не лезть". А то, что там Kent Pitman предлагает - вообще элементарно реализуется в виде макрообвязки над call/cc.

[sdfgh153.livejournal.com]

Ой, это прям проклятье какое-то. У нас внутренний лиспец тоже Microlisp называется.

[love5an.livejournal.com]

да ну это просто кодовое имя
запилю компилятора и прочее - придумаю нормальное

[dvig-al.livejournal.com]

Для компилятора какую машину в основу положишь, ну, ту самую - абстрактную вычислительную? И интересны детали, как например память менеджить будешь?

[love5an.livejournal.com]

я так думаю, регистровую с бесконечным числом регистров
память - GC, сначала попробую сделать простой stop-n-copy, по алгоритму Чейни, потом посмотрю, может на другой заменю.

[(Anonymous)]

почему бы не юзать что-нибудь LLVM-подобное, чтобы в идеале компилятор генерировал обычный LLVM ассемблер/биткод, который можно было бы оптимизировать прогнав через opt со всеми его 10500 оптимизациями, слинковать с тем же C++ кодом из clang-а и т.п.?

[(Anonymous)]

мини лисп на LLVM, на С++ : http://news.ycombinator.com/item?id=487994
http://paste.lisp.org/display/74068

биндинги cl-llvm устарели, кто бы обновил их до LLVM 3.0? вызываются через LLVM C API.

есть форк sbcl-llvm, но он сильно заброшен http://news.ycombinator.com/item?id=1007659

если целиться в LLVM, в первом приближении GC можно не переизобретать, а использовать GC от LLVM.

GC пишут в основном на С части, потому что хотят его удобно отлаживать. Но в принципе ничего не мешает написать GC языка на самом языке (примеры: HLVM, Oberon component pascal, и т.п.)

реализация GC на Ocaml-подобном HLVM есть в HLVM: http://forge.ocamlcore.org/projects/hlvm/ . Mark-n-sweep, похож на тот GC, что в Оберонах (там кстати, тоже компактная реализация)

Ещё интересная реализация GC есть Clozure CL / OpenMCL.


lisp500, лисп в 500 строчек на Си: http://www.reddit.com/r/programming/comments/1znpt/lisp500_a_500line_implementation_of_an_informally/

дохлая ссылка, http://www.modeemi.fi/~chery/lisp500/ -- cмотреть здесь: http://web.archive.org/web/20070722203906/http://www.modeemi.fi/~chery/lisp500/

lisp5000, деобфусицированный lisp500 с комментариями: http://code.google.com/p/lisp5000/source/browse/trunk/lisp500.c?r=5

[(Anonymous)]

А не рассматривал вариант компиляции в обычный CL (на макросах)?

[love5an.livejournal.com]

да можно в CL компилировать, но это не интересно

[linkfly.livejournal.com]

Очень интересный проект. А статья кроме прочего - хороший туториал для новичков по терминологии.

[(Anonymous)]

Интересно. Чем-то Goo напомнило, http://people.csail.mit.edu/jrb/goo/manual.46/goomanual.html http://people.csail.mit.edu/jrb/goo/ http://en.wikipedia.org/wiki/Goo_(programming_language) , только более низкоуровнево.

Кстати, интересно, что думаешь по поводу Goo. У него любопытная минималистичная объектная система.

[(Anonymous)]

Этих микролиспов -- вагон и маленькая тележка в гугле. Надо имечко позвучнее подобрать
http://lemonodor.com/archives/2007/11/microlisp.html https://github.com/mizuy/microlisp http://window.edu.ru/window/catalog?p_rid=47016 http://code.google.com/p/colony9/source/browse/include/away/lispy%2B%2B/microlisp.cpp?r=4e1f3959645baa2d118818a16a66ea54a0e2acfa http://nakkaya.com/2010/08/24/a-micro-manual-for-lisp-implemented-in-c/

зы. picolisp, nanolisp, femtolisp тоже уже заняты.