SICP Chapter 2 through §2.2.2

All code available on GitHub. Drawings/diagrams available here.

47 days in!

Chapter 2 is about building abstractions with data. Data abstractions feature heavily in my work as a software engineer and I think I have a reasonable grasp for them in OO languages (and Go). I have no idea how it will work for Lisps though!

;; Exercise 2.5.  Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a 3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

;; 2 and 3 are prime so the prime factorization of the number will be in the form given.

(defn pair-23 [a b]
  (* (Math/pow 2 a) (Math/pow 3 b)))

(defn car-23 [n]
  (let [check (fn [nn i]
                (if (zero? (mod nn 2)) (recur (quot nn 2) (inc i))
    (check n 0)))

(defn cdr-23 [n]
  (let [check (fn [nn i]
                (if (zero? (mod nn 3)) (recur (quot nn 3) (inc i))
    (check n 0)))

(car-23 (pair-23 4 5))
(cdr-23 (pair-23 4 5))

;; Noticing the common expression used in both car-23 and cdr-23 to find the number of times a factor appears in a factorization, we can also provide a helper procedure:

(defn factor-degree [n f]
  (let [check (fn [nn i]
                (if (zero? (mod nn f)) (recur (quot nn f) (inc i))
    (check n 0)))

Exercise 2.6 was definitely the most mind-bending part of the book so far. The background here is that one form of the Church-Turing thesis asserts that any computation can be expressed in Church’s encoding. In Alonzo’s Church’s untyped lambda calculus, the only primitive data type is a function, and Church was able to encode natural numbers with functions.

;; Exercise 2.6
(defn church-zero [] (fn [f] (fn [x] x)))
(defn church-add1 [n] (fn [f]
                        (fn [x]
                          (f ((n f) x)))))