The Y Combinator, or How to Succeed at Recursion Without Really Recursing

http://mvanier.livejournal.com/2897.html

by edw519 • 18 years ago

27 18 18 years ago

mvanier.livejournal.com

ced3• 18 years ago

Math envy.

Why do hackers focus on it so much? It has only very remote relevance to normal programming.

The beautiful idea I see behind the Y combinator is that of formalism. Once you describe something in mathematical terms, magic can happen. But this would be much better illustrated by a good introduction to analysis or algebra. Even number theory has some cool results, and it's easier to grasp.

In my second course at university, the teacher proved by contradiction that 1 >= 0:

   Assume 1 is negative, 1 < 0
   Multiply both sides by 1, so that 1*1 > 0*1 (multiplication by a negative flips the inequality)
   1 being an identity, this implies 1 > 0, contradiction

That was one of the few Wow moments I had in my education. Short and to the point.

(that proof above is not really satisfactory, especially without the context and the axioms, but it served its purpose well five years ago)

silentbicycle7• 18 years ago

1. Conceptual elegance. It seems to me that recursion and the complexity that emerges from uses it fascinates many people. GEB comes to mind.

2. Directly dealing with these mathematical formalisms (the Y combinator, SKI combinators (http://en.wikipedia.org/wiki/SKI_combinator_calculus), etc.) can become really important in programs such as interpreters.

ced3• 18 years ago

1. I was writing and rewriting a rebuttal, but you're right... There is something cool about achieving self-reference without a name.

2. Really? If you feel like elaborating / providing link, I'd appreciate.

scott_s2• 18 years ago

Because describing something formally means you have a deep understanding of it. Formal descriptions require synthesizing the important concepts from the whole.

Understanding a new concept feels good intellectually, but it also gives you more power: now you can recognize that pattern elsewhere and perhaps apply new techniques.

databus• 18 years ago

God, if I see another code example using Factorial I am going to hurl.

silentbicycle7• 18 years ago

What are some other simple examples of recursion, though?

Quicksort would be pretty good for this, but the straightforward recursive version has several edge cases that lead to bad performance.

Getting the length of a linked list is probably a better example:

  (* ocaml *)
  let rec length l = match l with
     | []   -> 0
     | h::t -> 1 + length t

  ; scheme
  (define (length l)
     (if (null? l)
         0
         (+ 1 (len (cdr l))))

Neither of these is tail-recursive, of course, but that's another post entirely.

Any other ideas?

13ren2• 18 years ago

Does performance matter when seeking "simple" examples?

I vote for quicksort - not because it's quick, but because its implementation has the same form as its proof. It's simple if you use the Erlang-style version.

paulgb2• 18 years ago

Factorial is the hello world of functional programming. The fact that everyone knows it inside out aids the example, because the reader can focus on the important details (the Y Combinator).

silentbicycle7• 18 years ago

Agreed, but in a parallel universe where the parent post actually asked the implied question, what other functions would you suggest? I try to explain these things to other people enough that I'd love to hear other suggestions.

Map might be another good one, although for better and worse it expects the reader to follow the idea of first class functions. Something like

  map square [1, 2, 3, 4, 5] ---> [1, 4, 9, 16, 25]

is pretty simple, though.

luigi• 18 years ago

"Recursing" and "recurse" aren't words. Recursion comes from the word recur. A function recurs, not recurses. Got taught that during the infamous CS1321 Scheme course at Georgia Tech in 2001.

scott_s2• 18 years ago

They are now. Words become a part of the language because enough people use them.

13ren2• 18 years ago

"English is what English-speaking people speak"

The Y Combinator, or How to Succeed at Recursion Without Really Recursing

Related Stories