Annotated lambda diagram

From apm
Jump to: navigation, search
Conversion of Cartesian coordinates to polar coordinates in the representation of annotated lambda diagrams.
For details see: ALDs – example Cartesian to polar.
Quicksort algorithm as a single function in the representation of annotated lambda diagrams. Here rotated 90° to matching the usual orientation of plain unannotated lambda diagrams to better show the correspondence.
For details see: ALDs – example quicksort.

Annotated lambda diagrams (ALDs) are a proposed "code projection" that aims at being a highly enjoyably usable interface for telling computers what to do (aka coding/programming/automating/...).

ALDs minimize discontinuous visual jumps and thereby minimize the necessity of expending mental resources on navigating codebases. A "bicycle for the mind".

ALDs where inspired by plain unannotated lambda diagrams as they are presented by
John Tromp on his homepage here:
ALDs add annotations and some minimal "syngraphic sugar" to plain lambda diagrams.

Mockup Demos

See main page: Annotated lambda diagram mockups – More images there.
If actually implemented all this should be dynamic, animated, and interactive.

ALDs are not a "node editor"

While there are visual line and box elements,
ALDs are not a node editor simply because they do not feature nodes.
What may look like nodes are merely tags/annotations of the lines.
As such there is no need to decide

  • which one of wires and nodes represents values and
  • which one represents value-transforming-functions

Unusual "inverse node editors" that swap the roles of lines and nodes are no less different to ALDs than conventional node editors are.
Swapped roles meaning: Lines represent value-transforming-functions and nodes represent values like e.g. in the PANE demo [1]

The lines

The orientation of the lines carries meaning and is thus not subject to arbitrary change in placement.
There are three types of lines:

  • abstraction lines
  • value lines, and
  • application lines

Matching lambda calculus, but there is no need for users to know that.

Lines can represent both values and value-transforming-functions.
Actual value-transformations are indicated by the T-crossings where the application-lines run into value-lines.

No conflation of abstraction and application

A huge difference to node editors is that ALDs do not conflate function abstraction and function application.

ALDs make an explicit distinction between:

  • unevaluated abstractions (disconnected context free – unconnected top of abstraction lines) and
  • evaluations (connected into context – application lines feeding source value lines into recipient value lines)

Node editors in contrast directly connect output ports with input ports.

What are the consequences of this difference?
Maybe this might be as relevant as adding a zero to a number system??

The center between visual and textual

ALDs seem to lie at the smack dead center between visual and textual code projections/representations.

That is: Annotated lambda diagrams seem to be as in the middle as it gets between:

  • typical textual programming interface (for pure/denotative programming languages)
  • typical box-and-wire visual programming interfaces and

The reader may judge.

Scalability on par with textual code

Unlike node editors the on-screen spacial layout-structure of ALDs is remarkably close to conventional textual code (of a denotative programming language).
Annotated lambda diagrams are very close in structure to textual code as seen in pure functional programming languages
(That is: Languages with computer checked guarantees on code purity like e.g. haskell, purescript, elm, ...)

Morphing an annotated lambda diagram representation into the corresponding textual representation requires only:

  • a slight rearrangement of the value-name-annotations
  • removal of the lines without making things ambiguous by addition of some textual syntactic sugar

This closeness of the annotated lambda diagrams to a purely textual code representation
necessarily makes the representation equally scaleable than a textual code representation.
Well, at least up to a constant factor given by the lower "on screen information density" that all graphical things necessarily come with.

Less visual discontinuities

ALDs would allow their users to browse codebases in a way that is visually almost free of discontinuities.
This would work by zooming into functions that the currently viewed function depends on.
This feature could be called: "adjustably scaled down in place preview".
(Minor side-note: Smooth zooming is important, avoid implementing scroll-wheel-notch-jumping-jar – for neurological health.)
The one very intentionally remaining visual discontinuity is the aforementioned
separation of function abstraction and function application.

Node editors could potentially allow for visually discontinuity free codebase browsing by
"adjustably scaled down in place preview" too, but due to the aforementioned conflation of function abstraction and function application
( or equivalently non-distinction between unevaluated and evaluated state )
they cannot properly (i.e. denotatively) show evaluation of code within the codebase visualization. ...
If basic node editors could do that, then they could represent lambda expressions, which they can't.

