Re: [racket-dev] using the Y combinator to...
I'll hijack the thread since I've been meaning to ask about the Y combinator. From SICP I've seen that the Y combinator is the function (define (y f) ((lambda (x) (f (x x))) (lambda (x) (f (x x) This makes mathematical sense, since (y f) = ((lambda (x) (f (x x))) (lambda (x) (f (x x = (f ((lambda (x) (f (x x))) (lambda (x) (f (x x) = (f (y f)) But when actually applying it: // g improves a function to get a ceiling function. The fixed point would be similar to (lambda (x) (inexact-exact (ceiling x))) (define (g f) (lambda (x) (if (= x 0) 0 (+ 1 (f (- x 1)) ((g (g (g (g (g #f) 3.3) 4 Now let's step through ((y g) 3.3) = (((lambda (x) (g (x x))) (lambda (x) (g (x x 3.3) = ((g ((lambda (x) (g (x x))) (lambda (x) (g (x x) 3.3) now, to get the (g ...) result we need to apply g to it's operand. For that, we need to evaluate it: = ((g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x)) 3.3) = ((g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x 3.3) = ((g (g (g (g ((lambda (x) (g (x x))) (lambda (x) (g (x x) 3.3) And I just ran out of memory. What am I missing here? It seems obvious to me that if we add a delay/force or somesuch thing it solves the problem. But that's not the y-combinator I was shown. _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev
Re: [racket-dev] using the Y combinator to...
The use of the Y combinator (as opposed to the built-in forms of recursion) seems to be hacking around the ability for Ruby methods to be redefined more than anything? Robby On Sat, Jul 31, 2010 at 8:54 PM, Shriram Krishnamurthi s...@cs.brown.edu wrote: ...provide a mis-feature that the language thoughtfully left out: http://www.eecs.harvard.edu/~cduan/technical/ruby/ycombinator.shtml (The bit about lexical scoping in Ruby is also neat. It says that deep down, Ruby really is the same as JavaScript and Python.) Shriram _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev _ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/dev