Clementine

From Esolang
Jump to navigation Jump to search
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