alti@tub-tfs.UUCP (Thorsten Altenkirch) (10/24/88)
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))
Thorstenkjell@saturn.ucsc.edu (Kjell Post) (10/26/88)
In article <8810241240.AA20497@tub-tfs.uucp> alti@tub-tfs.UUCP (Thorsten Altenkirch) writes: >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 ??? I haven't seen one but I certainly wouldn't mind. By the way, why isn't there a comp.lang.ml? fun Y f x = f (Y f) x; fun fac x = Y (fn f => fn x => if x = 0 then 1 else x*f(x-1)) x;
alti@tub-tfs.UUCP (Thorsten Altenkirch) (10/27/88)
> I think you are confusing the phenomenon of reduction to normal form > in the lambda calculus with the process of evaluation which takes > place in the case of a Scheme program yielding a value. Sorry, I haven't been clear here. There is a strong analogy between reduction and evaluation, but it's not the same thing. For me the lambda calculus serves as a principial model of functional languages, which can be used to understand certain aspects of these languages without the overload of accidential properties of implementations. So evaluation relates to reduction and values to normal forms. There are functional languages which use reduction as evaluation. MIRANDA is such an example, it uses a reduction machine for lazy evaluation. See the book of Simon L. Peyton Jones ("The implementation of functional programming languages", Prentice/Hall, 1988) for how lazy functional languages are implemented by reduction machines. > E.g., the result of the program (list 'list 8) is (list 8), *not* (8), > which would have been the case in the case of continual reduction. I think the relation between normal forms and values is, that normal forms somehow denotate values. The point that lisp values can be lisp programs again is - as important it is for programming practice - only confusing here. > >(define (yy y f x) ((f ((y y) f)) x)) > >(define y (yy yy)) > You doubtless imply currying, viz., > (define yy (lambda (y) (lambda (f) (lambda (x) ((f ((y y) f)) x))))) I am sorry, somehow I copied the old version of the function into my buffer. I imply nothing it's just a mistake - your version is the correct one. Thank you for your comments . . . Until now nobody has answered my other question (mailing list for theoretical questions of functional programming). Thorsten