Y Combinations
I found myself needing to use a Y-combinator last night, while playing with regular expressions. I wanted to recursively scan a string, finding matches inside other matches. Of course it could have been done by defining a function and calling it recursively, but that seemed unnecessary. I had a vague understanding of what a Y combinator was and what it could do, which allowed me to realise that it was what I needed in my regexp task. But of course I didn’t have one handy in my REPL of choice.
So that motivated me to spend the afternoon learning more about the Y combinator. Richard Gabriel’s Why of Y provided a good overview in Scheme, with me following along in a SBCL REPL — Which was a good experience about the differences between a Lisp-1 and a Lisp-2 in itself. An old post on Raganwald’s weblog had an implementation in Ruby, but it started a few steps in, so I spent some time re-deriving the contents of that post. I doubt that I’d be able to produce a Y combinator by myself yet, but it gave me a good idea how it works.
I ended up with (in Ruby):
def y &h
lambda { |g|
g[g]
}[lambda { |f| lambda { |*args| h[f[f],*args] } }]
end
And in Common-lisp:
(defun y (f)
(let ((g (lambda (h)
(lambda (n)
(funcall (funcall f (funcall h h)) n)))))
(funcall g g)))
But I also just learned about flet, which would simplify the CL version a bit.
There is a simpler Ruby version that they start with on Raganwald’s site:
def y(&f)
lambda { |*args| f[y(&f)][*args] }
end
And an equivalent Common-lisp version could be made (doesn’t seem very idiomatic, with the double funcall):
(defun y (f)
(lambda (args)
(funcall (funcall f (y f) args))))
I should post my working file that I used to nut it all out…
