Today data-flow diagrams are something every CS student and programmer has seen. It is a nice way of visualizing the general flow of data through an application. But it is rarely more than that. A few reasons for this might be an inconvenience in displaying details. They tend to get big!
Another problem is the rather limited language which is incapable of describing some fundamental ideas of CS like lambda functions. Would you know how to draw a lambda function in a data-flow diagram? If you ever heard of string diagrams, you might be able to do so, but most programmers wouldn't recognize them.
I myself adore data-flow diagrams and I'm fascinated by what you can do with them even in an functional setting. That's why I want to show you, how you can build lambda functions in a data-flow diagram in a functional way and what this has to do with time machines. But first lets start with some simple examples to get used to functional data-flow diagrams. Here we have a rather simple one.
/‾‾‾‾‾‾‾\
| input |
\_______/
|
|
/‾‾‾‾‾‾‾‾\
| output |
\________/
I hope this one fits your intuition of a data-flow diagram. It takes some input and feeds it directly to the output. Rather simple idea, but there is already a problem... This diagram is not functional: input and output processing is perhaps something for another post so we will leave those out of the diagram and only draw real functions like this identity diagram here:
|
|
|
Here we only have one wire. It transports one value from the top to the bottom. Here is another diagram:
|
/‾‾‾‾‾\ #
| 4 |
\_____/
|
|
In this diagram we discard the incoming value (discarding is done with #) and always send 4 down the wire. We will not talk about what exactly the box with the 4 is, we will take it as a given that we can somehow create numbers (even if there is more to it than you might think).
Now we want to play a bit with our values
|
/‾‾‾‾‾\ |
| 4 | |
\_____/ /
| /
| /
/‾‾‾‾‾‾‾‾\
| + |
\________/
|
Here we take a value and add 4 to it. This might confuse some of you as we have a box with a 4 which is a constant and another box with a + which is a function that takes two arguments. For now lets not think too much about it, you could imagine that the 4 is a constant function that outputs the value 4. To avoid drawing to many boxes that take up a lot of space I will draw those functions without a border like this:
|
( 4 ) |
| /
| /
| /
\ /
( + )
|
Then we have some rather obvious identities, but I want to spell them out as they are not true for everything (but luckily for our data-flow diagrams). We have the following identities.
\ / \ /
\ / \ /
\ / \ /
/ = \
/ \ / \
/ \ / \
f | | | | |
| g = f g = | g
| | | | f |
Crossing wires is valid and it does not matter which wire is on top. And the location of functions on a path does not matter as long, as the order of functions on any individual path does not change. The following example shows an inequality where a function surpasses another one on a specific path:
f | h |
| g != | g
h | f |
The function g is isolated in this example and it does not matter if it is before or after any of the parallel functions. But in general f cannot change positions with h. Now lets do something weird:
|
| /‾\
| / |
\_/ |
|
Okay.. If you should guess, what is meant by this, you probably would guess correctly.. it is simply the identity diagram written differently with some wiggles. Now we could ask ourselves, what down means in those diagrams. Somehow down seemed to be the direction in which data flows, but then we would get into trouble with the previous example.
Well Let's look at a rather normal data flow diagram with a loop.
|
|<----|
(- 1) |
| | yes
(> 0)----
|
| no
|
You might have seen something similar. The yes branch goes up in the data flow diagram. This is rather common in a day-to-day data-flow diagram and it seems rather natural to do so. But there are some caveats to this method. If we want to have functional data-flow diagrams we should never use a wire twice for one input (at least not until we undestand the necessary conditions to get sane behaviour). In the above example, if we had one incoming value, we would have exactly one or zero outgoing values and usually many rounds through the yes branch. We do not want that, it makes reasoning about it much harder and introduces some form of hidden state, as we have to keep track of the origins of each data field that goes through a wire.
To clarify let's look at the following example:
|
(< 6)
yes| |no
( * )
|
What do you think would happen in this data-flow diagram? We have an operation * that awaits two inputs. But we have two branches and only one would get data. This diagram would either introduce some form of Queue to store values (and thus requires some form of state) or it would be an invalid data-flow diagram. Both situations are quite bad. If we introduce state we would loose a lot of power in reasoning and increase the cognitive load to understand the diagram. If we would say, that the diagram is invalid we would loose a really neat property... composability.
Okay.. I never told you, that we have some form of composability, but we somehow took it for granted, that we can connect stuff. I must admit, that it is not that easy, but it is close. We have to respect the data types and the number of wires. We all would expect that the string values "a" and "b" are no valid inputs for *.
As a result we will not allow conditional branching! And with that loops become kinda senseless as there is no way of escaping them. I will address this issue probably in another post where I will introduce the Y-Combinator and some functor abstractions to enable the use of the Y-Combinator in data-flow diagrams.
Before we get to lambda functions, let's think about how to interpret a data-flow diagram with no loops. If we look at this example:
| |
f |
| g
\ /
h
|
We could transform this into code that could look like the following pseudo code.
function diagram (in1, in2) {
afterF = f(in1)
afterG = g(in2)
return h(afterF, afterG)
}Here you can see, that I used exactly the ordering given in the diagram. So the data-flow diagram somehow encodes information about what comes before what. If you want, you can interpret going downward as passing time and stuff that is horizontally next to each other is concurrent. If we now look again at the wiggly example:
|
| /‾\
\_/ |
|
We could extend it a bit like this:
|
| /‾\
f | g
\_/ |
|
As mentioned earlier, this is equivalent to the straightened out version where g is below f. But in this example f and g are concurrent. Well this is impossible, as g needs the output of f to do anything, unless the upward wire (in the wiggly part) would send the data back in time.
Hmm.. I hear some people frowning, that this is rather senseless. "Why would you ever add u-turns there..". Well I feel you, but we didn't speak about abstractions yet. In lambda-calculus you can create lambda functions and pass them around (nothing fancy). But you usually pass the function around without really knowing what it does (locally) and you usually do not care. If you want to know, what it does.. you have to look into the function, but as long as you pass it around it is treated like data (obviously I'm only speaking about languages where functions are first class citizens). Not-caring about the inner workings of a lambda function is called lambda abstraction and abstractions are exactly the concept I'm going for. Here is some pseudo-code for you:
function doubledArg(x, fn) {
return fn( 2 * x )
}
identity = (x) => x
doubledArg(4, identity)This function takes a value and a function and plugs the doubled value into the given function. After this the function is called with 4 and the identity function. Okay let's draw some diagrams.
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾‾\ /‾‾‾‾‾‾‾‾‾‾‾|‾‾\
|doubledArg | 2 | | |identity | |
| \ / | | | | |
| ( * ) | | \___________|__/
| \ / |
| apply |
| | |
\__________________|____/
This is how you could think of the two functions display in pseudo-code above. But now we have an apply and really don't know how to plug the identity function as an input into the doubledArg function. The wire in the identity function is the value x and not the function! This notation is in a way problematic, we are unable to distinguish between the function and the values of the function.
Before we get to the answer let's have a look at the parts. First the apply. If we think about what happens when apply receives a function like identity it should be rather obvious... Well it will simply plug the value into the function. That is the same thing as putting the diagram for identity where apply is located. Then we would get something like this in doubledArg:
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾‾\
|doubledArg | 2 | |
| \ / | |
| ( * ) | |
| \ # |
| \ |
| | |
\__________________|____/
Okay.. that is what happens, but now we have a disconnected path there. This is strange (and in fact we don't really want to change the topology here ;) ). But essentially this is, what happens when we apply an value to a function. Now we need to think about those wires. If we think about a function definition like identity = (x) => x we only know that, when it takes a value, it will return something. But the definition is usually done before applying values. Earlier I said "time passes when going down in the data-flow diagram", so the input and output come after the function definition and so you could say, input and output must be below the function. Let's try defining the identity diagram in this way.
/‾‾‾‾‾‾‾‾‾‾‾‾‾‾\
|identity |
| /‾\ |
| | | |
\________↑___↓_/
Here we have a diagram for identity that has two wires on the bottom and none above it. So it does not depend on any input, that seems plausible for the identity function, it always does the same thing. Then we have a u-turn inside the identity diagram and one part of the wire is going up (the input) and the other part is going down, out of the box (the output). For now, let's try to see what happens if we use this identity definition in our doubledArg example.
/‾‾‾‾‾‾‾‾‾‾‾‾‾‾\
|identity |
| /‾\ |
| | | |
\________↑___↓_/
| /
| |
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾|‾‾\
|doubledArg | 2 | | |
| \ / | | |
| ( * ) | | |
| \ | | |
| (apply) |
| | |
\___________________|_____/
Now we all of a sudden have two wires going into apply, but one is going up, the other one is going down. Perhaps we now can do better than before. Well simply disconnecting the function input from the apply and pasting the identity diagram will not really work in this setup, as our identity diagram looks kinda different now. Well if we think of all possible ways to connect the apply part of the diagram, there are essentially two ways of doing it now (if we try to respect the orientation of the wires). We now have either:
↓ ↑ ↓ ↓ ↑ ↓
( apply ) = \ \_/
↓ result ↓ result
Or
↓ ↑ ↓ ↓ ↑ ↓
( apply ) = \_/ /
↓ result ↓ result
Where we simply loop the function and pass the argument to the output. Or send the argument up and let the other wire through. Funny thing is: both would produce the right result in our case, but only because we have the identity function as one of our inputs. For any other function, only the second one is appropiate. Let's plug our apply into our doubledArg function and see what happens.
/‾‾‾‾‾‾‾‾‾‾‾‾‾‾\
|identity |
| /‾\ |
| | | |
\________↑___↓_/
| /
| |
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾|‾‾\
|doubledArg | 2 | | |
| \ / | | |
| ( * ) | | |
| \__/ | |
| / |
| / |
\___________________|_____/
Now if we remove the boundary around the identity diagram and move the u-turn inside the doubledArg we get.
/‾\
| |
↑ ↓
| /
| |
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾|‾‾\
|doubledArg | 2 | | |
| \ / | | |
| ( * ) | | |
| \__/ | |
| / |
| / |
\___________________|_____/
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾‾‾‾‾‾\
|doubledArg* | 2 /‾\ |
| \ / | | |
| ( * ) ↑ ↓ |
| \__/ | |
| / |
| / |
\___________________|_____/
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾‾‾‾‾‾\
|doubledArg* | 2 |
| \ / |
| ( * ) |
| \ |
| \ |
| \ |
\___________________|_____/
Well that looks nice. This is exactly what we wanted and apply is nothing special now. It simply connects input and output wires (and our function is nothing special too). Let's use another function instead of identity and do the same thing:
/‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾\
|lambda |
| /‾\ |
| | ( f ) |
\________↑___↓___/
| /
| |
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾|‾‾\
|doubledArg | 2 | | |
| \ / | | |
| ( * ) | | |
| \__/ | |
| / |
| / |
\___________________|_____/
Here we have a lambda function that applies the function f to the input. Now lets transform it.
/‾\
| ( f )
↑ ↓
| /
| |
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾|‾|‾‾\
|doubledArg | 2 | | |
| \ / | | |
| ( * ) | | |
| \__/ | |
| / |
| / |
\___________________|_____/
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾‾‾‾‾‾\
|doubledArg* | 2 /‾\ |
| \ / |(f) |
| ( * ) ↑ ↓ |
| \__/ | |
| / |
| / |
\___________________|_____/
/‾‾‾‾‾‾‾‾‾‾‾‾‾|‾‾‾‾‾‾‾‾‾‾‾\
|doubledArg* | 2 |
| \ / |
| ( * ) |
| \ |
| ( f ) |
| \ |
\___________________|_____/
Yeah, perfect. It pulls the function down and we have plugged the lambda function into the place where apply was. This would not happen if we choose the looping apply implementation.
So, if you want to define a function in a data-flow diagram, you take the inputs from the future (upwards wire), apply some operations to it and send the value back to the future where the input came from. If that does not sound like a time machine you should watch more old movies ;).
Special thanks to Benjamin B. who wrote an excellent article about monoidal categories and string diagrams on his page (sadly it is only available in German). Without him, I wouldn't be able to write this article. You should definitely check out his stuff (and if you cannot read German, try google translate :) ).