Блог товарища Nihirash

02.09.2018

Создание лисп-подбного скриптового языка. Часть 1.

Буквально на днях, я создал в твиттере пост, в котором обещал написать интерпретатор лисп-образного языка на Scala(если пост наберет 666 ретвитов,и а он, внезапно, набрал их), с возможностью внедрения в ваши scala-проекты для скриптования.

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

Что ж, первая статья под катом.

Введение

Зачем?

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

На Scala я пишу всего около полугода(сменил работу со сменой языка) - и я решил, что это будет хорошей практикой, помимо работы.

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

Ну и лично мой довод - это просто весело.

Что я хочу получить на выходе?

Минимальный прагматичный скриптовый язык, на котором можно было бы написать сценарий автоматизации какого-либо процесса.

Из того, что нам реально нужно для меня - это возможность отфильтровать значения, проверить некоторые условия, получить минимальное/максимальное значение и присвоить значение некой переменной.

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

Я не планирую затмить Ричча Хикки, разработчиков newLisp, picoLisp, Kawa или какого-нибудь другого lisp-name, я даже не заявляю, что мой скриптовый язык будет именно языком семейства Lisp, а будет Lisp-образный.

Для меня важна возможность определять функции как со стороны Lisp-кода, так и со стороны Scala-кода. Но при этом, я не обещаю бесшовного интеропа.

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

Что же уже решено

