Язык арифметических выражений с конструкцией let как dsl на Kotlin

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

variable("hello") + variable("habr") * 2016 where ("hello" to 1) and ("habr" to 2)

В статье читатель познакомится с такими конструкциями Kotlin, как extensions function, pattern matching, operator overriding, infix functions и некоторыми принципами функционального программирования. Написание парсера не входит в тему статьи, поэтому наш язык будем реализовывать внутри языка kotlin, подобно языкам скриптов систем сборки по отношению к скриптовым языкам, на которые первые написаны (grodle: groovy). Материал подается достаточно подробно. Желательно знание Java.

Постановка задачи

• определить синтаксис языка арифметических выражений;
• реализовать вычисление;
• придерживаться принципов функционального программирования

В нашем языке должны быть целочисленные константы, именованные выражения (let, where), операции сложения и умножения (для простоты).

Синтаксис

• const(2) — константа;
• variable("x") — именованное выражение. «x» не является переменной с точки зрения операции присвоения значения. Это лишь имя некого выражения, определенного до или после текущей выражения;
• const(2) + const(2) — пример операции сложения;
• variable("y") * 2 — пример операции умножения;
• variable("y") * const(2) — пример операции умножения;
• "x" let (const(2)) inExr (variable("x") * 4) — пример операции именования переменной в выражении;
• (variable("x") * 4) where ("x" to 1) — пример операции именования переменной в выражении.

Реализация

Для формализации синтаксиса языка удобно представлять выражения в форме Бэкуса — Наура. В данной схеме number — это целое число, string — строка из стандартной библиотеки:

  <expr> ::= (<expr>) | <const> | <var> | <let> | <operator>
  <const> := const(<number>)
  <var> := variable(<string>)
  <let> := <var> let <number> inExpr (<expr>) | <var> let <expr> inExpr (<expr>) | <let where>
  <let where> := (<expr>) where (<let where pair> ) | <let where> and (<let where pair> ) 
  <let where pair> ::= <var> to <const> | <var> to <number> | <var> to (<expr>)
  <operator> := <expr> * <expr> | <expr> + <expr> | <expr> * <number> | <expr> + <number>

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

Вычисления

Опишем структуру термов в виде классов. Мы будет использовать sealed class, так как далее нам будет удобно использовать его как образец. В котлине механизм паттерн матчинга является синтаксических сахаром над конструкциями switch case, isInstace из java, но не полноценным сопоставлением с образцом из мира функциональных языков.

  sealed class Expr {
    //константа лишь хранит свое значение
    class Const(val c: Int): Expr()
    //переменная хранит имя выражения
    class Var(val name : String) : Expr()

    //let конструкция хранит имя выражения и связанное выражение и выражение, где используется данное имя
    //мы будем использовать один класс для и для where конструкций 
    class Let(val name: String, val value: Expr, val expr: Expr) : Expr()

    //сумма хранит 2 выражения
    class Sum(val left : Expr, val right: Expr) : Expr()

    //произведение хранит 2 выражения
    class Sum(val left : Expr, val right: Expr) : Expr()

    override fun toString(): String = when(this) {
        is Const -> "$c"
        is Sum -> "($left + $right)"
        is Mult -> "($left * $right)"
        is Var -> name
        is Let -> "($expr, where $name = $value)"
    }
}

В зависимости от типа expr, нам становятся доступные поля, определенные в его потомках. Это реализуется с помощью smart-casts: неявного приведения типа внутри тела подобных if (obj is Type) конструкций. В аналогичном коде на языке java приходилось бы приводить типы вручную.

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

val example = Expr.Sum(Expr.Const(1), Expr.Const(2))

Вычислять выражения мы будем с помощью рекурсивной функции последовательно «раскрывая» выражения. Тут пора вспомнить про именования. Для реализации let конструкции нам понадобится где-то хранить именованные выражения. Введем понятие контекст вычисления: список пар имя -> выражение context: Map<String, Expr?>. Если вы встретим переменную по ходу вычисления, мы должны получить выражение из контекста.

fun solve(expr: Expr, context: Map<String, Expr? >? = null) : Expr.Const = when (expr) {
    //в случае константы просто вернем ее, вычисление завершено
    is Expr.Const -> expr
    //вернем перемноженные результаты левого и правого выражения 
    is Expr.Mult -> Expr.Const(solve(expr.left, context).c * solve(expr.right, context).c)
    
    //вернем сложенные результаты левого и правого выражения
    is Expr.Sum -> Expr.Const(solve(expr.left, context).c + solve(expr.right, context).c)
    
    //в текущий контекст добавим новую пару name -> value и вернем результат expr в новом контексте
    is Expr.Let -> {
        val newContext = context.orEmpty() + Pair(expr.name, expr.value)
        solve(expr.expr, newContext)
    }
    
    //если в контексте есть имя expr.name, вернем результат выражения, иначе остановим вычисления исключением
    is Expr.Var -> {
        val exprFormContext : Expr? = context?.get(expr.name)
        if (exprFormContext == null) {
            throw IllegalArgumentException("undefined var ${expr.name}")
        } else {
            solve(exprFormContext, context!!.filter { it.key != expr.name })
        }
    }
}

