Skip to content

Instantly share code, notes, and snippets.

@bmc
Created September 17, 2012 16:27
Show Gist options
  • Save bmc/3738317 to your computer and use it in GitHub Desktop.
Save bmc/3738317 to your computer and use it in GitHub Desktop.
Test case for Scala CPS bug (or is it a bug)?
import java.io.File;
import scala.util.continuations._
/** Functions that can be used to simulate Python-style generators.
* Adapted liberally from Rich Dougherty's solution, as outlined in
* Stack Overflow: [[http://stackoverflow.com/questions/2201882#2215182]]
*
* Example usage:
*
* {{{
* import grizzled.generator._
* import scala.util.continuations._
* import java.io.File
*
* def recursivelyListFiles(dir: File): Iterator[File] = generator[File] {
* def handleList(list: List[File]): Unit @cps[GeneratorIteration[File]] = {
* list match {
* case Nil => ()
*
* case f :: tail => {
* generate(f)
* doList(if (f.isDirectory) f.listFiles.toList else Nil)
* doList(tail)
* }
* }
* }
*
* handleList(dir.listFiles.toList)
* }
* }}}
*
* This package uses the Scala compilers continuations plug-in. The above
* example must be compiled with tha plug-in enabled. Use the
* `-P:continuations:enable` flag.
*/
object Generator {
sealed trait Iteration[+T]
case class Yield[+T](result: T, next: () => Iteration[T]) extends Iteration[T]
case object Done extends Iteration[Nothing]
/** Create a function trampoline. The body should return either
*
* - `Yield`, with the result and the next function to call, or
* - `Done`, to signal completion.
*/
def trampoline[T](body: => Iteration[T]): Iterator[T] = {
def loop(thunk: () => Iteration[T]): Stream[T] = {
thunk.apply match {
case Yield(result, next) => Stream.cons(result, loop(next))
case Done => Stream.empty
}
}
loop(() => body).iterator
}
/** Used to define a generator; the code (`body`) is the partial function
* to run as the generator. Within the body, you can call `generate()`
* to yield values. The result of a generator, from the caller's
* perspective, is a typed iterator.
*/
def generator[T](body: => Unit @cps[Iteration[T]]): Iterator[T] = {
trampoline {
reset[Iteration[T], Iteration[T]] {
body
Done
}
}
}
/** Called from within the body of a generator, `generate()` yields a
* value back from the generator.
*/
def generate[T](result: T): Unit @cps[Iteration[T]] = shift {
k: (Unit => Iteration[T]) => Yield(result, () => k(()))
}
}
object Test {
import Generator._
/**
* List a directory recursively, returning `File` objects for each file
* (and subdirectory) found. This method does lazy evaluation, instead
* of calculating everything up-front, as `walk()` does.
*
* If `topdown` is `true`, a directory is generated before the entries
* for any of its subdirectories (directories are generated top down).
* If `topdown` is `false`, a directory directory is generated after
* the entries for all of its subdirectories (directories are generated
* bottom up).
*
* Uses generators.
*
* @param file The `File` object, presumed to represent a directory.
* @param topdown `true` to do a top-down traversal, `false` otherwise.
*
* @return a generator (iterator) of `File` objects for everything under
* the directory. If `file` isn't a directory, the generator will
* be empty.
*/
def listRecursively(file: File, topdown: Boolean = true): Iterator[File] =
generator[File] {
def doList(list: List[File]): Unit @cps[Iteration[File]] = {
list match {
case Nil => ()
case f :: tail => {
if (topdown) {
generate(f)
doList(if (f.isDirectory) f.listFiles.toList else Nil)
}
else {
doList(if (f.isDirectory) f.listFiles.toList else Nil)
generate(f)
}
doList(tail)
}
}
}
if (file.isDirectory)
doList(file.listFiles.toList)
}
/** Tester, which bails.
*/
def main(args: Array[String]) = {
val paths = Set(
("/tmp/cpstest/foo", "bar.c"),
("/tmp/cpstest/foo", "baz.txt"),
("/tmp/cpstest", "test.txt"),
("/tmp/cpstest/foo/bar", "baz.txt")
)
paths.map { tup => new File(tup._1) }.foreach { dir => dir.mkdirs }
paths.map { tup =>
new File(tup._1 + "/" + tup._2)
}.foreach { f =>
new java.io.FileOutputStream(f, true) // touch
}
println(listRecursively(new File("/tmp/cpstest")).toSet)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment