Cells compared to Flow-Based Programming

I've read nearly half of the book http://www.jpaulmorrison.com/fbp/book.pdf
from the page http://www.jpaulmorrison.com/fbp/ and I think it would be
interesting for some people of this newsgroup to summarize the concepts of
Flow-Based Concepts (FBP), compare it to Cells and what we can learn from
it. If you like to read some of the basic concepts yourself, take a look at
http://en.wikipedia.org/wiki/Flow-based_programming for FBP and
http://bc.tech.coop/blog/030911.html for Cells.

Cells is a spreadsheet-like object oriented CLOS extension: You define
classes and getter and setter methods, and whenever a value is changed, all
values, which are calculated based on this value, changes too, and
listeners can be registered and called on value change.

FBP is very different: When developing applications, you start with
defining information packets (IP). In Lisp an IP could be a hashtable or
any other Lisp object. Then you define some processes and interconnect
them. A process has inputs and outputs for processing IPs. The process
itself is a program, with local storage. A process can be instantiated
multiple times and can be configured with configuration IPs (there are
preemptive and cooperative multitasking implementations).

The main motivation of FBP is to reuse stable and tested processes for many
applications. According to the book, at IBM they have successfully used it
in many projects and one example with three projects, in the third project
they achieved a reuse rate of about 97% (PDF pages 42/43 in the book). This
sounds impressive, but they were mostly talking about business
applications, like accounting applications for a bank, and if you have
three projects for three banks, I would expect such a rate for most modern
concepts and languages, but in these days when they were writing assembler,
COBOL, PL/I and other strange things on mainframes (these are some
languages the author of the book used at the time the book was written)
this would be more difficult.

I think Cells is more fine granular: there are not a few connected black
boxes, but a network of connected values. FBP has the advantage, that
connections are explicit, but the IP concept doesn't allow to connect one
outgoing connection to multiple input connections (but you can build a
process, which has one input and two outputs, which duplicates the input to
the outputs), like used for the spreadsheet-like Cells. I don't know which
concept is better, maybe this depends on the application. But I think every
Cells network can be transformed to a FBP-like network, but the other
direction would be more difficult, so FBP may be a more general concept.

Cells is somewhat orthogonal to FBP: you could use Cells objects as IPs
inside of processes and you could use FBP networks inside update rules of
Cells objects.

Anyone interested in implementing FBP in Lisp? Many things mentioned in the
book, which may be difficult in other languages, like the loose coupling of
components with IPs and the difficulties of typed structures, linking etc.,
are no problem in Lisp. An interesting problem could be to implement the
"driver" in Lisp, which provides an API for building and invoking the
network. Maybe for testing it would be nice to implement a simple virtual
machine, which could be used to implement process activation and
deactivation and preemptive multitasking in Common Lisp. Another idea maybe
would be to use preemtive multitasking, with Scheme-like continuations,
like implemented in ARNESI for Common Lisp.

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

FB> FBP is very different:

from what you describe it's different only terminologically..

FB> When developing applications, you start with defining information
FB> packets (IP). In Lisp an IP could be a hashtable or any other Lisp
FB> object.

so IP is just a fancy way to say "any object"? maybe it matter for
distributed
implementations, where IPs have to be serializable

FB> Then you define some processes and interconnect them. A process has
FB> inputs and outputs for processing IPs. The process itself is a program,
FB> with local storage. A process can be instantiated multiple times and
FB> can be configured with configuration IPs (there are preemptive and
FB> cooperative multitasking implementations).

in Cells terminology, process is model (class), process instance is an
object,
interconnect is synapse.

FB> The main motivation of FBP is to reuse stable and tested processes for
FB> many applications.

so is OOP, and articles you've linked say that OOP is quite related to FBP

FB> I think Cells is more fine granular: there are not a few connected
black
FB> boxes, but a network of connected values.

in other words, Cells doesn't hide guts of processes from you, right?

FB> better, maybe this depends on the application. But I think every Cells
FB> network can be transformed to a FBP-like network, but the other
FB> direction would be more difficult, so FBP may be a more general
FB> concept.

