Home

The essence of Dataflow Programming by Tarmo Uustalu and Varmo Vene

The Essence of Dataflow Programming

The abstract:

We propose a novel, comonadic approach to dataflow (streambased) computation. This is based on the observation that both general and causal stream functions can be characterized as coKleisli arrows of comonads and on the intuition that comonads in general must be a good means to structure context-dependent computation. In particular, we develop a generic comonadic interpreter of languages for context-dependent computation and instantiate it for stream-based computation. We also discuss distributive laws of a comonad over a monad as a means to structure combinations of effectful and context-dependent computation. We apply the latter to analyse clocked dataflow (partial streams based) computation.

If you've ever wondered about dataflow or comonads, this paper is a good read. It begins with short reviews of monads, arrows, and comonads and includes an implementation. One feature that stood out is the idea of a higher-order dataflow language.

By shapr at 2005-09-21 22:23 | Functional | Implementation | Logic/Declarative | Theory | other blogs | 28415 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

URL?

A link to the paper would be nice.

By slava at Wed, 2005-09-21 22:26 | login or register to post comments

Yeah!

Now with 100% more urls!

--Shae Erisson - ScannedInAvian.com

By shapr at Wed, 2005-09-21 22:29 | login or register to post comments

Nitpick

100% of zero is still zero...

This paper looks very interesting, but I think I need to work through some preparatory material first - a good tutorial on arrows, say. Do you know of any such material, perhaps as yet unpublished? ;)

By Dominic Fox at Thu, 2005-09-22 08:42 | login or register to post comments

John Hughes' "Generalising Mo

John Hughes' "Generalising Monads to Arrows" worked for me. YMMV, it assumes basic understanding of monads.

By Daniel Yokomizo at Thu, 2005-09-22 12:28 | login or register to post comments

For a concrete example using

For a concrete example using arrows, take a look at Anthony Courtney's work on the Fruit GUI toolkit. It gives an extended example that uses arrows as a structuring device. This helped me turn it from some abstract stuff into a concrete thing.

By neelk at Thu, 2005-09-22 15:14 | login or register to post comments

comonads and RT?

Browsing an earlier LtU thread on comonads, the question of whether comonads break referential transparency comes up. Has that issue been resolved?

By Greg Buchholz at Thu, 2005-09-22 15:15 | login or register to post comments

OI

Many comonads are implementable in Haskell, therefore they immediately are referentially transparent. The issue was with a comonadic IO scheme.

By Derek Elkins at Thu, 2005-09-22 21:18 | login or register to post comments

Recent developments

Einar Karttunen has written up a comonad library that includes convenient combinators and demonstrates Reader, State, Stream, and Writer implementations.

Dave Menendez replied to the original posting on the Haskell mailing list with code that compares monads, arrows, and comonads, and mentions some interesting possibilities.

Personally, I wonder if comonadic functional reactive simulations is easier and less troublesome than arrow based FRP.


--Shae Erisson - ScannedInAvian.com

By shapr at Mon, 2005-09-26 09:45 | login or register to post comments

I don't know...

...but I'm trying to find out. This is a really cool paper. :)

By neelk at Mon, 2005-09-26 18:49 | login or register to post comments

Here's my critique of this paper

As posted on another thread, here's a draft paper of mine, "Another essence of dataflow programming," which criticizes this paper, proposing that McBride & Paterson's applicative functor is a more appropriate data type than the comonad. Their paper is "Applicative programming with effects."

By bdenckla at Wed, 2006-01-11 19:57 | login or register to post comments

I'm afraid I at best scan-rea

I'm afraid I at best scan-read it, but can you characterise what about dataflow programming, if anything, you can capture with comonads that you can't with applicative functors?

By Philippa Cowderoy at Thu, 2006-01-12 14:35 | login or register to post comments

Why AF better than comonad in capturing dataflow semantics

I assume you mean the reverse of what you asked, i.e. what is captured better by applicative functor than comonad. In other words, what's better about my work than theirs.

To answer, first, my (AF-based) semantics are simpler, so, I claim to have come closer to capturing the "essence" of dataflow semantics than they have. I don't think there is one true "essence" but I don't feel comonads are even one of many possible essences.

Perhaps the fact that it can be done at all with a comonad (regardless of how simply) is of theoretical interest, but that is not the slant Uustalu and Vene and put on it. They claim (over-ambitiously I think) that comonadic semantics capture the "essence" of dataflow semantics.

Second, the AF approach captures the intuition that intensional dataflow languages like Lucid, are, semantically, functional languages with stream ground types. This intuition is not captured with comonads.

My personal take on the whole thing is they succumbed to the understandable excitement of finding an application for comonads and confused a task that *can* be done with a comonad for one that *should* be done with a comonad.

By bdenckla at Thu, 2006-01-12 16:51 | login or register to post comments