Mogensen's Inherited Limits paper describes a little self-hosting interpreter, as a running example. This is an implementation of that self-hosting interpreter inside req, a clean and simple term rewriting language by Darius Bacon. There's a larger (faster? more actively maintained?) term rewriting language named Pure, and this could probably be transliterated into Pure without too much effort. On the other hand, it could probably be transliterated into Scheme/Haskell/ML/Ocaml/Lua or lots of other languages with about the same amount of effort. The point is, this one works (or at least, that's what I believe now) and an executable specification can be used to doublecheck a reimplementation. In the req version, the first block of 18 lines is the (completely straightforward) interpreter. The rest is basically fluff, for running towers of self-interpreters, though getting the Peano-deBruijn-coded self-interpreter term right took a little debugging. The Lua and Prolog versions are simple transliterations of the req version. I don't know which one is fastest. The terminating-inputs are a brute force enumeration of grammatical inputs, squashed forcefully to make them terminating (otherwise infinite loops are annoying). The outputs file was generated from the req implementation, with the intention of it being a regression test for re-implementation. |