Tree Versus DAG Bindings

Qi is an interesting, flow-oriented programming language. It has a very tacit vibe. But still - sometimes it is useful to bind values to named identifiers. And with certain flow forms you end up with strange binding scopes.

Long, long time ago when AWK and Perl were used for creating most of the real world programs the implicit variable $_ ruled the world. But using implicit arguments does not need to happen only in these horrible write-only programming languages. In a flow-oriented programming language the implicit passing of values between flow steps is - of course - way nicer. Take a simple flow as an example:

#lang racket
(require qi)
(~>> (10) range (filter odd?) (map sqr) (foldl + 0))

And its result: 165.

A brief explanation would be as follows. An implicit right-threading flow is created and fed with one input value of 10. A range form is applied to create a list of numbers from 0 to 9, then the odd values are filtered, the results squared and summed together.

It is also easy even with bindings although this example is rather artificial:

#lang racket
(require qi)
(~>> (10) range (filter odd?) (map sqr) (foldl + 0) (as res) (gen 1) (+ res))

With the result being 166.

The binding is a bit redundant here but it is easy to see how the bindings are supposed to work. And they do actually work. On a side note, if we also required qi/list this flow would also get deforested.

Some complex flows are a bit different. See the documentation for the tee form to get the idea how the following works:

#lang racket
(require qi)
(~>> (10)
     (tee (~>> range (filter odd?) (map sqr) (foldl + 0))
          (~>> range (filter even?) (map sqr) (foldl + 0))))

We recieve two results: 165 and 120.

Technically speaking it would be nice if it was possible for the two branches of tee to be evaluated in parallel. But before we get to the core of the problem why it is not possible right now, here is how the bindings might be used in this example:

#lang racket
(require qi)
(~>> (10)
     (tee (~>> range (filter odd?) (map sqr) (foldl + 0) (as res1))
          (~>> range (filter even?) (map sqr) (foldl + 0) (as res2)))
     (gen res1 res2))

The bindings seem to resemble a let form, however they behave like a let* form, which allows for usage as the one seen in the following example:

#lang racket
(require qi)
(~>> (10)
     (tee (~>> range (filter odd?) (map sqr) (foldl + 0) (as res1))
          (~>> range (filter even?) (map sqr) (foldl + res1) (as res2)))
     (gen res1 res2))

With more interesting results of 165 and 285.

But that means there is an implicity dependency of the second branch on the first and therefore they cannot be - in general - computed in parallel, because the lexical scoping forms a pretty strict tree.

Not even a branching tree, it is so linear that we only see a linked list here.

Without the implied dependency it would not be possible to use bindings from the first branch in the second. On the other hand it shoult be possible then to compute the results of both branches in parallel. The explicit dependency forbids that the same way as the implicit one does:

How do we achieve that? If it was possible to specify lexical scoping rules as Directed Acyclic Graph (DAG), it would do the trick easily. Without the possibility of explicit dependency and no implicit dependency in place, both branches become lexically independent:

As we can see, both branches bind a new identifier to some value and downstream (in Qi terminology) the bindings are available without further ado. The open question remains: how do we do that? And if you want to find out, be sure to follow the latest news from the Qi Development Meetings.

A slightly different thought than usual but still with hopes you liked it. See ya next time for more!