Idiomatic expression simplification in Clojure

Question

Inspired by this excellent post I wanted to implement a simple expression simplifier in Clojure using the algorithm used in the post. The post gives example implementations in F#, Scala, Haskell, C++, and Julia which all appear fairly elegant.

I have come up with two different implementations (see below) but I have a nagging feeling that they are both less than idiomatic.

My question is: What would an idiomatic Clojure implementation look like?

First implementation, based primarily on protocols:

(defprotocol Expr
  (simplify1 [e])
  (simplify [e]))

(defrecord Const [n]
  Expr
  (simplify1 [this] this)
  (simplify [this] this))

(defrecord Variable [name]
  Expr
  (simplify1 [this] this)
  (simplify [this] this))

(defrecord Add [l r]
  Expr
  (simplify1 [{:keys [l r] :as expr}]
    (let [lclass (class l)
          rclass (class r)]
      (cond
        (= lclass rclass Const)
        (Const. (+ (:n l) (:n r)))
        (and (= lclass Const) (= (:n l) 0))
        r
        (and (= rclass Const) (= (:n r) 0))
        l
        :else expr)))
  (simplify [{:keys [l r]}]
    (simplify1 (Add. (simplify l) (simplify r)))))

(defrecord Mult [l r]
  Expr
  (simplify1 [{:keys [l r] :as expr}]
    (let [lclass (class l)
          rclass (class r)]
      (cond
        (= lclass rclass Const)
        (Const. (* (:n l) (:n r)))
        (and (= lclass Const) (= (:n l) 0))
        (Const. 0)
        (and (= rclass Const) (= (:n r) 0))
        (Const. 0)
        (and (= lclass Const) (= (:n l) 1))
        r
        (and (= rclass Const) (= (:n r) 1))
        l
        :else expr)))
  (simplify [{:keys [l r]}]
    (simplify1 (Mult. (simplify l) (simplify r)))))

(defmulti print-expr class)

(defmethod print-expr Const [e]
  (print-str (.value e)))

(defmethod print-expr ::expr [e]
  (print-str "The expression cannot be simplified to a constant"))

(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))]
  (-> e
      simplify
      print-expr))

Second implementation, primarily based on multimethods and more verbose than the first:

(defrecord Const [value])
(defrecord Variable [name])
(defrecord Add [l r])
(defrecord Mult [l r])

(derive Const ::expr)
(derive Variable ::expr)
(derive Add ::expr)
(derive Mult ::expr)

(defn sim-1-disp [{:keys [l r] :as e}]
  (if (some #{(class e)} [Add Mult])
      [(class e) (class l) (class r)]
      (class e)))

(defmulti simplify class)
(defmulti simplify1 sim-1-disp)
(defmulti print-expr class)

(defmethod simplify Add [{:keys [l r]}]
  (simplify1 (Add. (simplify l) (simplify r))))

(defmethod simplify Mult [{:keys [l r]}]
  (simplify1 (Mult. (simplify l) (simplify r))))

(defmethod simplify ::expr [e]
  e)

(defmethod simplify1 [Add Const Const] [{:keys [l r]}]
  (Const. (+ (:value l) (:value r))))

(defmethod simplify1 [Add Const ::expr] [{:keys [l r] :as e}]
  (if (= (:value l) 0)
    r
    e))

(defmethod simplify1 [Add ::expr Const] [{:keys [l r] :as e}]
  (if (= (:value r) 0)
    l
    e))

(defmethod simplify1 [Mult Const Const] [{:keys [l r]}]
  (Const. (* (.value l) (.value r))))

(defmethod simplify1 [Mult Const ::expr] [{:keys [l r] :as e}]
  (cond (= (:value l) 0)
        (Const. 0)
        (= (:value l) 1)
        r
        :else e))

(defmethod simplify1 [Mult ::expr Const] [{:keys [l r] :as e}]
  (cond (= (:value r) 0)
        (Const. 0)
        (= (:value r) 1)
        l
        :else e))

(defmethod simplify1 ::expr [e]
  e)

(defmethod print-expr Const [e]
  (print-str (.value e)))

(defmethod print-expr ::expr [e]
  (print-str "The expression cannot be simplified to a constant"))

(let [e (Add. (Mult. (Add. (Const. 1) (Mult. (Const. 0) (Variable. "X"))) (Const. 3)) (Const. 12))]
  (-> e
      simplify
      print-expr))

Answer 1

Not sure about being the idiomatic implementation, but I think as Guillermo Winkler mentioned core.match is a pretty natural alternative approach, especially with variants. As your linked article says, sum types are pretty neat.

(ns simplify
  (:require [clojure.core.match :refer [match]]))

(defn- simplify-1 [expr]
  (match expr
         [::add [::const 0] a]            a
         [::add a [::const 0]]            a
         [::add [::const a] [::const b]]  [::const (+ a b)]
         [::mult [::const 0] _]           [::const 0]
         [::mult _ [::const 0]]           [::const 0]
         [::mult a [::const 1]]           a
         [::mult [::const 1] a]           a
         [::mult [::const a] [::const b]] [::const (* a b)]
         _                                expr))

(defn simplify [expr]
  (match expr
         [::add a b ] (simplify-1  [::add (simplify a) (simplify b)])
         [::mult a b ] (simplify-1 [::mult (simplify a) (simplify b)])
         _                         (simplify-1 expr)))

Example:

(simplify [::add 
           [::mult 
            [::add [::const 1] [::mult  [::const 0] [::var 'x]]] 
            [::const 3]] 
           [::const 12]])
;=> [:simplify/const 15]

This lets you leverage pattern matching for terseness and have a similar elegance as some of your linked examples. There is a cost compared to your protocol/multimethod approaches though - those are sum types open to extension, including by other people's code without touching your source code. How useful that is depends on your application.

A few asides:

• You can also define simplify in terms of clojure.walk/postwalk with simplify-1 as the function argument. This is maybe a tad easier to extend since simplify no longer needs to know which expr variants are operations and can be simplified beyond calling simplify-1 on them.
• I tried to define a core.typed type for this, but my environment seems to have some issues loading that today so I can't check it.

Think this should more or less fit:

(defalias Expr
  "A variant type for algebraic expressions."
  (Rec [e]
       (U [(Value ::const) Number]
          [(Value ::add) e e]
          [(Value ::mult) e e]
          [(Value ::var) Symbol])))