- This language is a work in progress. There may be changes in the future.
Clementine (CLM) is a four command simple translation of Underload (excluding output) discovered by User:Orby during May 2020.
Commands
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.
Pattern
|
Rewrite
|
[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
Command
|
Action
|
[
|
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.
Underload
|
CLM
|
!
|
[]k
|
a
|
[]e!!
|
~
|
ae!k
|
^
|
[]~k
|
*
|
e~!~!
|
:
|
[]e!*^
|
(
|
[
|
)
|
]
|
CLM
|
Underload
|
e
|
a~a*:(a~*)*~:(a*)*~(~*)***^
|
k
|
~!^
|
[
|
(
|
]
|
)
|
Restricted CLM
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.
Underload
|
CLM
|
!
|
[]k
|
a
|
[][][e]k!!
|
~
|
a[][e]k!k
|
^
|
[]~k
|
*
|
[][e]k~!~!
|
:
|
[][][e]k!*^
|
(!)
|
[]a[k]*
|
(a)
|
[]a[e]*(!)*(!)*
|
(~)
|
(a)[e]*(!)*[k]*
|
(^)
|
[]a(~)*[k]*
|
(*)
|
[e](~)*(!)*(~)*(!)*
|
(:)
|
[]a[e]*(!)*(*)*(^)*
|
Open questions
- 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?
See also