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!
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!
posted by Clive at 10:09 pm
0 Comments:
Post a Comment
<< Home