From two very simple axioms it's possible to recreate the mathematical model upon which the ISO 216 paper size standard is based, i.e., the A0 - A10 papers sizes.
Computing with paper sizes is a good example of recursion which is ubiquitous in functional programming languages. A recursive function may or may not run in constant stack space and it is important to understand the difference and to be able to convert a stack consuming recursive function to a function that runs in constant space. This is where tail recursion comes into play.
It's also the case that explicit recursion often can be avoided with the use of higher order functions, which often make the program more declarative and concise. We will also investigate such programs here.
From now on I will assume that the height of all papers is longer than the width. Every time we halve a paper we halve it along the longer side. It's sometimes required to (mentally) rotate the paper in order to follow along. The following two axioms are used:
- Halving a paper does not alter the aspect ratio between it’s width and height.
- The area of an A0 paper is 1m² (= 1 000 000 mm²).
Let’s first work out the ratio between the height and the width of a paper. From (1) we get
It is now possible to calculate the exact dimensions for the width and hight of A0:
Yes, that is the fourth root of 2. Not every day you encounter that one.
From the previous section we get the width (w0) and height (h0)
values for A0 (all units are in millimeters):
(def w0 (/ 1000 (Math/sqrt (Math/sqrt 2))))
(def h0 (* w0 (Math/sqrt 2)))
(def A0 [w0 h0])First, we abstract the halving of a paper into a function. Given a paper size of [w h] half of that paper will be [h/2 w], or in Clojure terms:
(defn halve [[w h]]
[(/ h 2) w])(note the use of argument destructuring). For example
user=> (halve A0)
[594.6035575013607 840.8964152537146]
is half an A0 paper which is the size of an A1 paper.
Next, we define a recursive function A which, given a non-negative
integer argument, returns the size of that paper.
(defn A [n]
(if (zero? n)
A0
(halve (A (dec n)))))Let's try to calculate the size of an A4 paper
user=> (A 4)
[210.22410381342866 297.30177875068034]
With simple substitution it's possible to write down the sequence of steps that the algorithm executes:
(A 4)
(halve (A 3))
(halve (halve A2))
(halve (halve (halve (A 1))))
(halve (halve (halve (halve (A 0)))))
(halve (halve (halve (halve [840.8964152537146 1189.2071150027214])
(halve (halve (halve [594.6035575013607 840.8964152537146])))
(halve (halve [420.4482076268573 594.6035575013607]))
(halve [297.30177875068034 420.4482076268573])
[210.22410381342866 297.30177875068034]
What happens if we try to calculate the paper size for a very small paper? How about A1000 or A10000?
user=> (A 1000)
[2.5688850368950365E-148 3.63295205935427E-148]
user=> (A 10000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
In the last case, the function used up all available stack space and
was unable to provide an answer. Printing the stack trace (with
(.printStackTrace *e)) might provide a hint as to why this happened.
This limitation is neither Clojure nor JVM specific, it is fundamental
to recursive programming, and since recursion is common in functional
programming it is important understand its implications. The real
problem is the algorithm used. The call to halve after we recurse
forces the program to consume stack space and since we recurse n times
the stack usage is linear to the input.
The next function solves the problem
(defn A [n i size]
(if (= i n)
size
(recur n (inc i) (halve size))))In Clojure, we must use the recur special form instead of the
function name (A in this particular example) at the point of
recursion. This is not required by other functional languages. Running
on the JVM and sharing its calling convention forces Clojure to work
around some limitations of the underlying virtual machine.
Note also the extra arguments which is often necessary to make a recursive function run in constant space. This issue is easily mitigated by turning it into a helper function or, even better, using arity overloading:
(defn A
([n] (A n 0 A0))
([n i size]
(if (= i n)
size
(recur n (inc i) (halve size)))))Let's look at the execution of this version:
(A 4)
(A 4 0 A0)
(recur 4 (inc 0) (halve [840.8964152537146 1189.2071150027214]))
(recur 4 (inc 1) (halve [594.6035575013607 840.8964152537146]))
(recur 4 (inc 2) (halve [420.4482076268573 594.6035575013607]))
(recur 4 (inc 3) (halve [297.30177875068034 420.4482076268573]))
[210.22410381342866 297.30177875068034]
The size of the call stack does not grow linearly anymore. It is
required that the call to recur be in the functions tail
position which means that recur must produce the return value of the
function. Compare the previous definition of A with this one:
(defn A [n]
(if (zero? n)
A0
(halve (recur (dec n)))))Here, the call to recur provides a value to halve which produces the
final return value which means that the function halve, not recur,
is in tail position. This function definition will not pass the compiler.
Let's try the tail recursive version of A with a large input value:
user=> (A 10000)
[0.0 0.0]
The paper have been halved 10000 times which is why the size has been reduced to zero, atleast in the floating point sense.
Looking at the first excecution steps it is not difficult to notice a pattern:
(halve (halve (halve (halve (halve ... )))))
If we want to calculate A4 we successively apply halve four times to A0 or, looking at it in another way, we compose the function halve four times with itself, producing a new function, and apply that to A0:
(halve (halve (halve (halve A0))))
((comp halve halve halve halve) A0)
Using
apply,
we can rewrite the last expression as
((apply comp [halve halve halve halve]) A0)
and using repeat, we can write a function that composes halve n
times and applies it to A0:
(defn A [n]
((apply comp (repeat n halve)) A0))Let's try it on different inputs:
user=> (A 4)
[210.22410381342866 297.30177875068034]
user=> (A 10)
[26.278012976678582 37.16272234383504]
user=> (A 10000)
[0.0 0.0]
user=> (A 1000000)
[0.0 0.0]
It seems to work perfectly fine, even for large inputs.
Another approach, which is actually not uncommon, is to produce an
infinite (lazy) sequence (A0 A1 A2 ...) of answers and then, using
nth, pick out the desired answers.
(nth (A0 A1 A2 A3 ....) 4)
Such a sequence can be constructed with the function iterate. The
expression (iterate halve A0) produces the sequence
(A0
(halve A0)
(halve (halve A0))
(halve (halve (halve A0)))
...)
Putting the two together into the A function is now as simple as
(defn A [n]
(nth (iterate halve A0) n))- Rewrite the tail recursive version of
Ausingloop/recur. - Why are
applyanditeratecalled "higher order functions"? - Test the last version (the one using
iterate) ofAusing different inputs. Convince yourself that it works for large inputs. -
(bonus) Try the following instead:
(def As (iterate halve A0))and(defn A [n] (nth As n)). This (almost identical) version ofAfails for (very) large inputs. Why?