[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: self-replicating code
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]
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
(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.