💾 Archived View for dcreager.net › concatenative captured on 2024-02-05 at 09:56:30. Gemini links have been rewritten to link to archived content

View Raw

More Information

⬅️ Previous capture (2023-11-14)

➡️ Next capture (2024-03-21)

-=-=-=-=-=-=-

Concatenative programming languages

Categories of instructions in a concatenative basis

Can you compile quotations in parallel?

Kleffner's talk on stack language typing

The two-element linear concatenative basis

The three-element linear concatenative basis

The natural linear concatenative basis

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 does 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

Links

[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