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

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

On May 11, 11:42 pm, Mark Reid <mark.r...@gmail.com> wrote:

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.

On May 12, 1:54 pm, Sean Devlin <francoisdev...@gmail.com> wrote:

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

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.

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).

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.

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

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

On May 12, 7:12 am, Paul Stadig <p...@stadig.name> wrote:

On May 12, 12:17 am, Mark Reid <mark.r...@gmail.com> wrote:

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

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

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

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.

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

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.

Mark Reid a écrit :

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)

On May 13, 9:57 am, Christophe Grand <christo...@cgrand.net> wrote:

What does the patch do?

Rich

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)

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

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.

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

patch1.patch 2K Download

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 :

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

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

Christophe Grand a écrit :

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

inline-all.patch 2K Download