[Assorted-commits] SF.net SVN: assorted:[1564] sandbox/trunk/src/scala

[<yan...@us...>]

Revision: 1564
          http://assorted.svn.sourceforge.net/assorted/?rev=1564&view=rev
Author:   yangzhang
Date:     2010-02-08 03:09:40 +0000 (Mon, 08 Feb 2010)

Log Message:
-----------
more extensive exploration of continuations and implementations of `yield`

Modified Paths:
--------------
    sandbox/trunk/src/scala/Continuations.mk
    sandbox/trunk/src/scala/Continuations.scala

Modified: sandbox/trunk/src/scala/Continuations.mk
===================================================================
--- sandbox/trunk/src/scala/Continuations.mk	2010-02-08 02:05:32 UTC (rev 1563)
+++ sandbox/trunk/src/scala/Continuations.mk	2010-02-08 03:09:40 UTC (rev 1564)
@@ -4,6 +4,9 @@
 	fsc -Xplugin:/opt/scala-cont/continuations/build/pack/selectivecps-plugin.jar -deprecation -classpath $(CLASSPATH) $<
 run: all
 	scala -classpath .:$(CLASSPATH) Continuations
+gen: Continuations_cps.scala
+Continuations_cps.scala: Continuations.scala
+	fsc -Xplugin:/opt/scala-cont/continuations/build/pack/selectivecps-plugin.jar -deprecation -classpath $(CLASSPATH) -Xprint:selectivecps $< > $@
 clean:
 	rm -f Continuations.class
 .PHONY: run clean

Modified: sandbox/trunk/src/scala/Continuations.scala
===================================================================
--- sandbox/trunk/src/scala/Continuations.scala	2010-02-08 02:05:32 UTC (rev 1563)
+++ sandbox/trunk/src/scala/Continuations.scala	2010-02-08 03:09:40 UTC (rev 1564)
@@ -1,48 +1,33 @@
-import scala.continuations.ControlContext._
+import scala.continuations.cps
+import scala.continuations.ControlContext.{shift,reset,suspendable}
 
