Composite Self-Interpreters

It's funny how little snippets of more or less unrelated pieces of information can fuse in your mind when the conditions are right. I had one of those moments earlier tonight so I'm recording the result now before it has a chance to disintegrate and disappear!

First, a little while ago ago Dean Scarff mentioned in an email the idea of using a matrix (not necessarily square) to describe a cross-language interpreter in much the same way that I've been trying to use matrices to describe various self-interpreters. I think the cross-language aspect had floated through my head at some earlier point in time also but wasn't more than a fleeting thought at best.

Then earlier today Oleg Mazonka mentioned in another email some slightly surprising results he got from running combinations of my new cgbfi2.b BF self-interpreter and Daniel B. Cristofani's dbfi.b. I had also played around a little with running combinations in different orders during testing but hadn't thought all that much about it.

Also fresh in my thoughts was something I read about in the last day or two pointing out that if you have two matrices A and B, with A being m by n and B being n by m, then the eigenvalues of AB are the same as the eigevalues of BA (plus m-n eigenvalues of zero if we also assume m is greater than or equal to n).

And the final thing was a discussion I saw recently (on some site about esoteric programming languages) about one person who had written an interpreter in language L1 for a language L2, and someone else had written an interpreter in language L2 for L1. The comment was made that between the two of them, they now effectively had the first self-interpreter for one of those languages! (Update: 21 Dec. Found another copy of the discussion - actually about a Befunge to ETA compiler written in Ruby, and an ETA interpreter written in Befunge, but in this case my bad memory didn't do any real harm!)

Anyway, all this stuff kind of merged in my head not long ago, leading me to realise there is another interesting (but also probably totally useless!) thing we can say about self-interpreters that are composites of other interpreters.

Say we have a pair of complementary cross language interpreters as described above. The pair can be combined to make a logical single unit in two different ways - effectively creating a self-interpreter for either of the two languages involved. If we also assume we can build a matrix for each separate cross-language interpreter, then we can also get squares matrices AB and BA that must correctly describe the two "composite" self-interpreters. Then we can apply the result about eigenvalues of AB and BA being the same (except for additional zero eigenvalues if A and B not square) and see that the eigenratios (dominant eigenvalue) for each such pair of composite self-interpreters must be the same, even though they are for different languages!

Finally, we can also apply the same idea to two different self-interpreters for the same language. The "product" of those two can be built in two different ways, and again we can see that the eigenratio of these composite self-interpreters must be identical.

This all seems "very cool" to me... although I better go and check it out with an example or two because so far this is all "just theory"!

Thank you Oleg and Dean for providing the seeds for an interesting thought!

The Mark II Brainf*ck Self-Interpreter

I obsess, therefore I am...

This will be short and sweet, because all I really want to do is to "release" my second version of a faster BF self-interpreter to the world at large.

The commented version of cgbfi2.b is probably easier to understand but here's a lean and mean version anyway!

>>>>+[->>>++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++
++++<<-]+>>>,<++[[>[->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>
-]>]<[[[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<]>[-]+<<[--[
[-]>>-<<<+>]>>[-<<<<[>+<-]+<<+[->[<+>>>>>>+<<<<<-]<[>+<
-]>>>>>>>+<[-[-[-[-[-[-[-[-[[-]>-<]>[-<<+++++++>>]<]]]>
[-]<]>[-<<+++>>]<]>[-<<+>>]<]>[-]<]>[-<<<<<<<+>>>>>>>]<
]>[-]<<<<<]>>>[<<+>>-]<+<[-[-[-[-[-[-[-[-[-[-[[-]>-<<<[
-]<<+>>]]]]>[-]<]>[-<<<[-]<<+++++++>>>]<]]]>[-]<]>[-<<<
[-]<<+++++++>>>]<]]>[-]<<<<<<[-]>>[-<<<[>+>>+<<<-]>[<+>
-]>>[-[-[[-]>>]>[<<[<+>>+<-]>[<+>-]+<<-[-[-[-[-[-[-[-[-
[-[-<+>]<+++++++++++++>>[-]>->-<<]]]>>[->>>>>]<<]>>[-<<
<++++++++++++>>[-]>>-]<<]>>[->>>>>]<<]>>[-<<<++++++++++
+>>[-]>>-]<<]>>[-<<<++++++++++>>[-]>>-]<<]]>>[->>>>>]<<
]<]]>[>>]<<<]>>+>>>]<<]>>[->+>]<<<]<<[<<]>>[[<+>>+<-]+<
-[-[-[-[-[-[-[-[-[-[-[-[-[-[-[->->>[>>]>>[>>]<[<-<<-<]<
[<<]<<[<<]<]>[->>[>>]>>[>>]<[>+>>+>]<[<<]<<[<<]]<]>[->>
[>>]>>[>>]<[-]<[<<]<<[<<]]<]>[->>[>>]>>[>>]<[<-<]<[<<]<
<[<<]]<]>[->>[>>]>>[>>]<[>+>]<[<<]<<[<<]]<]>[->>[>>]>>[
>>]<<-<<-<<[<<]<<[<<]]<]>[->>[>>]>>[>>]+>>+[<<]<<[<<]]<
]>[->>[>>]>>[>>]<++<[<<]<<[<<]]<]>[->>[>>]>>[>>]<+<[<<]
<<[<<]]<]>[->>[>>]>>[>>]<,<[<<]<<[<<]]<]>[->>[>>]>>[>>]
<-<[<<]<<[<<]]<]>[->>[>>]>>[>>]<.<[<<]<<[<<]]<]>[->>[>>
]>>[>>]<<-<<[<<]<<[<<]]<]>[->>[>>]>>[>>]+[<<]<<[<<]]<]>
[->>[>>]>>[>>]<[>+>>+<<<-]>[<+>-]>>[<<+>>[-]]+<<[>>-<<-
]>>[<<+>>>>+<<-]>>[<<+>>-]<<[>>+<<-]+>>[<<->>-]<<<<[-<<
[<<]<<[<<]<<<<<++>>]>>[-<<<<<<[<<]<<[<<]<]>]<]>[->>[>>]
>>[>>]<[>+>>+<<<-]>[[<+>-]>>[-]+<<]>>[<<+>>>>+<<-]>>[<<
+>>-]<<[>>+<<-]+>>[<<->>-]<<<<[-<<[<<]<<[<<]<<<<<+>>]>>
[-<<<<<<[<<]<<[<<]<]>]>[<+>-]<<<<<<[>>+<<-[->>->>+[>>>[
-<+>>+<]+<-[-[[-]>-<]>[-<<<+>>>]<]>[-<<<->>>]>[-<+>]<<<
<[>>+<<-]>>]<<<<<<]>>[-<<+[>>>[-<+>>+<]+<-[-[[-]>-<]>[-
<<<->>>]<]>[-<<<+>>>]>[-<+>]<<<<[<<+>>-]<<]]]>>>>>>>]

Isn't it lovely? :-)

In a nutshell, cgbfi2.b is a derivative of cgbfi1.b that replaces "++", ">>", "<<", "[-]", "[>]", "[<]", "[>>]" and "[<<]" sequences in its input program with some new single value codes internally. This means those sequences are treated as single instructions in the main interpreter loop, thus requiring only one return trip between the emulated code and data in each case instead of (often) many more. In addition this strategy reduces the size of memory footprint of the emulated code, which also helps.

Of course, cgbfi2.b is a lot larger than cgbfi1.b (1758 instructions versus 950 once the comments are stripped out) but cgbfi2.b effectively sees itself as a 1178 instruction program after those common sequences described above are "compiled" to single instructions in memory. 1178 is still larger than 950 but the other gains made by the reduced trips to the data and back at runtime generally make this new version much faster. The other negative is that this new interpreter does more work when loading a program (it was hard work recognising those few short sequences!) so it can be slower than other interpreters when running some shorter/simpler programs. But for larger and more complex programs (including itself!) it is definitely much faster.

In terms of finding an eigenratio, it appears that this new interpreter might have an eigenratio of somewhere in the "low thousands". This guesstimate is again only based on results from running a few very small programs on a three level deep stack of the interpreter. But if this is not too far from the real value then it seems a fast PC might manage to run a four level stack in a few days. I'll have to find a faster machine than mine to test this with!

However I did manage to run a 4 level deep stack with a slight "cheat" about 10 days ago when I was experimenting with different strategies. The "cheat" was to create a version of the interpreter that expects its input to already be converted to binary values 1-8 instead of the original "][><.-,+" BF instructions, and values 9-16 for the "virtual instructions", plus 0 for the end of input marker. This means the loader routine was extremely short and simple (something like ">>>>>>+[-<,[>>>+<]>]>+<<<<[<<]>>"), but the main interpreter loop was unchanged. In that experiment, the four level stack of the "binary BF self-interpreter" appeared to be converging towards an eigenratio of about 600. Once again, on a faster machine this would seem to indicate that a 5 level stack might be able to be run (with a very simple program "on top") in a few days or so.

More later hopefully, once I find a faster machine, or someone else produces a faster faster version! For now, I think I'm just about out of ideas, energy and enthusiasm in that department - not to mention skill. Even finding a way to do basically the same thing as cgbfi2.b but in a more compact implementation should make it a lot faster.