Foray Into Clojure, Part 2: Polymorphism, Recursion, Debugging, and Sesame Cake | 日々是好日
“日々是好日” (Nichinichi kore kōnichi) means “Every day is a good day” or “Try to spend every day meaningfully”.
This blog post continues directly from the previous one, so I’ll skip the intros. Go read that one for context. Let’s just jump into it!
Table of Contents
Runtime Polymorphism
One day someone asked Master Yunmen, “What is the meaning of the teaching?”
The master said, “The answer is not finished yet.”
(ns koans.10-runtime-polymorphism
(:require [koan-engine.core :refer :all]))
(defn hello
([] "Hello World!")
([a] (str "Hello, you silly " a "."))
([a & more] (str "Hello to this group: "
(apply str
(interpose ", " (cons a more)))
"!")))
(defmulti diet (fn [x] (:eater x)))
(defmethod diet :herbivore [a] (str (:name a) " eats veggies."))
(defmethod diet :carnivore [a] (str (:name a) " eats animals."))
(defmethod diet :default [a] (str "I don't know what " (:name a) " eats."))
(meditations
"Some functions can be used in different ways - with no arguments"
(= "Hello World!" (hello))
"With one argument"
(= "Hello, you silly world." (hello "world"))
"Or with many arguments"
(= "Hello to this group: Peter, Paul, Mary!"
(hello "Peter" "Paul" "Mary"))
"Multimethods allow more complex dispatching"
(= "Bambi eats veggies."
(diet {:species "deer" :name "Bambi" :age 1 :eater :herbivore}))
"Animals have different names"
(= "Thumper eats veggies."
(diet {:species "rabbit" :name "Thumper" :age 1 :eater :herbivore}))
"Different methods are used depending on the dispatch function result"
(= "Simba eats animals."
(diet {:species "lion" :name "Simba" :age 1 :eater :carnivore}))
"You may use a default method when no others match"
(= "I don't know what Rich Hickey eats."
(diet {:name "Rich Hickey"})))
Using multi-arity functions
In the first blog post in the series
we’ve already seen multi-arity functions (in the greeting implementations).
So this is not new :)
Value-based polymorphism with defmulti
In this Koan, we see two new things: defmulti and defmethod.
(defmulti diet (fn [x] (:eater x)))
(defmethod diet :herbivore [a] (str (:name a) " eats veggies."))
(defmethod diet :carnivore [a] (str (:name a) " eats animals."))
(defmethod diet :default [a] (str "I don't know what " (:name a) " eats."))
Comparison to other languages
This is the way to implement run-time polymorphism in Clojure. Again, coming from different language means I have to compare to learn. There are two methods of implementing ploymorphism that I know: Type-based, which is like C++ inheritance, and Duck typing, which is like the source of plenty of Python bugs.
Breaking down what the code means
Let’s break down what this code means. To speak in the same terms, let’s take a
look at defmulti’s signature.
Tip: Want to see docs for something? When your cursor is on it,
, h h:
clojure.core/defmulti
[name docstring? attr-map? dispatch-fn & options]
So, defmulti is the way we define the dispatcher. If you call diet with
a value x, the dispatcher will dispatch it to the relevant method by getting
the value of out the :eater key and dispatching x to the relevant method.
This was defined by the dispatch-fn.
Now the question becomes, how do you install multifunctions (I like to think
about it like “register methods”) in the defmulti diet? How will diet know
where to dispatch to? Well, you register them
using defmethod. When you defmethod with the same name as the
multifunction, you register that method to the dispatcher. From the
documentation of defmethod:
clojure.core/defmethod
[multifn dispatch-val & fn-tail]
So, by choosing the dispatch-val we tell the multifunction where to dispatch
each x that’s passed, based on a value that’s in one of its keys.
:default is a special value for this use.
You can read more about multimethods in Clojure’s reference, since I probably can’t explain it better than the official docs.
Open to extension
Another cool thing is that this polymorphism is open to extension. What does
that mean? Let’s take a look at an example. Alice wants to extend
the diet multimethod we’ve defined in their own Clojure project. Since it’s a
different project, their code is in a different namespace. Alice wants to add
the :vegen dispatch-val. In a “normal” library let’s say in Python, the only
way to start doing it would be to inherit the Base class and impl diet. With
Clojure, Alice will only need to implement the defmethod. To do that, Alice
will require the koans.10-runtime-polymorphism :as k and simply will write:
(defmethod k/diet :vegen [a] (str (:name a) " eats without hurting anyone 💚."))
This is already cool, but the potential uses for this are awesome. For example:
how will you expose a library’s exception handling mechanism to extension and
modification? It’s hard to imagine how one might do that in other langauages,
but using multimethods one can simple allow users to override specific
exceptions.
Lazy Sequences
Tozan (Ummon’s future successor as head of the Ummon school) went to Ummon. Ummon asked him where he came from. Tozan said, “From Sato Village.”
Ummon asked: “In what temple did you remain for the summer?”
Tozan replied, “The temple of Hoji, south of the lake.”
“When did you leave there?” asked Ummon, wondering how long Tozan would continue with such factual answers.
“The twenty-fifth of August”, answered Tozan.
Ummon then said: “I should give you three blows, but today I forgive you.”
The next day Tozan bowed to Ummon and asked, “Yesterday you forgave me three blows. I do not know why you thought me wrong.” Ummon, rebuking Tozan’s spiritless responses, said: “You are good for nothing! You simply wander from one monastery to another.” Before Ummon’s words were ended, Tozan was enlightened.
(ns koans.11-lazy-sequences
(:require [koan-engine.core :refer :all]))
(meditations
"There are many ways to generate a sequence"
(= '(1 2 3 4) (range 1 5))
"The range starts at the beginning by default"
(= '(0 1 2 3 4) (range 5))
"Only take what you need when the sequence is large"
(= [0 1 2 3 4 5 6 7 8 9]
(take 10 (range 100)))
"Or limit results by dropping what you don't need"
(= [95 96 97 98 99]
(drop 95 (range 100)))
"Iteration provides an infinite lazy sequence"
(= [1 2 4 8 16 32 64 128] (take 8 (iterate (fn [x] (* x 2)) 1)))
"Repetition is key"
(= [:a :a :a :a :a :a :a :a :a :a]
(repeat 10 :a))
"Iteration can be used for repetition"
(= (repeat 100 "hello")
(take 100 (iterate identity "hello"))))
iterate is also zero-based
At first, I thought that the answer to this Koan
"Iteration provides an infinite lazy sequence"
(= __ (take 8 (iterate (fn [x] (* x 2)) 1)))
was this:
(= [2 4 8 16 32 64 128 256] (take 8 (iterate (fn [x] (* x 2)) 1)))
But that didn’t work, so I took a closer look at iterate’s documentation:
clojure.core/iterate
[f x]
Added in 1.0
Returns a lazy sequence of x, (f x), (f (f x)) etc. f must be free of
side-effects
So iterate is 0 based as well: it starts with 0 calls to f, and then moves on
to (f x), and then to (f (f x)). So here we need to start with x, so with
1, so:
(= [1 2 4 8 16 32 64 128] (take 8 (iterate (fn [x] (* x 2)) 1)))
Let’s express this in mathematical form. iterate basically composes a function
onto itself, so saying (nth (iterate f x) n) is the same as
$$ f^n(x) $$
therefore:
$$ n=0 \to f^0(x) = x | x=1 \to f^0(1) = 1 $$
Standing on the shoulders of giants - using identity
In the first blog post in this series, we
learned about the identity function. Here we use it to create an infinite lazy
sequence of the same value:
(iterate identity "hello")
Sequence Comprehensions
Once the Southern Han Emperor Gaozu summoned Master Yunmen to the capital for an audience. The Emperor asked, “What is Zen all about?”
Master Yunmen said, “Your Majesty has the question, and your servant the monk has the answer.”
The Emperor inquired, “What answer?”
The master replied, “I request Your Majesty to reflect upon the words your servant just uttered.”
(ns koans.12-sequence-comprehensions
(:require [koan-engine.core :refer :all]))
(meditations
"Sequence comprehensions can bind each element in turn to a symbol"
(= [0 1 2 3 4 5]
(for [x (range 6)]
x))
"They can easily emulate mapping"
(= '(0 1 4 9 16 25)
(map (fn [x] (* x x))
(range 6))
(for [x (range 6)]
(* x x)))
"And also filtering"
(= '(1 3 5 7 9)
(filter odd? (range 10))
(for [x (range 10) :when (odd? x)]
x))
"Combinations of these transformations is trivial"
(= '(1 9 25 49 81)
(map (fn [x] (* x x))
(filter odd? (range 10)))
(for [x (range 10) :when (odd? x)]
(* x x)))
"More complex transformations simply take multiple binding forms"
(= [[:top :left] [:top :middle] [:top :right]
[:middle :left] [:middle :middle] [:middle :right]
[:bottom :left] [:bottom :middle] [:bottom :right]]
(for [row [:top :middle :bottom]
column [:left :middle :right]]
[row column])))
:when and other predefined keyword modifiers
for in Clojure has some supported modifiers. For the docs:
Supported modifiers are: :let [binding-form expr ...],
:while test, :when test.
These keywords are parsed specifically by for, which in Clojure is a whole
DSL. There are a few of these “custom keyword” modifiers for different macros -
important to check the docs for these.
Creating Functions
A Zen student told Ummon, “Brilliancy of Buddha illuminates the whole universe.”
Before he finished the phrase, Ummon asked: “You are reciting another’s poem, are you not?”
“Yes”, answered the student.
“You are sidetracked”, said Ummon.
Afterwards another teacher, Shishin, asked his pupils: “At which point did that student go off the track?”
(ns koans.13-creating-functions
(:require [koan-engine.core :refer :all]))
(defn square [x] (* x x))
(meditations
"One may know what they seek by knowing what they do not seek"
(= [true false true] (let [not-a-symbol? (complement symbol?)]
(map not-a-symbol? [:a 'b "c"])))
"Praise and 'complement' may help you separate the wheat from the chaff"
(= [:wheat "wheat" 'wheat]
(let [not-nil? (complement nil?)]
(filter not-nil? [nil :wheat nil "wheat" nil 'wheat nil])))
"Partial functions allow procrastination"
(= 20 (let [multiply-by-5 (partial * 5)]
(multiply-by-5 4)))
"Don't forget: first things first"
(= [:a :b :c :d]
(let [ab-adder (partial concat [:a :b])]
(ab-adder [:c :d])))
"Functions can join forces as one 'composed' function"
(= 25 (let [inc-and-square (comp square inc)]
(inc-and-square 4)))
"Have a go on a double dec-er"
(= 8 (let [double-dec (comp dec dec)]
(double-dec 10)))
"Be careful about the order in which you mix your functions"
(= 99 (let [square-and-dec (comp dec square)]
(square-and-dec 10))))
The let special form
To understand the let call in this Koan, we must refer to the reference
documentation. Let’s break
this down:
"One may know what they seek by knowing what they do not seek"
(= [false true false] (let [not-a-symbol? (complement symbol?)]
(map not-a-symbol? [:a 'b "c"])))
So, using let, one can create a lexical context where the bindings inside
the “[]” are evaluated. The bindings are pairs. In this binding, we bind the
symbol not-a-symbol? to the result of the complement function call on
symbol?. Then we can call not-a-symbol? in the lexical context let
created.
Function composition with comp
This make a lot of sense, and seems very useful. Compose functions using comp f g h to get:
$$ f(g(h(x))) $$
Recursion
Once a monk asked Master Yunmen, “Will you say something that goes beyond the awakened ones and ancestral sages?”
The master said, “Sesame cake.”
(ns koans.14-recursion
(:require [koan-engine.core :refer :all]))
(defn is-even? [n]
(if (= n 0)
true
(not (is-even? (dec n)))))
(defn is-even-bigint? [n]
(loop [n n
acc true]
(if (= n 0)
acc
(recur (dec n) (not acc)))))
(defn recursive-reverse [coll]
(loop [coll coll
result (list)]
(if (empty? coll)
result
(recur (rest coll) (conj result (first coll))))))
(comment (recursive-reverse [1 2 3]);; => (3 2 1)
)
(defn factorial [n]
(if (= n 1)
1
(if (= n 2)
2
(loop [count n
accum 1]
(if (zero? count)
accum
(recur (dec count) (* accum count)))))))
(meditations
"Recursion ends with a base case"
(= true (is-even? 0))
"And starts by moving toward that base case"
(= false (is-even? 1))
"Having too many stack frames requires explicit tail calls with recur"
(= false (is-even-bigint? 100003N))
"Reversing directions is easy when you have not gone far"
(= '(1) (recursive-reverse [1]))
"Yet it becomes more difficult the more steps you take"
(= '(6 5 4 3 2) (recursive-reverse [2 3 4 5 6]))
"Simple things may appear simple."
(= 1 (factorial 1))
"They may require other simple steps."
(= 2 (factorial 2))
"Sometimes a slightly bigger step is necessary"
(= 6 (factorial 3))
"And eventually you must think harder"
(= 24 (factorial 4))
"You can even deal with very large numbers"
(< 1000000000000000000000000N (factorial 1000N))
"But what happens when the machine limits you?"
(< 1000000000000000000000000N (factorial 100003N)))
Use comment
Following a recommendation, I started using comment instead of testing in
the repl. But what does comment do?
> (doc comment)
-------------------------
clojure.core/comment
([& body])
Macro
Ignores body, yields nil
How is this useful? Well, look at the comment in the Koan body that I’ve added.
The marked part was added automatically by evaluating the comment’s body using
, e p ; -> cider-pprint-eval-to-comment. This is a good way to try out stuff
and get some “free” documentation on the way!
;; Evaluate this using , e p ; | get this output
;; ^^^^^^^^^^^^^^^^^^^^^^^^^ | ^^^^^^^^^^^^^^^
(comment (recursive-reverse [1 2 3]) ;; => (3 2 1)
)
loop?! Finally, with no for, that’s what I needed
As we’ve seen before, Clojure’s for is not a loop, but an iteration. Surely
loop is a loop, right?
loop is exactly like let, except that it establishes a recursion point at the top of the loop, with arity equal to the number of bindings. See recur.
OMG. Welp - let’s see recur:
> (doc recur)
-------------------------
recur
(recur exprs*)
Special Form
Evaluates the exprs in order, then, in parallel, rebinds
the bindings of the recursion point to the values of the exprs.
Execution then jumps back to the recursion point, a loop or fn method.
Please see http://clojure.org/special_forms#recur
OK. Following the Clojure docs link
as well provides a clearer picture. In our factorial implementation, after the
base cases, we have two exprs and two binding targets (sybmols):
(defn factorial [n]
(if (= n 1)
1
(if (= n 2)
2
(loop [count n ;; This is the first bind target
accum 1] ;; This is the second bind target
(if (zero? count)
accum
(recur (dec count) (* accum count))))))) ;; Here are the exprs
So, recur evaluates the exprs IN ORDER, and then rebinds count and accum
to the value of the revelant expression and jumps back to the loop.
In our case, count gets ---ed and accum is multiplied by count. Makes
sense! This how exactly how the factorial function is defined:
$$ n! = n \times (n-1) \times (n-2) \times . . . \times 2 \times 1 $$
Maybe this form is a clearer analogy:
$$ accum=1 | n! = \left(\left(\left(\left(\left(accum \times n\right) \times \left(n-1\right)\right) \times \left(n-2\right)\right) \times . . . \times 2\right) \times 1\right) $$
Clojure Debugging
To make sure that we understand this part, we can try to experiment with it using another tool we haven’t used yet: debugging. Clojure development is usually REPL-driven, so debugging isn’t always the tool to reach for, but it’s obviously very useful to know.
In order to debug in Spacemacs, we first write the expression we want to debug
(which, if we want, we can later use as a comment):
(println (factorial 5))
Then, with out cursor over it, , d b -> cider-debug-defun-at-point, will lead
us to the delightful:
And then to even more amazing:
What now?
We’re at the halfway point!
I really hope I’ll get back to the Koans sooner rather than later. But to quote someone really smart I know:
There’s never enough time; Thanks you for yours!
Check out the rest of my blogposts. You can browse them by subject here.