From: Dr. Edmund Weitz
Subject: smart compiler (example in PAIP)
Date: 
Message-ID: <m3zo6zu2ic.fsf@bird.agharta.de>
Hello!

While reading the chapter about efficiency issues in PAIP I came
across an amazing example (p. 279) where Norvig shows two functions

(defun f1 (n l)
  (let ((l1 (first l))
        (l2 (second l)))
    (expt (* 1 (+ n 0))
          (- 4 (length (list l1 l2))))))

(defun f2 (n l) (* n n))

where his particular Lisp compiler was so smart that both functions
yielded the same result if feeded to DISASSEMBLE:

> (disassemble 'f1)
   6 PUSH             ARG|0         ; N
   7 MOVEM            PDL-PUSH
   8 *                PDL-POP
   9 RETURN           PDL-POP
F1

Unfortunately, he doesn't name the system he was using. I tried his
example on CMUCL, CLISP, and the evaluation versions of LispWorks and
Allegro, but all of them produced much more code for F1 than for
F2. The last assembler program that I wrote was for a 6502 on my Apple
II, but all of the results looked to me as if the operations in the
definition of F1 were carried out more or less literally.

Now my questions, out of pure curiosity, are:

1. Does anybody know which smart compiler Norvig used in his example?
   Maybe one can infer this from the machine code above. LispM?

2. Why do the four implementations mentioned above not optimize this
   function? Is this extremely hard to do or was it just deemed to be
   not worth the effort? Or is it maybe forbidden by some part of the
   ANSI standard? (I think Norvig's book was pre-ANSI.)

Thanks for your time,
Edi.

From: Sam Steingold
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <uwv23twak.fsf@xchange.com>
> * In message <··············@bird.agharta.de>
> * On the subject of "smart compiler (example in PAIP)"
> * Sent on 10 Oct 2001 14:02:19 +0200
> * Honorable ···@agharta.de (Dr. Edmund Weitz) writes:
>
> While reading the chapter about efficiency issues in PAIP I came
> across an amazing example (p. 279) where Norvig shows two functions
> 
> (defun f1 (n l)
>   (let ((l1 (first l))
>         (l2 (second l)))
>     (expt (* 1 (+ n 0))
>           (- 4 (length (list l1 l2))))))
> 
> (defun f2 (n l) (* n n))
> 
> where his particular Lisp compiler was so smart that both functions
> yielded the same result if feeded to DISASSEMBLE:
> 
> > (disassemble 'f1)
>    6 PUSH             ARG|0         ; N
>    7 MOVEM            PDL-PUSH
>    8 *                PDL-POP
>    9 RETURN           PDL-POP
> F1

I believe this optimization is illegal
 - shouldn't (FIRST non-nil-atom) signal an error?

-- 
Sam Steingold (http://www.podval.org/~sds)
Support Israel's right to defend herself! <http://www.i-charity.com/go/israel>
Read what the Arab leaders say to their people on <http://www.memri.org/>
Bus error -- please leave by the rear door.
From: Kent M Pitman
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <sfwr8sb5z7y.fsf@world.std.com>
Sam Steingold <···@gnu.org> writes:

> I believe this optimization is illegal
>  - shouldn't (FIRST non-nil-atom) signal an error?

They "should signal", yes.  FIRST and friends are defined by analogy
to CAR/CDR.  CAR/CDR "should signal" an error of type TYPE-ERROR when
they get a wrong type argument.  ANSI CL defines this phrase "should
signal" as: "This means that an error is signaled in safe code, and an
error might be signaled in unsafe code."  See 1.4.2 (Error Terminology).

My reading is, therefore, is that an optimization that rewrites
(FIRST '(FOO)) as 'FOO is valid anytime SAFETY is less than 3.
From: Pierre R. Mai
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <87vghnbfzk.fsf@orion.bln.pmsf.de>
Kent M Pitman <······@world.std.com> writes:

> Sam Steingold <···@gnu.org> writes:
> 
> > I believe this optimization is illegal
> >  - shouldn't (FIRST non-nil-atom) signal an error?
> 
> They "should signal", yes.  FIRST and friends are defined by analogy
> to CAR/CDR.  CAR/CDR "should signal" an error of type TYPE-ERROR when
> they get a wrong type argument.  ANSI CL defines this phrase "should
> signal" as: "This means that an error is signaled in safe code, and an
> error might be signaled in unsafe code."  See 1.4.2 (Error Terminology).
> 
> My reading is, therefore, is that an optimization that rewrites
> (FIRST '(FOO)) as 'FOO is valid anytime SAFETY is less than 3.

Just to be pedantic, but isn't that particular optimization (since
'(foo) is a constant) valid even for SAFETY = 3?  SAFETY = 3 would
however inhibit the eliminiation of FIRST in the following way:

(PROG1 5 (FIRST FOO)) => 5

UNLESS the compiler can prove that FOO will always be of type LIST.

Regs, Pierre.

-- 
Pierre R. Mai <····@acm.org>                    http://www.pmsf.de/pmai/
 The most likely way for the world to be destroyed, most experts agree,
 is by accident. That's where we come in; we're computer professionals.
 We cause accidents.                           -- Nathaniel Borenstein
From: Carl Shapiro
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <ouyofnfft7h.fsf@panix3.panix.com>
···@agharta.de (Dr. Edmund Weitz) writes:

> > (disassemble 'f1)
>    6 PUSH             ARG|0         ; N
>    7 MOVEM            PDL-PUSH
>    8 *                PDL-POP
>    9 RETURN           PDL-POP
> F1
> 
> Unfortunately, he doesn't name the system he was using. 
                                                          
I suspect that this is the disassembly was done on a TI Explorer.
From: ···@itasoftware.com
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <elobp9mn.fsf@itasoftware.com>
Carl Shapiro <········@panix.com> writes:

> ···@agharta.de (Dr. Edmund Weitz) writes:
> 
> > > (disassemble 'f1)
> >    6 PUSH             ARG|0         ; N
> >    7 MOVEM            PDL-PUSH
> >    8 *                PDL-POP
> >    9 RETURN           PDL-POP
> > F1
> > 
> > Unfortunately, he doesn't name the system he was using. 
>                                                           
> I suspect that this is the disassembly was done on a TI Explorer.

Definitely a LispM, but it an Exploder, Lambda, or CADR would be
pretty much the same for this.
From: James A. Crippen
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <m3adyxrukf.fsf@kappa.unlambda.com>
···@itasoftware.com writes:

> Carl Shapiro <········@panix.com> writes:
> 
> > ···@agharta.de (Dr. Edmund Weitz) writes:
> > 
> > > > (disassemble 'f1)
> > >    6 PUSH             ARG|0         ; N

Pushes zeroth index of array pointed to by ARG pointer in FEF
(function entry frame) onto stack.  Comment tells you this was a
symbol named 'N.

> > >    7 MOVEM            PDL-PUSH

Copies top of stack to top of stack (ie, dups top of stack).
Presumably the compiler chose this instead of another PUSH ARG|0
because MOVEM was cheaper.

> > >    8 *                PDL-POP

Pops stack twice and multiplies the two values, then pushes the result.

> > >    9 RETURN           PDL-POP

Pops value and returns it.

> > > F1

The result of the DISASSEMBLE function.

> > > 
> > > Unfortunately, he doesn't name the system he was using. 
> >                                                           
> > I suspect that this is the disassembly was done on a TI Explorer.
> 
> Definitely a LispM, but it an Exploder, Lambda, or CADR would be
> pretty much the same for this.

From the Exploder System Software Design Notes, 2nd ed:

  PUSH base-obj                               [50] MAIN-OP
    Pushes the value at base-obj to the top of the stack.

  MOVEM base-loc                             [141] MAIN-OP
    Copies the value at the top of stack to base-loc.
    Does not pop the top of stack nor does it return a
    value.

  * x y                                       [62] MAIN-OP
    Limited argument instruction.  See description of
    corresponding multi-argument Lisp function.

  RETURN base-val                             [17] MAIN-OP
    Causes the current call frame to fold and a return to
    the previous call frame.  The value at base-val will
    be left on top of the stack, which is exactly where
    the current (function executing RETURN) call frame
    started.

So we can at least conclude that even if that code was generated on a
LAMBDA or a CADR, it would have run on an Exploder.  Given assembly
that is.

'james

-- 
James A. Crippen <·····@unlambda.com> ,-./-.  Anchorage, Alaska,
Lambda Unlimited: Recursion 'R' Us   |  |/  | USA, 61.2069 N, 149.766 W,
Y = \f.(\x.f(xx)) (\x.f(xx))         |  |\  | Earth, Sol System,
Y(F) = F(Y(F))                        \_,-_/  Milky Way.
From: Scott McKay
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <TiXw7.103826$vq.20564403@typhoon.ne.mediaone.net>
"Dr. Edmund Weitz" <···@agharta.de> wrote in message
···················@bird.agharta.de...
>
> While reading the chapter about efficiency issues in PAIP I came
> across an amazing example (p. 279) where Norvig shows two functions
>
> (defun f1 (n l)
>   (let ((l1 (first l))
>         (l2 (second l)))
>     (expt (* 1 (+ n 0))
>           (- 4 (length (list l1 l2))))))
>
> (defun f2 (n l) (* n n))
>
> where his particular Lisp compiler was so smart that both functions
> yielded the same result if feeded to DISASSEMBLE:
>
> > (disassemble 'f1)
>    6 PUSH             ARG|0         ; N
>    7 MOVEM            PDL-PUSH
>    8 *                PDL-POP
>    9 RETURN           PDL-POP
> F1

Yeah, 'f2' is a completely reasonable optimization of 'f1'.
'(length (list l1 l2))' gets partially evaluated to 2, '(- 4 2)' gets
constant-folded to 2, '(* 1 (+ n 0))' gets partially evaluated
to n, '(expt n 2)' gets strength-reduced to '(* n n)', and you're
done.  These are the kinds of optimizations that the Lisp
Machine compiler(s) did.  Amazingly, my recollection is
fuzzy on whether this is CADR-style assembly code or
3600-style (I can only clearly remember Ivory code right
now!).  This could either have been on a Symbolics 3600,
or one of a Symbolics LM-2, LMI Lambda, or TI Explorer.

> Unfortunately, he doesn't name the system he was using. I tried his
> example on CMUCL, CLISP, and the evaluation versions of LispWorks and
> Allegro, but all of them produced much more code for F1 than for
> F2. The last assembler program that I wrote was for a 6502 on my Apple
> II, but all of the results looked to me as if the operations in the
> definition of F1 were carried out more or less literally.
>
> Now my questions, out of pure curiosity, are:
>
> 1. Does anybody know which smart compiler Norvig used in his example?
>    Maybe one can infer this from the machine code above. LispM?
>
> 2. Why do the four implementations mentioned above not optimize this
>    function? Is this extremely hard to do or was it just deemed to be
>    not worth the effort? Or is it maybe forbidden by some part of the
>    ANSI standard? (I think Norvig's book was pre-ANSI.)
>
From: Tim Bradshaw
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <ey3wv23k4mi.fsf@cley.com>
* Scott McKay wrote:

> Yeah, 'f2' is a completely reasonable optimization of 'f1'.
> '(length (list l1 l2))' gets partially evaluated to 2, '(- 4 2)' gets
> constant-folded to 2, '(* 1 (+ n 0))' gets partially evaluated
> to n, '(expt n 2)' gets strength-reduced to '(* n n)', and you're
> done.  These are the kinds of optimizations that the Lisp
> Machine compiler(s) did.  Amazingly, my recollection is
> fuzzy on whether this is CADR-style assembly code or
> 3600-style (I can only clearly remember Ivory code right
> now!).  This could either have been on a Symbolics 3600,
> or one of a Symbolics LM-2, LMI Lambda, or TI Explorer.

I guess this depends on whether it's OK to optimize away the
possibly-invalid calls to FIRST and SECOND.  It probably is, I
suppose.

I think it's definitely not 3600 code (at least it doesn't look
anything like the disassembly I made of stuff on 36XXs).

--tim
From: Tim Bradshaw
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <ey31ykbljkf.fsf@cley.com>
* Edmund Weitz wrote:

> 1. Does anybody know which smart compiler Norvig used in his example?
>    Maybe one can infer this from the machine code above. LispM?

I don't *think* this is either of the symbolics architectures (3600,
Ivory) although it might be.  It's certainly something with pretty
direct support for Lisp (maybe a PDP-10?).

> 2. Why do the four implementations mentioned above not optimize this
>    function? Is this extremely hard to do or was it just deemed to be
>    not worth the effort? Or is it maybe forbidden by some part of the
>    ANSI standard? (I think Norvig's book was pre-ANSI.)

Well, one thing is that the example code for F2 is making assumptions
that are presumably either not being checked, or being checked in
hardware: the argument count to the function isn't obviously checked
anywhere, and whether N is actually some numeric type is not checked.
My guess is that for the latter of these, * checks and dispatches
according to type.  If * is an instruction rather than a function call
then you can see how much support the machine must have for Lisp to
produce code this concise.

In order to convert F1 into F2 worse assumptions are being made: that
L is in fact a cons or NIL.  Iff this is true then F1 can be
converted into F2, if it's not, then F1 should signal an error, I
think.

for more conventional hardware, to have some hope of getting code this
concise, you probably need to put in a type declaration for N of a
suitably good type (or live with a function call to the generic *
operation), and for F1 probably turn safety off completely.  Even in
that case you will probably have a fair amount more noise in the code,
since there will be register moves &c going on which don't happen on a
stack machine. I haven't experimented with this to see if you actually
can get code this small.

--tim
From: Raymond Toy
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <4nwv23txmw.fsf@rtp.ericsson.se>
>>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:

    Tim> for more conventional hardware, to have some hope of getting code this
    Tim> concise, you probably need to put in a type declaration for N of a
    Tim> suitably good type (or live with a function call to the generic *
    Tim> operation), and for F1 probably turn safety off completely.  Even in
    Tim> that case you will probably have a fair amount more noise in the code,
    Tim> since there will be register moves &c going on which don't happen on a
    Tim> stack machine. I haven't experimented with this to see if you actually
    Tim> can get code this small.

(defun f1 (n l)
  (let ((l1 (first l))
        (l2 (second l)))
    (expt (* 1 (+ n 0))
          (- 4 (length (list l1 l2))))))

I've played around a little with this with CMUCL.  Given all of the
assumptions you've made, CMUCL will convert (* 1 (+ n 0)) to just n
today without any problems.  However, the problem is that it's not
smart enough to determine that (list l1 l2) is of type (cons t (cons t
null)) (I think I got that right).  Then, the compiler doesn't know
the length of such a type is 2.

I tried once to add some of the smarts to the compiler to do this, but
it made a huge mess of things.  The compiler was deleting code left
and right because it thought things of type (cons t t) had length 1
but in fact is not and then when you destructively modified the list
it still didn't know anything had happened.

Needless to say, I stopped.  I suppose I could have added more, but
decided it probably wasn't worth the effort to get this simple example
in PAIP to produce the "optimized" code.  Would have been cool,
though. 

Ray
From: Raymond Toy
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <4ny9mi41zz.fsf@rtp.ericsson.se>
>>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:

    Tim> * Edmund Weitz wrote:
    >> 1. Does anybody know which smart compiler Norvig used in his example?
    >> Maybe one can infer this from the machine code above. LispM?

    Tim> for more conventional hardware, to have some hope of getting code this
    Tim> concise, you probably need to put in a type declaration for N of a
    Tim> suitably good type (or live with a function call to the generic *
    Tim> operation), and for F1 probably turn safety off completely.  Even in
    Tim> that case you will probably have a fair amount more noise in the code,
    Tim> since there will be register moves &c going on which don't happen on a
    Tim> stack machine. I haven't experimented with this to see if you actually
    Tim> can get code this small.

Paul Foley sent me a compiler macro for length and when you use this
on the following function, CMUCL produces pretty good results.

(define-compiler-macro length (&whole form thing)
    (cond ((not (consp thing))
           form)
          ((eq (first thing) 'list)
           (length (rest thing)))
          ((eq (first thing) 'list*)
           `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
          (t
           form)))

(defun f1 (n l)
  (declare (fixnum n) (cons l)
	   (optimize (speed 3) (safety 0)))
  (let ((l1 (first l))
        (l2 (second l)))
    (expt (* 1 (+ n 0))
          (- 4 (length (list l1 l2))))))

The (safety 0) is just so the disassembly doesn't have all of the code
to check for things.  (speed 3) probably isn't necessary either.

The result is:

;; Set up stack
      A0:       ADD        -18, %CODE
      A4:       ADD        %CFP, 32, %CSP

;; Move the arg (in %a0) to the register %nl0
      A8:       MOV        %A0, %NL0                   ; %A0 = #:G1
      AC:       ST         %OCFP, [%CFP]
      B0:       ST         %LRA, [%CFP+4]              ; No-arg-parsing entry point

;; Move n (in %nl0) to the 2 argument registers (%a0, %a1) for the call to generic *
      B4:       MOV        %NL0, %A1
      B8:       MOV        %NL0, %A0
      BC:       ADD        %CODE, 96, %LRA
      C0:       SETHI      %hi(#x10000000), %NL0
      C4:       J          %NL0+856                    ; #x10000358: GENERIC-*
      C8:       NOP
      CC:       ILLTRAP    0
      D0:       .LRA

;; Return from this function

      D4:       MOV        %OCFP, %CSP
      D8:       NOP

      DC:       ADD        -96, %CODE
      E0:       LDUW       [%CFP], %NL0                ; %NL0 = N
      E4:       LDUW       [%CFP+4], %A1

      E8:       MOV        %CFP, %CSP
      EC:       MOV        %NL0, %CFP
      F0:       J          %A1+5
      F4:       MOV        %A1, %CODE

Not too bad.  If you make n a (signed-byte 15) so it doesn't overflow,
you get the following code:

     600:       ADD        -18, %CODE
     604:       ADD        %CFP, 32, %CSP
     608:       SRA        %A0, 2, %NL0                ; No-arg-parsing entry point
     60C:       SMUL       %NL0, %A0
     610:       MOV        %CFP, %CSP
     614:       MOV        %OCFP, %CFP
     618:       J          %LRA+5
     61C:       MOV        %LRA, %CODE

So there's a little noise for setting up the stack and returning the
result.


Note that CMUCL notices that l1 and l2 are no longer used and then
deletes them which deletes the calls to first and second, even if the
declaration for l is left out.  A possible compiler bug?

Ray
From: Kent M Pitman
Subject: (safety 0) [was: Re: smart compiler (example in PAIP)]
Date: 
Message-ID: <sfwy9mignt4.fsf_-_@world.std.com>
Raymond Toy <···@rtp.ericsson.se> writes:

> The (safety 0) is just so the disassembly doesn't have all of the code
> to check for things.  (speed 3) probably isn't necessary either.

A lot of people use (safety 0) along with (speed 3) in order to "help it".
I'm not sure this is a good idea.  I think there are some implementations
in which this does no extra good, and maybe worse.

My recollection (please correct me if I'm wrong Xanalys-maintainers)
is that LispWorks in (safety 0) mode will not check for stack overflow
and one or two other things that I think of as essential and should not be
controllable in such a way, since I still expect (safety 0) code to run
correctly in the face of semantically correct code.  It is for this reason
that I try never to let anything less than (safety 1) creep into my code.
[There was once a chart floating around of what the settings actually do.
I wish we could get a comparison chart of the effects of these at the ALU
site...]
From: Raymond Toy
Subject: Re: (safety 0) [was: Re: smart compiler (example in PAIP)]
Date: 
Message-ID: <4nu1x63zzp.fsf@rtp.ericsson.se>
>>>>> "Kent" == Kent M Pitman <······@world.std.com> writes:

    Kent> Raymond Toy <···@rtp.ericsson.se> writes:
    >> The (safety 0) is just so the disassembly doesn't have all of the code
    >> to check for things.  (speed 3) probably isn't necessary either.

    Kent> A lot of people use (safety 0) along with (speed 3) in order to "help it".
    Kent> I'm not sure this is a good idea.  I think there are some implementations
    Kent> in which this does no extra good, and maybe worse.

    Kent> My recollection (please correct me if I'm wrong Xanalys-maintainers)
    Kent> is that LispWorks in (safety 0) mode will not check for stack overflow
    Kent> and one or two other things that I think of as essential and should not be
    Kent> controllable in such a way, since I still expect (safety 0) code to run
    Kent> correctly in the face of semantically correct code.  It is for this reason
    Kent> that I try never to let anything less than (safety 1) creep into my code.

Can't speak for others but on CMUCL, at least in this example, a
non-zero safety value puts in checks to see that the function is
called with the right number of arguments and that the arguments are
of the declared types.

I just didn't want the code cluttered with these checks.

CMUCL never checks for stack overflow and prefers to crash in those
situations.

I normally only use (safety 0) inside of functions where I know things
are safe.  But I've been caught in cases where it was safe, but then I
made changes that made it no longer safe and therefore incorrect. :-)

A good rule.

    Kent> [There was once a chart floating around of what the settings actually do.
    Kent> I wish we could get a comparison chart of the effects of these at the ALU
    Kent> site...]

That would be nice.

Ray
From: Bradford W. Miller
Subject: Re: (safety 0) [was: Re: smart compiler (example in PAIP)]
Date: 
Message-ID: <B7EB8949.9FA3%Bradford.W.Miller@motorola.com>
> 
>   Kent> [There was once a chart floating around of what the settings actually
> do.
>   Kent> I wish we could get a comparison chart of the effects of these at the
> ALU
>   Kent> site...]
> 
> That would be nice.
> 
> Ray

At least in Allegro Common Lisp, the programmer is able to change what
specific optimizations are associated with each level.
From: Christophe Rhodes
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <sqwv22qhss.fsf@cam.ac.uk>
Raymond Toy <···@rtp.ericsson.se> writes:

> >>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:
> 
>     Tim> * Edmund Weitz wrote:
>     >> 1. Does anybody know which smart compiler Norvig used in his example?
>     >> Maybe one can infer this from the machine code above. LispM?
> 
>     Tim> for more conventional hardware, to have some hope of getting code this
>     Tim> concise, you probably need to put in a type declaration for N of a
>     Tim> suitably good type (or live with a function call to the generic *
>     Tim> operation), and for F1 probably turn safety off completely.  Even in
>     Tim> that case you will probably have a fair amount more noise in the code,
>     Tim> since there will be register moves &c going on which don't happen on a
>     Tim> stack machine. I haven't experimented with this to see if you actually
>     Tim> can get code this small.
> 
> Paul Foley sent me a compiler macro for length and when you use this
> on the following function, CMUCL produces pretty good results.
> 
> (define-compiler-macro length (&whole form thing)
>     (cond ((not (consp thing))
>            form)
>           ((eq (first thing) 'list)
>            (length (rest thing)))
>           ((eq (first thing) 'list*)
>            `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
>           (t
>            form)))

Um, but, but, but ... I thought of this, but

(length (list (setf *foo* 'bar)))

?

I think the right thing to do is to get the type system to do this
right...

Cheers,

Christophe
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Roger Corman
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <3bc6a30d.571093879@news.callatg.com>
On 11 Oct 2001 17:10:11 +0100, Christophe Rhodes <·····@cam.ac.uk> wrote:

>Raymond Toy <···@rtp.ericsson.se> writes:
>
>> >>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:
>> 
>> Paul Foley sent me a compiler macro for length and when you use this
>> on the following function, CMUCL produces pretty good results.
>> 
>> (define-compiler-macro length (&whole form thing)
>>     (cond ((not (consp thing))
>>            form)
>>           ((eq (first thing) 'list)
>>            (length (rest thing)))
>>           ((eq (first thing) 'list*)
>>            `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
>>           (t
>>            form)))
>
>Um, but, but, but ... I thought of this, but
>
>(length (list (setf *foo* 'bar)))
>
>?

Ah, if we didn't allow side effects compilers would be much simpler, wouldn't
they?

How about this?
(define-compiler-macro length (&whole form thing)
   (cond ((not (consp thing))
               form)
             ((and (eq (first thing) 'list)
                     (consp (cdr thing))
                     (consp (second thing))
                     (eq (first (second thing)) 'setf))
              `(progn ,(second thing) ,(length (rest thing))))
             ((eq (first thing) 'list)
              (length (rest thing)))
             ((eq (first thing) 'list*)
            `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
             (t
              form)))

;-)

>
>I think the right thing to do is to get the type system to do this
>right...

Yes

-Roger
From: Christophe Rhodes
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <sqsncpqnfr.fsf@cam.ac.uk>
·····@corman.net (Roger Corman) writes:

> On 11 Oct 2001 17:10:11 +0100, Christophe Rhodes <·····@cam.ac.uk> wrote:
> 
> >Raymond Toy <···@rtp.ericsson.se> writes:
> >
> >> >>>>> "Tim" == Tim Bradshaw <···@cley.com> writes:
> >> 
> >> Paul Foley sent me a compiler macro for length and when you use this
> >> on the following function, CMUCL produces pretty good results.
> >> 
> >> (define-compiler-macro length (&whole form thing)
> >>     (cond ((not (consp thing))
> >>            form)
> >>           ((eq (first thing) 'list)
> >>            (length (rest thing)))
> >>           ((eq (first thing) 'list*)
> >>            `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
> >>           (t
> >>            form)))
> >
> >Um, but, but, but ... I thought of this, but
> >
> >(length (list (setf *foo* 'bar)))
> >
> >?
> 
> Ah, if we didn't allow side effects compilers would be much simpler, wouldn't
> they?
> 
> [snip slightly less broken compiler macro ;-)]
>
> >I think the right thing to do is to get the type system to do this
> >right...
> 
> Yes

Though Paul Foley in personal mail provided a reasonable compiler
macro:

  (define-compiler-macro length (&whole form thing)
    (cond ((not (consp thing))
           form)
          ((eq (first thing) 'list)
           `(progn ,@(rest thing) ,(length (rest thing))))
          ((eq (first thing) 'list*)
           `(progn ,@(rest (butlast thing))
                   (+ ,(- (length thing) 2) (length ,(first (last thing))))))
          (t
           form)))

which is I believe entirely correct (apart from the caveat that length
is in the CL package and therefore it isn't allowed to provide a
user-level compiler macro yadda yadda yadda). The problem with this
approach is that it doesn't allow the compiler to generalize; if the
compiler is SS[*] about types, then it will be able to get not just
this but many other things right without further intervention.

Of course, it's quite hard to make a compiler SS...

Christophe

[*] Sufficiently Smart, of course
-- 
Jesus College, Cambridge, CB5 8BL                           +44 1223 510 299
http://www-jcsu.jesus.cam.ac.uk/~csr21/                  (defun pling-dollar 
(str schar arg) (first (last +))) (make-dispatch-macro-character #\! t)
(set-dispatch-macro-character #\! #\$ #'pling-dollar)
From: Hallvard B Furuseth
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <HBF.20011012nknb@bombur.uio.no>
Christophe Rhodes <·····@cam.ac.uk> writes:
>Raymond Toy <···@rtp.ericsson.se> writes:
> 
>> Paul Foley sent me a compiler macro for length and when you use this
>> on the following function, CMUCL produces pretty good results.
>> 
>> (define-compiler-macro length (&whole form thing)
>>     (cond ((not (consp thing))
>>            form)
>>           ((eq (first thing) 'list)
>>            (length (rest thing)))
>>           ((eq (first thing) 'list*)
>>            `(+ ,(- (length thing) 2) (length ,(first (last thing)))))
>>           (t
>>            form)))
> 
> Um, but, but, but ... I thought of this, but
> 
> (length (list (setf *foo* 'bar)))

(define-compiler-macro length (&whole form thing)
  (if (and (consp thing)
           (member (first thing) '(list list*)))
      `(progn ,@(rest thing)
	      ;; Copy the rest from Paul Foley's macro.
              ,(if (eq (first thing) 'list)
                   (length (rest thing))
                   `(+ ,(- (length thing) 2)
                       (length ,(first (last thing))))))
      form))

-- 
Hallvard
From: Marco Antoniotti
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <y6csncpasp5.fsf@octagon.mrl.nyu.edu>
Hi 

I find this thread very interesting.  I never used a compiler macro so
far, but I will definitively add them to the "reasons why CL is good
for you", next time somebody comes up asking a comparison between Lisp
and C*.

Cheers

-- 
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group        tel. +1 - 212 - 998 3488
719 Broadway 12th Floor                 fax  +1 - 212 - 995 4122
New York, NY 10003, USA                 http://bioinformatics.cat.nyu.edu
                    "Hello New York! We'll do what we can!"
                           Bill Murray in `Ghostbusters'.
From: Pekka P. Pirinen
Subject: Re: smart compiler (example in PAIP)
Date: 
Message-ID: <u3d4or8vd.fsf@globalgraphics.com>
Hallvard B Furuseth <············@usit.uio.no> writes:
> Christophe Rhodes <·····@cam.ac.uk> writes:
> > Um, but, but, but ... I thought of this, but
> > 
> > (length (list (setf *foo* 'bar)))
> 
> (define-compiler-macro length (&whole form thing)
>   (if (and (consp thing)
>            (member (first thing) '(list list*)))
>       `(progn ,@(rest thing)
> 	      ;; Copy the rest from Paul Foley's macro.
>               ,(if (eq (first thing) 'list)
>                    (length (rest thing))
>                    `(+ ,(- (length thing) 2)
>                        (length ,(first (last thing))))))
>       form))

but

(length (list* (incf a)))

You can fix it by handling the last arg to list* specially.

(define-compiler-macro length (&whole form thing)
  (if (consp thing)
      (case  (first thing)
        (list
          `(progn ,@(rest thing)
                  ,(length (rest thing))))
        (list*
          `(progn ,@(butlast (rest thing))
                  (+ ,(- (length thing) 2)
                     (length ,(first (last thing))))))
        (otherwise form))
      form))
-- 
Pekka P. Pirinen
"You're always going to build a prototype -- the only question
is whether you're going to deliver it to the customer."
  - Bob Martin, Bellcore