Continuations...

I just found a paper, "Trampolined Style", by Gans, Friedman, and Wand, that describes alternatives to continuations.

http://www.cs.indiana.edu/~dfried/ts.ps

In some respects this style seems even more powerful then CPS with Call/CC. It is related to a technique I used to simulate continuations about 10 years ago using Catch / Throw. It is also distantly related to the technique I now use for running my GigaDSP simulation engines.

In GigaDSP I do not explicitly trampoline anything, but there is an evaluator thread always running against a queue of pending computations for each clock cycle. That queue is actually a 2-level priority queue. The front of the queue contains computations that need immediate processing. The back of the queue contains computations that should run once all pending immediate computations are completed.

The use of a 2-level priority queue (priority based on time of arrival - early arrivals have priority over later arrivals), allows for multi-rate computations and explicit sequencing on sub-clock cycles. Examples of such need would be a Runge-Kutta 4th order Integrator, where each computational time step involves 4 sub-cycles of computations of the corresponding network.

Another example would be where specific blocks of processing must proceed in some defined order. Since the network is asynchronous, one way to achieve an ordering is to produce sub-clock signals, and then tie the ordered block's clock inputs to sequential sub-clock outputs. Subclock initiated computations are added to the back end of the delayed priority portion of the queue. That allows all processing at one subclock interval to proceed to completion before the next subclock cycle gets initiated. And all subclocks proceed to completion before the next major clock cycle of the network.

My experience of a decade ago showed that Common Lisp could successfully use Catch / Throw with a central sequencer loop to simulate call/cc, but the runtime was penalized over kernel provided implementations. Catch / Throw is a relatively heavy-duty operation.

Dr. David McClain

Chief Technical Officer

Refined Audiometrics Laboratory

4391 N. Camino Ferreo

Tucson, AZ 85750

email: dbm@refined-audiometrics.com

phone: 1.520.390.3995

web: http://www.refined-audiometrics.com

Continuations...

David McClain writes:
 > I just found a paper, "Trampolined Style", by Gans, Friedman, and  
 > Wand, that describes alternatives to continuations.
 > 
 > http://www.cs.indiana.edu/~dfried/ts.ps
 > 
 > In some respects this style seems even more powerful then CPS with  
 > Call/CC. It is related to a technique I used to simulate  
 > continuations about 10 years ago using Catch / Throw. It is also  
 > distantly related to the technique I now use for running my GigaDSP  
 > simulation engines.
 > 
 > In GigaDSP I do not explicitly trampoline anything, but there is an  
 > evaluator thread always running against a queue of pending  
 > computations for each clock cycle. That queue is actually a 2-level  
 > priority queue. The front of the queue contains computations that  
 > need immediate processing. The back of the queue contains  
 > computations that should run once all pending immediate computations  
 > are completed.

There are similar structures used to schedule data transfers on
spacecraft busses.  Quite often there is a bus cycle related to the
spacecraft's control loop operating frequency (on the order of 10hz to
100hz range), each cycle's transfers are mapped out into a schedule.
The schedule details which data items are transfered between which
devices on the spacecraft bus.  Mapping out the schedules manually is
tedious but required in general, even though the amount of critical data
is fairly low, the non-critical transfers must also be controlled to
avoid interfering with the critical transfers.

Though its not generally considered from that perspective, this also
acts as a well specified quality of service implementation- since the
"slot" detailing each scheduled transfer has associated parameters
indicating how/if failures are retried, depth of queueing, etc.

On complex spacecraft, there may be are subschedules- or maybe small
cycles within the major cycles.  This sort of thing is driven by the
complexity of the data traversing the bus; ie a star tracker or a gyro
has a different sort of communications profile than a telemetry playback
function.  There are occasions for changing between schedules as well,
which can intentionally remove devices from the communication schedule-
free bandwidth, reduce power consumption, etcc.

Coupling of data transfers to computations may or may not be tight-
some computations must occur on the data items as they arrive, some can
be deferred until the cpu goes idle- depends on the task at hand.

Essentially, its a particular form of time domain multiplexing.

Greg