Wanted: Eigenratios of Brainf*ck Self-Interpreters
It's been a while since I've posted anything new here. I do have a draft of another post (written some time ago but still needing more work) that tries to summarise what I think I've discovered about "eigenratios" so far, and also makes an attempt to generalise some of this stuff in terms of Finite State Machines. But that'll have to wait until later because I've found a new obsession -- trying to find the eigenratio for a Brainf*ck self-interpreter.
A couple of weeks ago I received an email from Oleg Mazonka expressing some interest after finding one of my earlier messages about eigenratios to the ICFP Contest discussion list. We exchanged a few emails, mainly about the subleq/OISC self-interpreter to start with. You can find his implementation of an assembler, emulator, and self-interpreter (with extensions to what I did and a different assembly language syntax) here: http://mozaika.com.au/oleg/langsq.html.
When I first heard from Oleg I googled his name and found that he was the co-author (with Daniel Cristofani) of a paper about a Brainf*ck (BF from now on) self-interpreter that I had already added to my "links" on this site much earlier. (That was when I was collecting links to various self-interpreters, and the BF example was yet another that I hoped to perhaps be able to determine an eigenratio for one day.) Anyway, when I discovered Oleg's involvement with that paper, my interest in the BF self-interpreter was rekindled and has been occupying my mind ever since.
There are a few other BF self-interpreters out there but this one appears currently to be the shortest and perhaps also the fastest. It is also very well documented, but even so I had some difficulty initially, especially when trying to understand the details of exactly what was going on in the code and how the multiple levels of code/data were represented in memory with multiple self-interpreters running each other. But finally, after a few false starts I've think I've got most of the important details clear now.
Anyway, despite being relatively "fast", it still seems that this interpreter has a spectacularly high eigenratio! This is probably no surprise to those who have written much BF code before. In fact it seems to be so high that we haven't even been able to work out a reasonably accurate estimate of what it is yet. My current "best guess" is that will turn out to be somewhere between 12000 and 16000! (Compare that with the value of about 34 for my subleq/OISC self-interpreter.)
This rough estimate of the eigenratio is based on running as many copies of the interpreter as possible (in a "stack") and observing the ratio of total instructions executed with N+1 to that with N copies. But when I say "as many copies as possible", we've only managed to get to three so far (plus a small selection of different small programs on top of that)!! I've experimented with faster bottom level interpreters (BFF is my current leader in that category) and an optimising compiler for the bottom level (BFD, Windows only), but a performance hit of more than 10000 for every additional level of self-interpreter soon overwhelms whatever is sitting at the very bottom.
At the same time I've been trying to get my head around ways to build a matrix that would allow the eigenratio to be determined analytically. The problem with this approach is that the "full matrix" would seem to require an infinite number of rows and columns because (in the purest sense) the BF language has access to an arbitrarily large array of memory cells and also only supports "addressing memory" by moving one cell left or right from your "current position". So BF has this interesting property that the time your code takes to do something like move (or copy or compare) values between two cells is proportional to the "distance" between those two locations! When it comes to trying to determine a "full matrix" (one that could be used to calculate exactly how many instructions would be executed to interpret any other possible target program which could be arbitrarily large and possibly have it's own large amount of data beyond that also), there is also an arbitrarily large distance possible between an instruction in the code being interpreted by the self-interpreter below it and its "data" stored even further to the "right" in memory). What I think this means (at least as far as my current method of creating a matrix is concerned) is that there are infinite variations to be considered.
However, if we aim a bit lower and only attempt to build a matrix describing the specific situation of this particular BF interpreter running another copy of itself (running another copy of itself, ad nauseam) then we get back down to finite sized matrices. ("Finite" is so much easier to deal with than "infinite"!) Even so, there still seem to be a lot of "variations", possibly (probably?) still too many to be fully enumerated to a matrix.
Perhaps BF is just so "bad" that the exact eigenratio for this particular self-interpreter will remain a mystery - at least until Moore's Law has been applied a few more times.
That leaves one more option that I'm currently working on, which is to attempt to create a more "efficient" (lower eigenratio) version of this BF self-interpreter. I believe I've identified at least one area of the code that could be made faster but only by changing some other details (also meaning it uses more memory - bad! - and probably that the program will be larger also). Anyway, as they say, the proof is in the pudding. Hopefully I'll have more to say on this later when (and if) I manage to get it working!
A couple of weeks ago I received an email from Oleg Mazonka expressing some interest after finding one of my earlier messages about eigenratios to the ICFP Contest discussion list. We exchanged a few emails, mainly about the subleq/OISC self-interpreter to start with. You can find his implementation of an assembler, emulator, and self-interpreter (with extensions to what I did and a different assembly language syntax) here: http://mozaika.com.au/oleg/langsq.html.
When I first heard from Oleg I googled his name and found that he was the co-author (with Daniel Cristofani) of a paper about a Brainf*ck (BF from now on) self-interpreter that I had already added to my "links" on this site much earlier. (That was when I was collecting links to various self-interpreters, and the BF example was yet another that I hoped to perhaps be able to determine an eigenratio for one day.) Anyway, when I discovered Oleg's involvement with that paper, my interest in the BF self-interpreter was rekindled and has been occupying my mind ever since.
There are a few other BF self-interpreters out there but this one appears currently to be the shortest and perhaps also the fastest. It is also very well documented, but even so I had some difficulty initially, especially when trying to understand the details of exactly what was going on in the code and how the multiple levels of code/data were represented in memory with multiple self-interpreters running each other. But finally, after a few false starts I've think I've got most of the important details clear now.
Anyway, despite being relatively "fast", it still seems that this interpreter has a spectacularly high eigenratio! This is probably no surprise to those who have written much BF code before. In fact it seems to be so high that we haven't even been able to work out a reasonably accurate estimate of what it is yet. My current "best guess" is that will turn out to be somewhere between 12000 and 16000! (Compare that with the value of about 34 for my subleq/OISC self-interpreter.)
This rough estimate of the eigenratio is based on running as many copies of the interpreter as possible (in a "stack") and observing the ratio of total instructions executed with N+1 to that with N copies. But when I say "as many copies as possible", we've only managed to get to three so far (plus a small selection of different small programs on top of that)!! I've experimented with faster bottom level interpreters (BFF is my current leader in that category) and an optimising compiler for the bottom level (BFD, Windows only), but a performance hit of more than 10000 for every additional level of self-interpreter soon overwhelms whatever is sitting at the very bottom.
At the same time I've been trying to get my head around ways to build a matrix that would allow the eigenratio to be determined analytically. The problem with this approach is that the "full matrix" would seem to require an infinite number of rows and columns because (in the purest sense) the BF language has access to an arbitrarily large array of memory cells and also only supports "addressing memory" by moving one cell left or right from your "current position". So BF has this interesting property that the time your code takes to do something like move (or copy or compare) values between two cells is proportional to the "distance" between those two locations! When it comes to trying to determine a "full matrix" (one that could be used to calculate exactly how many instructions would be executed to interpret any other possible target program which could be arbitrarily large and possibly have it's own large amount of data beyond that also), there is also an arbitrarily large distance possible between an instruction in the code being interpreted by the self-interpreter below it and its "data" stored even further to the "right" in memory). What I think this means (at least as far as my current method of creating a matrix is concerned) is that there are infinite variations to be considered.
However, if we aim a bit lower and only attempt to build a matrix describing the specific situation of this particular BF interpreter running another copy of itself (running another copy of itself, ad nauseam) then we get back down to finite sized matrices. ("Finite" is so much easier to deal with than "infinite"!) Even so, there still seem to be a lot of "variations", possibly (probably?) still too many to be fully enumerated to a matrix.
Perhaps BF is just so "bad" that the exact eigenratio for this particular self-interpreter will remain a mystery - at least until Moore's Law has been applied a few more times.
That leaves one more option that I'm currently working on, which is to attempt to create a more "efficient" (lower eigenratio) version of this BF self-interpreter. I believe I've identified at least one area of the code that could be made faster but only by changing some other details (also meaning it uses more memory - bad! - and probably that the program will be larger also). Anyway, as they say, the proof is in the pudding. Hopefully I'll have more to say on this later when (and if) I manage to get it working!
posted by Clive at 10:21 am
0 comments
