You can find some good links about it here(javascript), here (wikipedia), and there's a ton of results for it if you search with google.
In a nutshell it's a fixed point combinator that can generate a recursive function from a function that is not defined recursively.
Take the following tried and true example of recursion, the factorial!
(define factorial
(lambda (x)
(cond ((= x 0) 1)
(else (* x (factorial (- x 1)))))))
factorial is a function defined in terms of itself (references factorial).
What if this wasn't allowed in your language though? How could you write this?
Well if you had the Y combinator you could write a step of the factorial calculation and add an argument which would be the next operation to run after this step is complete.
(define factstep
(lambda (next)
(lambda (n)
(if (= n 0) 1 (* n (next (- n 1)))))))
Now if you want to use factstep to compute factorials you must first pass in the "next" operation, which yields another function which takes the parameter to the factorial.
; factorial 1
((factstep 'blah) 1)
; factorial 3
((factstep (factstep (factstep (factstep 0)))) 3)
As you can see this gets really tedious without recursion.
Enter the Y combinator:
(define Y
(lambda (le)
((lambda (f) (f f))
(lambda (f)
(le (lambda (x) ((f f) x)))))))
Looks like complete nonsense if you don't know how it is derived. There's many different websites that go into that, so I'm not going to. I'm looking for a practical use of this thing.
Well it turns out by applying Y to the function "factstep" you can create the factorial function you're after.
(define factorial (Y factstep))
Now (factorial 6) still yields 720. (Yes Y seems quite magical at this point if you don't understand it, so I suggest reading up on that if it is confusing to you)
So what good is this if we can just define functions recursively to begin with?
Well what if we want to weave in some other behaviors?
Let's look at a more interesting primitive recursive function like fibonacci.
(define fibstep
(lambda (next)
(lambda (n)
(cond
((<= n 1) 1)
(else (+ (next (- n 1)) (next (- n 2))))))))
This is known to be horribly inefficient as it redoes a lot of the same work? Want to watch how inefficient it is? Ok, let's add a trace step.
(define tracestep
(lambda (label f)
(lambda (g)
(lambda (n)
(let ((res ((f g ) n)))
(display label) (display " ") (display res) (newline)
res)))))
This simply passes through the previous steps, stores an intermediate value, and prints it using a label that's passed in. Here's how to use it.
(define traced-fib (Y (tracestep "fib" fibstep)))
Now if we run it for say "traced-fib 6"
> (traced-fib 6)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
13
Look at all of those steps!!! Clearly this sucks, and if you try something like (traced-fib 100) you'll be waiting for a long time for completion. It expands it's "recursion" via Y like a bomb!
How can we improve on this? Well without modifying fibstep, we could add memoization, so first I'll make a global memoization table (forgive the possibly poor choice of data structures here)
Memoization is a technique to prevent computing the same value twice, which we're doing a lot above per the trace. (Again this has been explained on the web a lot. Googling around for why may prove enlightening)
(define memoization-table (make-vector 100 0))
This is a vector of 100 0s. I'm only going to memoize 100 values of this computation statically.
So now I'll write the memoization step.
(define memoize
(lambda (f)
(lambda (g)
(lambda (n)
(let ((ref (vector-ref memoization-table n)))
(if
(= 0 ref)
(let ((val ((f g) n)))
(vector-set! memoization-table n val)
val)
ref))))))
The indexes of the memoization table are the results of f(i), where i is the ith fibonacci number. f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3... etc
Basically once we compute a value for i, we insert it in the table, so we can look it up again. if f(i) is 0, it means we have to compute it yet, but we'll only do it one time.
So how do I stack all of this up with Y?
(define traced-memo-fib (Y (memoize (tracestep "fib" fibstep))))
or if you don't want tracing
(define memo-fib (Y (memoize fibstep)))
Let's watch it run for 6 now
> (traced-memo-fib 6)
fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
13
How about something bigger?
> (traced-memo-fib 8)
fib 21
fib 34
34
It didn't have to compute up to 13, so it just did fib(7) and fib(8). If we reset the memoization table (reload the program) we can see all the steps again.
> (traced-memo-fib 8)
fib 1
fib 1
fib 2
fib 3
fib 5
fib 8
fib 13
fib 21
fib 34
34
Compare this to the unmemoized fibonacci:
> (traced-fib 8)
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 21
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 1
fib 1
fib 2
fib 1
fib 3
fib 8
fib 1
fib 1
fib 2
fib 1
fib 3
fib 1
fib 1
fib 2
fib 5
fib 13
fib 34
34
Yikes! That's a lot of waste there.
What I've been able to do with Y is write steps of a computation in near isolation of each other, and then compose them with Y to form a useful function (arguably... it's just fibonacci) to optimize and augment behaviors by weaving them together.
Now I'm not sure what this means for Y in terms of practicality, but it's kind of neat. Obviously one has to obey certain rules to use Y compositionally, but it's totally possible for some classes of problems. I'm not sure how my coworkers would react to my using this in any sort of production code. Could anyone read it? :-)
Ah well, that's why this blog is just stuff that interests me.
No comments:
Post a Comment