• Why it is matter. Intro from vp
• Intro from author
• References
• Stack languages
• The One True Mother Language: C
• From Lambda Calculus to Combinatory Logic
• Turing Completeness of Stack Languages
• The Quest for Minimalism
• Associativity and Parallelism
• Real-World Applications: Uxn

§Why it is matter. Intro from vp

Stack-based architectures have dominated Virtual machines over a few decades. We hide this complexity from a developer and move it to the VM or compiler side. With rise of decentralized computing, web3, and smart contracts we get a new challenge that could be solved by stack languages. Even more - web assembly is a stack-based architecture. I see a big benefit for developers to understand mechanics deeply.

§Intro from author

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

Douglas Creager Walland Heavy Research @dcreager

I’ve been thinking about, and using, programming languages for a very long time. By day, I manage GitHub’s Semantic Code team, figuring out how to understand and analyze ~every programming language under the sun. By night, I balance family life with hacking on my own language, like any good PL enthusiast would!

§Stack languages

Stack-based languages have always been a subject of intrigue in the realm of computer science. The video delves into the conceptual simplicity and mathematical elegance of stack-based languages, taking the audience on a journey from Lambda Calculics to Turing completeness. The talk also explores the potential for parallelism and real-world applications, such as Uxn.

§The One True Mother Language: C

The video begins by discussing the Lambda 8cc project, an x86 C compiler written in and targeting the untyped Lambda calculus. The project demonstrates that C programs can be directly compiled into Lambda calculus terms, thereby proving Turing completeness. This sets the stage for the exploration of stack-based languages.

§From Lambda Calculus to Combinatory Logic

The Lambda calculus, although Turing complete, uses names, which can be cumbersome. The video introduces Combinatory Logic, which uses three carefully chosen Lambda terms (S, K, I) to rewrite any Lambda term. This eliminates the need for names and brings us closer to a stack-based language. The video also mentions the book “To Mock a Mockingbird” for those interested in diving deeper into Combinatory Logic.

§Turing Completeness of Stack Languages

The video then transitions to stack languages, which are almost Turing complete. By adding a few more instructions, the language becomes Turing complete. The proof involves translating Lambda terms into stack language equivalents, demonstrating that stack languages can express the same computations as Lambda calculus.

§The Quest for Minimalism

The video categorizes stack language instructions into six categories: unquoting, quoting, concatenating, reordering, destroying, and copying. It then introduces the concept of defining every instruction in terms of others, leading to a minimal set of primitives. This minimalism allows for elegant and efficient implementations.

§Associativity and Parallelism

One of the key insights is that syntactic concatenation is equivalent to semantic composition. This associativity allows for parallel execution, offering a performance boost. The video demonstrates this by compiling a stack language into x86 assembly and executing it in parallel chunks.

§Real-World Applications: Uxn

Finally, the video introduces Uxn, a real-world stack-based language. It showcases various applications running on Uxn, such as Snake and Pong, both on a laptop and a Raspberry Pi. This serves as a testament to the practicality and efficiency of stack-based languages.