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

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

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

Синтаксис

• 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) — пример операции именования переменной в выражении.

Реализация

  <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>

Вычисления

  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)"
    }
}

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

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()
                        } 
        

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

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)
    }

Синтаксис

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 накладывает ограничения);
• Отсутсвие других типов, кроме целочисленного.

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