Несколько слов о коде:

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

   sealed class Result { 
                           class Some(val t: Expr) : Result()
                           class Error(val message: String, val where: Expr) : Result()
                        } 
        

• С помощью функций из стандартной библиотеки можно несколько сократить код, это будет сделано в конце статьи

Бывают случаи, когда мы можем предсказать результат вычисления еще до его завершения. К примеру, при умножении на 0 результат будет 0. Введя функцию-расширение fun Expr.isNull() = if (this is Expr.Const) c == 0 else false умножение примет следующий вид:

is Expr.Mult -> when {
        p1.left.isNull() or p1.right.isNull() -> const(0)
        else -> const(solve(p1.left, context).c * solve(p1.right, context).c)
    }

К аналогичному подходу можно прибегать при реализации других операций. К примеру для деления потребуется проверка деления на 0

Синтаксис

Для реализации синтаксиса используются extension-functions и operator-overloading. Выглядит это весьма наглядно.

fun variable(name: String) = Expr.Var(name)
fun const(c : Int) = Expr.Const(c)

//const(1) * const(2) == const(1).times(const(2))
infix operator fun Expr.times(expr: Expr): Expr = Expr.Mult(this, expr)
infix operator fun Expr.times(expr: Int): Expr = Expr.Mult(this, const(expr))
infix operator fun Expr.times(expr: String) : Expr = Expr.Mult(this, Expr.Var(expr))

//аналогично для плюс
infix operator fun Expr.plus(expr: Expr): Expr = Expr.Sum(this, expr)
infix operator fun Expr.plus(expr: Int): Expr = Expr.Sum(this, const(expr))
infix operator fun Expr.plus(expr: String) : Expr = Expr.Sum(this, Expr.Var(expr))

//where
infix fun Expr.where(pair: Pair<String, Expr>) = Expr.Let(pair.first, pair.second, this)
@JvmName("whereInt")
infix fun Expr.where(pair: Pair<String, Int>) = Expr.Let(pair.first, const(pair.second), this)
@JvmName("whereString")
infix fun Expr.where(pair: Pair<String, String>) = Expr.Let(pair.first, variable(pair.second), this)

//let and
infix fun Expr.and(pair: Pair<String, Int>) = Expr.Let(pair.first, const(pair.second), this)

@JvmName("andExr")
infix fun Expr.and(pair: Pair<String, Expr>) = Expr.Let(pair.first, pair.second, this)

//let реализуется через вспомогательный класс:
// ("s".let(1)).inExr(variable("s"))
class ExprBuilder(val name: String, val value: Expr) {
    infix fun inExr(expr: Expr): Expr
            = Expr.Let(name, value, expr)
}

infix fun String.let(expr: Expr) = ExprBuilder(this, expr)
infix fun String.let(constInt: Int) = ExprBuilder(this, const(constInt))

Примеры

fun testSolve(expr: Expr, shouldEquals: Expr.Const) {
    val c = solve(expr)
    println("$expr = $c, correct: ${shouldEquals.c == c.c}")
}

fun main(args: Array<String>) {
    val helloHabr = variable("hello") * variable("habr") * 3  where ("hello" to 1) and ("habr" to 2)
    testSolve(helloHabr, const(1*2*3))

    val e = (const(1) + const(2)) * const(3)
    testSolve(e, const((1 + 2) *3))

    val e2 = "x".let(10) inExr ("y".let(100) inExr (variable("x") + variable("y")))
    testSolve(e2, const(110))

    val e3 = (variable("x") * variable("x") * 2) where ("x" to 2)

    testSolve(e3, const(2*2*2))

    val e4 = "x" let (1) inExr (variable("x") + (variable("x") where ("x" to 2)))

    testSolve(e4, const(3))

    val e5 = "x" let (0) inExr (variable("x") * 1000 + variable("x"))
    testSolve(e5, const(0))
}

((((hello * habr) * 3), where hello = 1), where habr = 2) = 6, correct: true
((1 + 2) * 3) = 9, correct: true
(((x + y), where y = 100), where x = 10) = 110, correct: true
(((x * x) * 2), where x = 2) = 8, correct: true
((x + (x, where x = 2)), where x = 1) = 3, correct: true
(((x * 1000) + x), where x = 0) = 0, correct: true

Недостатки решения

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

• Неэффективность методов вычисления и представления термов;
• Отсутствие описанной грамматики и приоритета операций;
• Ограниченный синтаксис (несмотря на выразительность, kotlin накладывает ограничения);
• Отсутсвие других типов, кроме целочисленного.

Идеологические

• Исключения рушат красоту чистых функций;
• Отсутсвие ленивости вычисления, присущие некоторым функциональным языкам.

P.S.
Приветствуется критика к изложению и коду.

Автор: punksta

Источник