carr%car@CS.UTAH.EDU (Harold Carr) (11/12/88)
Quite a number a people asked for copies of the self duplicating code
I requested. Here it is in one swell foop. If you have any self
duplicating code that is duplicated ( ;-) ) here I would like to see it.
Thanks for all the replies,
Harold
--------------
Summary-line: 7-Oct stoller@morgan #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25166; Fri, 7 Oct 88 13:56:07 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA06715; Fri, 7 Oct 88 13:56:00 MDT
Received: by morgan.utah.edu (5.54/utah-2.0-leaf)
id AA04067; Fri, 7 Oct 88 13:55:56 MDT
Date: Fri, 7 Oct 88 13:55:56 MDT
From: stoller@morgan (Leigh B. Stoller)
Message-Id: <8810071955.AA04067@morgan.utah.edu>
To: carr@car
Cc: pass@cs, scheme@mc.lcs.mit.edu, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 13:30:30 MDT <8810071930.AA25143@car.utah.edu>
Subject: Re: self reproducing code
*** EOOH ***
Date: Fri, 7 Oct 88 13:55:56 MDT
From: stoller@morgan (Leigh B. Stoller)
To: carr@car
Cc: pass@cs, scheme@mc.lcs.mit.edu, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 13:30:30 MDT <8810071930.AA25143@car.utah.edu>
Subject: Re: self reproducing code
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
Summary-line: 7-Oct Alan@AI.AI.MIT.EDU #self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25184; Fri, 7 Oct 88 14:11:43 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA07523; Fri, 7 Oct 88 14:10:26 MDT
Received: from QUESTION-AUTHORITY.AI.MIT.EDU by REAGAN.AI.MIT.EDU via CHAOS with CHAOS-MAIL id 141482; Fri 7-Oct-88 16:00:51 EDT
Date: Fri, 7 Oct 88 16:00 EDT
From: Alan Bawden <Alan@AI.AI.MIT.EDU>
Subject: self reproducing code
To: carr%car@cs
Cc: pass@cs, scheme@MC.LCS.MIT.EDU, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Message-Id: <19881007200040.6.ALAN@QUESTION-AUTHORITY.AI.MIT.EDU>
*** EOOH ***
Date: Fri, 7 Oct 88 16:00 EDT
From: Alan Bawden <Alan@AI.AI.MIT.EDU>
Subject: self reproducing code
To: carr%car@cs
Cc: pass@cs, scheme@MC.LCS.MIT.EDU, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: <8810071930.AA25143@car.utah.edu>
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...
Summary-line: 7-Oct sandra@defun #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25206; Fri, 7 Oct 88 14:24:23 MDT
Received: by defun.utah.edu (5.54/utah-2.0-leaf)
id AA16358; Fri, 7 Oct 88 14:24:21 MDT
From: sandra@defun (Sandra J Loosemore)
Message-Id: <8810072024.AA16358@defun.utah.edu>
Date: Fri, 7 Oct 88 14:24:20 MDT
Subject: Re: self reproducing code
To: carr@car (Harold Carr)
In-Reply-To: carr@car (Harold Carr), Fri, 7 Oct 88 14:19:26 MDT
*** EOOH ***
From: sandra@defun (Sandra J Loosemore)
Date: Fri, 7 Oct 88 14:24:20 MDT
Subject: Re: self reproducing code
To: carr@car (Harold Carr)
In-Reply-To: carr@car (Harold Carr), Fri, 7 Oct 88 14:19:26 MDT
Here's my contribution for the simplest piece of self-reproducing code:
T
-Sandra :-)
-------
Summary-line: 7-Oct jar@void.ai.mit.edu #self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25234; Fri, 7 Oct 88 14:40:52 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA08444; Fri, 7 Oct 88 14:40:40 MDT
Received: by void.ai.mit.edu (5.59/1.5)
id AA03464; Fri, 7 Oct 88 16:43:05 EDT
Date: Fri, 7 Oct 88 16:43:05 EDT
From: jar@void.ai.mit.edu (Jonathan Rees)
Message-Id: <8810072043.AA03464@void.ai.mit.edu>
To: carr%car@cs
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 13:30:30 MDT <8810071930.AA25143@car.utah.edu>
Subject: self reproducing code
Reply-To: jar@zurich.ai.mit.edu
*** EOOH ***
Date: Fri, 7 Oct 88 16:43:05 EDT
From: jar@void.ai.mit.edu (Jonathan Rees)
To: carr%car@cs
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 13:30:30 MDT <8810071930.AA25143@car.utah.edu>
Subject: self reproducing code
Reply-To: jar@zurich.ai.mit.edu
This works in both common lisp and scheme. You can expand the
backquotes into calls to list etc. if you like but I think this is
easier to understand. (As evidenced by the fact that I could generate
it from memory.)
(let ((x '`(let ((x ',x)) ,x)))
`(let ((x ',x)) ,x))
Summary-line: 7-Oct michaelf@decwrl.dec.com #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25246; Fri, 7 Oct 88 14:45:29 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA08608; Fri, 7 Oct 88 14:45:19 MDT
Received: from saturn.pa.dec.com by decwrl.dec.com (5.54.5/4.7.34)
id AA08422; Fri, 7 Oct 88 13:44:06 PDT
Received: from localhost by saturn.pa.dec.com (5.54.5/4.7.34)
id AA09432; Fri, 7 Oct 88 13:44:16 PDT
Message-Id: <8810072044.AA09432@saturn.pa.dec.com>
To: carr%car@cs (Harold Carr)
Subject: Re: self reproducing code
In-Reply-To: Your message of Fri, 07 Oct 88 13:30:30 -0600.
<8810071930.AA25143@car.utah.edu>
Date: Fri, 07 Oct 88 13:44:14 -0700
From: Michael A. Fetterman <michaelf@decwrl.dec.com>
*** EOOH ***
To: carr%car@cs (Harold Carr)
Subject: Re: self reproducing code
In-Reply-To: Your message of Fri, 07 Oct 88 13:30:30 -0600.
<8810071930.AA25143@car.utah.edu>
Date: Fri, 07 Oct 88 13:44:14 -0700
From: Michael A. Fetterman <michaelf@decwrl.dec.com>
The traditional piece of code to do this is a very famous piece of lambda
calculus:
((lambda (x) (x x)) (lambda (x) (x x)))
[Where the above is written in tradition lisp notation rather than in
lambda calculus notation].
The lambda calculus is very much like lisp or scheme, as you can tell. To
translate this to scheme, you get:
((lambda (x) (list x `',x)) '(lambda (x) (list x `',x)))
where I'm using quasi-quote from scheme r3rs.
If you don't have quasi-quote in your scheme, try:
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))
This same code should work fine in common lisp.
Summary-line: 7-Oct stever@Riverside.SCRC.Sym #self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25276; Fri, 7 Oct 88 15:39:05 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA10784; Fri, 7 Oct 88 15:38:51 MDT
Received: from HALEAKALA.S4CC.Symbolics.COM by IVORY.S4CC.Symbolics.COM via CHAOS with CHAOS-MAIL id 194006; Fri 7-Oct-88 17:04:11 EDT
Date: Fri, 7 Oct 88 17:04 EDT
From: stever@Riverside.SCRC.Symbolics.COM
Sender: Zippy@QUABBIN.SCRC.Symbolics.COM
Subject: self reproducing code
To: Harold Carr <carr%car@cs>
Cc: pass@cs, scheme@mc.lcs.mit.edu, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Message-Id: <19881007210401.2.LISP-MACHINE@HALEAKALA.S4CC.Symbolics.COM>
*** EOOH ***
Date: Fri, 7 Oct 88 17:04 EDT
From: stever@Riverside.SCRC.Symbolics.COM
Sender: Zippy@QUABBIN.SCRC.Symbolics.COM
Subject: self reproducing code
To: Harold Carr <carr%car@cs>
Cc: pass@cs, scheme@mc.lcs.mit.edu, shebs@apple.apple.com,
mohammad%hpcllz2@sde.hp.com
In-Reply-To: <8810071930.AA25143@car.utah.edu>
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,
Stephen
Summary-line: 7-Oct U09052@UICVM.BITNET #
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25286; Fri, 7 Oct 88 15:55:29 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA11334; Fri, 7 Oct 88 15:54:39 MDT
Message-Id: <8810072154.AA11334@cs.utah.edu>
Received: from UICVM.BITNET by CC.UTAH.EDU; Fri, 7 Oct 88 15:55 MDT
Received: by UICVM (Mailer X1.25) id 3599; Fri, 07 Oct 88 16:51:39 CDT
Date: 7 October 1988 16:50:27 CDT
From: U09052@UICVM.BITNET
To: CARR%CAR@cs
*** EOOH ***
Date: 7 October 1988 16:50:27 CDT
From: U09052@UICVM.BITNET
To: CARR%CAR@cs
I am sending you by "snail-mail" an article I published in Creative
Computing in 1980 on "Self-reproducing programs". It contains (at the end)
the Lisp code you are interested in.
Summary-line: 7-Oct bard@theory.lcs.mit.edu #self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25345; Fri, 7 Oct 88 17:05:33 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA13458; Fri, 7 Oct 88 17:05:18 MDT
Received: by toucan.LCS.MIT.EDU
id AA01684; Fri, 7 Oct 88 19:04:46 EDT
Date: Fri, 7 Oct 88 19:04:46 EDT
From: bard@theory.lcs.mit.edu
Message-Id: <8810072304.AA01684@toucan.LCS.MIT.EDU>
To: carr%car@cs
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
*** EOOH ***
Date: Fri, 7 Oct 88 19:04:46 EDT
From: bard@theory.lcs.mit.edu
To: carr%car@cs
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
My favorite is the PDP-11 machine code:
MOV --(PC), (R0)++
which copies itself throughout the machine's memory.
But it ain't lisp.
Summary-line: 7-Oct will@fog.cs.uoregon.edu #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25363; Fri, 7 Oct 88 17:22:58 MDT
Received: from mist.math.uoregon.edu by cs.utah.edu (5.54/utah-2.0-cs)
id AA14301; Fri, 7 Oct 88 17:22:51 MDT
Received: from fog.cs.uoregon.edu by mist.math.uoregon.edu; Fri, 7 Oct 88 16:18:46 PDT
Received: by fog.cs.uoregon.edu; Fri, 7 Oct 88 16:18:41 PDT
Date: Fri, 7 Oct 88 16:18:41 PDT
From: William Clinger <will@fog.cs.uoregon.edu>
Message-Id: <8810072318.AA25772@fog.cs.uoregon.edu>
To: carr%car@CS
Subject: Re: self reproducing code
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Organization: University of Oregon, Computer Science, Eugene OR
Cc:
*** EOOH ***
Date: Fri, 7 Oct 88 16:18:41 PDT
From: William Clinger <will@fog.cs.uoregon.edu>
To: carr%car@CS
Subject: Re: self reproducing code
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Organization: University of Oregon, Computer Science, Eugene OR
Cc:
In Scheme the code you are looking for might be something like
((lambda (x)
(list x (list 'quote x)))
'(lambda (x)
(list x (list 'quote x))))
You can't write something like ((lambda (lambda) ... because
lambda is a reserved word in Scheme (although some implementations
remove this restriction). On the other hand, I don't know why you'd
want to write it that way; "x" is shorter than "lambda".
A shorter self-reproducing expression is:
0
Peace, Will
Summary-line: 8-Oct FWHITE@G.BBN.COM #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25791; Sat, 8 Oct 88 11:58:01 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA28938; Sat, 8 Oct 88 11:57:47 MDT
Date: 8 Oct 1988 13:56-EDT
Sender: FWHITE@G.BBN.COM
Subject: Re: self reproducing code
From: FWHITE@G.BBN.COM
To: carr%car@CS
Cc: fwhite@BBN.COM
Message-Id: <[G.BBN.COM] 8-Oct-88 13:56:28.FWHITE>
In-Reply-To: <19881007200040.6.ALAN@QUESTION-AUTHORITY.AI.MIT.EDU>
*** EOOH ***
Date: 8 Oct 1988 13:56-EDT
Sender: FWHITE@G.BBN.COM
Subject: Re: self reproducing code
From: FWHITE@G.BBN.COM
To: carr%car@CS
Cc: fwhite@BBN.COM
In-Reply-To: <19881007200040.6.ALAN@QUESTION-AUTHORITY.AI.MIT.EDU>
Or if cheating is allowed, how about (in Common Lisp):
#1='#1#
Summary-line: 8-Oct iku.dk!danvy@uunet.UU.NET #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25849; Sat, 8 Oct 88 16:15:13 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA02854; Sat, 8 Oct 88 16:15:05 MDT
Received: from uunet.UU.NET (TCP 30003106601) by MC.LCS.MIT.EDU 8 Oct 88 17:54:32 EDT
Received: from mcvax.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA22266; Sat, 8 Oct 88 17:53:02 EDT
Received: by mcvax.cwi.nl; Sat, 8 Oct 88 22:23:48 +0100 (MET)
Received: from diku.dk
by dkuug.dk (3.2/smail2.5/ease)
id AA07492; Sat, 8 Oct 88 17:15:36 +0100
Received: by diku.dk (5.51/smail2.5/ease)
id AA14951; Sat, 8 Oct 88 17:15:22 +0100
Date: Sat, 8 Oct 88 17:15:22 +0100
From: mcvax!diku.dk!danvy@uunet.UU.NET (Olivier Danvy)
Message-Id: <8810081615.AA14951@diku.dk>
To: Alan@ai.ai.mit.edu, carr%car@cs
Subject: Re: self reproducing code
Cc: carr%car@cs, mohammad%hpcllz2@sde.hp.com, pass@cs, scheme@mc.lcs.mit.edu,
shebs@apple.apple.com
*** EOOH ***
Date: Sat, 8 Oct 88 17:15:22 +0100
From: mcvax!diku.dk!danvy@uunet.UU.NET (Olivier Danvy)
To: Alan@ai.ai.mit.edu, carr%car@cs
Subject: Re: self reproducing code
Cc: carr%car@cs, mohammad%hpcllz2@sde.hp.com, pass@cs, scheme@mc.lcs.mit.edu,
shebs@apple.apple.com
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
Summary-line: 8-Oct KMP@STONY-BROOK.SCRC.Symb #Re: self reproducing code
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA25910; Sat, 8 Oct 88 20:53:40 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA10632; Sat, 8 Oct 88 20:53:18 MDT
Received: from BOBOLINK.SCRC.Symbolics.COM by STONY-BROOK.SCRC.Symbolics.COM via CHAOS with CHAOS-MAIL id 473424; Sat 8-Oct-88 22:51:52 EDT
Date: Sat, 8 Oct 88 22:51 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: Re: self reproducing code
To: mcvax!diku.dk!danvy@uunet.UU.NET
Cc: Alan@ai.ai.mit.edu, carr%car@cs, mohammad%hpcllz2@sde.hp.com, pass@cs,
scheme@mc.lcs.mit.edu, shebs@apple.apple.com
In-Reply-To: <8810081615.AA14951@diku.dk>
Message-Id: <881008225128.4.KMP@BOBOLINK.SCRC.Symbolics.COM>
*** EOOH ***
Date: Sat, 8 Oct 88 22:51 EDT
From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
Subject: Re: self reproducing code
To: mcvax!diku.dk!danvy@uunet.UU.NET
Cc: Alan@ai.ai.mit.edu, carr%car@cs, mohammad%hpcllz2@sde.hp.com, pass@cs,
scheme@mc.lcs.mit.edu, shebs@apple.apple.com
In-Reply-To: <8810081615.AA14951@diku.dk>
() 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.
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA26669; Mon, 10 Oct 88 07:38:31 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA19565; Mon, 10 Oct 88 07:37:56 MDT
Received: by ATHENA.CS.YALE.EDU; Mon, 10 Oct 88 09:33:38 EDT
Date: Mon, 10 Oct 88 09:33:38 EDT
From: Ashwin Ram <ram-ashwin@YALE.ARPA>
Message-Id: <8810101333.AA05276@ATHENA.CS.YALE.EDU>
Received: by yale-ring (node-abc3/ABC3)
via WIMP-MAIL (Version 1.3/1.5) ; Mon Oct 10 09:24:25
To: carr%car@CS (Harold Carr)
Subject: Re: self reproducing code
Newsgroups: comp.lang.scheme
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Organization: Computer Science, Yale University, New Haven, CT 06520-2158
Reply-To: Ram-Ashwin@YALE.ARPA (Ashwin Ram)
*** EOOH ***
Date: Mon, 10 Oct 88 09:33:38 EDT
From: Ashwin Ram <ram-ashwin@YALE.ARPA>
To: carr%car@CS (Harold Carr)
Subject: Re: self reproducing code
Newsgroups: comp.lang.scheme
In-Reply-To: <8810071930.AA25143@car.utah.edu>
Organization: Computer Science, Yale University, New Haven, CT 06520-2158
Reply-To: Ram-Ashwin@YALE.ARPA (Ashwin Ram)
If you get any responses, could you please forward them to me?
Thanks.
-- Ashwin.
ARPA: Ram-Ashwin@cs.yale.edu
UUCP: {decvax,ucbvax,harvard,cmcl2,...}!yale!Ram-Ashwin
BITNET: Ram@yalecs
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA26949; Mon, 10 Oct 88 13:22:34 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA05433; Mon, 10 Oct 88 13:22:17 MDT
Received: from IBM.COM (TCP 30001235007) by MC.LCS.MIT.EDU 10 Oct 88 09:24:42 EDT
Date: 10 Oct 88 09:06:52 EDT
From: Cyril Alberga <ALBERGA@ibm.com>
To: scheme@mc.lcs.mit.edu
Message-Id: <101088.090653.alberga@ibm.com>
Subject: Self replicating code
*** EOOH ***
Date: 10 Oct 88 09:06:52 EDT
From: Cyril Alberga <ALBERGA@ibm.com>
To: scheme@mc.lcs.mit.edu
Subject: Self replicating code
Here is a brute-force expression which prints itself. This was in LISP370,
circa 1978.
(PRINT
( (LAMBDA (X Y)
(SEQ
(RPLACA (CDAR (CDDADR X)) (COPY Y))
(RPLACA (CDADR (CADADR X)) (COPY Y))
(EXIT X) ) )
(COPY
"(PRINT
( (LAMBDA (X Y)
(SEQ
(RPLACA (CDAR (CDDADR X)) (COPY Y))
(RPLACA (CDADR (CADADR X)) (COPY Y))
(EXIT X) ) ) (COPY "NIL) "NIL ) ) )
"(PRINT
( (LAMBDA (X Y)
(SEQ
(RPLACA (CDAR (CDDADR X)) (COPY Y))
(RPLACA (CDADR (CADADR X)) (COPY Y))
(EXIT X) ) ) (COPY "NIL) "NIL ) ) ) )
The uses of copy were to keep it from modifying itself.
Obviously, shared sub-structure could be used to shorten the
representation.
Cyril N. Alberga
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA28201; Tue, 11 Oct 88 05:50:17 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA27168; Tue, 11 Oct 88 05:50:11 MDT
Message-Id: <8810111150.AA27168@cs.utah.edu>
Received: from MITVMA.MIT.EDU (TCP 2227000003) by MC.LCS.MIT.EDU 11 Oct 88 07:15:39 EDT
Received: from MITVMA.MIT.EDU by MITVMA.MIT.EDU (IBM VM SMTP R1.1) with BSMTP id 1995; Tue, 11 Oct 88 07:13:31 EDT
Received: from IRUCCIBM by MITVMA.MIT.EDU (Mailer X1.25) with BSMTP id 1994;
Tue, 11 Oct 88 07:13:29 EDT
Received: from IRUCCVAX.UCC.IE by IRUCCIBM (Mailer X1.25) with BSMTP id 0193;
Mon, 10 Oct 88 15:45:35 IST
Date: Mon, 10 Oct 88 15:48 GMT
From: "G.OULSNAM" <STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU>
Subject: self-replicating code
To: SCHEME@MC.LCS.MIT.EDU
X-Vms-To: SCHEME
*** EOOH ***
Date: Mon, 10 Oct 88 15:48 GMT
From: "G.OULSNAM" <STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU>
Subject: self-replicating code
To: SCHEME@MC.LCS.MIT.EDU
X-Vms-To: SCHEME
Various respondents to the question of self-replicating anonymous lambda
expressions have given us solutions, but no derivations. I hope therefore
that the following contribution might be of interest.
If one has a normal-order evaluator in Scheme rather than an applicative
order one then the simplest self-replicating lambda expression is
((lambda (x) (x x)) (lambda (x) (x x)))
since the argument expression is substituted without being evaluated, but
loops forever with applicative order.
Any approach to generating self-replication in applicative order evaluators
must therefore include emulation of normal-order evaluation. Consider as a
first attempt:
(define f (lambda (x) (list 'f x)))
This doesn't quite work because the x in the list will be replaced by its
value. So a better attempt is:
(define f (lambda (x) (list 'f <reconstruction-of-x>)))
As a first step towards eliminating the recursive use of f, it makes sense
to pass f an argument that will evaluate to the lambda expression for f at
the 'f position, but will not itself (the argument that is) be evaluated to
f. The insight for this comes by recognizing that ((lambda () <body>))
evaluates to <body>. This suggests that f be recast to the form:
(define f (lambda (x) (list (x) <reconstruction-of-x>)))
and that it be passed the argument: (lambda () 'f). (This is where the
normal-order evaluation is emulated.)
The reconstruction of x can now be accomplished to give for f:
(define f (lambda (x) (list (x) (list 'lambda '() 'f))))
followed again by the elimination of 'f to yield:
(define f
(lambda (x)
(list (x)
(list 'lambda '() (list 'quote (x))))))
It can be verified that:
> (f (lambda () 'f)
(f (lambda () 'f)
>
Elimination of the define statement is now straightforward, to yield the
required anonymous self-replicating expression:
((lambda (x)
(list (x)
(list 'lambda '() (list 'quote (x)))))
(lambda ()
'(lambda (x)
(list (x)
(list 'lambda '() (list 'quote (x)))))))
Any comments?
Gordon Oulsnam
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA28267; Tue, 11 Oct 88 09:23:02 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA02848; Tue, 11 Oct 88 09:22:53 MDT
Received: from NSS.Cs.Ucl.AC.UK (TCP 20012204403) by MC.LCS.MIT.EDU 11 Oct 88 10:53:58 EDT
Received: from aiai.edinburgh.ac.uk by NSS.Cs.Ucl.AC.UK via Janet with NIFTP
id aa03181; 10 Oct 88 15:39 BST
Date: Mon, 10 Oct 88 15:39:36 BST
Message-Id: <10500.8810101439@subnode.aiai.ed.ac.uk>
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Subject: Re: self reproducing code
To: scheme@mc.lcs.mit.edu
*** EOOH ***
Date: Mon, 10 Oct 88 15:39:36 BST
From: Jeff Dalton <jeff%aiai.edinburgh.ac.uk@NSS.Cs.Ucl.AC.UK>
Subject: Re: self reproducing code
To: scheme@mc.lcs.mit.edu
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 '**)) **)))))
-- Jeff
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA29177; Tue, 11 Oct 88 17:51:07 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA21848; Tue, 11 Oct 88 17:50:54 MDT
Received: from EDDIE.MIT.EDU by MC.LCS.MIT.EDU via Chaosnet; 11 OCT 88 19:19:13 EDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA20412@EDDIE.MIT.EDU>; Tue, 11 Oct 88 19:18:42 EDT
Received: by BLOOM-BEACON.MIT.EDU with sendmail-5.59/4.7
id <AA29975@BLOOM-BEACON.MIT.EDU>; Tue, 11 Oct 88 18:55:18 EDT
Received: from USENET by bloom-beacon.mit.edu with netnews
for scheme@mc.lcs.mit.edu (scheme@mc.lcs.mit.edu)
(contact usenet@bloom-beacon.mit.edu if you have questions)
Date: 11 Oct 88 22:24:52 GMT
From: sun.soe!sun.soe.clarkson.edu!gary@tcgould.tn.cornell.edu (Gary Levin)
Organization: Clarkson University
Subject: Re: self reproducing code
Message-Id: <GARY.88Oct11182452@milo.mcs.clarkson.edu>
References: <10500.8810101439@subnode.aiai.ed.ac.uk>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
*** EOOH ***
Date: 11 Oct 88 22:24:52 GMT
From: sun.soe!sun.soe.clarkson.edu!gary@tcgould.tn.cornell.edu (Gary Levin)
Organization: Clarkson University
Subject: Re: self reproducing code
References: <10500.8810101439@subnode.aiai.ed.ac.uk>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
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
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA29347; Wed, 12 Oct 88 02:08:04 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA28514; Wed, 12 Oct 88 02:07:56 MDT
Received: by kestrel.arpa (5.58/SMI-DDN)
id AA16036; Wed, 12 Oct 88 01:07:26 PDT
Date: Wed, 12 Oct 88 01:07:26 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
Message-Id: <8810120807.AA16036@kestrel.arpa>
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
*** EOOH ***
Date: Wed, 12 Oct 88 01:07:26 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
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
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA29368; Wed, 12 Oct 88 03:37:21 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA29288; Wed, 12 Oct 88 03:37:11 MDT
Received: from kestrel.arpa (TCP 1200600040) by MC.LCS.MIT.EDU 12 Oct 88 04:08:34 EDT
Received: by kestrel.arpa (5.58/SMI-DDN)
id AA16036; Wed, 12 Oct 88 01:07:26 PDT
Date: Wed, 12 Oct 88 01:07:26 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
Message-Id: <8810120807.AA16036@kestrel.arpa>
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
*** EOOH ***
Date: Wed, 12 Oct 88 01:07:26 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
In-Reply-To: Harold Carr's message of Fri, 7 Oct 88 14:19:26 MDT <8810072019.AA25193@car.utah.edu>
Subject: self reproducing code
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
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA29603; Wed, 12 Oct 88 10:39:41 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA07201; Wed, 12 Oct 88 10:39:25 MDT
Message-Id: <8810121639.AA07201@cs.utah.edu>
Received: from MITVMA.MIT.EDU (TCP 2227000003) by MC.LCS.MIT.EDU 12 Oct 88 12:11:03 EDT
Received: from MITVMA.MIT.EDU by MITVMA.MIT.EDU (IBM VM SMTP R1.1) with BSMTP id 9799; Wed, 12 Oct 88 12:07:43 EDT
Received: from IRUCCIBM by MITVMA.MIT.EDU (Mailer X1.25) with BSMTP id 9798;
Wed, 12 Oct 88 12:06:34 EDT
Received: from IRUCCVAX.UCC.IE by IRUCCIBM (Mailer X1.25) with BSMTP id 1372;
Wed, 12 Oct 88 16:34:38 IST
Date: Wed, 12 Oct 88 16:35 GMT
From: "G.OULSNAM" <STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU>
Subject: Self-reproducing code (correction)
To: SCHEME@MC.LCS.MIT.EDU
X-Vms-To: SCHEME
*** EOOH ***
Date: Wed, 12 Oct 88 16:35 GMT
From: "G.OULSNAM" <STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU>
Subject: Self-reproducing code (correction)
To: SCHEME@MC.LCS.MIT.EDU
X-Vms-To: SCHEME
My thanks to John Gateley for pointing out the erroneous claim regarding
the normal order/applicative order evaluation of ((lambda (x) (x x) (lambda
(x) (x x)). I'm sorry he chose not to examine the rest of the derivation,
as it did not rely on the erroneous claim. For the record, what I now
consider I should have written was:
"Consider
((lambda (x) (x x)) (lambda (x) (x x))).
With normal order evaluation this reproduces itself, but loops forever on
attempting to evaluate the result. However, in Scheme the
argument is evaluated to an internal procedure, say #<procedure>, which
then loops forever trying to evaluate the first (x x) in the above
expression, without reproducing the original form directly."
The remark about Scheme applies to TI Scheme (v2), and can be checked by
depositing extra code to see what is being passed around. My point was, and
remains, that both normal order and applicative order (by-value in Scheme)
cause the above to loop, but for different reasons. Normal order provided
the idea for self-reproducing code, if one could first find a way to
emulate normal order evaluation, and then find a way to stop evaluation of
the result. The remainder of the article showed how.
Gordon Oulsnam.
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA29691; Wed, 12 Oct 88 12:02:08 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA11572; Wed, 12 Oct 88 12:01:48 MDT
Received: from EDDIE.MIT.EDU by MC.LCS.MIT.EDU via Chaosnet; 12 OCT 88 12:36:11 EDT
Received: by EDDIE.MIT.EDU with UUCP with smail2.5 with sendmail-5.45/4.7 id <AA07031@EDDIE.MIT.EDU>; Wed, 12 Oct 88 12:35:42 EDT
Received: by BLOOM-BEACON.MIT.EDU with sendmail-5.59/4.7
id <AA19237@BLOOM-BEACON.MIT.EDU>; Wed, 12 Oct 88 12:09:38 EDT
Received: from USENET by bloom-beacon.mit.edu with netnews
for scheme@mc.lcs.mit.edu (scheme@mc.lcs.mit.edu)
(contact usenet@bloom-beacon.mit.edu if you have questions)
Date: 10 Oct 88 22:58:15 GMT
From: dewey.soe.berkeley.edu!oster@ucbvax.berkeley.edu (David Phillip Oster)
Organization: School of Education, UC-Berkeley
Subject: Re: Self-reproduction
Message-Id: <26381@ucbvax.BERKELEY.EDU>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
*** EOOH ***
Date: 10 Oct 88 22:58:15 GMT
From: dewey.soe.berkeley.edu!oster@ucbvax.berkeley.edu (David Phillip Oster)
Organization: School of Education, UC-Berkeley
Subject: Re: Self-reproduction
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
A cute trick, not quite a self-reproducing program, but an interesting
example of a string that produces itself, is to take an arbitrary error
message, and hand it back to the interpreter as input. On many systems if
you repeat this 4-8 times, you reach a fixed point at which no further
change occurs. This is also fun with a C compiler.
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA00414; Thu, 13 Oct 88 02:58:28 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA03251; Thu, 13 Oct 88 02:58:22 MDT
Received: from mcvax.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA25781; Thu, 13 Oct 88 04:58:07 EDT
Received: by mcvax.cwi.nl; Wed, 12 Oct 88 04:47:36 +0100 (MET)
Received: from ski.cs.vu.nl by botter.cs.vu.nl id aa02469; 11 Oct 88 18:57 MET
To: carr%car@cs
From: J A Biep Durieux <mcvax!cs.vu.nl!biep@uunet.UU.NET>
Subject: Re: self reproducing code
Newsgroups: comp.lang.scheme
In-Reply-To: <8810072019.AA25193@car.utah.edu>
References: <19881007200040.6.ALAN@QUESTION-AUTHORITY.AI.MIT.EDU>
Organization: VU Informatica, Amsterdam
Cc:
Date: Tue, 11 Oct 88 18:58:01 MET
Sender: mcvax!cs.vu.nl!biep@uunet.UU.NET
Message-Id: <8810111858.aa17014@ski.cs.vu.nl>
*** EOOH ***
To: carr%car@cs
From: J A Biep Durieux <mcvax!cs.vu.nl!biep@uunet.UU.NET>
Subject: Re: self reproducing code
Newsgroups: comp.lang.scheme
In-Reply-To: <8810072019.AA25193@car.utah.edu>
References: <19881007200040.6.ALAN@QUESTION-AUTHORITY.AI.MIT.EDU>
Organization: VU Informatica, Amsterdam
Cc:
Date: Tue, 11 Oct 88 18:58:01 MET
Sender: mcvax!cs.vu.nl!biep@uunet.UU.NET
If you want trivial ones too, what about
NIL
or, even shorter
T
?
--
Biep. (biep@cs.vu.nl via mcvax)
Never confound "power", "command" with "right",
especially not when it concerns our own body!
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA00973; Thu, 13 Oct 88 14:40:38 MDT
Received: by cs.utah.edu (5.54/utah-2.0-cs)
id AA19175; Thu, 13 Oct 88 14:40:25 MDT
Received: from aic.nrl.navy.mil (TCP 3200200010) by MC.LCS.MIT.EDU 12 Oct 88 13:45:38 EDT
Return-Path: <hoey@aic.nrl.navy.mil>
Received: Wed, 12 Oct 88 13:43:58 EDT by aic.nrl.navy.mil id AA19260
Date: Wed, 12 Oct 88 13:43:58 EDT
From: Dan Hoey <hoey@aic.nrl.navy.mil>
Message-Id: <8810121743.AA19260@aic.nrl.navy.mil>
To: scheme@mc.lcs.mit.edu
Subject: Automatic programming
*** EOOH ***
Return-Path: <hoey@aic.nrl.navy.mil>
Date: Wed, 12 Oct 88 13:43:58 EDT
From: Dan Hoey <hoey@aic.nrl.navy.mil>
To: scheme@mc.lcs.mit.edu
Subject: Automatic programming
My favorite version of the LAMBDA self-reproducer is
((LAMBDA (LAMBDA) `(,LAMBDA ',LAMBDA))
'(LAMBDA (LAMBDA) `(,LAMBDA ',LAMBDA)))
though SCHEMErs will have to forgo the pun. There is also
(format t "~A~:*~S)" "(format t \"~A~:*~S)\" ")
Dan
Received: by car.utah.edu (5.54/utah-2.0-leaf)
id AA01218; Fri, 14 Oct 88 02:08:47 MDT
Received: from MC.LCS.MIT.EDU by cs.utah.edu (5.59/utah-2.0-cs)
id AA13301; Fri, 14 Oct 88 02:08:40 MDT
Received: from BLOOM-BEACON.MIT.EDU (TCP 2224000021) by MC.LCS.MIT.EDU 14 Oct 88 03:44:02 EDT
Received: by BLOOM-BEACON.MIT.EDU with sendmail-5.59/4.7
id <AA07904@BLOOM-BEACON.MIT.EDU>; Thu, 13 Oct 88 23:46:04 EDT
Received: from USENET by bloom-beacon.mit.edu with netnews
for scheme@mc.lcs.mit.edu (scheme@mc.lcs.mit.edu)
(contact usenet@bloom-beacon.mit.edu if you have questions)
Date: 12 Oct 88 09:58:03 GMT
From: mcvax!enea!kth!draken!Urd!newsuser@uunet.uu.net (LTH network news server)
Organization: Dept. of Automatic Control, Lund Inst. of Technology, Sweden
Subject: Self-reproducing code
Message-Id: <1988Oct12.105804.3747@LTH.Se>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
*** EOOH ***
Date: 12 Oct 88 09:58:03 GMT
From: mcvax!enea!kth!draken!Urd!newsuser@uunet.uu.net (LTH network news server)
Organization: Dept. of Automatic Control, Lund Inst. of Technology, Sweden
Subject: Self-reproducing code
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
Several examples of self-reproducing code has been given in this group
lately. While running a definite risc of reminding people of what may
be already generally known, I would like to submit the shortest solution
of all. And not only the shortest, it will work in almost any language!
The solution is:
The only problem with this solution, the empty program, is that someone
might argue that it is not a program at all. Still, I think it has a
certain elegance to it.
"Real Programmers aren't afraid of RISC architectures."
--
Jan Eric Larsson janeric@Control.LTH.Se +46 46 108795
Department of Automatic Control
Lund Institute of Technology "We watched the thermocouples dance to the
Box 118, S-221 00 LUND, Sweden spirited tunes of a high frequency band."
Received: from cs.utah.edu by car.utah.edu (5.59/utah-2.0-leaf)
id AA02703; Mon, 17 Oct 88 12:07:50 MDT
Received: from KESTREL.ARPA by cs.utah.edu (5.59/utah-2.0-cs)
id AA03697; Mon, 17 Oct 88 12:07:01 MDT
Received: by kestrel.arpa (5.58/SMI-DDN)
id AA14370; Mon, 17 Oct 88 07:50:21 PDT
Date: Mon, 17 Oct 88 07:50:21 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
Message-Id: <8810171450.AA14370@kestrel.arpa>
To: carr%car@cs
Subject: Lisp function which returns its own defining form
*** EOOH ***
Date: Mon, 17 Oct 88 07:50:21 PDT
From: gyro@kestrel.arpa (Scott B. Layson)
To: carr%car@cs
Subject: Lisp function which returns its own defining form
In deference to the recent complaints, I'm not sending this to the
whole list, but I thought you'd like to see it, since I had promised
it:
(defun generate-self ()
(let ((foo (quote (lambda (x)
(list (quote defun) (quote generate-self)
(list (quote let)
(list (list (quote foo)
(list (quote quote) x)))
(quote (funcall foo foo))))))))
(funcall foo foo)))
As you can see, it makes use of the somewhat archaic property retained
in Common Lisp that a list whose car is 'LAMBDA is a funcallable
object. To do the same thing in Scheme requires an explicit call to
EVAL, which makes it a little plainer what's going on.
-- Scott
Received: from cs.utah.edu by car.utah.edu (5.59/utah-2.0-leaf)
id AA03897; Wed, 19 Oct 88 05:20:38 MDT
Received: from uunet.UU.NET by cs.utah.edu (5.59/utah-2.0-cs)
id AA09978; Wed, 19 Oct 88 05:20:29 MDT
Received: from mcvax.UUCP by uunet.UU.NET (5.59/1.14) with UUCP
id AA05951; Wed, 19 Oct 88 07:19:56 EDT
Received: by mcvax.cwi.nl; Mon, 17 Oct 88 14:28:41 +0100 (MET)
Received: by inria.inria.fr with Fnet-EUnet; Fri, 14 Oct 88 14:39:17 +0100 (MET)
Date: Fri, 14 Oct 88 12:00:25 -0100
From: mcvax!poly!queinnec@uunet.UU.NET (Queinnec Christian)
Message-Id: <8810141100.AA23995@poly.poly.fr>
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
Subject: Self reproducing code
*** EOOH ***
Date: Fri, 14 Oct 88 12:00:25 -0100
From: mcvax!poly!queinnec@uunet.UU.NET (Queinnec Christian)
To: carr%car@cs
Cc: scheme@mc.lcs.mit.edu
Subject: Self reproducing code
I wrote these two solutions several years ago after seeing the original
problem in the McCarthy's paper "Lisp Micro-Manual, not the whole
truth" as a little exercice. Something like (as I remember)
Find s such that (equal s (eval s))
which is self-reproducing code.
They are written in Le-Lisp and can be found as examples in its manual
after description of EQUAL.
((lambda (s) `(,(car s) ',s))
'((lambda (s) `(,(car s) ',s))) )
and using old-style FLAMBDA (fexprs)
((flambda (s) `(,s ,s)) (flambda (s) `(,s ,s)))
which bears strong similarity to a certain lambda term.
-----------------------------------------------------------------------
New Address !!! Christian Queinnec
LIX Laboratoire d'Informatique de l'\'Ecole Polytechnique
Route de Saclay 91128 Palaiseau Cedex France
Internet: queinnec@poly.poly.fr Earn: QUEINNEC at FRPOLY11
-----------------------------------------------------------------------
Received: from cs.utah.edu by car.utah.edu (5.59/utah-2.0-leaf)
id AA07808; Tue, 25 Oct 88 17:04:02 MDT
Received: from MC.LCS.MIT.EDU by cs.utah.edu (5.59/utah-2.0-cs)
id AA10378; Tue, 25 Oct 88 17:03:53 MDT
Received: from MITVMA.MIT.EDU (TCP 2227000003) by MC.LCS.MIT.EDU 24 Oct 88 14:56:59 EDT
Received: from MITVMA.MIT.EDU by MITVMA.MIT.EDU (IBM VM SMTP R1.1) with BSMTP id 3598; Mon, 24 Oct 88 09:37:18 EDT
Received: from DB0TUI6.BITNET (ZTUBTFAL) by MITVMA.MIT.EDU (Mailer X1.25) with
BSMTP id 3597; Mon, 24 Oct 88 09:22:50 EDT
Received: by tub.UUCP; Mon, 24 Oct 88 13:38:39 +0200; AA06867
Received: by tub-tfs.uucp (4.0/SMI-3.0DEV3)
id AA20497; Mon, 24 Oct 88 13:40:34 +0100
Date: Mon, 24 Oct 88 13:40:34 +0100
From: alti%tub-tfs.uucp%TUB.BITNET@MITVMA.MIT.EDU (Thorsten Altenkirch)
Message-Id: <8810241240.AA20497@tub-tfs.uucp>
To: tub!scheme%mc.lcs.mit.edu
Subject: Re: self-replicating-code, self-replicating-messages
*** EOOH ***
Date: Mon, 24 Oct 88 13:40:34 +0100
From: alti%tub-tfs.uucp%TUB.BITNET@MITVMA.MIT.EDU (Thorsten Altenkirch)
To: tub!scheme%mc.lcs.mit.edu
Subject: Re: self-replicating-code, self-replicating-messages
I find it more interesting to discuss things like self replicating
code than technical details of SCHEME Implementations. Perhaps I am
on the wrong mailing list. Is there one about functional-programming,
lambda-calculus, theory and application ???
The most solutions to the problem were quite tricky. The reason is
that the problem was ill defined. The most interesting contributioon
came from
"G.OULSNAM" <uunet!MITVMA.MIT.EDU!STCS8004%IRUCCVAX.UCC.IE@tub.UUCP>
((lambda (x) (x x)) (lambda (x) (x x)))
The critic was that these expression has no normal form - even worse
it is an example for an so called non solvable term, which puts even
a lazy evaluator (which does only head reductions) into an infinite
loop.
But the point is, that every solution to the proble has no normal
form, because if :
x ---> x
(---> means reduces to), than you can go on reducing x...
More interesting is another question : Is there a function, which
returns itself for every argument ?
This problem can be solved more straightforward. You just need a
solution for the equation
f x = f , for every x.
This can be done with the fixed-point-combinator Y. The solution is
f = Y K
or in lambda notation :
f = lambda f . ( lambda x . f x x ) ( lambda x . f x x )
(lambda x y . x)
The Y - Kombinator is a relative of letrec in scheme, so in scheme you
would write :
(define y-k (letrec ((h (lambda (x) h))) h))
It is also possible to define Y in terms of simple scheme expressions
without refering to letrec at all :
(define (yy y f x) ((f ((y y) f)) x))
(define y (yy yy))
So now you can just write :
(define (k x) (lambda (y) x))
(define y-k (y k))
Thorsten
Received: from cs.utah.edu by car.utah.edu (5.59/utah-2.0-leaf)
id AA08172; Wed, 26 Oct 88 11:42:43 MDT
Received: from MC.LCS.MIT.EDU by cs.utah.edu (5.59/utah-2.0-cs)
id AA03858; Wed, 26 Oct 88 11:42:26 MDT
Received: from MITVMA.MIT.EDU (TCP 2227000003) by MC.LCS.MIT.EDU 26 Oct 88 13:16:05 EDT
Received: from MITVMA.MIT.EDU by MITVMA.MIT.EDU (IBM VM SMTP R1.1) with BSMTP id 1800; Wed, 26 Oct 88 13:13:48 EDT
Received: from DB0TUI6.BITNET (ZTUBTFAL) by MITVMA.MIT.EDU (Mailer X1.25) with
BSMTP id 1798; Wed, 26 Oct 88 13:13:04 EDT
Received: by tub.UUCP; Wed, 26 Oct 88 18:11:43 +0200; AA12857
Received: by tub-tfs.uucp (4.0/SMI-3.0DEV3)
id AA05234; Wed, 26 Oct 88 18:13:44 +0100
Date: Wed, 26 Oct 88 18:13:44 +0100
From: alti%tub-tfs.uucp%TUB.BITNET@MITVMA.MIT.EDU (Thorsten Altenkirch)
Message-Id: <8810261713.AA05234@tub-tfs.uucp>
To: tub!uunet!rice.edu!dorai
Cc: tub!scheme%mc.lcs.mit.edu
In-Reply-To: Dorai Sitaram's message of Tue, 25 Oct 88 22:46:50 CDT
<8810260346.AA26475@titan.rice.edu>
Subject: self-replicating-code, self-replicating-messages
*** EOOH ***
Date: Wed, 26 Oct 88 18:13:44 +0100
From: alti%tub-tfs.uucp%TUB.BITNET@MITVMA.MIT.EDU (Thorsten Altenkirch)
To: tub!uunet!rice.edu!dorai
Cc: tub!scheme%mc.lcs.mit.edu
In-Reply-To: Dorai Sitaram's message of Tue, 25 Oct 88 22:46:50 CDT
<8810260346.AA26475@titan.rice.edu>
Subject: self-replicating-code, self-replicating-messages
> I think you are confusing the phenomenon of reduction to normal form
> in the lambda calculus with the process of evaluation which takes
> place in the case of a Scheme program yielding a value.
Sorry, I haven't been clear here. There is a strong analogy between
reduction and evaluation, but it's not the same thing. For me the
lambda calculus serves as a principial model of functional languages,
which can be used to understand certain aspects of these languages
without the overload of accidential properties of implementations. So
evaluation relates to reduction and values to normal forms.
There are functional languages which use reduction as evaluation.
MIRANDA is such an example, it uses a reduction machine for lazy
evaluation. See the book of Simon L. Peyton Jones ("The implementation
of functional programming languages", Prentice/Hall, 1988) for how
lazy functional languages are implemented by reduction machines.
> E.g., the result of the program (list 'list 8) is (list 8), *not* (8),
> which would have been the case in the case of continual reduction.
I think the relation between normal forms and values is, that normal
forms somehow denotate values. The point that lisp values can be lisp
programs again is - as important it is for programming practice - only
confusing here.
> >(define (yy y f x) ((f ((y y) f)) x))
> >(define y (yy yy))
> You doubtless imply currying, viz.,
> (define yy (lambda (y) (lambda (f) (lambda (x) ((f ((y y) f)) x)))))
I am sorry, somehow I copied the old version of the function into my
buffer. I imply nothing it's just a mistake - your version is the
correct one.
Thank you for your comments . . .
Until now nobody has answered my other question (mailing list for
theoretical questions of functional programming).
Thorsten
Received: from cs.utah.edu by car.utah.edu (5.59/utah-2.0-leaf)
id AA08882; Thu, 27 Oct 88 15:33:32 MDT
Received: from MC.LCS.MIT.EDU by cs.utah.edu (5.59/utah-2.0-cs)
id AB05648; Thu, 27 Oct 88 15:33:14 MDT
Received: from BLOOM-BEACON.MIT.EDU (TCP 2224000021) by MC.LCS.MIT.EDU 27 Oct 88 16:16:53 EDT
Received: by BLOOM-BEACON.MIT.EDU with sendmail-5.59/4.7
id <AA22826@BLOOM-BEACON.MIT.EDU>; Thu, 27 Oct 88 05:47:31 EDT
Received: from USENET by bloom-beacon.mit.edu with netnews
for scheme@mc.lcs.mit.edu (scheme@mc.lcs.mit.edu)
(contact usenet@bloom-beacon.mit.edu if you have questions)
Date: 26 Oct 88 00:58:21 GMT
From: pasteur!agate!saturn!kjell@ames.arpa (Kjell Post)
Organization: University of California, Santa Cruz
Subject: Re: self-replicating-code, self-replicating-messages
Message-Id: <5259@saturn.ucsc.edu>
References: <8810241240.AA20497@tub-tfs.uucp>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
*** EOOH ***
Date: 26 Oct 88 00:58:21 GMT
From: pasteur!agate!saturn!kjell@ames.arpa (Kjell Post)
Organization: University of California, Santa Cruz
Subject: Re: self-replicating-code, self-replicating-messages
References: <8810241240.AA20497@tub-tfs.uucp>
Sender: scheme-request@mc.lcs.mit.edu
To: scheme@mc.lcs.mit.edu
In article <8810241240.AA20497@tub-tfs.uucp> alti@tub-tfs.UUCP (Thorsten Altenkirch) writes:
>I find it more interesting to discuss things like self replicating
>code than technical details of SCHEME Implementations. Perhaps I am
>on the wrong mailing list. Is there one about functional-programming,
>lambda-calculus, theory and application ???
I haven't seen one but I certainly wouldn't mind.
By the way, why isn't there a comp.lang.ml?
fun Y f x = f (Y f) x;
fun fac x = Y (fn f => fn x => if x = 0 then 1 else x*f(x-1)) x;
-------
That's it....