for my untrained eye Cells seems to be like a particular implementation of
FBP concepts. can you show an example what general FBP can do
but Cells can't?

Alex Mizrahi wrote:
> FB> FBP is very different:
>
> from what you describe it's different only terminologically..

I am curious if the "feel" is different. In Cells I think about state in
a static steady-state kinda way, just as a spreadsheet author thinks
about only how to compute the cell in front of them but then has to
write one rule for all time and all circumstances. Yes, it makes
event-handling trickier to think about, one giveback of Cells.

FBP sounds as if one thinks about a pipeline of processing and
transformations one wants for state.

We may have dataflow in both models and much different programming
experiences. But the IBM folks report the same high productivity Cells
users enjoy, so perhaps the key is exactly what Brooks identified:
decomposing the complexity of the the interdependence of large numbers
of kinds of state. As long as one does that (and both seem to) we're good.

FBP may be more work than Cells, btw. I do not think about these wires
coming in or about laying out some circuit, I Just Write the Code:
dependencies are detected automatically for me. eg, a spreadsheet author
(once they learn how one works) Just Writes Rules. I get the feeling
the FBP have to think in terms of circuits feeding circuits and getting
them wired together.

>
> FB> When developing applications, you start with defining information
> FB> packets (IP). In Lisp an IP could be a hashtable or any other Lisp
> FB> object.
>
> so IP is just a fancy way to say "any object"? maybe it matter for
> distributed
> implementations, where IPs have to be serializable
>
> FB> Then you define some processes and interconnect them. A process has
> FB> inputs and outputs for processing IPs. The process itself is a program,
> FB> with local storage. A process can be instantiated multiple times and
> FB> can be configured with configuration IPs (there are preemptive and
> FB> cooperative multitasking implementations).
>
> in Cells terminology, process is model (class), process instance is an
> object,
> interconnect is synapse.

And the idea of process as object is kinda weird to me. RDF has shaken
my affection for OO, but not state as central to application design. FBP
almost sounds as if it is still code-oriented, the way flowcharts make
processing preeminent and the data just happens to slide along these arrows.

>
> FB> The main motivation of FBP is to reuse stable and tested processes for
> FB> many applications.
>
> so is OOP, and articles you've linked say that OOP is quite related to FBP
>
> FB> I think Cells is more fine granular: there are not a few connected
> black
> FB> boxes, but a network of connected values.
>
> in other words, Cells doesn't hide guts of processes from you, right?

I guess each Cell could be considered a black box, but they are not so
general to my mind as a black box. Different instances of the same class
get different rules for the same slot, so these rules are not
super-reusable abstracted functions, they are very specific hard-coded
little value generators, often closures over values that further tailor
their output.

What ends up being reusable is the class (yippee! The Grail!) because
the class no longer says so much about an instance. ie, Cells cheats.

kt

>
> FB> better, maybe this depends on the application. But I think every Cells
> FB> network can be transformed to a FBP-like network, but the other
> FB> direction would be more difficult, so FBP may be a more general
> FB> concept.
>
> for my untrained eye Cells seems to be like a particular implementation of
> FBP concepts. can you show an example what general FBP can do
> but Cells can't?
>
>

--
http://smuglispweeny.blogspot.com/
http://www.theoryyalgebra.com/
ECLM rant:
http://video.google.com/videoplay?do...93764413&hl=en
ECLM talk:
http://video.google.com/videoplay?do...42928&q=&hl=en

On Sat, 24 May 2008 01:30:20 +0200, Frank Buss <fb@frank-buss.de>
wrote:

