Self Interpretation | ||||||||||||||||||||||||||
|
Minus Home What is Minus? Basics Proof of Concept Extensions Implementations Examples Files Self Interpreter |
Inspired by a very short self interpreter in brainfuck, here is a self interpreter in Minus. It is 227 characters in length, using 19 different symbols. mitccgpmpmAcpphtnikipnpnAcpppkpkucthtuAtppaieaeabifbfbaaa It only implements a subset of Minus commands, but it can interpret itself and it runs fine under the normal interpreter. It implements everything in the basics, except for numbers, and use of B-Z, and code must be stripped of all other characters. It could be made a little shorter by breaking backwards compatibility, by doing things such as assuming w,x,y,z start off as 0, and swapping the order of operands (ab would act as b-=a instead of a-=b). Another possible savings would be to assume only memory is used with a positive index. To execute this proceed the trailing ! immediately with the minus code you want to interpret. Note that Aiocp! are also being passed in as input, this is required and is counted in the 227 bytes. These specify the special variables in the language and you could change them if you like. This technique is a shortcut, and helps keep the size down since numbers are not allowed in the program, it also has the additional side effect that customizing the language is easy! This same technique could also have been used in the short brainfuck self interpreter, but perhaps the authors deemed it too impure. This is short self interpreter, nearly half the size of the BF one. However, keep in mind that it uses 19 symbols while the BF one uses only 9 (with !). Also the BF one chooses to be very compliant to optional BF behavior, possibly at the cost of size, while the Minus self interpreter discards parts of the language that are deemed not worth the cost to implement. A redeeming quality of this interpreter is that it is reasonably fast. In fact, running under a C implementation it is several times faster than a ruby interpreter interpreting Minus code directly. Whereas the BF self interpreter is horrendously slow (this is due to the nature of constantly having to make the pointer travel back and forth between code and memory which takes time proportional to that distance). An interesting thing to do with self interpreters is to have them interpret themselves. This nesting has been experimented with at eigenratios.blogspot.com. Eigenratio has been coined to describe the ratio of execution time as layers are added. It can be theoretically derived by creating a matrix of operations, for each operation count how many of each other operations it uses in its interpretation. Take this matrix and compute the eigenvalue, this is that ratio. (See the webpage for a more full description for this process). Applying the process to the Minus interpreter:
Minus is very simple so generating the matrix is easy because no matter what the statement it passes through almost the exact same code every time. This matrix has an eigenvalue of 87.2338. Experimental results, running a simple program nested in 5 self interpreters took 61.22 seconds, and nested 6 times took 5339 seconds, a ratio of 87.21. |