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

*To*: scheme%mc.lcs.mit.edu@tub.uucp*Subject*: Re: self-replicating-code, self-replicating-messages*From*: alti%tub-tfs.uucp%TUB.BITNET@MITVMA.MIT.EDU (Thorsten Altenkirch)*Date*: Mon, 24 Oct 88 13:40:34 +0100

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 "G.OULSNAM" <uunet!MITVMA.MIT.EDU!STCS8004%IRUCCVAX.UCC.IE@tub.UUCP> ((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 loop. 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)) Thorsten

**Follow-Ups**:**Re: self-replicating-code, self-replicating-messages***From:*pasteur!agate!saturn!kjell@ames.arpa (Kjell Post)

- Prev by Date:
**Re: Wanted: most recent xscheme** - Next by Date:
**-------------------------- call for votes -------------------** - Previous by thread:
**case-lambda and interpreter environments** - Next by thread:
**Re: self-replicating-code, self-replicating-messages** - Index(es):