In ALDs if one does manual code transformations during programming edit-time (like e.g. substitutions or factorizations) then
continuous animations could almost fully continuously show these transformations as code-circuits flowing through code-circuits.

Animating code transformations with minimal visual discontinuities

Mockup illustrating how annotated lambda diagrams could be animated with minimal visual discontinuities

Add live-coding to ALDs

The dependency graph (not tree!) of a codebase is basically a multiverse of all possible controlflow-paths that
an execution of this codebase can possibly take.
Since ALDs lay out controlflow-path-branching case-expressions in space

  • the actually taken control flow path can be highlighted (somewhat) while
  • the other not taken control flow paths get greyed out (soemwhat).

Sidenote: Most node editors and programming interfaces do not explicitely visualize inactive control flow paths.
Interesting trivia: case expressions are dual to type constructors, they do desrtuctive recursion as opposed to constructive corecursion

Note: I deliberately did not describe controlflow-paths as "active" or "inactive"
because there is no such thing as "active" and "inactive" in ALDs.

ALDs are for denotative systems

ALDs are visualization for denotative systems.
So they are timeless/unchanging/immutable. They are about what "is" not about what "happens".
Changes in control flow path are mapped out in (zoom)space rather than time.

If a user changes the content of a value like in a spreadsheet-like-cell (a cell that is annotating a value line),
and the user sees the actual control flow path "changing", then
what the user actually sees is just a switch to a different slice of the same timeless unchangeable immutable value.
As soon as this ephemeral exploratory parameter is baken in
(by connecting the spreadsheet like cell to other ALD values that representing the result of a computation)
any temporal changes get mapped to (zoom)space.

Of course, if so desired then user-inputs could be logged and treated as a timestamped timeless lists (enabling "timetravel debugging" [2])
First order FRP (like in early versions of the elm programming language [3]) may be a good match for ALDs.

Diving down the dependencies by zooming in during live-coding basically amounts to

  • step-tracing the code execution and
  • having it everywhere editable/snapshotable/... !!

One could maybe manually collapse sections of the codebase according to what the code-execution actually does
optionally including eventually preceding compiler optimizations.
This would be the same as edit time code transformations, just not permanent.
Well, one could take a snapshot.

The only things visually changing in ALDs are:

  • Switches between slices of functions by changing ephemeral test-input-values (spreadheet style live propagation)
  • New logged user input where conceptually we pretend to just uncover the next preexiting values.
  • The processor threads (&GPU?) filling up fresh untainted memory creating more of the "present-state-of-IS" based on "uncovered" userinputs, ungreying the taken control path.
  • The garbage collector(s) deallocating memory ( fully greying out taken control paths )

In ALD's all of the above "actors" (allocation, generation, usage, and cleanup) could be visualized simultaneously!!
Like busy ants visibly crawling through your code.

Observing the activity of scheduled runtime system "actors" that could be done:

  • at a high enough call-stack level for "changes" to be slow enough to be visible for the human eye
  • with slow motion mode such that "changes" become visible to the human eye – all the way down to manual processor instruction stepping
  • somewhere in-between
  • with a special superposition mode where the control paths get gradually colored according to the spaciotemporal ensemble of all all occurring call contexts being averaged over. That is: Control-flow paths get a coloring intensity depending on how often they get taken. Note that this deprives the observed ALD visualization of a specific call context though.

Remember that conceptually there is no change here. Typing something in and seeing resulting changes is merely
The GCs cleaning up the old "state of IS" and the CPUs building up the new "state of IS".
When separate fractions of the codebase are viewed in a live coding way then memoization questions may lead to some head-scratching in implementation here.

Peering into the entirety of the control flow multiverse while it's running live. The lines highlighted in dark blue mark the control flow path that is active at the current moment of execution time (possibly paused). A bright cyan background marks the active case-of-branches. – The "demo" function performs constructive corecursion with dataconstructors. The "showBinFancily" function performs deconstructive recursion with the case of construct. (TODO: Investigate avoiding recursive definitions alltogether. See Book: "The Little Typer")

