Wednesday, January 11, 2012

Where my Clojure plays with protocols, multimethods and the SICP

Hello again.

I wanted to share today the implementation of one of my exploration of the SICP book, and get your feedback on the solution I came with. 
While reading the book, I take the time to challenge both the exercises and code samples in Scheme - although I do regret not knowing it very well - and in Clojure. Somehow trying to reproduce each line of code in both languages can explain why it takes so much time :). 

Part two of the bookis dedicated to the exploration of data abstraction and more specifically, section 2.4 leads us slowly to a data directed programming example. Starting from the canonical example of operations on complex numbers Abelson and Sussman, creates a layered complex-arithmetic system, starting at the bottom from primitive list structures, implementing complex numbers,  up to program functions that use selector and constructor methods to manipulate complex numbers. 
The top higher order operations are not supposed to be aware of the lower details of the implementation as we should use as many representations of complex numbers as we would like to, in the bottom layer. 

Complex numbers can be represented by pairs describing rectangular or polar coordinate. Each of these representation suits more to specific operations. Adding two complex numbers is easier using a rectangular representation, while polar representation seems more adapted to multiplication for example. At any step we should be able to create new complex number instances from polar or rectangular data, which we can express as:

(make-from-real-imag 1 1)
(make-from-mag-ang 1 1)
  • In the first line we create a complex number for rectangular coordinates.The idoms real and imag respectively stand for real (x) and imaginay (y) components
  • In line two we create a complex number for polar coordinates. mag and ang respectively stand for magnitude(r) and angle (theta) components
At any step we should be able to select (x,y) components in rectangular representation and (r, theta) components in polar representation. What we wish to express is something like the following:

(real-part z1)
(imag-part z1)
(magnitude z1)
(angle z1)

All these constructors n' selectors should totally be unaware of the underlying representations.

But in addition, to conform to the SICP state of mind, the previous make-from-real-imag and make-from-mag-ang constructors should be adapted in order to choose the most suitable implementation. There, serious things begin. 

In order to both explore SICP book while playing with Clojure idioms, I voluntarily chose to use protocols. In a certain way, like Abelson and Sussman (see section 2.4.1), I do not want my higher order operations to depend on specific implementations because there can be many of them, but I want my implementations to be contracted by my higher order module operations. 
What I am expecting looks like a basic Inversion Of Control (IOC is a much higher concept than dependency injection, so check you do not confuse both ideas). Quoting Michael Fogus and Chris Houser's Joy Of Clojure: "protocols are set of function signatures, each with at least one parameter, that are given a collective name. 
To digg a little deeper into protocols, check also Stuart Halloway and Aaron Bedra's  book Programming Clojure and Stuart Halloway presentation over here

To be perfectly honest I am not at ease with protocols as they do remind me to much of OOP in a Functional Programming context. That is debatable I think. Both sets of constructors and selectors functions are perfect candidates for protocols.

(ns sicp.complex)

(defprotocol ComplexSelector
  (magnitude [this])
  (angle [this])
  (real-part [this])
  (imag-part [this]))

(defprotocol ComplexConstructor
  (make-from-real-imag-constructor [self x y])
  (make-from-mag-ang-constructor [self r t]))

Then we can provide a full implementation for rectangular coordinates:

(ns sicp.complex-rectangular
  (:use sicp.core)
  (:use sicp.complex))

(defrecord Rectangular [x y]
  ComplexSelector
  (real-part [z] (:x z))
  (imag-part [z] (:y z))
  (magnitude [z] (Math/sqrt (+ (square (real-part z)) (square (imag-part z)))))
  (angle [z] (Math/atan2 (imag-part z) (imag-part z))))

(defn rectangular-complex[]
  (reify ComplexConstructor
    (make-from-real-imag-constructor [self x y] (->Rectangular x y))

    (make-from-mag-ang-constructor [self r t]
      (->Rectangular (* r (Math/cos t)) (* r (Math/sin t))))))

