[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

self-replicating code

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