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))
i))]
(check n 0)))
(defn cdr-23 [n]
(let [check (fn [nn i]
(if (zero? (mod nn 3)) (recur (quot nn 3) (inc i))
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))
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)))))