[ANN] riddley: code-walking without caveats

[Zach Tellman]

When I announced Proteus [1], it was rightfully pointed out that it didn't play nicely with macros which rely on &env, as well as a few forms like 'letfn' that I hadn't explicitly handled.  This flaw has been shared by pretty much every library of this sort, and since this is a problem I've half-solved two or three times already, I figured something more general and lasting was in order.

The resulting library is called Riddley [2].  For obvious reasons, I've named it after a book which is written entirely in a barely-readable pidgin dialect. While there may be lingering issues, it's good enough to replace the code-walking mechanism in Proteus, which I think makes it the best game in town right now.  Bug reports and pull requests are welcome.

Zach

[1] https://groups.google.com/forum/#!searchin/clojure/proteus/clojure/7HNNiJJTte4/iMBWn8p6tZAJ

[2] https://github.com/ztellman/riddley

[Konrad Hinsen]

--On 2 septembre 2013 13:49:01 -0700 Zach Tellman <ztel...@gmail.com>
wrote:

> The resulting library is called Riddley [2]. For obvious reasons, I've
> named it after a book which is written entirely in a barely-readable
> pidgin dialect. While there may be lingering issues, it's good enough to
> replace the code-walking mechanism in Proteus, which I think makes it the
> best game in town right now. Bug reports and pull requests are welcome.

How does this compare to mexpand-all in clojure.tools.macro?

Konrad.

[Zach Tellman]

Hey Konrad, you can maybe speak with more authority as to what tools.macro does and doesn't provide, but my reading of it is that it does expression walking to prevent bound variables from being incorrectly symbol-macroexpanded.  This seems only important in the context of symbol macros, however; if you don't use symbol macros it's functionally equivalent to clojure.walk/macroexpand-all.  

This means that it suffers from all the same issues mentioned in Riddley's readme, namely no &env and no expansion of inlined functions.  The code walking is also only used to do expansion, no generic code walking mechanism is exposed for more general transformations a la Proteus.

Hope that helps,

Zach

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to
clojure+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.
To unsubscribe from this group and all its topics, send an email to clojure+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Konrad Hinsen]

--On 3 septembre 2013 02:08:23 -0700 Zach Tellman <ztel...@gmail.com>
wrote:

> Hey Konrad, you can maybe speak with more authority as to what
> tools.macro does and doesn't provide, but my reading of it is that it
> does expression walking to prevent bound variables from being incorrectly
> symbol-macroexpanded.  This seems only important in the context of
> symbol macros, however; if you don't use symbol macros it's functionally
> equivalent to clojure.walk/macroexpand-all.  

Not quite. It expands only terms that are evaluated, using a built-in table
of special forms, and it allows local macro definitions (macrolet). But
most importantly, it tracks local bindings and expands only macros that are
not shadowed. So if you have

