Re: Sacla loop: a new loop implementation

From: Duane Rettig (duane_at_franz.com)
Date: 10/19/04 

Date: 19 Oct 2004 08:57:31 -0700

Antonio Menezes Leitao <Antonio.Leitao@evaluator.pt> writes:

> Duane Rettig <duane@franz.com> writes:
>
> > Finally, once the foo macro receives its argument, then based on what
> > it sees in the variable-information for its argument, it can decide
> > whether to generate code that is generic (e.g. has a type-case) or
> > code which is specific (e.g. it can assume its argument is a fixnum).
> > Such code might be completely different for the two situations,
> > depending on how the macro is defined.
>
> Maybe I didn't understand your example but it seems to me that that's
> another perfect example of a situation where foo can be a normal macro
> that can simply expand into a typecase form and that then waits for
> the code optimization phase to remove the unneded branches based on
> the type information available about the type of the len variable.

This is what tends to occur now. Some of this is unavoidable. However,
There are two reasons for preferring to do this propagation at
macroexpand time:

 1. Rewriting code at the "source" level (i.e. internal representations
understood by all Lisp programmers) eliminates the "magic" of having
transformations and optimizations deep in the bowels of the compiler,
using whatever internal representations the compiler sees fit to
use. In essence, it "opens" the optimization implementation to user
analysis and extension.

 2. Sometimes a macroexpansion (which might itself represent an
optimization) removes critical information about the nature of the
source, thus making it hard (sometimes extremely hard) to reason
about types later in the compilation. See my trivial example below.

> This would avoid all the messy transformations that you described.

I used "messy" in a relative sense. It is _much_ more messy to try
to reason about internal compiler structures.

> That's why I ask about what is preferable. I would love to see an
> example where it really made a difference to have that information
> available at macroexpansion time.

Consider the trivial loop

  (dotimes (i 10) (foo i))

What is the type of i? The correct answer is (integer 0 10)
[one might actually guess (correctly) that all of the _uses_
of i will only ever see (integer 0 (10)), but in fact i
transiently takes on the value 10 when rounding the last
iteration in expanded code]
Now, based on the CL specification of what components dotimes
must macroexpand into, note that the macroexpansion becomes
much less trivial to reason about:

CL-USER(2): (pprint (macroexpand '(dotimes (i 10) (foo i))))

(BLOCK NIL
  (LET ((I 0))
    (TAGBODY
      #:|Tag2|
        (COND ((>= I 10) (RETURN-FROM NIL (PROGN))))
        (TAGBODY (FOO I))
        (PSETQ I (1+ I))
        (GO #:|Tag2|))))
CL-USER(3):

If the type propagation is done after the macroexpansion, then
unless some annotation os carried along with the code, extended
graph theory and type calculus must be done in order to reason
about the type of i (note that it is set once at initialization,
and then again within a loop,but the termination clause must be
examined to know what the upper limit is). If foo had been a
macro and the macroexpansion of foo could have generated better
code if it had known that i is as small as it turns out to be,
then by this time it is too late to rewrite foo's code.

But if we let macroexpansion do this job, using environments:

CL-USER(3): (pprint (macroexpand '(dotimes (i 10) (foo i))
                                 (sys:make-compile-file-environment)))

(BLOCK NIL
  (LET ((I 0))
    (DECLARE (TYPE (INTEGER 0 10) I))
    (TAGBODY
      #:|Tag3|
        (COND ((>= I 10) (RETURN-FROM NIL (PROGN))))
        (TAGBODY (FOO I))
        (PSETQ I (THE (INTEGER 0 10) (1+ I)))
        (GO #:|Tag3|))))
CL-USER(4):

then we see that the type is deduced, and is even propagated
to the psetq. Note that this macroexpansion is using the
"messy" style of annotating the code with THE forms. This is
still _much_ cleaner than trying to reason about tagbody forms.
The reason I call it messy, and eventually desire to move these
to the compilation environment rather than annotating the code
directly, is because sending this form to an interpreter forces
the interpreter to evaluate (and possibly treat as nops) the THE
forms.

> > Now, obviously, compiler-macros will benefit most from this kind
> > of macro-level type inference. But macros can also benefit; they
> > also can ask to receive an environment argument, and can test
> > whether the environment is a compilation environment or not. Also,
> > some of this can be done now, whenever arguments to macros are
> > either manifest constants or trivially calculable (though as I said
> > it can sometimes get messy). But it has _always_ been the case
> > that macros (whether compiler-macros or normal macros) have the
> > power to make decisions programmatically about what code they want
> > to expand to, given enough information. What I am working toward
> > is providing in a portable way more and more of that information,
> > information that won't be changing,and which is thus in a sense
> > "static" information, so that the macro has the ability to reason
> > and pare down its code produced to code that is only as dynamic
> > as is needed.
>
> That's good, obviously. Do you have any data regarding the amount of
> type information that you can provide to macroexpanders, e.g., in the
> following situation:
>
> (let ((len (my-length x)))
> (foo len))
>
> (defun my-length (x)
> (length x))

Assuming these two forms are in a file to be compiled: the ordering
of these forms disallows any transfer of type information for my-length.
However, if we instead consider a file with:

(defun my-length (x)
  (length x))

(let ((len (my-length x)))
  (foo len))

then the semantics of compile-file allows the compiler to assume
(unless my-length has been declaed notinline) that the my-length
call is in fact to the definiton one above it, and therefore it
might make sense to establish in the compile-file-environment an
automatic ftype declaration for my-length which would then be used
in the call. So if I understand the direction of your question,
then yes, a foo macro would be able to receive a type declaration
of (integer 0 #.most-positive-fixnum). 

-- 
Duane Rettig    duane@franz.com    Franz Inc.  http://www.franz.com/
555 12th St., Suite 1450               http://www.555citycenter.com/
Oakland, Ca. 94607        Phone: (510) 452-2000; Fax: (510) 452-0182

Relevant Pages

  • Re: Sacla loop: a new loop implementation
    ... > Let's consider my previous for-each macro and let's also consider the ... > macro without knowing the type of arg? ... > that the compiler must know that type in order to expand the macro. ... (declaim (inline foo)) ...
    (comp.lang.lisp)
  • Re: Sacla loop: a new loop implementation
    ... > transformations and optimizations deep in the bowels of the compiler, ... note that the macroexpansion becomes ... > macro and the macroexpansion of foo could have generated better ... What would be different if foo had access to type information? ...
    (comp.lang.lisp)
  • Re: approach to writing recursive macros
    ... "functional-replace" is a name of the desired macro and it accepts ... Here (foo bar) isn't an operator call, ... Common Lisp doesn't have a code walker function, ... into the compiler, ...
    (comp.lang.lisp)
  • Re: Strange MACRO Problem
    ... > Why following macro does not work? ... for all 'foo'. ... so the compiler should give you ... [and remove both pairs of the extra parentheses] ...
    (comp.lang.c)
  • Re: Creating compilation errors in macros
    ... inhibits converting to macros is error handling. ... similar to those issued by the compiler. ... (in macroexpansion of (FOO X)) ...
    (comp.lang.lisp)
Loading