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:

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

Normal bases

=> ‘cake’ and ‘k’ | ‘cat’, ‘drop’, ‘dup’, ‘i’, ‘swap’, and ‘unit’ [natural]

Linear bases

=> ‘cons’ and ‘sap’ | ‘take’, ‘cat’, and ‘i’ | ‘i’, ‘cat’, ‘unit’, and ‘swap’ [natural]

=> ..

Proxy Information
Original URL
gemini://dcreager.net/concatenative/basis-categories.gmi
Status Code
Success (20)
Meta
text/gemini;lang=en
Capsule Response Time
408.222739 milliseconds
Gemini-to-HTML Time
0.870676 milliseconds

This content has been proxied by September (ba2dc).