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

Re: self-replicating-code, self-replicating-messages

I find it more interesting to discuss things like self replicating
code than technical details of SCHEME Implementations. Perhaps I am
on the wrong mailing list. Is there one about functional-programming,
lambda-calculus, theory and application ???

The most solutions to the problem were quite tricky. The reason is
that the problem was ill defined. The most interesting contributioon
came from

                  ((lambda (x) (x x)) (lambda (x) (x x)))

The critic was that these expression has no normal form - even worse
it is an example for an so called non solvable term, which puts even
a lazy evaluator (which does only head reductions) into an infinite

But the point is, that every solution to the proble has no normal
form, because if :

x ---> x

(---> means reduces to), than you can go on reducing x...

More interesting is another question : Is there a function, which
returns itself for every argument ?

This problem can be solved more straightforward. You just need a
solution for the equation

f x = f , for every x.

This can be done with the fixed-point-combinator Y. The solution is

f = Y K

or in lambda notation :

f = lambda f . ( lambda x . f x x ) ( lambda x . f x x )
        (lambda x y . x)

The Y - Kombinator is a relative of letrec in scheme, so in scheme you
would write :

(define y-k (letrec ((h (lambda (x) h))) h))

It is also possible to define Y in terms of simple scheme expressions
without refering to letrec at all :

(define (yy y f x) ((f ((y y) f)) x))
(define y (yy yy))

So now you can just write :

(define (k x) (lambda (y) x))
(define y-k (y k))