I'm going to admit right off the bat here that I've never written a combinational parser before. I have quite a bit of experience with Clojure though, so I'll be primarily focusing on idiomatic Clojure, and proper functional practice.
I have a few main concerns with your code:
You're using
definside ofdefn! This is a very bad idea.def(and by extension,defn) creates globals that persist even after the function they're in has returned. Run your-main, then check what the value ofdigitis. You're in for a surprise. It's in scope, and has the last value that was assigned to it. From a functional perspective especially, this is bad.defcarries out side effects and is leaking the internal state of your functions. Useletinstead. Instead of writing:(def a 1) (def b 2) (println (+ a b))
Write:
(let [a 1
b 2]
(println (+ a b)))
let creates a restricted scope, and just generally looks much cleaner.
- Your brace placement is very reminiscent of imperative style curly brace placement. This is causing a lot of bloat and making your code more verbose than it needs to be.
I'm guessing you're doing this to make matching braces easier. If this is the case, don't make your life unnecessarily difficult! Lisps are quite difficult to write unassisted. If you're going to write Clojure, you should spend an afternoon getting familiar with Par-Infer. It infers parenthesis placement based on indentation, so you can write Clojure like it's Python.
I highly recommend IntelliJ with the Cursive plugin; both have free community versions. I've been using this setup for roughly 2 years now, and it's phenomenal.
Just to show the difference, this is what your many function automatically gets formatted as when I paste it into IntelliJ:
(defn many [p0]
(fn [stream]
((fn inner [stm]
((fn [res]
(if res
((fn [r1]
(if r1
(list (concat (nth res 0) (nth r1 0)) (nth r1 1))
res))
(inner (nth res 1)))
res))
(p0 stm)))
stream)))
No more needing to carefully place trailing braces to make debugging brace placement issues easier. Just let Par-Infer handle it for you.
Your variable names are bad. Names like
r1andp0give very little information, and are the kind of names I'd expect to see post-decompilation. For the sake of you and those who may read your code, more descriptive names are a must.You have what appears to be documentation as comments above the function.
defnhas a built-in ability to handle documentation:(defn alt "Returns first successful parse" [& ps] (fn [stream] (reduce #(or %1 %2) error (map #(% stream) ps))))
You use this for -main, but nowhere else.
After taking the above suggestions into consideration (except for the variable names), your code would look more like:
(ns main.core
(:gen-class))
(def error "The error message for the parser functions"
false)
(defn lit
"Parses a single charactor"
[c]
(fn [stream]
(if (= (first stream) (first (seq c)))
(list (seq c) (rest stream))
error)))
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(reduce #(or %1 %2) error (map #(% stream) ps))))
(defn seqn
"Tries to parse in series, error if any have an error"
[& ps]
(fn [stream]
(apply
(letfn [(inner ([stm p0] ; Letfn is the local equivilent of defn
(p0 stm))
([stm p0 p1]
((fn [r0]
(if r0
((fn [r1]
(if r1
(list (list (nth r0 0) (nth r1 0)) (nth r1 1))
error)
(p1 (nth r0 1))))
error)
(p0 stm))))
([stm p0 p1 & p]
(let [r0 (p0 stm)]
(if r0
((fn [r1]
(if r1
((fn [res]
(list (list (nth r0 0) (nth r1 0) (nth res 0)) (nth res 1))
(apply inner (nth r1 1) p)))
error)
(p1 (nth r0 1))))
error))))])
stream ps)))
(defn many
"Parser that parses as many times as it can, at least once though, or it is an error"
[p0]
(fn [stream]
((fn inner [stm]
((fn [res]
(if res
((fn [r1]
(if r1
(list (concat (nth res 0) (nth r1 0)) (nth r1 1))
res)
(inner (nth res 1))))
res)
(p0 stm)))
stream))))
(defn func
"Parser that applies a function to the result of another parser."
[p0 f]
(fn [stream]
((fn [res]
(list (f (nth res 0)) (nth res 1))
(p0 stream)))))
(defn num-to-int [n]
(Integer/parseInt (apply str n)))
(defn get-val [[res remains]]
res)
(defn -main
"Main function, this computes the number 1904 from the string '34*56'"
[& args]
(let [digit (alt (lit "1") (lit "2") (lit "3") (lit "4") (lit "5") (lit "6") (lit "7") (lit "8") (lit "9") (lit "0"))
number (func (many digit) num-to-int)
mul (func (seqn number (lit "*") number), (fn [[a b c]] (* a c)))]
(println (get-val (mul "34*56")))))
These were the main things. Now I'll just comment on more nitpicky things:
nil is more commonly used to represent bad data, instead of false. Unless you think you may want to change the value of error later though, I'd just write nil directly instead of labeling it as error. It's generally understood that nil represents the lack of usable data, which appears to be the intent here.
list is most commonly used when writing macros to create code in the macro. Consider just using a vector literal ([]) instead unless you really need list behavior.
Your functions are huge! I would definitely consider breaking them down. For example, I don't see why inner is defined inside of seqn. It doesn't form a closure over any local variables. From the looks of it, it's quite complicated and makes up the majority of the functionality of seqn. I'd make it it's own function, then have seqn use it. That will leave you with two, smaller, easier to test functions. Also, are you sure inner should be a giant function with multiple arities? It wouldn't be cleaner to have it with fewer arities, or even make it multiple smaller functions? Remember, when programming functionally, the function is considered the smallest unit of code. Functions should be as large as necessary, but as small as possible. If you look at my repositories, I have a ton of small, bite-sized functions that each have an extremely focused, narrow scope. This makes testing very easy, and prevents you from needing to glance at a giant wall of code making up a function trying to decipher what it's doing in it's entirety.
For num-to-int, long is the native number type that Clojure uses. You also might want to make it clearer that "n" is actually a seq. Calling the parameter n then writing (apply str n) is very confusing. I would change it to:
(defn num-to-int [n-seq]
(Long/parseLong (apply str n-seq)))
get-val is basically just first. Unless you really like how the name helps readability, I'd just use first.
(alt (lit "1") (lit "2") (lit "3") (lit "4") (lit "5") (lit "6") (lit "7") (lit "8") (lit "9") (lit "0"))
Has a ton of repetition. There's a ton of ways to fix this. I'd lean towards something like this though:
(->> "1234567890"
(map str) ; Turn each char into a string
(map lit) ; Turn each into a literal f
(apply alt)) ; Then give them to alt
Note that even though map is used twice, this only does a single iteration due to laziness! This could also be shortened using comp:
(->> "1234567890"
(map (comp lit str)) ; Turn each char into a string, then give to lit
(apply alt)) ; Then give them to alt
Although I find the former more readable.
I'm trusting that your constant return of anonymous functions is necessary for the algorithm. I've never seen so many functions being returned from other functions. If it's necessary, it's necessary, but while trying to debug a issue, I got a mess of an error like:
ArityException Wrong number of args (0) passed to: parser-review-fixed/func/fn--1421/fn--1422 clojure.lang.AFn.throwArity (AFn.java:429)
The function inside of the function inside of func threw an arity error! Good luck debugging that!
The recursive call inside of inner inside of many could/should be "optimized". Change:
(inner (nth res 1))))
to
(recur (nth res 1))))
Use of recur prevents Stack Overflows by essentially making use of Tail-Call Optimization (although, from what I understand, the inner workings are more complicated than that).
I personally love threading macros (-> and ->> mainly). I'd lean towards writing your alt function as:
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(->> ps
(map #(% stream))
(reduce #(or %1 %2) error))))
That's nice (imo), but it's not optimized. reduce actually allows for early exit using reduced! It would be more efficient (but more verbose) to write:
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(->> ps
(map #(% stream))
(reduce (fn [acc x]
(if x
(reduced x)
acc))
error))))
As soon as an accumulator for reduce becomes reduced, the reduction ends, and the reduced value is returned. This prevents the entire sequence from needing to be checked if, say, the first value is truthy.
BUT! Mr. Hicks already thought of this case, and provided the lovely some that returns the first truthy value according to a predicate. Since you don't need to do any conversion prior to testing for thrithiness, you can use identity to "forward" the value. Then alt just becomes:
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(->> ps
(map #(% stream))
(some identity)))) ; Some returns the first truthy value
#WARNING!
I have to admit, I have 0 clue what most of this code is doing, and because of the unidiomatic way that it's written, it confused the hell out of my IDE. Because of the indentation and the constant application of temporary functions, this was extraordinarily difficult to make runnable after I fixed it up. If you try to run that first "touched up" code dump I posted, you'll get an error. There's a mismatched brace somewhere in the seqn I posted, but I can't for the life of me find the issue. Use what I posted here more as a general guide instead of copying and pasting it and trying to use it.