Droste's Lair

Droste's Lair is an unusual programming environment for building and counting mathematical structures, built in a two-week sprint. In Droste's Lair, the user manipulates mathematical structures through direct interactions: dropping dominoes on chessboards and dragging items between lists. The system's power comes from two forms of abstraction on top of this foundation: an "amb" mechanism that allows strands of execution to branch from one another, and a procedure-calling mechanism that enables recursion.

Also, Droste's Lair is a swords-and-sorcery-style point-and-click adventure game. (Sort of.)

Walkthrough

To get you up to speed with the gameplay of Droste's Lair, we'll take you on three quick jaunts into the caverns. We invite you to join us on this walkthrough – links to the game are available at the top and bottom of each journey so you can play along from the beginning or jump to the conclusion.

The lair is a work in progress. If something feels confusing, it's not you, it's us.

Pan by scrolling, dragging the background, or moving the cursor with shift held. Undo is available with ctrl-z. Powers beyond these will be introduced in time, or kept deeply secret.

The Reversal of Fortune

A piece of parchment is against the dungeon wall, dimly lit by flickering candelight. On it is a list: [a, b, c, d].

Your teacher (who's also a cool wizard) has tasked you with reversing the elements of this list. You first try to do this by moving elements one by one. Clicking an element...

...picks it up, and reveals places it could go. You add it to the start of the second, currently empty list.

Your action has magically created a second square of parchment on the wall showing its effect. You could almost think of this as a "comic book", though the damp air and clink of chains in the distance make the situation anything but comical.

You could continue moving items one by one, and it wouldn't take long with a list this short. But you know that sooner than you would like, you will face far greater foes. Moving items by hand, you'd only make it through a handful of items before being knocked out by some orcish cudgel. You need a way to automate these motions, a sorceror's apprentise of sorts.

The spell to cast has been with you the whole time, in the top-left: ♌︎. This sigil marks the script you are writing. With it, you can take what you've done so far, and cast it again, as a spell of its own.

With some trepidation (you're playing with recursion, after all!), you grab the sigil and cast it onto the latest panel...

Your trepidation was called for. The effect of your spell is simply astonishing.

Portals into the wall have opened up, deep holes with deeper holes beyond. Inside each hole the sigil ♌︎ does its work. So each begins with the "start" parchment, and then has a "move item 1" parchment, just like the script outside the hole. But each starts with the outcome of the previous hole. So while the top level moves an "a", the next level moves a "b", and so on.

Where will this madness end? At the bottom, in a fateful encounter with the eldrich consequences of your sigilic incantation: the base case. You were never far from it. A short pan takes you over to the deepest hole, four levels below the surface.

In this deepest level, the first list has been exhasted. All items have been moved to the second list, in reverse order. This is great progress, but we're not done yet. Though our answer lurks in the depths of the the recursive holes, nothing is coming out to the surface. Yet.

The problem is that our parchment is getting stuck. The spirits of the parchment call out to us: "list is empty!". We know that, actually, the first list being empty isn't a problem at all – it just means that we are ready to call our answer back from the world of spirits. So we guide the parchment along by giving it an escape route. Clicking the double-dagger mark (‡) creates one.

The escape route guides the parchment from the deepest level, where it ran into the obstacle of the empty list. At each higher level, the escape route is available, but the parchment doesn't take it, since it can happily proceed through the item movement and the recursive call. At last, we have a final answer on the far right. Our strange recipe is complete. We are ready to face far larger lists, and the monstrous beings that might bring them to us with nefarious intent.

The Everbranching

You've done well in your first test, but your teacher reminds you that you are still a novice. After all, your first spell only traced one timeline. At each point, it did one thing, made one decision, defined one strand of possibility. The greatest spells dissolve the bounds of decision. These spells, when confronted with the question "yes or no?" respond "yes AND no", becoming the branching limbs of a tree reaching ever towards an infinite sky.

To learn this art, you take upon a simple task: generate every face card in the deck. You begin with the raw material: a list of ranks and a list of suits.

A face card is formed by combining a rank with a suit. So first, you pick a rank.

You do this just the same as when reversing the list: pluck out an item from the list of ranks and add it to a new list. So you've picked a particular rank. But that isn't what you really want. You really want to, you know, dissolve the bounds of decision, and pick all possible ranks.

To do this, you click the "move item 1" heading. It cycles through a few different headings ("move first item", "move last item") before landing on "move any item". That's the ticket!

Now there's a stack of three parchments, three parallel universes of action. They're fanned out because you're hovered over them, but moving away for a moment shrinks them into a compact stack.

Finishing the job means doing the same thing with the suits, creating branches on top of branches. You pick a suit off one of the panels on the right and put it next to the selected rank.

And you turn this step from "move item 2" into "move any item".

Your 12 face cards are all here. Fanned out in the candlelight, they're beautiful.

The Enumeration

You've learned the rudiments of casting recursive spells and splitting worlds into swarms of possibilities. Now it's time to put these arcane arts to use on a real challenge.

An evil sorceror is tormenting a nearby village with an insidious puzzle: How many ways, he asks, can a 2xN checkerboard be covered completely with dominoes?

What!? N isn't a number! That's a letter! There's no chance you'll be able to grapple with this sorcerer's "pretending letters are numbers" hocus-pocus quite yet. But you can start to get a feel by replacing N with a number. Let's say, 4.

You prepare a 2x4 checkerboard.

How to fill it? Well, you can try just putting a domino down.

Ah, now maybe we could fill the rest of the board with vertical dominoes like this. You realize you want to repeat a step over and over again, sort of like the reversal exercise you were trained on... but this is a little different. Before, you casted a recursive spell onto an entire panel of parchment. Here, that would cause the next dominoes to stack on top of the first domino in the same squares over and over again. We need to cast the spell so that it acts on the rest of the checkerboard, leaving out the first domino.

Maybe you can just... point your wand over a little?

You cast the spell onto the subgrid, and breathe a sigh of relief. It seems to have worked!

Deep in the recursion, your "place domino" action is failing, since it's going off the board. That's ok though; that just means the board has been filled. So you activate the escape route.

You've successfully found one way to fill the board with dominoes, using only vertical dominoes. Now you should explore using horizontal dominoes instead. Starting again from the blank board at the far left, you create a second branch to place two horizontal dominoes.

Once again, you're left with board to fill after your first two dominoes. You decide to once again cast a recursive spell, asing your top-level procedure how it might choose to fill the remainder of the board.

You expect to get another simple loop, showing how two more horizontal dominoes could be added to fill the board. But something extraordinary happens.

The two-way branching you defined at the top level has been replicated inside every level of your recursive spells! There are no simple one-way loops anymore – instead, with every deeper hole there are new branching possibilities.

You check the final output. Giving it a bit of thought, it seems like these five coverings are the only ones possible. Have you somehow stumbled onto a fully general program?

It's difficult to make sense of it all at once. Fortunately, your teacher taught you a "collapse calls beyond depth 1 spell" (hitting "2" on the keyboard), so you use it now. A great many of the holes before you shrink, leaving only the highest-level structure visible.

Ah, of course. After adding a vertical domino, you can add either a second vertical domino OR two horizontal dominoes. Similarly, after adding horizontal dominoes, you can add either a vertical domino OR two more horizontal dominoes. It does seem like following this branching pattern, always adding either a vertical or two horizontal dominoes, would get you every possible covering.

You've conquered the problem of the 2x4 checkerboard! But some mysteries remain... What did that evil sorceror mean by "N", anyway? Finding out will be journey for another day.

Exegesis (a.k.a. Discussion & Future Work)

Now that you've returned from your travails in the caverns, we'd like to tell you a bit about how Droste's Lair came to be. Grab a mug of spiced mead and take a seat.

Hi! We're Elliot and Josh. We met earlier this year through Internet circles like Ink & Switch. We discovered that we shared a lot of interests, especially around visualizing math. So we decided to embark on a little project together which ended up taking about two weeks.

We took the tight time-boxing of our project as an excuse to be indulgent and follow our whims. Droste's Lair is definitely an artistic investigation. It might also be a research project. We feel great about where it ended up. It's a genuinely weird little creation that combines some of our long-held principles with some out-on-a-limb experiments. It was really fun to make and it may even be fun to play with. We're not sure what it's good for, exactly, but we're fine with that.

For the rest of this "exegesis", we'll talk about the ideas that braided together to form Droste's Lair, some tensions we thought through, and some open questions that remain.

Programming model & origins thereof

This project fits into a lineage of projects that co-design an underlying programming model with a visual interface for viewing and interacting with that model. Of course we draw on ideas from traditional programming languages, but always while asking "what does this look like?" and "how does it feel to edit this?".

We were influenced by a few prior projects in this vein. Josh was interested in revisiting an old idea: a live-programming interface for building trees to solve combinatorial counting problems. His original prototype, called "Construct 'n' Count", adopted a functional-programming structure where each level of a branching tree acted like a "map" operation, defining a new variable that could be referred to deeper in the tree.

Marcel Goethals' recent Subsequently prototype offered an exciting alternative to this functional nested-scope vibe. In Subsequently, each comic pane contains the full state of the world at a point in time. You act directly on a pane's contents. There are no variables buried in some other pane; everything you need is right where you are. Subsequently also demonstrated that some processes (like picking elements out of arrays) feel more natural as imperative processes which mutate a world state, rather than as functional processes.

Subsequently's lack of "spooky action at a distance" and its imperative model felt appealing to us. They added up to a physical feeling that seemed appropriate for a live, interactive, visual programming system. Also, they were weird by conventional CS standards, which is always a good sign.

In order to extend the Subseqently model to work for Construct-'n'-Count-style counting problems, we had to add branching. Sure, Subsequently has conditional branches, as shown in the shot above, but we needed unconditional branches – branches that are all taken simultaneously, "dissolving the bounds of decision". This sounds fancy, but it's straightforward to build. It is also well-trodden ground in computer science, also known as "amb" or "the list monad" or "nondeterminism". Admittedly, it's less common to see this kind of thing in an imperative environment like Droste's Lair, which is exciting.

The Subsequently-plus-branching potion we brewed up was enough to cover some simple counting problems, like the cards we made in the Everbranching walkthrough. But some of the most interesting counting problems were still out of our grasp. These were the ones involving recursion: where counting possibilities for a larger structure involves splitting it into pieces, counting possibilities for each piece, and then recombining the possibilities of the pieces into possibilities for the whole. In the walkthrough, we showed how to use recursion to count ways to cover a checkerboard with dominoes. We were actually originally motivated by a more complicated question: counting paths on the fractal Sierpinski graph (also known as the Hanoi graph, since it maps out states in the Towers of Hanoi puzzle). We weren't able to get to this problem in our short sprint, but dominoes were a nice alternative.

Aside from the applicability of recursion to counting problems, we were also just plain curious about how to make recursive structures comprehensible in a visual programming interface. (Elliot in particular has been investigating this strand for some time.)

With that, we had the basic formula for the programming model in Droste's Lair:

• Subsequently-style imperative flowcharts
• ... plus branching paths
• ... plus recursion.

That's basically it, as long as you ignore (as we do for the moment) that Droste's Lair is also a point-and-click adventure game.

Branching

Droste's Lair provides two ways to produce branching computation:

1. invoking multiple actions or procedures off of a single panel, or
2. invoking an action or procedure that has multiple outputs.

When multiple distinct actions are invoked on a panel, they are shown branching from it (1). But when a single action or procedure has multiple outputs, we group those outputs into a stack of panels in the interface (2). It would have alternatively been possible to not group those outputs and to instead display them as branching paths.

There's a tradeoff involved in putting multiple outputs into a stack. The stack visualization we chose keeps the interface closer to the structure of an underlying flowchart: each action added by the user is depicted in one place. If "move any item" and actions like it instead produced branches in the interface, these actions would be depicted multiple times, making the interface less directly match the underlying program. But in some ways, the run-time behavior of the program would be more clear.

This tension between highlighting static and dynamic structures is common when building live-programming systems. The dynamic execution of a program is an "unfolding" (by loops / calls) and "slicing" (by conditionals) of the program's static specification. It is challenging to show both static and dynamic layers at once.

But there are techniques that can help. Thoughtful visual design can go a long way. And, lucky for us, computers are interactive, so we can use interactive techniques too. Future work on Droste's Lair could could let users switch between stacked and branched views as they please. Or perhaps hovering a panel could reveal, through highlights, other elements on the screen less obviously connected to it.

Recursion

Unlike Droste's Lair, Subsequently doesn't have recursion. To loop in Subsequently, you make an arrow from a step back to a previous step, essentially a "goto". Although goto is out of fashion these days, it is honestly a pretty great way to loop, for a certain range of situations.

Some of the problems we wanted our system to handle seemed to lie outside this range, like the Sierpinski problem alluded to earlier. We knew there was good reason to resist whole-hog recursion, which is notoriously difficult to learn and work with, especially for those who aren't committed programmers. So we spent some time sketching to see if we could find an alternative to recursion that gave us the expressivity we wanted while fitting better into Subsequently's model.

In the end, we couldn't make anything work, and we went for fairly traditional recursion. We still feel there could be something interesting down this road. For instance, we spent some time thinking about what it would mean for a flowchart arrow to flow not out of an entire panel of a flowchart, but out of a piece of a panel. In our imagination, this could let a flowchart express the "divide-and-conquer" structure of a recursion. (One way to look at this: Flowchart arrows roughly correspond to tail-recursive calls. What we have here suggests a gentle loosening of this constraint to allow making multiple simultaneous tail-recursive calls that commute with each other because they operate on different parts of a structure.)

Putting wild alternatives aside, it was now our job to bring recursive calls (procedure calls in general) into the Subsequently model. In Subsequently, an action is represented as a comic panel that shows a picture of the world after the action, annotated with graphics that illustrate the action itself and descriptive text above the panel.

We took this design and extended it to our depiction of procedure calls. Calls in our system are represented as a hole containing the body of the called procedure followed by an "after the 'procedure call' action" panel.

Visually representing a call as a physical hole in the cobbled floor of the editor was inspired by metaphors of "depth" in recursion, and by the spooky, disorienting feeling of crawling deeper and deeper into caves and/or recursive functions.

In Droste's Lair, you can call a procedure on an entire panel or on a piece of a panel's contents that you select.

A note on how we visualized panel contents inside of holes: The most straightforward move would have been to show a called procedure operating only on the piece it was given, without any reference on the parchments to the larger whole they came from. But we reckoned that doing this would give up a lot of the physical, "object-permanent" feeling that we were striving for in our design. Passing into and out of procedure calls would require reorientation. To maintain the feeling of grounding we wanted, we instead chose to always show parts in the context of the whole. We use a color-coded outline to show what part is actively focused by the procedure call, and fade out the rest.

(We maintain a conceptual color scheme throughout the interface of Droste's Lair: yellow for actions, purple for procedures & calls, and red for trouble.)

Although we've tried in this project to visualize recursion as concretely and understandably as possible, building a recursive procedure is still an immensely "programmer-brained" activity. It won't feel natural to most people, even with our visualizations. But we aren't ready to give up on recursion yet! What could we do to make building recursion in our system less programmer-brained? Maybe users could start by building concrete trees by hand, and then our system could help them build recursive functions to match these?

Conditionals

Our design naturally diverged from Subsequently's when it came to flow control. We were looking for ways to make recursion less "programmer-brained"; we gravitated towards letting the user do whatever they wanted, and then letting them handle the ensuing errors as a post-hoc reaction to the situation.

Leaving behind traditional, if-then-style conditionals opened up a large space of designs. We went through several iterations of error handling, during both the initial design process and early implementation. The first design that worked for all our examples was allowing the user to attach an error handler panel to any other panel as a "catch" for that panel's action. In the end we landed on a different mechanism that felt a bit more natural for our examples: attaching an "escape" panel for when all possible actions from a panel result in error.

We don't have much confidence that this is the "right" way to handle errors or other conditions in a system like this. More exploration is needed!

Juice & Aesthetics

So far in this exegesis, we haven't acknowledged the dragon in the room: Droste's Lair isn't just a visual programming system. It's also a swords-and-sorcery-style point-and-click adventure game. Kind of... Maybe not really, but it's certainly inspired by the aesthetics and design of those games.

This strange decision came from our hankering to dip our toes into Juice (a term from game development). Droste's Lair may not be the juiciest thing you've ever encountered. But we're used to making 0%-juice programming systems, so this is a big step into the juice for us.

Juice is cool
Just look at nool

Elliot came to code
through game development
rekindled

A crafted object
made with artistry and thoughtfulness
a pleasure to create together
hopefully also to use

Why do we make things?
Who do they appeal to?
Why do we make things that look like Microsoft Office?

Could Juice help a pink brain
overcome the pain of trying
to think through the mundane?

Making things less abstract
adding realistic textures and objects
helped some people understand recursion

Encourage game-like patterns of thought
and play

Even More Future Directions

We've already highlighted some limitations & open questions in the discussion above. But here are some more!

• More microworlds: The demos in the walkthroughs used two simple "microworlds" – lists and domino tilings. We've been been able to get a bit of fun out of these microworlds, but we wonder what other simple domains of state and action could be even more generative.
• Mixing microworlds: Why can't I drag a card suit into the domino grid? Why can't I place a domino in a list? Mashing worlds together could multiply the possibilities, but it's not at all clear what underlying models would make that work.
• Scaling: For this prototype, we've stuck to small toy examples – neither the data nor the flow charts get very large. When they do, the way we visualize things begins to break down. This dovetails with a common critique of visual programming – a failure to scale to larger situations. But we're not worrying much yet. When the time comes to scale up, we will have so many techniques to draw from! Expanding and collapsing, minimaps, outline views, more compact graphic design, and on and on. We've already dipped our toes into this space with the recursion-depth filter we showed in the Enumeration walkthrough.
• Learnability: If you've taken the plunge to actually spend some time in Droste's Lair, we applaud your courage. You may have noticed – it's tough to work with, in so many ways. What could we do to guide people in their explorations? Could we borrow narrative techniques from games? Could new mechanisms in our programming model give people a gentle ramp from concrete actions into abstract concepts like recursion?
• Representation of action: Following Subsequently's example, we've added visual representations of actions themselves to Droste's Lair. Rather than just seeing the states of the world before and after an action, annotations are added to the state to show what's happened. There are at least four hypothetical views relevant to an action: a "before" view, an "after" view, an annotated view of "before" showing what is about to happen, and an annotated view of "after" showing what just happened. In our current system, we focus on the annotated view of "after". Is this the best focus to have? Are there ways to include more views, or to allow moving between views?
• What do we do with it: We built Droste's Lair as a short experiment. We are, honestly, pretty delighted with it. But some may wonder: what good is this thing anyway? We wonder that too, although we'd phrase it less confrontationally. Could this project grow into an educational tool? A mathematical laboratory? An honest-to-goodness game? A programming environment for data integration workflows? Hmmmm.

Thanks to...

• Marcel Goethels, for the lovely inspiration of Subsequently.
• Ink & Switch and the Pacific Programming Interfaces Confab, for motivating us with venues for sharing.
• Ivan Reese, for play-testing & insightful feedback.
• Andrew Blinn, for play-testing, insightful feedback, and his championing of juice.
• Rocky430, for inspiring conversation with Elliot about Aesthetics such as Frutiger Aero and PSX.
• Nick Joliat, for fractal inspiration.
• Todd Matthews, for the brilliant name.

Droste's Lair
on GitHub

Please get in touch!
vez@duck.com
joshuah@alum.mit.edu