>I've read nearly half of the book http://www.jpaulmorrison.com/fbp/book.pdf
>from the page http://www.jpaulmorrison.com/fbp/ and I think it would be
>interesting for some people of this newsgroup to summarize the concepts of
>Flow-Based Concepts (FBP), compare it to Cells and what we can learn from
>it. If you like to read some of the basic concepts yourself, take a look at
>http://en.wikipedia.org/wiki/Flow-based_programming for FBP and
>http://bc.tech.coop/blog/030911.html for Cells.
>
>Cells is a spreadsheet-like object oriented CLOS extension: You define
>classes and getter and setter methods, and whenever a value is changed, all
>values, which are calculated based on this value, changes too, and
>listeners can be registered and called on value change.
>
>FBP is very different: When developing applications, you start with
>defining information packets (IP). In Lisp an IP could be a hashtable or
>any other Lisp object. Then you define some processes and interconnect
>them. A process has inputs and outputs for processing IPs. The process
>itself is a program, with local storage. A process can be instantiated
>multiple times and can be configured with configuration IPs (there are
>preemptive and cooperative multitasking implementations).
>
>The main motivation of FBP is to reuse stable and tested processes for many
>applications. According to the book, at IBM they have successfully used it
>in many projects and one example with three projects, in the third project
>they achieved a reuse rate of about 97% (PDF pages 42/43 in the book). This
>sounds impressive, but they were mostly talking about business
>applications, like accounting applications for a bank, and if you have
>three projects for three banks, I would expect such a rate for most modern
>concepts and languages, but in these days when they were writing assembler,
>COBOL, PL/I and other strange things on mainframes (these are some
>languages the author of the book used at the time the book was written)
>this would be more difficult.
>
>I think Cells is more fine granular: there are not a few connected black
>boxes, but a network of connected values. FBP has the advantage, that
>connections are explicit, but the IP concept doesn't allow to connect one
>outgoing connection to multiple input connections (but you can build a
>process, which has one input and two outputs, which duplicates the input to
>the outputs), like used for the spreadsheet-like Cells. I don't know which
>concept is better, maybe this depends on the application. But I think every
>Cells network can be transformed to a FBP-like network, but the other
>direction would be more difficult, so FBP may be a more general concept.
>
>Cells is somewhat orthogonal to FBP: you could use Cells objects as IPs
>inside of processes and you could use FBP networks inside update rules of
>Cells objects.
>
>Anyone interested in implementing FBP in Lisp? Many things mentioned in the
>book, which may be difficult in other languages, like the loose coupling of
>components with IPs and the difficulties of typed structures, linking etc.,
>are no problem in Lisp. An interesting problem could be to implement the
>"driver" in Lisp, which provides an API for building and invoking the
>network. Maybe for testing it would be nice to implement a simple virtual
>machine, which could be used to implement process activation and
>deactivation and preemptive multitasking in Common Lisp. Another idea maybe
>would be to use preemtive multitasking, with Scheme-like continuations,
>like implemented in ARNESI for Common Lisp.

You're reading too much into particular implementations and uses
described in the book. Flow based programming, and the dataflow model
in general, is about streaming data through a series of "filters"
which examine and/or transform it. The granularity of the filter -
process, thread, function, multiply-adder, whatever - is not really
relevant to the concept.

Originally dataflow was conceived as a software model of a parallel
hardware scheme called "asynchronous logic with registers". The
hardware idea was to have separately clocked (or free running analog)
logic units connected by register queues so each unit could run at its
own speed, triggered whenever input was available and not worrying
(much) about synchronization for input or output.

The simplest of the software dataflow models is one of server
processes communicating by messaging, but that is not the only
possible model. Somebody recently mentioned the Linda programming
language - a somewhat different implementation where all communication
between application units is performed through a software associative
memory.

You're also getting too caught up in the communication abstraction.
The book's "information packets" are nothing more than the logical
"wires" connecting the functional units of the application. It really
doesn't matter whether the wiring is implemented using IPC messaging,
in(ter)-process signaling, function callbacks, shared memory or actual
wires.

I don't know too much about Kenny's Cell projects except from skimming
what he has written here, but IIUC, Cells allows objects to be linked
into dependency notification chains so that a change to one object can
affect all its dependents. AFAICT from such a simple understanding,
Cells qualifies as an implementation of dataflow.

George
--
for email reply remove "/" from address

Alex Mizrahi wrote:

> so IP is just a fancy way to say "any object"? maybe it matter for
> distributed implementations, where IPs have to be serializable

