Tacit Programming with Arrows, Hands, and Zippers

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.

Here’s how.

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:

  1. In addition to modifying the environment, we are now free to move within it.
  2. 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.

Navigational Support!

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. 🙂

Advertisements
This entry was posted in Language Design. Bookmark the permalink.

7 Responses to Tacit Programming with Arrows, Hands, and Zippers

  1. CuriousSkeptic says:

    Navigating around a zipper to read and store values. Isn’t that just a Turing machine? I would say that that would be kind of a code smell. Isn’t the goal of better abstractions to avoid directly programming a Turing machine?

    In any case. Could the messing around with stack or tree traversal not be addressed by a more traditional approach such as indexed positions/edges (i.e. Named values and members)?

    • dmbarbour says:

      It’s closer to modeling the act of programming in terms of a programmer’s own story: gather the four mystic artifacts (runtime values and capabilities), compose them into a great spear (block of code), slay the terrible monster (apply), divide the monster’s carcass and distribute its flesh (more runtime values and capabilities). The story as a whole remains type-safe – indeed, the world, inventory, everything is modeled in the type system. A larger story can be effectively broken into reusable parts, so long as the programmer starts with an empty (or standardized) hand each time. If types are precise enough a story can serve as a proof of correctness.

      To program a Turing machine, you’d need to tell a story that describes the construction of a Turing machine…

      I do not believe there is a unique goal for ‘better abstraction’, nor is there an agreed upon ‘better’. But at least one useful goal is to lower burdens on developers. The primary burdens I was addressing in this blog article were gather/scatter data plumbing and extensibility.

      Regarding your third question: yes, names do address problems of data plumbing. Unfortunately, names tend to introduce new problems – such as unbounded recursion, speaking of the dead, or (especially for applications involving heterogeneous elements, such as CPU-GPU or Server-Client) poor use of names can imply inefficient communication patterns that should be explicit. That said, I do intend to model names within a tacit environment, e.g. using `(Static String * x)` and `"foo" lookup` (leveraging compile-time metaprogramming). I believe that I can, by doing so, constrain developers to safe uses of names.

  2. dmbarbour says:

    The number of possible environment models is large. I thought of another promising one, a potential sweet spot between flexibility and simplicity: a list of stacks. Navigation is left/right, and developers are always taking or dropping on the current stack.

    The two hands concept could still work, but devs would mostly use one of them to carry things. Since stacks aren’t extensible, the second hand could be used for modeling extensions of the language’s environment (keyword inventory, static PRNG, etc.)

  3. Pingback: Multi Stack Environment in Awelon | Awelon Blue

  4. Pingback: UI as an Act of Programming | Awelon Blue

  5. Pingback: Command Language for Awelon | Awelon Blue

  6. Pingback: Out of the Tarpit | Awelon Blue

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s