Emmental

From Esolang

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.

[edit] Instruction set

(Emmental's instruction set can be redefined, so what follows is the initial instruction set.)

#     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
.     Pop symbol from the stack and output it
,     Input symbol and push it onto stack
^     Enqueue top element of stack.
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.)
        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.)
;     Push the symbol ';' onto the stack.

[edit] Computability class

Emmental is thought to be Turing-complete. Since there is no conventional way to specify a loop or a recursive function call, the method of interpreter-redefinition is required in order for Emmental to repeatedly execute an operation: an operation is redefined using that operation as part of its definition.

There is also no conventional conditional, however, the discrete log ~ in conjunction with the "eval" operation ? can be used to "branch" to one of nine operations.