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

07.10.2018

Создание лисп-подбного скриптового языка. Часть 4. Функции и цитаты, с возможностью разцитирования фрагментов

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

В этой статье мы реализуем функции, а так же починим наши цитаты(реализовав форму unquote).

Да будут функции

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

case class EllsFunction(args: List[EllsIdentifier], body: Seq[EllsType]) extends EllsType

Для объявления функции(без связывания с именем) будем использовать форму (fn (список-параметров) ...тело) и добавим в наш eval еще эту форму. Параметров у нас может и не быть - в этом случае можно передать вместо них просто nil(или в форме пустых круглых скобок), либо в качестве параметров будет указан список идентификаторов. И форма задания функции записывается очень просто:

 def fnForm(args: Args, env: Env): EllsType = {
    val funArgs = args.head
    funArgs match {
      case EllsNil() => EllsFunction(List.empty, args.tail)
      case EllsList(l) => EllsFunction(l.map(_.toIdentifier), args.tail)
      case _ => throw EllsEvalException(s"wrong function form (fn $args)")
    }
  }

Это позволит нам уже получить несвязанное определение функции, которое может будет связать через форму def с идентификатором, например так:

(def incr (fn (x) (+ 1 x)))

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

scala> val env = Env.empty
env: com.nihirash.ells.Env = Env(None,Map())

scala> val expr0 = "(def incr (fn (x) (+ 1 x)))"
expr0: String = (def incr (fn (x) (+ 1 x)))

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

scala> Parser(expr0).map(eval.eval(_, env))
res2: scala.util.Either[String,com.nihirash.ells.EllsType] = Right((fn (x) (+ 1 x)))

scala> env
res3: com.nihirash.ells.Env = Env(None,Map(incr -> EllsFunction(List(x),List((+ 1 x)))))

У нас имеется связанная с именем функция, которую нам нужно теперь выполнить.

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

def evalFunction(fn: EllsFunction, args: Args, env: Env): EllsType = {
    if (fn.args.length != args.length) throw EllsArityException()
    val argValues = fn.args zip args
    val innerEnv = Env(
      parent = Some(env),
      definitions = MutableMap(argValues: _*)
    )
    eval(fn.body, innerEnv)
  }

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

    case _ => env.get(id) match {
      case EllsNil() => EllsNil()
      case f: EllsFunction => evalFunction(f, args.map(evalExpression(_, env)), env)
      case _ => throw EllsEvalException(s"Can't eval form '$id' with args '$args'")
    }

Попробуем выполнить наш код, даже с вложенным вызвовом функции:

scala> val expr1 = "(incr (incr 1))"
expr1: String = (incr (incr 1))

scala>  Parser(expr1).map(eval.eval(_, env))
res4: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(3.0)

