Macros applied to entire programs

[Mark Reid]

Hi,

I'm quite new to macros so forgive me if this is a naïve question, but
is it possible to write macros that are applied to an entire Clojure
program?

The reason I ask is that, in other threads in this group, some simple
transformations to improve efficiency of Clojure programs were
mentioned. In particular, it seems converting `(+ 1 2 3)` to `(+ 1 (+
2 3))` can speed things up. Applying such a transformation to my own
code would be a mindless pattern matching job, and thus perfect for
automation.

Any suggestions how I might write a Clojure program that takes as
input another Clojure program and outputs a third one that is
optimised but semantically equivalent to the input? Are macros the
right tool for the job in this case?

Thanks,

Mark.
--
http://mark.reid.name

[Sean Devlin]

Macros are definitely the tool to do this. Take a look here at Paul
Graham's "The Roots of Lisp". In it you'll get an idea of why eval is
so powerful, and why macros are exactly the tool for the job you're
thinking of.

http://lib.store.yahoo.net/lib/paulgraham/jmc.ps

I'll let someone else answer "how" with respect to Clojure.

Sean

[Mark Reid]

Hi,

I have read Graham's "On Lisp". That, and my background in Java and
Haskell programming were the main reasons I was drawn to Clojure.
Based on that article and others like it I had the impression that
program transformations like the one I suggested were relatively easy
in homoiconic languages like Clojure and macros seem to be the tool to
do it.

I guess what I'm really looking for now is the "how".

Mark.

[Konrad Hinsen]

On 12.05.2009, at 05:42, Mark Reid wrote:

> I'm quite new to macros so forgive me if this is a naïve question, but
> is it possible to write macros that are applied to an entire Clojure
> program?

It depends on what you call a "program". Clojure code is structured
in the form of namespaces, and inside each namespace there is a
sequence of top-level expressions that are evaluated in order.
Launching a program written in Clojure means launching a function in
a namespace, which would typicall call other functions from several
other namespaces. Some of these would typically be part your
"application", other would be in libraries or in the Clojure core.

I don't think there is any way to apply a macro to all of that
without modifying Clojure itself. I also don't think there is a good
reason to apply a macro to everything. If you find a way to speed up
basic operations in Clojure that are of general interest, you'd
better propose a patch to Clojure than write your own compiler on top
of it.

What can be done fairly easily is apply a macro to all of a
namespace. If you macro is called "optimize", you insert the line

(optimize

right below the ns form and a line

)

at the end of the namespace. But I am still not convinced that this
is a good idea, as you would still be writing a compiler on top of
Clojure. As with all optimization, I would recommend to first
identify the parts of your program that are the performance
bottleneck, and then optimize those.

> The reason I ask is that, in other threads in this group, some simple
> transformations to improve efficiency of Clojure programs were
> mentioned. In particular, it seems converting `(+ 1 2 3)` to `(+ 1 (+
> 2 3))` can speed things up.

