Liscript

Некоторое время назад мне захотелось изучить язык программирования Clojure и вообще познакомиться с возможностями лиспа поближе. Но вместо практики на Clojure я начал читать SICP и захотел реализовать свой интерпретатор диалекта лиспа, для лучшего понимания заложенных в нем концепций. В результате получился язык, который я в своем локальном окружении связал с именем Liscript. :)

ОК - основная концепция

В качестве языка реализации я выбрал Haskell, потому что хотел параллельно попрактиковаться в нем при решении этой задачи. Собственно, основной целью было реализовать интересную мне функциональность, не уделяя внимания оптимизации скорости исполнения, потребления памяти, сомнительному синтаксическому сахару и прочим второстепенным в смысле основной задачи вещам. Поэтому, например, в синтаксисе Liscript нет привычных let - их заменяют локальные def, нет if ... then ... else - их заменяет cond и т.п. Вообще, вопрос что реализовывать через особые формы (внутренние команды языка), а что через макросы и библиотечные функции не имеет однозначного правильного ответа, и даже известные реализации лисповых диалектов решают его различным образом.

Нет параметров функций по умолчанию - это тривиально реализуется функциями-обертками, причем хоть 20 разных вариантов параметров по умолчанию, нет оптимизации хвостовой рекурсии, сборщика мусора и т.д. Во всех случая далее, когда мне надо будет пояснить, почему в языке не реализована та или иная функциональность или поведение, я буду для краткости ссылаться на эту “ОК” - основную (общую) концепцию. :) С кодом интерпретатора, файлом стандартной библиотеки” и некоторыми небольшими тестовыми примерами можно ознакомиться по этой ссылке. А здесь я постараюсь на словах рассказать о возможностях и некоторых особенностях реализации интерпретатора.

Краткая характеристика

1. Строгий язык с вызовом по значению, последовательным выполнением инструкций.
2. Реализованы отложенные вычисления и ленивые списки-потоки (через макросы).
3. Первоклассные функции, анонимные функции, полноценные замыкания.
4. Первоклассные рантаймовые макросы (макросы времени исполнения).
5. Модель памяти - древовидное иерархическое мутабельное окружение.
6. Возможность связывания значений с неконстантными именами (имя переменной вычисляется как строка).
7. Глубокое связывание и автоцитирование (со всеми плюсами и минусами).

Инфраструктура - файлы, парсинг

В коде интерпретатора перечислены имена файлов, которые он последовательно загружает и интерпретирует. Их состав можно менять, добавлять сколько угодно своих файлов, в данный момент первым идет файл “библиотеки”, в котором определены некоторые общие и списковые функции и файл кода, который будет выполнен. Файлы имеют расширение txt и должны лежать рядом с файлом кода (при запуске в интерпретаторе GHCi) или рядом со скомпилированным exe файлом - при запуске скомпилированного интерпретатора. В последнем случае стоит раскомментарить строку запроса ввода значения от пользователя в конце работы, иначе окно терминала сразу закроется.

Про парсер. Когда я начал искать необходимую информацию, я наткнулся на эту ссылку. Честно говоря, половину этой реализации я не понял, а вторая половина мне не понравилась. В итоге я оттуда подсмотрел только тип LispVal и его инстансы, да и то частично. Парсер же там реализован на библиотеке Parsec. Я попробовал приспособить его для своих нужд, но не сумел с ним разобраться, и в результате мне было гораздо проще написать свой парсер - из текста в сразу готовое AST, безо всяких дополнительных преобразований во время интерпретации. Код моего парсера занимает 20 (!) строк (можете посмотреть и поругать).

Типы - примитивы и контейнеры

Можно было бы написать, что с точки зрения программиста Liscript является динамически слабо типизированным языком, и в какой-то степени это можно считать верным - нет контроля валидности программы на соответствия типов, нет даже намека на типизацию в тексте программы. Но с другой стороны не будет ошибочным сказать, что это статически типизированный язык с единственным примитивным типом - строкой :) Посмотрим, почему это так. Тип, который могут принимать выражения языка, описывается так:

