Arrows are a general purpose, highly composable programming model (and the foundation for my Reactive Demand Programming model). Zippers are a mechanism to model a bi-directional cursor in a tree-like structure (including the degenerate case of lists). A hand is a simple augmentation to a cursor: a hand can pick things up, carry them. Tacit programming is a style of programming based on uniform composition and manipulating an environment-of-inputs instead of lambdas or parameters (aka point-free; but also wire-free).
Combine these in one language, and what do you get? A technical summary is: tacit arrow composition using static types, with data plumbing through navigation in a zipper-based environment, with automated navigation support, all at compile-time. A non-technical summary is: Program source code looks somewhat like a plumber’s MOO, moving from one room to another while laying out data pipes.
The resulting system promises to be very intuitive. I believe it worth implementing to discover if this promise is kept.
Tacit programming with Arrows
First, let’s consider how arrows and tacit programming can be combined. Arrows have two essential operations:
(>>>) :: (a ~> b) -> (b ~> c) -> (a ~> c) -- COMPOSITION first :: (a ~> a') -> ((a * b) ~> (a' * b)) -- PARTIAL APPLICATION
In tacit programming, the (>>>) operator would become implicit, i.e. juxtaposition is composition. This is nice; it removes most syntactic noise from our programs. The difficulty is with ‘first’, which takes an explicit parameter. We must eliminate that parameter, for programming to be tacit. For a long time, I never got past that little stumbling block. Then, recently, I realized a simple trick: place the parameter into the environment with a static type (enforcing that the value computable at compile-time), then apply it. The tacit version of `first` thus becomes:
first :: (Static (a ~> a') * (a * b)) ~> (a' * b)
We might conceptualize the type
(a * (b * (c * ...))) as a stack-like environment. With that in mind, we can think of `first` as applying the first element in the stack to the second. The remaining question is: how do we get a `Static (a ~> a’)` value on top of the stack? Existing tacit programming languages have an answer: some way to represent ‘blocks’ of code as first-class values. A block of code can simply be pushed onto the stack like any other literal. Essentially, we treat literals as primitive behaviors:
42 -- e ~> (Static Integer * e) 12.3 -- e ~> (Static Rational * e) "Hello, World" -- e > (Static String * e) [swap] -- e ~> (Static ((a*b)~>(b*a)) * e)
Between first, blocks of code, and a few additional primitives, we can do some awesome work:
first :: (Static (a ~> a') * (a * b)) ~> (a' * b) swap :: (a * b) ~> (b * a) -- PRIMITIVE assocl :: (a * (b * c)) ~> ((a * b) * c) -- PRIMITIVE dup :: a ~> (a * a) -- PRIMITIVE (unless you want linear types) intro1 :: a ~> (Unit * a) -- PRIMITIVE elim1 :: (Unit * a) ~> a -- PRIMITIVE apply :: (Static (x ~> y) * x) ~> y apply = [intro1 swap] second first swap elim1 tail :: (Static (b ~> b') * (a * b) ~> (a * b')) tail = swap [swap] first swap first swap assocr :: ((a * b) * c) ~> (a * (b * c)) assocr = [swap] first swap assocl [swap] first swap second :: (Static (b ~> b') * (a * (b * e))) ~> (a * (b' * e)) second = [first] tail third = [second] tail fourth = [third] tail -- roll will move an element to the top of the stack roll2 :: (a * (b * c)) ~> (b * (a * c)) roll2 = assocl [swap] first assocr roll3 :: (a * (b * (c * d)) ~> (c * (a * (b * d)) roll3 = [rot2] tail rot2 roll4 = [rot3] tail rot2 -- pick will duplicate an element to the top of the stack pick0 :: (a * e) ~> (a * (a * e)) pick0 = [dup] first assocr pick1 :: (a * (b * e)) ~> (b * (a * (b * e))) pick1 = [pick0] tail rot2 pick2 = [pick1] tail rot2 pick3 = [pick2] tail rot2 pick4 = [pick3] tail rot2
Of course, in the context of arrows this ‘stack’ is really just a conceptual representation of the environment type. It is not a runtime entity. Consequently, all this data plumbing can be eliminated at compile-time.
Static Types with Arrows are Awesome
Traditional arrows have a severe expressiveness problem: code of the form `first foo` must specify the behavior `foo` right there, syntactically binding it. Thus, if developers want to create a variation of this arrow that uses something other than `foo`, they must either re-implement the entire context containing `foo`, or use an orthogonal construction layer (e.g. lambda substitution).
With static types, this expressiveness problem immediately goes away: developers can separate the code constructing a static behavior from the code applying it without leaving the arrows model. One can even construct a static behavior from smaller pieces using a `compose` primitive for static blocks.
But there is a price: arrows with static apply are Turing complete, much like monads, or arrows with dynamic apply. It can be difficult to reason about them.
[copy apply] [copy apply] apply OR (\x.(x x) \x.(x x))
This could be prevented in a number of effective but inelegant ways (e.g. modeling code-size expansion quotas, or depth limits), or we could just live with it as the price for greater expressiveness and compositionality. As it happens, my RDP model has the same issue with dynamic behaviors. I’m still thinking about how and whether I want to address this concern.
Static types can feasibly be used for a wide variety of compile-time computations:
- ad-hoc compile-time parameters and processing
- load external resources (e.g. files as strings) at compile time
- value dependent types and decisions
Of course, static computation is possible even without arrows. But arrows have an advantage of cleanly separating the static and runtime behaviors, even when they are deeply interwoven in the source code. Basically, developers gain all the features of macros and staged programming (even multi-stage; see below), with none of the nastiness – no quote, no unquote, lack of hygiene is a non-problem because we don’t use variables, etc..
Loading a static value into the runtime becomes precise, meaningful operation, i.e. something like: `
lowerStatic :: Static x ~> Runtime x` in a typical paradigm. Though, for RDP, I need something closer to: `
const :: (Representation p x) => (Static x * Signal p ()) ~> Signal p x` where ‘p’ describes heterogeneous locations in space-time (e.g. a CPU, GPU, client, or server) and ‘Representation’ ensures that ‘x’ is a type supported by ‘p’ (e.g. GPUs might not support ad-hoc strings or trees).
From Stacks to Zippers
Stacks are sufficient for ad-hoc environment manipulation. But in many ways, stacks are fragile and awkward. Stacks are awkward due to cleanup issues: developers are forever manipulating the stack to get the essential arguments to the top, then carefully restoring the stack to its original shape but with a few modified inputs. Stacks are fragile to extension – e.g. with respect to annotations and optional parameters.
Arrows greatly mitigate the issues with stacks. First, since the stack is a compile-time-only entity, developers don’t need to worry about the ‘cost’ of swaps, rotates, etc.. Second, the types in the stack are not limited: in `
(a * (b * (c * ...)))` each of a, b, and c may be arbitrarily complex, even themselves be stacks. Third, derived behaviors such as `second` and `third` allow partial applications without first rotating elements to the top.
Nonetheless, I still felt the pain of those cleanup and extension issues. Not immediately. But typeful models of keyword and optional arguments, magnetic auto-wiring, signposts, and so on proved to be very awkward and required way too much foresight. (Yeah, I’m one of those idiots who learned about C++ templates and immediately found a hundred ways to abuse them.)
By switching from a stack to a zipper, developers gain two potentially useful degrees of freedom:
- In addition to modifying the environment, we are now free to move within it.
- The environment can have a more ad-hoc and extensible structure, such as a tree.
Now, for ultimate extensibility, my dream environment is a tree where each node can have a finite, unbounded number of children. But let’s take this one step at a time. First, let’s consider the simple case of modeling an environment as a list zipper. A list zipper looks very much like a pair of stacks, with our cursor being in the middle (having no particular value). I.e. we’re in the middle of middle, our type will look like `
((d * (i * (m * Unit))) * (d * (l * (e * Unit)))`.
Modeling operations on the environment is easy enough, but to really switch to a new environment we need to consider the various programming idioms… e.g. we’ll want a new version for `first`, and a new model for inserting literals.
-- List Zipper looks like (LHS * RHS), with us in between. -- Empty List Zipper is (Unit * Unit) -- NAVIGATION: trivial! only two directions to travel stepLeft :: ((a * lhs) * rhs) ~> (lhs * (a * rhs)) stepRight :: (lhs * (b * rhs)) ~> ((b * lhs) * rhs) stepLeft = [swap] first assocr stepRight = assocl [swap] first -- LITERALS: add these to the left hand side. If I write `10 11 12` -- from left to right, it makes sense that I can stepLeft afterwards. 42 -- (lhs * rhs) ~> ((Static Integer * lhs) * rhs) 12.3 -- (lhs * rhs) ~> ((Static Rational * lhs) * rhs) "Hello, World" -- (lhs * rhs) ~> ((Static String * lhs) * rhs) [swap] -- (lhs * rhs) ~> ((Static ((a*b)~>(b*a)) * lhs) * rhs) -- PARTIAL APPLICATION: what is the intuition here? What should the -- syntax look like? Maybe want a couple common case ops: -- apl: write a function then apply it to the element on our left -- apr: write a function then apply it to the element on our right apl :: ((Static (x ~> y) * (x * lhs)) * rhs) ~> ((y * lhs) * rhs) apr :: ((Static (x ~> y) * lhs) * (x * rhs) ~> (lhs * (y * rhs)) apl = [first] onLeft apr = stepLeft [first] onRight onLeft = first -- exec stack-like ops on left onRight = tail -- exec stack-like ops on right
It should also be obvious that we haven’t really gained much using a simple list zipper! There was no improvement to extensibility. Also, while developers can plod around and nudge things, but they’ll be right back to stack manipulation (onLeft or onRight) to get useful work done. Me? I blame the lack of hands. Our poor developers are more like code turtles than code monkeys.
To achieve extensibility let’s take the next step for our environment type: trees! If you aren’t familiar with XML, or JSON, or OOP, or… well, modern programming, you might ask: how do trees offer extensibility?
Glad you asked! Let’s say I write a number – 42. Now, I might want to annotate that number with a description: “A possible answer to the life, the universe, and everything.” If I’m stuck with a list, I would only have a few options: I can put this description to the left or right of the number, or I could replace 42 with a complex type like `(42 * (“description” * “life, universe, everything”))`. But in both cases, something breaks: the environment, or the consumers expecting an integer. However, if values are always the root of a tree with unlimited extensions, recursively… then I’m free to add my description.
So… we need a tree-zipper, where each node has a value… modeled using simple `*` types so we don’t forget our, um, roots. Sounds a little intimidating? Nothing to do but try!
-- node: (val * listOfChildren) -- nodeZipper: (childZipper * (nodeVal * parent)) -- childZipper: (lhs * rhs) -- parent: either Unit or nodeZipper (recursively) -- NAVIGATION: FREEDOM! -- Now we have a nice 2D world: up, down, left, right. nodeLeft :: ( ((a * lhs) * rhs) * nvp ) ~> ( (lhs * (a * rhs)) * nvp ) nodeRight :: ( (lhs * (a * rhs)) * nvp ) ~> ( ((a * lhs) * rhs) * nvp ) nodeDown :: ((lhs * ((c*gc) * rhs)) * nvp) ~> (gc * (c * ((lhs * rhs) * nvp))) nodeUp :: (gc * (c * ((lhs * rhs) * nvp))) ~> ((lhs * ((c * gc) * rhs)) * nvp) nodeLeft = [stepLeft] first nodeRight = [stepRight] first nodeUp = [rot2] first assocr [swap] first assocr nodeDown = assocl [swap] first assocl [rot2] first -- a few utility operations sibLeft = nodeUp nodeLeft nodeDown sibRight = nodeUp nodeRight nodeDown -- LITERALS: Hmmm. So much freedom. Maybe too much. Where should we add these? -- Perhaps just write them into the current node, much like we did before? -- We add a (Unit*Unit) empty child list to each, and we ignore the parent. 42 -- ((lhs * rhs) * nvp) ~> ((((Static Integer*(Unit*Unit))) * lhs) * rhs) * nvp) 12.3 -- ((lhs * rhs) * nvp) ~> ((((Static Rational*(Unit*Unit)) * lhs) * rhs) * nvp) "Hello, World" -- ((lhs * rhs) * nvp) ~> ((((Static String*(Unit*Unit)) * lhs) * rhs) * nvp) [swap] -- ((lhs * rhs) * nvp) ~> ((((Static ((a*b)~>(b*a))*(Unit*Unit)) * lhs) * rhs) * nvp)
Woah, those types are getting ugly! Fortunately, I’m not actually expecting developers to write types in their source code. Developers will work more in terms of the concepts of navigation, structure, and manipulation.
Freedom of motion has its cost: there’s now a risk of getting lost! (I’ll return to the issue of navigational support, later.)
A potentially alarming decision is maintaining the ziplist “navigation state” within each child node. This is preventable, i.e. I could instead force developers to `nodeLeft` until they hit a wall before executing `nodeUp`. However, I made this decision because it fits the intuition of stepping away from an object (e.g. to grab a value from elsewhere) then returning to it and getting some work done.
Hands are Great! OR Monkeys make better programmers than Turtles!
Developers benefit from a SIMPLE conceptual model for manipulating their environment, which means they should just need a few verbs. With stacks, it was pretty much `pick`, `roll`, and `first` – easy to express. Of course, the developer’s burden was instead shifted to keeping that stack in order. But the manipulations were easy to remember, and that matters! In the ‘upgraded’, navigable environments, there are too many possible environment manipulations; I don’t even know where to start.
That’s where hands (or a user-model/avatar, in a sense) come in! Instead of rearranging the typeful fabric of reality to get elements into close enough proximity to combine them, developers are able to pick up an object, carry it someplace, and apply or place it. Using hands, the manipulation verbs are simple: go grab or copy what you need, go back and place or apply it. Done. Of course, our manipulations may still be very complicated… but now they’re expressed in step-by-step terms humans can grok.
In context of Reactive Demand Programming, these ‘objects’ developers would be picking up include both static values and runtime signals. The idea of picking up a runtime signal and wandering around with it might be intuitively likened to grabbing one end of a hose – albeit, without the traditional physical difficulties like weight and entanglement with bushes.
So how should we model our hands? How much flexibility – and complexity – do we want with ‘inventory management’? Initially I favored modeling hands as another full environment (and an earlier version of the article reflected this) but after some time thinking about it, I want my hands to be simpler than my environment. So instead of using a full environment, I’ll use a pair of stacks (i.e. a list zipper).
Supporting the intuition of hands, the concept of ‘two hands’ is effectively built right in: (leftHand*rightHand). The active object or tool in each hand would simply be the top element. Developers could model flexible extensions to this concept – e.g. modeling a purse, a tool belt, a key chain – using the extra space deeper in the stacks. One might think of the deeper stack for each hand as ‘pockets’.
Awesome. Now it’s easy to think of basic manipulations:
- world-to-hand manipulations: copy, take
- hand-to-world manipulations: paste, put, apply a block to a node value, or to the world
- hand-to-hand manipulations: compose, apply between hands, swap, passing objects, drop/destroy
I think implementing these would not be problematic. Mind, it’s a lot of data plumbing and I don’t feel like writing it right now, but we ultimately just have a (world*hands) pair subject to the normal assoc/swap/etc. operations.
Literals, I imagine, would be created in the right hand. By default. I can think of scenarios where I might wish to list several literals in source and apply a uniform action to each, and I’d rather not need to write `
10 action 11 action 12 action` so I’m thinking about ways to control how literals enter the environment. (The idea of equipping a ‘literal brush’ is a bad idea – might forget which brush we carry. Some sort of vector/matrix type, plus support for static foreach, might do the job.)
When developers apply a subprogram to the world, that subprogram should not impact (nor be impacted by) the programmer’s current hand. The intuition here is that the programmer is installing an independent software component that will operate without further intervention. All inputs for that subprogram must be introduced explicitly. If a subprogram uses the hands/zippers concept, it should start with empty hands. This constraint has some nice properties. Reuse is easier, because many subprograms will not depend on the hand. It makes it much easier to reason about what resources a program might access. If the programming system also uses the object capability model to distribute authority, most of that authority can be held by the programmer (almost literally) and only selectively embedded in applied behaviors.
Anyhow, lots of questions remain for how the programming experience should be refined and the standard vocabulary developed. But I think this is still a very promising basis for in-the-large tacit programming.
Lost… in a maze of twisty little passages, all alike. Can we avoid this?
I have one more crazy idea to offer: as we navigate through our world, we might automatically construct a static subprogram that will move us back to where we were – e.g. to an anchor. Alternatively, we might extend our environment with signs or labels, such that we can perform a static search for how to reach them.
Constructing a program to go back sounds fragile, since the type of the world may have changed since then. But some ability to drop labels or ‘unique’ anchors in the type system and automatically construct a navigational program to reach them is very feasible (assuming sufficient support for reflection and typeful meta-programming).
In addition to mitigating risk of getting lost, I believe dropping a few anchors and teleporting between them might be a convenient way to get certain kinds of work done.
Yeah, it’s essentially a ‘goto’. However, I think it will be less of a problem for such static operations. 🙂