¶Categories of instructions in a concatenative basis

Brent Kerby describes several “bases” — sets of primitive instructions that are sufficient to make a concatenative language Turing complete, since all other instructions can be written in terms of your basis.

The Theory of Concatenative Combinators [Kerby]

In my Strange Loop talk, I call out that there are six “categories” that your primitive instructions need to cover to form a valid basis:

• quote
• unquote
• concatenate
• reorder (exchange)
• duplicate (contraction)
• destroy (weakening)

I also call out that there is a “natural” basis (though I didn't use that term in the talk), where there is a 1:1 correspondence between primitive instructions and their categories. (That is, each category is covered by exactly one primitive instruction, and each primitive instruction does only what is required by its category and nothing else.)

Kerby also discusses “conservative” bases, where we remove “destroy” from the list, and “linear” bases where we remove “duplicate” and “destroy”.

[Strange Loop] Concatenative programming and stack-based languages

Kerby » Conservative Completeness

Kerby » Linear Completeness