tag:blogger.com,1999:blog-11295132.post114352409380990775..comments2015-03-09T08:25:32.318-07:00Comments on A Neighborhood of Infinity: The General Theory of Self-Reproducing ProgramsDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-11295132.post-1144694188520330982006-04-10T11:36:00.000-07:002006-04-10T11:36:00.000-07:00augustss,Actually I've had to deal with the differ...augustss,<BR/><BR/>Actually I've had to deal with the difference between trivial and non-trivial partial evaluation <A HREF="http://groups.google.com/group/comp.lang.functional/browse_thread/thread/d53dfc388c9329b6/e2d29040cc7ae70d?rnum=3#e2d29040cc7ae70d" REL="nofollow">recently</A>. I was writing Haskell code to evaluate expressions in a Newton-Raphson style solver. This expression evaluator was a kind of interpreter which meant it was slow - it had to reparse the expression every time the functions were evaluated. After a lot of fiddling about I eventually managed to convert it, by hand, into a 'compiler' which returned a partially evaluated function that no longer needed to reparse the original expressions. In effect I was ensuring that the expression parsing was done by partial evaluation leaving the remainder of the computation, the actual expression computation, uncompleted and ready for numerical input. What was interesting was just how similar the interpretation and compilation code was.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1144430973588267572006-04-07T10:29:00.000-07:002006-04-07T10:29:00.000-07:00Yes, a trivial implementation of partial evaluatio...Yes, a trivial implementation of partial evaluation is by some form of currying. But that implementation is uninteresting.<BR/>You have to be very careful to define what it means to have a "real" partial evaluator, but it can be done. (If I remember right Neil Jones et al have done it by a complexity measure that includes constant factors.)<BR/><BR/>What I find amazing is that the third Futamura projection can be implemented so that it actually does something interesting, i.e., suitable applied it does specialize an interpreter into a compiler.<BR/>And it has done some non-trivial work.augustsshttp://www.blogger.com/profile/05153404423721072935noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1144418666188453122006-04-07T07:04:00.000-07:002006-04-07T07:04:00.000-07:00augustss,According to the definition in Vicious Ci...augustss,<BR/><BR/>According to the definition in Vicious Circles, there is a program that can turn an interpreter into a compiler. Unpacking the definitions you find there is a trivial way to do this: just write a program that takes as input code written in language L and outpus an interpreter for L bundled with with that source code. Behaviourally it looks like a compiler - it outputs standalone pieces of code generated from source code in L. But this doesn't give you anything more than an interpreter because internally it <EM>is</EM> an interpreter. You can do this because there is a trivial way to 'cheat' an implemention of partial evaluation. There doesn't seem to be anything about the theorem, as stated in VC, that forces partial evaluation to mean anything non-trivial.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1144336552142903902006-04-06T08:15:00.000-07:002006-04-06T08:15:00.000-07:00In what sense do you think that the Futamura proje...In what sense do you think that the Futamura projections are bogus?<BR/>They have been implemented and there has been a lot of work on the im the field of partial evaluation.augustsshttp://www.blogger.com/profile/05153404423721072935noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1143683855562532542006-03-29T17:57:00.000-08:002006-03-29T17:57:00.000-08:00P(x) is just any program that always has the same ...P(x) is just any program that always has the same output as P does on input x?<BR/><BR/>Yes. P(x) is <EM>any</EM> program with the property [P(x)] = [P](x). In order to do the self-reproducing trick this way we use a program S such that P(x) = [S](P,x), ie. S makes P(x) out of P and x. A heavy handed approach to implementing S might be to actually build S from an interpreter that computes [P](x) and then outputs a program that outputs this value.<BR/><BR/>Vicious Circles defines a whole family of these S programs and defines a language to be "Turing Complete" if it can compute computable functions and has such programs S. The latter condition was new to me.<BR/><BR/>I didn't fully understand the posting that you linked to (though I think I get the gist of it). It looks like what I'm saying (repeating from the book, actually) does address one of the issues: you really don't have to worry about escaping quotes as there's always guaranteed to be a way for a program to quote the required part of itself. Many of the examples <A HREF="http://www.nyx.net/~gthompso/self_c.txt" REL="nofollow">here</A> are attempts to work around self-imposed restrictions making it harder and harder to do the escaping - disallowing ASCII codes. disallowing printf and so on. As long as you don't break Turing completeness you're guaranteed to find a way.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1143677006576216102006-03-29T16:03:00.000-08:002006-03-29T16:03:00.000-08:00Ok, I think I see what's going on. When you give ...Ok, I think I see what's going on. When you give as one possibility for a way to get P(x), "a new piece of code that simply calls P and supplies it with a hard-coded argument", this shows that if you have an interpreter in your language, then you have sufficient power to get from P and x to P(x)? If that's right, am I correct in saying that you're interpreting "program" in a rather extensional way, so that P(x) is just any program that always has the same output as P does on input x? That is, as opposed to saying that there could be a distinct function that gives the same outputs, but P(x) is one that has the code for x substituted in a very particular way in the code for P?Kennyhttp://www.blogger.com/profile/12226268498253877151noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1143596621139321872006-03-28T17:43:00.000-08:002006-03-28T17:43:00.000-08:00I really do mean compute P(x). I mean that you nee...I really do mean compute P(x). I mean that you need to be able to write a program that can take as input another program P, and some data x, and output another program that acts like P except with x hard-coded into it. This is the crux of the matter - you need to be able to do this kind of textual processing on the source code, P.<BR/><BR/>An example should make things clear: in Haskell, "p" is an expression representing the function called "p". "p x" means the expression that you get from applying p to x. So in Haskell, to a good approximation, you can compute P(x) simply by concatenating the code for x after P, and that's what ++ does in my code. You also need use "show x" instead of "x" to deal with quotes. And strictly speaking it should put parentheses around the x, but I cheated a bit because I knew that the one time I applied this function I wasn't going to have operator precedence issues.<BR/><BR/>That kpp program I link to is an example of a program that computes P(x) from P and x, but you have to interpret 'argument' or 'input' every so slightly differently.<BR/><BR/>Incidentally, a piece of code that computes [P(x)], instead of P(x), from P and x is an example of what the book calls an "interpreter" as it interprets the program P. And there's a computable function that can automatically turn one of these into a "compiler".<BR/><BR/>I can follow your second link. Haven't read it yet. Though I can say that this is essentially the same as the key step in Tarski's proof of the undefinability of truth, and also Godel's theorem.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1143587023857091782006-03-28T15:03:00.001-08:002006-03-28T15:03:00.001-08:00Does this link work?Does <A HREF="http://www.ocf.berkeley.edu/~easwaran/blog/2006/02/quantifying_into_sentence_posi.html" REL="nofollow">this link</A> work?Kennyhttp://www.blogger.com/profile/12226268498253877151noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-1143587007881824002006-03-28T15:03:00.000-08:002006-03-28T15:03:00.000-08:00"So here's the demand that we make of our programm..."So here's the demand that we make of our programming language: that it's powerful enough for us to write a program that can compute P(x) from inputs P and x."<BR/><BR/>Do you mean "a program that can compute <I>[P(x)]</I> from inputs P and x."? This is always where the different types of quotation marks and evaluation notations get tricky. I've only ever learned about this stuff in the theory of truth and philosophy of language, but I've thought that computer programming would be the best way to really learn it.<BR/><BR/>I tried to write something similar (on the philosophical side) here:<BR/><BR/>http://www.ocf.berkeley.edu/~easwaran/blog/2006/02/quantifying_into_sentence_posi.htmlKennyhttp://www.blogger.com/profile/12226268498253877151noreply@blogger.com