mlatu-6
mlatu-6 is a concatenative language and an esoteric programming language and a subset of mlatu.
Language Overview
mlatu-6 is a term rewriting language consisting of 6 primitive operators and "quotations". A quotation is a sequence of terms wrapped in parentheses. When a primitive appears directly after a quotation, a reduction can be made. The primitives are:
| Command | Description |
|---|---|
+
|
Copies the preceding quotation |
-
|
Removes the preceding quotation |
<
|
Removes a level of nesting from the preceding quotation |
>
|
Adds a level of nesting to the preceding quotation |
,
|
Concatenates the contents of the two preceding quotations into a new quotation |
~
|
Swap the contents of the two preceding quotations |
On top of this, we use letters of the latin alphabet to denote inert or opaque combinators that can't be reduced further. These come in handy to look at stack effects.
Usually programs are presented without whitespace, but if you want, you can just add a reduction rule that gets rid of whitespace.
Evaluation Order
In theory, the order of applying reductions should not matter, but in practice, it gets tricky for interpreters. See, there might be an infinite loop lurking in a quotation, but if you evaluate outermost reductions first, you will never hit it. You have two ways to handle this:
- If you always evaluate the outermost reductions first, this issue cannot happen.
- Loops are always caused by the existence of + and <, so you can always reduce the other 4. As long as you keep either one for last actually, you can do the other 5 in whatever order.
Concatenative Theory
In the concatenative calculus, there are 6 main capabilities we can do with the stack: we can copy the top element, we can remove it, we can wrap it in a quote, we can unwrap it from its quote, we can concatenate the top two quotes, and we can swap the top two quotes.
If we make a base of 6 combinators that do exactly one of these capabilities and give them simple 1-character names, we end up with exactly mlatu-6. This makes it an excellent language to study concatenative calculus further.
A Simple Program
(+<)+<
Consider this simple program. The only operator that appears directly after a quotation is the second +, so that will be our first reduction:
(+<)(+<)<
We copied the quotation, next up we can reduce the third <:
(+<)+<
We arrived back at the initial state! Since the language is deterministic, this means there's no point in further reduction, we have reached an infinite loop. When we arrive at a previous state, or our program can no longer be reduced, it is finished. Interpreters will often just stop after a set number of reductions too though.
Counting Program Length
The infinite program from the previous section is the smallest non-halting program at 6 symbols. Any other non-halting programs are at least 7 characters big. You will also notice that loops always seem to resemble this basic loop.
(A)+
The length of this program is 1. When counting program length, we don't count the inert quotations that tend to precede the program. We can also write down the stack effect of this program: (A) -- (A)(A). This syntax means that the input is on the left, and the output is on the right. The "A" here is more like a variable, it could be any sequence of combinators, and it will be copied from the input to the output (twice in fact, in this case). We don't always have to include the inert quotations:
~
Everyone understands that this program only works when you append it to two other quotations. We say that the program has the stack effect (B)(A) -- (A)(B) (we swap around, remember?).
Base Lengths
Now that we have a method of counting program length, we can take concatenative combinators, figure out the smallest program with this stack effect, and consider the length of that program the length of the combinator. k which has the stack effect (B)(A) -- A has a program length of 3, thanks to the program ~-<.
The combinator cake with stack effect (B)(A) -- ((B)A)(A(B)) seems to have a minimal length of 12 thanks to the program >~>>,+<~,~<. Now, in concatenative calculus, {k, cake} forms a complete base, just like our 6 primitive combinators form one (it means that all other combinators can be created from them). We can add up the lengths of k and cake and arrive at a "base length" of 15. The 6 primitives combinator base has a base length of 6. You can never have a base length smaller than 6, because we picked 6 primitives to start with.
Now, we could define a new combinator zapdup with stack effect (B)(A) -- (B)(B) and corresponding program -+ and replace both + and - with this new combinator in the primitive base. It turns out that we can then construct + and - from this new base quite easily. What this means is that this new base of 5 combinators still has a length of 6!
It's an open question what the minimal base lengths are for 4, 3 and 2 combinator bases.
Simplifying Reductions
Some constructs can always be replaced with others. For example, you can always replace +~ with + because the top two items are the same after a copy. Here's a list of reductions you can do (empty right hand side means you can just remove them altogether):
+- == >< == ~~ == +~ == + >- == - -- == ,- ~-- == -- ~,- == ,- +>~ == >+< +>~> == >+ >+<> == >+ >,<< == ,<
Kerby Combinators
Brent Kerby's page on concatenative calculus contains a list of combinators. Here are these combinators and the smallest programs we've found for them. There might be mistakes in this list and the programs listed might not yet have been confirmed to be minimal.
zap == (A) --
1: -
i == (A) -- A
1: <
unit == (A) -- ((A))
1: >
dup == (A) -- (A)(A)
1: +
cat == (B)(A) -- (BA)
1: ,
swap == (B)(A) -- (A)(B)
1: ~
m == (A) -- (A)A
2: +< = dup i
z == (B)(A) -- B
2: -< = zap i
sap == (B)(A) -- AB
2: ,< = cat i
t == (B)(A) -- (A)B
2: ~< = swap i
nip == (B)(A) -- (A)
2: ~- = swap zap
swat == (B)(A) -- (AB)
2: ~, = swap cat
tack == (B)(A) -- (B(A))
2: >, = unit cat
k == (B)(A) -- A
3: ~-< = nip i
= swap z
rep == (A) -- AA
3: +,< = dup sap
take == (B)(A) -- (A(B))
3: ~>, = swap tack
run == (A) -- A(A)
4: +>,< = dup unit sap
= dup tack i
dip == (B)(A) -- A(B)
4: ~>,< = take i
cons == (B)(A) -- ((B)A)
4: ~>~, = swap unit swat
w == (B)(A) -- (B)(B)A
6: (+)~,< = (dup) swap sap
= (dip) swat i
7: ~>+,~,<
c == (C)(B)(A) -- (B)(C)A
6: (~)~,< = (swap) swap sap
= (swap) swat i
11: >~>~,~>,<~<
poke == (C)(B)(A) == (A)(B)
7: >~>,~-< = unit take k
peek == (B)(A) -- (B)(A)(B)
8: >(+)~,<~ = unit w swap
9: >~>+,~,<~
dig == (C)(B)(A) -- (B)(A)(C)
8: (~)~>,<~ = (swap) dip swap
9: >~>~,~>,<
bury == (C)(B)(A) -- (A)(C)(B)
8: ~(~)~>,< = swap (swap) dip
9: >~>,~>,<~
flip == (C)(B)(A) -- (A)(B)(C)
8: >~>,~>,<
9: ~(~)~>,<~ = swap dig
= bury swap
b == (C)(B)(A) -- ((C)B)A
9: (~>~,)~,< = (cons) swap sap
= (cons) swat i
13: >~>,~>,<>~,~<
sip == (B)(A) -- (B)A(B)
11: >(+)~,<~>,< = peek tack i
= unit w dip
12: >~>+,~,<~>,<
cake == (B)(A) -- ((B)A)(A(B))
12: >~>>,+<~,~< (by Garklein and Moja)
s == (C)(B)(A) -- ((C)B)(C)A
15: ((+>)~>,<,~)~,< (by Moja and Forth Truffle)
23: >~>,~>,<>>+,~>,<,>~,~,< (by Moja)
s' == (D)(C)(B)(A) -- ((D)C)A(D)B
25: ~(((>+)~>,<,~)~>,<~,<)~,< (by Moja)
30: ~>,>~>,~>>+,~>,<~>,<~,>~,~,<~< (by sakito system)
j == (D)(C)(B)(A) -- ((C)(D)A)(B)A
27: +>(>~>,)~,(~>~,)~(,),>,<~,< (by Garklein and Zhil)
j' == (E)(D)(C)(B)(A) -- ((D)A(E)B)(C)B
35: ~(~(~>~,~>,)~>,<)~>,<+(~(,)~>,<)~,< (by Garklein)