In 1974, Daniel P. Friedman published a little book called The Little LISPer. It was only 68 pages, but it did a remarkable thing: It could teach you to think recursively. It used some pretend dialect of LISP (which was written in all caps in those days). The dialect didn't fully conform to any real LISP. But that was ok because it wasn't really about LISP, it was about recursive functions. You didn't need a computer in order to work through the exercises. After reading the book, I was changed. In a good way. There are very few books that deeply change the way that you think. This is one of those books.
The format is a programmed text with questions on the left side and answers on the right. The way you use it is to read a question, think about the question, come up with an answer, and then compare your answer to Friedman's answer.
He used the names of foods as the symbols that are manipulated by your functions, and little jokes were scattered around to pull you back when things get so deep that your head is going to pop off. It even has a place reserved for JELLY STAINS!
The book has been through several revisions. The latest, The Little Schemer (Fourth Edition), updated by Friedman and Matthias Felleisen, now conforms more closely to a real programming language, Scheme, and has new chapters which delve much deeper into recursive function theory and language processors.
Felleisen is not as comfortable with the programmed text format, so instead of questions and answers, he has a deranged dialog going on which reads a little like Sméagol and Gollum discussing (quote (fishes)).
The Little Schemer is not a complete book on programming. It is weak in practical concerns like documentation, defensive programming, and computational efficiency. The development of a system of arithmetic from three primitives is delightful from a mathematical perspective and shockingly horrible from an engineering perspective.
It also will not teach you very much about Scheme. It touches on only a very small part of the language: a very good part.
Despite its flaws, the book has a very loyal following and that is because it works. It teaches one thing, a thing that is very difficult to teach, a thing that every professional programmer should know, and it does it really well. These are lessons that stick with you. You need to grab a sandwich and study this book.
JavaScript has much in common with Scheme. It is a dynamic language. It has a flexible datatype (arrays) that can easily simulate s-expressions. And most importantly, functions are lambdas. All JavaScript programmers should have recursive functions in their toolkits.
Because of this deep similarity, all of the functions in The Little Schemer can be written in JavaScript. The syntaxes of these two languages are very different, so some transformation rules are needed.
Little Scheme |
JavaScript |
|---|---|
(define foo (lambda (a b c) (body))) |
const foo = function (a, b, c) {
return body;
};
|
function foo(a, b, c) {
return body;
}
|
|
(foo a b c) |
foo(a, b, c) |
(cond
(p1 e1)
(p2 e2)
(else en)
)
|
(
p1
? e1
: (
p2
? e2
: en
)
) |
(and p1 p2 ... pn) |
(p1 && p2 ... && pn) |
(or p1 p2 ... pn) |
(p1 || p2 ... || pn) |
'() |
null |
'a |
"a" |
'(a b c) |
["a", ["b", ["c"]]] |
foo? |
isFoo |
foo* |
foostar |
#t #f |
true false |
So get a copy of The Little Schemer and start recursing. I have prepared a file containing primitive functions (cons, cdr, etc.), a pair of functions (p and s) for converting from s-expressions to text and back), and most of the functions in the book, expressed in JavaScript.
Pay particular attention to The Applicative Order Y Combinator, one of the most strange and wonderful artifacts of Computer Science.
function Y(le) {
return (function (f) {
return f(f);
}(function (f) {
return le(function (x) {
return f(f)(x);
});
}));
}
Perhaps even more strange and wonderful, nowhere in this book about recursive functions is the Factorial Function ever mentioned. So here is my own special contribution to triteness and hackneyed banality:
var factorial = Y(function (fac) {
return function (n) {
return (
n <= 2
? n
: n * fac(n - 1)
);
};
});
var number120 = factorial(5);
The final chapter of The Little Schemer is a Little Scheme interpreter, capable of evaluating most of the expressions in the book. I made a couple of modifications.
I added the define function, which allows you to enter all of the Scheme functions and run them.
It can use your own JavaScript functions as Scheme primitives, so you can add new JavaScript capability without modifying the interpreter.
It runs in a web page, so you can execute your Scheme programs in any web browser. Just type your well-formed functions into the input box, press the big fat button, and see the result in the output box.
This interpreter was not designed for speed or reliability, so don't lean on it too hard. But it is responsive, and it is a good companion to the book.
(define demo '(((hotdogs))(and)(pickle) relish)) (car (car demo))