- This language is a work in progress. There may be changes in the future.
CLM is similar to Underload, but uses a different basis. CLM is composed of 4 commands: [, ], e and k.
The symbols e, k and the empty string are concatenative combinators. If a and b are concatenative combinators then [a] and ab are concatenative combinators.
CLM as a term rewriting language
CLM uses two rewrite rules. They are applied from left to right.
|[b] [a] e||[[b]a] [a[b]] [ba]|
|[b] [a] k||a|
where a and b are concatenative combinators.
CLM as a stack based language
|[||Begin a quote. To enclose a combinator in quotes means to push it onto the stack.|
|]||End a quote. To enclose a combinator in quotes means to push it onto the stack.|
|e||Pop a. Pop b. Push [b]a. Push a[b]. Push ba.|
|k||Pop a. Pop b. Execute a.|
Simple translation to Underload
Note that this is proof of Turing-completeness.
A restricted version of CLM that is quote free consists of the combinators , [e], [k] and k. It is Turing-complete by the following reduction to Underload.
- Is there a single concatenative combinator f with a single rewrite rule such that f combined with quoting is Turing-complete? What about "restricted f" with (), (f) and f?
- Does a three command simple translation of CLM exist?
- Does a two command simple translation of CLM exist?