Subject: [clisp-list] on optimizations (was: New, from-scratch implementation of backqu ote.)

From: "Hoehle, Joerg-Cyril" <[email-masked]>
Date: Wed Mar 26 04:06:14 2003

Hi,

Kaz implicitly raised the topic on who/what component ought to do Lisp-level optimizations (or code-rewrites).

Kaz Kylheku wrote:
>   (cons 'a (cons 'b (append a (append b c))))
>where the original implementation would put out:
>   (list* 'a 'b (append a b c))

>Profiling under CLISP shows that even for making a list of two cons
>cells, one call to list* with three arguments is slightly faster than
>two calls to cons, so this reduction appears worthwhile, and can be
>done by a trivial cleanup pass.

[164]> (disassemble #'(lambda (x y z) (cons x (cons y z))))
Disassembly of function :LAMBDA
[...]
3     (CONS)
4     (CONS)
5     (SKIP&RET 4)
#<COMPILED-CLOSURE :LAMBDA>
It could have been the bytecode (LIST* 2)

One can argue that the best place for optimizations at the Lisp-level is the Lisp compiler[*]. Especially it's not the macro writer's job to do trivial transformations of degenerate or simple cases. This makes the macro's code clumsy and less readable.

To me the bottom line is always the same: a compiler written with a human programmer in mind need not do such optimizations. It embeds assumptions which only apply to hand-written code.

Such assumptions typically lead to stupid-looking restrictions like a line-length limit of 1024 bytes (see your favourite HTTP reference on URL length), a small nesting limit on loops etc. - Examples are abundant. A decade ago, trying to port CLISP to various platforms, we hit various C preprocessors who could not deal with CLISP's many C macros: expanded lines became too long, macro nesting was too deep, etc. We kicked al these products. IIRC, a result of this is that CLISP still contains utils/gcc-cccp.c, a working C preprocessor, instead of relying on the vendors one. We also hit numerous arbitrarily small restrictions in the C compiler itself, which each could be traced to an implicit assumption that hand-written C code would never look like what the C compiler got to see with CLISP.

Some people have claimed that CLISP abuses the C preprocessor. I counter: it's a legitimate use. More on that another time.

A compiler written with machine/lexers/macro-generators in mind gets to see code which never would be written by hand. IMHO, it should nevertheless produce good code.

An important point is: Optimization cost analysis time that a compiler written for a human programmer need not spend. Maybe CLISP should look at DECLARE SPEED settings?

[*] Talking about Lisp-level optimizations, I mean things like CONS of CONS->LIST*, either at the level of Lisp-code or byte-code rewrites. I do not request that a Lisp compiler shall find the possible optimizations of the application's domain, e.g. backtrack points for a Prolog written on top of Lisp.
There are also many situations where the compiler cannot figure out whether an optimization is possible, without whole program analysis. Constant folding is a typical example, stack-allocation another one.

Regards,
	Jorg Hohle.

---

From: Kaz Kylheku <[email-masked]>
Date: Wed Mar 26 13:26:13 2003

On Wed, 26 Mar 2003, Hoehle, Joerg-Cyril wrote:

> Kaz implicitly raised the topic on who/what component ought to do
> Lisp-level optimizations (or code-rewrites).

Right. When your backquote puts out code like (APPEND (LIST A) (LIST
B)) who should optimize that? In principle, the Lisp compiler can do
the code transformation to (LIST A B), so the backquote implementor
doesn't have to worry about it.

> One can argue that the best place for optimizations at the Lisp-level
> is the Lisp compiler[*]. Especially it's not the macro writer's job to
> do trivial transformations of degenerate or simple cases. This makes
> the macro's code clumsy and less readable.

But then again macros *are* compilers. ;) Macros that are built into an
implementation like CLISP are effectively part of the compiler. So
whether or not backquote does the APPEND reduction, or the Lisp
compiler, is immaterial to the user. It's an architectural decision
impacting the internals.

There is a good case that can be made for having backquote do the code
transformations: the user can interact with backquote and see what it
is doing. The optimized list construction code is also more readable,
because it's closer to what a Lisp programmer would write, had she no
backquote syntax.

If I typed 

  (macroexpand-1 '`(,a ,b ,c))

I'd rather read

  (LIST A B C)

than

  (APPEND (LIST A) (LIST B) (LIST C))

When you have nested backquotes, the extra verbiage piles up on your
brain. ;)

Here is another way to look at it: the backquote translator is a robot
programmer who writes *source* code, and as such, that programmer
should write the same kind of decent code that a human would write.
This is not really even an optimization issue; there is some esthetic
principle involved here. :)

Here is another consideration: there are cases when the backquote
translator can legitimately reduce, for instance, (LIST 1 2 3) 
to '(1 2 3).

But the Lisp compiler cannot do this reduction, because the result
of the expression may be destructively manipulated somewhere.
After the backquote expander has done its job, the context is lost:
it's no longer obvious that the code came from a backquote notation.

So then you are looking at either rolling the backquote logic into the
compiler, doing the constant folding in the backquote implementation
(so you are still arguably doing part of a compiler's job there, oops!)
or having the backquote notation emit special annotations that hint to
the compiler that the reduction may be done, like:

 (SYSTEM::THE-RESULT-OF-BQ-EXPANSION (APPEND ...))

Hmm.