mlatu

mlatu

Paradigm(s)	functional, concatenative, pointfree, rewriting, declarative
Designed by	Caden Haustein
Appeared in	2021
Type system	untyped
Computational class	Turing complete
Reference implementation	mlatu
Major implementations	readable-mlatu
Dialects	generalised Mlatu, readable mlatu
Influenced by	catlangwiki:Cat, catlangwiki:Joy, concatenative calculus
Influenced	mlatu-6
File extension(s)	.mlt, .mlb

mlatu (also cased Mlatu) is a concatenative programming language based on concatenative calculus with added support for atom rewriting rules. It is paired with a custom terminal text editor specifically designed for writing mlatu code. The name "mlatu" comes from the word for cat in the logical language Lojban, punning on "concatenative" and languages like Cat.

Syntax and semantics

The core of the language is based on six simple operators called combinators from the theory of concatenative calculus. mlatu programs are expressions made up of terms. Each term can either be a combinator, an atom, or a quote of zero or more terms. Since quotes can nest, they are denoted with parentheses. Atoms (or words) are denoted with any string of characters that does not contain whitespace, parentheses, or the primitive combinators. Atoms are inert on their own, they are irreducible unless there are pattern matching rules which replace them.

Combinators operate on quotes. Each combinator takes in either one or two quotes preceding it, and replaces the quotes with some new expression without the combinator. Note in this listing, A and B may be any sequence of zero or more terms.

Combinator	Name	Redex	Reduction
+	duplicate	(A)+	(A)(A)
-	remove	(A)-	empty
>	quote	(A)>	((A))
~	swap	(A)(B)~	(B)(A)
<	unquote	(A)<	A
,	concat	(A)(B),	(A B)

Pattern matching rules match patterns of atoms and rewrite them into a list of terms. They specifically match atoms, they cannot match quotes.

mlatu has opaque quotation, meaning the contents of quotes are made inert. Combinators or patterns cannot be rewritten if inside a quote.

Evaluation happens from left to right on the outermost layer of the expression (since it does not recurse into quotes). Every step, the evaluator will find the leftmost longest redex and reduce it to yield a new expression. The longest redex is found by starting at the first term and considering if the entire rest of the string is part of it, if not, it considers if all but the last term is, etc. If no redex was found for the first term, it tries with the second, then the third, etc. If no redex was found in the expression, the expression is considered to be in normal form and evaluation ends.

Pseudocode for the evaluation order:

for start in 0..length(expression) // index terms at the uppermost layer, left to right
    for end in length(expression)..start // try the longest subsequence first
        redex = expression.slice(start, end)
        if redex in patterns:
            return reduce(expression, patterns[redex], start, end)
        if redex is combinator expression:
            return reduce(expression, combinators[redex], start, end)
return FINISHED

Concatenative calculus is confluent, meaning that without evaluation order, expressions which rewrite to a normal form (one with no further reductions) will only ever have one eventual normal form, regardless of the order in which reductions are made. This mirrors the Church-Rosser theorem of lambda calculus (and is often called the Church-Rosser theorem or property when applied elsewhere). mlatu's pure calculus portion, without pattern matching rewrite rules, is also confluent since it is simply an alternate notation for concatenative calculus.

mlatu's pattern matching deviates from confluence, meaning that a given expression can be rewritten into multiple normal forms, each of which cannot be reduced to a further common form. Consider the program:

a b = c.
b c = a.

a b c

Without evaluation order, the string a b c may be rewritten to either c c or a a, with both of those expressions lacking a further reduction, meaning mlatu is not confluent. With the standard evaluation order, the expression deterministically rewrites to c c.

History

Prior versions of mlatu had a vastly different syntax than the current iteration. Included were function definitions, typing, lists, builtin numbers, and various other features. It originally used Prolog as a backend, then switched to Erlang. The official implementation is now an interpreter, rather than bytecode compiler.

Computational class

mlatu's combinators form a complete basis, meaning that any combinator can be expressed in terms of them. Since combinatory logic is Turing complete, and mlatu can create any combinator, mlatu is itself Turing complete. Interestingly, mlatu's combinators are even complete without ~ (swap).

Additionally, mlatu's pattern matching feature also confers Turing completeness on its own. The argument is similar to proofs of the universality of Markov algorithms.

This means that mlatu can be cleaved into two distinct Turing complete languages. mlatu-6 is effectively an isolation of mlatu's calculus portion.

See also

• mlatu-6 for expressions of various concatenative combinators without pattern matching

External links

• mlatu's official implementation (Rust): https://github.com/mlatu-lang/mlatu
• mlatu implemented in C, with support for importing files (readable mlatu): https://github.com/mlatu-lang/readable-mlatu
• Official mlatu introduction: https://mlatu-lang.github.io/mlatu/
• Mlatu at the concatenative language wiki
• mlatu implemented in Paka: https://github.com/ShawSumma/litter
• Dialect of mlatu supporting quote matching rules (generalised Mlatu, C++): https://github.com/Jackojc/unreadable-mlatu