Scalaz(35)- Free :运算-Trampoline,say NO to StackOverflowError

   在前面几次讨论中我们介绍了Free是个产生Monad的最基本结构。它的原理是把一段程序(AST)一连串的运算指令(ADT)转化成数据结构存放在内存里,这个过程是个独立的功能描述过程。然后另一个独立运算过程的Interpreter会遍历(traverse)AST结构,读取结构里的运算指令,实际运行指令。这里的重点是把一连串运算结构化(reify)延迟运行,具体实现方式是把Monad的连续运算方法flatMap转化成一串Suspend结构(case class),把运算过程转化成创建(construct)Suspend过程。flatMap的表现形式是这样的:flatMap(a => flatMap(b => flatMap(c => ....))),这是是明显的递归算法,很容易产生堆栈溢出异常(StackOverflow Exception),无法保证程序的安全运行,如果不能有效解决则FP编程不可行。Free正是解决这个问题的有效方法,因为它把Monad的递归算法flatMap转化成了一个创建数据结构实例的过程。每创建一个Suspend,立即完成一个运算。我们先用个例子来证明Monad flatMap的递归算法问题:

 1 ef zipIndex[A](xa: List[A]): List[(Int,A)] =
 2   xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(
 3     (acc,a) => for {
 4       xn <- acc
 5       s <- get[Int]
 6       _ <- put[Int](s+1)
 7     } yield ((s,a) :: xn)
 8   ).eval(1).reverse                               //> zipIndex: [A](xa: List[A])List[(Int, A)]
 9 
10 zipIndex(1 |-> 10)                                //> res6: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))
11 zipIndex(1 |-> 10000)                             //> java.lang.StackOverflowError

在这个例子里我们使用了State Monad。我们知道for-comprehension就是flatMap链条,是一种递归算法,所以当zipIndex针对大List时就产生了StackOverflowError。

我们提到过用Trampoline可以heap换stack,以遍历数据结构代替递归运算来实现运行安全。那么什么是Trampoline呢?

1 sealed trait Trampoline[+A] 
2 case class Done[A](a: A) extends Trampoline[A]
3 case class More[A](k: () => Trampoline[A]) extends Trampoline[A]

Trampoline就是一种数据结构。它有两种状态:Done(a: A)代表结构内存放了一个A值,More(k: ()=>Trampoline[A])代表结构内存放的是一个Function0函数,就是一个运算Trampoline[A]。

我们先试个递归算法例子:

 1 def isEven(xa: List[Int]): Boolean =
 2   xa match {
 3     case Nil => true
 4     case h :: t => isOdd(t)
 5   }                                               //> isEven: (xa: List[Int])Boolean
 6 def isOdd(xa: List[Int]): Boolean =
 7   xa match {
 8     case Nil => false
 9     case h :: t => isEven(t)
10   }                                               //> isOdd: (xa: List[Int])Boolean
11 
12 isOdd(0 |-> 100)                                  //> res0: Boolean = true
13 isEven(0 |-> 10000)                               //> java.lang.StackOverflowError

可以看到isEven和isOdd这两个函数相互递归调用,最终用大点的List就产生了StackOverflowError。

现在重新调整一下函数isEven和isOdd的返回结构类型:从Boolean换成Trampoline,意思是从返回一个结果值变成返回一个数据结构:

 1 def even(xa: List[Int]): Trampoline[Boolean] =
 2   xa match {
 3     case Nil => Done(true)
 4     case h :: t => More(() => odd(t))
 5   }                                               //> even: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]
 6 def odd(xa:  List[Int]): Trampoline[Boolean] =
 7   xa match {
 8     case Nil => Done(false)
 9     case h :: t => More(() => even(t))
10   }                                               //> odd: (xa: List[Int])Exercises.trampoline.Trampoline[Boolean]
11   
12 even(1 |-> 123001)                                //> res0: Exercises.trampoline.Trampoline[Boolean] = More(<function0>)