data LispVal = Atom String
             | List [LispVal]
             | Func { params :: [String], body :: [LispVal], closure :: Env }
             | Macr { params :: [String], body :: [LispVal] }

Просто, аскетично, ничего лишнего. Если оставить 2 последних кейса, которые мы рассмотрим позже, то первый кейс - это собственно тип-примитив языка, а второй - список, содержащий значения любого (не обязательно примитивного) типа. То есть, встроенный контейнер единственный - список, и встроенный тип тоже - строка. При синтаксическом разборе текста программы парсер заполняет значениями Atom String любые токены, которые не распознает как списки, функции или макросы - и “abc”, и 2, и 3.5. Но потом при выполнении встроенных примитивных операций сама операция определяет как надо трактовать ее аргументы - ++ считает аргументы строками, + целыми числами, а +' числами с плавающей точкой, соответственно делая приведение значений к этим типам перед выполнением операции с последующим переводом в строку результата. В этом смысле ВСЕ встроенные операции являются операциями над строками, но для программиста создается впечатление, что он работает с числами.

Можно ли сделать иначе? Разумеется - добавить кейсы для Atom Int и Atom Double, при разборе текста программы сразу определять в какой тип класть какое значение, и т.п. И разумеется это будет работать быстрее при численных расчетах - нам не надо постоянно переводить из строк и в строки. И тогда уже можно будет сделать примитивную проверку типов - их соответствие операциям, но все равно потребуется писать функции преобразования, и более того - делать их примитивами языка, вынося пользователю. Но в соответствии с ОК был выбран более простой вариант реализации, который вполне работоспособен.

Типы - функции и макросы

Функции являются полноценными объектами первого класса языка - то есть их можно передавать в качестве аргументов и возвращать в качестве значений из функций, поддерживаются полноценныезамыкания, не говоря уже любых рекурсиях, можно объявлять анонимные функции. При вычислении функций используется вызов по значению - сначала последовательно (строго по порядку, в отличие от Scheme, например) вычисляются значения аргументов, эти значения связываются с именами формальных параметров в новом дочернем кадре-окружении (см. раздел про модель памяти), а потом в этом окружении вычисляется тело функции - как завещал SICP. Определение различных функций с одним именем и разным количеством параметров в одном окружении не поддерживается (следующее определение просто заменяет предыдущее), передача параметров по умолчанию - тоже. Оптимизиции хвостовой рекурсии нет в соответствии с ОК.

Макросы - рантаймовые, то есть и раскрываются и исполняются во время интерпретации программы. Оно и понятно - нет стадии компиляции или ее подобия, на которой бы макросы раскрывались до выполнения кода - сразу идет интерпретация и выполнение. Некоторых удивляет этот факт, и мне говорят что тогда это не макросы, а наверное F-выражения. Но это именно макросы, самые настоящие, и по поведению ничем не отличающиеся от обычных - вычисляются в 2 этапа, в окружении вызова, не имея своего окружения (в отличие от функций, как замыканий). Но в отличие от многих других лиспов, в Liscript макросы также как и функции являются объектами первого класса. Для ознакомления с этим чудом природы можно почитать заметку (обнаружил эту ссылку после своей реализации).

Модель памяти - связь имен со значениями

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

type Frame = Map.Map String LispVal -- кадр связывания имен ключ-значение

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

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

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

data Env = NullEnv | Voc (IORef Frame, Env) -- дерево кадров текущий-родитель

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

Дальнейшие планы

А дальнейших планов пока никаких :) Нет, я конечно не исключаю, что когда-нибудь реализую первоклассные модули и пространства имен или еще какие интересные фичи. Но свою первоначальную задачу я выполнил, реализовал желаемый набор возможностей, и даже порой пишу на Liscript некоторые прототипы и задачки (например, решатель Судоку, символьное дифференцирование, редукция лямбда-термов и т.п.) - и мне это проще чем на Haskell, потому что есть мутабельное окружение, побочные эффекты и т.п. :) И если у кого вдруг появятся вопросы или предложения/комментарии по общим моментам, кодам примеров на Liscript, моему коду на Haskell или еще чему, с интересом почитаю/постараюсь ответить.

P.S. И да, Clojure все-таки не оставляю надежд выучить :)