How to Generate Self-Referential Programs | Hacker News Reader

How to Generate Self-Referential Programs

malisper.me

62 pointsluu14 comments

Usually called a "Quine", right?

Here's a JavaScript one that's pretty neat: http://aem1k.com/world/

It struck me that this ends up looking a lot like the Y-combinator, which makes sense, since it's a function that acts on itself without a recursive definition. Pretty cool to see the overlap of simple concepts in various ways. I've always wondered how quines worked on general principle.

This definitely feels like cheating. There's so much one could do rather than just use the ` operator to quote the program. Given a program f, one can create a program g which prints out g and then does f, and one does not require any special operators to do this. There's some cool computability stuff in this area, and I don't know (off the top of my head) of a readable introduction.

Your observation is a consequence of Kleene's recursion theorem, which I summarised briefly in http://vimeo.com/66863570#at=13m40s (extracted from chapter 8 of http://computationbook.com/).

I agree. Using quote is basically using the Lisp parser to do the work and is almost like reading the source program as input. It would have been interesting if their program contained a parser (which I think wouldn't be too distracting because of homoiconicity).

I found this an interesting read anyways especially when they start parametrizing the quine by a function F near the end. Although my interest shouldn't be that much of a surprise given my username:

asrp: a self-referential person/program/place

Doug H, is that you?

Can anyone give an example of a real world application that uses this technique? Why would you do it?

Starting from here, then adding a bit of modification, gets to Trusting Trust: http://wiki.c2.com/?TheKenThompsonHack

I have a number of projects that make use of self-reference. Although not using the particular method in this article and instead of passing code through an interpreter, it passes some first-thing into a second-thing which gives another first-thing that can again be given to second-thing. They're also all very self-referential.

https://github.com/asrp/pymetaterp The boot portion of this parser can its own AST from its own grammar and its own AST

https://github.com/asrp/tkui This GUI editor can modify and (re)generate itself. Its the "generate UI code" button.

https://asrp.github.io/blog/gui_toolkit This toolkit maker can (and is required to) make itself.

There is some reason to believe that self-reference is at the heart of intelligence. Human beings, for example, talk about themselves all the time. (I even do in this comment.) Hence, it's possible that self-reference might be important in the creation of artificial intelligence.

I don't think there really is one. It's just an interesting puzzle that can be enjoyable.

I'd imagine this is very useful for writing self-modifying or polymorphic code.

And anything using this technique would be a perfect illustration of the fact that code is harder to debug than to write, so if you write the cleverest code you can write, you are by definition not smart enough to debug it.

""" On Self-Modifying Code and the Space Shuttle OS

I was doing some reading about Metaprogramming and Self-modifying code at Wikipedia, a fascinating topic with many uses from optimization, patching, and genetic programming.

And it reminded me of my days during the early 1990s working as a software engineer on the Space Shuttle operating system (FCOS). Many people don’t know that the Space Shuttle OS implements self-modifying code for the purpose of “fault-tolerance”.

...

An alternative to self-modifying or patching code is to use conditions (if statements) and local store (such as in-memory) to store flags that are used determine the paths to take (assuming such paths are known ahead of time, which might not be the case on genetic programming). Being the Space Shuttle a memory-limited, non-dynamic memory map and management environment, it is cheaper, less complex, and safer to patch specific instructions directly. """

http://weblog.cenriqueortiz.com/computing/2007/08/18/on-self...

It sounds useful in the appropriate contexts, much like every other technique.

Reply on news.ycombinator.com