[Tutor] OT self-implementation?
Brian van den Broek
bvande at po-box.mcgill.ca
Sat Jul 2 06:11:00 CEST 2005
Michael P. Reilly said unto the world upon 01/07/2005 22:18:
> On 7/1/05, Brian van den Broek <bvande at po-box.mcgill.ca> wrote:
>>A recent thread on comp.lang.python has touched on to what extent C
>>was written in C. I know PyPy aims to implement Python in Python. I
>>believe I've heard that many lisp fans think you don't have a language
>>unless you can write the language's interpreter in the language
>>itself. (Perhaps one or more of these claims is a bit inaccurate, but
>>the substance seems right.)
>>This sounds, to the untutored, rather like magic.
>>Naively, one thinks that to write
>>anything in C, you'd have to *have* C to write in, etc.
<snip me (Brian) asking for refs>
> If you are interested in a more abstract explanation on this, you can read
> up on one reason why lisp programmers are such fans of writting lisp
> interpreters in lisp: Turing Machines (TM). Abstract computer constructs
> that, arguably, are equivalent to your desktop computer in terms of
> programming. They are really for theoretical research, especially good for
> algorithm creation. But one of the early algorithms was to create a TM with
> a TM.
Thanks to Max, Michael, and Sean for the replies.
Max's stepwise explanation, which I will distort in summary by
simplifying to "Write a complier in a lower level language and use
that to compile your C compiler written in C" was very helpful. Seeing
it on screen makes me wonder how I didn't work it out for myself, but
there you go :-)
Max's and Sean's pointing toward compiler design gives me something to
start looking for. Having a search term is key to good googling!
Once we get down to Turing Machines and away from real-world
messiness, I'm much more happy. I have often found that there is, for
me, quite a gap between the abstract mathematical foundations of
recursion theory, formal logic, etc. that I have a good handle on, and
the real world use and applications of the theory. A prime motive for
tackling Python was to try to close that gap.
A fun point about Turing machines:
The Church-Turing Thesis (roughly, the claim that any intuitively
computable function is computable by a Turing machine has, as far as I
know, the distinction of being the first mathematically significant
claim widely accepted yet know to be insusceptible of proof.
(Goedel had earlier shown that any formalism based on a language
adequate for arithmetic could formulate propositions not decidable by
the formalism, but it wasn't until much later that any natural
examples of independent mathematical interest arose. Early on in my
graduate career, I spent an excited few days thinking I'd found a
refutation of the Thesis employing something similar to the Godel
construction. What a let down when I found the fallacy :-( )
The Thesis has, however, much empirical confirmation in that every
well defined abstract notion of computability put forth has been
proven to be co-extensive with Turing Machine computability. The entry
of empirical methods into mathematical argument in this way has made
many mathematicians and philosophers of math quite uncomfortable.
And, that's more than enough ramble :-)
More information about the Tutor