现在我们获得了一个在heap上存放了123001个元素的数据结构More(<function0>)。这是一个在内存heap上存放的过程,并没有任何实质运算。 现在我们需要一个方法来遍历这个返回的结构,逐个运行结构中的function0:

1 sealed trait Trampoline[+A] {
2   final def runT: A =
3     this match {
4       case Done(a) => a
5       case More(k) => k().runT
6     }
7 }
8 
9 even(1 |-> 123001).runT                           //> res0: Boolean = false

由于这个runT是个尾递归(Tail Call Elimination TCE)算法,所以没有出现StackOverflowError。

实际上scalaz也提供了Trampoline类型:scalaz/Free.scala

  /** A computation that can be stepped through, suspended, and paused */
  type Trampoline[A] = Free[Function0, A]
...
object Trampoline extends TrampolineInstances {

  def done[A](a: A): Trampoline[A] =
    Free.Return[Function0,A](a)

  def delay[A](a: => A): Trampoline[A] =
    suspend(done(a))

  def suspend[A](a: => Trampoline[A]): Trampoline[A] =
    Free.Suspend[Function0, A](() => a)
}

Trampoline就是Free[S,A]的一种特例。S == Function0,或者说Trampoline就是Free针对Function0生成的Monad,因为我们可以用Free.Return和Free.Suspend来实现Done和More。我们可以把scalaz的Trampoline用在even,odd函数里:

 1 import scalaz.Free.Trampoline
 2 def even(xa: List[Int]): Trampoline[Boolean] =
 3   xa match {
 4     case Nil => Trampoline.done(true)
 5     case h :: t => Trampoline.suspend(odd(t))
 6   }                                               //> even: (xa: List[Int])scalaz.Free.Trampoline[Boolean]
 7 def odd(xa:  List[Int]): Trampoline[Boolean] =
 8   xa match {
 9     case Nil => Trampoline.done(false)
10     case h :: t => Trampoline.suspend(even(t))
11   }                                               //> odd: (xa: List[Int])scalaz.Free.Trampoline[Boolean]
12   
13 even(1 |-> 123001).run                            //> res0: Boolean = false

语法同我们自定义的Trampoline差不多。 那么我们能不能把Trampoline用在上面的哪个zipIndex函数里来解决StackOverflowError问题呢?zipIndex里造成问题的Monad是个State Monad,我们可以用State.lift把State[S,A升格成StateT[Trampoline,S,A]。先看看这个lift函数:scalaz/StateT.scala 

 def lift[M[_]: Applicative]: IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] = new IndexedStateT[({type λ[α]=M[F[α]]})#λ, S1, S2, A] {
    def apply(initial: S1): M[F[(S2, A)]] = Applicative[M].point(self(initial))
  }

这个函数的功能等于是:State.lift[Trampoline] >>> StateT[Tarmpoline,S,A]。先看另一个简单例子:

1 def incr: State[Int, Int] =  State {s => (s+1, s)}//> incr: => scalaz.State[Int,Int]
2 incr.replicateM(10000).eval(0) take 10            //> java.lang.StackOverflowError
3 
4 import scalaz.Free.Trampoline
5 incr.lift[Trampoline].replicateM(100000).eval(0).run.take(10)
6                                                   //> res0: List[Int] = List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

上面这个例子也使用了State Monad:函数incr返回的是State,这时用replicateM(10000).eval(0)对重复对10000个State进行运算时产生了StackOverflowError。我们跟着用lift把incr返回类型变成StateT[Trampoline,S,A],这时replicateM(10000).eval(0)的作用就是进行结构转化了(State.apply:Trampoline[(S,A)]),再用Trampoline.run作为Interpreter遍历结构进行运算。用lift升格Trampoline后解决了StackOverflowError。

