Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!killer!ames!mailrus!cornell!batcomputer!sun.soe!sun.soe.clarkson.edu!gary
From: gary@milo.mcs.clarkson.edu (Gary Levin)
Newsgroups: comp.lang.scheme
Subject: Re: self reproducing code
Message-ID: <GARY.88Oct11182452@milo.mcs.clarkson.edu>
Date: 11 Oct 88 22:24:52 GMT
References: <10500.8810101439@subnode.aiai.ed.ac.uk>
Sender: root@sun.soe
Organization: Clarkson University
Lines: 43
In-reply-to: jeff@aiai.edinburgh.ac.UK's message of 10 Oct 88 14:39:36 GMT

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.edu