STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU ("G.OULSNAM") (10/10/88)
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 Oulsnamgateley@mips.csc.ti.com (John Gateley) (10/12/88)
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