The functional pearl "There and and back again" by Danvy and Golfberg use this problem as a motivational example.

Here is the first page:

There and back again

Yes, my exercise is a variation on the first of Danvy's exercises. The difference is that I ask for the function to be tail recursive. This difference makes a big difference!

The space requirements for n stack frames or n dataflow variables are both O(n). Is there really a difference?

Well, is there a difference whether append is tail-recursive or not, since the input list is O(n)? In both the append and the convolution examples, the difference in space is (just) a constant factor. If the input list has 10 million elements, it can make a difference. But the purpose of my little exercise was to show an example of the expressive power of dataflow variables when used in sequential functional programming.

Note though, that the solution on page 3 in the paper is tail recursive.

the solution on page 3 in the paper is tail recursive

Yes, but it does more than n recursive calls, because it has to call a helper function. My exercise explicitly asked for a single function that does just n recursive calls. (As a warm-up, write a tail-recursive append that takes just n recursive calls and that does not need any helper functions.)

Here is a tail-recursive append written in Oz that does not need any helper functions:

 proc {Append Xs Ys Zs}
    case Xs
    of nil then Zs=Ys
    [] X|Xr then Zr in
       Zs=X|Zr
       {Append Xr Ys Zr}
    end
 end

Although this is a function, I have written it in procedural notation to highlight why it is tail recursive. (The procedural notation is a partial translation to the Oz kernel language, which is the process calculus underlying Oz.) This definition uses an unbound dataflow variable Zr, which is passed to the recursive call. Because Zr is left unbound before the recursive call, the list construction X|Zr can be done *before* the call, which makes the Append tail recursive. The above definition can be written in a functional notation:

 fun {Append Xs Ys}
    case Xs
    of nil then Ys
    [] X|Xr then X|{Append Xr Ys}
    end
 end

This has identical semantics as the previous definition. The symbolic convolution also uses unbound dataflow variables. Both the tail-recursive append and the symbolic convolution show the expressive power of dataflow variables for sequential functional programming. (Of course, concurrent programming is where dataflow variables really shine. These examples show that they are also useful for sequential programming.)

The naive translation of the functional notation to Alice-ML would have:

   fun append (nil, ys)   = ys
     | append (x::xs, ys) = x::append(xs, ys);
   val x = append([1,2,3], [4,5,6]);
   inspect x;

But this doesn't capture what Oz is actually doing. Instead, you have to thread a promise through as a parameter, just as you did in your procedural code above:

   fun append (nil, ys, p) = Promise.fulfill(p, ys)
     | append (x::xs, ys, p) =
         let
            val px = Promise.promise()
         in
            Promise.fulfill(p, x::(Promise.future px));
            append(xs, ys, px)
         end;
   val p = Promise.promise();
   append([1,2,3], [4,5,6], p);
   inspect (Promise.future p);

Definitely impressed me that in Oz you could express it in the functional style and the compiler would automatically translate it to the more procedural style. Means that you can be operating on the results before the function is completed, if you choose to push the function call to a seperate thread. (Edit Note: Not to mention you get tail recursion for free).

Dataflow variables are very similar to (and a generalization of) unix pipes

I'm not sure we are using "dataflow variable" the same way here, but this doesn't seem right to me.

The ports/streams of message-passing concurrency are generalizations of pipes, but dataflow variables in the CTM sense are monotonic (once a value is set, it can't be taken away) and deterministic (they only have one observable value), which are not properities shared by pipes.

Yeah I was playing a bit fast and loose with terminology, but it wasn't with the idea of a dataflow variable.

Data that goes through a unix pipe is completely untyped/unstructured but in practice a line of text acts in much the same way as a dataflow variable. Lines of text are monotonic, once they go into standard out we are stuck with that value. I think identyfing an analogy between the set of valuations of a given dataflow variable in a non-deterministic language and the lines that pass through a unix pipe is a fairly accurate one.

Consider the following program:

echo "ls" | grep ls | sh

this program will list the current directory and if a line=dataflow var it could correspond roughly to:

echo("ls",Y),grep(Y,"ls",Z),sh(Z,Output)

how about:

ls /bin/ | grep ls | sh

ls("/bin/",Y),grep(Y,"ls",Z),sh(Z,Output)

Here Y aquires a number of valuations all of which then are "piped" through to grep, which kills off a number all but one, and sends it to sh.

Anyhow, that was the correspondence that I was refering to. The generalization is simply the fact that the topology of the flow doesn't have to be totally linear.

----------------------------------------------------
If people never did silly things nothing intelligent would ever get done.
--Ludwig Wittgenstein

I think identyfing an analogy between the set of valuations of a given dataflow variable in a non-deterministic language and the lines that pass through a unix pipe is a fairly accurate one.

I guess I'm still not seeing this one. I can see how you are saying that a stream is like a sequence of single-assignment values.

However, the only access method in this instance is by sequence, whereas dataflow variables have naming.

Are you observing that declarative concurrency with dataflow variables imposes an observed order on evaluation? If so, I'd have to say that is sort of the whole idea.

I was trying to say that each line of text was like one valuation on a single dataflow variable, not that its like a valuation on a sequence of dataflow variables without naming. ie. f(x,y),g(y,z) where y takes on the successive values of each line of output from f. Pipes have naming as well, its just that the names are resticted to identifying the standard output, standard input and standard error.

Yeah, I think this is what I'm observing. Isn't this also the whole idea of monads and arrows? If so, is there a formal connection?

----------------------------------------------------
If people never did silly things nothing intelligent would ever get done.
--Ludwig Wittgenstein

If so, is there a formal connection?

For a more serious account, see From Direct Style to Monadic Style through CPS .