November 2007, Chris Pressey, Cat's Eye Technologies
Emmental is a self-modifying programming language. That is not to say that is a language in which programs are self-modifying; rather, it is the language itself, as defined by a meta-circular interpreter, that can be modified during the course of a running program. Indeed, this is how Emmental, without conventional conditional and repetition/recursion constructs, achieves Turing-completeness.
One way to attempt to define a language is by giving what's called a meta-circular interpreter (often shortened to "MCI" in this document.) This is an interpreter for some language which is written in that same language (or at least, a language which is very close to it.)
Meta-circular interpreters were a popular way to the describe the semantics of programming languages, especially LISP-like languages, and especially before the advent of denotational semantics. The term "meta-circular" was apparently coined by John C. Reynolds in his paper "Definitional Interpreters for Higher-Order Programming Languages" (1972 Proceedings ACM National Conference.)
Of course, in the real world, MCI's are not often used. They certainly can be used: if you have a working Scheme interpreter that came with your computer system, there is nothing stopping you from writing another Scheme interpreter in Scheme, and running your programs on your interpreter (which is itself running on your system's interpreter.) However, this is quite a bit less efficient due to the duplication of effort. A somewhat more realistic case might be if your system came with, say, a Scheme compiler. You might then feed your Scheme interpreter (written in Scheme) through that to make a native Scheme interpreter, and use that to interpret your programs. (In this setup, the interpreter is usually described as "self-hosting" rather than "meta-circular".)
But, as should be obvious, you already need an implementation of Scheme for your Scheme interpreter written in Scheme to be of much practical use to you. If your meta-circular interpreter is all you have, you won't be able to use it to run or understand Scheme programs. Because the MCI is defined in terms of itself, you'll need some other source of "understanding how it works" to make it complete. This understanding might come from an implementation in some other programming language, or a specification in some formal language, or a description in some natural language, or simply from intuition — but it has to come from somewhere.
Assuming that we do have that external source of understanding, the meta-circular interpreter can come in quite handy in codifying the semantics of the language. And, in Emmental's case, altering those semantics: Emmental's MCI supports operations which instruct Emmental's MCI to modify its behaviour.
To describe the structure of Emmental's MCI, we first examine the general structure of interpreters. If you've ever written a virtual machine executor in, say, C, you've noticed that it has the general form
pc = start;
while (!done) {
switch (instruction[pc]) {
case INSTR_ONE:
/* implement semantics of INSTR_ONE */
pc += advance(INSTR_ONE);
break;
case INSTR_TWO:
/* implement semantics of INSTR_TWO */
pc += advance(INSTR_TWO);
break;
/* ... */
case INSTR_HALT:
done = 1;
break;
default:
perror("Invalid opcode");
}
}
Note that advance() is some function that computes how far the
program counter is advanced on that instruction. This value is typically
+1 for most instructions, but more or less than 1 (and dependent on the
state of the program) for a handful of "branch" instructions.
Note also that advance() would not typically be implemented in C
as a function; I'm just showing it like this to emphasize the
regular structure.
From this we infer that the basic structure of an interpreter is a dictionary or map that associates program symbols with operations. There is some extra housekeeping like the fetch-execute cycle that surrounds this dictionary, but this can (hopefully) be handled mostly automatically, freeing us to concentrate on symbols and operations.
The symbols could be taken from any finite alphabet, but in Emmental, to keep things relatively simple, we'll just use the ASCII character set. (Actually, to be precise, this is the full 8-bit ASCII character set. Non-printable control characters are allowed, as are characters between 128 and 255, and each has a distinct meaning. But their representations are not defined.)
The operations can be thought of, abstractly, as functions which transform program states. Or they can be thought of, concretely, as segments of code — mini-programs which implement these functions. In the case of a meta-circular interpreter, these mini-programs would be written in the language being interpreted.
To extend this idea to a self-modifying meta-circular interpreter, the operations can be thought of as functions which transform both program states and interpreter definitions. (Alternatively, the interpreter definition could be thought of as part of the program state, although I feel that's a bit gorier a way to look at it, and I prefer the other view, at least for Emmental.)
In Emmental, most operations leave the interpreter definition unchanged. However, there is one operation which alters the interpreter definition, and it is this altered definition that is used to interpret the remainder of the program.
Emmental is essentially a stack-based language. (There's also a queue, but it's not as central.) All operations implicitly get data from, and implicitly deposit results back onto, a single stack. For orthogonality's sake, this stack may contain only ASCII symbols. (And note that trying to pop an empty stack, or dequeue an empty queue, is an error that aborts the program.)
Note that because we've established that an interpreter (at least, insofar as Emmental ever needs to know) is simply a map that takes symbols to operations, and that operations in Emmental are defined (meta-circularly) as Emmental programs, we can use the following notation to describe interpreters:
% → XYZ+*! & → 'ap'ag'ag
That is, the symbol %, when encountered in an Emmental
program, indicates an operation that
is defined by the Emmental program XYZ+*!, and so forth.
When a main Emmental program begins execution for the first time, it starts with what's called the initial Emmental interpreter. (This fact, of course, doesn't apply to any further point of execution inside an Emmental program, or execution of operations defined in Emmental's MCI, since these would be considered subprograms of a sort. These cases use whichever interpreter happens to be in force in that point in time.)
The inital Emmental interpreter is defined as follows:
a → a b → b c → c ...
That is, for every symbol x in the ASCII set,
x → x.
Doesn't tell us a lot about Emmental's semantics, does it? No. Nothing at all, really. But remember what I said about needing an external source of understanding, in order to actually get full value out of an MCI. And remember the purpose of Emmental's MCI: it is not there so much to help us understand Emmental, but to allow us to change Emmental, from inside an Emmental program.
And, for all that our description of the initial Emmental interpreter
is unhelpfully tautological, it is not incorrect: the semantics of
a can in fact be thought of as being defined by an Emmental
program that consists of only one instruction, a. This
happy state of affairs comes about because Emmental is stack-based;
the "signature" (the requirements for the "before" and "after" stacks)
of the symbol a is the same as the signature of the program
containing the single symbol a. No extra syntax to specify
arity and the like is necessary.
Above all, don't panic: we will describe what symbols like
a actually mean in Emmental, we'll just need to do it in something
besides Emmental. In fact, let's do that right now.
# pushes the symbol NUL (ASCII 0) onto the stack.
The symbols 0, 1, ... 9
pop a symbol from the stack, multiply its ASCII value by 10 modulo 256, add
the value 0, 1, ... 9 (respectively) to that value modulo 256, and
push the resulting symbol back onto the stack.
The upshot of these 11 operations is that you can push arbitrary
symbols onto the stack by spelling out their ASCII values in decimal.
For example, #64 pushes a @ onto the stack.
+ pops two symbols off the stack, adds together their
ASCII values modulo 256, and pushes the symbol with the resultant ASCII value
back onto the stack.
- pops two symbols off the stack, subtracts the ASCII value
of the first popped from the ASCII value of the second popped modulo 256,
and pushes the symbol with the resultant ASCII value back onto the stack.
~ ("log") pops a symbol from the stack, computes the discrete
base-2 logarithm of the ASCII value of that symbol,
and pushes the symbol with the resultant ASCII value back onto the stack.
The discrete base-2 logarithm of a number is the floor or integer part
of the base-2 logarithm of that number. Alternately, it is the number of
the highest bit position (starting with the LSB = bit position 0)
with a bit set when the number is viewed as binary.
Because the base-2 logarithm of the number 0 itself is undefined,
the number 0 is treated as 256 for this operation; its discrete base-2
logarithm is 8.
^ ("enqueue a copy") pops a symbol off the stack, makes a copy of it, pushes
it back onto the stack, and enqueues the copy onto the queue.
v ("dequeue") dequeues a symbol from the queue and pushes it onto the
stack.
Using these operations in combination, one can form "discard", "duplicate",
"swap", and other more advanced stack manipulation operations. For example,
assuming an empty queue and more than two elements on the stack, "swap" can
be accomplished with the code ^v^-+^^v^v^v-+^v-+^v-+vv.
Despite this fact, the operation : duplicates the top value
of the stack. (Emmental is not an absolutely minimal language; note, for
instance, that it has all ten decimal digits as operations when these
could surely have been defined in terms of only one or two operations.
The reasons for a seperate : operation are given below in the
section on Computational Class.)
. pops a symbol off the stack and sends it to the
standard output as an ASCII symbol.
, waits for an ASCII symbol to arrive on standard input,
and pushes it onto the stack.
First let's define what it means to pop a string off the stack.
Symbols are popped off the stack until a ; symbol is
found on the stack. The symbols popped off are considered a string
in the reverse order they were popped; i.e. the last symbol popped
is the first symbol of the string. The ; symbol is
popped off the stack, but is not made part of the string; it is simply discarded.
Since an Emmental program is a string, popping a program is the same as popping a string, just that the string is interpreted as a program.
! (sometimes called "supplant")
pops a symbol, which we call s, off the stack.
Then it pops a program t.
It then inserts the association s → t into the
interpreter definition. This overwrites whatever mapping of s might have
been in the interpreter definition previously. This new interpreter definition
is used for all subsequent execution (until it is changed again, of course.)
Note that ! does early binding. That is,
the meaning of each symbol in this program t is
the meaning of that symbol at the time ! is executed.
If some subsequent ! operation later changes the meaning of one
of the symbols that occurs in t, the meaning of t
is not changed. The semantics of t are "captured" or "frozen".
This implies, among other things, that supplanting some
symbol z with itself (a program consisting only of the symbol z)
is a no-op, because z's meaning, at the time that !
is executed, is invariably z.
? (sometimes called "eval") pops a symbol, which we call s, off the stack.
It then executes that symbol (interprets it as an operation)
with the interpreter currently in effect.
Note that ? does late binding. That is,
in contrast with !, ? never "freezes" the semantic
definition of the thing that it is executing. This is true even when
? occurs in a operation redefinition (i.e. the program
that supplanted some symbol's semantics when an ! was executed.)
This implies, among other things, that supplanting some symbol z
with the program that consists of instructions that push the ASCII value of
z onto the stack, followed by a ? instruction,
creates a cyclic meaning for z.
This is because the z that will be executed by the ?
will always be the present z, that is, the z
that is executing the ?.
For convenience's sake, ; pushes the symbol ;
onto the stack.
All other symbols are no-ops.
I believe Emmental is Turing-complete with only the operations that have been given so far, but I haven't proved it yet. All the elements are there, and although some of them are somewhat "cramped", they look viable.
If you want to try thinking about how you could write real programs (like a universal Turing-machine simulator) in Emmental, you might want to skip this section, since it contains "spoilers".
Repetition can be accomplished by assigning a symbol a cyclic semantics,
by use of a ? within a !. For example, we can
redefine the semantics of 0 to be #48?. This is
simply a program that pushes the symbol 0 onto the stack and
executes it with the current interpreter, and, since 0 has been
redefined to mean #48? in the current interpreter, this will
loop forever. The entire program to do this to 0 and run the
infinite loop is:
;#35#52#56#63#48!0
This technique can also be used to "jump" from one definition to
another, by using ? to execute some other symbol
at the end of a definition (that is, some symbol other than the symbol
being defined.)
Conditionals are a little more restrictive. The trick to them is,
strangely, the discrete log operator ~ in combination
with the eval operator ?. Since ~ maps
all symbols into a set of nine symbols, and ? executes
the symbol on the stack, ~? will execute one of the
symbols from ASCII 0 (NUL) to ASCII 8 (BS). We can then, for instance,
define NUL to do one thing, define SOH through BEL to do the same
as NUL, and define BS to do some other thing; this essentially
distinguishes between 0 (which executes BS) and every other value
(which executes NUL). Further, we can use this in conjunction
with - to compare two values for equality. So, for
example, a program which inputs a character, and outputs Y if
the character is M and N otherwise, would be:
#59#35#55#56#46#!;##1!;##2!;##3!;##4!;##5!;##6!;##7!#59#35#56#57#46#8!,#77-~?
In case NUL through BS are in use for some reason, we can always
add 9 to the result of the log (~#9+?)
to map the answer onto HT through DC1. Or, of course, any of
a great number of other arithmetical mappings of our choosing.
The most severe constraint is that there be 9 available symbols
to act as "destinations" for our "branch". Even if we never
overwrite one "branch" with another (and we can do that in Emmental!)
and even if we allocate one extra symbol to be the "launch point"
of the branch, we still have room for 25 branches in the ASCII
character set.
So these parts look good. If there's a problem, it's
with the queue. Specifically, the problem seems to be
the need to know the present size of the queue in order to do stack housework
like "duplicate" and the subsequent need for "duplicate" to achieve
"discard." (Duplicate can be defined as ^v, but this only
works when the queue is empty. Discard can be defined as duplicate plus
-+, but this only works when there are other elements below
the element being discarded. [This last point is not generally a problem
since we can push arbitrary values onto the stack before any
program.])
However, if it turns out that we need "duplicate" or "discard" in order to write routines that can handle a variable-sized queue — and that strikes me as likely — then it looks like we have a severe problem.
Here's one way I could try to deal with it. I could say that the queue
is local to the operation being defined (or the main program.)
Then you could define : to be ^v, and inside
:'s definition, the queue would always initially be empty,
so the definition would work.
But... we need the queue to store our global data. For example, if we are going to simulate a Turing machine, we'd need to use the queue to store the tape (perhaps "doubled up", with one symbol of each pair telling us "the next symbol is a simulated tape symbol" or "the next symbol is some housekeeping value.") We can't store the tape on just one stack. And, once you are looping in Emmental, you've left the "main program" forever; you're jumping from definition to definition, and each has their own queue. At best, you'd need to "dump" the queue onto the stack each time you switched definitions, and even then you'd need a loop to do that, and to loop you need to switch definitions. It's a royal mess.
So here's how I will deal with it. I will add a primitive duplicate
operation, :, to Emmental. Proving that Emmental is Turing-complete
is still, then, a challenge, although a doable-seeming challenge.
I will then propose a more formidable challenge: prove that
the language formed by removing the : operation from
Emmental is Turing-complete. (Equivalently, prove that the set of
Emmental programs that begin with ;#0#58! is Turing-complete.
The nice thing about Emmental is that you can always shoot yourself in
the foot — until you erase your pistol, that is.)
And if you really like a challenge, try proving that Emmental
without ~ is Turing-complete. I don't think that it is,
although it's possible for it to compute parity, at least (input a
symbol, output E if its ASCII value is even, and O if it's odd.
To accomplish this, multiply the input's ASCII value by 128 by adding 127
copies of it to it; this is modulo 256, so the only results can be
0 or 128. Define those operations to print out E and O respectively.
But that's as far as I've gotten.)
I would've liked to have given Emmental a ' or "
instruction similar to Funge's "quote" and "quote-mode" instructions;
instructions that treat one or more of the following symbols in the program
literally, pushing them, as symbols, onto the stack, instead of executing them.
However, such instructions are somewhat problematic, both theoretically and
(for the approach I took implementing Emmental) practically. There are
two ways of thinking about the problems that arise.
One is that the function which implements ' is given
access to the program text itself, and possibly the position within the program,
and it uses these to extract the "immediate mode" symbol past the '. This information
could be available because these pieces of information are considered extra arguments
to the function, or because they are (gorily) considered part of the overall
program state. Either way, this operation is given a lot of information to work with,
and for consistency (since we want to be all nice and neat and say that all operations
have the same signature so that our dictionary has a nice uniform type,) all operations
have access to this information. This is almost too much information; that is, it
is so much that operations don't really need the dictionary. We could just say
there is one operation, defined by a function, and that function is given the
current symbol and has to decide what it means through whatever means it likes.
This approach is very powerful, of course, but it's just not the style that
Emmental embodies. (In fact, the idea to view interpreters as dictionaries
was one of the foundational design choices for Emmental, to the point where I
started constructing a "little theory of interpreters as maps." It really
wasn't exploited as much as I think it could have been. If an interpreter is
a map of symbols to strings of symbols, it's much more tractable than an
opaque function would be; you can define all sorts of operations on them,
for example concatenating two interpreters (for all symbols s
in interpreter a and interpreter b,
c[s] → a[s]b[s] —
that sort of thing,) computing union or intersection of interpreters,
Cartesian product, etc.)
The other way of looking at it is to say that there are in fact
multiple meta-circular interpreters available inside Emmental, and symbols
like ' switch temporarily to an alternate MCI. This alternate MCI
interprets every symbol as "push this symbol", then reinstates the previous MCI.
I like this explication better than the one above — MCIs begin
to look a bit like continuations! — but to do it justice would take some
work. I envision a language where the program has fine control
over which MCI is in effect, possibly by keeping a map from symbols to MCIs,
or maybe even being able to push MCIs onto the stack.
This is a wee bit much for Emmental too though, and
perhaps I'll explore these possibilities in a future language.
You can make the argument that Emmental's way of being Turing-complete
is really nothing new: when you redefine some symbol, you're really just
defining a new function, and when you use ? to execute that
symbol from within its own definition, you're just making a recursive
function call.
Well, yes, you can make that argument. But it has to do with how you think
about "what is a language", I think. Does a Pascal program fragment which
defines a procedure called PrintFibonacci represent another
programming language, one different from Pascal? You could certainly
say that it does — it's
the language Pascal where the token PrintFibonacci has
some meaning that it doesn't have in Pascal.
In that view, any language where you can define procedures, or functions, or standard libraries, or the like, is an extensible language. But even languages where you can't define new procedures or functions is arguably an extensible language. Take some initial Brainfuck program fragment, for instance. After it executes, it leaves the Brainfuck tape and while-stack in some state that depends on the input. Any Brainfuck fragment that executes after that, will execute in that environment, and that environment is arguably a version of the language Brainfuck, suitably extended.
You don't normally think of it that way, I bet, but you could — and you would need to, to some degree, to claim that Emmental is "just" defining new functions. The reason you don't typically look at languages like this (unless you are very strange) is because it's much more useful to divide the world into "languages" and "programs." And Emmental does make this division, it just makes it in a slightly different place than usual.
As far as I'm concerned, if I describe what Emmental does as modifying the Emmental language via its MCI, and what Emmental actually does is consistent with the idea of modifying the Emmental language via its MCI, then what Emmental effectively does is modify the Emmental language via its MCI. And if it needs to do this in a certain way in order to simulate a universal Turing machine, then that difference (however slight) sets it apart from systems where this simulation needs to be done by defining recursive functions.
emmental.hs is a reference interpreter for Emmental
written in Haskell. Run the function emmental on a
string; you can also run debug on a string to view
the state of the program (stack & queue) during execution.
(Note that debug is not able to show
program states that occur internal to an operation.)
Happy interpreter-redefining!
Chris Pressey
Chicago, IL
November 11, 2007