6 ms·

How to Generate Self-Referential Programs

62 points by luu 10y ago

gtirloni 10y ago
Can anyone give an example of a real world application that uses this technique? Why would you do it?
- nv-vn 10y ago
  I don't think there really is one. It's just an interesting puzzle that can be enjoyable.
- __s 10y ago
  Starting from here, then adding a bit of modification, gets to Trusting Trust: http://wiki.c2.com/?TheKenThompsonHack http://wiki.c2.com/?TheKenThompsonHack
- travmatt 10y ago
  I'd imagine this is very useful for writing self-modifying or polymorphic code.
  - taneq 10y ago
    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.
    - travmatt 10y ago
      """ 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-modifying-code-and-the-space-shuttle-os/ http://weblog.cenriqueortiz.com/computing/2007/08/18/on-self... It sounds useful in the appropriate contexts, much like every other technique.
- brianberns 10y ago
  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.
- asrp 10y ago
  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 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 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 https://asrp.github.io/blog/gui_toolkit This toolkit maker can (and is required to) make itself.
tyingq 10y ago
Usually called a "Quine", right? Here's a JavaScript one that's pretty neat: http://aem1k.com/world/ http://aem1k.com/world/
ivanbakel 10y ago
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.
Smaug123 10y ago
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.
- asrp 10y ago
  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
  - kazinator 10y ago
    Doug H, is that you?
- tomstuart 10y ago
  Your observation is a consequence of Kleene's recursion theorem, which I summarised briefly in http://vimeo.com/66863570#at=13m40s http://vimeo.com/66863570#at=13m40s (extracted from chapter 8 of http://computationbook.com/ http://computationbook.com/).

62 points by luu 10y ago

gtirloni 10y ago

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

nv-vn 10y ago
I don't think there really is one. It's just an interesting puzzle that can be enjoyable.
__s 10y ago
Starting from here, then adding a bit of modification, gets to Trusting Trust: http://wiki.c2.com/?TheKenThompsonHack http://wiki.c2.com/?TheKenThompsonHack
travmatt 10y ago
I'd imagine this is very useful for writing self-modifying or polymorphic code.
- taneq 10y ago
  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.
  - travmatt 10y ago
    """ 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-modifying-code-and-the-space-shuttle-os/ http://weblog.cenriqueortiz.com/computing/2007/08/18/on-self... It sounds useful in the appropriate contexts, much like every other technique.
brianberns 10y ago
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.
asrp 10y ago
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 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 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 https://asrp.github.io/blog/gui_toolkit This toolkit maker can (and is required to) make itself.

tyingq 10y ago

Usually called a "Quine", right? Here's a JavaScript one that's pretty neat: http://aem1k.com/world/ http://aem1k.com/world/

ivanbakel 10y ago

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.

Smaug123 10y ago

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.

asrp 10y ago
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
- kazinator 10y ago
  Doug H, is that you?
tomstuart 10y ago
Your observation is a consequence of Kleene's recursion theorem, which I summarised briefly in http://vimeo.com/66863570#at=13m40s http://vimeo.com/66863570#at=13m40s (extracted from chapter 8 of http://computationbook.com/ http://computationbook.com/).