Lucid, the Dataflow Programming Language (1985) [pdf] | Hacker News Reader

Lucid, the Dataflow Programming Language (1985) [pdf]

worrydream.com

57 pointstjalfi13 comments

Very interesting. Here is the plucid implementation, with an user manual: https://code.google.com/archive/p/plucid/downloads

https://github.com/mpw/pLucid-osx is a port of plucid to OS X.

It was merged with Java a bit at one point:

http://citeseerx.ist.psu.edu/viewdoc/citations;jsessionid=38...

Lustre gets more attention in research and formal verification. Maxeler has accelerators for data flow. Hardware languages are big into this paradigm. Just a few that come to mind.

Many times I've heard that DF is dead ..

Are you saying it seriously or sarcastically? Either way, it's currently a niche thing that seems to work for those using it but also poses challenges that people keep working on. Like many other techs. It's certainly not dead if we're talking about model-driven development of embedded where there's more vendors and tools over time.

No, I come from CGI where DF (DAG) are ubiquitous and many times people said "been there done that meh". I'm just surprised.

Interesting. I didn't even know they used that paradigm a lot in CGI. You have an example?

They often call that node based workflow, basically any high end software package use that be it 2D/Video compositing (ex Shake, Fusion, old Discreet (now autodesk) Flame and siblings) also Nuke. And in 3D Maya (hypergraph), Houdini (procedural modeling <= heh..). One interesting fact about Houdini, is that it allows freeform node composition be it 1D, 2D, 3D types of data.. basically you have a 3D first version of Mathematica. People used voronoi tesselation to generate cities out of random sampling of space into cloud points and then traditional extrusion operations. It's liberating.

It may not be exactly dataflow but it's a lazy recomputation of a graph by propagating changes from inputs to ouputs and using previously computed/cached values otherwise.

Computation aside, as a user I feel it's one of the most effective interface possible, there's no hidden parts, the model is right in your face and you can toy with it / iterate to understand the part you don't. Alas it's niche.. either research or rich markets.

Mike Pall's fantasy language is built around Dataflow...

https://www.freelists.org/post/luajit/Ramblings-on-languages...

(quoted in full for conveninece)

----

Szabó Antal wrote: > This topic interest me too, and I was wondering what a completely newly designed language + implementation (so it doesn't have any limitations or restrictions of existing languages) created by Mike would be like.

Well, I've been thinking about this for quite some time. But I'm approaching it from the other side: what's the most efficient CPU architecture and what would a language have to look like that makes the best use of it?

I'll start with a simple observation from the perspective of a compiler writer:

All modern and advanced compilers convert source code through various stages and representation into an internal data-flow representation, usually a variant of SSA. The compiler backend converts that back to an imperative representation, i.e. machine code. That entails many complicated transforms e.g. register allocation, instruction selection, instruction scheduling and so on. Lots of heuristics are used to tame their NP-complete nature. That implies missing some optimization opportunities, of course.

OTOH a modern CPU uses super-scalar and out-of-order execution. So the first thing it has to do, is to perform data-flow analysis on the machine code to turn that back into an (implicit) data-flow representation! Otherwise the CPU cannot analyze the dependencies between instructions.

Sounds wasteful? Oh, yes, it is. Mainly due to the impedance loss between the various stages, representations and abstractions.

That's just one example of a general problem: it's hard to preserve programmer intent across all stages down to the silicon. So when designing a language, one should strive to offer more intent-based programming concepts.

I strongly believe in the Sapir-Whorf hypothesis when it comes to computer language design. A likely conjecture is that if you offer the right abstractions, people will use them. So better design abstractions that map cleanly onto the target architecture(s). Alas, if you're only looking at current CPU architectures, you'd primarily offer plain imperative concepts. Thankfully, the arrival of GPGPUs in the mainstream has opened up the perspective somewhat.

But we're still very much entrenched in the thinking that jointly created the CPU architectures plus the matching languages in the last decades. This is neither surprising nor a bad thing per se -- we've witnessed enormous progress in scalar execution performance and (much less spectacular) progress in programming language implementation efficiency. But the real advances in e.g. parallel execution will only materialize by out-of-the-box thinking.

So, dreaming a little bit, a CPU based on a data-flow architecture is probably the way to go. Obviously, data-flow programming languages are a natural match. But most of the existing ones are visual languages. That's nice for some tasks, but IMHO these are not suitable for general programming. And before the functional programming crowd cheers: nope, sorry, the usual blend of concepts offered by FP languages is decidedly not what I'd personally consider worthwhile (some concepts in isolation certainly are).

Ok, so I have plenty of ideas for all levels of the stack, but not enough time to pursue them with sufficient rigor. And I can offer little tangible results at this time. Duh. But then, you've seen the subject of this posting, so that's what you got. :-) It's tough to find the right mix of concepts for such a language and yet make it attractive for programmers.

Anyway, please consider this my personal ramblings on what needs to be done to advance the state of the art. Your mileage may vary. Have fun thinking about these ideas and discussing them (but probably not here on this list). And please use them freely. Maybe start some research and revolutionize the world? Who knows ...

--Mike

I agree with Mike that conceptually, dataflow is a lot of what digital programming "does". And I've investigated how to apply dataflow to some depth and found that there are three thorny issues:

1. Digital logic is special: you want a logic coding syntax and often some additional abstraction like a FSM; manipulating little logic gate nodes in the flow graph is too fine-grained and doesn't lend itself to describing something like a network protocol. (On the other hand, it might make sense to compile down to that representation at code generation time.)

2. Addressing data is special: finding out "where state is" to pluck it out for processing, and to subsequently store it, is consistently more complicated than dereferencing a pointer, and motivates the complexity of database engines, IP addressing, etc. There are varying degrees of data binding, layers of caching, etc. This is a missing piece of the puzzle that hinders dataflow from being the obvious choice for any given scenario.

3. Bounded buffers are an important engineering detail: a dataflow language that lets you dump an unlimited amount of data into a node and push "start" is a pleasant abstraction, but does not properly express the hardware bottlenecks that motivate parallelism. Morrison FBP gets this aspect right, while many other approaches bury it, which imperils them later.

System Hyper Pipelining [1] can solve lots of problems with logic density, area reuse and having the right balance between operations on data and moving data around.

[1] https://arxiv.org/abs/1508.07139

Language ergonomics is more important than being CPU efficient. We have enough CPU performance that we can be a wasteful, LLVM in my opinion is good enough. Current industry standard languages are terrible in terms of productivity. Compared to Smalltalk or Lisps we seems to be standing in the same place for last 20 years.

What I would like to see is some kind of new take on Smalltalk with async/fibers and inferred static typing . I would like to see language that have hybrid interpreter/compiler modes that allow for decent performance in interpreted mode but to compile into binary when deploying into production.

> We have enough CPU performance that we can be a wasteful

This argument can't apply to an entire system with all its layers of abstraction. For example, if web browser developers had this attitude, the modern web could never exist -- the platform just wouldn't be fast enough. Every performance gain to things like CPU architectures or programming languages means more opportunities to "waste" the gain at a higher level on things like nice UI or ease of development.

Reply on news.ycombinator.com