Summary
There are many different models of computation. Here's an uncommon one which could have relevance in the future.

I love programming languages. I don’t know why, but whenever I hear of a new one I think, well, here’s a chance to think about problems in a different way. Some languages push you towards new insights and others are just crude variations on the last popular language. Yet others are just fun. If you have a chance, try googling “esoteric programming languages”, “befunge”, “brainf**k”, “unlambda”, or “thue.” There is a thriving subculture of people who enjoy designing and reading about these small, quirky languages (here I’m using the word “thriving” as a euphemism for sporadic postings by people with interests like mine on an extremely low volume mailing list: listar@esoteric.sange.fi). But, hey, not all interests can be popular.

Most esoteric programming languages are designed to be weird for weirdness sake, as a sort of reclusive form of performance art, but a few weeks ago, I was reminded of an extremely interesting programming language. I don’t know if anyone has branded it esoteric, but I know that I’ve had more fun thinking about it than any one person should have. The name of the language is Lucid. I was reminded of it by a mention in a recent interview with Alan Kay (the father of Smalltalk). It reminded me of the weeks I’d checked out a book called ‘Lucid, the Dataflow Programming Language’ back when I was in school. It was great fun trying to decipher it, but most of it was beyond me back then.

So, here’s Lucid..

Lucid is a non-imperative dataflow language, designed over 20 years ago by William W. Wadge and Edward A. Ashcroft. The idea is that nearly all programming languages are based in the idea of ‘flow of control’. What do we get when we try to orient around ‘flow of data’ instead? One immediate reaction would be, “well, I bet it is like programming with pipes and filters in UNIX", and sure enough it is, but Lucid goes a little beyond that. Let’s build up a simple example.

Here is a simple program in Lucid (as I understand it, I haven’t found an interpreter yet)..

	x

That was simple enough. We typed in a variable name, x. The program just sits there now until we give it a value for x. Suppose we type in 3. If we do, the program will reply with a 3. The value 3 is accepted by x, so that is what we get when the program is evaluated. Let’s look at another program:

	x + y

We type that in, and the program just sits there waiting, so we type in 31. More silence as the program waits.. then we type in another number: 11. The program responds with 42. What’s going on here? Well, Lucid doesn't evaluate expressions in a conventional way. It interprets an expression until it gets to a variable that it doesn’t know, then it patiently waits for a value (a daton) on the input stream. Once it has all the values it needs, it advances to the next stage of computation. Sometimes that involves outputting the next value.

Interestingly, this means that expressions have state in the language. When the expression x + y sees 31, the 31 is held in memory until another value is seen. Then the two values are added together and flushed out to the output stream. I’ll show a larger Lucid program a little later, but it’s kind of interesting to notice right off the bat that Lucid programs have persistent state by default, and they don’t ever have to halt. You can pause them by cutting off the flow of data into them, but then they will just sit there, with data in them in much the same way that plumbing without pressure holds residual water.

Here is a slightly more involved Lucid program:

	total
		where
			total = 0 fby total + x
		end;

This program computes a running total of its inputs. To understand it, you have to know that ‘fby’ is a binary operator named “followed by”. The statement total = 0 fby total + x should be understood as “the value of total starts with 0, all subsequent times it will be total + x. Because we have not given a value to x, x will pull the next value off the stream when it is evaluated.

So, far these examples have been pretty tame, but there are some very interesting/odd features in the language. One of them is an operator named ‘next’. The ‘next’ operator returns the next value in a stream. So, for instance, the expression:

	next a – a

won’t produce anything when we give it it’s first value, say 0, for instance. But when we give it another value, say, 1, it will produce 1. If we then give it 4, we will get 3. With next, we can have programs like this one:

	running_avg
		where 
			sum = first(input) fby sum + next(input);
			n = 1 fby n + 1;
			running_avg = sum / n;
		end;

And, that isn’t all. Lucid has a series of other operators. Ones like asa (read: “as soon as”), upon (“advance upon”), and whenever. They are used to pause, condition, and filter flows within programs.

Lucid isn’t a very active language, to say the least, but from what I’ve read it influenced a series of other data flow languages in the mid-80s. Last week, I purchased a copy of the one and only book about Lucid: Lucid, the Dataflow Programming Language (Academic Press 1985 ISBN 0-12-72965-1) from a used book seller, just to satisfy my curiosity. Sadly, the book is out of print, but there is other information on Bill Wadge’s website.

If you ask me why I’m reading about Lucid, I’d have to say that I don’t know. Just curiosity, I guess. But I think there is something deeper. I really like how Lucid seems to make computation very tangible. Object orientation does this with message passing, Lucid does it with the metaphor of infinite streams of values flowing through a program. Both seem to encourage the same sort of operational thinking. The fact that Lucid is completely different makes it very intriguing to me. From what I've read, functional (Lisp-ish) thinking is as much of a drawback in dataflow programming as imperative thinking.

Practical value? I don’t know, but recently there has been a lot of talk about how the pace of processor speed improvements is slowing. One of the motivations behind Lucid was to create a language that could easily take advantage of parallelism. Think of an architecture where a program is a vast network of pipes and each stage in the pipeline can be dedicated to a processor. The data flows from stage to stage with much of the computation happening in parallel. That was the dream, but this language is 20 yrs old. I’m curious about what happened to this line of research.

Note: most of the examples in this blog were gleaned from Wadge and Ashcroft's book. Without having an interpreter in hand, I wasn't comfortable publishing new ones.

Talk Back!

Have an opinion? Readers have already posted 9 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Michael Feathers adds a new entry to his weblog, subscribe to his RSS feed.

Digg | del.icio.us | Reddit

About the Blogger

Michael has been active in the XP community for the past five years, balancing his time between working with, training, and coaching various teams around the world. Prior to joining Object Mentor, Michael designed a proprietary programming language and wrote a compiler for it, he also designed a large multi-platform class library and a framework for instrumentation control. When he isn't engaged with a team, he spends most of this time investigating ways of altering design over time in codebases.