Arithmetic expression language with let as dsl construct in Kotlin

Under the cut will be described the implementation of the language of simple arithmetic expressions with let construction. Reading will be interesting for people who are not familiar with the kotlin language or just starting their journey in functional programming.

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

In the article, the reader will get acquainted with Kotlin constructs such as extensions function, pattern matching, operator overriding, infix functions and some principles of functional programming. Writing a parser is not part of the topic of the article, therefore, we will implement our language inside the kotlin language, similar to the scripting languages ​​of assembly systems in relation to the scripting languages ​​that were first written (grodle: groovy). The material is supplied in sufficient detail. Knowledge of Java is desirable.

Formulation of the problem


  • define the syntax of the language of arithmetic expressions;
  • implement the calculation;
  • adhere to the principles of functional programming

Our language should have integer constants, named expressions (let, where), operations of addition and multiplication (for simplicity).

Syntax


  • const(2) Is a constant;
  • variable("x")- a named expression. “X” is not a variable in terms of the value assignment operation. This is just the name of an expression defined before or after the current expression;
  • const(2) + const(2) - an example of an addition operation;
  • variable("y") * 2 - an example of a multiplication operation;
  • variable("y") * const(2) - an example of a multiplication operation;
  • "x" let (const(2)) inExr (variable("x") * 4) - An example of the operation of naming a variable in an expression;
  • (variable("x") * 4) where ("x" to 1) - An example of a variable naming operation in an expression.


Implementation


To formalize the syntax of a language, it is convenient to represent expressions in the form of Backus - Naura . In this scheme, number is an integer, string is a string from the standard library:

 ::= () |  |  |  |  := const()
   := variable()
   :=  let  inExpr () |  let  inExpr () |  := () where ( ) |  and ( ) 
   ::=  to  |  to  |  to ()
   :=  *  |  +  |  *  |  + 

Where possible, const is replaced by number for concise syntax. The issues of its implementation will be described at the end of the article. Now we will be interested in computing.

Calculations


We describe the structure of terms in the form of classes. We will use the sealed class, since it will be more convenient for us to use it as a model . In Kotlin, the matching pattern mechanism is syntactic sugar over switch case, isInstace constructions from java, but not a full-fledged comparison with a sample from the world of functional languages.


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

Depending on the type of expr, we get available fields defined in its descendants. This is implemented using smart-casts : implicit type casting within the body of similar if (obj is Type)structures. In a similar code in java, you would have to cast types manually.

Now we can describe the expressions by exporting the constructors of the Expr descendant classes, and for now this is enough for us. In the syntax section, we describe functions that allow you to write expressions more concisely.

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

We will calculate expressions using a recursive function by sequentially “revealing” the expressions. Then it's time to remember about naming. To implement the let construct, we need to store named expressions somewhere. We introduce the concept of calculation context: a list of pairs name -> expression . If you encounter a variable as part of the calculation, we must get the expression out of context.context: Map

fun solve(expr: Expr, context: Map? = 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 })
        }
    }
}

A few words about the code:

  • For context, immutable objects are used. This means that adding a new pair to the context, we get a new context. This is important for subsequent calculations: functions called from this should not change the current context. This is a fairly common approach in functional programming.
  • From the point of view of pure functions and their calculations, exceptions are unacceptable. The function should determine the mapping of one set to another. You can solve the error problem during calculation by entering a type for the calculation result:

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

  • Using functions from the standard library, you can slightly reduce the code, this will be done at the end of the article

There are times when we can predict the result of a calculation before it is completed. For example, if you multiply by 0, the result will be 0. By entering the extension function, the fun Expr.isNull() = if (this is Expr.Const) c == 0 else false multiplication will take the following form:

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

A similar approach can be resorted to when implementing other operations. For example, division requires checking division by 0

Syntax


To implement the syntax, extension-functions and operator-overloading are used . It looks very clear.


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) = Expr.Let(pair.first, pair.second, this)
@JvmName("whereInt")
infix fun Expr.where(pair: Pair) = Expr.Let(pair.first, const(pair.second), this)
@JvmName("whereString")
infix fun Expr.where(pair: Pair) = Expr.Let(pair.first, variable(pair.second), this)
//let and
infix fun Expr.and(pair: Pair) = Expr.Let(pair.first, const(pair.second), this)
@JvmName("andExr")
infix fun Expr.and(pair: Pair) = 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))

Examples




fun testSolve(expr: Expr, shouldEquals: Expr.Const) {
    val c = solve(expr)
    println("$expr = $c, correct: ${shouldEquals.c == c.c}")
}
fun main(args: Array) {
    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))
}

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


Disadvantages of the solution


The problem statement and solution are educational. The following disadvantages can be distinguished in the solution:
Pragmatic:
  • Inefficiency of methods for calculating and representing terms;
  • Lack of described grammar and priority of operations;
  • Limited syntax (despite expressiveness, kotlin imposes restrictions);
  • Lack of types other than integer.

Ideological
  • Exceptions ruin the beauty of pure functions;
  • Lack of laziness is a computation inherent in some functional languages.


PS
Criticism to the presentation and code is welcome.

Source code with addition of division, real numbers and If expression

Also popular now: