Skip to content

Instantly share code, notes, and snippets.

@mbrcknl

mbrcknl/ABOUT.markdown

Last active August 29, 2015 14:06
Show Gist options
  • Save mbrcknl/4a8c06257564273cbdfc to your computer and use it in GitHub Desktop.
Save mbrcknl/4a8c06257564273cbdfc to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ABOUT.markdown

Learning about trampolining in Scala.

I began with Ken Scambler's YOW! Lambda Jam 2014 workshop on Free monads, but found that the simple formulation of Free derived in exercise 1 was susceptible to stack overflow when used for trampolining in exercise 2. This is just an investigation into what causes this stack overflow, and how scalaz's GoSub trick avoids it.

Bad.scala is the code from exercise 1 and 2 smashed into its minimal form. That is, Free and Function0 are fused into Trampoline, and unused functions are removed. BadEval.markdown is an informal step-by-step evaluation of the append function, showing its linear stack-size and quadratic time requiremnets.

Good.scala contains the parts of the scalaz Trampoline necessary to run the same example, with some things inlined. This is just to reduce the amount you need to look at to follow the step-by-step evaluation shown in GoodEval.markdown. Clearly, this works in constant stack and linear time.

Raw
Bad.scala
import scala.annotation.tailrec
object Bad {
import Trampoline.{Return, Suspend}
def append[A](xs: List[A], ys: List[A]): Trampoline[List[A]] = xs match {
case Nil => Return(ys)
case x::r => Suspend(() => append(r,ys) map (x::_))
}
def main(args: Array[String]) = {
println(append((1 to 29999).toList, List(30000)).run)
}
object Trampoline {
case class Return[A](a: A) extends Trampoline[A] {
override def map[B](f: A => B) = Return(f(a))
}
case class Suspend[A](suspension: () => Trampoline[A]) extends Trampoline[A] {
override def map[B](f: A => B) = Suspend(() => suspension() map f)
}
}
sealed abstract class Trampoline[A] {
def map[B](f: A => B): Trampoline[B]
@tailrec
private final def go(trampoline: Trampoline[A]): A = trampoline match {
case Suspend(suspension) => go(suspension())
case Return(a) => a
}
final def run: A = go(this)
}
}
Raw
BadEval.markdown

Initial call

go(append(List(1,2,3,4,5),List(6)))

Descend into argument

append(List(1,2,3,4,5),List(6))
go(...)

Pattern match (append)

Suspend(() => append(List(2,3,4,5),List(6)) map (1::_))
go(...)

Return result from append into go

go(Suspend(() => append(List(2,3,4,5),List(6)) map (1::_)))

Pattern match (go), descend into suspension

append(List(2,3,4,5),List(6)) map (1::_)
go(...)

Descend into ... map (1::_)

append(List(2,3,4,5),List(6))
... map (1::_)
go(...)

Pattern match (append)

Suspend(() => append(List(3,4,5),List(6)) map (2::_))
... map (1::_)
go(...)

Return result from append to ... map (1::_)

Suspend(() => append(List(3,4,5),List(6)) map (2::_)) map (1::_)
go(...)

Apply ... map (1::_), descend into suspension

append(List(3,4,5),List(6)) map (2::_)
Suspend(() => ... map (1::_))
go(...)

Descend into ... map (2::_)

append(List(3,4,5),List(5,6))
... map (2::_)
Suspend(() => ... map (1::_))
go(...)

Pattern match (append)

Suspend(() => append(List(4,5),List(6)) map (3::_))
... map (2::_)
Suspend(() => ... map (1::_))
go(...)

Return result from append to ... map (2::_)

Suspend(() => append(List(4,5),List(6)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
go(...)

Apply ... map (2::_), descend into suspension

append(List(4,5),List(6)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Descend into ... map (3::_)

append(List(4,5),List(6))
... map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Pattern match (append)

Suspend(() => append(List(5),List(6)) map (4::_))
... map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result from append to ... map (3::_)

Suspend(() => append(List(5),List(6)) map (4::_)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (3::_), descend into suspension

append(List(5),List(6)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Descend into ... map (4::_)

append(List(5),List(6))
... map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Pattern match (append)

Suspend(() => append(nil,List(6)) map (5::_))
... map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result from append to ... map (4::_)

Suspend(() => append(nil,List(6)) map (5::_)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (4::_), descend into suspension

append(nil,List(6)) map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Descend into ... map (4::_)

append(nil,List(6))
... map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Pattern match (append)

Return(List(6))
... map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result from append to ... map (5::_)

Return(List(6)) map (5::_)
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (5::_)

Return(List(5,6))
Suspend(() => ... map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Return(List(5,6)) map (4::_))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)) map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_))
go(...)

Return result

go(Suspend(() => Suspend(() => Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_)))

Pattern match (go), descend into suspension

Suspend(() => Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)) map (2::_)) map (1::_)
go(...)

