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 2a 3b. Give the corresponding definitions of the procedures cons, car, and cdr.
In case representing pairs as procedures wasn’t mind-boggling enough,
consider that, in a language that can manipulate procedures, we can
get by without numbers (at least insofar as nonnegative integers are
concerned) by implementing 0 and the operation of adding 1 as
This representation is known as Church numerals, after its
inventor, Alonzo Church, the logician who invented the λ calculus.
Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)).
Give a direct definition of the addition procedure + (not in
terms of repeated application of add-1).