Last active
February 7, 2019 13:27
-
-
Save sergey-scherbina/f0d99206b83d934db63638ea196f02f4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import scala.annotation.tailrec | |
import Thunk._ | |
/* | |
https://www.cs.utah.edu/~mflatt/past-courses/cs6520/public_html/s02/cps.pdf | |
*/ | |
sealed trait Thunk[A, B] { | |
@inline final def run(f: A => B): B = Thunk.run(this, f) | |
} | |
object Thunk { | |
trait =>>[A, B] { | |
@inline final def <<=(a: A) = More(this, a) | |
def apply(a: A): Thunk[A, B] | |
} | |
final case class Done[A](a: A) extends Thunk[A, A] | |
final case class More[A, B](k: A =>> B, a: A) extends Thunk[A, B] | |
object Return { | |
@inline final def apply[A]: A =>> A = Done[A] | |
} | |
@tailrec final def run[A, B](thunk: Thunk[A, B], f: A => B): B = thunk match { | |
case More(k, a) => run(k(a), f) | |
case Done(a) => f(a) | |
} | |
implicit class ThunkOp[A](val thunk: Thunk[A, A]) extends AnyVal { | |
@inline final def get() = thunk.run(identity) | |
} | |
} | |
object CpsTco extends App { | |
@tailrec def mkList[T](n: Int)(k: List[Int] => T): List[Int] => T = | |
if (n <= 0) k else mkList(n - 1)(l => k(n :: l)) | |
print("\n`mkList(10)(id)`(Nil) == ") | |
println(mkList(10)(identity)(Nil)) | |
val `mkList(10000)(id)` = mkList(10000)(identity) | |
println("\nFunction `mkList(10000)(id)` exists: " + `mkList(10000)(id)`) | |
print("\n`mkList(10000)(id)`(Nil) == ") | |
try println(`mkList(10000)(id)`(Nil)) catch { | |
case t: Throwable => println(t) | |
t.getStackTrace().toStream.take(10).foreach(println) | |
} | |
@tailrec def mkListTco[T](n: Int)(k: List[Int] =>> T): List[Int] =>> T = | |
if (n == 0) k else mkListTco(n - 1)(l => k <<= n :: l) | |
print("\n`mkListTco(10)(id)`(Nil) == ") | |
println(mkListTco(10)(Return[List[Int]])(Nil)) | |
print("\n`mkListTco(10000)(id)`(Nil) == ") | |
println(mkListTco(10000)(Return[List[Int]])(Nil).get()) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment