I'm going to admit right off the bat here that I've never written a parser using combinator functions 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 of which 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. Also, unless you think you may want to change the value of error later, 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, the core already has a function that basically does this: some. Since you don't need to do any conversion prior to testing for thruthiness though, you can use identity to "forward" the value in place of a predicate. Then alt just becomes:
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(->> ps
(map #(% stream))
(some identity)))) ; some returns the first truthy value
I came back to this and realized it can be reduced further! You can get rid of the call to map and make the #(% stream) the predicate of some. This makes it trivial:
(defn alt
"Returns first successful parse"
[& ps]
(fn [stream]
(some #(% stream) ps)))
Regarding your recent edit clarifying what seqn is doing, these are the two options I'd choose between:
(defn sequence-parser1 [& parsers]
(fn [stream]
(reduce (fn [[res acc-stream] p]
(let [[r stream'] (p acc-stream)]
[(conj res r) stream']))
[[] stream]
parsers)))
(defn sequence-parser2 [& parsers]
(fn [stream]
(loop [[p & rest-parsers] parsers
acc-stream stream
res []]
(if p
(let [[r stream'] (p acc-stream)]
(recur rest-parsers stream' (conj res r)))
[res acc-stream]))))
Both are basically the same code; just a reduction over parsers. I tend to lean towards using loop when I have multiple accumulators though, as I find constant pairing/deconstruction in the reducing function to be messy.
If you didn't need to accumulate a stream while iterating the parsers, this could be done very succinctly using map, but alas, that wouldn't work here unfortunately.
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.
