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.

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)

  }

}

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.

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)

  }

}

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.