我们试着调整一下zipIndex函数:

 1 def safeZipIndex[A](xa: List[A]): List[(Int,A)] =
 2   (xa.foldLeft(State.state[Int,List[(Int,A)]](List()))(
 3     (acc,a) => for {
 4       xn <- acc
 5       s <- get[Int]
 6       _ <- put(s + 1)
 7     } yield (s,a) :: xn
 8   ).lift[Trampoline]).eval(1).run.reverse         //> safeZipIndex: [A](xa: List[A])List[(Int, A)]
 9   
10   safeZipIndex(1 |-> 1000).take(10)               //> res2: List[(Int, Int)] = List((1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (10,10))

表面上来看结果好像是正确的。试试大一点的List:

1  safeZipIndex(1 |-> 10000).take(10)   //> java.lang.StackOverflowError
2                                       //| at scalaz.IndexedStateT$$anonfun$flatMap$1.apply(StateT.scala:62)
3                                       //| at scalaz.IndexedStateT$$anon$10.apply(StateT.scala:95)
4                                       //| at scalaz.IndexedStateT$$anonfun$flatMap$1.apply(StateT.scala:62)
5 ...
6  

还是StackOverflowError,看错误提示是State.flatMap造成的。看来迟点还是按照incr的原理把foldLeft运算阶段结果拆分开来分析才行。

以上我们证明了Trampoline可以把连续运算转化成创建数据结构,以heap内存换stack,能保证递归算法运行的安全。因为Trampoline是Free的一个特例,所以Free的Interpreter也就可以保证递归算法安全运行。现在可以得出这样的结论:FP就是Monadic Programming,就是用Monad来编程,我们应该尽量用Free来生成Monad,用Free进行编程以保证FP程序的可靠性。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java初学

spring框架(3)— spring集合类的注入

36013
来自专栏技术小黑屋

有点意思的Kotlin的默认参数与JVMOverloads

在Java中,当我们定义一个类的时候,总会出现一些变量是必须要填写的,而另一些是可选的。比如像下面这样,我们定一个Person类,其中name是必须填写的,而性...

1785
来自专栏函数式编程语言及工具

泛函编程(29)-泛函实用结构:Trampoline-不再怕StackOverflow

   泛函编程方式其中一个特点就是普遍地使用递归算法,而且有些地方还无法避免使用递归算法。比如说flatMap就是一种推进式的递归算法,没了它就无法使用for-...

2419
来自专栏一个会写诗的程序员的博客

《Groovy极简教程》第12章 Groovy的JSON包《Groovy极简教程》JsonOutputJsonSlurper

Groovy自带了转换JSON的功能,相关类都在groovy.json包下。本文参考自Groovy文档 Parsing and producing JSON。

573
来自专栏陈树义

注解的那些事儿(三)| 注解的使用

在上面的 SweetDemo 中会发现我们在使用 @Sweet 注解的时候,手动给 sweetLevel 属性赋值。如果没有赋值,那么会报错。

1012
来自专栏吴伟祥

单元测试的利器 Jmockdata 原

Jmockdata是一款实现模拟JAVA类型或对象的实例化并随机初始化对象的数据的工具框架。

1774
来自专栏函数式编程语言及工具

泛函编程(10)-异常处理-Either

     上节我们介绍了新的数据类型Option:一个专门对付异常情况出现时可以有一致反应所使用的数据类型。Option可以使编程人员不必理会出现异常后应该如何...

1925
来自专栏Ryan Miao

jackson简单使用,对象转json,json转对象,json转list

添加jackson依赖: // https://mvnrepository.com/artifact/com.fasterxml.jackson.core/ja...

35511
来自专栏小樱的经验随笔

Codeforce 712A Memory and Crow

A. Memory and Crow time limit per test:2 seconds memory limit per test:256 megab...

3066
来自专栏猿人谷

编程小技巧

1.判断一个自然数是否是某个数的平方?(其实就是判断这个数一定是奇数相加的) 由于 (n+1)^2 =n^2 + 2n + 1, = ... = 1 +...

21110

扫码关注云+社区