Apply ... map (1::_), descend into suspension

Suspend(() => Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
go(...)

Apply ... map (2::_), descend into suspension

Suspend(() => Return(List(5,6)) map (4::_)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (3::_), descend into suspension

Return(List(5,6)) map (4::_)
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (4::_)

Return(List(4,5,6))
Suspend(() => ... map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Return(List(4,5,6)) map (3::_))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Return(List(4,5,6)) map (3::_)) map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Suspend(() => Return(List(4,5,6)) map (3::_)) map (2::_)) map (1::_))
go(...)

Return result

go(Suspend(() => Suspend(() => Suspend(() => Return(List(4,5,6)) map (3::_)) map (2::_)) map (1::_)))

Pattern match go, descend into suspension

Suspend(() => Suspend(() => Return(List(4,5,6)) map (3::_)) map (2::_)) map (1::_)
go(...)

Apply ... map (1::_), descend into suspension

Suspend(() => Return(List(4,5,6)) map (3::_)) map (2::_)
Suspend(() => ... map (1::_))
go(...)

Apply ... map (2::_), descend into suspension

Return(List(4,5,6)) map (3::_)
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Apply ... map (3::_)

Return(List(3,4,5,6))
Suspend(() => ... map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Return(List(3,4,5,6)) map (2::_))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Suspend(() => Return(List(3,4,5,6)) map (2::_)) map (1::_))
go(...)

Return result

go(Suspend(() => Suspend(() => Return(List(3,4,5,6)) map (2::_)) map (1::_)))

Pattern match (go), descend into suspension

Suspend(() => Return(List(3,4,5,6)) map (2::_)) map (1::_)
go(...)

Apply ... map (1::_), descend into suspension

Return(List(3,4,5,6)) map (2::_)
Suspend(() => ... map (1::_))
go(...)

Apply ... map (2::_)

Return(List(2,3,4,5,6))
Suspend(() => ... map (1::_))
go(...)

Return result

Suspend(() => Return(List(2,3,4,5,6)) map (1::_))
go(...)

Return result

go(Suspend(() => Return(List(2,3,4,5,6)) map (1::_)))

Pattern match (go), descend into suspension

Return(List(2,3,4,5,6)) map (1::_)
go(...)

Apply ... map (1::_)

Return(List(1,2,3,4,5,6))
go(...)

Return result

go(Return(List(1,2,3,4,5,6)))

Pattern match (go)

List(1,2,3,4,5,6)

Finished.

Raw
Good.scala
import scala.annotation.tailrec
object Good {
import Trampoline.{GoSub, Return, Suspend}
def append[A](xs: List[A], ys: List[A]): Trampoline[List[A]] = xs match {
case Nil => Return(ys)
case x::r => Suspend(() => append(r,ys) map (x::_))
}
def main(args: Array[String]) = {
println(append((1 to 999999).toList, List(1000000)).run.length)
}
object Trampoline {
case class Return[A](a: A) extends Trampoline[A] {
override def flatMap[B](k: A => Trampoline[B]): Trampoline[B] = goSub(this, k)
}
case class Suspend[A](suspension: () => Trampoline[A]) extends Trampoline[A] {
override def flatMap[B](k: A => Trampoline[B]): Trampoline[B] = goSub(this, k)
}
private sealed abstract case class GoSub[A]() extends Trampoline[A] {
type I
val a: Trampoline[I]
val f: I => Trampoline[A]
override def flatMap[B](k: A => Trampoline[B]): Trampoline[B] = goSub(a, (x: I) => goSub(f(x), k))
}
private def goSub[I0,A](a0: Trampoline[I0], f0: I0 => Trampoline[A]) = new GoSub[A] {
type I = I0
val a = a0
val f = f0
}
}
sealed abstract class Trampoline[A] {
def map[B](f: A => B): Trampoline[B] = flatMap(a => Return(f(a)))
protected def flatMap[B](k: A => Trampoline[B]): Trampoline[B]
@tailrec
private final def go(trampoline: Trampoline[A]): A = trampoline match {
case Suspend(suspension) => go(suspension())
case Return(a) => a
case s @ GoSub() => s.a match {
case Suspend(suspension) => go(suspension() flatMap s.f)
case Return(a) => go(s.f(a))
case t @ GoSub() => go(t.a.flatMap(z => t.f(z) flatMap s.f))
}
}
final def run: A = go(this)
}
}
Raw
GoodEval.markdown

