"Concatenative programming and stack-based languages" by Douglas Creager

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!
----
Recorded on Sept 21, 2023 in the PWLConf track at Strange Loop 2023 in St. Louis, MO.
thestrangeloop.com
pwlconf

[@blaiseutube]

I took a class with Alan Perlis when I was in college. Yes, I did have a slight idea of how lucky I was.

[@sjmaddox]

Great talk! Very clear exposition. And thanks for the reference 🙂

[@JohannesRiecken]

Why isn’t “swap” called “dig” for consistency with “dig2”? Very enjoyable to see how stack languages relate to other compiler theory concepts!

[@DevineLuLinvega]

In the joy docs, it says `Note that "dig1" is the same as "swap". ` It looks like it wanted to have a word that was symmetric to buryn/dign.

[@teeesen]

This is bringing back a lot of memories. Back in the early 90s I made a semantics for machine code that had the same sort of [| p q |] = [| p |] o [| q |] distributivity relationship between semantics, concatenation, and composition, allowing you to break a machine code program at any point and get the same meaning. But, I’m wondering whether the language in the talk actually has this property. Since “[“ and “]” aren’t given meaning on their own, it seems that you only get the distributivity property if “[“ and “]” are replaced using quote and compose.

[@TaranovskiAlex]

Nice talk, thank you!

[@BartoszGolda]

Very nice, even if one would not get 100% - still, it's helpful. Examples in one of Forth standards could be more universal though - if it's doable at all (cons?)..

[@DevineLuLinvega]

Forth is not based on lambda calculus tho, it'd be trickier, you'd have to have to build library words that are non standard, joy and factor have those built into the standard implementations.

[@docteurklein]

great talk!