Tuesday, November 30, 2010

Nondeterministic Evaluation in Scala

Scala continuations can be used to implement nondeterministic evaluation.

Contents

Background

Nondeterministic evaluation is an approach in which choices among multiple alternatives are factored out of an application so as to allow writing the application as if all alternatives were simultaneously being considered. Factoring the application in this way allows using different strategies for searching the space of available choices with no or only small changes to the application code.

A truly nondeterministic evaluation would potentially give different results (possibly the same set of results in a different order) each time it is run. In the simplest implementations, the evaluation is actually deterministic and does give the same results every time it is run. A different way of interpreting the phrase "nondeterministic evaluation" is to think of it from the point of view of the application built on top of such an evaluator: the application is written as if the evaluation were nondeterministic, and the decision as to whether the implementation is deterministic or not is entirely within the evaluation package. In other words, the application is not determining the order of evaluation among alternatives, therefore from its perspective the evaluation is nondeterministic. If at some later time the evaluator is replaced by one with the same API but which is truly nondeterministic, the correctly-written application will continue to deliver valid results.

One of the benefits of a nondeterministic evaluation environment is that an application using that environment can (with some assumptions about the application's avoidance of side-effects) transparently be run in a multi-thread, multi-processor or multi-host version of that environment so as to parallelize the computation. Development of such an application can be done on a single-processor workstation using a small dataset, then moved to a more powerful environment for use on the real problem with a much larger dataset.

One simple model of nondeterministic evaluation is the amb evaluator discussed in the MIT "Wizard Book", Structure and Interpretation of Computer Programs (SICP) in Section 4.3. The amb operator was introduced by John McCarthy in his 1963 paper A Basis For a Mathematical Theory of Computation.

Goal

Before getting into the implementation, let's take a look at an example to show where we want to go. SICP starts its section on Logic Puzzles with this example:
The following puzzle (taken from Dinesman 1968) is typical of a large class of simple logic puzzles:
Baker, Cooper, Fletcher, Miller, and Smith live on different floors of an apartment house that contains only five floors. Baker does not live on the top floor. Cooper does not live on the bottom floor. Fletcher does not live on either the top or the bottom floor. Miller lives on a higher floor than does Cooper. Smith does not live on a floor adjacent to Fletcher's. Fletcher does not live on a floor adjacent to Cooper's. Where does everyone live?
We can determine who lives on each floor in a straightforward way by enumerating all the possibilities and imposing the given restrictions:
(define (multiple-dwelling)
  (let ((baker (amb 1 2 3 4 5))
        (cooper (amb 1 2 3 4 5))
        (fletcher (amb 1 2 3 4 5))
        (miller (amb 1 2 3 4 5))
        (smith (amb 1 2 3 4 5)))
    (require
     (distinct? (list baker cooper fletcher miller smith)))
    (require (not (= baker 5)))
    (require (not (= cooper 1)))
    (require (not (= fletcher 5)))
    (require (not (= fletcher 1)))
    (require (> miller cooper))
    (require (not (= (abs (- smith fletcher)) 1)))
    (require (not (= (abs (- fletcher cooper)) 1)))
    (list (list 'baker baker)
          (list 'cooper cooper)
          (list 'fletcher fletcher)
          (list 'miller miller)
          (list 'smith smith))))
Evaluating the expression (multiple-dwelling) produces the result
((baker 3) (cooper 2) (fletcher 4) (miller 5) (smith 1))
Here is what the above looks like in my Scala implementation (see the Examples section below for boilerplate):


MultipleDwelling.scala
class MultipleDwelling extends AmbEval[List[(String,Int)]] {
    def distinct(vals:List[Int]):Boolean = {
        vals.distinct.length == vals.length
    }
    generate {
        val baker = amb(List(1,2,3,4,5))
        val cooper = amb(List(1,2,3,4,5))
        val fletcher = amb(List(1,2,3,4,5))
        val miller = amb(List(1,2,3,4,5))
        val smith = amb(List(1,2,3,4,5))
        require(distinct(List(baker,cooper,fletcher,miller,smith)))
        require(baker!=5)
        require(cooper!=1)
        require(fletcher!=5)
        require(fletcher!=1)
        require(miller>cooper)
        require(scala.math.abs(smith-fletcher)!=1)
        require(scala.math.abs(fletcher-cooper)!=1)
        yld(List(
            ("baker",baker),
            ("cooper",cooper),
            ("fletcher",fletcher),
            ("miller",miller),
            ("smith",smith)))
    }
}
As you can see, it is quite similar to the lisp implementation. In particular, the code that solves this specific problem includes very little other than the statement of the problem: a set of possible values, a set of requirements, and a yielding of the solution. The implementation choices about how to make choices among the alternatives listed in the amb expressions and how to evaluate those alternatives are all handled in the code for the AmbEval class.

Of course, you could write something very similar to the above using for-comprehensions with guard statements, and that would likely be more practical for most situations, but besides the fact that you can't currently use a for-comprehension in suspendable (CPS) code and thus can't use that construct in a generator without modifications such as introduced in this post, that's just not as interesting as the amb evaluator.

The authors of SICP note that the evaluation of their straightforward implementation of multiple-dwelling is "very slow". When I execute my version on my desktop machine, it runs in less than 1/100th of a second. If that line was written in the original version of 1980, that same program could have taken 10,000 times as long to run, a couple of minutes - a long time for what seems like a small and simple program.

Implementation

In this post I implement a simple nondeterministic evaluator modeled on the amb evaluator introduced above that allows specific problems to be stated as in the above example and solved by the nondeterministic evaluator.

In SICP they build the amb evaluator in lisp along with a REPL that knows how to retrieve and print the multiple results returned by the evaluation. Rather than building my own Scala REPL, I chose to treat the nondeterministic evaluation as a generator. Thus a nondeterministic computation is implemented as a special kind of generator, and it returns its values as does a generator.

In my previous blog post I showed how to use Scala's delimited continuations to create a standalone generator. I now extend that generator to support nondeterministic evaluation. The use of continuations is an essential part of this implementation. Unlike in my previous examples of the use of continuations, where continuations were captured but only executed a single time, in this case a single continuation is executed multiple times.

As seen in the example in the Goal section above, the implementation uses a class called AmbEval, which defines the amb and require methods.
AmbEval.scala
package net.jimmc.scoroutine

import scala.collection.Iterator
import scala.util.continuations._

class AmbEval[T] extends StandaloneGenerator[T] {
    def amb[A](seq:Iterable[A]):A @cpsParam[Unit,Unit] = {
        shift { k:(A=>Unit) =>
            val it = seq.iterator
            reset[Unit,Unit] {
                //Use of var for v is workaround for Scala bug #3501
                var v:A = null.asInstanceOf[A]
                while (it.hasNext) {
                    v = it.next
                    k(v)
                    stepUntilDone
                }
            }
        }
    }

    def require(condition: =>Boolean):Unit @cpsParam[Unit,Unit] = {
        if (!condition) { amb(List()) }
    }
}
The amb method is mostly straightforward: it iterates through the values provided to it and calls the supplied continuation for each value. The continuation represents the remainder of the code following the call to amb, which means all of the code following the call to amb will be executed multiple times, once with each value supplied to the call to amb. Each of these calls is "searching" the solution space using one value from the set of alternatives supplied to amb.

When the calling code calls amb a second time, amb once again turns around and calls the remaining code multiple times, once for each value passed to amb. Thus the application code following the second call to amb gets executed once for each combination of every value in the first call to amb times every value in the second call to amb, which is the cross-product of those two set of alternatives. Likewise if the application has a third or fourth call to amb; each call to amb multiplies the number of times the following code is executed.

One subtlety of the implementation is the call to stepUntilDone. The call to the continuation k(v), which calls the code in the application following its call to amb, will return when that code has finished running; but if that code calls yld, it will be suspended, and control will return to amb after that suspension. At this point we need to suspend the amb code as well, and when it is resumed, ensure that we resume the continuation code that we called as k(v). As long as the continuation called from amb continues to suspend itself by calling yld, we need to continue suspending ourself in the same way. Once the continuation called from amb finishes and returns to amb without suspending itself, then amb can continue in its loop and invoke the continuation with the next selected value.

Note that using the yld method to return values from the generator and allowing multiple calls to yld by ensuring that every branch finishes its execution gives us a capability not in the lisp implementation defined in SICP and shown above. In that implementation, a valid choice is indicating by successfully reaching the end of a branch; the valid value is the return value of the function. In our implementation, a single branch can return multiple valid values by calling yld multiple times. This means that, in the Scala spirit, you are free to write your own code that imperatively determines for itself the validity of some of the potential alternatives rather than always using the amb and require methods to prune out invalid alternatives.

The stepUntilDone method implements the above algorithm to ensure that the called continuation completes. In order to know if the called continuation has suspended itself or completed execution, stepUntilDone needs to examine private data in the StandaloneGenerator class, so the cleanest solution is to add the stepUntilDone method to that class:
//Part of StandaloneGenerator.scala
    def stepUntilDone:Unit @suspendable = {
        //Use of var for saveStep is workaround for Scala bug #3501
        var saveStep:(Unit=>Unit) = null
        while (nextStep.isDefined) {
            saveStep = nextStep.get
            suspend     //sets nextStep to point here
            saveStep()
        }
    }
Note that the previously saved continuation from nextStep is saved in the local variable saveStep, which in turn is captured as part of the continuation then saved by the call to suspend. This provides a stacking mechanism that allows us to nest multiple calls to amb and properly manage the required backtracking. Since we are using local storage for this, we can have multiple instances of nondeterministic generators simultaneously suspended.

In both SICP and my implementation, the amb function does a depth-first search of the space of alternatives. This means it is not suitable for problems that includes multiple sets of alternatives where one or more sets are infinite. In fact, it really only does well on collections of sets that are small enough that the cross-product of all of the sets of choices can be fully enumerated, since the code choosing among alternatives makes its choice trivially and without any knowledge of which choices might be better than others. Also, the search space must not include any non-terminating branches, since eventually the algorithm would select that branch and get stuck.

As in SICP, the require method simply calls amb with no alternatives if its predicate is false, thus pruning the search tree at that point.

I did not attempt to implement any kind of side-effects backtracking such as capturing changes to global variables and undoing them after a branch finishes. Instead, regarding attempting to use code with side effects within a nondeterministic evaluation block, I offer this common suggestion: Don't Do That!

Examples

Using the AmbEval class we can easily code up the examples given in SICP. We start with the imports we use for all of the examples below:
import scala.collection.Iterator
import scala.util.continuations._
import net.jimmc.scoroutine._
Our examples will all be implemented as generator classes that extend the AmbEval class. We can see the results of each such computation by creating an instance of that class and printing out all of the values returned by the iterator. To simplify this, we define a little helper function to dump all of the results of an iterator:
def dump[T](gen:Iterator[T]) {
    for (x <- gen) println(x)
}
Here's how we can use this to print the results of evaluating the MultipleDwelling class given in the Goal section above:
dump(new MultipleDwelling)
output:
List((baker,3), (cooper,2), (fletcher,4), (miller,5), (smith,1))
Here are a few more examples, with their output given in a comment at the end of each code block.
A Pythagorean Triple Between
This problem is from SICP (exercise 4.35):
"implement a procedure that finds Pythagorean triples, i.e., triples of integers (i,j,k) between the given bounds such that i < j and i^2 + j^2 = k^2"
APythagoreanTripleBetween.scala
class APythagoreanTripleBetween(low:Int,high:Int) extends AmbEval[(Int,Int,Int)] {
    generate {
        val i = amb(low to high)
        val j = amb(i to high)
        val k = amb(j to high)
        require(i*i + j*j == k*k)
        yld((i,j,k))
    }
}
output from dump(new APythagoreanTripleBetween(1,20)):
(3,4,5)
(5,12,13)
(6,8,10)
(8,15,17)
(9,12,15)
(12,16,20)
Liars
This problem is from SICP (exercise 4.42):
Solve the following ``Liars'' puzzle (from Phillips 1934):
Five schoolgirls sat for an examination. Their parents -- so they thought -- showed an undue degree of interest in the result. They therefore agreed that, in writing home about the examination, each girl should make one true statement and one untrue one. The following are the relevant passages from their letters:
  • Betty: ``Kitty was second in the examination. I was only third.''
  • Ethel: ``You'll be glad to hear that I was on top. Joan was second.''
  • Joan: ``I was third, and poor old Ethel was bottom.''
  • Kitty: ``I came out second. Mary was only fourth.''
  • Mary: ``I was fourth. Top place was taken by Betty.''
What in fact was the order in which the five girls were placed?
Liars.scala
class Liars extends AmbEval[List[(String,Int)]] {
    def distinct(vals:List[Int]):Boolean = {
        vals.distinct.length == vals.length
    }
    generate {
        val betty = amb(List(1,2,3,4,5))
        val ethel = amb(List(1,2,3,4,5))
        val joan = amb(List(1,2,3,4,5))
        val kitty = amb(List(1,2,3,4,5))
        val mary = amb(List(1,2,3,4,5))
        require(distinct(List(betty,ethel,joan,kitty,mary)))
        require((kitty==2 && betty!=3) || (kitty!=2 && betty==3))
        require((ethel==1 && joan!=2) || (ethel!=1 && joan==2))
        require((joan==3 && ethel!=5) || (joan!=3 && ethel==5))
        require((kitty==2 && mary!=4) || (kitty!=2 && mary==4))
        require((mary==4 && betty!=1) || (mary!=4 && betty==1))
        yld(List(
            ("betty",betty),
            ("ethel",ethel),
            ("joan",joan),
            ("kitty",kitty),
            ("mary",mary)))
    }
}
output from dump(new Liars):
List((betty,3), (ethel,5), (joan,2), (kitty,1), (mary,4))
RosettaExample
This problem is from the rosettacode.org wiki page for Amb:
The example is using amb to choose four words from the following strings:

set 1: "the" "that" "a"

set 2: "frog" "elephant" "thing"

set 3: "walked" "treaded" "grows"

set 4: "slowly" "quickly"

It is a failure if the last character of word 1 is not equal to the first character of word 2, and similarly with word 2 and word 3, as well as word 3 and word 4. (the only successful sentence is "that thing grows slowly").
RosettaExample.scala
class RosettaExample extends AmbEval[List[String]] {
    generate {
        def joins(s1:String, s2:String) = s1.endsWith(s2.substring(0,1))
        val w1 = amb(List("the","that","a"))
        val w2 = amb(List("frog","elephant","thing"))
        val w3 = amb(List("walked","treaded","grows"))
        val w4 = amb(List("slowly","quickly"))
        require(joins(w1,w2))
        require(joins(w2,w3))
        require(joins(w3,w4))
        yld(List(w1,w2,w3,w4))
    }
}
output from dump(new RosettaExample):
List(that, thing, grows, slowly)

Other Implementations

If you poke around on the net you can find implementations of nondeterministic evaluators such as the amb evaluator. Some of these implementations suffer from one or more of three problems:
  • They use a for-comprehension or direct sequence iteration rather than an external amb evaluator. To see the difference, consider how the code would have to be modified in order to choose alternatives from each set of choices in random order rather than left-to-right. In an amb evaluator, this change can be made in one place.
  • They don't separate the application requirements from the mechanism that makes choices among alternatives. This can be seen by considering how a second example problem would be implemented in the same framework. It should be possible to implement the second problem by sharing code used in the implementation of the first problem but without either modifying or duplicating any code from the first problem.
  • They use a global variable to store a stack of continuations. This makes it impossible to run two independent nondeterministic evaluations at the same time.
Implementations of amb in various languages:
  • RosettaCode, implementations in many languages - but many of the implementations suffer from the problems listed above. In particular, the Scala implementation uses direct sequence iteration (in the form of a recursive tail operation on a list) and does not separate the application requirements (of first and last letters of adjacent words being the same) from the mechanism that makes choices among alternatives.
  • Nondeterministic evaluation in under 300 bytes of Python - Uses a global variable to store a stack of continuations.
  • Ruby - Uses a global variable to store a stack of continuations.
  • C#, Linq - Uses direct sequence iteration.
  • Scheme
Some interesting terms:
  • Angelic choice - always avoids choices that lead to nonterminating branches.
  • Demonic choice - always makes choices that lead to nonterminating branches.
  • Erratic choice - choices may or may not lead to nonterminating branches.