Created
September 17, 2012 16:27
-
-
Save bmc/3738317 to your computer and use it in GitHub Desktop.
Test case for Scala CPS bug (or is it a bug)?
This file contains hidden or 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 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