Due to work stuff, I’m very busy this week, and I don’t have time to write a detailed
pathological language post, so I chose something that doesn’t take a lot of explanation, but
which is delightfully twisted. It’s a language called [Muriel](http://web.archive.org/web/20021205092706/http://demo.raww.net/muriel/), aka
the *”Monumentally Useless ReIterative Execution Language”.
Muriel is based on the idea of [*quines*](http://www.nyx.net/~gthompso/quine.htm). A quine for a programming language is a program in that language which produces itself as output. Quines are
considered interesting puzzles in some circles, which has led to generation of huge collections of quines in just about every imaginable programming language. Follow the link above to see one such collection. Muriel takes things a step further: instead of quines being an interesting (if pointless) challenge, in
Muriel, they’re an essential part of the language!
To give you a sense of what a quine looks like, here’s a fairly verbose but easy-to-follow quine in Java:
public class Myself {
static String[] me = {
“public class Myself {“,
” static String[] me = {“,
” };”,
” static char quote =”,
” public static void main(String argv[]) {“,
” for (int i = 0; i < 2; i++)",
" System.out.println(me[i]);",
" for (int i = 0; ; ) {",
" for (int j = 0; j < 4; j++)",
" System.out.print(' ');",
" System.out.print(quote + me[i] + quote);",
" if (++i == me.length) {",
" System.out.println();",
" break;",
" }",
" System.out.println(',');",
" }",
" for (int i = 2; i <= 3; i++)",
" System.out.println(me[i]);",
" for (int i = 0; i < 4; i++)",
" System.out.print(' ');",
" System.out.print(''');",
" System.out.print(quote);",
" System.out.print(''');",
" System.out.println(';');",
" for (int i = 4; i < me.length; i++)",
" System.out.println(me[i]);",
" }",
"}"
};
static char quote =
'"';
public static void main(String argv[]) {
for (int i = 0; i < 2; i++)
System.out.println(me[i]);
for (int i = 0; ; ) {
for (int j = 0; j < 4; j++)
System.out.print(' ');
System.out.print(quote + me[i] + quote);
if (++i == me.length) {
System.out.println();
break;
}
System.out.println(',');
}
for (int i = 2; i <= 3; i++)
System.out.println(me[i]);
for (int i = 0; i < 4; i++)
System.out.print(' ');
System.out.print(''');
System.out.print(quote);
System.out.print(''');
System.out.println(';');
for (int i = 4; i < me.length; i++)
System.out.println(me[i]);
}
}
A more twisted example is the following C which is *almost* a one-liner (it would be a one-liner
if it weren't for the fact that the author wanted it to be *valid* ANSI C).
#include
main(){char*c=”\”#include%cmain(){char*c=%c%c%c%.102s%cn%c
;printf(c+2,c[102],c[1],*c,*c,c,*c,c[1]);exit(0);}n”;printf(c+2,c[10
2],c[1],*c,*c,c,*c,c[1]);exit(0);}
So, what does this stuff have to do with Muriel?
The only control structure in Muriel is “evaluate string as program”. What that means is that the
only way to make a loop in Muriel is to create a subprogram which is a quine for the loop. Without
quining, Muriel is a simple rotten programming language that isn’t even turing complete. *With* quining, Muriel is *still* a simple rotten programming language – but it *is* turing complete.
Ok, time for a quick look at the language.
* There are two kinds of variables in Muriel: string-valued variables and integer-valued variables. String valued variables are written as upper case letters; integer variables as lower case letters.
* Assignment in Muriel is written with the colon character, as in `a:3` or `B:”Foobar”`.
* The “.” character is a print statement, which only outputs strings; e.g., `.A` or `.”Hello there”`.
* The “@” character is the execute-string-as-program command. It takes a string, and executes
that string as a Muriel program, *replacing the currently executing program*. There is *no*
communication between the caller and the callee – no parameters, no shared variables: everything
has to be coded into the string being executed.
* Muriel of course includes the usual arithmetic operators for integers: `+`, `-`, `*`, `>`, `0*&Z”;
Z:”b:”+$b+Q+|Q+””;nR:””+|R+R;
@%Z,0,b>0*&Z
The first couple of lines are pretty simple: set b to 99, print out a verse of the song, decrement b.
The sixth, seventh, and eighth lines of the program are the nightmare: a mess which really just
quines up the program, but with the decremented value of b. Finally, in the 9th line, it checks if “b” is 0; if not, then it executes the quine that it generated.
For a *real* nightmare,
[this](http://web.archive.org/web/20020705102824/demo.raww.net/muriel/bub.txt) is basically a
brainfuck interpreter written in Muriel. (It’s not *quite* BF; it’s a variant called “Bub”. In order
to avoid needed to do the position recording of the BF loop operator, it uses a conditional “goto”
statement; translating BF programs to Bub is trivial.)
P:”000100120022003200420052006200720082009202360110012201320142015201620172018201920201021301170230024502510262027202820292030203120322042603400352036203720382039104030347042004320445045204620472048204920502051205250535054205520562057506160593059706110622063206420652066206720682069207960710072207320742075207610773071707900805081108220832084208520862087208820892090209120922102609400952096209720982099210011013094710201035104110521062107210821092110211121122121611401152116211721181119311471210122512321242125212651273128312931303131313231335134313531363137313831393140314131425146614431447146114721482149215021512152215321542164615601572158215921602161116231567164016521665170616831687170217121722173217421752176217721782179218051818″;
M:”0 “;
c:0;
I:” “;
d:0;
A:”??????????n??n?????????????????? !”#$%&'()*+,-./0123456789:;?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~”;
w:4;
N:(%P,c*w,(c*w)+w);S:(%N,w-1,w);
Q:”P:””+|P+””;nM:””+M+””;nc:”+$c+”;nI:””+|I+””;nd:”+$d+”;nA:””+|A+””;nw:”+$w+”;nc:c+1;nl:#(%M,d,d+3);n”;
G:”d:d-3;”;
Q:Q+(%G,0,&G*(#S=0));
G:”d:d+3;M:M+(%”0 “,0,(d=&M)*3);”;
Q:Q+(%G,0,&G*(#S=1));
G:”;F:(%($(l+1)+” “),0,3);M:(%M,0,d)+F+(%M,d+3,&M);”;
Q:Q+(%G,0,&G*(#S=2));
G:”F:(%($(l-1)+” “),0,3);M:(%M,0,d)+F+(%M,d+3,&M);”;
Q:Q+(%G,0,&G*(#S=3));
H:”I:~;”;
G:(%H,0,&H*(&I=0))+”M:(%M,0,d)+(%I,0,3)+(%M,d+3,&M);I:(%I,3,&I);”;
Q:Q+(%G,0,&G*(#S=4));
G:”.(%A,l,l+1);”;
Q:Q+(%G,0,&G*(#S=5));
j:#(%N,0,w-1);
G:”c:(c*(1-(l=0)))+(“+$j+”*(l=0));”;
Q:Q+(%G,0,&G*(#S=6));
G:”c:(c*(l=0))+(“+$j+”*(1-(l=0)));”;
Q:Q+(%G,0,&G*(#S=7));
G:”@” “”;
Q:Q+(%G,0,&G*(#S=8));
R:”N:(%P,c*w,(c*w)+w);nS:(%N,w-1,w);nQ:”P:\””+|P+”\”;\nM:\””+M+”\”;\nc:”+$c+”;\nI:\””+|I+”\”;\nd:”+$d+”;\nA:\””+|A+”\”;\nw:”+$w+”;\nc:c+1;\nl:#(%M,d,d+3);\n”;nG:”d:d-3;”;nQ:Q+(%G,0,&G*(#S=0));nG:”d:d+3;M:M+(%\”0 \”,0,(d=&M)*3);”;nQ:Q+(%G,0,&G*(#S=1));nG:”F:(%($(l+1)+\” \”),0,3);M:(%M,0,d)+F+(%M,d+3,&M);”;nQ:Q+(%G,0,&G*(#S=2));nG:”F:(%($(l-1)+\” \”),0,3);M:(%M,0,d)+F+(%M,d+3,&M);”;nQ:Q+(%G,0,&G*(#S=3));nH:”I:~;”;nG:(%H,0,&H*(&I=0))+”M:(%M,0,d)+(%I,0,3)+(%M,d+3,&M);I:(%I,3,&I);”;nQ:Q+(%G,0,&G*(#S=4));nG:”.(%A,l,l+1);”;nQ:Q+(%G,0,&G*(#S=5));nj:#(%N,0,w-1);nG:”c:(c*(1-(l=0)))+(“+$j+”*(l=0));”;nQ:Q+(%G,0,&G*(#S=6));nG:”c:(c*(l=0))+(“+$j+”*(1-(l=0)));”;nQ:Q+(%G,0,&G*(#S=7));nG:”@\” \””;nQ:Q+(%G,0,&G*(#S=8));nR:””;
Z:””;nX:Q+R+|R+”\”;Z:\””+|Z+Z;n@X”;
X:Q+R+|R+””;Z:””+|Z+Z;
@X
Don’t ask me to explain that mess. I’ve got a faint clue of how it works, but there’s not a chance in hell that I could explain it in any coherent way. In fact, I’m pretty sure that *no one* can explain it in a coherent way, because it’s fundamentally incoherent.
But fun, in a twisted way.
Not that it has anything to do with Muriel, but a haskell quine can be quite simple:
(x -> putStr (x ++ show x))”(\x -> putStr (x ++ show x))”
quine in python:
“”
The classic quine in BASIC (circa 1963) is
10 LIST
which outputs its source program.
Woo, that stuff certainly messed up the formatting of the site!
That is by far the most difficult language I’ve ever seen so far. Still quite interesting, though.
By the way, it’s generally accepted that null programs and programs which directly access their source code aren’t true quines. By that, the Python quine would probably be deemed invalid (it’s not *quite* null, but close enough), and so would the BASIC quine.
I need to go looking for the site again, but there was a very interesting quine site I saw that explained that all Turing-complete languages have quine capability – it’s not just an ability reserved for languages with certain special qualities. It’s a mathematical property of Turing-completeness.
Yep. It’s a simple application of the Recursion Theorem from computability theory.
In any Turing complete language, given a computer program (program A), it’s very easy to write a program (program B) that produces A as output. In fact, you could easily write a program (program C) that does that for you: C takes A as input and outputs B.
The Recursion Theorem says that any program which takes a program as input and outputs another program has an effective fixed point. By effective fixed point, I don’t mean that the input and output are identical, but rather that they have the exact same behaviour as programs.
So take Q an effective fixed point for C. Then Q and C(Q) do the exact same thing, and C(Q) was constructed to output Q. So Q must output Q, making it a quine.
Let me see if I get this straight: Mark says that quining makes Muriel TC, and conversely TC makes a program quine?
That one is one of those off tangent math things that probably will stick. I’m reminded of the statement that a memory implies that a part of the system must have an amplification A > 1. (I read it once, but the reference given was some old print I never accessed. If someone has a current reference, it would be appreciated!)
It tied in with some old work of mine on some obscure process systems with hysteresis (dynamic memory). While amplification obviously was the reason for the strong non-linearity, it wasn’t obvious that there was such a universal property in the model. But sure enough, it was there all along!
The odd (or mad 🙂 things you learn…
Torbjön:
You’ve *almost* got it. In computation theory, one of the requirements of a turing complete effective computing system is that it be capable a kind fixed point capability, and fixed point capability in a language for an ECS implies that you *can* write a quine in the language.
Muriel just short-circuits that process a bit. It provides its recursive capability by directly exploiting the fixed-point property.
So it’s not quite circular. But it is insane.
Mark:
Oh, I wasn’t worried by circularity, I was thinking of equivalence.
Looking at all the fixed point theorems, fixed points follows from operations similar to folding sets onto (subsets of) themselves, as I believe you are saying too – if there is a fixed point, it is because we already have recursivity, though it may need a fixed point operator to be expressed. I think Antendren shows that Muriel does the equivalent to what the lambda fixed point Y combinator do as explained in your “Why oh why Y” post. QEH. (“Quod Erat Handwavum”.)
But it is still madness, agreed. 🙂
I recently had reason to write a small program in dc, the unix “desk calculator”, and it reminded me of this – you do all your programming by arranging for the appropriate string to be in the appropriate spot on the stack, and then call the “execute string” function.
(Okay, so there wasn’t a very good reason to write the program in dc, but it was fun)
Mark, this post isn’t categorized properly – it doesn’t show up on http://scienceblogs.com/goodmath/goodmath/programming/pathological_programming/ as it should.