How much do you expect to gain from this? I didn't see a discussion
on this topic before (but I don't read all messages on this group).

> Applying such a transformation to my own code would be a mindless
> pattern matching job, and thus perfect for automation.

Indeed, and macros are the right tool for that. But if you want to
make such a macro general enough that it is safe to apply to
arbitrary code, expect to spend a lot of time on writing that macro.
It is easy enough to write a macro that goes through a form,
identifies + subforms, and rewrites them. However, not every form
beginning with + is a call to clojure.core/+. It might be a call to a
function called + in another namespace (for example
clojure.contrib.generic.arithmetic/+), or it might be part of a macro
template or some other quoted expression.

For these reasons, I'd suggest to apply your optimizations only to
code that you know well enough to be sure it doesn't contain some
tricks you might not have thought about.

Konrad.

[Paul Stadig]

You could write a Clojure program that took in a Clojure program and spit out an optimized Clojure program. You could do something similar to the meta-circular evaluator, where you step through the program (which is just a data structure) recursively matching the head each time against different symbols. In your case you could match against '+ and do something special, but as Konrad mentioned there are some difficulties with that.

Another possibility would be to write a macro called my-+ or ++ or something, and use that instead. This would be a simple solution, because you wouldn't have to rewrite all of the matching for all of the different forms. The only problem would be that you'd have to change any existing code, but at least that way you'd be optimizing the parts of your code that need it and it would be clear what you are doing. You could also exclude clojure.core/+ from your namespace and write a macro called + that would then call clojure.core/+. I'm not sure if the following code works and is bug-free, but it'd be something like:

(ns test
  (:refer-clojure :exclude [+]))

(defmacro +
  ([] 0)
  ([a] `(clojure.core/+ ~a))
  ([a b] `(clojure.core/+ ~a ~b))
  ([a b & c] `(clojure.core/+ ~a (+ ~b ~@c))))

There are some "challenges" to having '+ or my-+ or ++ be a macro, it means that you would have to wrap it with a function literal before you could pass it to functions like 'map.

It is true that '+ gets inlined with two arguments, so it is faster than calling it with three or more arguments. Another possibility would be to just discipline yourself to use the two argument form instead of the three or more argument form.


Paul

[Sean Devlin]

One thing hit me as I went to bed last night about this problem:

Writing a macro to optimize an s-exp *is* writing a compiler.

The good news is that you *don't* have to write a parser. There is
some low hanging fruit here (like the + macro described above), but I
imagine there will be a lot of subtle cases that make it very
difficult do to this job. The biggest issue I see is that you could
accidently apply a macro that creates MORE work for the JVM.

So I'd recommend doing something for the easy cases, and let the JVM
do its job for everything else.

Sean

[Stuart Sierra]

On May 12, 12:17 am, Mark Reid <mark.r...@gmail.com> wrote:
> I guess what I'm really looking for now is the "how".

It's relatively easy to write a program that transforms Clojure source
code:

(loop []
(when-let [code (read *in* false nil)]
... do some transformation on code ...
(prn transformed-code)
(recur)))

But this sort of source-level transformation is rarely used in Lisp-
like languages. A more typical approach would be to write a macro or
function that overrides some core function, then use that in your own
namespace.

-Stuart Sierra

[Mark Reid]

I should clarify: I asked my original question not because I wanted to
actually write an optimiser but rather I was interested in how far the
idea of code-modifying code could be pushed in a Lisp-like language
such as Clojure. The example I gave was just the simplest thing I
could think of that demonstrated what I was imagining.

Basically, I wanted a little exercise to try to understand macro
programming better and though this would be a fun exercise. I just
didn't know where to start. Stuart's template is more or less what I
was after.

Konrad, I agree, it would make more sense to add simple optimisations
like the one for addition to Clojure itself. However, the potential
problem you mention regarding the clash of multiple definitions of `+`
doesn't seem like that big an issue since an optimising macro can just
call `resolve` against the first symbol and see if it is equal to
`clojure.core/+`. Paul's suggestion also seems to get around this
problem.

Thanks for all the responses.

Mark
--
http://mark.reid.name

[Konrad Hinsen]

On 13.05.2009, at 02:43, Mark Reid wrote:

> Konrad, I agree, it would make more sense to add simple optimisations
> like the one for addition to Clojure itself. However, the potential
> problem you mention regarding the clash of multiple definitions of `+`
> doesn't seem like that big an issue since an optimising macro can just
> call `resolve` against the first symbol and see if it is equal to
> `clojure.core/+`. Paul's suggestion also seems to get around this
> problem.

It's not a really big issue, I just wanted to illustrate with a
simple example that global code modifications requires a lot of
attention to details. As you say, checking if + resolves to
clojure.core/+ is one step in the correct procedure, but it's not
sufficient. You need to check first if + is not locally bound in a
surrounding let statement, or a surrounding function argument list.
And you must expand all surrounding macros first, because they might
transform the + into something else as well. In fact, the only
practical way to to the kind of optimization you envisage is to do a
full macro expansion first, and then walk through the code, keeping
track of let* an fn* forms.

I have done exactly that recently when writing clojure.contrib.macro-
utils, which contains a full macro expansion engine because that's
the only way to implement symbol macros and local macros. It was an
interesting exercice in macro programming.

Konrad.

[Konrad Hinsen]

On 13.05.2009, at 08:32, Konrad Hinsen wrote:

> I have done exactly that recently when writing clojure.contrib.macro-
> utils, which contains a full macro expansion engine because that's
> the only way to implement symbol macros and local macros. It was an
> interesting exercice in macro programming.

It just occurred to me that local macros are probably a very good way
for implementing the kind of optimization you have in mind:

(macrolet [(fn + [& ops] ...)]
(expr1)
(expr2)
...)

takes care of not touching occurrences of + that should be left as
is, and correctly interacts with other macros. Inside the (fn + ...),
you just have to make sure that your output forms use clojure.core/+
instead of an unqualified +, to prevent the macro from being executed
in an endless loop. Using a local macro will even make sure that +
passed as a parameter to other functions is not touched. The only
limitation is that code using clojure.core/+ explicitly is not
modified. This may well be an advantage, as it provides an escape
mechanism from optimization.

Konrad.

[Christophe Grand]

Mark Reid a écrit :

> In particular, it seems converting `(+ 1 2 3)` to `(+ 1 (+
> 2 3))` can speed things up.

Rich, would you accept a patch to make all arities inlinable for basic
math ops?

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

[Rich Hickey]

On May 13, 9:57 am, Christophe Grand <christo...@cgrand.net> wrote:
> Mark Reid a écrit :
>
> > In particular, it seems converting `(+ 1 2 3)` to `(+ 1 (+
> > 2 3))` can speed things up.
>
> Rich, would you accept a patch to make all arities inlinable for basic
> math ops?
>

What does the patch do?

Rich

[Christophe Grand]

Rich Hickey a écrit :

It would rewrite (+ 1 2 3) as (+ (+ 1 2) 3) but this implies to break
some cases, currently we have:
user=> (+ Integer/MAX_VALUE Integer/MAX_VALUE)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:0)
user=> (+ Integer/MAX_VALUE Integer/MAX_VALUE Integer/MAX_VALUE)
6442450941

with such a patch, we would have:
user=> (+ Integer/MAX_VALUE Integer/MAX_VALUE Integer/MAX_VALUE)
java.lang.ArithmeticException: integer overflow (NO_SOURCE_FILE:0)

it's a change but at least (+ a b c) and (+ (+ a b) c) would behave
similarly.

(and to be more specific this patch would certainly introduce a private
macro: def-left-associative-op)

[Christophe Grand]

Rich Hickey a écrit :

Here is the patch, it breaks tests in contrib for (-) and (/) since both
forms now throw an exception at compile-time.

[Christophe Grand]

I'm sure there's something wrong with my patch (the "eval" smell) and
the fact that I'm assoc-ing a closure in the metadat map.
I'll rework it if you agree with the idea of this patch

Christophe Grand a écrit :

[Christophe Grand]

I attached a better patch: no eval and a more standard "inline".

Christophe Grand a écrit :