Eli Bendersky's website I like that higher-order functions are presented so early in the book. In some sense, it makes the inherent simplicity and power of Lisp apparent. Imagine pointers to functions explained in the first chapter of a book about C ! Since the syntax of Lisp is so uniform, the distinctions between code and data blend, which makes higher-order functions much more natural.
Anyway, this section is a good place to recall the major difference between Scheme and Common Lisp in regards to treating symbols as functions. I referred to this topic in the introduction post of this series, so I’ll get right to the code. This is the implementation of sum, in CL:
(defun cube (x)
(* x x x))
(defun sum (term a next b)
(if (> a b)
0
(+ (funcall term a)
(sum term (funcall next a) next b))))
(defun sum-integers (a b)
(sum #'identity a #'1+ b))
(defun pi-sum (a b)
(defun pi-term (x)
(/ 1.0 (* x (+ x 2))))
(defun pi-next (x)
(+ x 4))
(sum #'pi-term a #'pi-next b))
(defun integral (f a b dx)
(defun add-dx (x)
(+ x dx))
(* (sum f (+ a (/ dx 2.0)) #'add-dx b)
dx))
In short – functions live in a separate namespace from variables in CL. Therefore, we can’t just call a function by placing it as the leftmost symbol in a form (unlike Scheme). Rather, we must specify explicitly that it is a function call by using the funcall function. In addition, we can’t just pass a name of a function around like a variable, we must use the special #’ tag (which is really syntactic sugar for the function form), as the code above shows1.
Exercise 1.29
Below is the implementation of Simpson’s Rule in terms of sum.
(defun simpson-integral (f a b n)
(let ((h (float (/ (- b a) n))))
(defun simpson-term (k)
(* (funcall f (+ a (* k h)))
(cond ((or (= k 0) (= k n)) 1)
((oddp k) 4)
(t 2))))
(* (/ h 3)
(sum #'simpson-term 0 #'1+ n))))
Note that it is different from integral in the sense that the sum is invoked on the range 0..n and not a..b, because the computation of simpson-term must be aware of the k.
Also note the explicit call to float. This is because CLISP did the computation in rational numbers instead of floating point numbers, and to compare the results to integral I wanted floating point. Here is the comparison:
(print 'integral) (print (integral #'cube 0 1 0.01)) (print (integral #'cube 0 1 0.001)) (print 'simpson-integral) (print (simpson-integral #'cube 0 1 100)) (print (simpson-integral #'cube 0 1 1000)) ==> INTEGRAL 0.24998708 0.24999388 SIMPSON-INTEGRAL 0.24999997 0.2500002
Obviouly, the approximation provided by Simpson’s Rule is better – the results converges better with the same amount of iterations.
Exercise 1.30
(defun sum-iter (term a next b)
(defun iter (a result)
(if (> a b)
result
(iter (funcall next a)
(+ (funcall term a) result))))
(iter a 0))
Exercise 1.31
It is very simple to design product since it’s very similar to sum (this similarity is the central topic of this and the following two exercises).
(defun product (term a next b)
(if (> a b)
1
(* (funcall term a)
(product term (funcall next a) next b))))
And here we use product:
(defun factorial (n)
(product #'identity 1 #'1+ n))
(defun wallis-pi (n)
(defun wallis-term (k)
(let ((nom
(if (evenp k)
(+ k 2)
(+ k 1)))
(denom
(if (evenp k)
(+ k 1)
(+ k 2))))
(float (/ nom denom))))
(* 4 (product #'wallis-term 1 #'1+ n)))
The second part of the exercise asks to design an iterative process for product, which is also very similar to sum-iter:
(defun product-iter (term a next b)
(defun iter (a result)
(if (> a b)
result
(iter (funcall next a)
(* (funcall term a) result))))
(iter a 1))
Exercise 1.32
Here is the recursive definition of accumulator and sum defined in terms of it:
(defun accumulator (combiner null-value term a next b)
(if (> a b)
null-value
(funcall combiner
(funcall term a)
(accumulator combiner null-value term (funcall next a) next b))))
(defun sum (term a next b)
(accumulator #'+ 0 term a next b))
And here is the iterative version and product defined in terms of it:
(defun accumulator-iter (combiner null-value term a next b)
(defun iter (a result)
(if (> a b)
result
(iter (funcall next a)
(funcall combiner (funcall term a) result))))
(iter a null-value))
(defun product (term a next b)
(accumulator-iter #'* 1 term a next b))
Exercise 1.33
(defun filtered-accumulator (combiner null-value term a next b filter)
(cond ((> a b) null-value)
((funcall filter a)
(funcall combiner
(funcall term a)
(filtered-accumulator combiner null-value term (funcall next a) next b filter)))
; call without combining this term
(t (filtered-accumulator combiner null-value term (funcall next a) next b filter))))
(defun sum-squares-of-primes (a b)
(filtered-accumulator #'+ 0 #'square a #'1+ b #'prime?))
(defun product-of-relatively-prime (n)
(defun relatively-prime-to-n? (k)
(= (gcd k n) 1))
(filtered-accumulator #'* 1 #'identity 1 #'1+ (1- n) #'relatively-prime-to-n?))
Conclusion
I firmly believe that abstraction is one of the (if not the) most important concepts to grasp about programming. If you understand what abstractions are and how to use them, you are a better programmer. Curiously, many programmers are unaware of a whole level of abstraction – the higher-order functional abstraction. This is probably because the more popular languages (of until a few years ago) don’t allow such abstractions in any simple manner. Imagine writing filtered-accumulator in C or Pascal! Lisp, however, supports these abstractions at its very base. Moreover, the uniform syntax of Lisp makes these abstractions look very natural, which allows tutorials on Lisp to introduce them very early in the teaching. Seeing and using such powerful abstractions right from the beginning is definitely very helpful for developing good programming skills. This is probably why people say that merely learning and understanding Lisp can make you a better programmer for life.
Footnotes
1 There are several ways to do these things in Common Lisp. For example, the apply function can be used in a similar manner to funcall. Also, function names can be passed with the simple ’ quote instead of the special #’ quote. I don’t want to delve too much into the details of CL, however, unless there is a very specific need.