For those of you who are familiar with Clojure monads, please consider
the following problem. In the REPL log below, I define a monad parser-
m whose monadic values are parser functions (in fact, it's the same as
state-m, only with nil indicating failure) and a function rep+ that
creates a new rule that repeats a given subrule. The problem with rep+
right now is that it increases the stack for every token it consumes,
which overflows the stack with large amounts of tokens.
Is there, then, a way to rewrite rep+ so that it does not grow the
stack?
Clojure 1.1.0-new-SNAPSHOT
user=> (use 'clojure.contrib.monads)
nil
user=> (def parser-m (state-t maybe-m))
#'user/parser-m
user=> (defn lit [token]
(fn [state]
(let [[first-token & rest-tokens] state]
(if (= first-token token)
[first-token rest-tokens]
(m-zero state)))))
#'user/lit
user=> (def rule-a (lit 'a))
#'user/rule-a
user=> (rule-a '[a b c])
[a (b c)]
user=> (rule-a '[b b c])
nil
user=> (def rule-b (lit 'b))
#'user/rule-b
user=> (def rule-ab (domonad parser-m [a rule-a, b rule-b] (str a b)))
#'user/rule-ab
user=> (rule-ab '[a b c])
["ab" (c)]
user=> (rule-ab '[b b c])
nil
user=> (def rule-a-or-b (with-monad parser-m (m-plus rule-a rule-b)))
#'user/rule-a-or-b
user=> (rule-a-or-b '[b b c])
[b (b c)]
user=> (rule-a-or-b '[a b c])
[a (b c)]
user=> (defn rep+
"Creates a new rule that is the greedy repetition
of the given subrule. The repetition is one-or-more."
[rule]
(domonad parser-m
[first-token rule
rest-tokens (m-plus (rep+ rule) (m-result nil))]
(cons first-token rest-tokens)))
#'user/rep+
user=> (def one-or-more-a (rep+ rule-a))
#'user/one-or-more-a
user=> (one-or-more-a '[a b c])
[(a) (b c)]
user=> (one-or-more-a '[a a a b c])
[(a a a) (b c)]
user=> (one-or-more-a '[b c])
nil
user=> (one-or-more-a (repeat 10000 'a))
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
