3
\$\begingroup\$

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))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

I like what you have done and much enjoyed getting to grips with it. Let's take a look.

The Clojure reader provides a syntax tree of sequences, which your algorithm traverses

  • vertically, by recursive descent and
  • horizontally by double shunting an operator stack and a value stack.

Let's look at the role of next-op - the last binding in the loop.

  • It's a boolean flag - true or false.
  • It alternates between these two values: the true handler recurs it to false and vice versa.

We can

  • transform this phase change into mutual tail recursion, then
  • flatten it by using trampoline.

Donald Knuth discusses similar transformations in Structured Programming with Goto Statements. Look at example 4 on page 11/271.

Mutual tail-recursion

We lose the next-op local, replacing it with two mutually recursive functions:

  • next-op - the true phase, expecting an operator;
  • next-val - the false phase, expecting a value.

Minor changes:

  • I've used split-with to pop the operator stack. This is just an abbreviation of what you did.
  • I test expr with seq? rather than list?, just in case we want to supply a lazy sequence or such. No need for this, as it happens.

We get

(defn infix-parse [expr]
  (if (seq? expr)
    (letfn [(next-op [val-stack op-stack remaining]
              (if next-op
                (let [prec (if (empty? remaining)
                             ##-Inf
                             (operator-precedence (first remaining)))
                      [popped left] (split-with #(>= (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)
                    (next-val result
                      (cons (first remaining) left)
                      (rest remaining))))))
            (next-val [val-stack op-stack remaining]
              (next-op (cons (infix-parse (first remaining)) val-stack)
                op-stack
                (rest remaining)))]
      (next-val () () expr))
    expr))

Flattening the Tail Recursions

The above recurses on every token. Ouch! But these are tail recursions - hardly surprising since they derive from recurs. So we can flatten them using trampoline.

The procedure is as follows:

  • Wrap each recursive call as a parmeterless function - prefixing # does that.
  • Insert trampoline into the initial call

This produces ...

(defn infix-parse [expr]
  (if (seq? expr)
    (letfn [(next-op [val-stack op-stack remaining]
              ...
                    #(next-val result
                       (cons (first remaining) left)
                       (rest remaining))))))
            (next-val [val-stack op-stack remaining]
              #(next-op (cons (infix-parse (first remaining)) val-stack)
                 op-stack
                 (rest remaining)))]
      (trampoline next-val () () expr))
    expr))

Is it worth it? I don't know. It certainly helped me understand the algorithm. However, there is a simpler approach.

Amalgamating the alternating phases

The phase alternation represents the alternation of operators and operands in any (horizontal) expression. So we can unroll the two phases of the operator-operand pair into one pass of the loop. This is easy because we are dealing with only binary operators.

Modifying your code along these lines, I came up with the following:

(defn infix-parse [expr]
  (if-not (seq? expr)
    expr
    (loop [val-stack ()
           op-stack ()
           [opd op & expr] expr]
      (let [priority (if op (operator-precedence op) ##-Inf)
            [popped-ops unpopped-ops] (split-with
                                        #(>= (operator-precedence %) priority)
                                        op-stack)
            val-stack (reduce
                        (fn [[right left & vals] op]
                          (cons (list op left right) vals))
                        (cons (infix-parse opd) val-stack)
                        popped-ops)]
        (if-not op
          (first val-stack)
          (recur val-stack (cons op unpopped-ops) expr))))))

I've changed some of the names and inverted some ifs to make the code easier to follow. I've also assumed that the expression is not allowed to be empty, and used destructuring to detect this case.

I've also rebound the same names in loop and let where the new expression takes over the role of the old - yes, it's like assignment. I like doing so. Many don't.

Finally, I rewrote your macro ...

(defmacro infix [& form]
  (infix-parse form))

... so that it accepts expressions inline:

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

Again, trivial stuff.

Appendix

Why your algorithm isn't quite the Dijkstra Shunting Yard Algorithm (SYA) you refer to.

  • You take in a Clojure form that is an ordered tree of tokens, where parentheses have disappeared into the structure of the tree. The SYA takes in a flat sequence of tokens that includes parentheses.
  • You put out a tree of Clojure operator invocations, where operator scope/arity is resolved by the tree structure (which presents as parentheses). The SYA puts out a flat postfix (reverse Polish) token stream of operator invocations without parentheses, where the scope of each operator is resolved by its fixed arity.
  • Your algorithm is explicitly recursive (in the last recur). The SYA is entirely iterative.

To show that your algorithm is properly recursive, define

(defn nest [thing depth]
  (if (pos? depth)
    (recur (list thing) (dec depth))
    thing))

... , a function that wraps its first argument in as many lists as its second argument prescribes. For example,

user=> (nest :a 6)
((((((:a))))))

Now ask infix-parse to handle a deeply parenthesised/nested expression:

user=> (do (infix-parse (nest -36 1E6)) :b)
Execution error (StackOverflowError) at infix/infix-parse (infix.clj:34).

It runs out of stack space.

\$\endgroup\$
  • \$\begingroup\$ You’re right that parentheses are handled by the compiler in this case; the core principle of the algorithm (maintaining monotonic stacks of ops and values) is the same though. My goal is to convert an infix expression to s-expressions - as the wikipedia article you linked says, shunting yard can also output ASTs, which is what I’m trying to do here. \$\endgroup\$ – Eric Zhang Apr 1 at 14:00
  • \$\begingroup\$ @EricZhang SYA proper operates in two dimensions on the syntax tree: along and down. You are doing SYA along but down you are doing recursive descent. Whether you choose to call your hybrid algorithm SYA is of little consequence. \$\endgroup\$ – Thumbnail Apr 2 at 23:14
  • \$\begingroup\$ I agree with you, I am simply trying to solve the problem being posed, not an implementation of the "proper" shunting yard algorithm which as typically stated solves a slightly different task :) \$\endgroup\$ – Eric Zhang Apr 4 at 0:05
  • \$\begingroup\$ I can now offer some constructive advice, instead of merely carping. \$\endgroup\$ – Thumbnail Apr 5 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.