Vertical Composition

I've been thinking lately about designing a pure concatenative language influenced by Haskell to explore an idea I have about concatenative programs as diagrams. It would involve investigating how monads would work out in this type of language, as well as optimization and reasoning in terms of diagrams. I would probably try embedding it in Haskell and perhaps one day compiled to C. As part of this I've noticed an operator that I haven't seen in any concatenative languages (not even Factor, with all its awesome combinators) but seems like it might be useful. I call this operators "vertical composition".

Vertical composition is similar to the product of functions- if f:a->b and g:c->d then fxg : axc -> bxd (also written as fxg : (a,c) -> (b,d)). If these functions effect the stack, then their usual composition (which I'm calling horizontal composition and is written for f:a->b and g:b->c as g.f:a->c or f;g:a->c) creates a function that performs the the first function, and then the second. This means that the composition is valid if the stack after the first operator is a valid input to the second (possible requiring extra items deeper in the stack then the first function used). Vertical composition, on the other hand, is always valid just as the pointwise action of a pair of functions is always valid. Instead of operating sequentially, vertical composition acts in parallel (at least, conceptually) by performing the first function on the part of the stack that it needs, and the second function on the part of the stack just under that part used by the first function. The resulting stack is the result of the first function followed by the result of the second. I will write vertical composition as f|g, though I'm considering f/g, so we pronounce it "f over g". I will try to clarify this below, but the point is that you can reach under part of the stack without rearranging it. This would involve some amount of rearranging to arrange so the stack ends up with no "holes" where, for example, if f has stack effect ( a b - ) and g has stack effect ( c - c ) then f|g has stack effect ( a b c - c ). This would mean that the value c should be two places lower after f|g, which can't be known beforehand in a language like forth. If implemented naively as a stack this is a problem but the diagrams I mentioned earlier should remove any overhead of that kind. I hope to post about this strategy soon.

Something interesting about this operator is that the operations it composes could be performed in parallel. This isn't something I expect to see, but it is interesting that the horizontal form of composition is sequential and the vertical form is parallel.

Note that the vertical composition has the empty word as its identity and is associative, just like horizontal composition.

So, this operator is definable. Is it useful? I will write about that in a future post. The point is that this is the first step to a postfix program as a diagram.