dcreager.net

Concatenative programming languages

Categories of instructions in a concatenative basis

Can you compile quotations in parallel?

Reduction semantics

Slip and slurp

Kleffner's talk on stack language typing

2022-08-10

John Purdy has a good overview of concatenative programming languages. He points out that they are built around function *concatenation*, rather than function *application*, but also points out that this definition doesn't really help explain *why* they're useful or interesting.

Why Concatenative Programming Matters [Purdy]

A different view that he describes is that *everything* in a concatenative language is a function that operates on a stack — and in particular, on a *prefix* of the stack. If you were to type one of these functions, you could explicitly include the “stack variable” that shows how the function's input and output relates to the prefix:

2 :: (σ) → (σ, int)
+ :: (σ, int, int) → (σ, int)

This is exactly like the symbol stack pre- and post-conditions in stack graphs!

Stack graphs

Should stack graphs just be Forth programs?

And the prefix variables are just like the globs in a Swanson environment type!

Should Swanson be concatenative?

Papers

Mihelic2021 is a good rendering of the operational semantics of a stack-based language.

Mihelic2021

Pestov2010 describes Factor, which introduces checked stack effect annotations as a means of adding types to stack-based programs.

Pestov2010

Diggins has two unpublished papers that describe the type system of Cat, which inspired how Factor _checks_ the stack effect annotations in a program, instead of treating them as unchecked documentation like in Forth.

Diggins2008a

Diggins2008b

[Kerby2002] The theory of concatenative combinators

[Maddox2022] Foundations of Dawn: The untyped concatenative calculus

Videos

Jon Purdy, Stanford Seminar: Concatenative programming: From ivory to metal