The several types of zooming

Per window global zoom-level

There is the global zooming to browse through the codebase.
One of course will want to have multiple windows with different global zoom-levels to show different far apart pieces of codebases simultaneously.

In place preview zoom-level

There is the relative zoom-scale for in place preview of functions.
That is when the annotation of a line in an ALD shows an ALD preview of the function it is referencing.
Adjusting this zoom-level keeps the scale of the ALD that is currently in focus unchanged but only scales one (or more) previews inside.
Whether (or how deeply) this in place preview scaling should act recursively could be adjusted by a setting. Probably nontrivial to implement.
Different in place previews in the same ALD may feature different in place preview scales.

Since this adds up to a geometric series in consumed screen-space even an infinite nesting would take only finite screen-space.
Of course one will want to implement an adjustable cutoff (and mipmapping) and
of course one will want to implement options to open up just the one next deeper preview instead of the whole recursive dependency tree.

Nearing a 1:1 scale-ratio for in place preview, nestings will get big.
What about going beyond that, making the in place previews bigger than the ALD in focus?
Well, better to switch the frame of reference then.
this could be done in reverse for the super-context,
one of the the functions that is calling the function in focus.
See: Inverse tabs

ALD vs TV zoom-level

There is the relative zoom scale between ALD and TV-GUI-element code projection (more on that further down).
This would work like a seesaw making one bigger makes the other smaller
(and eventually vanish at some reasonable threshold defined in the default setting)

Desirable combination with higher level novel GUI concepts

ALDs could and should very much be combined with higher level novel GUI concepts.

The idea:

  • ALDs shall have the baseline capability of showing their overall result value as a GUI element – a multimedia annotation for ALD-output-value-lines
  • The best fundamental baseline approach for GUI-type-ALD-result-value-annotations seems to be the model of tangible values.

For GUI elements that containing elements positioned in an arbitrary convenient way (this includes even freehand positioned elements)
that positioning would be part of the value that represents the displayed GUI element and thus
can be conjured up by progressive exposure of the GUI element as an ALD.
GUI element positioning that does not correspond to code structure is going beyond tangible Values but is also needed in practical UIs.
It should be possible to layer that atop Tangible Values, having TVs still form the core basis.

ALDs could and should be combined with advanced ideas like:

  • Spreadsheet like tables (or better) – e.g. ZigZag [4]
  • Sketch-n-Sketch like interfaces [5]
  • Apparatus like interfaces [6]
  • Other domain specific interactive data representations [7]
  • Direct manipulation GUI layout bootstrapping?

Zooming down into the dependencies should give users an awesome spreadsheet like experience on steroids.
due to progressive disclosure tearing down the GUI vs CLI rift.

Totally tearing down the GUI vs command-line rift!

The idea is as follows:
If all progressive disclosure is in the "hide-the-details state" then the UI is completely indistinguishable from a conventional GUI.
Except one little "+" or something as the starting point for progressive disclosure.
A progressive disclosure step opens up the ALD that corresponds to the visual element (a Tangible Value).
From there the "end-user" (now elevated to status of "deveuser") can trace the codebase to non-displayed or even non-visual code elements.
Tracing the codebase entails tracing the nicely visually traceable lines in the ALDs.

With disclosure of enough GUI elements and hiding of enough visualizations one eventually ends up with Just ALDs or some other kind of code projection
Like e.g. a conventional purely textual code projection. That would correspond to the CLI end of the spectrum just that code is fully or partially represented as ALDs rather than fully textual.

If both the ALD and the GUI part of a tangible value is shown simultaneously then there is obviously the option for a relative scaling factor between the two. Making one bigger makes the other smaller while both stay in a fixed frame.

Finally add to that: Bookmarking of "interface visualizations" and

Datastoragewiki – abandon tree shaped filesystems

Organizing "code" documentation and data storage in a desktop wiki like system
that is implemented in that whole programming system in a bootstrapped way.

Desirable combination with lower level code projections/representations novel

