Dataflow and Comonads was Re: [Haskell-cafe] Monads in Scala, ...

Bill Wood william.wood3 at comcast.net
Sat Nov 26 17:25:59 EST 2005


On Sat, 2005-11-26 at 18:43 +0100, Shae Matijs Erisson wrote:
> Greg Woodhouse <gregory.woodhouse at sbcglobal.net> writes:
> 
> > Maybe this is a different topic, but exploring concurrency in Haskell is
> > definitely on my "to do" list, but this is really a bit of a puzzle.  One
> > thing I've been thinking lately is that in functional programming the process
> > is really the wrong abstraction (computation is reduction, not a sequence of
> > steps performed in temporal order). But what is concurrency if their are no
> > processes to "run" concurrently? I've beren thinking about action systems and
> > non-determinism, but am unsure how the pieces really fit together.
> 
> Maybe dataflow languages like Lucid Synchrone, Esterel and Lustre?
> http://en.wikipedia.org/wiki/Dataflow_language
> http://en.wikipedia.org/wiki/Synchronous_programming_language

I also think dataflow is a very nice model for concurrency in pure
functional languages.  You might want to look at some of the work done
by Edward Lee's group in the EE Dept. at Berkeley.  They developed a
generalization of dataflow called "token flow" which is quite nice.  It
became one of the basic models supported by their heterogeneous
simulation systems, Ptolemy and Ptolemy II.  I seem to recall that one
student at a Texas university did a PhD thesis on dataflow for Haskell
and then went to work on token flow in Lee's group.

The one downside I found to using dataflow was that most software people
seem to be uncomfortable with the lack of identifiable processes doing
significant bits of work.  I guess if they they're not floundering
around in mutual exclusion, semaphores, deadlock detection and all the
other manifestations of unmanaged complexity, they don't feel they've
*accomplished* anything (BTW I grew up on Dijkstra, Hoare and Hanson, so
I can get away with saying this :-).  Interestingly enough, and perhaps
obvious in retrospect, I often found hardware designers to be very
comfortable with dataflow computations.

Does anyone know whether much research has been done on using dataflow
for concurrency in pure functional computation?  How does it mesh with
evaluation strategies?  And, of course, the flip side: has anyone looked
at re-examining real-world problems, conventionally handled with
coordinating/communicating processes, as dataflow computations?

The latter consideration may be the toughest to deal with.  I was
working on a project to handle PHY level communication algorithms with
dataflow, and I had a great deal of difficulty with the comma-detect
function of XAUI.  I made some progress, but I never found a
satisfactory solution.  On the other hand, I did work out a fairly nice
dataflow algorithm for CRC32.

 -- Bill Wood




More information about the Haskell-Cafe mailing list