No description, website, or topics provided.
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.idea
Liscript.hs
README.md
lib.txt
test.txt
test1.txt

README.md

Liscript

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

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

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

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

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

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

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

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

Про парсер. Когда я начал искать необходимую информацию, я наткнулся на эту ссылку https://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours Честно говоря, половину этой реализации я не понял, а вторая половина мне не понравилась. В итоге я оттуда подсмотрел только тип 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 макросы также как и функции являются объектами первого класса. Для ознакомления с этим чудом природы можно почитать http://matt.might.net/articles/metacircular-evaluation-and-first-class-run-time-macros/ (обнаружил эту ссылку после своей реализации).

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

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

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

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

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

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

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

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

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

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

ЗЫ и да, Clojure все-таки не оставляю надежд выучить :)