Single line textual interfaces could easily be integrated into the ALDs annotations.
This seems somewhat related to syntactic sugar or syngraphic sugar.
Even simple one line interfaces could be made into projectional structural editors that let you type normally.
See the "tile-based editor" demo tylr: [8]

tl;dr – Summaries

The basic benefits of ALDs

Combines the best of the two worlds (of textual and graphical code):

  • Like graphical box-and-wire programming (like node editors) annotated lambda diagrams give a visual circuit board like network that is easy to trace for human eyes.
  • Almost as traceable as graphical code (since there are traceable "program circuit" lines)
    – these lines are quite different to "conventional" graphical programming though
  • Almost as scaleable as textual code (since the structure closely follows textual code) – a little less dense

Does NOT combine the worst of the two worlds:

  • notorious non-scalability of node based graphical programming
  • hard traceability of textual codebases containing lots of indirection but no means for visually continuous transitions

Other nice properties:

  • Seeing the whole code multiverse at a glance – and and the live running state as a literal "red thread" within.
  • Browsing the codebase in all dimensions without detours and disruptive jumps
    Human mental RAM is limited, it shouldn't be used for pointless navigation hurdles.

  • Annotated lambda diagrams likely have an on "screen information density" somewhere between purely textual and box-and-wire visual code representations.

  • Unlike graphical box-and-wire programming abstractions and applications are kept separated. To reiterate that.

ALD's – The basic idea in brief bullet points

  • Basic annotations are: variable names, types, current values, kinds (aka types of types), ... (not all shown per default of course)
  • Make them into a structured editor where you can type normally pretty much as you would in "plain textfile code editing"
    – (See: Fructure Specifically in this video with Andrew Blinn shortly after 6:03 [1] where he says "My preferred alternative is to simply type normally")
  • Make program fragments drag and drop interactive (like puzzle pieces)
    Give reasonable visual cues for efficiency (rather than fancy): identicons, arity mismatch visualization, ...
  • Give ALDs typed holes of input holes, output holes, and bridge holes. Don't forget the bridge holes!
    Such that program fragments are extendable: upstream, downstream, and ...
    can also be tied up in one or more still open concurrent paths (wiki-TODO: make a sketch)
  • (Eventually make data flow around holes as far as this is possible. See: Hazel)
  • Add type directed context sensitive suggestions for extending onto the present holes
  • Give ALDs a zooming user interface (ZUI) capability – that allows for (arbitrarily deep) in place evaluation preview

  • Add inverse tabs – allowing to navigate the codebase-graph upwards along different upstream paths that where formerly traced downstream along some dependency tree
    This is about answering the question "By which functions is this function that I currently look at used by?" Basic functions will have a huge list as answer. So this needs to be filterable.
    (Some dependency tree is only a subset of the codebase graph. This needs more awareness.)
  • Use an ultra finegrainedly content addressed programming language as a base!!!
    That in order to mop up with fragility of references, dependency hell and fix quite a number of other things too.
    (ony such language in construction as of 2021 seems to be the unison language)

Eventually add higher level data visualization:

  • that follow code structure (see: Tangible values – by Conal Elliott) – but with added progressive disclosure.
  • that give an immediate connection by bidirectional data-flow (see: Drawing Dynamic Visualizations – by Bret Victor) (See: enso language)

Further important properties

Structural editors often fail in usability (feel overly restrictive and boxing in) due to not allowing to ...

  • (0) ... type normally and thus presenting new users with a steep learning curve to a novel experimental system that might no even be worth learning.
  • (1a) ... extend program fragments in both directions (code upstream and code downstream)
  • (1b) ... start writing program fragments at arbitrary "floating" place that are neither top-most nor bottom-most
  • (1c) ... deliberately cross invalid states since that is the fastest path to valid states again

Structural editors provide huge opportunies in improvement in

  • (2) ... management of code versions at the single edit level
  • (3) ... seeing as much of all the code processing phases as possible (gradual typing ...)

(0) Allow to type normally – highly advisable

