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 `def` inside of `defn`! This is a very bad idea. `def` (and by extension, `defn`) create(s) globals that persist even after the function they're in has returned! Run your `-main`, then check what the value of `digit` is. 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. `def` carries out side effects and is leaking the internal state of your functions into the global scope. Use `let` instead.
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 for you. 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. This is *huge*. Besides the odd edge case, I never need to manually add a closing brace, or worry about its placement.
I ***highly*** recommend IntelliJ with the Cursive plugin; both have free community versions. I've been using them for roughly 2 years now, and it's a phenomenal environment to write in.
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 `r1` and `p0` give 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 your functions. `defn` has 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 also 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 your intent here.
-----
`list` is most commonly used when writing macros to create code in the macro (because lisps are homoiconic). Consider just using a vector literal (`[]`) instead unless you absolutely need `list` behavior:
(list (seq c) (rest stream))
to
[(seq c) (rest stream)]
-----
Some of 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 go over 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. If you cast to `int`, it's just going to be converted to ` long` somewhere down the road, and that could *potentially* lead to a performance hit. You might also want to make it clearer that "`n`" is actually a seq. Calling the parameter `n` then writing `(apply str n)` is very confusing, since I wouldn't expect `n` to be a sequence. 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 lot 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 string 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 this:
> 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 far 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)))) ; %1 can just be written as %
That's nice (imho), 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 thruthiness though, 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 basically no 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.