Yes, in the FBP book an IP can be any object. There are special IPs, like
brackets for implementing sub-streams. But this is just a concept, not
built into the framework.

> in Cells terminology, process is model (class), process instance is an
> object, interconnect is synapse.

What is a Cells synapse? I didn't used Cells very much, but I don't think
this maps very well, because in FBP all processes are running in parallel,
which is not possible with Cells.

> FB> The main motivation of FBP is to reuse stable and tested processes for
> FB> many applications.
>
> so is OOP, and articles you've linked say that OOP is quite related to FBP

Yes, the local storage and instances of processes are a bit similar to
classes and objects and a FBP implementation can be done in OOP, like done
with Java and threads:

http://www.jpaulmorrison.com/fbp/jsyntax.htm

> for my untrained eye Cells seems to be like a particular implementation of
> FBP concepts. can you show an example what general FBP can do
> but Cells can't?

I'm sure you can implement everything in Cells which you can implement in
FBP, but it might look different and I'm not sure, if reusable for large
applications is as high as with FBP.

For example, take a look at the telegram problem:

http://en.wikipedia.org/wiki/Flow-ba...ram_Problem.22

Your task is to write a function, which reformats a text for a specified
line width, e.g. this call:

(telegram "
Du bist am Ende- was du bist. Setz dir Perücken auf von Millionen Locken,
Setz deinen Fuß auf ellenhohe Socken, Du bleibst doch immer, was du bist."
30)

outputs these lines:

Du bist am Ende- was du bist.
Setz dir Perücken auf von
Millionen Locken, Setz deinen
Fuß auf ellenhohe Socken, Du
bleibst doch immer, was du
bist.

In Lisp, it could look like below. I think implementing the driver should
be not too difficult. E.g. in LispWorks there are some nice multithreading
functions and the "mailbox" object, which could be used for the
connections.

The implementation is longer than a conventional implementation, but the
coupling between the processes are very loose, so unlike in conventional
OOP programs reusing it in other programs is easier. A nice GUI for placing
the process instances, configuring it, and drawing the connections would be
cool.