(0) Is heavily hampering adoption rate but does not necessarily pose a fundamental limitation to the programming UI system.
Perhaps there really is a better way to program than to type normally. That remains to be shown though.
Perhaps for small form-factor touchscreen-only type devices.
For now it seems highly advisable to implement the possibility to type normally though since
this is just the by far most tried, tested, and proven to be good interface.

(1) Do not create insurmountable obstacles for code-changes – mandatory

(1) If not averted this does, in contrast to (0), pose a fundamental limitation to programming UI system since
some essentially important program transformation pathways are fundamentally blocked. This absolutely must not be the case.
The solution seem to be to treat holes in the program as explicit formal entities that carry transformation rules. As typed holes.

(2) Treat user edits formally

Treat program transformations that are executed by the programmer during programming (aka user edits during "edit-time") formally.
Ideally record them in the same (or extended) formal framework in which the program transformations during code execution (compile-time and run-time) happen.

There might be an elegant (discovered rather than invented) way to efficiently store code changes (versions with undo history) via
formally differentiating the datastructures in which the code is represented in.
In fact the edit calculus might be derivable from that.
Explanation detour:
Algebraic data structures (ADTs) are basically nested product-types and sum-types (tuples and enums respectively).
ADTs are powerful enough for storing basically anything. Including a tree representation of program code – aka algebraic syntax trees (ASTs).
Differentiating ADTs means converting them into a different representation (see Curry Howards correspondence for details) and
literally applying the ruled of mathematical differentiation to them. Then converting back.
This leads to special ADTs called zippers. Datastructures that contain unfilled slots.
When slots in zipper ADTs are filled back in with recorded edits they give back the original AST-ADT datastructure.
(The hole process seems analogous to a Taylor series.)

(3) From batch-processed "times" to interleaved "phases"

Have edit-time, compile-time, and run-time all happening at the same time in different parts of the program.
Run all program fragments as far as they can be run to preliminary normal forms that
may still contain unfilled holes (or holes filled with ephemeral or random example values ~ program-slice-viewing or program-quick-testing respectively).

Have code flow around holes (as prototyped in the hazel language).

The "-time" part in the terminology no longer makes sense, and becomes a historic remnant that we may want to ditch due to causing confusion.
Maybe edit-phase, compile-phase, and run-phase are good alternatives?

Status of development

Unfortunately as of yet (2021-07) annotated lambda diagrams are still "vaporware" and only static non-interactive mock-ups exist.
This is a mammoth project. With these mockups at least the idea might get out there.

Relation to the context that is this wiki

We really really need software that is not broken in a future world where matter essentially becomes software.

Relation (and transformation) to other known code representations

How "annotated lambda diagrams" can be continuously transformed into abstract syntax trees and and other known representations.

Naming choice

The reader might occasionally stumble over places where these diagrams are referred to as ELDs rather than ALDs. These are historic remnants.
The original idea was using E in ELDs for a multi meaning situation where E could stand for any of:
enriched / extended / embellished / endorsed / extravagant / enamoured?! / encabulated (joke) / Erabu (Japanese for "choose") / ...

But ...

  • "enriched" is exotic and seems (perhaps for this reason) to be used in category theory - a theory that is contextually close - so not a good idea ...
  • "extended" as the next most reasonable seeming one of these may be interpreted as more than just adding annotations for visualization and interactivity.

Thus the choice fell to "annotated" and ALDs instead.

  • To add an emphasize on interactivity one could add an I like so: I-ALDs
  • To add further emphasis on live coding one could add an LC like so: ILCALDs
  • To add further emphasis of static typing one could add an ST: STILCALDs
  • Suggestions welcome ...


External links

A basic write-up of some ideas with links to twitter posts.
(wiki-TODO: this needs to be published more properly (that is: more resilliently))

Zooming user interface:
For many user interfaces this idea seems rather impractical.
It is likely extremely useful for the case of ALD's though.


  1. PANE programming interface –
  2. Wikipedia –
  3. Youtube: ""Controlling Time and Space: understanding the many formulations of FRP" by Evan Czaplicki" – 2014-09-17
  4. ZigZag –
  5. Sketch-n-Sketch –
  6. Apparatus –
  8. "Tile-based editor" tylr: