Michael P. Reilly said unto the world upon 01/07/2005 22:18: > On 7/1/05, Brian van den Broek <[EMAIL PROTECTED]> wrote:
<snip> >>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. <snip> >>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. > > http://en.wikipedia.org/wiki/Turing_machine > http://plato.stanford.edu/entries/turing-machine/ 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 :-) Thanks again. Brian vdB _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
