💾 Archived View for dcreager.net › concatenative › normal-basis-2.gmi captured on 2024-03-21 at 15:38:19. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
Kerby suggests ‘cake’ and ‘k’ as the most “elegant” 2-element basis in a normal (i.e., non-substructural) concatenative language.
The Theory of Concatenative Combinators » An Elegant Base
[B] [A] cake ≜ [[B] A] [A [B]] [B] [A] k ≜ A
Here are the translations of each natural basis instruction into the 2-element basis:
[B] [A] cat ≜ [B] [A] [[i] cake k i] cake [] k cake [] k
^^^^^^^^^^^^^^^^^^^^^^^
= [B] [[A] [i] cake k i] [[i] cake k i [A]] [] k cake [] k
^^^^^^^^^^^^^^^^^^^^^^^
= [B] [[A] [i] cake k i] cake [] k
^^^^^^^^^^^^^^^^^^^^^^^^^^^
= [[B] [A] [i] cake k i] [[A] [i] cake k i [B]] [] k
^^^^^^^^^^^^^^^^^^^^^^^^^^^
= [[B] [A] [i] cake k i]
^^^^^^^^^^^^
= [[B] [[A] i] [i [A]] k i]
^^^^^^^^^^^^^^^^^
= [[B] i [A] i]
^^^^^
= [B [A] i]
^^^^^
= [B A]
[A] drop ≜ [A] [] k
^^^^^^^^
=
[A] dup ≜ [A] [] cake cake k cake k
^^^^^^^^^^^
= [[A]] [[A]] cake k cake k
^^^^^^^^^^^^^^^^
= [[[A]] [A]] [[A] [[A]]] k cake k
^^^^^^^^^^^^^^^^^^^^^^^^^
= [A] [[A]] cake k
^^^^^^^^^^^^^^
= [[A] [A]] [[A] [A]] k
^^^^^^^^^^^^^^^^^^^^^
= [A] [A]
[A] i ≜ [A] [[]] cake k k
^^^^^^^^^^^^^
= [[A] []] [[] [A]] k k
^^^^^^^^^^^^^^^^^^^
= [] [A] k
^^^^^^^^
= A
[B] [A] swap ≜ [B] [A] [] cake [cake] k k
^^^^^^^^^^^
= [B] [[A]] [[A]] [cake] k k
^^^^^^^^^^^^^^
= [B] [[A]] cake k
^^^^^^^^^^^^^^
= [[B] [A]] [[A] [B]] k
^^^^^^^^^^^^^^^^^^^^^
= [A] [B]
[A] unit ≜ [A] [] cake [] k
^^^^^^^^^^^
= [[A]] [[A]] [] k
^^^^^^^^^^
= [[A]]