Мову арифметичних виразів з конструкцією let як dsl Kotlin

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

variable("привіт") + variable("habr") * 2016 where"привіт" 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©

//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("привіт") * variable("habr") * 3 where"привіт" 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), де y = 100), де x = 10) = 110, correct: true
(((x * x) * 2), де x = 2) = 8, correct: true
((x + (x, де x = 2)), де x = 1) = 3, correct: true
(((x * 1000) + x), де x = 0) = 0, correct: true


Недоліки рішення
Постановка задачі та рішення є навчальними. У рішенні можна виділити наступні недоліки:
Прагматичні:
  • Неефективність методів обчислення та подання термів;
  • Відсутність описаної граматики і пріоритету операцій;
  • Обмежений синтаксис (незважаючи на виразність, kotlin накладає обмеження);
  • Відсутність інших типів, крім цілочисельного.
Ідеологічні
  • Винятку руйнують красу чистих функцій;
  • Відсутність ліниво обчислення, властиві деяким функціональним мовам.


P. S.
Критика вітається до викладу і кодом.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.