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`) creates 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. 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. 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 `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 the function. `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 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.