Clementine

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

• Underload was the first esoteric programming language of this sort.
• The Theory of Concatenative Combinators was a major inspiration for this language.