Emmental

Emmental is an esoteric programming language designed by Chris Pressey in 2007.
Emmental is a self-modifying language. It is defined by a meta-circular interpreter (an Emmental interpreter described in Emmental.) The meta-circular interpreter provides an operation which modifies operations of the meta-circular interpreter.
Emmental is a stack-based language, but it also has a queue.
==Instruction set==
(Emmental's instruction set can be redefined, so what follows is the initial instruction set.)
Instruction	Description
# 	Push NUL (ASCII 0) onto stack.
0..9 	Pop symbol, multiply by 10, add 0..9 respectively, push back on.
+ 	Pop two symbols, add them, push back result.
- 	Pop two symbols, subtract first from second, push back result.
~ 	Pop symbol, push discrete base-2 log of symbol. As a special case, the discrete base-2 log of 0 is considered to be 8.
. 	Pop symbol from the stack and output it.
, 	Input symbol and push it onto stack.
^ 	Enqueue top element of stack without popping it.
v 	Dequeue symbol from queue and push onto stack.
: 	Duplicate top element of stack.
! 	Pop a symbol and an Emmental program (a string of symbols terminated by ;). Then redefine that symbol as having the same semantics as that Emmental program in the meta-circular interpreter.
? 	Pop a symbol and execute it (with the current interpreter). This is sometimes called the 'eval' operator.
; 	Push the symbol ; onto the stack.
==Examples==
===Infinite loop===
Go into an infinite loop. This is done by redefining 0 to mean #48?, and then executing 0.
 ;#35#52#56#63#48!0
===Cat program===
Redefines * (ASCII 42) to mean ,.#42? and executes *. This program is an infinite loop that does not observe EOF.
 ;#44#46#35#52#50#63#42!*
===Hello, World!===
Output "Hello, world!". This is done by pushing the ASCII representation of every character on to the stack, and then popping them off with the . operator.
 #0#10#33#100#108#114#111#119#32#44#111#108#108#101#72...............
Alternatively, this code performs a loop over the characters (rather than outputting each character individually.)
 ;#58#126#63#36!;#46#36#!;#0#1!;#0#2!;#0#3!;#0#4!;#0#5!;#0#6!;#0#7!#0#33#100#108#114#111#119#32#44#111#108#108#101#72$
===Conditional branching===
Emmental doesn't have explicit conditional statements, but the eval instruction ? can be used to "branch" by executing an instruction that depends on the symbol on top of the stack. The discrete base-2 log instruction ~ can be used in combination with eval: it basically maps the 256 possible symbols into 9 "equivalency classes" 0, 1, 2-3, 4-7, 8-15, 16-31, 32-63, 64-127 and 128-255.
The following programs display different approaches to conditional branching.
====Using the discrete log====
Input a character and report whether its ASCII value is congruent with 0, 1 or 2 modulo 3. This is done by repeatedly subtracting 3, and branching with the base-2 log.
Readable version	Emmental program
;0.#8!
;1.#0!
;
 ;2.'#'2'!
 ;0.'#'3'!
 '?
#1!
;'#'3'-':'~'?#2!
;'#'3'-':'~'?#3!
;'#'3'-':'~'?#4!
;'#'3'-':'~'?#5!
;'#'3'-':'~'?#6!
;'#'3'-':'~'?#7!
,:~?	;#35#52#56#46#8!
;#35#52#57#46#0!
;
 #35#53#57 #35#51#53#35#53#51#35#52#56 #35#52#54#35#50#33
 #35#53#57 #35#51#53#35#53#50#35#53#54 #35#52#54#35#51#33
 #63
#1!
;#35#51#45#58#126#63#2!
;#35#51#45#58#126#63#3!
;#35#51#45#58#126#63#4!
;#35#51#45#58#126#63#5!
;#35#51#45#58#126#63#6!
;#35#51#45#58#126#63#7!
,:~?
For better readability, the program has been written using the notation 'A for #65 (and so forth with every ASCII char). This is not a feature of the Emmental language, it is merely a convention adopted in this article to help understand the examples. With this notation:
* '0 means #48
* 0 means '#'4'8 which in turn means #35#52#56
* 0 means '#'3'5'#'5'2'#'5'6 which in turns means #35#51#53#35#53#50#35#53#54
Note the nested definitions of symbols 2 and 3 inside the definition of symbol 1: those symbols will be defined when symbol 1 is evaluated.
====Using implicit modulo 256====
Input a character and report whether its ASCII value is odd or even. This is done by multiplying it by 128.
Readable version	; '^'v ':!
; E'. #!
; O'. #128!
; ':'+':'+':'+':'+':'+':'+':'+
'm!
,m?
Emmental program	#59#94#118#58!#59#35#54#57#46#!#59#35#55#57#46#128!
#59#58#43#58#43#58#43#58#43#58#43#58#43#58#43
#109!,m?
====Using massive symbol redefinition====
Input a character and report whether its ASCII value is congruent with 0, 1 or 2 modulo 3. This is done by redefining every symbol to "subtract 3 and try again".
Readable version	Emmental code
; '#'4'8 '. #!
; '#'4'9 '. #1!
; '#'5'0 '. #2!
; '#'3'-':'? #3!
; '^':'-'#'5'9'+'#'3'v'! #4!
;
 '#'5'9 '#'3 '#'2'5'5'!
 ',':'?
#255!
; #4#4#4#4#4#4#4#4#4#4 #5!
; #5#5#5#5#5 #5!
; #5#5#5#5#5#4 #4!
#4
; ':'#'1'+ 'd!
; 'd'd'd'd'd'd'd'd'd'd 'd!
; 'd'd'd'd'd 'd!
; 'd'd'd'd'd #4 #255 'd!
d	; #35#52#56#46 #!
; #35#52#57#46 #1!
; #35#53#48#46 #2!
; #35#51#45#58#63 #3!
; #94#58#45 #35#53#57 #43#35#51 #118#33 #4!
;
 #35#53#57 #35#51 #35#50#53#53#33
 #44#58#63
#255!
; #4#4#4#4#4#4#4#4#4#4 #5!
; #5#5#5#5#5 #5!
; #5#5#5#5#5#4 #4!
#4
; #58#35#49#43 #100!
; #100#100#100#100#100#100#100#100#100#100 #100!
; #100#100#100#100#100 #100!
; #100#100#100#100#100 #4#255 #100!
d
* the symbols \0, \1 and \2 are defined to output '0', '1' or '2'.
* the symbol \3 is defined to "subtract 3 from top stack element, duplicate it, evaluate the copy", and the symbol \4 to "pop top stack element and define it to be a synonym of \3".
* the symbol \255 is defined to "redefine myself to be a synonym of \3; then take one char from input, duplicate it, evaluate the copy".
* the symbol \4 is redefined to "repeat \4 251 times"
* the value 4 is pushed on the stack
* the symbol d is defined to "duplicate top stack element and increment the copy"
* the symbol d is redefined to "repeat d 250 times, then \4, then \255"
* d
Note that all symbols are redefined to "subtract 3 and try again" when d is executed; for that reason, that occurrence of d must be the very last character in the program — even whitespace are not allowed.
===Truth-machine===
 ;#58#46#58#63#49!
 ,:.:?
===99 Bottles of Beer===
 ;#35#51#50#46#35#57#56#46#35#49#49#49#46#35#49#49#54#46#35#49#49#54#46#35#49#48#56#46#35#49#48#49#46#35#49#49#53#46#35#51#50#46#35#49#49#49#46#35#49#48#50#46#35#51#50#46#35#57#56#46#35#49#48#49#46#35#49#48#49#46#35#49#49#52#46#81!
 ;#35#51#50#46#35#49#49#49#46#35#49#49#48#46#35#51#50#46#35#49#49#54#46#35#49#48#52#46#35#49#48#49#46#35#51#50#46#35#49#49#57#46#35#57#55#46#35#49#48#56#46#35#49#48#56#46#82!
 ;#35#51#51#46#83!
 ;#35#52#52#46#85;
 ;#35#56#52#46#35#57#55#46#35#49#48#55#46#35#49#48#49#46#35#51#50#46#35#49#49#49#46#35#49#49#48#46#35#49#48#49#46#35#51#50#46#35#49#48#48#46#35#49#49#49#46#35#49#49#57#46#35#49#49#48#46#35#52#52#46#35#49#48#46#35#49#49#50#46#35#57#55#46#35#49#49#53#46#35#49#49#53#46#35#51#50#46#35#49#48#53#46#35#49#49#54#46#35#51#50#46#35#57#55#46#35#49#49#52#46#35#49#49#49#46#35#49#49#55#46#35#49#49#48#46#35#49#48#48#46#35#52#52#46#84!
 ;#35#49#48#46#78!
 ;#58#45#63#124!
 ;#94#124#94#124#118#118#10#94#124#94#124#10#118#58#35#52#56#43#46#94#124#10#118#58#35#52#56#43#46#94#124#10#118#118#80!
 ;#94#124#94#124#10#118#118#118#10#58#35#52#56#43#46#94#124#10#58#35#52#56#43#46#94#124#10#94#124#10#118#118#90!
 ;#35#49#45#32#58#32#35#50#48#48#32#43#32#63#68!
 ;#124#35#49#45#35#57#199!
 ;#124#58#32#35#50#51#48#43#63#32#35#48#200!
 ;#118#35#94#124#124#124#35#48#35#48#230!
 ;#80#81#82#85#78#10#80#81#83#78#10#84#78#10#35#55#54#32#94#124#32#68#10#90#81#82#83#78#78#10#118#63#76!
 #9
 #9
 L
==Computability class==
An Underload implementation in Emmental is available, generated by a Haskell program.
It is not quite an ordinary interpreter: It uses Emmental's metacircular evaluation principles to turn the Emmental interpreter into an Underload one. As such, the Underload program you wish to interpret should be appended to the Emmental one.
It supports all Underload commands, but not all Underload characters: By the necessities of this kind of Emmental programming, 10 byte values have been reserved for the interpreter's internal use. These are all non-printable control codes.
In any case I believe this proves Emmental Turing-complete. However it may happen to do so in a way which I have previously disagreed with Chris Pressey on whether it counts or not. :P
I also attempted to minimize the number of initial Emmental instructions used for this, based partially on certain challenges proposed in the Emmental distribution. In particular:
* It doesn't use the queue.
* It doesn't use the ~ or : instructions.
In fact, it only uses the initial instructions #1-.?! (and the special stack-separator function of ;).
==Implementations==
The Emmental reference interpreter is written in Haskell and can be found in the Emmental distribution on Codeberg. It also contains some example programs as test cases.
There is also an implementation in OCaml by User:Koen.
All three implementations are in the public domain.
==See also==
* Enema, another stack-based, instruction-rewriting esolang
* Mascarpone, a direct successor of Emmental
==External resources==
* 
* Emmentool, tool for turning text into emmental code. By User:Truttle1
Category:Languages
Category:Implemented
Category:Self-modifying
Category:Stack-based
Category:Turing complete
Category:2007