The language of arithmetic expressions with the let construction as dsl on Kotlin

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

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

In the article, the reader will get acquainted with such Kotlin constructions as extensions function, pattern matching, operator overriding, infix functions and some principles of functional programming. Writing a parser is not included in the topic of the article; therefore, we will implement our language inside the kotlin language, like the scripting languages of the build systems with respect to the scripting languages that were first written (grodle: groovy). The material is served in sufficient detail. Preferred knowledge of Java.

Formulation of the problem

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

In our language there must be integer constants, named expressions (let, where), addition and multiplication operations (for simplicity).

Syntax

const(2) is a constant;
variable("x") is a named expression. “X” is not a variable in terms of the value assignment operation. This is just the name of a certain expression defined before or after the current expression;
const(2) + const(2) is an example of the addition operation;
variable("y") * 2 is an example of a multiply operation;
variable("y") * const(2) is an example of a multiply operation;
"x" let (const(2)) inExr (variable("x") * 4) is an example of a variable naming operation in an expression;
(variable("x") * 4) where ("x" to 1) is 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 Backus – Naur form . In this scheme, number is an integer, string is a string from the standard library:

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

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 the calculation.

Calculations

We describe the structure of terms in the form of classes. We will use the sealed class, since it will be convenient for us to use it as a model . In Cotlin, the pattern matching mechanism is syntactic sugar over switch case, isInstace from java constructs, 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 the available fields defined in its descendants. This is implemented with the help of smart-casts : implicit type casting inside the body of if (obj is Type) structures. In similar code in java, you would have to manually type types.

Now we can describe expressions by exporting the constructors of classes-heirs Expr, and so far this is enough for us. In the syntax section, we describe functions that allow you to write expressions more succinctly.

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

We will calculate expressions with the help of a recursive function by successively “expanding” expressions. Then it's time to remember about naming. To implement the let construct, we need to store the named expressions somewhere. Let us introduce the notion of calculation context: a list of pairs name -> expression context: Map<String, Expr?> . If you encounter a variable in the course of the calculation, we need to get the expression out of context.

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

A few words about the code:

The context uses immutable objects. This means that by 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 not allowed. The function should define the mapping of one set to another. You can solve the error problem during the calculation by entering the type for the result of the calculation:
```
  sealed class Result { class Some(val t: Expr) : Result() class Error(val message: String, val where: Expr) : Result() } 
```
Using the functions from the standard library, you can shorten the code somewhat; this will be done at the end of the article.

There are cases when we can predict the result of a calculation before it is completed. For example, when multiplying by 0, the result will be 0. Entering the function-extension fun Expr.isNull() = if (this is Expr.Const) c == 0 else false multiplication takes 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, the division will require verification of the division by 0

Syntax

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

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

Examples

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

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