Mike Vanier (mvanier) wrote,
Mike Vanier
mvanier

The Y Combinator (Slight Return)

or:

How to Succeed at Recursion Without Really Recursing

Tiger got to hunt,
Bird got to fly;
Lisper got to sit and wonder, (Y (Y Y))?

Tiger got to sleep,
Bird got to land;
Lisper got to tell himself he understand.

    — Kurt Vonnegut, modified by Darius Bacon

Introduction

I recently wrote a blog post about the Y combinator. Since then, I've received so many useful comments that I thought it was appropriate to expand the post into a more complete article. This article will go into greater depth on the subject, but I hope it'll be more comprehensible as well. You don't need to have read the previous post to understand this one (in fact, it's probably better if you haven't.) The only background knowledge I require is a tiny knowledge of the Scheme programming language including recursion and first-class functions, which I will review. Comments are (again) welcome.

Read moreCollapse )
Subscribe

Recent Posts from This Journal

  • Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 34 comments

Recent Posts from This Journal