免费monad与AST的关系 [英] Relation of free monad and AST

问题描述

我指的是下面列出的Ken Scambler的源代码，另请参见

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

如果遵循这些幻灯片，则任何脚本(请参见源代码中的5..)在免费monad中被转换"为Suspend(Op(Suspend(Op(......(Result(Op))..))之类的东西.

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.

不幸的是，低于5的脚本只是线性的命令序列.

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:

1. 线性运算的顺序(当然也是一棵树)由Suspend(Op(Suspend(Op(......(Result(Op))..))表示，因此是AST的表示.这个假设正确吗?
2. 在免费的monad中如何表示 real AST?我猜想，包括控制结构在内会发生这种情况吗? (例如，取决于条件的左右树枝).有人可以举例说明真正的AST发挥作用的例子吗?也许，可以举例说明在给定示例中如何实现"if".
3. 将控制结构包含到脚本中的一般方法是什么(如源代码中第5点所述?)

1. 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?
2. 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.
3. What is the general approach to include control structures into scripts (as given under 5 in source code?)

P.S .:请尝试坚持使用Scala/ScalaZ，因为Haskell还不是我的专业领域.

P.S.: Please try to stick to Scala / ScalaZ, as Haskell is not (yet) my field of expertise.

推荐答案

在Scalaz中，Free monad是两种情况(简化并忽略了GoSub优化):

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]

首先让我们看看Free.liftF的作用，例如

Let's first see what Free.liftF does, e.g. for

def get(key: String): Script[String] = liftF(Get(key, identity))

做get("key")时我们会得到

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:

1. 线性运算的顺序(当然也是一棵树)由Suspend(Op(Suspend(Op(......(Result(Op))..)))表示，因此表示AST?这个假设对吗?

从本质上讲是这样，使用由函子产生的免费monad在DSL中编写的程序表示步骤"链，其中每个步骤要么是包含您的函子案例之一的Suspend，要么是代表结尾的Return的链条.

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.

作为一个具体示例，script看起来像这样:

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

如您所见，我们实际上只是通过继续计算来填充"函子的孔，并以Return终止.在示例DSL中，由于KVS函子的每种情况都只有一个孔"要填充，因此没有分支，因此我们将始终具有线性链.

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.

1. 在免费的monad中如何表示真实的AST?我猜想，包括控制结构在内会发生这种情况吗? (例如，取决于条件的左右树枝).有人可以举例说明真正的AST发挥作用的例子吗?也许，可以举例说明在给定示例中如何实现"if".

让我们用分支结构扩展DSL:

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

因此，现在您有了一个真实的" AST，我将您的真实的"解释为具有分支节点"，而不是像现在这样的线性链形式.输出符合预期:

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)

1. 将控制结构包含到脚本中的一般方法是什么(如源代码中第5点所述?)

首先，请记住，例如，如果您有内在的理解，就可以使用该标准:

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

第二，请记住，由于Script[A]只是Free[KVS,A]的事实，您可以使用一个monad，因此，例如Scalaz for monad也将为您工作:

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

看看Monad.scala和MonadSyntax.scala，还有whileM和iterateWhile.

这篇关于免费monad与AST的关系的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！