challenged versus the following tests:

(ns sicp.test.complex-rectangular-spec
  (:use [sicp complex complex-rectangular])
  (:use clojure.test))

(deftest complex-rectangular-should-bind-magnitude
  (is (= 5.0 (magnitude (->Rectangular 3 4)))))

(deftest complex-rectangular-should-bind-angle
  (is (= (/ Math/PI 4) (angle (->Rectangular 1 1)))))

(deftest complex-rectangular-should-bind-real-part
  (is (= 1 (real-part (->Rectangular 1 2)))))

(deftest complex-rectangular-should-bind-real-part
  (is (= 2 (imag-part (->Rectangular 1 2)))))

and for polar coordinates:

(ns sicp.complex-polar
  (:use sicp.core)
  (:use sicp.complex))

(defrecord Polar [radius theta]
  ComplexSelector
  (magnitude [z] (:radius z))
  (angle [z] (:theta z))
  (real-part [z]
    (* (magnitude z) (Math/cos (angle z))))
  (imag-part [z]
    (* (magnitude z) (Math/sin (angle z)))))

(defn polar-complex []
  (reify ComplexConstructor
    (make-from-real-imag-constructor [self x y]
      (->Polar (Math/sqrt (+ (square x) (square y))) (Math/atan2 y x)))

    (make-from-mag-ang-constructor [self r t] (->Polar r t))))


challenged versus the following tests:

(ns sicp.test.complex-polar-spec
  (:use [sicp complex complex-polar])
  (:use clojure.test))

(deftest complex-polar-should-bind-magnitude
  (is (= 1 (magnitude (->Polar 1 2)))))

(deftest complex-polar-should-bind-angle
  (is (= 2 (angle (->Polar 1 2)))))

(deftest complex-polar-should-bind-real-part
  (is (= 1 (real-part (->Polar 1 0))))
  (is (= 0 (imag-part (->Polar 1 0)))))

(deftest complex-polar-should-bind-real-part
  (is (< 0.0001 (Math/abs  (- 1.0 (imag-part (->Polar 1 Math/PI))))))
  (is (< 0.0001 (Math/abs  (real-part (->Polar 1 Math/PI))))))

As an example I used on each implementation the reify macro so to create anonymous instances of the ComplexConstructor protocol. You get access to them by closure, not by declaration. 
All this is nice and good and tests keep green. The upcoming logical step leads us to the definition of the higher order functions for dividing, adding, multiplying etc. 
There raises a small difficulty. If I really want to build an expressions like:

defn add-complex [z1 z2]
  (make-from-real-imag (+ (real-part z1) (real-part z2))
    (+ (imag-part z1) (imag-part z2))))

(defn mul-complex [z1 z2]
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
    (+ (angle z1) (angle z2))))


that would make use of the make-from-real-imag and the make-from-mag-ang functions , I would like to be able to choose a suitable data representation on each .

Wait a minute, I wanted to invert the control, so naturally at the time of defining both the functions, in the same module as the protocols, I have no idea about which representation could be used. In order to get out of this trap enter multi-methods. The trick I used is not - I think - so different from Abelson and Sussman data directed programming
Their proposal aims to update or get data in a two dimension table, one axis being the "type" of the representation and the other axis being a symbol defining the operation expected. 
So each table cell hosts a reference towards the function, matching both a type and its operation. Implementing the protocols provides me with a dispatch on type. All I need is to identify my functions. Each function can be a multi-method declaration in the same module as the complex numbers protocols definition:

(defmulti make-from-real-imag (fn [x y] :real-imag-constructor))
(defmulti make-from-mag-ang (fn [r theta] :mag-ang-constructor))

defn add-complex [z1 z2]
  (make-from-real-imag (+ (real-part z1) (real-part z2))
    (+ (imag-part z1) (imag-part z2))))

(defn mul-complex [z1 z2]
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
    (+ (angle z1) (angle z2))))