-/*
-class YieldReturnIterator[+T] extends Iterator[T] {
-  private[this] var nextValue: Option[Option[T]] = None
-  private[this] var getNext: () => Unit = null
-  protected def yieldReturn(x: T): Unit @cps[Unit, Unit] = {
-    shift { cont =>
-      nextValue = Some(Some(x))
-      getNext = cont
-    }
-  }
-  protected def body: Unit @cps[Unit, Unit] {
-    getNext = { () =>
-      reset {
-        body
-        nextValue = Some(None)
-        getNext = null
-      }
-    }
-  }
-  def hasNext: Boolean = {
-    if (nextValue.isEmpty)
-      getNext()
-    nextValue.get.isDefined
-  }
-  def next: String = {
-    if (nextValue.isEmpty)
-      getNext()
-    val e = nextValue.get.get
-    nextValue = None
-    e
-  }
-}
+// To see the plugin-rewritten source, use the `gen` make target.
 
-class My(array: Array[String]) extends YieldReturnIterator[String] {
-  def body = for (s <- array) yieldReturn(s)
-}
-*/
-
 object Continuations {
   def main(args: Array[String]) {
+    basics
+    println
+    nondelim
+    println
+    yielditer
+    println
+    symmetricYield
+    println
+    trampolineYield
+  }
+
+  def basics {
+    // Prints:
+    //
+    //   outside pre
+    //   inside pre
+    //   outside post
+    //   inside mid
+    //   outside post
+    //   inside post
     reset {
       println("outside pre")
-      val shi = shift { k: (Unit => Unit) =>
+      shift { k: (Unit => Unit) =>
         println("inside pre")
         k()
         println("inside mid")
@@ -50,11 +35,23 @@
         println("inside post")
       }
       println("outside post")
-    } // reset always just returns Unit
+    }
 
     println
 
-    reset {
+    // reset returns the evaluation of its first shift (that's where the
+    // computation may diverge).
+    //
+    // Prints:
+    //
+    //   outside pre
+    //   inside pre
+    //   outside post 2
+    //   inside mid 0.1
+    //   outside post 4
+    //   inside post 0.1
+    //   6
+    val six = reset {
       println("outside pre")
       val a = shift { k: (Int => Double) =>
         println("inside pre")
@@ -62,39 +59,345 @@
         println("inside mid " + b)
         val c = k(4) // pass a 4
         println("inside post " + c)
+        "6"
       }
       println("outside post " + a)
-      6.0
-    } // reset always just returns Unit
+      0.1
+    }
+    println(six)
 
     println
 
-    def next = shift { k: (Int => Unit) =>
+    // reset and shift don't have to be syntactically nested/statically associated
+    def threesome = shift { k: (Int => Unit) =>
       k(1)
       k(2)
       k(3)
     }
+    reset { println(threesome) } // prints 1 2 3
+    reset { println(threesome) } // prints 1 2 3
 
-    reset { println(next) } // prints 1 2 3
-    reset { println(next) } // prints 1 2 3
+    println
 
+    // You can have multiple shifts per reset.
+    //
+    // Prints:
+    //
+    //    1
+    //    1
+    //    2
+    //    3
+    //    2
+    //    1
+    //    2
+    //    3
+    //    3
+    //    1
+    //    2
+    //    3
+    reset { println(threesome); println(threesome) }
+
     println
 
-    //var nextVal: Int = 0
-    //var getNext: () => Int = null
-    //def next2 = shift { k: (Unit => Unit) =>
-    //  getNext = { () =>
-    //    nextVal += 1
-    //    k()
-    //    nextVal
-    //  }
-    //}
+    // for-loops, while-loops work inside shifts
+    def threesome2 = shift { k: (Int => Unit) => for (i <- 1 to 3) k(i) }
+    def threesome3 = shift { k: (Int => Unit) =>
+      var i = 0
+      while (i < 3) { i += 1; k(i) }
+    }
 
-    //reset {
-    //  next2
-    //  println(getNext)
-    //  next2
-    //  println(getNext)
-    //}
+    // But shifts don't work inside for-loops/while-loops.
+    // reset {
+    //   var i = 0
+    //   while (i < 3) threesome
+    //   ()
+    // }
+    // reset {
+    //   for (i <- 0 to 3) threesome
+    // }
+
+    // They *do* work in ifs/defs, and only if the `else` also is CPS.
+    reset {
+      if (true) threesome
+      else threesome
+      if (true) { threesome; () }
+      else { threesome; () }
+      // This doesn't work; if/else must return the same cps-type
+      // if (true) { threesome; () }
+      // else threesome
+      ()
+    }
+    reset {
+      def foo =
+        if (true) threesome
+        else threesome
+      def foo2 = {
+        if (true) threesome
+        else threesome
+        ()
+      }
+      foo
+      foo2
+      ()
+    }
+
+    // Need own looping constructs. See `loopWhile` for a general, reusable
+    // construct. Need to specify types because of recursion. Unfortunately,
+    // no way to leverage existing map/foreach/etc (a la for loops), because
+    // that would imply doing a CPS break-up of the map/foreach/etc.
+    reset {
+      def loop(i: Int): Unit @suspendable = {
+        if (i < 3) { threesome; loop(i+1) }
+      }
+      loop(0)
+    }
+
+    // The continuation really is just a regular function of the specified
+    // signature. Here, we "leak" it out of the whole shift-reset. (The only
+    // part of the code that is "transformed"/broken up is inside reset,
+    // broken up around the shift; this is what the type annots are for.)
+    //
+    // Prints:
+    //
+    //   in shift
+    //   outside reset, before kstore()
+    //   in reset, after shift
+    //   outside reset, after kstore()
+    val kstore = reset {
+      shift { k: (Unit => Unit) => println("in shift"); k }
+      println("in reset, after shift")
+    }
+    println("outside reset, before kstore()")
+    kstore()
+    println("outside reset, after kstore()")
   }
+
+  def nondelim {
+    // We can't implement non-delimited continuations, because anything
+    // outside of reset can't be broken up and must be run
+    // in-line/immediately.
+
+    def callCC(f: (Unit => Unit) => Unit) =
+      reset { shift { k: (Unit => Unit) => f(k); 3 }; println("cont") }
+
+    println("callCC returns " + callCC {
+      k: (Unit => Unit) => {
+        println("inside callCC")
+        k()
+      }
+    } )
+
+    println("callCC returns " + callCC {
+      k: (Unit => Unit) => {
+        println("inside callCC")
+        // If you comment this out, then only "cont" won't get printed,
+        // but everything outside the reset runs.
+        // k()
+      }
+    } )
+  }
+
+  // A reusable continuation-split looping construct.
+  def loopWhile(cond: =>Boolean)(body: =>(Unit @suspendable)): Unit @suspendable = {
+    if (cond) {
+      body
+      loopWhile(cond)(body)
+    }
+  }
+
+  def yielditer {
+    {
+      class Gen {
+        var prodCont: Unit => Unit = null
+        var i = 0
+        def prod = {
+          reset {
+            i += 1
+            shift { k: (Unit => Unit) => prodCont = k }
+
+            i += 1
+            shift { k: (Unit => Unit) => prodCont = k }
+
+            i += 1
+            shift { k: (Unit => Unit) => prodCont = k }
+          }
+        }
+        prodCont = { x: Unit => prod }
+        def next = { prodCont(); i }
+      }
+      val it = new Gen
+      println(it.next)
+      println(it.next)
+      println(it.next)
+      // Prints 3 again, because the continuation (after the last shift) does
+      // nothing.
+      println(it.next)
+    }
+
+    println
+
+    {
+      class Gen {
+        var prodCont: Unit => Unit = null
+        var i = 0
+        def prod = {
+          reset {
+            // Recall that the plugin can't handle shifts inside `while`s, but
+            // can handle our own looping constructs.
+            loopWhile (true) {
+              i += 1
+              shift { k: (Unit => Unit) => prodCont = k }
+            }
+          }
+        }
+        prodCont = { x: Unit => prod }
+        def next = { prodCont(); i }
+      }
+      val it = new Gen
+      println(it.next)
+      println(it.next)
+      println(it.next)
+    }
+
+    println
+
+    {
+      class Gen {
+        var prodCont: Unit => Unit = null
+        var nextVal = 0
+        def yld(i: Int) = shift { k: (Unit => Unit) => nextVal = i; prodCont = k }
+        def prod = {
+          reset {
+            var i = 0
+            loopWhile (true) {
+              i += 1
+              yld(i)
+            }
+          }
+        }
+        prodCont = { x: Unit => prod }
+        def next = { prodCont(); nextVal }
+      }
+      val it = new Gen
+      println(it.next)
+      println(it.next)
+      println(it.next)
+    }
+  }
+
+  def symmetricYield {
+    // Another way to provide yield, using continuations at the consumer as
+    // well (requiring the consumer to be transformed, i.e. can't provide
+    // conventional Iterator interface with this approach). From
+    // <http://stackoverflow.com/questions/2137619/scala-equivalent-to-python-generators/2146456#2146456>.
+
+    abstract class Generator[T] {
+      var producerCont : (Unit => Unit) = null
+      var consumerCont : (T => Unit) = null
+
+      protected def body : Unit @suspendable
+
+      reset {
+        body
+      }
+
+      def generate(t : T) : Unit @suspendable =
+        shift {
+          (k : Unit => Unit) => {
+            producerCont = k
+            if (consumerCont != null)
+              consumerCont(t)
+          }
+        }
+
+      def next : T @suspendable =
+        shift {
+          (k : T => Unit) => {
+            consumerCont = k
+            if (producerCont != null)
+              producerCont()
+          }
+        }
+    }
+
+    val g = new Generator[Int] {
+      def body = {
+        var i = 0
+        loopWhile(i < 10) {
+          generate(i)
+          i += 1
+        }
+      }
+    }
+
+    reset {
+      loopWhile(true) {
+        println("Generated: "+g.next)
+      }
+    }
+  }
+
+  def trampolineYield {
+    // From
+    // <http://stackoverflow.com/questions/2201882/implementing-yield-yield-return-using-scala-continuations/2215182#2215182>.
+    sealed trait Iteration[+R]
+    case class Yield[+R](result: R, next: () => Iteration[R]) extends Iteration[R]
+    case object Done extends Iteration[Nothing]
+
+    def trampoline[R](body: => Iteration[R]): Iterator[R] = {
+      def loop(thunk: () => Iteration[R]): Stream[R] = {
+        thunk.apply match {
+          case Yield(result, next) => Stream.cons(result, loop(next))
+          case Done => Stream.empty
+        }
+      }
+      loop(() => body).iterator
+    }
+
+    // Poor man's yield.
+
+    val itr1 = trampoline {
+      Yield(1, () => Yield(2, () => Yield(3, () => Done)))
+    }
+
+    for (i <- itr1) { println(i) }
+
+    println
+
+    // Rich man's yield.
+
+    def iterator[R](body: => Unit @cps[Iteration[R],Iteration[R]]): Iterator[R] =
+      trampoline {
+        reset[Iteration[R],Iteration[R]] { body ; Done }
+      }
+
+    def yld[R](result: R): Unit @cps[Iteration[R],Iteration[R]] =
+      shift((k: Unit => Iteration[R]) => Yield(result, () => k(())))
+
+    // Example.
+
+    val itr2 = iterator[Int] {
+      yld(1)
+      yld(2)
+      yld(3)
+    }
+
+    for (i <- itr2) { println(i) }
+
+    println
+
+    // Something more advanced.
+
+    def power(number: Int, exponent: Int): Iterator[Int] = iterator[Int] {
+      def loop(result: Int, counter: Int): Unit @cps[Iteration[Int],Iteration[Int]] = {
+        if (counter < exponent) {
+          yld(result)
+          loop(result * number, counter + 1)
+        }
+      }
+      loop(number, 0)
+    }
+
+    for (i <- power(2, 8)) { println(i) }
+  }
 }


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.