Функция выполнилась корректно! Чтобы избежать многословности в духе (def var (fn (.... создадим небольшой синтаксический сахар в виде функции defn, которая, по факту, просто объединит создание функции и связывание ее со значением.

Попробуем решить практическую задачу с помощью нашего языка.

Для примера, я возьму алгоритм поиска квадратного корня методом Ньютона. Он описан в книге "Структура и Интерпретация Компьютерных Программ"(кстати, очень рекомендую к прочтению эту книгу).

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

Основная функция остается, практически неизменной(не считая имена ключевых слов):

(defn sqrt-iter (guess x)
	(if (good-enought? guess x)
		guess
		(sqrt-iter (improve guess x)
			       x)))

(defn improve (guess x)
	(average guess (/ x guess)))

(defn average (x y)
	(/ (+ x y) 2))
	
(defn good-enought? (guess x)
	(< (abs (- (square guess) x)) 0.001))
		

Но нам не хватает функций возведения в квадрат и получения абсолютного значения числа - реализуем их:

(defn square (x)
	(* x x))
	
(defn abs (x)
	(if (> x 0) x (- 0 x)))

А так же, определим точку входа:

(defn sqrt (x)
	(sqrt-iter 1.0 x))

И попробуем получить значение:

scala> val testPrg = """
     | (defn sqrt-iter (guess x) (if (good-enought? guess x) guess (sqrt-iter (improve guess x) x)))
     | 
     | (defn improve (guess x) (average guess (/ x guess)))
     | 
     | (defn average (x y) (/ (+ x y) 2))
     | 
     | (defn good-enought? (guess x) (< (abs (- (square guess) x)) 0.001))
     | 
     | (defn square (x) (* x x))
     | 
     | (defn abs (x) (if (> x 0) x (- 0 x)))
     | 
     | (defn sqrt (x) (sqrt-iter 1.0 x))
     | 
     | (sqrt 9)"""
testPrg: String =
"
(defn sqrt-iter (guess x) (if (good-enought? guess x) guess (sqrt-iter (improve guess x) x)))

(defn improve (guess x) (average guess (/ x guess)))

(defn average (x y) (/ (+ x y) 2))

(defn good-enought? (guess x) (< (abs (- (square guess) x)) 0.001))

(defn square (x) (* x x))

(defn abs (x) (if (> x 0) x (- 0 x)))

(defn sqrt (x) (sqrt-iter 1.0 x))

(sqrt 9)"

scala> Parser(testPrg).map(eval.eval(_, env))
res3: scala.util.Either[String,com.nihirash.ells.EllsType] = Right(3.00009155413138)

Наш интерпретатор уже способен выполнять полезный код!

Все же вернемся к нашим цитатам

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

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

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

Для начала примем небольшие соглашения - сократим записать (quote expr) и (unquote expr), как 'expr и @expr соответственно.

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

(def x 1)

(set! 'x 2)

x

Результатом выполнения этого кода должно стать числовое значение 2.

Функция set! должна принять следующий вид:

(defn set! (var val)
	(eval '(set @var @val)))

Будем считать выполнение этого кода - условным показателем рабочести цитат. Я же его вынес в код теста(конкретно этот для исполнения конструкции eval и исполнял пока не получил положительный результат).

    "eval" - {
      "will eval quoted expression" in {
        val env = Env.empty
        val expression =
          """
            |(def x 1)
            |(defn set! (var val)
            | (eval '(set @var @val)))
            |
            | (set! 'x 2)
            | x
          """.stripMargin
        val evaled = Parser(expression).map(eval.eval(_, env))

        evaled shouldEqual Right(EllsLong(2))
      }
    }

Добавим к этому еще тест-кейс просто на правильный quote-unquote:

"quote" - {
	"will eval unquoted values" in {
        val expression1 = "'(1 2 @(+ 1 2))"
		Parser(expression1).map(eval.eval(_, Env.empty)) shouldEqual Right(EllsList(List(
          EllsLong(1), EllsLong(2), EllsLong(3)
        )))
	}
}

Для начала добавим в парсер краткую запись quote и unquote:

val quoteParser: Parser[EllsType] = P("'" ~ expressionParser).map(v => EllsList(List(EllsIdentifier("quote"), v)))
val unquoteParser: Parser[EllsType] = P("@" ~ expressionParser).map(v => EllsList(List(EllsIdentifier("unquote"), v)))

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

После чего необходимо доработать обработчик функции quote, чтобы он проходил все вложенные списки и искал форму unquote и вычислял ее:

private def quote(tail: Args, env: Env): EllsType = tail match {
    case h :: Nil => unquote(h, env)
    case h :: t => throw EllsArityException()
    case Nil => throw EllsArityException()
}

private def unquote(arg: EllsType, env: Env): EllsType = arg match {
    case EllsList(List(EllsIdentifier("unquote"), v)) => evalExpression(v, env)
    case EllsList(v) => EllsList(v.map(unquote(_, env)))
    case t: EllsType => t
}

Тест на цитаты начал проходить, осталось реализовать форму eval, которую можно реализовать просто как простой кейс функции evalCall:

case "eval" => eval(args.map(a => evalExpression(a, env)), env)

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