I provided an elementary dispatching function using a returned symbol as selecting value. 

It is up to the implementing module that will gather both the complex module sicp.complex and its implementations to attach the corresponding defmethod definitions. 
Here is the full complex module:

(ns sicp.complex)

(defprotocol ComplexSelector
  (magnitude [this])
  (angle [this])
  (real-part [this])
  (imag-part [this]))

(defprotocol ComplexConstructor
  (make-from-real-imag-constructor [self x y])
  (make-from-mag-ang-constructor [self r t]))

(defmulti make-from-real-imag (fn [x y] :real-imag-constructor))
(defmulti make-from-mag-ang (fn [r theta] :mag-ang-constructor))

(defn add-complex [z1 z2]
  (make-from-real-imag (+ (real-part z1) (real-part z2))
    (+ (imag-part z1) (imag-part z2))))

(defn sub-complex [z1 z2]
  (make-from-real-imag (- (real-part z1) (real-part z2))
    (- (imag-part z1) (imag-part z2))))

(defn mul-complex [z1 z2]
  (make-from-mag-ang (* (magnitude z1) (magnitude z2))
    (+ (angle z1) (angle z2))))

(defn div-complex [z1 z2]
  (make-from-mag-ang (/ (magnitude z1) (magnitude z2))
    (- (angle z1) (angle z2))))

The best place to simulate a container hosting the complex module and matching representations, being a test module, I implemented the following:

(ns sicp.test.complex-spec
  (:use [sicp core complex complex-rectangular complex-polar])
  (:use clojure.test))


(def rectangular-datum (rectangular-complex))
(def polar-datum (polar-complex))

(defmethod make-from-real-imag :real-imag-constructor [x y]
  (make-from-real-imag-constructor rectangular-datum x y))

(defmethod make-from-mag-ang :mag-ang-constructor [r theta]
  (make-from-mag-ang-constructor polar-datum r theta))


(deftest make-from-real-imag-with-dispatch-should-create-rectangular-coordinate
  (is (= (->Rectangular 1 1) (make-from-real-imag 1 1))))

(deftest make-from-mag-ang-with-dispatch-should-create-rectangular-coordinate
  (is (= (->Polar 1 1) (make-from-mag-ang 1 1))))

(deftest add-complex-should-produce-rectangular-as-sum-of-real-imag
  (is (=  (->Rectangular 3 3)
        (add-complex
          (make-from-real-imag 1 1)
          (make-from-real-imag 2 2)))))

(deftest sub-complex-should-produce-rectangular-as-sum-of-real-imag
  (is (=  (->Rectangular 2 2)
        (sub-complex
          (make-from-real-imag 3 3)
          (make-from-real-imag 1 1)))))

(deftest mul-complex-should-produce-rectangular-as-sum-of-real-imag
  (is (=  (->Polar 6 0.9)
        (mul-complex
          (make-from-mag-ang 2 0.5)
          (make-from-mag-ang 3 0.4)))))

(deftest div-complex-should-produce-rectangular-as-sum-of-real-imag
  (is (=  (->Polar 3 0.4)
        (div-complex
          (make-from-mag-ang 6 0.9)
          (make-from-mag-ang 2 0.5)))))


where in white color, rectangular-datum and polar-datum reference instances of the ComplexConstructor protocol, each of one being respectively invoked thruough the def-methods make-from-real-imag and make-from-mag-ang
The dispatch functions used in the sicp.complex module being very simple our binding remains too very simple. We could maybe try to experiment on  and make evolve the dispatching function to extend the power and flexibility of the binding in the sicp.test.complex-spec module.

Tests green. 

So we have been able to define protocols, then we used elements from that protocols from higher order function and multi-methods, imposing our control to upcoming implementations, and finally we have been able to bind our higher order functions to the expected implementations. No that bad for a simple morning. Do not hesitate to come back with comments. 

 Be seeing you !!! :)

0 comments:

Post a Comment