;;;
;;; split a string into lines
;;;
(defun read-sequence ()
(with-input-from-string (s (config-port-read 'input-string))
(loop for line = (read-line file nil) while line do
(port-send 'line line))))

(add-config-port #'read-sequence 'input-string)
(add-output-port #'read-sequence 'line)

;;;
;;; split a line into words
;;;
(defun de-compose ()
(loop for line = (port-read 'line)
while line do
(loop for word in (split-sequence #\Space line) do
(port-send 'word word)))
(port-send 'word nil))

(add-input-port #'de-compose 'line)
(add-output-port #'de-compose 'word)

;;;
;;; merge words into a line
;;;
(defun re-compose ()
(let ((line "")
(line-width (config-port-read 'line-width)))
(loop for word = (port-read 'word)
while word do
(if (> (+ (length line) (length word))
line-width)
(progn
(port-send 'line line)
(setf line word))
(setf line (concatenate 'string line " " word))))
(port-send 'line line))
(port-send 'line nil))

(add-config-port #'re-compose 'line-width)
(add-input-port #'re-compose 'word)
(add-output-port #'re-compose 'line)

;;;
;;; write lines to output
;;;
(defun write-sequence ()
(loop for line = (port-read 'line)
while line do (format t "~x~%" line)))

(add-input-port #'write-sequence 'line)

;;;
;;; create network and run it
;;;
(defun telegram (string line-width)
(let ((read-sequence (make-process #'read-sequence))
(de-compose (make-process #'de-compose))
(re-compose (make-process #'re-compose))
(write-sequence (make-process #'write-sequence)))
(configure read-sequence ort 'input-string :value string)
(configure re-compose ort 'line-width :value line-width)
(connect :sender read-sequence :sender-port 'line
:receiver de-compose :receiver-port 'line)
(connect :sender de-compose :sender-port 'word
:receiver re-compose :receiver-port 'word)
(connect :sender re-compose :sender-port 'line
:receiver write-sequence :receiver-port 'line)
(run-fbp-network)))

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

George Neuner wrote:

> The simplest of the software dataflow models is one of server
> processes communicating by messaging, but that is not the only
> possible model. Somebody recently mentioned the Linda programming
> language - a somewhat different implementation where all communication
> between application units is performed through a software associative
> memory.

Erlang has another nice idea for connections between processes, like the
mailbox functions in LispWorks.

> You're also getting too caught up in the communication abstraction.
> The book's "information packets" are nothing more than the logical
> "wires" connecting the functional units of the application.

I think this is wrong, because the information packets are the data, which
are traveling through the connections.

> It really
> doesn't matter whether the wiring is implemented using IPC messaging,
> in(ter)-process signaling, function callbacks, shared memory or actual
> wires.

Yes, this is true. I think it could be very useful for high performance
applications with multiple CPU cores and multiple computers.

> I don't know too much about Kenny's Cell projects except from skimming
> what he has written here, but IIUC, Cells allows objects to be linked
> into dependency notification chains so that a change to one object can
> affect all its dependents. AFAICT from such a simple understanding,
> Cells qualifies as an implementation of dataflow.

This depends on how you define "dataflow" :-)

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

Frank Buss wrote:

> What is a Cells synapse? I didn't used Cells very much, but I don't think
> this maps very well, because in FBP all processes are running in parallel,
> which is not possible with Cells.

Why is it not possible?

Ken Tilton wrote:

> FBP sounds as if one thinks about a pipeline of processing and
> transformations one wants for state.

Yes, that's right. The author compares it with the pipe operator found in
DOS and Unix shells: There are lots of simple programs, like sort, unique
etc., and you can feed the output of one program to the input of another
program.

> We may have dataflow in both models and much different programming
> experiences. But the IBM folks report the same high productivity Cells
> users enjoy, so perhaps the key is exactly what Brooks identified:
> decomposing the complexity of the the interdependence of large numbers
> of kinds of state. As long as one does that (and both seem to) we're good.

While trying to implement the telegram problem in FBP Lisp, this was
exactly my feeling: You can concentrate on writing just one process, with
explicit defined input and outputs. Then you can connect the components and
the program just works (if you've tested the components before and the
specification of the ports matches).

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

Sohail Somani wrote:

> Frank Buss wrote:
>
>> What is a Cells synapse? I didn't used Cells very much, but I don't think
>> this maps very well, because in FBP all processes are running in parallel,
>> which is not possible with Cells.
>
> Why is it not possible?

We have to ask this Kenny, but I don't think that Cells is multithreading
safe and the concept of Cells is not to have many parallel running
processes.

--
Frank Buss, fb@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de

In article <tvmp8kuaxn1f$.kpjws99l19su$.dlg@40tude.net>,
Frank Buss <fb@frank-buss.de> wrote:

> Alex Mizrahi wrote:
>
> > so IP is just a fancy way to say "any object"? maybe it matter for
> > distributed implementations, where IPs have to be serializable
>
> Yes, in the FBP book an IP can be any object. There are special IPs, like
> brackets for implementing sub-streams. But this is just a concept, not
> built into the framework.
>
> > in Cells terminology, process is model (class), process instance is an
> > object, interconnect is synapse.
>
> What is a Cells synapse? I didn't used Cells very much, but I don't think
> this maps very well, because in FBP all processes are running in parallel,
> which is not possible with Cells.
>
> > FB> The main motivation of FBP is to reuse stable and tested processes for
> > FB> many applications.
> >
> > so is OOP, and articles you've linked say that OOP is quite related to FBP
>
> Yes, the local storage and instances of processes are a bit similar to
> classes and objects and a FBP implementation can be done in OOP, like done
> with Java and threads:
>
> http://www.jpaulmorrison.com/fbp/jsyntax.htm
>
> > for my untrained eye Cells seems to be like a particular implementation of
> > FBP concepts. can you show an example what general FBP can do
> > but Cells can't?
>
> I'm sure you can implement everything in Cells which you can implement in
> FBP, but it might look different and I'm not sure, if reusable for large
> applications is as high as with FBP.
>
> For example, take a look at the telegram problem:
>
> http://en.wikipedia.org/wiki/Flow-ba...ram_Problem.22
>
> Your task is to write a function, which reformats a text for a specified
> line width, e.g. this call:
>
> (telegram "
> Du bist am Ende- was du bist. Setz dir Perücken auf von Millionen Locken,
> Setz deinen Fuß auf ellenhohe Socken, Du bleibst doch immer, was du bist."
> 30)
>
> outputs these lines:
>
> Du bist am Ende- was du bist.
> Setz dir Perücken auf von
> Millionen Locken, Setz deinen
> Fuß auf ellenhohe Socken, Du
> bleibst doch immer, was du
> bist.
>
> In Lisp, it could look like below. I think implementing the driver should
> be not too difficult. E.g. in LispWorks there are some nice multithreading
> functions and the "mailbox" object, which could be used for the
> connections.
>
> The implementation is longer than a conventional implementation, but the
> coupling between the processes are very loose, so unlike in conventional
> OOP programs reusing it in other programs is easier. A nice GUI for placing
> the process instances, configuring it, and drawing the connections would be
> cool.
>
> ;;;
> ;;; split a string into lines
> ;;;
> (defun read-sequence ()
> (with-input-from-string (s (config-port-read 'input-string))
> (loop for line = (read-line file nil) while line do
> (port-send 'line line))))
>
> (add-config-port #'read-sequence 'input-string)
> (add-output-port #'read-sequence 'line)
>
> ;;;
> ;;; split a line into words
> ;;;
> (defun de-compose ()
> (loop for line = (port-read 'line)
> while line do
> (loop for word in (split-sequence #\Space line) do
> (port-send 'word word)))
> (port-send 'word nil))
>
> (add-input-port #'de-compose 'line)
> (add-output-port #'de-compose 'word)
>
> ;;;
> ;;; merge words into a line
> ;;;
> (defun re-compose ()
> (let ((line "")
> (line-width (config-port-read 'line-width)))
> (loop for word = (port-read 'word)
> while word do
> (if (> (+ (length line) (length word))
> line-width)
> (progn
> (port-send 'line line)
> (setf line word))
> (setf line (concatenate 'string line " " word))))
> (port-send 'line line))
> (port-send 'line nil))
>
> (add-config-port #'re-compose 'line-width)
> (add-input-port #'re-compose 'word)
> (add-output-port #'re-compose 'line)
>
> ;;;
> ;;; write lines to output
> ;;;
> (defun write-sequence ()
> (loop for line = (port-read 'line)
> while line do (format t "~x~%" line)))
>
> (add-input-port #'write-sequence 'line)
>
> ;;;
> ;;; create network and run it
> ;;;
> (defun telegram (string line-width)
> (let ((read-sequence (make-process #'read-sequence))
> (de-compose (make-process #'de-compose))
> (re-compose (make-process #'re-compose))
> (write-sequence (make-process #'write-sequence)))
> (configure read-sequence ort 'input-string :value string)
> (configure re-compose ort 'line-width :value line-width)
> (connect :sender read-sequence :sender-port 'line
> :receiver de-compose :receiver-port 'line)
> (connect :sender de-compose :sender-port 'word
> :receiver re-compose :receiver-port 'word)
> (connect :sender re-compose :sender-port 'line
> :receiver write-sequence :receiver-port 'line)
> (run-fbp-network)))

See the history of Scheme:
http://research.sun.com/projects/plr...2006public.pdf

Scheme was created to understand the Actors theory from Carl Hewitt.

Inspired in part by SIMULA and Smalltalk, Carl Hewitt
developed a model of computation around ³actors²
Every agent of computation is an actor
Every datum or data structure is an actor
An actor may have ³acquaintances² (other actors it knows)
Actors react to messages sent from other actors
An actor can send messages only to acquaintances
and to actors received in messages
³You don¹t add 3 and 2 to get 5; instead, you send 3
a message asking it to add 2 to itself²

This means that programs are networks of concurrent Actors that
are sending messages and react to messages.

There are a couple of Actor implementations. I did a rough port
of ABCL/R2 to Clozure CL and to another Lisp system. The actors are
running concurrently.

Here is a snippet of an actor (example from ABCL1) from a Car Wash simulation:

You can see that the object reacts to a couple of messages (:arrive, :available, ...),
creates other objects and send messages to them. There are different types of
messages. Typically each object has an input queue of messages and executes
those (this can be interrupted by 'express messages'). In the original Actor (IIRC)
model the Actor copies itself and the copy executes the next message and so on.

[object Manager
(state [history := [createHistory <== :new]]
[car-q := [createPriorityQueue <== [:new #'< #'third]]]
[worker-q := [createPriorityQueue <== [:new #'< #'third]]]
[previous-worker-available-time := 0])

(script
(=> [:arrive X] ; X ::= [:car CarId ArrivalTime]
[car-q <= [:enqueue X]]
(processing))
(=> [:available X] ; X ::= [:worker Worker AvailableTime]
[worker-q <= [:enqueue X]]
(processing))
(=> [:undo [:available [:worker Worker AvailableTime]]]
(loop-forever
(match [history <== :top]
(is [:record Car ArrivalTime PreviousWorker PreviousAvailableTime]
where (and (>= PreviousAvailableTime AvailableTime)
(not (eq Worker PreviousWorker)))
[history <= op]
[car-q <= [:undequeue [:car Car ArrivalTime]]]
[worker-q <=
[:undequeue [:worker PreviousWorker PreviousAvailableTime]]]
[PreviousWorker <=
[:undo [:wash Car :from (max ArrivalTime PreviousAvailableTime)]]])
(otherwise (return))))
(match [history <== :top]
(is [:record Car ArrivalTime PreviousWorker PreviousAvailableTime]
where (and (eq Worker PreviousWorker)
(= AvailableTime PreviousAvailableTime))
[history <= op]
[car-q <= [:undequeue [:car Car ArrivalTime]]]
[PreviousWorker <=
[:undo [:wash Car :from (max ArrivalTime PreviousAvailableTime)]]])
(otherwise
[worker-q <= [:remove [:worker Worker AvailableTime]]]))
(match [history <== :top]
(is nil [previous-worker-available-time := 0])
(is [:record _ _ _ AvailableTime]
[previous-worker-available-time := AvailableTime])))
(=> :reset
[[car-q worker-q history] <= :reset]
[previous-worker-available-time := 0])
(=> [rint-history]
[history <= rint]))
(routine
(processing ()
(loop-forever
(match [worker-q <== :top]
(is [:worker Worker AvailableTime]
where (>= AvailableTime previous-worker-available-time)
(match [car-q <== :top]
(is nil (return))
(is [:car Car ArrivalTime]
(washing Car ArrivalTime Worker AvailableTime))))
(is [:worker Worker AvailableTime]
where (< AvailableTime previous-worker-available-time)
(roll-back Worker AvailableTime))
(otherwise (return)))))
(washing (car arrival-time worker available-time)
[Worker <= [:wash car :from (max arrival-time available-time)]]
[car-q <= :dequeue]
[worker-q <= :dequeue]
[history <= [ush [:record car arrival-time worker available-time]]]
[previous-worker-available-time := available-time])
(roll-back (worker available-time)
(match [history <== :top]
(is [:record Car ArrivalTime PreviousWorker PreviousAvailableTime]
[history <= op]
[car-q <= [:undequeue [:car Car ArrivalTime]]]
[PreviousWorker <=
[:undo [:wash Car :from (max ArrivalTime PreviousAvailableTime)]]]
[worker-q <= :dequeue]
[worker-q <=
[:undequeue [:worker PreviousWorker PreviousAvailableTime]]]
[worker-q <= [:undequeue [:worker worker available-time]]]))
(match [history <== :top]
(is nil [previous-worker-available-time := 0])
(is [:record _ _ _ AvailableTime]
[previous-worker-available-time := AvailableTime]))))]

--
http://lispm.dyndns.org/