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

*To*: SCHEME@MC.LCS.MIT.EDU*Subject*: self-replicating code*From*: "G.OULSNAM" <STCS8004%IRUCCVAX.UCC.IE@MITVMA.MIT.EDU>*Date*: Mon ,10 Oct 88 11:48:00 EDT

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

- Prev by Date:
**Scheme Mailing List** - Next by Date:
**Re: self reproducing code** - Previous by thread:
**Self replicating code** - Next by thread:
**Re: self-replicating code** - Index(es):