You're right that dataflow is well suited for concurrent programming. For a certain class of problems, it's ability to express your intentions in simplistic form is outstanding.

I currently work on the compiler team for a dataflow programming language. Our compiler generates machine code for various processors, as well as VHDL for FPGAs. As you would probably expect, the generated code is very different depending on the target. Most CPUs are more suited to imperative programming rather than dataflow, so we often have to compromise on the granularity of parallelism to get good performance. On FPGAs, the compromise is typically reducing either parallelism or performance to save resources and making the code fit on the device.

Programming for a dataflow environment is definitely a very different experience. Our customers typically do not have a computer science background, and in some ways this is a blessing. Most people with a computer science background initially try to program imperatively when exposed to an inherently parallel dataflow language. It takes some time to adjust to it, but when it finally clicks you can begin to look at problems from the both perspectives simultaneously. I feel like having a mastery of the different styles (imperative, dataflow, functional, etc.) has improved my overall ability to solve problems regardless of which model of computation I decide to use.

Are you able to talk about your dataflow language and/or compilation techniques? I'd love to hear about them, if possible, as its something I'm very interested in and am looking into myself. I've found it dificult to find information on compilation techniques for compiling a dataflow language to a traditional processor so have been making most of it up as I need, but my own work is far from optimal. Any insights you can provide here would be appreaciated.

Are you simply converting dataflow code to blocks of imperative code and have these blocks running concurrently (eg, in threads) and communicating with each other? Or is there a more elaborate instruction scheduling mechanism at work?

Without going into too much detail for obvious reasons, we are doing as you mention - converting dataflow into blocks of imperative code and scheduling them on threads. Although the scheduling we do both at the thread level and also at the block level is non-trivial and reasonably optimized. I'm sure most of what I'll mention below you've already discovered if you're implementing a dataflow language, but just in case:

When implementing/generating code for a dataflow language it really depends on the level of granularity you want for your parallelism. On one extreme, you have super-fine-grained parallelism and can schedule each operation independently. On the other extreme, you have little or no parallelism and pre-schedule all of your operations in one big chunk. In the middle somewhere is typically a sweet spot where you have chunks of operations pre-scheduled, and then dynamically schedule those chunks.

A key to optimal dataflow code generation (while retaining parallelism) is figuring out where to draw that line regarding parallelism granularity. Too granular and you spend all your time scheduling. Too coarse and you lose all of your parallelism. The ideal point somewhere in the middle likely depends on the operations themselves (i.e. the composition of your language). In some cases it is a decision you have to make by trial and error. In other cases you can make more informed decisions based on the nature of the operations and the context of their use within the program.

Communication is really important as well. CPU caches encourage you to minimize data copies and operate on the data in place when possible (to minimize cache line fetches). Thus if your communication is based on a scheme where you need separate copies for each operation then your performance will really suffer. Message passing can work, so long as you are passing things by pointer and aren't having to make copies.

Thank you!!

My own simple implementation currently compiles mathematical expressions with an (optional) pre- and post-condition into a single block and then executes these blocks in a thread pool (ie, they don't have dedicated threads, but share a number of pre-created threads). There is obviously a significant overhead in passing data between the blocks, determining when they are ready to execute and so on. I have not yet looked at merging blocks, at some point I think I'll JIT merge multiple small blocks into a single large block.

As for data, my current system is statically typed, so it knows ahead of time what the datatype is. Simple values are passed in place and copied as needed. Complex values (structures, lists etc) are (or will be, I still have some work to do here) passed as pointers and the pointers copied as needed. In this case, the data itself uses a copy-on-write scheme, so that if it is only read, then no copies are made.

My implementation is currently not very intelligent. Operations are executed and scheduled in a virtual machine of sorts, though I will be JIT compiling expressions and conditions within the next week or two. Theres still loads of room for optimization though and I'm still trying to think of ways to make the block scheduling cheaper.

Always interested in hearing how people go about these problems, so thanks again for sharing.

Dataflow programming is exceptional for GUI programming, although I've never tried using it in a large application.

This style of programming does its best if it has support from the underlying language to enforce consistency. Without it, it's just too easy to get the program into an unconsistent state.

I'm aware of only two implementations providing dataflow programming: Cells for Common Lisp and FrTime for PLT Scheme (but I've actually used only the former).

