Newbie: Trying to defer evaluation of unbound variable arguments until needed with macros

[samppi]

I tried asking about this yesterday, but it seems like I expressed my
problem poorly. Anyways, here's another shot. :)

I have a little parser library. With its metafunctions, one can create
rules that accept tokens and spit out a result or nil if the tokens it
receives are invalid.
For instance, literal creates a basic literal rule that matches only a
token coll that starts with a certain literal token.
conc takes many rule functions and creates a new rule function that
slurps up the results of its subrules in order; if any of its subrules
fail, it fails too.
alt takes many rules and creates a new rule that tries each of its
subrules; it returns the results of the first one that succeeds.

This pattern has been going great for what I need for the past month,
until I needed to create a parser for a language containing rules that
referred to each other. Specifically, a language where a "value" can
be 0, 1, or an "array"—and "arrays" can contain two values.

Whenever I've tried to do this, I've always encountered unbound
variable errors for the value variable. So therefore, I need a way to
defer evaluation of conc and alt's arguments so that their arguments
are not called until needed.

I want to make the code below possible with as little API change as
possible, and the only way I can think of is by changing conc and alt
to macros. I'm not good with macros, so I have little idea how to do
this as elegantly as possible. Here's the code below:

(defn conc [& subrules]
(fn [tokens]
(loop [subrule-queue (seq subrules), remaining-tokens (seq
tokens), products []]
(if (nil? subrule-queue)
[products remaining-tokens]
(let [[subrule-products subrule-remainder :as subrule-result]
((first subrule-queue) remaining-tokens)]
(when-not (nil? subrule-result)
(recur (rest subrule-queue) subrule-remainder
(conj products subrule-products))))))))

(defn alt [& subrules]
(fn [tokens]
(some #(% tokens) subrules)))

(defn literal [literal-token]
(fn [tokens]
(let [first-token (first tokens), remainder (rest tokens)]
(when (= first-token literal-token)
[first-token remainder]))))

; Here's the language rules below, defined in terms of literal, conc,
and alt.

(def on (literal \1))
(def off (literal \0))
(def bit (alt on off))

; (bit (seq "starst")) -> (bit (seq "1, 0")) -> [\1 (\, \space \0)]

(def array-start (literal \[))
(def array-end (literal \]))
(def array-sep (literal \,))

; (array-start (seq "[1, 0]")) -> [\[ (\1 \, \0 \])]

(declare value)

(def array (conc array-start value array-sep value array-end))

(def value (alt array bit))

; (array (seq "0")) -> nil
; (bit (seq "0")) -> [\0 nil]
; (value (seq "0")) -> [\0 nil]

; (array (seq "[0,0]")) -> [[\[ \0 \, \0 \]] nil]
; (bit (seq "[0,0]")) -> nil
; (value (seq "[0,0]")) -> [[\[ \0 \, \0 \]] nil]

; (array (seq "[0,[1,0]]")) -> [[\[ \0 \, [\[ \q \, \0 \]] \]] nil]
; (bit (seq "[0,[1,0]]")) -> nil
; (value (seq "[0,[1,0]]")) -> [[\[ \0 \, [\[ \q \, \0 \]] \]] nil]

[Christophe Grand]

hello,

samppi a écrit :

> I tried asking about this yesterday, but it seems like I expressed my
> problem poorly. Anyways, here's another shot. :)
>

> (declare value)
>
> (def array (conc array-start value array-sep value array-end))
>
> (def value (alt array bit))
>

You can get your code to work by writing:

(declare value)
(def array (conc array-start #'value array-sep #'value array-end))

(def value (alt array bit))

#'value introduces an indirection by returning the var and not the
functions (and a var proxies calls to its current value) but this
indirection is mutable.

You can also try to use delays:

(defn conc [& subrules]
(fn [tokens]

(loop [subrule-queue (map force subrules), remaining-tokens (seq
tokens), products []] ; force (potentially) delayed rules

(if (nil? subrule-queue)
[products remaining-tokens]
(let [[subrule-products subrule-remainder :as subrule-result]
((first subrule-queue) remaining-tokens)]
(when-not (nil? subrule-result)
(recur (rest subrule-queue) subrule-remainder
(conj products subrule-products))))))))

(defn alt [& subrules]
(fn [tokens]

(some #((force %) tokens) subrules))) ; added force

Here a subrule is either a function or a delay on a function:

(declare value)
(def array (delay (conc array-start value array-sep value array-end)))

(def value (alt array bit))

samppi=> (value (seq "[0,0]"))
[[\[ \0 \, \0 \]] nil]
samppi=> (array (seq "[0,0]"))
java.lang.ClassCastException: clojure.lang.Delay cannot be cast to
clojure.lang.IFn (NO_SOURCE_FILE:0)
samppi=> ((force array) (seq "[0,0]"))
[[\[ \0 \, \0 \]] nil]

You may have to write a "call-rule" helper function to force the rule
before calling it.

But, without resorting to macros, You can also do:
(defn conc [tokens & subrules]

(loop [subrule-queue (seq subrules), remaining-tokens (seq tokens),
products []]
(if (nil? subrule-queue)
[products remaining-tokens]
(let [[subrule-products subrule-remainder :as subrule-result]
((first subrule-queue) remaining-tokens)]
(when-not (nil? subrule-result)
(recur (rest subrule-queue) subrule-remainder
(conj products subrule-products)))))))

(defn alt [tokens & subrules]
(some #(% tokens) subrules))

(declare value)
(defn array [tokens]
(conc tokens array-start value array-sep value array-end))
(defn value [tokens]
(alt tokens array bit))

(But really it's what a macro should produce :-()

Hope this help.

Christophe

--
Professional: http://cgrand.net/ (fr)
On Clojure: http://clj-me.blogspot.com/ (en)

[Christophe Grand]

Christophe Grand a écrit :

> (def array (delay (conc array-start value array-sep value array-end)))
>

or:
(def array (conc array-start (delay value) array-sep (delay value)
array-end))

and you don't need the call-rule helper.

[samppi]

Thanks for the reply. I've tried delays, but it seemed to make my
functions much slower. I think I'm going to go with var-quoting—it
seems to be the least intrusive option, and it definitely works. My
nightmare is finally over. :)

I wonder if there's a way to make a macro make even this unneeded for
the end-user, though.

[Christophe Grand]

samppi a écrit :

> Thanks for the reply. I've tried delays, but it seemed to make my
> functions much slower. I think I'm going to go with var-quoting—it
> seems to be the least intrusive option, and it definitely works. My
> nightmare is finally over. :)
>
> I wonder if there's a way to make a macro make even this unneeded for
> the end-user, though.
>

Yup, elaborating on my third option:

(defn conc* [tokens & subrules]

(loop [subrule-queue (seq subrules), remaining-tokens (seq tokens),
products []]
(if (nil? subrule-queue)
[products remaining-tokens]
(let [[subrule-products subrule-remainder :as subrule-result]
((first subrule-queue) remaining-tokens)]
(when-not (nil? subrule-result)
(recur (rest subrule-queue) subrule-remainder
(conj products subrule-products)))))))

(defn alt* [tokens & subrules]
(some #(% tokens) subrules))

(defmacro conc [& subrules]
`(fn [tokens#]
(conc* tokens# ~@subrules)))

(defmacro alt [& subrules]
`(fn [tokens#]
(alt* tokens# ~@subrules)))

(declare value)
(def array (conc array-start value array-sep value array-end))
(def value (alt array bit))

Christophe

[samppi]

Perfect. This is exactly what I need. Thank you. :)

I wonder, is it customary to append an * to the names of functions
that do the grunt work of corresponding macros?