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.
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:
- 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”.