Live 2D Compositional Programming

Introduction

This system started out as an experiment in making an obtuse programming paradigm more approachable. Sometimes regarded as "write-only languages", stack-based concatenative languages rely on implicit argument passing and return values, with programs often just a bare sequence of function names, but they provide a very concise expression of pipelines.

A two-dimensional layout showing both the functions and the corresponding values on the stack could help to make clear where values are coming from and going. Having built it, though, it turned out to naturally express programs outside of that paradigm as well—and perhaps more usefully. In fact, artificial restrictions were necessary to ensure that programs did remain concatenative, while the non-concatenative constructions had clear meaning.

This system lends itself to live editing of a program and displaying intermediate (and final) values throughout, and to exposing exactly the operations that are available at any given time. The following sections will discuss the background, demonstrate usage, explore what can be done with it, and divert to investigating the uncovered semantics of the language.

Compositional Programming

Concatenative languages are those taking two programs and appending them together forms a new program, performing the operation of one on the results of the other. This operation is composition, and is exactly analogous to composition of mathematical functions, or to composition operators in functional languages like Haskell. In fact, concatenative languages can be analysed as functional languages where the default (juxtaposition) operation is function composition, rather than application (as in Haskell).

Many concatenative languages are stack-based (e.g. Forth, Joy, Factor), passing arguments and return values implicitly between functions, though there are non-stack-based languages as well; we (largely) do not deal with those here. The Concatenative wiki lists and provides information about a number of concatenative languages.

Composing sequences of (sub)programs into larger programs is also analogous to Unix pipelines, and composition can be a core operation without being strictly concatenative. One useful feature that these languages tend to have is the ability for functions to have multiple return values, and send some of them on for further processing. This particular aspect of compositional programming is key in what this system does.

The next section will discuss the origins of this system in trying to support concatenative programming, before relaxing that requirement and exploring what else can be done with it.

Origins

The original motivation for this system was to provide a more approachable way to read and write concatenative programs. Concatenative languages are sometimes seen as "write-only", because reading unknown code often requires simulating the parameter-passing stack mentally for each function, and knowing at least the arities of every function involved.

This two-dimensional notation can represent any of these concatenative programs with all arguments and return values explicitly manifest in the display: each function cell is laid out directly below its arguments, and stretched above its return values. The grid thus alternates row-by-row between functions and values. A linear concatenative program can be rendered directly into the grid:

Either the types or concrete values can be displayed for the argument/return values. Similarly, it is possible to linearise a program back into conventional textual form.

This notation permits editing the programs as well: Because adjacent stack elements are side-by-side, a single drag can select arguments to give to a function, and a menu of available functions that can consume those arguments offered to select from. If the values are not in the right order, the option to swap is always available.

However, for purely concatenative use there is one further limitation: the rightmost argument chosen must be the rightmost output of another function, in order for these values ever to be on top of the stack together.

Relaxing this rule results in programs that do not correspond to typical concatenative programs, but which still have clear meaning: each function consumes the values from above, and produces the values below, and only lacks the ability to turn into a — fairly inscrutable — textual concatenative program. This relaxed non-linearisable system is what we are interested in here, as it provides a number of convenient features for live and exploratory programming, despite an execution model that is quite strange in conventional terms.

Live Programming

The interface allows displaying either the types accepted/produced by each function, or the concrete values of the arguments/returns. In the latter case, true live programming is available: the user can select a value, or a series of consecutive values, and choose the operation to process it or to combine them, and the result is also displayed.

Working in this way, available operands are always visible and tangible. This is useful both for manipulation, and potentially for the display itself, which may be the purpose of the program in the first place. At any point the user can stop, and has a program that calculates and displays some values.

This representation also shows the provenance of the results innately: all of the precursor steps, and precursor values, are explicitly part of the display.

High-level Data Types

Examples so far have used primitive types, but arbitrary values could be displayed for the user to work with, including compound types or images. Displaying these higher-level types may again be the purpose, but also provides the opportunity for further affordances.

Exploratory Programming

Because all available values are always visible, the user can engage in undirected exploration of the program space. Selecting a value, or range of values, and seeing what functions can be applied to them, enables discovering available pathways to experiment with.

A function can be chosen, its results seen, and then be either continued with, or reverted. Any function can also be replaced in-place with another of the same type proferred from the menu.

The nullary functions for literals are also editable live, so that a numeric or string constant can be experimentally replaced and the impact on the program seen.

Comments

The grid structure opens up an interesting possibility for comments: the user can select a range of cells, and add a comment to them. These need not cover the entire row, and can be applied to only particular values rather than functions, lines, or blocks. Of course, it is still possible to select the entire row to comment, but additional flexibility is provided.

Working with Functions

So far we have looked only at building a whole program at once out of built-in functions, but user-defined functions can work in the same way.

Another option provided when choosing a sequence of arguments is to create a new function that could accept them. This function will be in a new tab, with the chosen parameter types set out across the top, and all the usual affordances available as well. The values left over at the end of the function will be what it returns, and the function can be used anywhere that those parameter types are available.

As in concatenative programming, abstracting sequences of operations to named functions of their own is encouraged, to keep the program clear and comprehensible. In this system in particular, the sheer amount of space taken up by the grid layout provides added incentive.

Lifting Functions

This environment provides no looping constructs, and not (so far) higher-order functions. Given a list of values, there is thus no way to apply some operation across the list (neither a map nor a fold).

