カットの下で、let構築を使用した単純な算術式の言語の実装について説明します。 読書は、kotlin言語に精通していないか、関数型プログラミングの旅を始めたばかりの人にとって興味深いものになります。
variable("hello") + variable("habr") * 2016 where ("hello" to 1) and ("habr" to 2)
この記事では、拡張機能、パターンマッチング、演算子のオーバーライド、中置機能、関数型プログラミングのいくつかの原則などのKotlin構成体について詳しく説明します。 パーサーの作成は記事のトピックの一部ではないため、最初に記述されたスクリプト言語（grodle：groovy）に関連するアセンブリシステムのスクリプト言語と同様に、kotlin言語内に言語を実装します。 材料は十分に詳細に提供されます。 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)は、式で変数に名前を付ける操作の例です。
実装
言語の構文を形式化するには、
Backus-Nauraの形式で式を表すのが便利です。 このスキームでは、数値は整数で、文字列は標準ライブラリの文字列です。
<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は簡潔な構文のために番号に置き換えられます。 実装の問題については、記事の最後で説明します。 次に、コンピューティングに興味があります。
計算
用語の構造をクラスの形式で説明します。
モデルとして使用する方が便利なため、sealedクラスを使用します。 Kotlinでは、マッチングパターンメカニズムは、スイッチケース上の構文シュガー、javaのisInstace構造ですが、関数型言語の世界のサンプルとの本格的な比較ではありません。
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のタイプに応じて、その子孫で定義された使用可能なフィールドを取得します。 これは、
スマートキャストを使用して実装されます。同様の
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 }) } } }
コードに関するいくつかの言葉：
計算が完了する前に計算結果を予測できる場合があります。 たとえば、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による除算のチェックが必要です。
構文
構文を実装するには、
拡張機能と
演算子のオーバーロードが使用されます。 それは非常に明確に見えます。
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 == 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)) }
おわりに ((((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は制限を課します）;
- 整数以外のタイプの欠如。
イデオロギー- 例外は純粋な機能の美しさを台無しにします。
- 怠inessの欠如は、一部の関数型言語に固有の計算です。
PS
プレゼンテーションとコードの批判を歓迎します。
除算、実数、If式を追加したソースコード