Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!killer!pollux!ti-csl!mips!gateley
From: gateley@mips.csc.ti.com (John Gateley)
Newsgroups: comp.lang.scheme
Subject: Re: self-replicating code
Message-ID: <60753@ti-csl.CSNET>
Date: 11 Oct 88 21:58:29 GMT
References: <8810111207.AA15692@BLOOM-BEACON.MIT.EDU>
Sender: news@ti-csl.CSNET
Reply-To: gateley@mips.UUCP (John Gateley)
Organization: TI Computer Science Center, Dallas
Lines: 26

In article <8810111207.AA15692@BLOOM-BEACON.MIT.EDU> STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU ("G.OULSNAM") writes:
>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.
[rest of derivation]
>Any comments?
>Gordon Oulsnam

I did not try to follow the rest of the derivation. Your first statement
is incorrect. The expression is an infinite loop in both normal and
applicative order evaluation. Also, the problem is even more complex
than normal order/applicative order. Scheme is a by-value system, which means
that

(lambda (x) (infinite-loop))

terminates in Scheme, but not in a by name system (such as the lambda calc).
I could not think of the smallest normal-order self-replicating code off
the top of my head.

John
gateley@mips.csc.ti.com