We briefly discussed guarded commands and while loops. Jay would like to see a section in the user guide covering all of the branching constructs: if/then/else, the if site, pattern matching, guarded commands.

We also discussed lazy evaluation. Our running example is a function which publishes an alternating streams of 0s and 1s. The following naive implementation: def stream() = 0 >!_> 1 >!_> stream() does not work; since Orc evaluates eagerly, and recursive calls are allowed to happen within a single round, the evaluation of this expression publishes infinitely many values in a single round and thus causes starvation of the rest of the program by preventing any site from returning. The standard approach to simulating laziness in an eager functional language is to use a thunk. The closure suspends the computation, and the evaluation of the closure forces evaluation. In the case of streams of values, each unfolding needs to be explicit. Furthermore, the stream must return the next thunk to be evaluated: Here is the 01010... stream:

def one() = (1, zer) 
def zer() = (0, one)
This expression publishes one value from the stream every millisecond:
def stream(s) = Rtimer(1) >> s() >(!_,t)> stream(t) stream(zer)
From here we moved on to a discussion of scheduling and fairness in Orc. We discussed two options: 1. Every evaluation step takes some amount of time. This precludes doing an infinite amount of work in one round, and can be made fair with a FIFO strategy. However, it allows an external event to interrupt an ongoing internal computation, so it is possible to observe how long individual evaluation steps in Orc take to complete: val c = Buffer() def loop(i) = c.put(i) >> stop | loop(i+1) let(loop(0) | Rtimer(1000)) >> maximum(c.getAll()) This program determines how many recursive calls to loop were allowed to occur in one second. 2. Only returns from non-immediate site calls take time; they are scheduled between rounds, and every other action occurs within a round. This allows stronger reasoning about the behavior of time, and it prevents an external response from interrupting an internal computation. However, it is inherently unfair, because it allows internal computations to starve subexpressions that are waiting on external results. It is possible to partially resolve 1 and 2 by specifying that expansion of recursion occurs between rounds. Then, every round is necessarily finite, because the number of non-recursive steps is limited by the finite size of the program. This is similar to #1 except that it is possible to prioritize internal over external actions within a single round by still requiring that non-immediate sites return between rounds (presumably in some sort of fair scheduling along with recursion).

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-6) was last changed on 15-Dec-2010 16:42 by DavidKitchin