Типы данных:

  • Строка(поддерживающая стандартный эскейпинг строк)
  • Целые числа(скаловый Long)
  • Числа с плавающей запятой(скаловый Double)
  • Булевые значения(используются ключевые слова true и false, никаких #f, #t или других специальных значений)
  • Списки
  • Nil - пустой список, null будет в него тоже кастоваться
  • Функция
  • Идентификатор(на переменную или функцию)

Общее пространство имен для кода и данных.

Отсутствие классических Lisp-макросов(просто по причине отсутствия компиляции, нет компиляции - нет смысла в макросах)

Парсинг на парсер-комбинаторах(библиотека lihaoyi/fastparse).

Вся работа будет вестись публично, с написанием статей в блог, а так же с публичным git-репозиторием

Парсинг

Начал я разработку с разбора выражений из строк, с использованием библиотеки fastparse.

Ознакомиться с ней можно на ее официальной странице.

Начнем с разбора числовых значений.

Каждое числовое значение состоит из цифр(вне зависимости от того - целое число или с плавающей запятой). Для этого опишем наш парсер цифр:

val digitsParser = P(CharsWhileIn("0123456789"))

Данный комбинатор выбирает символы, которые находятся в указанном списке(а строки в Scala - это список символов). Что ж, практически все, что требуется для разбора целого числа нам достататочно(а еще неплохо было бы иметь знак числа) и мы пишем следующую конструкцию:

val longsParser = P(("-".? ~ digitsParser).!.map(_.toLong))

Конструкция "-".? указывает, что ведущим символом может быть минус, а может и не быть, после чего мы объединяем наши парсеры с помощью метода ~, получая парсер, который ищет последовательность цифр, с опционально, ведущим минусом. Метод ! возвращает нам всю последовательность в виде одной строки. map применется к успешному результату и выполнит кастование нашего числа к числу.

Попробуем спарсить наше число?

scala> longsParser.parse("-666999")
res0: fastparse.core.Parsed[Long,Char,String] = Success(-666999,7)

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

Отлично, но теперь мы хотим получить и числа с плавающей запятой.

У такого числа, помимо целой части, есть еще дробная часть, и, потенциально, экспоненциальная. Для них парсеры пишутся достаточно легко:

val fractionalParser = P("." ~ digitsParser)
val exponentParser = P(CharIn("eE") ~ CharIn("+-").? ~ digitsParser)
  

Теперь, нам нужно получить парсер, который бы работал как целая часть+дробная и потенциально экспоненциальная часть числа.

val doubleParser = P(("-".? ~ (digitsParser ~ fractionalParser ~ exponentParser.?)).!.map(_.toDouble))

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

scala> doubleParser.parse("-12.3e-1")
res1: fastparse.core.Parsed[Double,Char,String] = Success(-1.23,8)

Отлично, а попробуем разобрать идентификаторы. Идентификатор в нашем языке - это последовательность символов начинающаяся со спец.символа или буквы и состоящая из букв, цифр или спец.симоволов. Например: def, hello, >, isNil?

Для этого опишем парсеры для стандартных букв и спец.символов:

val specialCharsParser = P(CharsWhileIn("!@#$%^&*_-><="))
val charParser = P(CharIn('A' to 'Z') | CharIn('a' to 'z'))

А так же и сам парсер идентификаторов:

val identityParser = P(((charParser | specialCharsParser) ~ (digitsParser | specialCharsParser | charParser).rep).!)

Проверка показывает, что все работает как надо:

scala> identityParser.parse("isNil?")
res2: fastparse.core.Parsed[String,Char,String] = Success(isNil,5)

scala> identityParser.parse("1isNil?")
res3: fastparse.core.Parsed[String,Char,String] = Failure((charParser | specialCharsParser):1:1 ..."1isNil?")

scala> identityParser.parse(">>=")
res4: fastparse.core.Parsed[String,Char,String] = Success(>>=,3)

Попробуем собрать теперь список из известных нам значений(а это практически готовый самая важная часть каждого Lisp-образного языка)!

Для этого попробуем сделать парсер, который разбирает все известные нам конструкции:

val valueParser = P(doubleParser | longsParser | identityParser)

И он работает как нужно:

scala> valueParser.parse("123")
res5: fastparse.core.Parsed[Any,Char,String] = Success(123,3)

scala> valueParser.parse("123.3e3")
res6: fastparse.core.Parsed[Any,Char,String] = Success(123300.0,7)

scala> valueParser.parse("isNull?")
res7: fastparse.core.Parsed[Any,Char,String] = Success(isNull,6)

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

Требуемый парсер выглядит очень просто:

val separatorParser = P(CharsWhileIn(" \r\n\t,").?)

Приступим к парсеру списков - он описывается как значения или списки, окруженные круглыми скобками и разделенные между собой с помощую разделителей.

val listParser:Parser[Object] = P(("(" ~/ (valueParser | listParser).rep(sep = separatorParser) ~ separatorParser ~ ")"))

Здесь у нас появляется интересный момент - параметр sep у метода rep - он позволяет указать разделитель между последовательностью элементов. Парсер рекурсивный - поэтому тип указывать обязательно. Пока у нас упрощенный вариант - укажем тип Object, но в реальности все данные нужно будет обернуть в ADT.

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

scala> listParser.parse("(hello 123 1.33)")
res8: fastparse.core.Parsed[Object,Char,String] = Success(ArrayBuffer(hello, 123, 1.33),16)

scala> listParser.parse("(hello 123 (1.33 world))")
res11: fastparse.core.Parsed[Object,Char,String] = Success(ArrayBuffer(hello, 123, ArrayBuffer(1.33, world)),24)

Немного о типах

Для того, чтобы не оперировать списками от Any или другим подобным адом необходимо ввести наши типы данных для интерпретатора. Все типы данных у нас будут наследоваться от трейта EllsTypes

sealed trait EllsType

И, к примеру, индентификатор у нас из просто строки превратится в EllsIdentifier:

case class EllsIdentifier(v: String) extends EllsType {
  override def toString: String = v
}

А наш парсинг, превращается уже вот в такую конструкцию(мы полученную строку заворачиваем в EllsIdentifier)

val identityParser: Parser[EllsType] = P(((charParser | specialCharsParser) ~ (digitsParser | specialCharsParser | charParser).rep).!.map(id => EllsIdentifier(id)))

Со всеми остальными типами проделываем тоже самое. Дописываем остальное(у меня на гитхабе уже немного дописано) и покрываем тестами.

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