free monad 和 AST 的关系 [英] Relation of free monad and AST
问题描述
我指的是下面列出的 Ken Scambler 的源代码，另见 GitHub 源代码.
包 kenbot.free进口scalaz._导入 Scalaz._免费进口._导入 scala.collection.mutable//此示例基于 Runar Bjarnason 的死简单依赖注入"演讲中的示例.//http://www.youtube.com/watch?v=ZasXwtTRkio//0. 幻想API//def put(key: String, value: String): 单位//def get(key: String): String//def delete(key: String): 单位//1. ADT密封特性KVS[+下一个]case class Put[Next](key: String, value: String, next: Next) extends KVS[Next]//<---- def put(key: String, value: String): Unitcase class Get[Next](key: String, onResult: String => Next) extends KVS[Next]//<---- def get(key: String): Stringcase class Delete[Next](key: String, next: Next) extends KVS[Next]//<---- def delete(key: String): Unit对象 KVS {输入脚本[A] = 免费[KVS, A]//2. 函子定义隐式 val 函子:Functor[KVS] = new Functor[KVS] {def map[A,B](kvs: KVS[A])(f: A => B): KVS[B] = kvs match {case Put(key, value, next) =>Put(key, value, f(next))case Get(key, onResult) =>Get(key, onResult andThen f)case Delete(key, next) =>删除(键，f(下一个))}}//3. 提升函数def put(key: String, value: String): Script[Unit] = liftF( Put(key, value, ()) )def get(key: String): Script[String] = liftF(Get(key, identity))def delete(key: String): Script[Unit] = liftF(Delete(key, ()))//4. 复合函数def modify(key: String, f: String => String): Free[KVS, Unit] = for {v <- 获取(键)_ <- put(key, f(v))} 屈服 ()//5. 编写脚本val 脚本:免费[KVS，单位] = for {id <- get("swiss-bank-account-id")_ <- 修改(id，(_ + 1000000))_ <- put("百慕大机场", "逃生车")_ <- 删除(税务记录")} 屈服 ()//6. 解释器//构建一个不可变的结构def interpretPure(kvs: Script[Unit], table: Map[String, String] = Map.empty): Map[String, String] = kvs.resume.fold({case Get(key, onResult) =>解释纯(onResult(表(键))，表)case Put(key, value, next) =>interpretPure(next, table + (key -> value))case Delete(key, next) =>解释纯(下一个，表 - 键)}, _ =>桌子)//直接运行效果def interpretImpure(kvs: Script[Unit], table: mutable.Map[String, String]): Unit = kvs.go {case Get(key, onResult) =>onResult(表(键))case Put(key, value, next) =>table += (key -> value);下一个case Delete(key, next) =>表 -= 键；下一个}}如果遵循这些幻灯片，任何脚本(请参阅源代码中的 5.)在自由 monad 中被转换"为类似 Suspend(Op(Suspend(Op(......(Result(Op))..)) 的东西.
不幸的是，5 下的脚本只是一个线性的命令序列.
即使在网上搜索了几个小时后，我也找不到任何可以让我更深入地了解以下问题的示例:
- 线性操作的序列(当然也是树)用
Suspend(Op(Suspend(Op(......(Result(Op))..))因此是 AST 的一种表示?这个假设是否正确? - 真实 AST 在自由 monad 中是如何表示的?我假设，当包含控制结构时会发生这种情况吗?(例如左右树枝，视情况而定).有人可以举例说明真正的 AST 发挥作用的例子吗?也许，可以说明如何在给定的示例中实现if".
- 将控制结构包含到脚本中的一般方法是什么(如源代码中的第 5 项所示?)
P.S.:请尽量坚持使用 Scala/ScalaZ，因为 Haskell 还不是我的专业领域.
在 Scalaz 中，Free monad 作为两种情况(简化并忽略了 GoSub 优化):
密封抽象类 Free[S[_], A]case class Return[S[_], A](a: A) extends Free[S, A]case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]让我们先看看 Free.liftF 做了什么，例如对于
def get(key: String): Script[String] = liftF(Get(key, identity))当做get("key")时我们会得到
get("key")//获取的定义LiftF(Get("key",identity)//定义liftFSuspend(Get("key",identity).map(Return)//上面 Get 的映射定义Suspend(Get("key", identity and Then Return))//身份 andThen f == f暂停(获取(键"，返回))有了这个，让我们从您的问题开始:
<块引用>- 线性操作序列(当然也是一棵树)由 Suspend(Op(Suspend(Op(......(Result(Op))..)) 表示，因此是AST?这个假设正确吗?
本质上是的，使用由函子产生的自由 monad 用 DSL 编写的程序代表一连串步骤"，其中每个步骤是一个 Suspend ，其中包含一个函子案例或一个 Suspendcode>Return 代表链的末端.
作为一个具体的例子，script 看起来像这样:
Suspend(Get("swiss-bank-account-id",id =>暂停(获取(ID，v =>暂停(放置(ID，v + 1000000，_ =>暂停(放置(百慕大机场"，逃亡车"，_ =>暂停(删除(税务记录"，_ =>返回(()))))))))))))如您所见，我们本质上只是通过继续计算来填充"函子的空洞，并以 Return 结束.在示例 DSL 中，我们将始终有一个线性链，因为 KVS 函子的每种情况都只有一个洞"要填充，因此没有分支.
- 一个真正的 AST 在自由 monad 中是如何表示的?我假设，当包含控制结构时会发生这种情况吗?(例如左右树枝，视情况而定).有人可以举例说明真正的 AST 发挥作用的例子吗?也许，可以说明如何在给定的示例中实现if".
让我们用一个分支结构来扩展我们的 DSL:
case class Cond[Next](cond: Boolean, ifTrue: Free[KVS,Next], ifFalse: Free[KVS,Next]) extends KVS[Next]def cond[A](c: Boolean)(ifTrue: => Script[A])(ifFalse: => Script[A]): Script[A] =LiftF(Cond(c,ifTrue,ifFalse))更改解释器案例后，可以这样使用:
val script2: Script[Unit] = for {id <- get("swiss-bank-account-id")_ <- cond(id == "123") {Free.point[KVS,Unit](())} {为了 {_ <- 修改(id，(很多"+ _))_ <- put("百慕大机场", "逃生车")_ <- 删除(税务记录")} 屈服 ()}} 屈服 ()所以现在你有一个真实的"AST，我将你的真实"解释为有分支节点"，而不是迄今为止的线性链形式.输出符合预期:
println(interpretPure(脚本2，Map("swiss-bank-account-id" -> "42", "42" -> "money", "tax-records" -> "acme corp")))//Map(swiss-bank-account-id -> 42, 42 -> LOTS OF money, bermuda-airport -> getaway car)println(解释纯(脚本2，Map("swiss-bank-account-id" -> "123", "tax-records" -> "acme corp")))//Map(swiss-bank-account-id -> 123, tax-records -> acme corp)<块引用>
- 将控制结构包含到脚本中的一般方法是什么(如源代码中的第 5 项所示?)
首先，请记住，例如，您可以在 for-comprehensions 中使用标准 if:
val script3: Script[Unit] = for {id <- get("swiss-bank-account-id")_ <- if (id == "123") {Free.point[KVS,Unit](())} 别的 {为了 {_ <- 修改(id，(很多"+ _))_ <- put("百慕大机场", "逃生车")_ <- 删除(税务记录")} 屈服 ()}} 屈服 ()其次，请记住，由于 Script[A] 只是 Free[KVS,A]，您可以使用一个 monad，因此任何控制结构"" 定义在例如用于 monad 的 Scalaz 也适用于您:
val script4: Script[Unit] = modify("key",_+"!").untilM_ { get("key").map(_.length > 42) }println(interpretPure(script4, Map("key" -> "")))//Map(key -> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!！)看看Monad.scala 和MonadSyntax.scala，还有whileM 和iterateWhile.
I'm referring to the Ken Scambler's source code listed below, also see GitHub source .
package kenbot.free
import scalaz._
import Scalaz._
import Free._
import scala.collection.mutable
// This example is based off the one in Runar Bjarnason's "Dead Simple Dependency Injection" talk.
// http://www.youtube.com/watch?v=ZasXwtTRkio
// 0. Fantasy API
// def put(key: String, value: String): Unit
// def get(key: String): String
// def delete(key: String): Unit
// 1. ADT
sealed trait KVS[+Next]
case class Put[Next](key: String, value: String, next: Next) extends KVS[Next] // <---- def put(key: String, value: String): Unit
case class Get[Next](key: String, onResult: String => Next) extends KVS[Next] // <---- def get(key: String): String
case class Delete[Next](key: String, next: Next) extends KVS[Next] // <---- def delete(key: String): Unit
object KVS {
type Script[A] = Free[KVS, A]
// 2. Functor definition
implicit val functor: Functor[KVS] = new Functor[KVS] {
def map[A,B](kvs: KVS[A])(f: A => B): KVS[B] = kvs match {
case Put(key, value, next) => Put(key, value, f(next))
case Get(key, onResult) => Get(key, onResult andThen f)
case Delete(key, next) => Delete(key, f(next))
}
}
// 3. Lifting functions
def put(key: String, value: String): Script[Unit] = liftF( Put(key, value, ()) )
def get(key: String): Script[String] = liftF(Get(key, identity))
def delete(key: String): Script[Unit] = liftF(Delete(key, ()))
// 4. Composite functions
def modify(key: String, f: String => String): Free[KVS, Unit] = for {
v <- get(key)
_ <- put(key, f(v))
} yield ()
// 5. Write scripts
val script: Free[KVS, Unit] = for {
id <- get("swiss-bank-account-id")
_ <- modify(id, (_ + 1000000))
_ <- put("bermuda-airport", "getaway car")
_ <- delete("tax-records")
} yield ()
// 6. Interpreters
// Building an immutable structure
def interpretPure(kvs: Script[Unit], table: Map[String, String] = Map.empty): Map[String, String] = kvs.resume.fold({
case Get(key, onResult) => interpretPure(onResult(table(key)), table)
case Put(key, value, next) => interpretPure(next, table + (key -> value))
case Delete(key, next) => interpretPure(next, table - key)
}, _ => table)
// Directly running effects
def interpretImpure(kvs: Script[Unit], table: mutable.Map[String, String]): Unit = kvs.go {
case Get(key, onResult) => onResult(table(key))
case Put(key, value, next) => table += (key -> value); next
case Delete(key, next) => table -= key; next
}
}
If a follow these slides, any script (see 5. in source code) is "transformed" into something like Suspend(Op(Suspend(Op(......(Result(Op))..)) within the free monad.
Unfortunately, the script under 5 is just a linear sequence of commands.
Even after searching the web for several hours, I wasn't able to find any examples, that gave more insight on the following questions:
- The sequence of linear operations (which is also a tree of course) is represented by
Suspend(Op(Suspend(Op(......(Result(Op))..))and is thus a representation of the AST? Is this assumption right? - How is a real AST represented within the free monad? I assume, this happens, when control structures are included? (e.g. left and right tree branch, depending on condition) . Could someone please illustrate an example where real ASTs come into play? Maybe, an illustration of how an "if" could be implemented in the given example.
- What is the general approach to include control structures into scripts (as given under 5 in source code?)
P.S.: Please try to stick to Scala / ScalaZ, as Haskell is not (yet) my field of expertise.
In Scalaz, the Free monad as the two cases (simplified and ignoring the GoSub optimization):
sealed abstract class Free[S[_], A]
case class Return[S[_], A](a: A) extends Free[S, A]
case class Suspend[S[_], A](a: S[Free[S, A]]) extends Free[S, A]
Let's first see what Free.liftF does, e.g. for
def get(key: String): Script[String] = liftF(Get(key, identity))
when doing get("key") we will get
get("key")
// definition of get
liftF(Get("key",identity)
// definition of liftF
Suspend(Get("key",identity).map(Return)
// definition of map for Get above
Suspend(Get("key", identity andThen Return))
// identity andThen f == f
Suspend(Get("key", Return))
Having that, let's start with your questions:
- The sequence of linear operations (which is also a tree of course) is represented by Suspend(Op(Suspend(Op(......(Result(Op))..)) and is thus a representation of the AST? Is this assumption right?
Essentially yes, a program written in the DSL using the free monad arising from a functor represents a chain of "steps" where each step is either a Suspend containing one of your functor cases or a Return representing the end of the chain.
As an concrete example, script looks about like this:
Suspend(Get("swiss-bank-account-id",
id => Suspend(Get(id,
v => Suspend(Put(id, v+1000000,
_ => Suspend(Put("bermuda-airport","getaway car",
_ => Suspend(Delete("tax-records",
_ => Return(())
))))))))))
As you can see, we essentially just "fill" the holes of our functor with the continuation of the computation, terminating with a Return. In the sample DSL we will always have a linear chain, due to the fact that every case of the KVS functor only has one "hole" to fill, so no branching.
- How is a real AST represented within the free monad? I assume, this happens, when control structures are included? (e.g. left and right tree branch, depending on condition) . Could someone please illustrate an example where real ASTs come into play? Maybe, an illustration of how an "if" could be implemented in the given example.
Let's extend our DSL with a branching construct:
case class Cond[Next](cond: Boolean, ifTrue: Free[KVS,Next], ifFalse: Free[KVS,Next]) extends KVS[Next]
def cond[A](c: Boolean)(ifTrue: => Script[A])(ifFalse: => Script[A]): Script[A] =
liftF(Cond(c,ifTrue,ifFalse))
after changing the interpreter cases, it can be used like this:
val script2: Script[Unit] = for {
id <- get("swiss-bank-account-id")
_ <- cond(id == "123") {
Free.point[KVS,Unit](())
} {
for {
_ <- modify(id, ("LOTS OF " + _))
_ <- put("bermuda-airport", "getaway car")
_ <- delete("tax-records")
} yield ()
}
} yield ()
So now you have a "real" AST where I interpret your "real" as "has branching nodes" instead of the linear chain form as was the case up until now. Output is as expected:
println(interpretPure(
script2,
Map("swiss-bank-account-id" -> "42", "42" -> "money", "tax-records" -> "acme corp")))
// Map(swiss-bank-account-id -> 42, 42 -> LOTS OF money, bermuda-airport -> getaway car)
println(interpretPure(
script2,
Map("swiss-bank-account-id" -> "123", "tax-records" -> "acme corp")))
// Map(swiss-bank-account-id -> 123, tax-records -> acme corp)
- What is the general approach to include control structures into scripts (as given under 5 in source code?)
First of all, remember that you can for example use the standard if inside for-comprehensions:
val script3: Script[Unit] = for {
id <- get("swiss-bank-account-id")
_ <- if (id == "123") {
Free.point[KVS,Unit](())
} else {
for {
_ <- modify(id, ("LOTS OF " + _))
_ <- put("bermuda-airport", "getaway car")
_ <- delete("tax-records")
} yield ()
}
} yield ()
Secondly, remember that due to the fact that Script[A] is just Free[KVS,A] you have a monad at disposal, so any "control structure" defined in e.g. Scalaz for monads will work for you too:
val script4: Script[Unit] = modify("key",_+"!").untilM_ { get("key").map(_.length > 42) }
println(interpretPure(script4, Map("key" -> "")))
// Map(key -> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!)
Have a look at Monad.scala and MonadSyntax.scala, there's also whileM and iterateWhile.
这篇关于free monad 和 AST 的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
