Posts tagged with ‘recursion’ (2)

I’m not putting this in the lambda-calculus series, though it touches on issues from the last post in the series, but specifically issues of recursion. I was curious to go back and recall how The Little Schemer dealt with problems of recursion (and the Y Combinator (which we still haven’t got properly to yet, but we will, I promise)). In Chapter 9 of The Little Schemer (“and Again, and Again, and Again,…"), it starts off by querying the reader if they want caviar and how to find it in a list, and then essentially gets (from caviar and grits) into issues around the halting problem.

From the previous entry in this series, one of the things of note in discussing the nature of the connections between LISP and (the) lambda calculus was John McCarthy’s concern about recursion and higher-order functions. A couple of excerpts from previous quotes from McCarthy on the subject to set the stage: …And so, the way in which to [be able to handle function passing/higher order functions] was to borrow from Church’s Lambda Calculus, to borrow the lambda definition.