Initial call

go(append(List(1,2,3),List(4)))

Descend into argument

append(List(1,2,3),List(4))
go(...)

Pattern match (append)

Suspend(() => append(List(2,3),List(4)) map (1::_))
go(...)

Return result from append into go

go(Suspend(() => append(List(2,3),List(4)) map (1::_)))

Pattern match (go), descend into suspension

append(List(2,3),List(4)) map (1::_)
go(...)

Descend into ... map (1::_)

append(List(2,3),List(4))
... map (1::_)
go(...)

Pattern match (append)

Suspend(() => append(List(3),List(4)) map (2::_))
... map (1::_)
go(...)

Return result from append to ... map (1::_)

Suspend(() => append(List(3),List(4)) map (2::_)) map (1::_)
go(...)

Apply ... map (1::_)

Suspend(() => append(List(3),List(4)) map (2::_)).flatMap(a => Return(1::a))
go(...)

Apply flatMap

sub(Suspend(() => append(List(3),List(4)) map (2::_)), a => Return(1::a))
go(...)

Return result

go(sub(Suspend(() => append(List(3),List(4)) map (2::_)), a => Return(1::a)))

Pattern match (go), descend into flatMap

append(List(3),List(4)) map (2::_)
go(... flatMap (a => Return(1::a)))

Descend into ... map (2::_)

append(List(3),List(4))
... map (2::_)
go(... flatMap (a => Return(1::a)))

Pattern match (append)

Suspend(() => append(nil,List(4)) map (3::_))
... map (2::_)
go(... flatMap (a => Return(1::a)))

Return result from append to ... map (2::_)

Suspend(() => append(nil,List(4)) map (3::_)) map (2::_)
go(... flatMap (a => Return(1::a)))

Apply ... map (2::_)

Suspend(() => append(nil,List(4)) map (3::_)).flatMap(a => Return(2::a))
go(... flatMap (a => Return(1::a)))

Apply flatMap

sub(
  Suspend(() => append(nil,List(4)) map (3::_)),
  a => Return(2::a)
)
go(... flatMap (a => Return(1::a)))

Return result

go(
  sub(
    Suspend(() => append(nil,List(4)) map (3::_)),
    a => Return(2::a)
  )
  flatMap (a => Return(1::a))
)

Apply flatMap

go(
  sub(
    Suspend(() => append(nil,List(4)) map (3::_)),
    x => sub(
      Return(2::x),
      a => Return(1::a)
    )
  )
)

Pattern match (go), descend into flatMap

append(nil,List(4)) map (3::_)
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Descend into ... map(3::_)

append(nil,List(4))
... map (3::_)
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Pattern match (append)

Return(List(4))
... map (3::_)
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Return result from append to ... map (3::_)

Return(List(4)) map (3::_)
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Apply ... map (3::_)

Return(List(4)).flatMap(a => Return(3::a))
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Apply flatMap

sub(
  Return(List(4)),
  a => Return(3::a)
)
go(
  ...
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Return result

go(
  sub(
    Return(List(4)),
    a => Return(3::a)
  )
  flatMap (x => sub(
    Return(2::x),
    a => Return(1::a))
  )
)

Apply flatMap

go(
  sub(
    Return(List(4)),
    y => sub(
      Return(3::y),
      x => sub(
        Return(2::x),
        a => Return(1::a)
      )
    )
  )
)

Pattern match (go)

go(
  sub(
    Return(List(3,4)),
    x => sub(
      Return(2::x),
      a => Return(1::a)
    )
  )
)

Pattern match (go)

go(
  sub(
    Return(List(2,3,4)),
    a => Return(1::a)
  )
)

Pattern match (go)

go(Return(List(1,2,3,4)))

Pattern match (go)

List(1,2,3,4)

Finished.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment