Sunday, 14 June 2009
The Shunting Yard Algorithm (2)
In my previous post, I looked at the Shunting Yard algorithm and implemented a *really* bad version which required you to escape parenthesis. Not very Lispy!
The code below makes a very small change which converts nested expressions (via lists) into RPN.
This is much nicer as now, as the tests below show, you can write expressions in a more natural way.
I was thinking (as was Mark) that I could write a macro in order to simplify writing expressions. The idea would be to write something to convert infix to prefix (rather than postfix as here).
On a slight tangent, in other Lisps, you can write a reader macro which would allow you to annotate an expression with a symbol that your reader would use to convert into the appropriate form. Clojure doesn't allow reader macros (there's a discussion here [see around 19:00] as to the reasons why).
Before we write this as a macro, we'll first need an evaluator loop. This is dead simple and just involves (again) a stack. This is a very basic version that assumes all operators have arity 2.
Having written this code, what does it buy me to write it as a macro? Not much! A macro is simply a translation of some source code to another lump of source code. In this case I'm better off writing a simple function, such as
The one use of the macro that I can see would be for constant folding which I'm sure already occurs as part of the compilation process!
Programming Clojure gives a taxonomy of macros as:
None of these seem appropriate here to me, so I *think* writing it as a function is the right way to do it. I need to read On Lisp again since I think my macro understanding is a little off.
The code below makes a very small change which converts nested expressions (via lists) into RPN.
(defn shunting-yard
([expr]
(shunting-yard expr []))
([expr stack]
(if (empty? expr)
stack
(let [token (first expr)
remainder (rest expr)]
(cond
(number? token) (lazy-seq
(cons token (shunting-yard remainder stack)))
(operator? token) (if (operator? (first stack))
(let [stackfn (partial op-compare token)]
(lazy-seq
(concat (take-while stackfn stack)
(shunting-yard remainder
(cons token
(drop-while stackfn stack))))))
(shunting-yard remainder (cons token stack)))
(sequential? token) (lazy-seq
(concat (shunting-yard token) (shunting-yard remainder stack)))
:else (assert false))))))
This is much nicer as now, as the tests below show, you can write expressions in a more natural way.
(deftest test-shuntingyard
;; Basic operators defined
(is (= (pretty-print (shunting-yard [100 + 200])) '(100 200 +)))
(is (= (pretty-print (shunting-yard [100 * 200])) '(100 200 *)))
(is (= (pretty-print (shunting-yard [100 / 200])) '(100 200 /)))
(is (= (pretty-print (shunting-yard [100 - 200])) '(100 200 -)))
;; Test some precedence rules
(is (= (pretty-print (shunting-yard [100 * 200 + 300])) '(100 200 * 300 +)))
(is (= (pretty-print (shunting-yard [100 + 200 * 300])) '(100 200 300 * +)))
;; Redundant Parenthesis
(is (= (pretty-print (shunting-yard [[[[1 + 1]]]] '(1 1 +)))))
(is (= (pretty-print (shunting-yard [1 + [1]] '(1 1 +)))))
(is (= (pretty-print (shunting-yard [[1] + [1]] '(1 1 +)))))
;; Bracketing of expressions
(is (= (pretty-print (shunting-yard [[1 + 2 + 3] + 4])) '(1 2 + 3 + 4 +)))
(is (= (pretty-print (shunting-yard [[1 + 2 * 3] + 4])) '(1 2 3 * + 4 +)))
(is (= (pretty-print (shunting-yard [[4 + 5] / [7 - 8]])) '(4 5 + 7 8 - /))))
I was thinking (as was Mark) that I could write a macro in order to simplify writing expressions. The idea would be to write something to convert infix to prefix (rather than postfix as here).
On a slight tangent, in other Lisps, you can write a reader macro which would allow you to annotate an expression with a symbol that your reader would use to convert into the appropriate form. Clojure doesn't allow reader macros (there's a discussion here [see around 19:00] as to the reasons why).
Before we write this as a macro, we'll first need an evaluator loop. This is dead simple and just involves (again) a stack. This is a very basic version that assumes all operators have arity 2.
(defn rpn-evaluator
([expr]
(rpn-evaluator expr []))
([expr stack]
(if (empty? expr)
(if (= 1 (count stack))
(first stack)
(assert false)) ;; unbalanced
(let [f (first expr)]
(cond
(number? f) (recur (rest expr) (cons f stack))
;; Should look up arity of operator!
(operator? f) (recur (rest expr)
(cons
(f (second stack) (first stack))
(drop 2 stack))))))))
Having written this code, what does it buy me to write it as a macro? Not much! A macro is simply a translation of some source code to another lump of source code. In this case I'm better off writing a simple function, such as
(def infix (comp rpn-evaluator shunting-yard)) to get the job done. The main point is that the macro doesn't have access to the values in the expression (unless they are constant). If the code was (infix [a + b]) then the macro can not evaluation a and b because the values will not be known at macro expansion time.The one use of the macro that I can see would be for constant folding which I'm sure already occurs as part of the compilation process!
Programming Clojure gives a taxonomy of macros as:
- Conditional Evaluation
- Defining vars
- Java interop
- Postponing evaluation
- Wrapping evaluation
- Avoiding a lambda
None of these seem appropriate here to me, so I *think* writing it as a function is the right way to do it. I need to read On Lisp again since I think my macro understanding is a little off.
Monday, 2 February 2009
Clojure Macros
Macros are one of the defining features of Lisp languages. A macro operates prior to compilation, allowing you to shape the code as you wish. Since Lisp code is homoiconic the macro language is the language.
Languages like C/C++ have macros, but they are in no way the same. You have a very limited language and you don't get the fine grained access to the code that you do with Lisp (since the code is just itself a Lisp data structure).
Pl Patterns tries to describe a taxonomy of macro use. One of the examples is debug printing with an example from the Arc language. Converted to Clojure this looks like this:
So now when I'm trying to debug code there's no more repetition of print x, return x I can just edit my function definition by adding dbg-prn (without the normal hardship of wrapping extra brackets around).
You can use
Languages like C/C++ have macros, but they are in no way the same. You have a very limited language and you don't get the fine grained access to the code that you do with Lisp (since the code is just itself a Lisp data structure).
Pl Patterns tries to describe a taxonomy of macro use. One of the examples is debug printing with an example from the Arc language. Converted to Clojure this looks like this:
(defmacro dbg-prn
"Debugging form that prints out results"
[& more]
`(let [start# ~more]
(print '~more "==>" start# "\n")
start#))
defmacro defines a new macro with similar structure to defn The ` is used to create a template expression, where we can evaluate certain items within the expression by using macro characters (#,~,`,list-frag?). In this example we used start# to create a uniquely named value for the let expression and ~more to evaluate the parameters.So now when I'm trying to debug code there's no more repetition of print x, return x I can just edit my function definition by adding dbg-prn (without the normal hardship of wrapping extra brackets around).
user> (dbg-prn + 1 2 3 4 5)
(+ 1 2 3 4 5) ==> 15 ;; printed to std-out
15
user> (dbg-prn + (* 2 3) (* 4 5))
(+ (* 2 3) (* 4 5)) ==> 26
26
You can use
macroexpand-1 to expand out macros to see what they actually do:
user> (macroexpand-1 '(dbg-prn + 1 1))
(clojure.core/let [start__2150__auto__ (+ 1 1)]
(clojure.core/print (quote (+ 1 1)) "==>" start__2150__auto__ "\n")
start__2150__auto__)
Subscribe to Posts [Atom]