(defmacro foo [] ...)
(let [foo (fn [] ...)]
(foo 'bar))

the form (foo 'bar) is not expanded because its local binding is a
function. The version in clojure.walk doesn't take this into account, and
can therefore produce incorrect code, which is a major pain to debug. I
know because it happened to me, that's why I ended up writing my own macro
expander. And that's why I wonder how riddley handled this.

Konrad.

[Ben Wolfson]

On Tue, Sep 3, 2013 at 12:41 PM, Konrad Hinsen <google...@khinsen.fastmail.net> wrote:

Not quite. It expands only terms that are evaluated, using a built-in table of special forms, and it allows local macro definitions (macrolet). But most importantly, it tracks local bindings

Local binding tracking is at best inconsistent. mexpand-all produces the same incorrect result that Proteus's previous code-walker did:

user=> (require '[clojure.tools.macro :as m])
nil
user=> (defmacro aif [test then else]
  #_=>            (let [it (first (filter #(not (contains? &env %))
  #_=>                                    (cons 'it (map #(symbol (str "it-" %)) (iterate inc 1)))))]
  #_=>              `(let [~it ~test] (if ~it ~then ~else))))
#'user/aif
user=> (m/mexpand-all '(aif (get {:x {:y 3}} :x) (aif (get it :y) [it it-1] it) nil))
(let* [it (get {:x {:y 3}} :x)] (if it (let* [it (get it :y)] (if it [it it-1] it)) nil))

The inner let* should be binding it-1.

--
Ben Wolfson
"Human kind has used its intelligence to vary the flavour of drinks, which may be sweet, aromatic, fermented or spirit-based. ... Family and social life also offer numerous other occasions to consume drinks for pleasure." [Larousse, "Drink" entry]

[Zach Tellman]

I see.  This is honestly something I hadn't considered, but since Riddley actually uses the Clojure compiler internals to track locals, this would be as simple as a (when-not (contains? (riddley.compiler/locals) (first expr)) ...) guard in the macroexpansion.  As Ben points out, using the compiler this way is the only way to make sure that locals are consistent everywhere, rather than just in your own targeted use to track shadowing.

Hope that helps,

Zach

Konrad.

[Konrad Hinsen]

Zach Tellman writes:

> I see.  This is honestly something I hadn't considered, but since
> Riddley actually uses the Clojure compiler internals to track
> locals, this would be as simple as a (when-not (contains?
> (riddley.compiler/locals) (first expr)) ...) guard in the
> macroexpansion.

If you don't need complete recursive expansion, that's indeed an
approach worth exploring. For tools.macros that's not an option
because the compiler knows nothing about local macros and symbol
macros.

> As Ben points out, using the compiler this way is the only way to
> make sure that locals are consistent everywhere, rather than just
> in your own targeted use to track shadowing.

Well, either you use the compiler or you replicate what it does. For
tools.macro I had to choose the second approach. I don't claim it has
no bugs, I just claim I haven't had any bug reports ;-) (until today
at least).

Konrad

[Zach Tellman]

I'm not sure what you mean by "complete recursive expansion".  Could you expand on that?

As for replicating the behavior of the compiler, I'd assert that unless &env is precisely what it would be without ahead of time macroexpansion, the compiler's behavior isn't being replicated.  The tools.macro library emulates an aspect of its behavior, certainly, and the fact that Clojure's existed this long without anyone doing something like this indicates that maybe this isn't such a huge omission, but without there remains an uncanny valley.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+u...@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.

To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.

[Konrad Hinsen]

On Wed, Sep 4, 2013, at 09:25 AM, Zach Tellman wrote:

 

    I'm not sure what you mean by "complete recursive expansion".  Could you expand

    on that?

 

Completely ;-)

 

By complete recursive expansion I mean that you get a form that is fully reduced to

the core language, i.e. it contains no more macro applications at any level.

 

If you leave macro expansion to the compiler, it does it when it arrives at the

macro during evaluation. Then it does a plain non-recursive macroexpand and goes on

evaluating. Any macro thus has access to the unexpanded contents of its form, but

not to what it eventually expands to. For many applications that's just fine, which

is why this approach has been the default in the Lisp world for a long time.

 

    As for replicating the behavior of the compiler, I'd assert that unless &env is

    precisely what it would be without ahead of time macroexpansion, the compiler's

    behavior isn't being replicated.

 

I agree. tools.macro predates &env, which is why it is not supported. Since I have

never need &env support and nobody ever asked for it (before now), it's not there.

I don't see any reason why it couldn't be supported.

 

Konrad.

 

[Zach Tellman]

So "complete recursive expansion" is postwalk macroexpansion?  It seems like that could break anaphoric macros, and likely others.  A macro has the option of calling macroexpand-all on its own contents if it wants only special forms, but it shouldn't be forced to take only special forms.

Also, here's a sketch of how you could do symbol macros using Riddley: https://gist.github.com/ztellman/6439318.  Please let me know if I'm missing something w.r.t. how symbol macros are done in tools.macros.

Zach

--

[Ben Wolfson]

Postwalk expansion would break macros that inspect their argument forms for e.g. writing special-purpose queries, if they *also* adopt the symbols "and" and "or" for conjunction or disjunction. Korma's "where", for instance, does this; one can write

(select my-table (where (and (...) (...))))

And the "where" detects the "and".

Arguably this is wrongheaded behavior from the get-go (it can be somewhat confusing and makes it necessary to use something like clojure.core/and within "where" if you want normal clojure-land "and" semantics), but it's a style of non-anaphoric macro that relies on receiving an unexpanded form.

You received this message because you are subscribed to the Google Groups "Clojure" group.
To unsubscribe from this group and stop receiving emails from it, send an email to clojure+u...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

[Zach Tellman]

Actually, postwalk expansion (if that is in fact what you were describing) would ignore any binding forms created by the outer macro.  This means that something simple like:

(defmacro with-db [db & body]

  `(with-open [~db (create-db)]

     ~@body))

would be expanded without any knowledge of the 'db' local variable, since that would only get turned into a let form later.  Prewalk is pretty much the only way this works.

[Konrad Hinsen]

--On 4 septembre 2013 09:27:12 -0700 Zach Tellman <ztel...@gmail.com>
wrote:

> So "complete recursive expansion" is postwalk macroexpansion?  It seems
> like that could break anaphoric macros, and likely others.  A macro has
> the option of calling macroexpand-all on its own contents if it wants
> only special forms, but it shouldn't be forced to take only special forms.

Recursive macro expansion still works from outside in, so each macro gets
to see the unexpanded form. It's only after the macro has done its
transformation that the inner forms get expanded.

> Also, here's a sketch of how you could do symbol macros using
> Riddley: https://gist.github.com/ztellman/6439318.  Please let me know
> if I'm missing something w.r.t. how symbol macros are done in
> tools.macros.

It's on my reading list for tomorrow!

Konrad.

[Zach Tellman]

I guess I'm confused, then.  You contrast "complete recursive expansion" with what the compiler does, and then say it's recursive prewalk expansion, which is exactly what the compiler does.  Can you clarify the difference between what you're doing and what the compiler does?

Konrad.

--
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+unsubscribe@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
--- You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.

To unsubscribe from this group and all its topics, send an email to clojure+unsubscribe@googlegroups.com.

[Konrad Hinsen]

Zach Tellman writes:

 

 > I guess I'm confused, then.  You contrast "complete recursive

 > expansion" with what the compiler does, and then say it's recursive

 > prewalk expansion, which is exactly what the compiler does.  Can

 > you clarify the difference between what you're doing and what the

 > compiler does?

 

Here's an example:

 

   (defmacro foo [x]

     `(list ~x ~x))

 

   (defmacro bar [x]

     `[~x ~x])

 

Now let's work on the form

 

   (foo (bar 'baz))

 

Plain macroexpand returns

 

   (list (bar 'baz) (bar 'baz))

 

whereas tools.macro/mexpand-all gives

 

   (list ['baz 'baz] ['baz 'baz])

 

It does this by first calling macroexpand, so foo gets called exactly

as during Clojure compilation and returns

 

   (list (bar 'baz) (bar 'baz))

 

mexpand-all then goes through that form and expands the two subforms

(bar 'baz).

 

So mexpand-all does exactly what the compiler does, in particular it

calls the macros with exactly the same arguments. But the compiler

interleaves macro expansion with compilation, so it never gives you

access to the fully expanded but uncompiled form which is

 

   (list ['baz 'baz] ['baz 'baz])

 

Konrad

[bertschi]

Hi Zach,

you might want to look at this paper explaining how to write a correct macroexpand-all (which requires a code walker) in Common Lisp:
http://www.merl.com/publications/TR1993-017/

The compiler certainly has to do something like that, but might not do all of the macroexpansion before starting any compilation as Konrad explained. What the compiler needs to do is track the lexical environment while walking down the source forms. When a code walker wants to introduce additional bindings, such as macrolet (for local macros) or symbol-macrolet (for new symbols) it needs to be able to extend the environment accordingly. So, you either have to access the compiler internals, especially its environment handling, or track the environment yourself (as Konrad suggested).
As an aside: The problem in Common Lisp is mainly that the environment handling is not exposed in the standard, thus you cannot write a portable code walker without doing some environment handling yourself.

You might also want to look at core.async, which uses a code walker to transform go blocks into state machines. I have not (yet) checked its restrictions (someone told me, that it cannot even look into anonymous fn forms within its body!), but it is generally very hard to write a code walker that can handle all special forms (in Common Lisp I don't know any).

+10 for having a library that supports writing correct and (almost) complete code walkers

Best,

   Nils

[Stathis Sideris]

Thanks for this library Zach,

It seems that the released version is a bit behind in comparison to the generated documentation [1]. For example, walk-exprs is advertised as being able to accept a special-forms parameter, but that's not the case in the jar that leiningen retrieved when I used [riddley "0.1.0"] in my project.clj.

Thanks,

Stathis

[1] http://ideolalia.com/riddley/

[Zach Tellman]

Sorry, that documentation reflected 0.1.1-SNAPSHOT, which I've just released as 0.1.1.  Let me know if you have any other issues.

Zach

--

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+u...@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.

To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.

[Zach Tellman]

Hi Nils,

Thanks for the link, I hadn't seen that before.  Happily, what you describe is pretty much exactly what Riddley does, in this case by accessing the compiler internals.  An example of how macrolet or symbol-macrolet could be implemented using this is linked above in my response to Konrad.  This means that macros which rely on the clojure.lang.Compiler$LocalBinding (which includes [1] and [2]) will still work.  As far as I can tell, this is not the case in either tools.macro or core.async.

If you know of any ways to make the code-walking more complete, please let me know.

Zach

[1] https://github.com/ztellman/proteus/blob/master/src/proteus.clj#L60

[2] https://github.com/flatland/useful/blob/develop/src/flatland/useful/datatypes.clj#L62

--

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+u...@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.

To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.

[Zach Tellman]

Hi Konrad,

Okay, I think I was just being dense.  I thought you were talking about a different macroexpansion strategy, rather than just doing full macroexpansion without interleaved compilation.  Thanks for your patience in explaining what you meant.

I will note, though, that &env is an implicit argument to the macros, so anything which works "exactly" like the compiler needs to mimic that as well.

Zach

--

--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clo...@googlegroups.com
Note that posts from new members are moderated - please be patient with your first post.
To unsubscribe from this group, send email to

clojure+u...@googlegroups.com

For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
---
You received this message because you are subscribed to a topic in the Google Groups "Clojure" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/clojure/a68aThpvP4o/unsubscribe.

To unsubscribe from this group and all its topics, send an email to clojure+u...@googlegroups.com.

[Konrad Hinsen]

Zach Tellman writes:

> I will note, though, that &env is an implicit argument to the macros, so anything which
> works "exactly" like the compiler needs to mimic that as well.

I certainly agree, and I'll put this on the to-do list for tools.macro
(as soon as JIRA will let me in again, but that's another story). As I
said, tools.macro is older than &env, so the claims it makes were
correct at the time the code was written.

Konrad.