dcreager.net

The natural linear concatenative basis

I've already called out the 2- and 3-element bases from Brent Kerby's writeup.

The two-element linear concatenative basis

The three-element linear concatenative basis

But I neglected to talk about the 4-element basis! Kerby doesn't mention that one directly, but while rewatching my Strange Loop talk, I realized it's worth discussing.

In particular, I mention in my talk that the 6-element nonlinear basis (i, cat, drop, dup, unit, swap) is the most commonly chosen basis, because there is a 1:1 correspondence between primitive instructions and the “categories” of instruction that you have to cover to have a complete basis. (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.) I think it's worth calling this 1:1 basis the “natural” basis.

The natural normal concatenative basis

[Strange Loop] Concatenative programming and stack-based languages

Categories of instructions in a concatenative basis

So, what would the natural linear basis be? Well, you'd just remove ‘drop’ and ‘dup’, leaving you with:

  • i
  • cat
  • unit
  • swap

Is that enough to be complete? To see if it is, we just have to reduce from one of the other bases:

cons ≜ swap unit swap cat

          ┃ [B] [A] cons
          ┃ [B] [A] swap unit swap cat
      [B] ┃ [A] swap unit swap cat
  [B] [A] ┃ swap unit swap cat
  [A] [B] ┃ unit swap cat
[A] [[B]] ┃ swap cat
[[B]] [A] ┃ cat
  [[B] A] ┃
sap ≜ swap cat i

        ┃ [B] [A] sap
        ┃ [B] [A] swap cat i
    [B] ┃ [A] swap cat i
[B] [A] ┃ swap cat i
[A] [B] ┃ cat i
  [A B] ┃ i
    A B ┃ i

(I originally had more complicated definitions, but was able to find simpler ones.)

Defining ‘cons’ with only empty quotations

A simpler definition of ‘sap’