I'd like to write a macro called OPTIMIZE for another dialect of lisp
(not common lisp), but i think the
question makes sense here so i'll pose the question using CL examples.
I'd like the macro "somehow" have a set of simplification rules that
it can apply to
its given code body. The rules hopefully are extensible in some way.
I think such a macro is ultimately equivalent to a compiler, but
perhaps there
are some easy optimizations which can be made that will make code
faster
without having to implement a full compiler. Maybe I'm wrong :-(
Does anyone have experience with such a thing. Are there resources
where i can
find useful code tranformations which are easy to implement?
Examples might be.
1. If a variable is declared in a LET to some initial constant, and it
is never modified
but used several times, then replace the usages with the constant.
(let ((a 100) (b 200))
(+ a (foo b)))
==> (+ 100 (foo 200))
2. If a variable is declared in a LET to some inital value returned
from an expression,
and then only used once, then there are cases when eliminating the
variable makes
sense and other times when it does not.
(let ((a (bar)))
...
(+ a (foo)))
==> (+ (prog1 (bar) ...) (foo))
jimka <·····@rdrop.com> writes:
> I'd like to write a macro called OPTIMIZE for another dialect of
> lisp (not common lisp), but i think the question makes sense here so
> i'll pose the question using CL examples.
>
> I'd like the macro "somehow" have a set of simplification rules that
> it can apply to its given code body. The rules hopefully are
> extensible in some way.
All such rules will be language specific, since they rely for their
correctness on the ability to know particular truths about the language
that guarantee the correctness of the rule.
As a trivial example, there are lisps without assignment, and so in
those lisps, any variable access can be freely moved around within the
scope of its binding because you know it refers to the same value in
all cases. Other Lisps, with side-effects, require flow analysis.
Other optimizations may depend critically on whether there are nuances
of how operators work together, and which an be substituted for one another.
That may depend on whether consistent sets of overloads/genericity apply.
> I think such a macro is ultimately equivalent to a compiler, but
> perhaps there are some easy optimizations which can be made that
> will make code faster without having to implement a full compiler.
> Maybe I'm wrong :-(
You're probably both wrong in thinking this can be easily specified portably
among languages AND in thinking that changing things to something you think
is simpler will improve code.
Compilers often make assumptions you don't expect. For example, you might
think you should macroexpand the code first, because then your rewrite rules
can work on low-level details. But some compilers can't recognize in all
cases the idioms of high-level constructs, and so they only compile them well
when they are not macroexpanded and when the unmacroexpanded form gives them
the right cue. This is why CL allows compilers to implement some macros as
special forms, as long as it also provides a macroexpander for code that
expects to find one.
I don't use the clisp implementation of Lisp commonly, although it's certainly
a fun and interesting implementation, but its byte-code properties are a
perfect example of another pitfall: In most implementations, turning a
function call to a high-level operation into a bunch of low-level aref-style
operations with highly specific types would speed things up. But in clisp
it will probably slow things down is my recollection. That's kind of cool
in a strange way, because it rewards people writing stuff in a straightforward
way without lots of micromanagement of the low-level details, but on the other
hand it means if you need to tweak speed by expanding things, it's hard.
But my point isn't that clisp is right or wrong--it's that vendors have the
choice to decide what's important to them, and they attract audiences that
like the set of choices they make.
Also, anything that changes the shape of any expression, in general, means
you're giving up some shape A for shape B. Since most compilers don't use
general-purpose, combinatoric algebra to assure that any shape A that is
transformable by any means to shape B is optimized, the result is that you're
simply gambling that the compiler is looking for shape B rather than shape A.
Sometimes this is a good gamble, but you can't easily know all of the cases
where that happens, and without being intimately familiar with each compiler
you can't be sure to win. Also, even if you can be intimately familiar,
you are making your code fragile and unportable.
> Does anyone have experience with such a thing. Are there resources
> where i can find useful code tranformations which are easy to
> implement?
I don't know that you'll find anything, but if you do, I would be
quite wary of anything you find that seems superficially the right
thing unless you plan to seriously doubel-check the applicability of
each transformation.
It's worth noting that there is meta-information of this kind that people
have that is generally applicable, so the problem must be something that
ultimately will be addressable by computer science. But it's hard to
carefully quantify the total knowledge that programmers bring to bear when
doing such analysis, and it's likely that there are complicated things they
have as special pre- and post-conditions that they don't always think to
write down. The problem of meta-annotating the rules as to applicability
and variability seems to me non-trivial.
> Examples might be.
> 1. If a variable is declared in a LET to some initial constant, and it
> is never modified
> but used several times, then replace the usages with the constant.
You'd be better off starting with a representation of a language that
thoroughly understands programs in both languages and then uses rules
like this directly, rather than in some rule form.
The key point is that "initial", "constant", "modified", "used several
times", "replace", and "usage" are terms that mean different things in
each language. And yet, it may be possible to make suitably robust meanings
of these terms so that you could say this was a rule. It's just that it
wouldn't apply to many languages because pattern-matching on the meanings
of all the terms and making sure that the language even had all of these
concepts in the way that made the rule true might be hard.
And if it was there, it might be that the same visual program in one language
would simplify but not in another, since it might be that although the rule
was true, setq in one language could expand macros [as with CL's symbol
macros, which can expand into macro calls, which can turn into SETF] while
in another language it cannot, so in one language you might get a structure
assignment due to SETF and in another only a change in variable.
> (let ((a 100) (b 200))
> (+ a (foo b)))
> ==> (+ 100 (foo 200))
>
> 2. If a variable is declared in a LET to some inital value returned
> from an expression,
> and then only used once, then there are cases when eliminating the
> variable makes
> sense and other times when it does not.
The notion of use would, of course, vary in languages that did and didn't
have global specials or lexicals by default, since otherwise you can't be
sure that any operator doesn't assign a free special that can affect you.
The question of used only once would depend on whether there were macros,
whether all the operators do the same things in all languages, etc.
> (let ((a (bar)))
> ...
> (+ a (foo)))
> ==> (+ (prog1 (bar) ...) (foo))
You're also presuming here that PROG1 is a more efficient thing to do.
What if PROG1 is simply implemented as the LET you started with and all
you're doing is slowing down compilation? What if PROG1 has, in some
implementation, some subtle difference in behavior regarding multiple
values that isn't there in another--you have to make sure to code for
that. What if prog1 was just assumed by a compiler writer to be a rare
construct to use and so was not optimized well, whereas LET was assumed
to be common and so was optimized?
What if the construct allows declarations in one language, but not
another, or if the declarations differ in scope or other semantics.
You have to avoid accidentally rewriting
(let ((a (bar))) (declare (special a)) ... (+ a (baz)))
to
(prog1 (bar) (declare (special a)) (+ (bar) (baz))) ;syntax ill-formed
or
(+ (prog1 (bar) ...) (baz)) ;what if baz uses special a?
This goes to the question of what a use of A is.
One might claim that my COUNT-USES predicate should return 1 in this case.
The problem isn't intractable, just hugely hard.
It's probably not your best first avenue of work. But if you want to
tackle it seriously, maybe you should talk to the guys at Cyc, who
probably well understand by now the complexity of making common sense
apply generally rather than specifically.
I hope this helps.
On Sat, 06 Oct 2007 03:53:39 -0700, jimka wrote:
> I'd like to write a macro called OPTIMIZE for another dialect of lisp (not
> common lisp), but i think the
> question makes sense here so i'll pose the question using CL examples.
>
> I'd like the macro "somehow" have a set of simplification rules that it
> can apply to
> its given code body. The rules hopefully are extensible in some way.
>
> I think such a macro is ultimately equivalent to a compiler, but perhaps
> there
> are some easy optimizations which can be made that will make code faster
> without having to implement a full compiler. Maybe I'm wrong :-(
>
> Does anyone have experience with such a thing. Are there resources where
> i can
> find useful code tranformations which are easy to implement?
Check Pinku Surana's dissertation, a copy is at
ftp://lispnyc.org/meeting-assets/2007-02-13_pinku/SuranaThesis.pdf
It develops a mechanism for optimization/compiling that has the
properties you are interested in. He has some comments about how much a
macro can (not) do.
And, of course, GCC has a generic optimizer. However, I would be surprised
if you could extract the rules/process easily.
On Oct 6, 10:53 pm, jimka <·····@rdrop.com> wrote:
> I'd like to write a macro called OPTIMIZE for another dialect of lisp
[[...]]
> I'd like the macro "somehow" have a set of simplification rules that
[[...]]
> I think such a macro is ultimately equivalent to a compiler, but
> perhaps there
> are some easy optimizations which can be made that will make code
> faster
> without having to implement a full compiler. Maybe I'm wrong :-(
>
> Does anyone have experience with such a thing. Are there resources
> where i can
> find useful code tranformations which are easy to implement?
If I'm not mistaken, what you want is exactly described by Darius
Bacon in
"A Hacker's Introduction to Partial Evaluation"
You are basically trying to do as much evaluation (at compile time) as
possible
given data that is known at compile time. The cybertyggr link you
might find would be
intermittently up and down, so you might need to find other cache or
mirrors on the web.
The example was given in Scheme, but you can see that an
implementation in CL,
using macros and compiler macros, would not only be more correct, but
in my opinion,
more elegant, given that you will be using the base language directly
for program
manipulation. Think environments, code walkers (implicit in
macroexpander), compilation
etc.
I hope that's what you wanted, it's really cool!
thanks for the reference.
I don't think what i'm looking for
is partial evaluation. The examples I gave are just two examples
of the type of reduction i'm looking for. They do amount
perhaps to partial evaluation. but i think there are many
simplifications which are very implementation dependent.
It seems that
many times i write macros, the macro expansion becomes
complicated when trying to deal with special cases which
are possible but unlikely. I.e., a setf style macro
that is really correct needs to destructure the the code
to assure side effects only happen once. to do this, normally
intermediate variables are introduced which often are
unnecessary. another case is that progn often contains a
single expression or leading nils which can be simplified.
I do not want to build all that intelligence into every
macro but have a rule based simplifier which can be
run after macro expansion. the rules would be based on
the run time characteristics of my particular lisp.
I really think what i'm looking for is very difficult.
I do not have much faith that it can really be useful without
being super intelligent. but i hope i'm wrong.
-jim
On Oct 8, 3:08 am, szergling <···············@gmail.com> wrote:
> On Oct 6, 10:53 pm, jimka <·····@rdrop.com> wrote:
>
> > I'd like to write a macro called OPTIMIZE for another dialect of lisp
>
> [[...]]
>
> > I'd like the macro "somehow" have a set of simplification rules that
>
> [[...]]
>
> > I think such a macro is ultimately equivalent to a compiler, but
> > perhaps there
> > are some easy optimizations which can be made that will make code
> > faster
> > without having to implement a full compiler. Maybe I'm wrong :-(
>
> > Does anyone have experience with such a thing. Are there resources
> > where i can
> > find useful code tranformations which are easy to implement?
>
> If I'm not mistaken, what you want is exactly described by Darius
> Bacon in
>
> "A Hacker's Introduction to Partial Evaluation"
>
> You are basically trying to do as much evaluation (at compile time) as
> possible
> given data that is known at compile time. The cybertyggr link you
> might find would be
> intermittently up and down, so you might need to find other cache or
> mirrors on the web.
> The example was given in Scheme, but you can see that an
> implementation in CL,
> using macros and compiler macros, would not only be more correct, but
> in my opinion,
> more elegant, given that you will be using the base language directly
> for program
> manipulation. Think environments, code walkers (implicit in
> macroexpander), compilation
> etc.
>
> I hope that's what you wanted, it's really cool!
On Oct 9, 7:35 am, jimka <·····@rdrop.com> wrote:
> many times i write macros, the macro expansion becomes
> complicated when trying to deal with special cases which are
> possible but unlikely. I.e., a setf style macro that is really
> correct needs to destructure the the code to assure side
> effects only happen once. to do this, normally intermediate
> variables are introduced which often are unnecessary. another
> case is that progn often contains a single expression or
> leading nils which can be simplified. I do not want to build
> all that intelligence into every macro but have a rule based
> simplifier which can be
In fact, this was kinda in that article I referenced. Your rule
interpreter can be called by any macro that needs it. So, you can
have (hypothetically, implementation left as exercise (: ) rules
like:
(progn ?any) -> ?any
(progn nil . ?any) -> (progn . ?any)
(progn) -> nil
This is a special case where we eliminate expressions with no
side-effects (in this case, the expression 'nil'). More
generally, intermediate variable elimination:
(?once-only ?var ?expressions
(let ((?var ?any)) . ?expressions))
-> (?substitute (?var ?any) (progn . ?expressions))
this hypothetical rule looks hard to implement, and even has to
check that ?any has no side effects (otherwise, it gets the order
of evaluation wrong). Yeah, this is starting to get too hard to
do off-hand!
The setf ones, I'll need to revise my get-setf-expansion, but
maybe this is helped by all the built in setf expansion
utilities?
As long as these rules always reduce, you can run them repeatedly
until everything 'settles'.
> run after macro expansion. the rules would be based on
after? Ideally, it'll be during macroexpansion, seamlessly
interleaved into your macro expansion.
> the run time characteristics of my particular lisp. I really
> think what i'm looking for is very difficult. I do not have
> much faith that it can really be useful without being super
> intelligent. but i hope i'm wrong.
So you cannot possibly handle everything. That's why you need to
open up as much of your compiler (macros are one way to do this)
to the user as possible. They know what they need, so they can
write their own source-to-source translation rules. You need only
provide the rule interpreter.
Just some of my thoughts, I haven't actually tried out everything
I said.