未割り当て最終インタープリター（タグレス最終インタープリター- 約Per。 ）は、「インタープリター」パターンの実装に基づいた、従来の代数データ型（および一般化ADT）の代替アプローチです。 このテキストは、Scalaの「未割り当ての最終」アプローチを表しており、最近追加されたタイプの暗黙関数を備えたDottyがこのアプローチをさらに魅力的にする方法を示しています。 すべてのコード例は、 型付きタグレス最終通訳：講義ノート （セクション2）に示されているHaskellバージョンの直接配置です。
インタプリタパターンは最近Scalaコミュニティでますます注目を集めています。 ADT / GADTベースのソリューションの最大の欠点である拡張性に取り組むことに多くの努力が注がれています。 手始めに、 データ型アラカルトのアイデアの実装として、猫からのタイプ typeclass Inject
を見ることができます。 Freekライブラリは、型レベルの操作の装置を使用して、ジュエリーを使用して3つ以上の代数を組み合わせるためのツールを提供します。 Freer Monadsが提案するソリューション、Extensible Effectsは拡張性にも重点を置いており、 eff 、 emm 、 paperdollなどの小さなScalaライブラリのセットに触発されています。 ある意味では、割り当てられていない有限インタープリターは、より伝統的なADT / GADTの代わりに、クラスタイプを直接使用して、反対側から適切です。 また、明らかな危険を伴うことなく、すぐに使用できる拡張性に優れています。
概要では、ADT / GADTとクラスタイプを使用したアプローチのプレゼンテーションと比較の詳細に進み、最初を最初として、2番目を最終として指定します。 簡潔にするために、このテキストは主に有限の通訳者に捧げられています。
はじめに
電卓で使用されるものと同様の単純な数式を使用します。 私たちのタスクは、そのような式を計算するだけでなく、それらをシリアル化、逆シリアル化、および単純化することでもあります。 怠zyなエンジニアの観点からは、（組み込み）ドメイン固有言語（ドメイン固有言語）を使用してサブジェクトエリアを想像することは完全に合理的です-さらに、サブジェクトエリアの誤った表現を追跡する必要がなくなります-基本的なプログラミング言語面倒を見てくれます。 私たちのサブジェクトエリアは、整数リテラル、加算、反対符号の取得のみで構成されます。 あなたの頭の中に生じたエンコーディングは次のようになります。
sealed trait IExp final case class Lit(i: Int) extends IExp final case class Neg(e: IExp) extends IExp final case class Add(r: IExp, l: IExp) extends IExp
たとえば、数式8 - (1 + 2)
、 IExp
型の値としてエンコードできます。
val fe: IExp = Add(Lit(8), Neg(Add(Lit(1), Lit(2))))
これまでのところ、すべてがシンプルに見えますよね？ fe
を整数として解釈すると、 IExp => Int
型の再帰関数が使用され、シリアル化は関数IExp => Json
、逆シリアル化はJson => Option[IExp]
で行われ、変換は関数IExp => IExp
ます。
抽象的には、 IExp
データIExp
はサブジェクト領域の初期エンコードを指します。 現時点では、それを忘れることができます。代わりに最終エンコードを使用するためです。
trait Exp[T] { def lit(i: Int): T def neg(t: T): T def add(l: T, r: T): T }
Exp
を使用して8 - (1 + 2)
を表すにはどうすればよいですか？ どういうわけか：
def tf0[T](implicit e: Exp[T]): T = e.add(e.lit(8), e.neg(e.add(e.lit(1), e.lit(2))))
Haskellでは（適切な言語拡張を使用）、 tf0
は多態的な値になります。 Scalaでは、タイプT
パラメーターと制約（constraint- およそPer。 ） implicit Exp[T]
持つ関数を使用します。 e.
を削除することにより、構文を（たとえば）簡素化できますe.
ヘルパー関数の使用：
object ExpSyntax { def lit[T](i: Int) (implicit e: Exp[T]): T = e.lit(i) def neg[T](t: T) (implicit e: Exp[T]): T = e.neg(t) def add[T](l: T, r: T)(implicit e: Exp[T]): T = e.add(l, r) } import ExpSyntax._ // def tf1[T: Exp]: T = add(lit(8), neg(add(lit(1), lit(2))))
この時点で、 「このtf1
インタープリターをどのように作成すればよいでしょうか？」 。 答えは簡単です： Exp
の実装を定義する！
implicit val evalExp: Exp[Int] = new Exp[Int] { def lit(i: Int): Int = i def neg(t: Int): Int = -t def add(l: Int, r: Int): Int = l + r }
implicit val printExp: Exp[String] = new Exp[String] { def lit(i: Int): String = i.toString def neg(t: String): String = s"(-$t)" def add(l: String, r: String): String = s"($l + $r)" }
解釈は型定義によって行われます。 tf1
をInt
として見てみましょう。
scala> tf1[Int] res0: Int = 5
String
としてのtf1
はどうですか？
scala> tf1[String] res1: String = (8 + (-(1 + 2)))
拡張性
製品演算で数式を補完することにした場合はどうなりますか？ 最初の （ADTに基づく） IExp
エンコーディングでは、2つの面倒な選択肢があります。これまでに作成したすべてのインタープリターでコンパートメントのIExp
データ型IExp
更新するか、 IExp
値を抽象型合計（coproducts- 約trans。 ） Data Typeàla Carteのスタイル。 そして、この点で、 最終的な未割り当てアプローチが実際に現れます。 記述されたコードを変更（または再コンパイル）することなく、自然な方法で拡張できます。 製品の操作のために、完全に独立した新しい型クラスを導入します。
trait Mult[T] { def mul(l: T, r: T): T } object MultSyntax { def mul[T](l: T, r: T)(implicit e: Mult[T]): T = e.mul(l, r) } import MultSyntax._
数値の乗算を使用する式には、追加の制限Mult
（追加の暗黙的（暗黙- 約Per。 ）引数Mult[T]
、それだけです）が必要です。 これは、 tfm2 = 7 * (8 - (1 + 2))
tfm1 = 7 - 1 * 2
およびtfm2 = 7 * (8 - (1 + 2))
を定義する方法です。
def tfm1[T: Exp : Mult] = add(lit(7), neg(mul(lit(1), lit(2)))) def tfm2[T: Exp : Mult] = mul(lit(7), tf1)
どこにでも追加することに満足していない場合: Exp : Mult
、先を見据えて、記事の最後に表示されると言います：Dottyでは、これは暗黙的な関数型（（implicit-function-type-近似トランス。 ）
これらの新しい式を解釈するには、 Int
およびString
Mult
実装を提供する必要があります。
implicit val evalMult: Mult[Int] = new Mult[Int] { def mul(l: Int, r: Int): Int = l * r } implicit val printMult: Mult[String] = new Mult[String] { def mul(l: String, r: String): String = s"$l * $r" }
追加のバインディングなしで、 Exp
およびMult
実装は解釈中に自動的に結合されます。
scala> tfm1[String] res2: String = (7 + (-1 * 2)) scala> tfm1[Int] res3: Int = 5 scala> tfm2[String] res4: String = 7 * (8 + (-(1 + 2))) scala> tfm2[Int] res4: Int = 35
逆シリアル化
より複雑な逆シリアル化のタスクに移りましょう。 ターゲット形式は、次のように定義されたJsonのようなツリー構造です。
sealed trait Tree final case class Leaf(s: String) extends Tree final case class Node(s: String, ts: List[Tree]) extends Tree
式をこのJsonのような形式に変換することは、 String
シリアライズすることより難しくありません。 Exp
およびMult
実装が定義されている場所に応じて、それらをグループ化できます。
implicit val toTree: Exp[Tree] with Mult[Tree] = new Exp[Tree] with Mult[Tree] { def lit(i: Int): Tree = Node("Lit", List(Leaf(i.toString))) def neg(t: Tree): Tree = Node("Neg", List(t)) def add(l: Tree, r: Tree): Tree = Node("Add", List(l , r)) def mul(l: Tree, r: Tree): Tree = Node("Mult", List(l , r)) }
scala> val tf1Tree = tf1[Tree] tf1Tree: Tree = Node(Add,List(Node(Lit,List(Leaf(8))), Node(Neg,List(Node(Add,List(Node(Lit,List(Leaf(1))), Node(Lit,List(Leaf(2)))))))))
シリアル化をfromTree
するには、 fromTree
関数を記述して、JsonのようなTree
を最終的なエンコードに変換する必要があります。 これを考えると、 有限コード値は[T] => Exp[T] => T
型の関数です（Dottyでは、これは型のラムダ関数の構文です({type L[T] = Exp[T] => T})#L
）、最初の推測はfromTree
をdef fromTree[T](t: Tree)(implicit e: Exp[T]): Either[ErrMsg, T]
として定義することですdef fromTree[T](t: Tree)(implicit e: Exp[T]): Either[ErrMsg, T]
type ErrMsg = String def readInt(s: String): Either[ErrMsg, Int] = { import scala.util.{Try, Success, Failure} Try(s.toInt) match { case Success(i) => Right(i) case Failure(f) => Left(f.toString) } } def fromTree[T](t: Tree)(implicit e: Exp[T]): Either[ErrMsg, T] = t match { case Node("Lit", List(Leaf(n))) => readInt(n).right.map(e.lit) case Node("Neg", List(t)) => fromTree(t).right.map(e.neg) case Node("Add", List(l , r)) => for(lt <- fromTree(l).right; rt <- fromTree(r).right) yield e.add(lt, rt) case _ => Left(s" $t") }
これは機能しますが、 fromTree
呼び出すときにT
とExp[T]
完全に定義する必要があるため、ポリモーフィズムは失われ、結果のfromTree
は単一の解釈を持つ場合があります。 次のアプローチを使用して結果をラップすることにより、この問題を回避します。
trait Wrapped { def value[T](implicit e: Exp[T]): T }
シノプシスは、新しい署名を使用してfromTree
を書き換えるfromTree
をさらに提案します： def fromTree(t: Tree): Either[ErrMsg, Wrapped]
が、 Exp[Wrapped]
実装を定義することで同じ結果が得られるという事実を見落としていましたfromTree
元のコードを使用します。
implicit val wrappingExp: Exp[Wrapped] = new Exp[Wrapped] { def lit(i: Int) = new Wrapped { def value[T](implicit e: Exp[T]): T = e.lit(i) } def neg(t: Wrapped) = new Wrapped { def value[T](implicit e: Exp[T]): T = e.neg(t.value) } def add(l: Wrapped, r: Wrapped) = new Wrapped { def value[T](implicit e: Exp[T]): T = e.add(l.value, r.value) } }
これは、ファーストクラスのポリモーフィズムを得るのに十分です
scala> fromTree[Wrapped](tf1Tree) match { | case Left(err) => | println(err) | | case Right(t) => | println(t.value[Int]) | println(t.value[String]) | println |} 5 (8 + (-(1 + 2)))
しかし、私たちはタスクの半分しか管理していませんでした。デシリアライザーはまだ拡張性に欠けています。 事後事後乗算を追加できるようにするには、 fromTree
オープン再帰スタイルで書き換える必要があります。 これは、非常に単純なアイデアのもう1つの恐ろしい名前です。オプションのrecur
パラメーターを使用して、 fromTree
からの再帰呼び出しをすべて書き換えることができます。
// , `recur` `fromTree _` ! def fromTreeExt[T] (recur: => (Tree => Either[ErrMsg, T])) (implicit e: Exp[T]) : Tree => Either[ErrMsg, T] = { val e = implicitly[Exp[T]] tree => tree match { case Node("Lit", List(Leaf(n))) => readInt(n).right.map(e.lit) case Node("Neg", List(t)) => recur(t).right.map(e.neg) case Node("Add", List(l , r)) => for(lt <- recur(l).right; rt <- recur(r).right) yield e.add(lt, rt) case t => Left(s" $t") } }
次に、固定小数点演算子（ "fix per。"）を使用して再帰がまとめられます。
def fix[A](f: (=> A) => A): A = f(fix(f))
def fromTree2[T: Exp](t: Tree): Either[ErrMsg, T] = fix(fromTreeExt[T] _)(t)
したがって、製品オペレーターのデシリアライザーを個別に決定し、再び「ノードを締める」ことが可能になります。
def fromTreeExt2[T] (recur: => (Tree => Either[ErrMsg, T])) (implicit e: Exp[T], m: Mult[T]) : Tree => Either[ErrMsg, T] = { case Node("Mult", List(l , r)) => for(lt <- recur(l).right; rt <- recur(r).right) yield m.mul(lt, rt) case t => fromTreeExt(recur).apply(t) }
def fromTree3[T: Exp : Mult](t: Tree): Either[ErrMsg, T] = fix(fromTreeExt2[T] _)(t)
これで、たとえば次を使用して、 e
シリアル化と逆シリアル化をテストできます。
assert(fromTreeN[String](e[Tree]) == Right(e[String]))
Scalaでは、この実装はスタックに対して安全ではないことに注意してください。 大きなデータ構造に対してこの再帰トリックを使用するには、トランポリンを追加する必要があります。
変換
数式をさまざまな他の表現に変換する方法を見ました。 解釈; 別のビューから数学式を作成する方法：逆シリアル化。 しかし、数式を別の数式に変換するのはどうですか？
8 - (1 + 2)
が8 + ((-1) + (-2))
8 - (1 + 2)
なるように、単項マイナスをリテラルの一番下まで下げる変換を考えてください。 タスクは、 初期 （ADTベース）エンコーディングでは単純にIExp => IExp
ます。単純な関数IExp => IExp
機能します
def pushNeg(e: IExp): IExp = e match { case Lit(_) => e case Neg(Lit(_)) => e case Neg(Neg(n)) => n case Neg(Add(l, r)) => Add(pushNeg(Neg(l)), pushNeg(Neg(r))) case Add(l, r) => Add(pushNeg(l), pushNeg(r)) }
これは最終的なエンコードでは不可能のようです。 パターンマッチングは、特定のコンテキストでの変換に非常に便利ですExp
実装内で同様の便利さをどのように実現しますか 秘Theは、以前に行ったようにExp[T]
を処理する代わりに、適切なコンテキストでExp[Ctx => T]
を操作することです。 この場合、コンテキストは非常に簡単です。現在のノードの符号を変更するかどうかを知る必要があるだけです。
sealed trait NCtx final case object PosCtx extends NCtx final case object NegCtx extends NCtx
変換はExp[NCtx => T]
として表されExp[NCtx => T]
。
implicit def negDownExp[T](implicit e: Exp[T]): Exp[NCtx => T] = new Exp[NCtx => T] { def lit(i: Int): NCtx => T = { case PosCtx => e.lit(i) case NegCtx => e.neg(e.lit(i)) } def neg(x: NCtx => T): NCtx => T = { case PosCtx => x(NegCtx) case NegCtx => x(PosCtx) } def add(l: NCtx => T, r: NCtx => T): NCtx => T = c => e.add(l(c), r(c)) }
変換を適用するには、最初に式を関数NCtx => T
に変換してから、初期コンテキストでそれを呼び出す必要があります。
scala> tf1[NCtx => String].apply(PosCtx) (8 + ((-1) + (-2)))
初期コンテキストは、機能でレンダリングすることもできます。
scala> def pushNeg[T](e: NCtx => T): T = e(PosCtx) pushNeg: [T](e: NCtx => T)T scala> pushNeg(tf1[NCtx => String]) (8 + ((-1) + (-2)))
残念ながら、この場合のscalac
型推論メカニズムでは、内部型パラメーターを明示的に定義する必要があります。これは、いくつかの変換を構成するときに非常に見苦しい場合があります： pushNeg(pushNeg(pushNeg(tf1[NCtx => NCtx => NCtx => String])))
。 Dottyの型推論メカニズムの改善により、単純にpushNeg(pushNeg(pushNeg(tf1))): String
を記述できるようになりました。これは、Haskellでの記述方法と同様です。 Dottyの型推論メカニズムの概要については、「 Dottyと型：これまでのストーリー 」を参照してください。
この変換は、追加の実装Mult[NCtx => T]
定義することにより、製品操作に自然に拡張できます。
implicit def negDownMult[T](implicit e: Mult[T]): Mult[NCtx => T] = new Mult[NCtx => T] { def mul(l: NCtx => T, r: NCtx => T): NCtx => T = { case PosCtx => e.mul(l(PosCtx), r(PosCtx)) case NegCtx => e.mul(l(PosCtx), r(NegCtx)) } }
scala> pushNeg(tfm1[NCtx => String]) (7 + 1 * (-2)) scala> pushNeg(tfm2[NCtx => String]) 7 * (8 + ((-1) + (-2)))
この講義では、同様のコンテキスト紹介の手法を使用した変換の別の例を続けます。 これまで見てきた変換は非常に独創的で、疑問に思うかもしれません。 最終エンコーディングを使用して記述できるものはすべて初期エンコーディングでも表現でき、その逆も同様です。 これらの2つの表現は実際には同等であり、全単射の存在によって実証できます。
// ADT implicit def initialize: Exp[IExp] = new Exp[IExp] { def lit(i: Int): IExp = Lit(i) def neg(t: IExp): IExp = Neg(t) def add(l: IExp, r: IExp): IExp = Add(l, r) } // ADT def finalize[T](i: IExp)(implicit e: Exp[T]): T = i match { case Lit(l) => e.lit(l) case Neg(n) => e.neg(finalize[T](n)) case Add(l, r) => e.add(finalize[T](l), finalize[T](r)) }
暗黙的な関数型を使用して型クラスの制約を組み合わせる
暗黙関数は、Dottyコンパイラーへの最近の追加です。 考えは、暗黙的な引数を持つ関数のサポートにより現在利用可能な構文を拡張することです。 ご存知のように、Scalaの関数は次のように定義されています。
trait Function1[A, B] { def apply(a: A): B }
コンパイラは、タイプA => B
をFunction1[A, B]
変換する構文シュガーを実装しFunction1[A, B]
ユーザーが関数値を簡潔に定義できるようにします。 暗黙的な関数は似ています： implicit A => B
は、 ImplicitFunction1[A, B]
で展開された正しい型になります。
trait ImplicitFunction1[A, B] { def apply(implicit a: A): B }
暗黙的な関数の型を返す関数の定義は、スコープ内に暗黙的なパラメーターを自動的に配置する追加の拡張で追加の利点を活用します。
def f: implicit Ctx => Unit = ???
展開先：
def f: implicit Ctx => Unit = { implicit $e1: Ctx => ???: Unit }
この単純な例では、構文糖はあまり役に立たないかもしれませんが、このタイプの同義語では、すでにより興味深いものになっています。
type Contextualized[T] = implicit Ctx => T def f: Contextualized[Unit] = ???
複数の暗黙的なパラメーターが含まれる場合、暗黙的な関数のタイプにより、以前は不可能だったことができます。つまり、暗黙的なパラメーターから抽象化します。
type Constrained[T] = implicit (TC1[T], TC2[T], TC3[T]) => T def f: Constrained[Int] = ???
展開先：
def f: Constrained[Int] = { ($e1: TC1[Int], $e2: TC2[Int], $e3: TC3[Int]) => implicit $e4: TC1[Int] = $e1 implicit $e5: TC1[Int] = $e2 implicit $e6: TC1[Int] = $e3 ???: Int }
数式の最終的なエンコードに戻ると、Dottyの暗黙的な関数型により、最小限の構文オーバーヘッドでエンコードを拡張できます。
type Ring[T] = implicit (Exp[T], Mult[T]) => T def tfm1[T]: Ring[T] = add(lit(7), neg(mul(lit(1), lit(2)))) def tfm2[T]: Ring[T] = mul(lit(7), tf1)
これで、未割り当てのエンドインタープリターへの復帰は完了です（この記事のすべての（Scala 2.11）コードスニペットをご覧ください！）
Unallocated Finite Interpreterについて詳しく知りたい場合は、単純に型指定されたラムダ計算をエンコードするための概要のセクション3および4を引き続き検討することを強くお勧めします。