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

25.09.2018

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

Что ж, продолжу свой цикл статей о ходе разработки интерпретатора ЛИСП-подобного языка.

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

Напоминаю, что ход разработки можно отследивать на github-странице проекта.

Что ж, вернемся к самой разработке.

Недолго подумав, я решил, что связывание в языке будет лексическим, а не динамическим. Это не настолько сложнее реализуется, насколько упрощает жизнь тем, кто пользуется этим. Некоторые современные языки семейства Lisp до сих пор имеют динамическое связывание(например, picoLisp) и я имел опыть отстреливания себе колений с помощью таких языков.

Реализуем окружение

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

Так как определения у нас могут изменяться в качестве хранилища их используем мутабельный мэп из scala.collection.mutable и case-класс описывающий наше окружение принимает следующую сигнатуру:

import scala.collection.mutable.{Map => MutableMap}

case class Env(parent: Option[Env], definitions: MutableMap[EllsIdentifier, EllsType] = MutableMap.empty)

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

Для этого реализуем метод define:

  def define(id: EllsIdentifier, value: EllsType): Unit = definitions.update(id, value)

Значение мы можем установить, но его нам нужно получить. И тут мы сталкиваемся с тем, что определние может быть объявлено не в нашем окружении, а в родительском, для этого нам необходимо рекурсивно пройти вверх по всем определенным определениям.

В этом нам поможет метод getOrElse определенный, как для Option, так и для Map. А в случае, если мы ничего не нашли - кинем исключение.

Наш метод получает следующий вид:

  def get(id: EllsIdentifier): EllsType = definitions.getOrElse(
    id,
    parent.getOrElse(throw EllsDefinitionNotFound()).get(id)
  )

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

scala> val env0 = Env(parent = None)
env0: com.nihirash.ells.Env = Env(None,Map())

scala> val env1 = Env(parent = Some(env0))
env1: com.nihirash.ells.Env = Env(Some(Env(None,Map())),Map())

scala> env0.define(EllsIdentifier("x"), EllsString("строка"))

scala> env1.get(EllsIdentifier("x"))
res1: com.nihirash.ells.EllsType = строка

scala> env1.define(EllsIdentifier("x"), EllsString("другая строка"))

scala> env1.get(EllsIdentifier("x"))
res3: com.nihirash.ells.EllsType = другая строка

scala> env0.get(EllsIdentifier("x"))
res4: com.nihirash.ells.EllsType = строка

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

Но иногда требуется изменить значение из вышестоящего окружения на нужное, что же делать в этом случае? Для этого нам необходимо реализовать метод set, который будет искать определение рекусивно по всем окружениям и изменять его только в том окружении, в котором оно объявлено. И в случае, если объявление не будет найдено - будет выброшено исключение:

 def set(id: EllsIdentifier, value: EllsType): Unit =
    definitions.get(id) match {
      case Some(_) => definitions.update(id, value)
      case None => parent.getOrElse(throw EllsDefinitionNotFound()).set(id, value)
    }

Для теста объявим в окружении env0 новое определение, а из окружения env1 порпобуем его обновить и посмотрим, что же у нас получилось:

scala> env0.define(EllsIdentifier("second"), EllsString("тест"))

scala> env1.set(EllsIdentifier("second"), EllsString("обновили"))

scala> env0.get(EllsIdentifier("second"))
res7: com.nihirash.ells.EllsType = обновили

scala> env1.get(EllsIdentifier("second"))
res8: com.nihirash.ells.EllsType = обновили

Окружения работают(сами по себе), теперь было бы неплохо их объеденить с eval'ом.

Добавим связывание в наш интерпретатор

Что ж, для начала прокинем везде наше окружение в коде класса Eval, начиная от метода eval и до самого конца. Расписывать все изменения я не буд - вы их легко увидете на github.

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

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

  def evalExpression(e: EllsType, env: Env): EllsType = e match {
    case e: EllsScalar => e
    case l: EllsList => evalForm(l, env)
    case i: EllsIdentifier => env.get(i)
    case _ => throw new Exception(s"Can't eval $e")
  }

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

scala> var parsed = Parser("(list x \"привет\")")
parsed: com.nihirash.ells.Parser.parseResult = Right(ArrayBuffer((list x привет)))

scala> val eval = new Eval
eval: com.nihirash.ells.Eval = com.nihirash.ells.Eval@7855c699

scala> parsed.map(eval.eval(_, env0))
res11: scala.util.Either[String,com.nihirash.ells.EllsType] = Right((строка привет))

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

Для этого нам нужно обеспечить вычисление форм def(связать определение с текущим окружением) и set(изменить значение текущего определения).

Выполнение этих форм вынесем в функции defForm и setForm, первый аргумент который должен быть идентификатором, а второй - значением, и все, что они делают - вызывают на текущем окружении функции define и set.

  private def defForm(args: Args, env: Env): EllsType = {
    val id = args.head
    id match {
      case id: EllsIdentifier =>
        args.tail match {
          case value :: Nil =>
            env.define(id, evalExpression(value, env))
            value
          case _ => throw EllsArityException("Expected one expression")
        }
      case _ => throw EllsTypesException("Expected identifier")
    }
  }

  private def setForm(args: Args, env: Env): EllsType = {
    val id = args.head
    id match {
      case id: EllsIdentifier =>
        args.tail match {
          case value :: Nil =>
            env.set(id, evalExpression(value, env))
            value
          case _ => throw EllsArityException("Expected one expression")
        }
      case _ => throw EllsTypesException("Expected identifier")
    }
  }

Не забудем добавить эти формы в метод evalCall и можем проверять:

scala> var defSetEval = Parser("(def var1 123) (def var2 321) (set var2 234) (list var1 var2)")
defSetEval: com.nihirash.ells.Parser.parseResult = Right(ArrayBuffer((def var1 123), (def var2 321), (set var2 234), (list var1 var2)))

scala> defSetEval.map(eval.eval(_, env0))
res12: scala.util.Either[String,com.nihirash.ells.EllsType] = Right((123 234))

scala> env0.definitions
res13: scala.collection.mutable.Map[com.nihirash.ells.EllsIdentifier,com.nihirash.ells.EllsType] = Map(var2 -> 234, var1 -> 123, second -> обновили, x -> строка)

Теперь наш код может быть более осмысленным, мы можем определять переменные и выполнять несложные вычисления.

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