Scheming to learn recursion

Reading Gödel, Escher, Bach broadened my perspective on recursion and the idea of the pervasiveness of composition of self with self. Recursion is everywhere: in the Piaget’s genetic epistemology, where new mental abstractions are defined by existing ones; the actual neurological structure of our brain via feedback loops, and its digital analogue in neural networks; visicious and virtuous cycles in systems thinking and economics; fractals; and also in various programming languages, especially those with lamdba calculus roots.

One languages celebrating recursion is Guy Steele and Gerry Sussman’s Scheme, a dialect of of Lisp known for its minimal syntax and library. Scheme was created partially as a teaching aid for introductory computer science courses at MIT. Lisp, in turn, has its roots as a theoretical language in the AI Lab in the late 50’s. John McCarthy famously created it without intended it to be implemented; it took a student named Steve Russell to create the first interpreter. The LISP 1.5 Programmers Manual, by McCarthy himself, remarkably implements the entirety of a Lisp interpreter in a single page (see Appendix B’s definition of eval).

However, my initial interest in Lisp began with Paul Graham’s essays. He waxed eloquent in Hackers and Painters’s “Beating the Averages”, about how business with limited labor should be using programming languages that maximize their productivity, ideally via higher-level abstractions and meta-languages. Around the same time, I picked up a copy of Daniel Friedman’s Essentials of Programming Languages, an academic treatise on programming language theory that assumed a working knowledge of Scheme.

Rather than diving headfirst into the text, I figured it would better to start small and work my way up. What I’m reading now is The Little Schemer, also by Daniel Friedman. This book’s style is the complete opposite of Essentials; it assumes no experience programming, and works as a two-way dialogue, where the reader is encouraged to programming questions along the way. The tone is absurd in the vein of Why’s Poignant Guide, with pages devoted as a tablemat for PB&J sandwiches. It’s a quick read, but worthwhile if you’re looking for an entertaining weekend guide to recursive thinking.

It’s unfortunate the syntax of Lisp has been a roadblock, as its S-Expressions, enabling homoiconicity, are one of language’s strengths. M-Expressions, as McCarthy originally intended Lisp to be written in, were meant to provide a more familiar imperative facade to the language. This never caught on, even with valiant attempts by Apple with its Dylan language. Whether syntax is the reason, CS schools, and most famously MIT, have phased out teaching Scheme in their introductory courses. There’s an interesting debate about practicality of programming languages taught at the university level. Papert would argue that the first language you learn tends to influence your view of others, and in this case Scheme might be a good theoretical foundation. Python, on the other hand, has a strong resemblance to what we typically write as pseudocode, which may serve a more enlightened discourse for beginners. In any case, Lambda the Ultimate article explores the issue further.