Tarmo Uustalu | 21 Sep 22:29 2005
Picon
Picon

Paper: The essence of dataflow programming


Dear Haskell subscribers,

We would like to announce our new paper

The essence of dataflow programming

http://cs.ioc.ee/~tarmo/papers/essence.pdf

which describes a novel comonadic foundation of dataflow computing,
incl. semantics of dataflow languages a la Lucid or Lustre. The
central point is that comonads structure the context-dependence in
dataflow paradigms in much the same way as monads organize
effects. The paper was specifically written for functional
programmers (as opposed to semanticists).

The paper will not be presented at TFP/ICFP/GPCE in Tallinn. A
trimmed-down version will appear in Proc. of APLAS 2005. The full 
text has been submitted.

Best wishes,

Tarmo Uustalu, Varmo Vene
David Menendez | 26 Sep 07:01 2005

Re: Paper: The essence of dataflow programming

Tarmo Uustalu writes:

| We would like to announce our new paper
| 
| The essence of dataflow programming
| 
| http://cs.ioc.ee/~tarmo/papers/essence.pdf
| 
| which describes a novel comonadic foundation of dataflow computing,
| incl. semantics of dataflow languages a la Lucid or Lustre. The
| central point is that comonads structure the context-dependence in
| dataflow paradigms in much the same way as monads organize
| effects. The paper was specifically written for functional
| programmers (as opposed to semanticists).

This is really cool!

For those who haven't read the above paper yet, it describes how to
structure an interpreter for a dataflow language using comonads, similar
to the way you can structure an interpreter for an impure language using
monads. Inspired, I've tried my hand at implementing some of the example
dataflow functions directly in Haskell. 

This message is literate Haskell code. It uses the arrow syntax in a few
places; these are just examples, so you may comment them out if you do
not have a recent-enough GHCi or an arrow syntax preprocessor.

> {-# OPTIONS -farrows #-}
> module Dataflow where
> import Prelude hiding (sum)
(Continue reading)

Einar Karttunen | 26 Sep 09:45 2005
Picon
Picon

Re: Paper: The essence of dataflow programming

On 26.09 01:01, David Menendez wrote:
> We'll also define the injection combinator from Kieburtz's paper[1]:
> 
> > (.>>) :: Functor d => d a -> b -> d b
> > d .>> a = fmap (const a) d

We add some nice combinators:

(>>-) :: Comonad co => (co a -> co b) -> (co b -> co c) -> co a -> co c
a >>- b = b . a
infixr >>-

(>>--) :: Comonad co => (co a -> co b) -> (b -> co b -> co c) -> co a -> co c
a >>-- b = \co -> let x = a co in b (counit x) x
infixr >>--

coreturn v = cobind (const v)

And define the simple state comonad:

data StateC st a = StateC (st -> a) st

instance Comonad (StateC st) where
  counit (StateC f v)     = f v
  cobind fun (StateC f v) = StateC (\v -> fun (StateC f v)) v

get :: StateC st a -> StateC st st
get (StateC _ st) = StateC id st

set :: st -> StateC st a -> StateC st a
(Continue reading)

Tarmo Uustalu | 26 Sep 14:44 2005
Picon
Picon

Re: Paper: The essence of dataflow programming


Dear Dave,

Thanks for the nice propaganda!

A few comments regarding the points you made in your message.

Ineffeciency of fibo-like programs: Your observations are true. But this is a 
comonadic interpreter analogous to the cbv monadic interpreter. One can also 
define an analogue to the cbn monadic interpreter. This is better than the 
"cbv" version on the n first Fibonacci numbers but worse on the nth number 
alone...

Zippers: Yes, of course! Streams are an infinite linear datastructure, but you 
can also do trees (eg decorated parse trees of a CFG). Such trees with a 
distinguished position are of course the zipper datatype and this is a comonad 
as well. And similarly to the comonadic approach to the semantics of dataflow 
languages one can give a comonadic structure eg to attribute grammar 
specifications (either purely synthesized attribute grammars or general 
attribute grammars). We've developed these ideas in a paper that was presented 
at TFP, see

http://www.cs.ioc.ee/~tarmo/papers/tfp05.pdf

(this is the symposium version, the full version is in preparation.)

To present the comonadic semantics of attribute grammar specifications neatly, 
one needs either GADTs or dependent types.

Best wishes,
(Continue reading)


Gmane