¶Description

In this talk we’ll explore stack-based programming languages, in which your program operates directly (and only!) on a stack of values. It might seem daunting at first to program without variable names, but the simplicity of stack-based languages makes them interesting to reason about mathematically, and also fun to tinker with! We’ll look at how stack-based languages are concatenative, letting you break apart your program into arbitrary pieces without affecting its meaning. We’ll compare them with combinatory logic, and see how small we can make our language while still being Turing-complete. And we’ll show how they make good low-level (but still readable!) assembly languages, by examining a Uxn program and running it on a variety of interesting hardware.

References:

• Henry Baker. “Linear logic and permutation stacks — The Forth shall be first”. SIGARCH Computer Architecture News 22:1, March 1994.
• Jeremy Gibbons. “Continuation-Passing Style, Defunctionalization, Accumulations, and Associativity”. The Art, Science, and Engineering of Programming, 2022.
• Brent Kirby. “The theory of concatenative combinators”.
• Slava Pestov, Daniel Ehrenberg, Joe Groff. “Factor: A Dynamic Stack-based Programming Language”. ACM SIGPLAN Notices 45:12. December 2010.
• Smullyan, Raymond. To Mock a Mockingbird. Alfred A. Knopf: New York, 1985.
• Manfred von Thun. “The mathematical foundations of Joy”.

[Baker1994] Linear logic and permutation stacks

[Pestov2010] Factor: A dynamic stack-based programming language

¶Reviewer info

As a hook, I’ll point out that the talk will cover both combinatory logic and the mathematical foundations of computing; as well as showing a retro game implemented in a stack language, running both on my presentation laptop and on a Nintendo DS.

I’ll start by calling out how names are complicated in most of our programming languages—calling back to my Strange Loop 2021 talk about the hoops we have to jump through to implement Precise Code Navigation in my $DAY_JOB at GitHub. As Larry Wall famously said, one of the three Programmer’s Virtues is laziness. So what would our languages look like if we got rid of this complexity, by removing names completely? Or at least, by not being able to name the values that our programs operate on?

My hunch is that in general, the audience will be more familiar with stack-based languages as an implementation technique, and less familiar with the notion of a language being concatenative. So to start, we’ll look at a very simple stack-based language, similar in spirit to Forth or Factor. We’ll show some example programs being evaluated, and how they affect the execution stack. For example, executing the program <1 2 + 3 4 4 + sqrt> produces <5>. Next we can break the program into pieces, and execute the pieces separately. Executing <1 2 + 3 4> produces <9 4>. Executing <4 + sqrt> produces <4 * + sqrt> (assuming that you handle stack underflow by pushing the operator onto the stack instead of evaluating it). The key insight is that the results are themselves stacks that we can execute! If we join the results back together, <9 4 4 * + sqrt>, and execute, we get <5>, as before. And importantly, this works no matter where we break apart the original program, and even if we break the program into more than two pieces.

Manfred von Thun described this property while creating and exploring the Joy language [vonThun]. In his more mathematical treatment, the “meaning” of a Joy program is a function that takes in a stack as an input, and produces a stack as an output. Two Joy programs can be concatenated together (like we did with the two halves of our example program), and the meaning of the result is the function composition of the meanings of the two pieces. This is what it means for a language to be concatenative — “syntactic concatenation is semantic composition”.

[vonThun] Mathematical foundations of Joy

From here we’ll move into talking about how concatenative languages are Turing complete. We’ll briefly show the SKI calculus from combinatory logic, which took the same “what if we got rid of the names” trick and applied it to the lambda calculus. Even though the SKI calculus is very simple, it’s Turing complete! Stack-based languages usually come equipped with some built-in words to manipulate the stack — dup, drop, apply, swap, etc — which we can view as the analogues to the S, K, and I combinators. Which built-in words do we need for our language to be Turing complete? Brent Kirby has an excellent article [Kirby] exploring this, looking at different “bases” that are equally powerful. There is a “typical” 6-word basis that most stack languages seem to have landed on — apply, compose, drop, dup, quote, and swap. Kirby shows that you can get this down to two — cake and k.

[Kirby] The Theory of Concatenative Combinators

Lastly we’ll come up from the world of logic and start doing some tinkering. The simplicity of stack-based languages makes them easy to reason about mathematically — but it also makes them great substrates for implementing things! Many high-level VMs (like the JVM or the WebAssembly VM) are famously stack-based. But we’re going to take a different approach and look at [Uxn]. This project defines a small stack-based assembly language, and the I/O interfaces for a simple virtual computer. Because of the simplicity of the language and machine spec, folks have implemented emulators for this language all over the place! [Emulators] There are obvious ones that let you run Uxn programs on all of the major desktop platforms, but Uxn has also been ported to a number of retro handheld gaming consoles. Here I’ll briefly walk through parts of a Uxn program (most likely [catclock]), and show it running both on my laptop and on a Nintendo DS that I’d bring with me. Maybe also my reMarkable tablet? We’ll see which devices I can get it working on.

[Uxn]

[Emulators]

[catclock]

¶Notes

The last part of the talk will hopefully involve showing some example programs running on a physical device or two that I bring along. I would bring all of the necessary equipment — the device itself, and a camera to capture its screen on the laptop. For recording purposes everything I’d want to present would come through the HDMI-out on the laptop, so I don’t think that would require any special A/V setup. Only thing I might need from the conference organizers is a table to put it all on in case the lectern is not large enough.