On May 2, 10:59 pm, David Barksdale <[email protected]> wrote:
> On Dec 28 2009, 7:03 am, Konrad Hinsen <[email protected]>
> wrote:
>
>
>
> > On 27.12.2009, at 01:47, samppi wrote:
>
> > > 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?
>
> > I don't see one immediately. The problem is not really related to
> > monads, it's that your rep+ is recursive but not tail-recursive. Tail-
> > recursive monadic functions can be handled using lazy evaluation, but
> > this simple solution does not work in your case. Your rep+ needs to be
> > written in a very different way.
>
> > One idea: if you can express rep+ in terms of m-until, you can then
> > use the specialized version state-m-until that is not recursive any
> > more.
>
> > Konrad.
>
> I also found this problem with Jim Duey's none-or-more and one-or-
> more. After finding this post I took Konrad's advise and came up with
> this:
>
> (defn none-or-more2
> "Makes aparserrepeat none or more times."
> [mv]
> (state-m-until
> #(:done (meta %))
> #((fn [s]
> (if-let [x (mv s)]
> [(conj % (first x)) (second x)]
> [(with-meta % {:done true}) s])))
> #^{:done false} []))
>
> Not liking the metadata solution I hacked this up:
>
> (defn none-or-more
> "Makes aparserrepeat none or more times."
> [mv]
> (fn [s1]
> (let [[v s2] ((state-m-until
> first
> #(fn [s3]
> (if-let [x (mv s3)]
> [[false (conj (second %) (first x))] (second
> x)]
> [[true (second %)] s3]))
> [false []]) s1)]
> [(second v) s2])))
>
> I'd like to see what you guys think and if anyone can clean these up
> more.
>
I tried to define "n-times" using the pattern of none-or-more and came
to the realization that the state-m-until does not handle a parser
that fails. So here is m-until for the parser monad and my n-times
using it:
(defn parser-m-until
"An optimized implementation of m-until for the parser monad that
replaces recursion by a loop."
[p f x]
(letfn [(until [p f x s]
(if (p x)
[x s]
(when-let [xs ((f x) s)]
(recur p f (first xs) (second xs)))))]
(fn [s] (until p f x s))))
(defn n-times
"Makes a parser repeat exactly n times."
[mv n]
(fn [s]
(when-let [xs ((parser-m-until
#(>= (first %) n)
#(fn [s]
(when-let [xs (mv s)]
[[(inc (first %)) (conj (second %) (first
xs))]
(second xs)]))
[0 []]) s)]
[(second (first xs)) (second xs)])))
--
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
