carr%car@CS.UTAH.EDU (Harold Carr) (10/08/88)
A couple of years ago I found an example of self reproducing code. It looked something like: ((lambda (lambda) (list (quote (lambda .... It was an anonymous lambda application which, when evaluated in Common Lisp, would return the exact same for, which could then be evaluated again, always returning the same anonymous application. If anyone has this code please send it to me. Thanks, Harold
stoller%morgan@CS.UTAH.EDU (Leigh B. Stoller) (10/08/88)
Date: Tue, 19 May 87 15:39:42 MDT From: carr@orion.utah.edu (Harold Carr) To: kessler@orion.utah.edu Subject: Fun stuff Cc: pass@orion.utah.edu Here's one everyone has already probably seen, but I forgot about it. What does the following evaluate to? ((lambda (x) (list x (list (quote quote) x))) (quote (lambda (x) (list x (list (quote quote) x))))) Great problem for Bob's Lisp class. Harold
Alan@AI.AI.MIT.EDU (Alan Bawden) (10/08/88)
Date: Fri, 7 Oct 88 13:30:30 MDT
From: carr%car@cs.utah.edu (Harold Carr)
A couple of years ago I found an example of self reproducing code....
in Common Lisp, ...
My favorite example:
(let ((let '`(let ((let ',let))
,let)))
`(let ((let ',let))
,let))
I believe that Mike McMahon is the author of this variant. It is
unfortunate that this isn't standard Scheme because of the use of
LET as an identifier...carr%car@CS.UTAH.EDU (Harold Carr) (10/08/88)
Thanks for the self-reproducing code. Since yours is different from what I was looking for it prompts me to ask of everyone: send me any examples you have of self-reproducing code. I'd like to make a collection of them. If possible, cite the author as Alan has done. Thanks, Harold ps: I don't care whether the code is interlisp, cl, psl, scheme, not quite legal - just so it does (or has) run on some system that does (or has) exists.
stever@RIVERSIDE.SCRC.SYMBOLICS.COM (10/08/88)
Date: Fri, 7 Oct 88 13:30:30 MDT
From: carr%car@cs.utah.edu (Harold Carr)
It was an anonymous lambda application which, when evaluated in Common
Lisp, would return the exact same for, which could then be evaluated
again, always returning the same anonymous application.
((LAMBDA (TEMPLATE)
(SETF (SECOND (SECOND TEMPLATE)) (COPY-TREE TEMPLATE))
TEMPLATE)
'((LAMBDA (TEMPLATE)
(SETF (SECOND (SECOND TEMPLATE)) (COPY-TREE TEMPLATE))
TEMPLATE)
(QUOTE *PLACEHOLDER*)))
This will work. I'm pretty sure there's a more elegant way to do it.
If anyone send you one, I'd appreciate a copy.
Thanks,
Stephendanvy@diku.dk (Olivier Danvy) (10/08/88)
Chez Scheme Version 2.0.3 Copyright (c) 1987 R. Kent Dybvig > () () > This one is pretty small :-) It is illegal according to the r3rs's BNF for Scheme, though. Olivier
KMP@STONY-BROOK.SCRC.SYMBOLICS.COM (Kent M Pitman) (10/09/88)
() by itself is certainly cute, but I don't think it counts.
It's not -constructing- a program, it's just -returning- one.
All self-evaluating forms have the same property, after all.
{{1, 2, 3, ...}, {#t, #f}, ...}
Another borderline case, that comes up in Common Lisp, is:
#1='#1#
But depending on your model of what QUOTE does, that's just
self-evaluating, too, and doesn't count either. Btw, don't
try to look at the result without setting *print-circle* or
*print-level* appropriately.jeff@aiai.edinburgh.ac.UK (Jeff Dalton) (10/10/88)
Here's one I wrote a while ago using the fairly standard technique
of having some data that looks pretty much like the code that uses
the data to reconstruct the data and the code.
;;; Self-reproducing function
(defun v ()
(let ((m '(subst m
'**
'(defun v () (let ((m '**)) **)))))
(subst m
'**
'(defun v () (let ((m '**)) **)))))
-- Jeffgary@milo.mcs.clarkson.edu (Gary Levin) (10/12/88)
A non-trivial expression must be a list of at least 2 elements, so
let's guess that our solution looks like:
( ____________ ___________ )
The first blank must be a lambda expression if we are to avoid the
necessity of defining a function outside of our solution. (Which
would violate the self-reproducing aspect to some extent.)
( (lambda (x) ________ ) ____________ )
The choice of the name ``x'' was arbitrary. The choice of one
argument followed from the assumption of a two element list. The body
of the lambda expression must return a two element list, if we are to
re-produce the original input. There are different choices possible;
I'll choose
( (lambda (x) (list _____ _____ )) ___________ )
The argument might as well be quoted, otherwise we need to delve
deeper into the expression. This then determines some of the second
argument to ``list''.
( (lambda (x) (list _1_ (list (quote quote) _2_ ))) (quote _3_ ) )
Now comes the ``magic'' part. Notice that whatever is written in _3_,
we can make the second element of our result match by replacing _2_ by x.
( (lambda (x) (list _1_ (list (quote quote) x ))) (quote _3_ ) )
yields ( value_of_1_ (quote _3_ ) )
We can now use ``x'' for _1_, which let's us determine the value_of_1_
by our choice of _3_. The solution follows immediately.
( (lambda (x) (list x (list (quote quote) x )))
(quote (lambda (x) (list x (list (quote quote) x ))) ) )
The logic of the derivation makes this easy to remember/reconstruct.
--
-----
Gary Levin/Dept of Math & CS/Clarkson Univ/Potsdam, NY 13676/(315) 268-2384
BitNet: gary@clutx Internet: gary@clutx.clarkson.edugyro@KESTREL.ARPA (Scott B. Layson) (10/12/88)
Here's a fun variation: write a Lisp function which returns its own defining form (that is, a form EQUAL to the one you typed in to define the function in the first place). My solution to follow. No doubt there are many. -- Scott