"(issuing commands to hardware often has to be strictly sequential, for example)"

Do they, though? I mean, yes, sure, with current hardware this is true, but is this a true necessity, or an artifact of the fact that modern hardware is designed to be used by von Neumann machines?

Honest question, I don't know enough about hardware to have an answer. Can there be "functional hardware", or perhaps more practical, "dataflow hardware"?

See the recent discussion about Fleet dataflow hardware: http://news.ycombinator.com/item?id=723882

I missed this! Thank you for posting the link!!

It would be hard to create truly "functional" hardware. A piece of hardware is a real physical object with an internal state which is shared by all accessors and which can change over time. Shared, modifiable state is the exact opposite paradigm from the one that pure functional languages use.

I think this is also why pure functional languages are so hard for "normal" people to understand -- their basic premise is the opposite of the real world around us that's filled with stateful physical objects.

I think one other reason why von Neumann-type imperative programming was chosen over dataflow IS because sequential instructions and shared memory makes a lot of sense to us.

Having said that, a lot of non-programmers use graphical dataflow languages all the time, so maybe dataflow is ACTUALLY easier (at least for non-programmers - maybe the mathematical feel of imperative code attracts us programmers to it?) - eg, graphics tools often have dataflow languages for defining animations, materials, lighting and so on. I once used a dataflow tool for generating 3D visualizations and it was very intuitive.

The way I have had it explained to me (which I still don't quite get) is that an object is immutable if there was no time. When you mutate an object, it only happens due to time passing (ie if you were to "go back in time" the object would be as it was) - so changing something creates something else (in time). Confused.

If the commands don't have to be executed sequentially, then you don't have to issue them sequentially.

A modern processor will look at the incoming instructions and execute whatever it can without creating a hazard, this is called out of order execution.

http://en.wikipedia.org/wiki/Out-of-order_execution

OOO still preserves sequential semantics, so it's not that interesting from the programmer's perspective.

Not all the time, but often, yes.

A very simple example is user input and output: I want to print the prompt text before I let the user type their input.

The same is true for plenty of other hardware: I need to move the robot forward before I turn on the drill; I need to print page 1 before page 2 - etc etc. There are plenty of inherently sequential operations, thats all I was trying to say. ;-)

But you are not incorrect - obviously there IS some hardware which is only sequential because it was designed for von Neumann machines to drive it.

Dataflow hardware can exist (there are, or were, dataflow processors made) and hardware itself is inherently dataflow. In fact, VHDL and Verilog are inherently dataflow languages (possibly) running on FPGAs, which I guess could be seen as a sort of low level dataflow processor.

EDIT: @scott_s: Sure, but the end effect is the same, isn't it?

I think it's inaccurate to characterize VHDL and Verilog as "languages running on FPGAs." FGPAs aren't designed in anyway to run those languages; they're designed to emulate hardware. Since those are the languages used to describe hardware - including modern processors - what they produce can be mapped to run on an FPGA.

dkersten, indeed, the effect is the same. But this is a good discussion, and I wanted to make sure we all had the facts right.

Meta talk: responding to my post instead of editing yours makes more sense to me. First, I'm more likely to see it, and second, now I'm in the awkward position of replying to myself. I also find it disheartening that someone downmodded your comment from 2 to 1, presumably because I corrected you, but probably unaware that I was the one who upmodded you to begin with. Your point was valid, I just wanted the record to be accurate.

I'm glad that you are correcting me. I like to be corrected, because it means that I'm not relying on invalid information and I very much like learning new things, especially if related to something which interests me - like dataflow.

Sorry, HN wouldn't allow me to reply to your comment for some reason, so I edited mine.

PG recently implemented a brief "cooling off" period for comments, where there was no reply link. The purpose was to prevent long, nit-picking back-and-forths.