Instead, user-defined functions have a "lifting" configuration option, accessible in their sidebar. These liftings, in effect, wrap the function in a higher-order operation: the "Mappable" lifting applies the Functor map operation to it, for example.

A Mappable function that takes in a single string and returns a single int can be applied to a list of strings, a set of strings, or an optional of string, and will return the same wrapper type with the produced int value(s) inside. Similarly, a Foldable function that takes in an integer and a string can be applied to a list of strings and an integer initial value (in the opposite order for compositional convenience). This appproach provides the power of common higher-order functions without needing users to understand that sort of abstraction, and without requiring a more complex "syntax".

Additional higher-order operations are possible, but it is likely that at some point they introduce too much complexity to the type system and user interface. So far, the system does not support first-class functions themselves, but they may be appropriate for a future version.

Identifying Inputs and Outputs

For functions with multiple inputs or outputs, it is not always obvious which order these will be in. To make this easier, some functions have a label configured for each argument and return value position, which is displayed within the cell of the corresponding value, as smaller text above the value or type for a return value label, and below for a label given by the function consuming the value.

These annotations are quite noisy and it is not clear that they are always advantageous, but the current implementation includes them for arithmetic functions, built-in functions with many arguments, and accessors for record types.

The user can also apply one of these labels to any stack value using a special @label function. A manual label may be just a note for the programmer, but will also be carried through as a label for a return value of a user-defined function, and is preserved by operations such as swap and dup.

Language Semantics

While stack-based concatenative programs are expressible in this system, the non-linearisable programs have an unusual execution model that would be difficult to express in a conventional textual language. We describe two ways of analysing the execution of programs in this model, but neither is notably useful; the visible vertical dataflow should be the primary understanding of the approach, and we identify these here for completeness only.

There is a linearisable representation of the semantics, but it is queue-based rather than stack-based. Functions shift their arguments from the queue and push their return values onto it, and are executed in order left-to-right row-by-row. The "empty" function cells where values span multiple rows are represented by the identity function in this linearisation, so the pushes and pulls will add up but corresponding operations will virtually always be distant from each other.

It can also be analysed as each row defining a function performing the operations of all its cells, from a tuple of arguments to a tuple of outputs to be consumed by the next row.

In either case, this is still actually concatenative: a program that transforms A B to C D can be concatenated with one transforming C D to E F to get a program that transforms A B to E F. In terms of the 2D representation, this concatenativity is row-by-row—cutting off the final rows of a program results in a new program that consumes the outputs of the first. However, the value of this fact is limited and the direct argument-function-outputs mapping represented by the grid layout is always likely to be most useful.

Inspirations

A significant inspiration for this work was Userland, a grid-structured dataflow programming environment. Userland's approach to shell pipelines in particular, where consecutive stages of the pipeline were laid out horizontally, the standard output of each phase below, showed a path for this sort of composition.

Another of course is the spreadsheet, the most widely-used dataflow programming system, and a grid-based one as well. The actual execution of this system is not similar to spreadsheets, but some of the affordances for working with the grid are.

Live dataflow systems like Natto, and Ink & Switch's Capstone project, also inspire the approach to live updating and high-level data types. The Hazel environment and its "typed holes" also contributed to the interaction design.

The Kitten language was an entry point into statically-typed concatenative functional programming languages and influenced the approach taken in the original version of this system.

The animations between the textual and visual representations draw on my past work on Tiled Grace, which introduced this mechanism for making clear the relationship between sides in multiple-representation environments.

Alexander Obenauer's "itemized operating system" project also influences the approach to very high-level data types. It would be interesting to integrate with external systems that expose their data in this way, so that it can be programmatically accessed with the pathway to obtain the result being explicit.

Implementation

The working environment is accessible in any web browser here. All programs execute client-side, and the grid is manipulated with the pointer: drag to select values (or click on single values), tap on functions to replace, remove, or edit them, and tap on the plus button on the right to add a new constant value. Functions and programs are accessed via the tab bar at the top, and all functions are saved in the browser's local storage upon switching.

A working version of the system is also below, although it has some limitations in this environment and is less full-featured here.

As it runs in the browser, the implementation is in JavaScript and is limited by the browser sandboxing in what it can provide. When running from a local file (rather than over HTTP) there are further limitations.

Future Work

The present system serves as a demonstration of the concept, and has a range of functionality to explore the ideas. However, there are a number of areas for future work, including simply building out more comprehensive functionality in the present sphere.

The core interaction modality seems like it would be a good fit for a mobile device or other touch-screen interaction, and it would be interesting to explore this further. Swipe and tap gestures are typical interactions on such devices and align directly with the grid and function selection. This approach could provide a mechanism for programming on these devices, in the vein of what TouchDevelop aimed at. Some preliminary work extending this system for tablets has shown satisfying interactions.

The system is currently limited to a single grid, and it would be interesting to explore the possibility of multiple grids visible at once, with the ability to connect them together. This would allow for more complex dataflow systems, and would also allow for the possibility of multiple users working on the same system at the same time.

Additional data types, and richer affordances for working with them, would also be useful. Especially in the exploratory programming context, it would be helpful to have a wide range of operations and clear discovery mechanisms, while more direct manipulation of displayed high-level values to produce code outputs would also be good.

Connecting to external systems would also be interesting, and the design of functions permits live-updating inputs for reactive programming.