Ytdyklly

I'm trying to teach myself Clojure by reading the Brave Clojure book online, and at the end of Chapter 7 there is an exercise to parse a mathematical expression written as a list in infix notation to s-expressions, following operator precedence rules.

To do this I implemented the shunting-yard algorithm in Clojure. However I am not sure if I am doing this in a functional way, as I am used to programming in languages like C++ and Python. In particular, I am uncertain whether the use of the loop operator is valid, as I'm coding this in basically the same way I would as in C++, just using recur on every loop iteration instead of mutating variables. This makes it seem a little repetitive.

Below is the code. It would be greatly appreciated someone takes a look and offers advice about how to do this in a more idiomatic functional way, or about anything else.

(def operator-precedence {'= 1, '+ 5, '- 5, '* 6, '/ 6})



(defn infix-parse

  "Converts an infix expression to s-expressions in linear time with the

  shunting-yard algorithm."

  [expr]

  (if (list? expr)

    (loop [val-stack ()

           op-stack ()

           remaining expr

           next-op false]

      (if next-op

        (let [prec (if (empty? remaining)

                     ##-Inf

                     (operator-precedence (first remaining)))

              popped (take-while #(>= (operator-precedence %) prec) op-stack)

              result (reduce

                       (fn [[a b & vals] op]

                         (cons (list op b a) vals))

                       val-stack

                       popped)]

          (if (empty? remaining)

            (first result)

            (recur result

                   (cons (first remaining)

                         (drop (count popped) op-stack))

                   (rest remaining)

                   false)))

        (recur (cons (infix-parse (first remaining)) val-stack)

               op-stack

               (rest remaining)

               true)))

    expr))



(defmacro infix

  [form]

  (infix-parse form))

(infix (1 + 3 * (4 - 5) * 10 / 2))

=> -14

(infix-parse '(1 + 3 * (4 - 5) * 10 / 2))

=> (+ 1 (/ (* (* 3 (- 4 5)) 10) 2))

First, yes, this is functional, and yes, this is how to use loop properly.

. . . using recur on every loop iteration instead of mutating variables.

This is the intent of loop. Instead of mutating a variable, you just pass the "altered data" to the next iteration via recur.

You also aren't abusing side effects by misusing def or atoms, so that's good.

My main concern with this code is how it's really just one giant function. There's no function names indicating what certain code is doing, and no comments noting the significance of any lines. Now, I'm personally a stickler for breaking code down into functions, but it's generally regard as best practice as well. As this answer notes (ignoring the mention of "imperative"):

Having a large imperative function that conveys many ideas is hard to digest and reuse.

I think the size of this function does make it hard to digest.

Just as an extreme counter example, here's the same algorithm that I wrote a year ago*. It's almost 4x longer as yours, but it's also much clearer what each bit of code is doing (and has ~10 lines dedicated to documentation). Code like

(-> equation

    (tokenize-equation)

    (infix->RPN-tokens op-attr-map)

    (tokens-to-string)) ; Should arguably be called token->string

makes it fairly clear what it's responsible for, even without taking into consideration the function name that it's in.

I'm won't try to break your code down (mostly because I burned my hand pretty bad, and typing this is hard enough), but if you take a look at my example, you may be able to find some inspiration and strike a middle ground for granularity.

Good luck

* Although my version doesn't evaluate the expression since I'm translating it into a String and in my example, the data isn't available at compile-time.