Mlatu-6

mlatu-6 is a concatenative esoteric programming language based on the theory of concatenative calculus. It is a subset of mlatu.

Language Overview

mlatu-6 is a term rewriting language consisting of 6 primitive operators (called combinators) and quotations. A quotation is a sequence of terms wrapped in parentheses. Since quotations and combinators are both terms, quotations can be nested arbtirarily. When a primitive appears directly after an appropriate amount of quotations, 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

There are also inert combinators which have no reduction, or, equivalently, take no arguments and return themselves. Inert combinators are written as letters of the Latin alphabet. They are primarily used to demonstrate the reduction behavior of combinators rather than serving as data.

Whitespace is entirely ignored.

Evaluation Order

mlatu-6 considers quotations as opaque pieces of data, as does mlatu. Reductions are performed one at a time. When evaluating an expression, it will only perform reductions on the outermost layer, not recursing into quotations. Since the combinators take a fixed number of arguments and only apply to quotations, the evaluation order does not matter.

An optimizing implementation may wish to evaluate the contents of quotes to reduce the amount of data being lugged around. This can cause issues, since quotes can contain fixed points (loops) within them. An implementation can solve this by simply not evaluate the contents of quotes until unwrapped (canonical behavior), not reducing the + or < combinators (since they are required for loops) within quotes, evaluating quotes in parallel (stopping when the quote gets unwrapped), keeping track of states, or any combination thereof.

Concatenative Theory

There are multiple bases for concatenative calculus. A particularly simple basis has the following stack operations: copy the top element (dup), pop it, wrap it in a quote, unwrap it from its quote, concatenate the top two quotes, and 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 for studying concatenative calculus.

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

~

When evaluated alone, this program simply reduces to itself, it is already fully reduced. When this program is put after two quotations, a reduction can be made. We say that the program has the stack effect (B)(A) -- (A)(B) (we swap around, remember?).

In general, if we have a program which performs some stack effect when it's put after some amount of quotations, we can refer to it as its own combinator and use it in larger programs.

Base Lengths

Now that we have a method of counting program length, we can take a concatenative combinator, figure out the smallest program with the same stack effect as the combinator, and consider the length of that program to be the length of the combinator. k which has the stack effect (B)(A) -- A has a length of 3, since the smallest program which implements it is ~-<.

The combinator cake with stack effect (B)(A) -- ((B)A)(A(B)) seems to have a minimal length of 12 thanks to the program >~>>,+<~,~<. In concatenative calculus, {k, cake} forms a complete base, just like our 6 primitive combinators form one, any combinator can be formed from either of these bases. We can add up the lengths of k and cake and arrive at a "base length" of 15. The 6 primitive combinator base has a base length of 6.

Now let's do something clever. Let's invent a new combinator as follows:

# = ,>+ (B)(A) -- ((B A))((B A))

Here's what this new combinator can do when combined with - and <:

- = -
< = <
> = ()#-
, = #-<
(...)~ = #((--(...)))#<<->,<>,<>,<
+ = ()#(<)~,<
~ = (>(-))~>,<>,>,+,<->,<

We can still get all 6 combinators from the 3! This means that {X, -, <} is a complete base with length 5! Isn't that cool?

It's still an open problem what the minimal base length is for a 2-combinator base.

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)
   29: >+>~,~>,<>~,>~,~>>,~>>,<,~,~<
 
 j' == (E)(D)(C)(B)(A) -- ((D)A(E)B)(C)B
   35: ~(~(~>~,~>,)~>,<)~>,<+(~(,)~>,<)~,< (by Garklein)

External Resources

• Interpreter by Eric James Parfitt