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

15.09.2018

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

Продложение цикла моих статей по разработке интерпретатора.

В этой статье мы приступим к интерпретации простых выражений.

Небольшое вступление

Все типы, используемые у нас в интерпретаторе уже наследуются от трейта EllsType. Для "скалярных" типов есть трейт EllsScalar, а так же каждый из типов реализует методы toNumber, toString(стандартный метод Scala, но приведенный к нужному поведению) и isNil(является ли значение ложным, для небулевых - пустым).

Парсер был чуть доработан, чтобы его apply-метод принимал строку, а возвращал Either содержащий последовательность c типом EllsType(а это любой валидный код) либо сообщение об ошибке.

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

О том, как мы интерпретируем код

Результатом интерпретации нашего кода всегда должен быть тип данных, нашего скриптового языка. Т.е. Функция интерпретации выражения имеет тип EllsType => EllsType.

Если к ней на вход попадает скалярное выражение - мы его возвращаем как есть. Что же у нас является скалярными типами данных?

  • Числа - с плавающей запятой и без
  • Строки
  • Булевые выражения
  • nil

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

Интерпретация

Наш код в плавно превращается во что то такое:

def evalExpression(e: EllsType): EllsType = e match {
    case e: EllsScalar => e
    case l: EllsList => evalForm(l)
    case _ => throw new Exception("Can't eval")
  }

def evalForm(l: EllsList): EllsType = {
    val car = l.v.head
    val cdr = l.v.tail
    car match {
      case i: EllsIdentifier => evalCall(i, cdr)
      case f => throw new RuntimeException(s"Cant eval form: $l")
    }
  }

def evalCall(id: EllsIdentifier, tail: List[EllsType]): EllsType = ???

Теперь нам необходимо реализовать исполнение каких либо форм. Начнем с самой простой - quote - ее суть заключается в том, чтобы вернуть переданное ей значение без каких либо изменений. И наша функция evalCall получает свою минимальную реализацию:

  def evalCall(id: EllsIdentifier, tail: List[EllsType]): EllsType = id.v match {
    case "quote" => tail match {
      case h :: Nil => h
      case h :: t => throw EllsArityException()
      case Nil => throw EllsArityException()
    }
    
    case f => throw EllsEvalException(s"Can't eval '$f' form")
}

Что ж, попробуем выполнить код(из sbt console):

scala> import com.nihirash.ells._
import com.nihirash.ells._

scala> val eval = new Eval
eval: com.nihirash.ells.Eval = com.nihirash.ells.Eval@4f05f695

scala> Parser("(quote (hello world))").map(_.head).map(eval.evalExpression)
res0: scala.util.Either[String,com.nihirash.ells.EllsType] = Right((hello world))

Выглядит как раз, как надо!

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

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

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

    case "+" =>
      val args = tail.map(v => evalExpression(v).toNumber)
      args.tail.fold(args.head)((l: EllsNumber, r: EllsNumber) => l + r)

Следует обратить внимание на то, что сложение, вычитание, умножение и деление являются методами трейта EllsNumber - числовых типов данных.

Учитывая исполнение всех аргументов - то мы получим исполнение и всех вложенных вычислений:

scala> Parser("(+ 1 2 (+ 3.3 2.2 (quote 3)))").map(_.head).map(eval.evalExpression)
res2: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(11.5)

Вычитание, деление и умножение делаем абсолютно по аналогии.

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

В случае, если условие будет ложным, а ложная форма отсутствует - то будет возвращено nil.

Аргументы не исполняются автоматически(кроме условия) и в зависимости от того является ли nil-ом условие будет выполнена либо ложная-форма, либо истенная.

case "if" =>
      tail match {
        case expression :: rightCase :: leftCase :: Nil =>
          if (!evalExpression(expression).isNil)
            evalExpression(rightCase)
          else
            evalExpression(leftCase)
        case expression :: rightCase :: Nil =>
          if (!evalExpression(expression).isNil)
            evalExpression(rightCase)
          else
            EllsNil()
        case _ => throw EllsArityException("Wrong IF-form")
      }

Что ж, проверим:

scala> Parser("(if true (+ 1 1) (- 1 1))").map(_.head).map(eval.evalExpression)
res3: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(2.0)

scala> Parser("(if false (+ 1 1) (- 1 1))").map(_.head).map(eval.evalExpression)
res4: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(0.0)

Работает, но врядли наши условия будут всегда требовать исполнения лишь одной функции/формы.

Да и программа на Lisp обычно состоит более, чем из одной команды. Для этого нам необходимо реализовать исполнение не одного выражения, а блока. Результатом же исполнения блока является последнее вычисленное значение.

Реализуем функцию eval:

  def eval(exprs: Seq[EllsType]): EllsType = exprs.map(evalExpression).last

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

scala> Parser("\"Некая строка\" (* 3 (+ 10 11)) nil").map(eval.eval)
res10: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(EllsNil())

Несмотря на вычисления, которые были в блоке до этого, мы получили последнее вычисленное значение - nil.

Теперь реализуем форму, позволяющую принимать блок кода, вместо одного выражения - назовем ее формой do

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

    case "do" => eval(tail)

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

Что ж, пока что не много, но уже работающая интерпретация s-выражений.

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