Try it online @ catseye.tc | Wiki entry @ esolangs.org | See also: Emmental
You are lost in a twisty maze of meta-circular interpreters, all alike.
Mascarpone is a self-modifying programming language in the style of Emmental. In fact it is a rationalization and further exploration of some of the basic ideas behind Emmental. In Mascarpone, meta-circular interpreters are "first-class objects": they can be pushed onto the stack, have operations extracted from and installed into them, and can themselves be meta-circularly extracted from the language environment ("reified") or installed into it ("deified.") New operations can be defined as strings of symbols, and these symbols are given meaning by an interpreter that is "captured" in the definition, similar to the way that lexical variables are captured in closures in functional languages. An operation may also access, and modify, the interpreter that invoked it.
Like Emmental, Mascarpone relies on meta-circular interpreter-modification to achieve Turing-completeness. Unlike Emmental, Mascarpone is purely symbolic; there are no arithmetic instructions.
Like Emmental, Mascarpone is a stack-based language. Unlike Emmental, Mascarpone's stack may contain things other than symbols. A stack element in Mascarpone may be a symbol, an operation, or an interpreter.
Strings are popped off Mascarpone's stack slightly differently than
Emmental's. A string begins with the symbol ] on the stack; this is
popped and discarded. Symbols are then successively popped and prepended
to a growing string. As further ]'s are encountered, they too are
prepended to the string, but the nesting level is incremented for each
one as well. Whenever a [ is encountered, it is prepended to the
string and the nesting level is decremented, unless it is zero, in which
case the [ is discarded and the string is complete. The net effect of
all this futzing around is that [] work as nestable quoting symbols.
Also unlike Emmental, Mascarpone does not have a queue.
The idea of an interpreter in Mascarpone is similar to that in Emmental. In Mascarpone, an interpreter is a map that takes symbols to operations, and an operation is a sequence of symbols that is given meaning by some interpreter.
Of course, this is a circular definition, but that doesn't seem unreasonable, since we're working with meta-circular interpreters. If you like, you can think of it as forming an "infinite tower of meta-circular interpreters," but that's never been a really satisfying explanation for me. As I explained in the Emmental documentation, I think you need some source of understanding external to the definition in order to make complete sense of a meta-circular interpreter. (I also happen to think that humans have some sort of innate understanding of interpretation — that is, language — so that this demand for further understanding doesn't recurse forever.)
There is a special interpreter in Mascarpone called "null". It is an error to try to interpret anything with this interpreter. Expect that any program that tries to do this will come crashing to a halt, or will spin off into space and never be heard from again, or something equally impressive.
Every interpreter (except for null) is linked to a "parent" interpreter (which may be null.) No interpreter can be its own ancestor; the parent-child relationships between interpreters form a directed, acyclic graph (or DAG.)
There is, at any given time in a Mascarpone, a current interpreter: this is the interpreter that is in force, that is being used to interpret symbols. The parent interpreter of the current interpreter is generally the interpreter that was used to execute the current operation (that is, the operation currently being interpreted; it consists of a string of symbols is interpreted by the current interpreter.)
The current interpreter when any top-level Mascarpone program begins is the initial Mascarpone interpreter, which is described in English in the next section.
v ("reify") pushes the current interpreter onto the stack.
^ ("deify") pops an interpreter from the stack and installs it as the
current interpreter.
> ("extract") pops a symbol from the stack, then pops an interpreter.
It pushes onto the stack the operation associated with that symbol in
that interpreter.
< ("install") pops a symbol from the stack, then an operation, then an
interpreter. It pushes onto the stack a new interpreter which is the
same as the given interpreter, except that in it, the given symbol is
associated with the given operation.
{ ("get parent") pops an interpreter from the stack and pushes it's
parent interpreter onto the stack.
} ("set parent") pops an interpreter i from the stack, then pops an
interpreter j. It pushes a new interpreter which is the same as i,
except that it's parent interpreter is j.
* ("create") pops an interpreter from the stack, then a string. It
creates a new operation defined by how that interpreter would interpret
that string of symbols, and pushes that operation onto the stack.
@ ("expand") pops an operation from the stack and pushes a program
string, then pushes an interpreter, such that the semantics of running
the program string with the interpreter is identical to the semantics of
executing the operation. (Note that the program need not be the one that
the operation was defined with, only equivalent to it, under the given
interpreter; this allows one to sensibly expand "intrinsic" operations
like those in the initial Mascarpone interpreter.)
! ("perform") pops an operation from the stack and executes it.
0 ("null") pushes the null interpreter onto the stack.
1 ("uniform") pops an operation from the stack and pushes back an
interpreter where all symbols are associated with that operation.
[ ("deepquote") pushes a [ symbol onto the stack and enters "nested
quote mode", which is really another interpreter. In nested quote mode,
each symbol is interpreted as an operation which pushes that symbol onto
the stack. In addition, the symbols [ and ] have special additional
meaning: they nest. When a ] matching the first [ is encountered,
nested quote mode ends, returning to the interpreter previously in
effect.
' ("quotesym") switches to "single-symbol quote mode", which is really
yet another interpreter. In single-symbol quote mode, each symbol is
interpreted as an operation which pushes that symbol onto the stack,
then immediately ends single-symbol quote mode, returning to the
interpreter previously in effect.
. pops a symbol off the stack and sends it to the standard output.
, waits for a symbol to arrive on standard input, and pushes it onto
the stack.
: duplicates the top element of the stack.
$ pops the top element of the stack and discards it.
/ swaps to the top two elements of the stack.
As you can see, Mascarpone's semantics and initial operations are a lot
less "fugly" than Emmental's. It's a more expressive language, in that
it's easier to elegantly convey things involving interpreters and
meta-circularity in Mascarpone than it is in Emmental. It explores at
least one idea that I explicitly mentioned in the Emmental documentation
that I'd like to explore, namely, having multiple meta-circular
interpreters and being able to switch between them (and lo and behold,
Mascarpone has very well-developed [] and ' operations.) It's also
"prettier" in that there's more attention paid to providing duals of
operations (both * and @, for example.)
Mascarpone also appears to be Turing-complete, despite the lack of
explicit conditional, repetition, and arithmetic operators. A cyclic
meaning can be expressed by an operation which examines its own
definition from the parent interpreter of the current interpreter and
re-uses it. A conditional can be formed by creating a new interpreter in
which one symbol, say S, maps to an operation which does something,
and in which all other symbols do something else; executing a symbol in
this interpreter is tantamount to testing if that symbol is S.
"But", you point out, "Mascarpone only has one stack! You need at least
two stacks in order to simulate a Turing machine's tape." Actually,
Mascarpone does have another, less obvious stack: each interpreter has
a parent interpreter. By getting the current interpreter, modifying it,
setting it's parent to be the current interpreter, and setting it as the
current interpreter (in Mascarpone: v...v}^), we "push" something
onto it; by getting the current interpreter, getting its parent, and
setting that as the current interpreter (v{^), we "pop".
Actually, even if there was no explicit parent-child relationship between interpreters, we'd still be able to store a stack of interpreters, because each operation in an interpreter has its own interpreter that gives meaning to the symbols in that operation, and that interpreter can contain operations that can contain interpreters, etc., etc., ad infinitum. This isn't a very classy way to do it, but it's very reminiscent of how structures can be built in the lambda calculus by trapping abstractions in other abstractions.
It's also worth noting that this is how you'd have to accomplish arithmetic, with something like Church numerals done with interpreters and operations, since Mascarpone has nothing but symbols. On the plus side, this means Mascarpone, unlike Emmental, is highly independent of character set or encoding — it doesn't even have to be ordered. Any set of symbols that contains the symbols of the initial Mascarpone interpreter, plus the symbols appearing in the Mascarpone program being executed, plus the symbols that are desired for input and output, ought to suffice.
Actually, that's not quite true: it should be a finite set. This is
mainly for the sake of the definition of the ' operator: it switches
to an interpreter where all symbols indicate operations that push that
symbol on the stack. From this we can infer that there should either be
a finite number of such operations (and thus symbols,) or somehow these
operations know what symbol they are to push. They take the symbol that
invoked them as an argument, perhaps. But other operations in Mascarpone
do not have such capabilities: an operation need not even be invoked by
a symbol, as it could be invoked by the ! operation, for instance.
That would make the operations in the ' interpreter gratuitously
special. And, practically, most character sets, on which sets of symbols
are based, are finite, so I don't suppose this restriction is much of a
problem.
One further, somewhat related design decision deserves mention. Any
symbol which is not defined in the initial interpreter is interpreted as
a no-op. It probably would have been nicer to treat it as an explicit
error-causing operation. This could be extended to looking, inside each
putative definition, for symbols undefined in the desired interpreter
when executing a * operation, and causing a (preferably intelligible)
error early in that case. Semantics like this would have helped me save
time in debugging one or two of the test case programs. However, while
Mascarpone is arguably supposed to be less hostile than Emmental when it
comes to being programmed in, it's certainly still not what you'd call a
mainstream programming language, so while I'm somewhat irked by this
deficiency, I hardly consider it a show-stopper.
There are definitely two related works that are worth mentioning: Brian Cantwell Smith's Ph.D. thesis "Procedural Reflection in Programming Languages" (MIT, 1982,) and Friedman and Wand's paper "Reification: Reflection without Metaphysics" (ACM LISP conference, 1984.) (Forgive me for not giving proper, perfectly-formatted, Turabianly-correct references to these two works, but frankly, this is the age of the Internet: if you're interested in either of these papers, and you can't find them, there's something wrong with you! If, on the other hand, you don't have access to them, perhaps there's something wrong with the institutions whose assumed goal is to increase the amount of human knowledge — but not, it seems, to widen its availability.)
It's hard to say how much influence Smith's 3-LISP language and Friedman and Wand's Brown language (introduced in the respective papers) have had on Mascarpone: probably some, since I had read both of them (well, not all of Smith's monster! but enough of it to grasp the main ideas, I think) and thought about what they were trying to convey. (What Brown calls "reflection" I've called "deification" to give a sort of phonological dual to "reification". Also, the term "reflection" seems to have taken on a more general meaning in computer science since the '80's, so I wanted to avoid its use here.) But that was a couple of years previous, and the subject of meta-circular interpreters came up this time from a different angle; Mascarpone came primarily from trying to "un-knot" the ideas behind Emmental, which itself came to be, quite indirectly, from thinking about issues raised by John Reynolds' original work on meta-circularity.
Certainly a huge difference that sets Mascarpone apart is that 3-LISP and Brown are caught up in the whole LISP/Scheme thing, so they just use S-expressions and functions to represent reified interpreter parts, which include environments and continuations. Mascarpone, on the other hand, reifies whole interpreters at once, as values which are complete interpreters. Because interpreters contain operations which contain interpreters ("ad infinitum", one might think,) this approach seems to highlight the meta-circularity in a way that is particularly striking. In addition, Mascarpone's "applicative" organization (like XY or Joy; that is, like an idealized version of FORTH) lets it avoid some of the referential issues like names and environments, and gives a nice direct one-symbol-one-operation correspondence.
Because Mascarpone has interpreters as first-class values, it is never
obliged to make the guts of the running interpreter explicit during
reification — it just needs to make that interpreter available as a
value. The contract of the @ operation (which, by the way, was a
somewhat late add to the language design, fulfilling the desire for a
dual to *) says you get a program and an interpreter with semantics
equivalent to the operation you specify, but it doesn't say how
they're provided. You could successively perform @ on an intrinsic
operation (like, say, @ itself) and get successively more explicit
definitions, written in Mascarpone, of what @ means. Each one could be
thought of as descending (or ascending? does it matter?) a level in that
infinite tower dealie. Or, you might only get back a single, random
symbol, and an interpreter where all symbols have the semantics of @,
with no explanation whatsoever. This inbuilt ambiguity is, I think, the
appropriate level of abstraction for such an operation (in a
meta-circular context, anyway;) saying that you always get back the
program you defined the operation with seems overspecified (and unable
to handle the case of intrinsics,) and saying that you always get back
something opaque, like a function value, seems quite nonplussing in the
context of an interpreter that can supposedly examine its own structure.
It's not clear to me that either 3-LISP or Brown addresses this point to
this degree.
And of course, neither 3-LISP nor Brown tries to use reification and deification as a means of achieving Turing-completeness in the absence of conventional conditional and repetition constructs.
mascarpone.hs is a reference interpreter for Mascarpone written in
Haskell. Run the function mascarpone on a string, or demo n to run
one of the included test cases. mascarpone.hs also has a much nicer
debugging facility than emmental.hs; you can run debug on a string
to view the state of the program (the current instruction, the rest of
the program, the stack, and the current interpreter) at each step of
execution. And you can run test n to debug the test cases. Lastly,
there is a main function that runs mascarpone on a string read from
a file named by the first argument, so a Haskell compiler can be used to
build a stand-alone Mascarpone interpreter from this source code.
Even happier interpreter-redefining!
Chris Pressey
Chicago, IL
December 8, 2007