Monday, October 28, 2013

Expression Problem: Discussion

logaan was kind enough to leave some comments on twitter regarding my recent post on Refactoring in Java, Scala, and Clojure. I needed more than 140 characters so I am responding here.

Discussion

Glen replied: (Untyped) Clojure wraps the function with converters instead of wrapping a user-defined data type. Functional view of same issue?

logaan replied: My understanding is that the expression problem is linked to polymorphism. Clojure's solution is protocols. Protocols allow you to add more types to existing behaviour and more behaviour to existing types. In Scala it needs implicits.

Reply

Thank you Logaan for your insightful comments. I really appreciate you taking the time to read my article and offer constructive criticism. Forming this response was very educational for me.

Chris Houser's Solution to the Expression Problem on InfoQ was a very interesting talk and, I assume, the basis for your criticism. It turns out that there was a debate on Lambda the Ultimate about the nature of The Expression Problem in response to Chouser's presentation.

Since Clojure rejects type safety as a design goal, applying Clojure to the Expression problem seemed somewhat of a stretch to me. On the other hand, Martin Odersky's paper points out:

The term expression problem was originally coined by Phil Wadler in a post on the Java-Genericity mailing list, in which he also proposed a solution written in an extended version of Generic Java. Only later it appeared that Wadler’s solution could not be typed.

If Philip Wadler's solution to his 1998 problem was not type-safe, that made me think the door was open to applying this problem to a dynamic language like Clojure.

In terms of needing Scala's implicits to solve the Expression problem, there may be some aspect to this that I was not understanding. It was actually Odersky's paper that made me think traits were the solution to this problem. I am impressed with how well they solve it. Especially compared to all the typing Java requires when I have 8 implementing classes of an interface that needs to change!

Ultimately, the exact definition of Wadler's original problem is much less interesting to me than solving or side-stepping this general type of problem. In response to your insightful criticism, I have renamed my post, "Refactoring in 3 Languages" and provided an alternate Clojure solution below. Thank you again for taking the time to respond.

Alternate Solution

The Clojure page on protocols actually mentions the Expression Problem. But protocols look like more complication than my little example requires. I can imagine how more complicated "Expression-Like Problems" are well served by records and protocols, yet I feel that Clojure's sweetest spot involves side-stepping these issues when practical by ignoring data specification as much as possible (by leveraging maps).

Here is an alternate "solution" to my earlier post using records and protocols:

(defrecord YearMonth [year month])

(defprotocol MONTH_ADDIBLE 
  (addMonths [MONTH_ADDIBLE mos]))

(extend-type YearMonth
  MONTH_ADDIBLE
  (addMonths [ym, addedMonths]
      (let [newMonth (+ (:month ym) addedMonths)]
           (cond (> newMonth 12)
                    ;; convert to zero-based months for math
                    (let [m (- newMonth 1)]
                         ;; Carry any extra months over to the year
                         (assoc ym :year (+ (:year ym) (quot m 12)),
                                   :month (+ (rem m 12) 1)))
                 (< newMonth 1)
                    ;; Carry any extra months over to the year, but the
                    ;; first year in this case is still year-1
                    (let [y (dec (+ (:year ym) (quot newMonth 12))),
                          ;; Adjust negative month to be within one year.
                          ;; To get the positive month, subtract it from 12
                          m (+ 12 (rem newMonth 12))]
                       (assoc ym :year y :month m))
                 :else (assoc ym :month newMonth)))))
                 
;; Tests
(addMonths (YearMonth. 2013, 7) 2)
;; #user.YearMonth{:year 2013, :month 9}
(addMonths (YearMonth. 2012, 12) 1)
;; #user.YearMonth{:year 2013, :month 1}
(addMonths (YearMonth. 2013, 1) -1)
;; #user.YearMonth{:year 2012, :month 12}

;; With an additional field
(addMonths (assoc (YearMonth. 2013, 7) :otherField1 "One") 2)
;; #user.YearMonth{:year 2013, :month 9, :otherField1 "One"}
(addMonths (assoc (YearMonth. 2012, 12) :otherField1 "One") 1)
;; #user.YearMonth{:year 2013, :month 1, :otherField1 "One"}
(addMonths (assoc (YearMonth. 2013, 1) :otherField1 "One") -1)
;; #user.YearMonth{:year 2012, :month 12, :otherField1 "One"}

(defrecord YearMonth2 [yyyyMm])

(defn yearAndMonthToYm [year month] (+ (* year 100) month))

(extend-type YearMonth2
  MONTH_ADDIBLE
  (addMonths [ym, addedMonths]
      (let [year (quot (:yyyyMm ym) 100),
            newMonth (+ (rem (:yyyyMm ym) 100) addedMonths)]
           (cond (> newMonth 12)
                    ;; convert to zero-based months for math
                    (let [m (- newMonth 1)]
                         ;; Carry any extra months over to the year
                         (assoc ym :yyyyMm (yearAndMonthToYm (+ year (quot m 12)),
                                                             (+ (rem m 12) 1))))
                 (< newMonth 1)
                    ;; Carry any extra months over to the year, but the
                    ;; first year in this case is still year-1
                    (let [y (dec (+ year (quot newMonth 12))),
                          ;; Adjust negative month to be within one year.
                          ;; To get the positive month, subtract it from 12
                          m (+ 12 (rem newMonth 12))]
                       (assoc ym :yyyyMm (yearAndMonthToYm y, m)))
                 :else (assoc ym :yyyyMm (yearAndMonthToYm year, newMonth))))))

(addMonths (YearMonth2. 201307) 2)
;; #user.YearMonth2{:yyyyMm 201309}

;; With an additional field
(addMonths (assoc (YearMonth2. 201307) :otherField2 1.1) 2)
;; #user.YearMonth2{:yyyyMm 201309, :otherField2 1.1}