From: K.S.Sreeram
Subject: why is lisp fast?
Date: 
Message-ID: <1155672348.117574.217240@m79g2000cwm.googlegroups.com>
Most lispers claim that lisp speed is close to that of C/C++. See this
page for instance:
http://www.norvig.com/python-lisp.html

Is lisp fast *only* if you add type annotations? Or are there any
language features which make it inherenly easier to generate effecient
native code? Take python for instance, there have been attempts to
write native code compilers for it, but none of them have worked well.
What language design features make lisp more suitable for compilers?

[sreeram;]

From: Tim Bradshaw
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155682335.311479.195790@m79g2000cwm.googlegroups.com>
K.S.Sreeram wrote:

>
> Is lisp fast *only* if you add type annotations? Or are there any
> language features which make it inherenly easier to generate effecient
> native code? Take python for instance, there have been attempts to
> write native code compilers for it, but none of them have worked well.
> What language design features make lisp more suitable for compilers?

It's a couple of years since I wrote any Python so take this with a
pinch of salt, but I think `not making catastrophically bad design
decisions' is probably up there.  In particular I think Python at least
exposed way too much of its implementation, and that implementation was
not particularly amenable to optimization.  CL avoided that mistake
although it's flirted with it with things like the CLOS MOP (which I
think mostly avoids the pitfalls, in fact, although it was never clear
to me).

CL also made some good decisions about types & classes - everything is
an object, but built-in classes (like numbers, conses, arrays) have
restrictions that allow for good implementation.  Compare with the `you
can subclass floats' that some languages do, or the alternative `floats
are not objects' that, say, Java does.

--tim
From: K.S.Sreeram
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155719518.313904.110720@p79g2000cwp.googlegroups.com>
Tim Bradshaw wrote:
> K.S.Sreeram wrote:
>
> >
> > Is lisp fast *only* if you add type annotations? Or are there any
> > language features which make it inherenly easier to generate effecient
> > native code? Take python for instance, there have been attempts to
> > write native code compilers for it, but none of them have worked well.
> > What language design features make lisp more suitable for compilers?
>
> CL also made some good decisions about types & classes - everything is
> an object, but built-in classes (like numbers, conses, arrays) have
> restrictions that allow for good implementation.  Compare with the `you
> can subclass floats' that some languages do, or the alternative `floats
> are not objects' that, say, Java does.

Take a simple expression like (+ a b). Every symbol involved here has
to be looked up from the environment, and then the '+' function has to
be called.

Here is the rough list of steps that need to be performed at runtime:

1) Lookup '+' from the environment, (returns a function)
2) Lookup 'a' from the environment  (return a number)
3) Lookup 'b' from the environment  (returns another number)
4) Call the function '+' and return the result

An equivalent expression in C 'a + b', will require the following
steps:
1) mov eax, [a]   (load value from address-of-a into accumulator)
2) add eax, [b]   (add value from address-of-b to accumulator)
3) return eax

If these were the steps required at runtime.. how can lisp *EVER* have
speed that is comparable to C??? It looks like lisp will be around a
couple of orders of magnitude slower than C!

I guess i must be missing something about how the lisp runtime behaves.
Please enlighten me!

[sreeram;]
From: Rob Thorpe
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155720720.813948.214740@p79g2000cwp.googlegroups.com>
K.S.Sreeram wrote:
> Tim Bradshaw wrote:
> > K.S.Sreeram wrote:
> >
> > >
> > > Is lisp fast *only* if you add type annotations? Or are there any
> > > language features which make it inherenly easier to generate effecient
> > > native code? Take python for instance, there have been attempts to
> > > write native code compilers for it, but none of them have worked well.
> > > What language design features make lisp more suitable for compilers?
> >
> > CL also made some good decisions about types & classes - everything is
> > an object, but built-in classes (like numbers, conses, arrays) have
> > restrictions that allow for good implementation.  Compare with the `you
> > can subclass floats' that some languages do, or the alternative `floats
> > are not objects' that, say, Java does.
>
> Take a simple expression like (+ a b). Every symbol involved here has
> to be looked up from the environment, and then the '+' function has to
> be called.
>
> Here is the rough list of steps that need to be performed at runtime:
>
> 1) Lookup '+' from the environment, (returns a function)
> 2) Lookup 'a' from the environment  (return a number)
> 3) Lookup 'b' from the environment  (returns another number)
> 4) Call the function '+' and return the result
>
> An equivalent expression in C 'a + b', will require the following
> steps:
> 1) mov eax, [a]   (load value from address-of-a into accumulator)
> 2) add eax, [b]   (add value from address-of-b to accumulator)
> 3) return eax
>
> If these were the steps required at runtime.. how can lisp *EVER* have
> speed that is comparable to C??? It looks like lisp will be around a
> couple of orders of magnitude slower than C!
>
> I guess i must be missing something about how the lisp runtime behaves.
> Please enlighten me!

In many cases most of the work can be removed.

'+' doesn't need to be looked up from the environment, it's is just a
function call.  Normally a function call the can take numbers of any
kind, floating point, bignums etc.

If a and b are defined in a local 'let' binding then the compiler knows
about them, they need not be looked up.  But, if a and b are defvars
then they do need looking up.

If a and b are only used as numbers the compiler can find this out by
analysing the 'let' block they are defined in. Also, if a and b are
used only as fixnums the compiler can sometimes find this out too.  The
programmer could also specify the type explicitly.

Given that a and b are fixnums then the compiler knows that it need not
call the function '+' it can just insert the relevant machine code.  If
these conditions are met then it can emit the same machine code as a C
compiler.

In fact, given the above it may be able to do slightly better.  In C if
there is a pointer to a or b then those values can't be assigned to a
register, they must be updated in memory.  Since there are no free
pointers in lisp a and b could be assigned to registers, resulting in
just something like "add eax, edx".

In many practical situations the conditions aren't met, only some are.
So the result is less than ideal, but normally still fairly good.
From: Tim Bradshaw
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155724628.816031.37610@m73g2000cwd.googlegroups.com>
K.S.Sreeram wrote:

>
> Take a simple expression like (+ a b). Every symbol involved here has
> to be looked up from the environment, and then the '+' function has to
> be called.
>
> Here is the rough list of steps that need to be performed at runtime:
>
> 1) Lookup '+' from the environment, (returns a function)
> 2) Lookup 'a' from the environment  (return a number)
> 3) Lookup 'b' from the environment  (returns another number)
> 4) Call the function '+' and return the result

Almost none of those need to happen in compiled code.  To give a more
realistic example (really: to be clear about the binding so no one says
`poh yes but A and B might be special):

(let ((a 1) (b 2))
  ... code that manipulates A and B perhaps
 (+ a b))

Here: A and B are completely known-about at compile time: the very most
that has to be done is that references to where they sit on the stack
need to be generated.  + (assuming + is CL:+) is even better: this is a
known function which can never be altered.  So the system is free to
either simply directly call the known function or more likely inline
the code.  It may even know more about A and B - either it's been told
or it can infer their types, in which case it can probably generate a
direct add instruction (with some overflow checking).

Of course there are cases where this is *not* the case (for instance A
and B are special variables, or the function is something which might
get redefined etc), but they are not the common case.

--tim
From: Pascal Bourguignon
Subject: Re: why is lisp fast?
Date: 
Message-ID: <8764gt9e4h.fsf@thalassa.informatimago.com>
"K.S.Sreeram" <·········@gmail.com> writes:

> Tim Bradshaw wrote:
>> K.S.Sreeram wrote:
>>
>> >
>> > Is lisp fast *only* if you add type annotations? Or are there any
>> > language features which make it inherenly easier to generate effecient
>> > native code? Take python for instance, there have been attempts to
>> > write native code compilers for it, but none of them have worked well.
>> > What language design features make lisp more suitable for compilers?
>>
>> CL also made some good decisions about types & classes - everything is
>> an object, but built-in classes (like numbers, conses, arrays) have
>> restrictions that allow for good implementation.  Compare with the `you
>> can subclass floats' that some languages do, or the alternative `floats
>> are not objects' that, say, Java does.
>
> Take a simple expression like (+ a b). Every symbol involved here has
> to be looked up from the environment, and then the '+' function has to
> be called.
>
> Here is the rough list of steps that need to be performed at runtime:
>
> 1) Lookup '+' from the environment, (returns a function)
> 2) Lookup 'a' from the environment  (return a number)
> 3) Lookup 'b' from the environment  (returns another number)
> 4) Call the function '+' and return the result

How wrong you are!


* (disassemble (compile (defun f (a b) (the fixnum (+ (the fixnum a) (the fixnum b))))))
STYLE-WARNING: redefining F in DEFUN

; 0AF3ED56:       01FA             ADD EDX, EDI               ; no-arg-parsing entry point
;       58:       8D65F8           LEA ESP, [EBP-8]
;       5B:       F8               CLC
;       5C:       8B6DFC           MOV EBP, [EBP-4]
;       5F:       C20400           RET 4
;       62:       90               NOP
;       63:       90               NOP
;       64:       90               NOP
;       65:       90               NOP
;       66:       90               NOP
;       67:       90               NOP
; 
NIL
* 

> An equivalent expression in C 'a + b', will require the following
> steps:
> 1) mov eax, [a]   (load value from address-of-a into accumulator)
> 2) add eax, [b]   (add value from address-of-b to accumulator)
> 3) return eax

sbcl generates better code because it's able to pass arguments in
registers which C cannot do.


> If these were the steps required at runtime.. how can lisp *EVER* have
> speed that is comparable to C??? 

Who said they were required at runtime?


> It looks like lisp will be around a
> couple of orders of magnitude slower than C!
>
> I guess i must be missing something about how the lisp runtime behaves.
> Please enlighten me!

Basically, the difference is in the type system.


Imagine you'd have a C compiler able to generate code from such a program:

     fact(n){
       if(n<=1){ return(1); }
       else{ return(n*fact(n-1)); }

that is, no type declaration.  First, this C compiler would have to add types:

     typedef struct object {
         int tag;
         union {
            char   c;
            short  s;
            long   l;
            float  f;
            double d;
            char*  string;
         } data;
     } object;
            
            
     object fact(object n){
        switch(n.tag){
        case 0: if(n.data.c<=1){goto then;}else{goto else;}
        case 1: if(n.data.s<=1){goto then;}else{goto else;}
        case 2: if(n.data.l<=1){goto then;}else{goto else;}
        case 3: if(n.data.f<=1){goto then;}else{goto else;}
        case 4: if(n.data.d<=1){goto then;}else{goto else;}
        case 5: error("Cannot compare strings");
        default: error("Invalid object type");
        }
      then:
        return(1);
      else:
        switch(n.tag){
        case 0: return(object(0,n.data.c*fact(object(0,n.data.c-1))));
        case 1: return(object(1,n.data.s*fact(object(1,n.data.s-1))));
        case 2: return(object(2,n.data.l*fact(object(2,n.data.l-1))));
        case 3: return(object(3,n.data.f*fact(object(3,n.data.f-1e0))));
        case 4: return(object(4,n.data.d*fact(object(4,n.data.d-1d0))));
        case 5: error("Cannot multiply strings");
        default: error("Invalid object type");
        }}

Note that the * generated in the case 0 is not the same as the *
generated in the other cases by the C compiler.  In case 0, it can by
a byte*byte->short multiply. In case 4, it's a double floating point
multiplicate.


Well, in Lisp it's the same.
If you write:

   (defun fact (n) 
     (declare (fixnum n))
     (if (<= n 1)
         1
        (the fixnum (* n (fact (- n 1))))))

you get the same (buggy) code as in C with types, and if you write:

   (defun fact (n) 
     (if (<= n 1)
         1
         (* n (fact (- n 1)))))

you get the correct code, which contrarily to C is able to give
correct results for more than 13 values, and both for floating point
arguments or integers, even if it's slower because it has to make some
run-time type checking and polymorphic operations.



And it can even produce symbolic results:

   (shadow '(*))
   (defun * (a &rest b) `(* ,a ,@b))
   (defun fact (n) 
     (if (<= n 1)
         1
         (* n (fact (- n 1)))))
   (fact 10) 
   --> (* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 1)))))))))

Try to do that in C!


-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.
From: ············@gmail.com
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155724335.685355.155790@75g2000cwc.googlegroups.com>
Though C might not do this well, C++ with template can overcome such
weakness. Template is really good in do static polymorphism.
From: ···············@yahoo.com
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155735773.085812.252790@75g2000cwc.googlegroups.com>
Here's another version (Allegro 7.0 on Windows).

(defun my-add (a b)
  (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
  (+ a b))
MY-ADD

(compile 'my-add)
MY-ADD
NIL
NIL

(disassemble 'my-add)
;; disassembly of #<Function MY-ADD>
;; formals: A B

;; code start: #x2063f794:
   0: 03 c2      addl	eax,edx
   2: f8          clc
   3: 8b 75 fc  movl	esi,[ebp-4]
   6: c3          ret
   7: 90          nop

As Pascal says, this code leads to bugs (in C or Lisp) unless you're
*sure* the addition won't overflow.
From: ············@gmail.com
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155741966.087379.205950@i3g2000cwc.googlegroups.com>
In Corman Lisp it's like this

?(disassemble 'my-add)
;Disassembling from address #xB73F98:
;#x0: 55             push    ebp
;#x1: 8BEC           mov     ebp,esp
;#x3: 57             push    edi
;#x4: FF750C         push    dword ptr [ebp+0000Ch]
;#x7: 8B4508         mov     eax,[ebp+00008h]
;#xA: 5A             pop     edx
;#xB: 03C2           add     eax,edx
;#xD: 7108           jno     0017
;#xF: 2BC2           sub     eax,edx
;#x11: FF9604180000   call    near dword ptr [esi+000001804h]      ;
Call COMMON
-LISP::%PLUS_EAX_EDX
;#x17: B901000000     mov     ecx,0001
;#x1C: 8BE5           mov     esp,ebp
;#x1E: 5D             pop     ebp
;#x1F: C3             ret
NIL
From: John Thingstad
Subject: Re: why is lisp fast?
Date: 
Message-ID: <op.tedqnj0rpqzri1@pandora.upc.no>
On Wed, 16 Aug 2006 15:42:53 +0200, <···············@yahoo.com> wrote:

> Here's another version (Allegro 7.0 on Windows).
>
> (defun my-add (a b)
>   (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
>   (+ a b))
> MY-ADD
>
> (compile 'my-add)
> MY-ADD
> NIL
> NIL
>
> (disassemble 'my-add)
> ;; disassembly of #<Function MY-ADD>
> ;; formals: A B
>
> ;; code start: #x2063f794:
>    0: 03 c2      addl	eax,edx
>    2: f8          clc
>    3: 8b 75 fc  movl	esi,[ebp-4]
>    6: c3          ret
>    7: 90          nop
>
> As Pascal says, this code leads to bugs (in C or Lisp) unless you're
> *sure* the addition won't overflow.
>

ODD. It cost's nothing to check for overflow. (on intel processors - the  
into instruction fires interrupt 0x04)
In Lispworks you need to set (fixnum-safety 0) to disable interupt on  
overflow.
Normally I never set it lower than 1 unless I want to emulate C behaviour.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0ac63tl6d.fsf@franz.com>
"John Thingstad" <··············@chello.no> writes:

> On Wed, 16 Aug 2006 15:42:53 +0200, <···············@yahoo.com> wrote:
>
>> Here's another version (Allegro 7.0 on Windows).
>>
>> (defun my-add (a b)
>>   (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
>>   (+ a b))
>> MY-ADD
>>
>> (compile 'my-add)
>> MY-ADD
>> NIL
>> NIL
>>
>> (disassemble 'my-add)
>> ;; disassembly of #<Function MY-ADD>
>> ;; formals: A B
>>
>> ;; code start: #x2063f794:
>>    0: 03 c2      addl	eax,edx
>>    2: f8          clc
>>    3: 8b 75 fc  movl	esi,[ebp-4]
>>    6: c3          ret
>>    7: 90          nop
>>
>> As Pascal says, this code leads to bugs (in C or Lisp) unless you're
>> *sure* the addition won't overflow.
>>
>
> ODD. It cost's nothing to check for overflow. (on intel processors -
> the  into instruction fires interrupt 0x04)

It costs the into instruction, which in competitions with C can cause
as much as a 20% performance impact (consider a tight loop, with
increments on integers that are never expected to overflow into
bignums - and if they were to overflow, one could never use a simple
add instruction to add two bignums together anyway, so in more generic
code there would have to be an additional test for fixnum-ness.  Now,
some of these kinds of numerial limits can be determined by the
compiler using type inferrence, but there are times (especially in
competition with other languages, where accuracy is not the highest
goal) where the "modulo 32" arithmetic cannot be easily emulated
without declaring the (Lisp) code to the hilt, and it is simply easier
to say to the compiler "I want this compiled similar to how C compiles
it".

The behavior of Allegro CL at speed=3/safety=0 is well-documented, and
we further always recommend that safety never be set to 0 unless the
programmer exercises great care.

> In Lispworks you need to set (fixnum-safety 0) to disable interupt on
> overflow.
> Normally I never set it lower than 1 unless I want to emulate C behaviour.

Yes, another safety issue.  In general, if you want CL to be safe,
don't ask it to be unsafe.

-- 
Duane Rettig    ·····@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   
From: Christophe Rhodes
Subject: Re: why is lisp fast?
Date: 
Message-ID: <sqac63xzes.fsf@cam.ac.uk>
···············@yahoo.com writes:

> Here's another version (Allegro 7.0 on Windows).
>
> (defun my-add (a b)
>   (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
>   (+ a b))
> MY-ADD
>
> As Pascal says, this code leads to bugs (in C or Lisp) unless you're
> *sure* the addition won't overflow.

No, your code should not lead to bugs in Lisp if the addition would
overflow the fixnum range, because you have not declared anything
about the return type of the addition.  

(MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
valid call to MY-ADD given the above code, and it should return the
integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
conformance bug.

> (disassemble 'my-add)
> ;; disassembly of #<Function MY-ADD>
> ;; formals: A B
>
> ;; code start: #x2063f794:
>    0: 03 c2      addl	eax,edx
>    2: f8          clc
>    3: 8b 75 fc  movl	esi,[ebp-4]
>    6: c3          ret
>    7: 90          nop

I consider it unfortunate that Allegro CL misbehaves in this way on
code that would otherwise demonstrate the safety advantages of Lisp.

Christophe
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o064grtixw.fsf@franz.com>
Christophe Rhodes <·····@cam.ac.uk> writes:

> ···············@yahoo.com writes:
>
>> Here's another version (Allegro 7.0 on Windows).
>>
>> (defun my-add (a b)
>>   (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
>>   (+ a b))
>> MY-ADD
>>
>> As Pascal says, this code leads to bugs (in C or Lisp) unless you're
>> *sure* the addition won't overflow.
>
> No, your code should not lead to bugs in Lisp if the addition would
> overflow the fixnum range, because you have not declared anything
> about the return type of the addition.  

In fact, he has, by virtue of the speed=3/safety=0 declaration, and
how it is implemented in Allegro CL:
http://www.franz.com/support/documentation/8.0/doc/variables/compiler/declared-fixnums-remain-fixnums-switch.htm


> (MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
> valid call to MY-ADD given the above code, and it should return the
> integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
> conformance bug.

This is true.  Every CL that wants to compete with C must have such a
non-conformance.  Ours comes (effectively and indirectly) with the
declaration of optimization settings of speed = 3 and safety = 0.

Now, is that a bad thing?  Can any CL impementation be completely
conforming?  No; a run through Paul Dietz's conformance test suite
gives the understanding that no implementation is completely
conformant, even though all of them do "purport to conform".  In fact,
Dietz has actually removed tests in cases where the standard was shown
to be inconsistent with itself.  He has logged such inconsistencies
and needs for clarification here:

http://www.cliki.net/Proposed%20ANSI%20Revisions%20and%20Clarifications

So no CL implementation can truly be conformant.
However, in the _spirit_ of conformance, section 1.5.1.5 of the spec
requires implementations that purport to conform to list their
exceptions to conformance.  Allegro CL does so here, and the issue of
fixnums remaining fixnums after additions or subrtractions is included:

http://www.franz.com/support/documentation/8.0/doc/implementation.htm#compliance-1
(see point #2 under the second minor heading "Other non-conformances")
as well as some warning text for the switch itself, including
instructions on how to disable it:
http://www.franz.com/support/documentation/8.0/doc/variables/compiler/declared-fixnums-remain-fixnums-switch.htm

>> (disassemble 'my-add)
>> ;; disassembly of #<Function MY-ADD>
>> ;; formals: A B
>>
>> ;; code start: #x2063f794:
>>    0: 03 c2      addl	eax,edx
>>    2: f8          clc
>>    3: 8b 75 fc  movl	esi,[ebp-4]
>>    6: c3          ret
>>    7: 90          nop
>
> I consider it unfortunate that Allegro CL misbehaves in this way on
> code that would otherwise demonstrate the safety advantages of Lisp.

Allegro CL is behaving in exactly the way it is documented to behave.
Also, a choice it given to users as to how they will deal with the
issue of non-compliance - they can either avoid the speed=3/safety=0
combination, or they can set the value of
comp::declared-fixnums-remain-fixnums-switch to nil.  This option has
been present for at least 18 years, and I would guess that out of all
of our customers, at most one or two have ever set the switch to nil
globally, and perhaps a few more have set the switch to nil in lexical
scope, using compiler-let.

-- 
Duane Rettig    ·····@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   
From: Pierre THIERRY
Subject: Re: why is lisp fast?
Date: 
Message-ID: <pan.2006.08.17.16.55.36.874111@levallois.eu.org>
Le Thu, 17 Aug 2006 09:39:55 -0700, Duane Rettig a écrit :
> Allegro CL is behaving in exactly the way it is documented to behave.
> Also, a choice it given to users as to how they will deal with the
> issue of non-compliance - they can either avoid the speed=3/safety=0
> combination, or they can set the value of
> comp::declared-fixnums-remain-fixnums-switch to nil.

Why not use an implementation-specific declaration instead?

Curiously,
Nowhere man
-- 
···········@levallois.eu.org
OpenPGP 0xD9D50D8A
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o01wrftebz.fsf@franz.com>
Pierre THIERRY <···········@levallois.eu.org> writes:

> Le Thu, 17 Aug 2006 09:39:55 -0700, Duane Rettig a écrit :
>> Allegro CL is behaving in exactly the way it is documented to behave.
>> Also, a choice it given to users as to how they will deal with the
>> issue of non-compliance - they can either avoid the speed=3/safety=0
>> combination, or they can set the value of
>> comp::declared-fixnums-remain-fixnums-switch to nil.
>
> Why not use an implementation-specific declaration instead?
>
> Curiously,
> Nowhere man

See the glossary term for "conforming implementation":
http://www.franz.com/support/documentation/8.0/ansicl/glossary/c.htm#conformingimplementation

Note that it says "An implementation which has been extended may
still be a conforming implementation provided that no extension
interferes with the correct function of any conforming program."

So an implementation-specific declaration which causes compilation of
integer addition in such a way that produces a wrong answer violates
this requirement, and such an implementation is still not a conforming
implementation.

So why a switch rather than a declaration?  Well, let's be honest
here; what we're _really_ talking about is benchmarks and raw speed.
And for implementations which purport to conform but which also claim
high performance, say, within 20% of C or faster, such nonconformances
are necessary.  Benchmarking code tends to allow implementations some
global setup, but there are usually very few allowances made to
provide special implementation-dependent declarations within the code,
presumably to keep the benchmarks "pure".  If you look at various
instances of the "Gabriel" benchmarks, also known as the Stanford
benchmarks, you'll notice that there are literally hundreds of
versions out there, with varying levels of optimizations.  So which do
you use, in order to measure one Lisp against another, or to measure
CL implementations against purportedly equivalent code in another
language?  In practice, objective keepers of benchmarking code tend to
shy away from allowing implementation-specific declarations within the
major body of the benchmarking source, usually allowing instead
implementation-dependent initialization files where global switches
and declarations can be made (including setups for gcs, space
pre-allocation, etc).  So in reality, for benchmarks, any
implementation-specific declaration would have to be used in a global
manor anyway, which is no different use than a global switch like the
one we provide.

So what about situations where we're _not_ talking about just
benchmarking, and we truly want to get fixnum+fixnum => fixnum
calculations?  No problem, and no need to be non-conformant: instead
of saying (+ (the fixnum x) (the fixnum y)) under speed=3/safety=0
optimizations, simply say
  (the fixnum (+ (the fixnum x) (the fixnum y)))
under higher safety setting, and the calculation will not include the
overflow test, _because_ you have promised to the compiler that the
result will not overflow and if you break that promise, the code has
the right to do whatever it wants, including executing the hcf
instruction.  So in real situations, standard declarations can be made
in conforming and portable ways to ensure that such code is generated
as fast as possible, without resorting to non-conformance in order to
get the samee result.  Why use a non-conforming switch or a
non-conforming implementation-specific declaratin when a perfectly
fine standard declaration will work just as well?

-- 
Duane Rettig    ·····@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   
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0wt97rznu.fsf@franz.com>
Duane Rettig <·····@franz.com> writes:

> So an implementation-specific declaration which causes compilation of
> integer addition in such a way that produces a wrong answer violates
=============================================================^
> this requirement, and such an implementation is still not a conforming
> implementation.

I should add "from correct inputs"...

-- 
Duane Rettig    ·····@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   
From: Pierre THIERRY
Subject: Re: why is lisp fast?
Date: 
Message-ID: <pan.2006.08.17.19.57.35.344128@levallois.eu.org>
Le Thu, 17 Aug 2006 11:19:27 -0700, Duane Rettig a écrit :
> So an implementation-specific declaration which causes compilation of
> integer addition in such a way that produces a wrong answer violates
> this requirement, and such an implementation is still not a conforming
> implementation.

I think a missed the point: what is the difference between a switch and
a declaration in this matter?

Curiously,
Nowhere man
-- 
···········@levallois.eu.org
OpenPGP 0xD9D50D8A
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0odujrulb.fsf@franz.com>
Pierre THIERRY <···········@levallois.eu.org> writes:

> Le Thu, 17 Aug 2006 11:19:27 -0700, Duane Rettig a écrit :
>> So an implementation-specific declaration which causes compilation of
>> integer addition in such a way that produces a wrong answer violates
>> this requirement, and such an implementation is still not a conforming
>> implementation.
>
> I think a missed the point: what is the difference between a switch and
> a declaration in this matter?

You missed nothing.  As far as I am concerned, there is no difference.

-- 
Duane Rettig    ·····@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   
From: Christophe Rhodes
Subject: Re: why is lisp fast?
Date: 
Message-ID: <sqk657urm6.fsf@cam.ac.uk>
Duane Rettig <·····@franz.com> writes:

> Christophe Rhodes <·····@cam.ac.uk> writes:
>
>> ···············@yahoo.com writes:
>>
>>> Here's another version (Allegro 7.0 on Windows).
>>>
>>> (defun my-add (a b)
>>>   (declare (type fixnum a b) (optimize speed (safety 0) (debug 0)))
>>>   (+ a b))
>>> MY-ADD
>>>
>>> As Pascal says, this code leads to bugs (in C or Lisp) unless you're
>>> *sure* the addition won't overflow.
>>
>> No, your code should not lead to bugs in Lisp if the addition would
>> overflow the fixnum range, because you have not declared anything
>> about the return type of the addition.  
>
> In fact, he has, by virtue of the speed=3/safety=0 declaration, and
> how it is implemented in Allegro CL:
> http://www.franz.com/support/documentation/8.0/doc/variables/compiler/declared-fixnums-remain-fixnums-switch.htm

I grant that Franz has documented this deviation from the standard,
and that this follows the spirit of the requirement on implementations
which purport to conform with exceptions.

>> (MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
>> valid call to MY-ADD given the above code, and it should return the
>> integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
>> conformance bug.
>
> This is true.  Every CL that wants to compete with C must have such a
> non-conformance.  Ours comes (effectively and indirectly) with the
> declaration of optimization settings of speed = 3 and safety = 0.

I do not accept this, however.  Why do you equate "wanting to compete
with C" with "must deviate from the standard in this respect"?  In
particular, why do you reject the possibility of declaring the result
of the addition as a fixnum if the user wishes to inform the system
that there will be no overflow, and the definition of a new operator
if the user wishes to perform signed arithmetic with the natural word
size of the platform?

(For onlookers -- since I'm sure Duane knows this -- the C standard
makes no guarantees about the behaviour of signed arithmetic overflow,
so competing with C with respect to overflow on signed integers is a
pretty nebulous concept.  I'll happily read that as "competing with
common C implementations of addition", though.)

> Now, is that a bad thing?  Can any CL impementation be completely
> conforming?  

These two questions are different.  My view is that Allegro CL's
deviation from the standard in this case is a bad thing, and that no
CL implementation can be completely conforming.  (For the sake of
clarity, I do not think that all deviations from the standard are
created equal; as an example, I believe that there is far less value
in, say, arrays which cannot hold anything than there is in being able
to add two numbers together reliably.)

> No; a run through Paul Dietz's conformance test suite
> gives the understanding that no implementation is completely
> conformant, even though all of them do "purport to conform".  In fact,
> Dietz has actually removed tests in cases where the standard was shown
> to be inconsistent with itself.  He has logged such inconsistencies
> and needs for clarification here:
>
> http://www.cliki.net/Proposed%20ANSI%20Revisions%20and%20Clarifications

You may not be aware (since the revision history of that page is
unfortunately not terribly accessible) that other major contributors
to that page and the issues linked from it include various
implementors, particularly Bruno Haible, working both in conjunction
with Paul Dietz and his test suite and independently of it.

> So no CL implementation can truly be conformant.

Granted.  (Leaving aside the usual PROG2 typo, the requirement that
array upgrading be precise involves deciding undecideable problems :-)

>>> (disassemble 'my-add)
>>> ;; disassembly of #<Function MY-ADD>
>>> ;; formals: A B
>>>
>>> ;; code start: #x2063f794:
>>>    0: 03 c2      addl	eax,edx
>>>    2: f8          clc
>>>    3: 8b 75 fc  movl	esi,[ebp-4]
>>>    6: c3          ret
>>>    7: 90          nop
>>
>> I consider it unfortunate that Allegro CL misbehaves in this way on
>> code that would otherwise demonstrate the safety advantages of Lisp.
>
> Allegro CL is behaving in exactly the way it is documented to behave.

I apologize for my phrasing, which in the word "misbehaves" was with
reference to standard behaviour and was not intended to imply that
this deviation was accidental nor that it was not useful in some
circumstances.  I consider it unfortunate that Allegro CL deviates
from the standard in this way on code that would otherwise demonstrate
the safety advantages of Lisp; I furthermore believe that there are
better ways of expressing the aim of performing hardware arithmetic on
lisp objects.

Christophe
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0sljvrupo.fsf@franz.com>
I'm not sure if you read my post in another location on this thread
before you sent this one.  I will assume not.

Also, I am getting the sense from your attention to alternatives, that
the main thrust of your post is contained  in these two places, first
in the next-to-last paragraph here:

>>> (MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
>>> valid call to MY-ADD given the above code, and it should return the
>>> integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
>>> conformance bug.
>>
>> This is true.  Every CL that wants to compete with C must have such a
>> non-conformance.  Ours comes (effectively and indirectly) with the
>> declaration of optimization settings of speed = 3 and safety = 0.
>
> I do not accept this, however.  Why do you equate "wanting to compete
> with C" with "must deviate from the standard in this respect"?  In
> particular, why do you reject the possibility of declaring the result
> of the addition as a fixnum if the user wishes to inform the system
> that there will be no overflow, and the definition of a new operator
> if the user wishes to perform signed arithmetic with the natural word
> size of the platform?

[and, for the record, I don't know how much Ansi C specifies about its
mudular arithmetic, so I can agree to your "comon C implementations"
modification, below]

> (For onlookers -- since I'm sure Duane knows this -- the C standard
> makes no guarantees about the behaviour of signed arithmetic overflow,
> so competing with C with respect to overflow on signed integers is a
> pretty nebulous concept.  I'll happily read that as "competing with
> common C implementations of addition", though.)

And secondarily, the last sentence of your paragraph, below:

>> Allegro CL is behaving in exactly the way it is documented to behave.
>
> I apologize for my phrasing, which in the word "misbehaves" was with
> reference to standard behaviour and was not intended to imply that
> this deviation was accidental nor that it was not useful in some
> circumstances.  I consider it unfortunate that Allegro CL deviates
> from the standard in this way on code that would otherwise demonstrate
> the safety advantages of Lisp; I furthermore believe that there are
> better ways of expressing the aim of performing hardware arithmetic on
> lisp objects.

If this is the case, let me summarize the discussion with two
questions:

1. Given two operations at some nondescript but agreed-upon settings
for speed and safety (you're welcome to choose), and given some
implementation-defined declaration (let's call it
fixnums-remain-fixnums, for argument), are the two functions here
semantically equivalent?

(defun foo (x y)
  (declare (optimize speed) (fixnum x y))
  (declare (fixnums-remain-fixnum t))
  (+ x y))

(defun bar (x y)
  (declare (optimize speed) (fixnum x y))
  (the fixnum (+ x y)))

2. When you say 

> better ways of expressing the aim of performing hardware arithmetic on
> lisp objects.

are you suggesting continuing to use the + or - operators?

-- 
Duane Rettig    ·····@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   
From: Christophe Rhodes
Subject: Re: why is lisp fast?
Date: 
Message-ID: <sqejvfum0w.fsf@cam.ac.uk>
Duane Rettig <·····@franz.com> writes:

> I'm not sure if you read my post in another location on this thread
> before you sent this one.  I will assume not.

I hadn't, no.

> Also, I am getting the sense from your attention to alternatives, that
> the main thrust of your post is contained  in these two places, first
> in the next-to-last paragraph here:

Right.  I'm not at all against the idea that Lisp can perform hardware
arithmetic; I do think that introducing incompatibilities with the
standard is unnecessary.

>>>> (MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
>>>> valid call to MY-ADD given the above code, and it should return the
>>>> integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
>>>> conformance bug.
>>>
>>> This is true.  Every CL that wants to compete with C must have such a
>>> non-conformance.  Ours comes (effectively and indirectly) with the
>>> declaration of optimization settings of speed = 3 and safety = 0.
>>
>> I do not accept this, however.  Why do you equate "wanting to compete
>> with C" with "must deviate from the standard in this respect"?  In
>> particular, why do you reject the possibility of declaring the result
>> of the addition as a fixnum if the user wishes to inform the system
>> that there will be no overflow, and the definition of a new operator
>> if the user wishes to perform signed arithmetic with the natural word
>> size of the platform?
>
> [and, for the record, I don't know how much Ansi C specifies about its
> mudular arithmetic, so I can agree to your "comon C implementations"
> modification, below]

Fair enough.  My understanding, though it's only second-hand -- I
wouldn't claim to be a C language lawyer by any means -- is that for
unsigned overflow C specifies wrap-around to zero, while for signed
overflow the behaviour is unspecified in ANSI C.

>> I furthermore believe that there are better ways of expressing the
>> aim of performing hardware arithmetic on lisp objects.
>
> If this is the case, let me summarize the discussion with two
> questions:
>
> 1. Given two operations at some nondescript but agreed-upon settings
> for speed and safety (you're welcome to choose), and given some
> implementation-defined declaration (let's call it
> fixnums-remain-fixnums, for argument), are the two functions here
> semantically equivalent?
>
> (defun foo (x y)
>   (declare (optimize speed) (fixnum x y))
>   (declare (fixnums-remain-fixnum t))
>   (+ x y))
>
> (defun bar (x y)
>   (declare (optimize speed) (fixnum x y))
>   (the fixnum (+ x y)))

I think they could be made semantically equivalent, given reasonable
implementation choices and documentation.  After my previous post, I
read your message where you said that a new declaration would be
similarly non-conforming, and (if that is indeed what you meant; I
realise I'm paraphrasing) I think I disagree; I think the intent of
the interaction of language extensions and conformance is that if the
extension is not used (lexically or dynamically) by any given piece of
code, its behaviour should be that of a program run in an
implementation without the extension.

In the specific case of an implementation-defined declaration, the
CLHS explicitly says that

  An implementation is free to support other (implementation-defined)
  declaration identifiers as well.

and since it's unlikely that an implementation-defined declaration
that the standardizers were referring to would have no effect, I think
it's reasonable to accept that implementation-defined declarations
could change the behaviour of programs that the declarations apply to.

So, I would say that an implementation could document the
FIXNUMS-REMAIN-FIXNUM declaration, make it off by default, and then
any code which is compiled and run in the default environment would
behave as standardized; code using it could have its meaning changed
in the form currently in Allegro CL under high speed and low safety,
and the net effect would be as before. 

In the second case, it is mandated that the return value be the
mathematically correct one if the sum is indeed a fixnum.  If it
isn't, "the consequences are undefined", so it would not be strictly
conforming code.  However, much as in the first version, an
implementation could document the behaviour of code which is not
conforming, as a language extension; one useful extension in this case
might be to return the "logical" wrapped-around fixnum.

(I'm not sure I'm answering the question under your question; it's
possible I've missed or misread something either in your question or
in the standard, because I don't think this is terribly controversial.
Maybe if it is, someone else will chip in and tell me so.)

> 2. When you say 
>
>> better ways of expressing the aim of performing hardware arithmetic on
>> lisp objects.
>
> are you suggesting continuing to use the + or - operators?

Let me preface my answer by observing that there seems to me to be a
practical difference as well as an implementation difference between
signed and unsigned arithmetic.  The implementation difference is that
a sign-bit introduces additional complexity in implementing any scheme
for bitwise operators.  So I'm going to start by talking about
unsigned arithmetic, and I hope that when I tie it back to signed
arithmetic the extension (if you pardon the pun) will be at least
plausible.

So, the practical difference for lisp programmers -- not lisp
implementors -- between hardware unsigned and signed arithmetic is
that there is a natural way for the programmer to request such
arithmetic in conforming Common Lisp, and it involves no declarations
at all.

In

  (defun baz (x y)
    (declare (type (unsigned-byte 32) x y))
    (logand #xfffffff (+ x y)))

the programmer specifies a computation.  This happens to be a
computation that can be efficiently carried out on 32-bit (and some
64-bit) processors, but the actual hardware operations carried out
can, to a first approximation, be ignored by the programmer; it is
only when this function (or a more complicated variant, more likely)
becomes a bottleneck that the quality-of-implementation of the
Sufficiently Smart Compiler comes into play.

I claim that there are several advantages of using this style of
request for efficiency over a combination of optimization
declarations.  Not least is the fact that the meaning of the program
is lexically visible; it no longer depends on some
implementation-defined behaviour.  Additionally, it is more naturally
composable, not limited to addition and subtraction;

  (defun quux (x y)
    (declare (type (unsigned-byte 32) x y))
    (logand #xffffffff (+ x (* y (lognot (- x y))))))

can be compiled into the obvious sequence of hardware instructions.
So, yes, we can continue to use our beloved + and - operators, as well
as *, /, ash and logfoo.

Now, how do we extend this to signed arithmetic?  I'm afraid I'm going
to wave my hands a little bit here, and suggest that it's either easy
or impossible :-) Let's posit an operator such as EX:SLOGAND ("Signed
LOGAND"), but I'm not going to make it as general as LOGAND: it's only
allowed to take values that are (2^k)-1 for positive k.  EX:SLOGAND
interprets its field as a twos-complement integer with the high bit
treated as a sign bit.  Then I can write a fixnum add by saying

  (defun frob (x y)
    (declare (type fixnum x y))
    (ex:slogand (1- (exp (1+ (integer-length most-negative-fixnum))))
                (+ x y)))

and, again, compiling this to hardware arithmetic then becomes a
quality of implementation issue.

Does this answer your second question?  

Although some of the details are different, this general thrust has
been implemented in current Lisp systems and used for efficient
implementation of cryptographic and compression algorithms, so it's
not quite empty theorizing.

Christophe
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0k656s84r.fsf@franz.com>
Christophe Rhodes <·····@cam.ac.uk> writes:

>> 1. Given two operations at some nondescript but agreed-upon settings
>> for speed and safety (you're welcome to choose), and given some
>> implementation-defined declaration (let's call it
>> fixnums-remain-fixnums, for argument), are the two functions here
>> semantically equivalent?
>>
>> (defun foo (x y)
>>   (declare (optimize speed) (fixnum x y))
>>   (declare (fixnums-remain-fixnum t))
>>   (+ x y))
>>
>> (defun bar (x y)
>>   (declare (optimize speed) (fixnum x y))
>>   (the fixnum (+ x y)))
>
> I think they could be made semantically equivalent, given reasonable
> implementation choices and documentation.  After my previous post, I
> read your message where you said that a new declaration would be
> similarly non-conforming, and (if that is indeed what you meant; I

Yes, this is what I meant.

> realise I'm paraphrasing) I think I disagree; I think the intent of
> the interaction of language extensions and conformance is that if the
> extension is not used (lexically or dynamically) by any given piece of
> code, its behaviour should be that of a program run in an
> implementation without the extension.
>
> In the specific case of an implementation-defined declaration, the
> CLHS explicitly says that
>
>   An implementation is free to support other (implementation-defined)
>   declaration identifiers as well.
>
> and since it's unlikely that an implementation-defined declaration
> that the standardizers were referring to would have no effect, I think
> it's reasonable to accept that implementation-defined declarations
> could change the behaviour of programs that the declarations apply to.

However, consider 1.6:

http://www.franz.com/support/documentation/8.0/ansicl/section/languag0.htm

The first paragraph cites the applicability of the extension, and uses
words "specifies as ... extendable by the implementation".  So this
section applies here, since we're talking about new declarations.
Note, though, that the third paragraph says "An implementation can
have extensions, provided they do not alter the behavior of conforming
code ...".  A declaration that alters the behavior of conforming code
(i.e. to become not conforming) is not allowed.  Note that the
emphasis in the first paragraph is to interpolate or extrapolate, not
to change.

> So, I would say that an implementation could document the
> FIXNUMS-REMAIN-FIXNUM declaration, make it off by default, and then
> any code which is compiled and run in the default environment would
> behave as standardized; code using it could have its meaning changed
> in the form currently in Allegro CL under high speed and low safety,
> and the net effect would be as before. 

Yes, the net effect would be as before, but in fact, for the most part,
the switch we use provides the same functionality (and thus I label
both as nonconformant) - both are off by default (because the default
speed and safety in Allegro CL are 1 and 1, respectively, and safe
code is in fact defined as safety = 3 (per
http://www.franz.com/support/documentation/8.0/ansicl/glossary/s.htm#safe
and the next-to-last paragraph of
http://www.franz.com/support/documentation/8.0/ansicl/dictentr/optimize.htm)
and when activated, both produce a nonconformant change in behavior in
fixnum addition and subtraction (e.g. (1+ most-positive-fixnum)
becomes most-negative-fixnum).  The only difference between the two
is that the current actual switch allows the nonconformance to take
place under circumstances where it is most likely to be desired, in
very fast-and-loose coding, usually either during benchmarks or in
tightly controlled situations.  Perhaps all of your users are purists,
but most of our customers appreciate this capability, and those who
don't simply stay away from the speed=3/safety=0 optimization
combination.

> In the second case, it is mandated that the return value be the
> mathematically correct one if the sum is indeed a fixnum.  If it
> isn't, "the consequences are undefined", so it would not be strictly
> conforming code.

Yes, this first part is correct.

>  However, much as in the first version, an
> implementation could document the behaviour of code which is not
> conforming, as a language extension; one useful extension in this case
> might be to return the "logical" wrapped-around fixnum.

And this is correct, but _not_ like the first version.  Note that in
this case there is undefined behavior that can be filled, whereas in
the first case the behavior is defined and (non-conformantly) changed.

> (I'm not sure I'm answering the question under your question; it's
> possible I've missed or misread something either in your question or
> in the standard, because I don't think this is terribly controversial.
> Maybe if it is, someone else will chip in and tell me so.)

Yes, you've understood the question.  We just have disagreed on the
answer.  Hopefully I've convinced you of the difference, and of the
greater similarity of the first situation to Allegro CL's switch than
to the second situation.

>> 2. When you say 
>>
>>> better ways of expressing the aim of performing hardware arithmetic on
>>> lisp objects.
>>
>> are you suggesting continuing to use the + or - operators?
>
> Let me preface my answer by observing that there seems to me to be a
> practical difference as well as an implementation difference between
> signed and unsigned arithmetic.

I'll stop you right here - I appreciate your trepidation in presenting
a handwaving session about signedness issues, but that is not what I
was after, so let's not get into signedness.  Instead, I'll point you
in the direction I was trying to lead us to.

Your example is perfectly good:

>   (defun baz (x y)
>     (declare (type (unsigned-byte 32) x y))
>     (logand #xfffffff (+ x y)))

and is similar (in the way that I am after) to the typical style of
overflow management which was the second example in the first
question, above:

(defun bar (x y)
  (declare (fixnum x y))
  (the fixnum (+ x y)))

So how are these two forms similar?  They are similar in that they are
opposed to the minimalist declaration of this code:

(defun bas (x y)
  (declare (fixnum x y))
  (+ x y))

and I there is an argument to be made for this code not checking for
overflow.  Indeed, we've had many customers demand such capability,
and have even had customers _thank_ us for making such a capability
available:

What is a fixnum?  Well, it has a formal definition which includes
its limits (i.e. most-{negative,positive}-fixnum), and it has a
minimum size (it must be at least 15 bits plus sign).  However,
other than its marriage to bignum to form the exhaustive partition of
type integer, the spec goes out of its way _not_ to do too much with
fixnum ort bignum, and to instead treat type integer as the real basic
type.  Have you wondered why there is no fixnump or bignump
predicates, and yet there is an integerp predicate?  Is that an
oversight, or is it foresight?

Let's move on:  Why does one declare something to be of type fixnum?
It would be just as correct to declare the type to be 
(integer #.most-negative-fixnum #.most-positive-fixnum), but obviously
that would be harder to type.  However, why would one use fixnum
rather than some other integer range, especially since that
declaration isn't really portable (i.e. its range varies from
implemnentation to implementation)?  Why not try to be more accurate
in the declaration?

I submit that often, the reason for this abundant use of the fixnum
type is not necessarily to specify a specific range, but instead as a
lazy way of saying "something small".  I think we've probably all done
this; we aren't sure what the range of an integer variable will be,
but we do know that it will be a small integer, so we say "I'll just
declare it fixnum...".

Common Lisp doesn't have a way to declare something a "small integer";
any deftype definition of small-integer would have to expand into a
concrete type of the form (integer <low> <high>).  So since the fixnum
type is available and for the most part it does what we want it to do,
we use that. 

So let's get back to our bas definition:  why, as a customer of a CL,
do I want to not have to wrap that addition in a (the fixnum ...) or
(logand ...)?  Well, imagine that I'm working in a tough environment,
with lots of C-centric programmers and PHB's breathing down my neck;
I don't like having to explain to those C experts why I have to have
all of those extra declarations (and what is this "the" thing, anyway,
some sort of _cast_?!)  So I want to be able to say, in bas: "I have
two "small" integers, and I want to be able to add them together as
efficiently as possible (where efficiency includes source code size
and execution speed).  So I set a switch (C people understand switches
:-) and it just works as I had intended.  I guess you could say that
this is a situation where "worse is better".

I'm not sure how much further I want to go with this; hopefully you
get my drift, and hopefully I'm making sense at this late hour.

-- 
Duane Rettig    ·····@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   
From: Christophe Rhodes
Subject: Re: why is lisp fast?
Date: 
Message-ID: <sq4pwa9war.fsf@cam.ac.uk>
Duane Rettig <·····@franz.com> writes:

> Christophe Rhodes <·····@cam.ac.uk> writes:
>
>> In the specific case of an implementation-defined declaration, the
>> CLHS explicitly says that
>>
>>   An implementation is free to support other (implementation-defined)
>>   declaration identifiers as well.
>>
>> and since it's unlikely that an implementation-defined declaration
>> that the standardizers were referring to would have no effect, I think
>> it's reasonable to accept that implementation-defined declarations
>> could change the behaviour of programs that the declarations apply to.
>
> However, consider 1.6:
>
> http://www.franz.com/support/documentation/8.0/ansicl/section/languag0.htm
>
> The first paragraph cites the applicability of the extension, and uses
> words "specifies as ... extendable by the implementation".  So this
> section applies here, since we're talking about new declarations.
> Note, though, that the third paragraph says "An implementation can
> have extensions, provided they do not alter the behavior of conforming
> code ...".  A declaration that alters the behavior of conforming code
> (i.e. to become not conforming) is not allowed.  Note that the
> emphasis in the first paragraph is to interpolate or extrapolate, not
> to change.

I think this could be argued both ways.  For instance, 1.5.2 point 5
specifies that conforming code cannot depend on a language extension,
so code that uses the FIXNUMS-REMAIN-FIXNUMS declaration is
necessarily non-conforming.  (I confess to find 1.5.2 not terribly
clear, because point 5 appears to contradict point 1.  Maybe there is
no conforming code at all, and we'll all vanish in a puff of
logic. :-)

> Yes, you've understood the question.  We just have disagreed on the
> answer.  Hopefully I've convinced you of the difference, and of the
> greater similarity of the first situation to Allegro CL's switch than
> to the second situation.

I'm afraid I think that the effect on code that uses these extensions
is the same: the code becomes non-conforming.  In both of these cases
the conformance of the implementation in this respect is the same,
which is a difference between the FIXNUMS-REMAIN-FIXNUMS declaration
and the situation in speed=3 safety=0 mode.

> So how are these two forms similar?  They are similar in that they are
> opposed to the minimalist declaration of this code:
>
> (defun bas (x y)
>   (declare (fixnum x y))
>   (+ x y))
>
> and I there is an argument to be made for this code not checking for
> overflow.  Indeed, we've had many customers demand such capability,
> and have even had customers _thank_ us for making such a capability
> available:

Well, you can't argue (much) with customers.  And I am happy to
concede that I have the luxury of being able to argue with users, at
least for now.  On the other hand, we have had users thank us for the
ability to perform hardware arithmetic and logical operations -- not
that I doubt that you have more grateful customers than we have
grateful users ;-)

> I submit that often, the reason for this abundant use of the fixnum
> type is not necessarily to specify a specific range, but instead as a
> lazy way of saying "something small".  I think we've probably all done
> this; we aren't sure what the range of an integer variable will be,
> but we do know that it will be a small integer, so we say "I'll just
> declare it fixnum...".

I think I agree with this characterization of the fixnum declaration;
from the point of view of "outward" portability of code, or even
portability across platforms of the same implementation, it can be
unhelpful, but within a controlled environment or for quick speedups
it can be helpful.

> So let's get back to our bas definition:  why, as a customer of a CL,
> do I want to not have to wrap that addition in a (the fixnum ...) or
> (logand ...)?  Well, imagine that I'm working in a tough environment,
> with lots of C-centric programmers and PHB's breathing down my neck;
> I don't like having to explain to those C experts why I have to have
> all of those extra declarations (and what is this "the" thing, anyway,
> some sort of _cast_?!)  So I want to be able to say, in bas: "I have
> two "small" integers, and I want to be able to add them together as
> efficiently as possible (where efficiency includes source code size
> and execution speed).  So I set a switch (C people understand switches
> :-) and it just works as I had intended.  

I'm afraid I think that there is a distinction between wrapping (the
fixnum ...) around a form and wrapping (logand ...) or (slogand ...).
In the former case, there is no expressive advantage gained without
reference to a particular implementation's documentation, and a
particular implementation at a particular time at that.  In the
latter, the programmer has expressed an algorithm independent of a
particular implementation's extensions.  This may not make a
difference for use-once code, and as you say may have a slight
negative impact in certain circumstances, but I contend that there
will be situations where the long-term benefits of expressing an
algorithm rather than a solution are positive, too.

> I guess you could say that this is a situation where "worse is
> better".

This is very close to what I was trying to express by the word
"unfortunate", for what it's worth.

> I'm not sure how much further I want to go with this; hopefully you
> get my drift, and hopefully I'm making sense at this late hour.

Fair enough; in case you don't want to reply, thank you for the
discussion.

Christophe
From: Duane Rettig
Subject: Re: why is lisp fast?
Date: 
Message-ID: <o0mza2rnhq.fsf@franz.com>
Christophe Rhodes <·····@cam.ac.uk> writes:

> Duane Rettig <·····@franz.com> writes:
>
>> Christophe Rhodes <·····@cam.ac.uk> writes:
>>
>>> In the specific case of an implementation-defined declaration, the
>>> CLHS explicitly says that
>>>
>>>   An implementation is free to support other (implementation-defined)
>>>   declaration identifiers as well.
>>>
>>> and since it's unlikely that an implementation-defined declaration
>>> that the standardizers were referring to would have no effect, I think
>>> it's reasonable to accept that implementation-defined declarations
>>> could change the behaviour of programs that the declarations apply to.
>>
>> However, consider 1.6:
>>
>> http://www.franz.com/support/documentation/8.0/ansicl/section/languag0.htm
>>
>> The first paragraph cites the applicability of the extension, and uses
>> words "specifies as ... extendable by the implementation".  So this
>> section applies here, since we're talking about new declarations.
>> Note, though, that the third paragraph says "An implementation can
>> have extensions, provided they do not alter the behavior of conforming
>> code ...".  A declaration that alters the behavior of conforming code
>> (i.e. to become not conforming) is not allowed.  Note that the
>> emphasis in the first paragraph is to interpolate or extrapolate, not
>> to change.
>
> I think this could be argued both ways.  For instance, 1.5.2 point 5
> specifies that conforming code cannot depend on a language extension,
> so code that uses the FIXNUMS-REMAIN-FIXNUMS declaration is
> necessarily non-conforming.  (I confess to find 1.5.2 not terribly
> clear, because point 5 appears to contradict point 1.  Maybe there is
> no conforming code at all, and we'll all vanish in a puff of
> logic. :-)

Only if you confuse the separation between conforming _code_ and a
conforming _implementation_.  The THE violation of (the fixnum ...)
wrapped example is a user _code_ violation only (and that, only if
there is an expectation of a certain behavior at the point of
overflow).  The implementation conforms completely.  The theoretical
FIXNUMS-REMAIN-FIXNUMS declaration is a non-conforming extension to
the _implementation_.  Of course, use of it might make the code that
uses it non-conformant as well, so in that sense the two styles are
similar.  But not too similar; if the (non-conformant) declaration
were placed in a global declaim outside the user's code, the code is
not non-conformant, as long as it doesn't _count_ on the results of
the addition to wrap around - in reality the likely story is that the
programmer wasn't expecting it to overflow anyway, so the only
negative effect would be that the code becomes slower because it must
check for overflow.  But by relegating the extended declaration (as a
global switch, if you will) to some location outside of the code, the
code itself remains conformant. Similar things can be said of the (the
fixnum (+ x y)) case - it would only be nonconformant if the
programmer passed values for x and y that would indeed overflow fixnum
range, and thus if the actual _intention_ is for "small integers" and
no assumptions are made about wrapped-around results, then the code is
still conformant, portable code.  This can be done now (as of Ansi CL)
because of the lower limit placed on fixnum size; it was a much harder
case to argue in CLtL1 days, when it was legal to implement the fixnum
type as the values 0 and -1, and all other integers would then be
bignums...  back then we waved hands and argued that no CL implementor
in their right mind would implement fixnums that small.

>> Yes, you've understood the question.  We just have disagreed on the
>> answer.  Hopefully I've convinced you of the difference, and of the
>> greater similarity of the first situation to Allegro CL's switch than
>> to the second situation.
>
> I'm afraid I think that the effect on code that uses these extensions
> is the same: the code becomes non-conforming.  In both of these cases
> the conformance of the implementation in this respect is the same,
> which is a difference between the FIXNUMS-REMAIN-FIXNUMS declaration
> and the situation in speed=3 safety=0 mode.

Again, I'm not talking about conforming _code_, I'm talking about
conforming _implementation_.

>> So how are these two forms similar?  They are similar in that they are
>> opposed to the minimalist declaration of this code:
>>
>> (defun bas (x y)
>>   (declare (fixnum x y))
>>   (+ x y))
>>
>> and I there is an argument to be made for this code not checking for
>> overflow.  Indeed, we've had many customers demand such capability,
>> and have even had customers _thank_ us for making such a capability
>> available:
>
> Well, you can't argue (much) with customers.  And I am happy to
> concede that I have the luxury of being able to argue with users, at
> least for now.  On the other hand, we have had users thank us for the
> ability to perform hardware arithmetic and logical operations -- not
> that I doubt that you have more grateful customers than we have
> grateful users ;-)

:-)

>> I submit that often, the reason for this abundant use of the fixnum
>> type is not necessarily to specify a specific range, but instead as a
>> lazy way of saying "something small".  I think we've probably all done
>> this; we aren't sure what the range of an integer variable will be,
>> but we do know that it will be a small integer, so we say "I'll just
>> declare it fixnum...".
>
> I think I agree with this characterization of the fixnum declaration;
> from the point of view of "outward" portability of code, or even
> portability across platforms of the same implementation, it can be
> unhelpful, but within a controlled environment or for quick speedups
> it can be helpful.
>
>> So let's get back to our bas definition:  why, as a customer of a CL,
>> do I want to not have to wrap that addition in a (the fixnum ...) or
>> (logand ...)?  Well, imagine that I'm working in a tough environment,
>> with lots of C-centric programmers and PHB's breathing down my neck;
>> I don't like having to explain to those C experts why I have to have
>> all of those extra declarations (and what is this "the" thing, anyway,
>> some sort of _cast_?!)  So I want to be able to say, in bas: "I have
>> two "small" integers, and I want to be able to add them together as
>> efficiently as possible (where efficiency includes source code size
>> and execution speed).  So I set a switch (C people understand switches
>> :-) and it just works as I had intended.  
>
> I'm afraid I think that there is a distinction between wrapping (the
> fixnum ...) around a form and wrapping (logand ...) or (slogand ...).
> In the former case, there is no expressive advantage gained without
> reference to a particular implementation's documentation, and a
> particular implementation at a particular time at that.  In the
> latter, the programmer has expressed an algorithm independent of a
> particular implementation's extensions.  This may not make a
> difference for use-once code, and as you say may have a slight
> negative impact in certain circumstances, but I contend that there
> will be situations where the long-term benefits of expressing an
> algorithm rather than a solution are positive, too.

No need to be afraid :-) I agree completely that there are
distinctions between these two approaches.  What I was trying to
emphasize was not their distinction, but their similarity when
compared with a raw (+ x y), in that the raw (+ x y) is in fact
unadorned - it is what it is, an addition between two (in this case)
fixnums, and the result is guaranteed, unless the implementation
chooses to do something non-conformant.  The other two cases represent
adornments, which might have varying degrees of effectivity and
portabiolity, but they are adornments nonetheless, which the user must
make beyond the raw (+ x y) form.

>> I guess you could say that this is a situation where "worse is
>> better".
>
> This is very close to what I was trying to express by the word
> "unfortunate", for what it's worth.

Well, why didn't you say so in the first place? :-) :-) :-)

>> I'm not sure how much further I want to go with this; hopefully you
>> get my drift, and hopefully I'm making sense at this late hour.
>
> Fair enough; in case you don't want to reply, thank you for the
> discussion.

I had to go one more round, but it's been an interesting exercise in
putting down thoughts that have been discussed many times over the
last 18 years.  It is, of course, only my point of view, but I think
you'd find similar stories from other Franz staff, or from whomever
added the "fixnum-safety" declaration to Lispworks (I believe that the
original LCL also had such a global switch-or-declaration, as well),
as well as any other General-Purpose-hardware lisps that went through
the Gabriel benchmark wars during the years just before and after his
book came out.

-- 
Duane Rettig    ·····@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   
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: why is lisp fast?
Date: 
Message-ID: <87zme3qjz4.fsf@qrnik.zagroda>
Duane Rettig <·····@franz.com> writes:

>> (MY-ADD MOST-POSITIVE-FIXNUM MOST-POSITIVE-FIXNUM) is a perfectly
>> valid call to MY-ADD given the above code, and it should return the
>> integer which is twice MOST-POSITIVE-FIXNUM.  Any other answer is a
>> conformance bug.
>
> This is true.  Every CL that wants to compete with C must have such a
> non-conformance.

I doubt it. If forcing users to declare types of arithmetic results
explicitly would be too much burden for them, why can't it require a
non-standard declaration to assume that certain arithmetic doesn't
overflow fixnums? I believe CL doesn't rule out non-standard
declarations.

> Now, is that a bad thing?  Can any CL impementation be completely
> conforming?

This is a silly argument. Even if there are cases where complying is
impossible because of defects in the standard, this one isn't one of
them.

> http://www.franz.com/support/documentation/8.0/doc/variables/compiler/declared-fixnums-remain-fixnums-switch.htm

This piece of documentation is not quite clear about what is the
default value of the switch. Although this could be perhaps guessed
from the remark about turning it off.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: K.S.Sreeram
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155820893.979642.18520@h48g2000cwc.googlegroups.com>
Thanks for the detailed explanation!

I managed to get sbcl 0.9.15 compiled on win32, and when i tried the
following:
(disassemble (compile (defun f (a b) (the fixnum (+ (the fixnum a) (the
fixnum b))))))
I got 3 pages of output! Are optimizations not enalbed on sbcl-win32,
or is it something else?
; 0A59B30D:       A803             TEST AL, 3                 ;
no-arg-parsing entry point
;      30F:       7551             JNE L3
;      311:       8BD0             MOV EDX, EAX
;      313:       F7C703000000     TEST EDI, 3
;      319:       754C             JNE L4
;      31B:       8BCF             MOV ECX, EDI
;      31D:       C1FA02           SAR EDX, 2
;      320:       C1F902           SAR ECX, 2
;      323:       01CA             ADD EDX, ECX
;      325:       8BCA             MOV ECX, EDX
;      327:       D1E1             SHL ECX, 1
;      329:       7043             JO L5
;      32B:       D1E1             SHL ECX, 1
;      32D:       703F             JO L5
;      32F: L0:   F6C103           TEST CL, 3
;      332:       750D             JNE L1
;      334:       C1E202           SHL EDX, 2
;      337:       8D65F8           LEA ESP, [EBP-8]
;      33A:       F8               CLC
;      33B:       8B6DFC           MOV EBP, [EBP-4]
;      33E:       C20400           RET 4
;      341: L1:   8BCA             MOV ECX, EDX
;      343:       D1E1             SHL ECX, 1
;      345:       7074             JO L9
;      347:       D1E1             SHL ECX, 1
;      349:       7070             JO L9
;      34B: L2:   8B15ACB2590A     MOV EDX, [#xA59B2AC]       ; 'FIXNUM
;      351:       CC0A             BREAK 10                   ; error
trap
;      353:       03               BYTE #X03
;      354:       1F               BYTE #X1F                  ;
OBJECT-NOT-TYPE-ERROR
;      355:       4E               BYTE #X4E                  ; ECX
;      356:       8E               BYTE #X8E                  ; EDX
;      357:       90               NOP
;      358:       CC0A             BREAK 10                   ; error
trap
;      35A:       02               BYTE #X02
;      35B:       18               BYTE #X18                  ;
INVALID-ARG-COUNT-ERROR
;      35C:       4D               BYTE #X4D                  ; ECX
;      35D:       CC0A             BREAK 10                   ; error
trap
;      35F:       02               BYTE #X02
;      360:       18               BYTE #X18                  ;
INVALID-ARG-COUNT-ERROR
;      361:       4D               BYTE #X4D                  ; ECX
;      362: L3:   CC0A             BREAK 10                   ; error
trap
;      364:       02               BYTE #X02
;      365:       08               BYTE #X08                  ;
OBJECT-NOT-FIXNUM-ERROR
;      366:       0E               BYTE #X0E                  ; EAX
;      367: L4:   CC0A             BREAK 10                   ; error
trap
;      369:       04               BYTE #X04
;      36A:       08               BYTE #X08                  ;
OBJECT-NOT-FIXNUM-ERROR
;      36B:       FECE01           BYTE #XFE, #XCE, #X01      ; EDI
;      36E: L5:   C605AC02000504   MOV BYTE PTR [#x50002AC], 4
;      375:       B908000000       MOV ECX, 8
;      37A:       030D20EA5100     ADD ECX, [#x51EA20]        ;
_boxed_region
;      380:       3B0D24EA5100     CMP ECX, [#x51EA24]
;      386:       7607             JBE L6
;      388:       E89774E7F5       CALL #x412824              ;
_alloc_overflow_ecx
;      38D:       EB09             JMP L7
;      38F: L6:   890D20EA5100     MOV [#x51EA20], ECX        ;
_boxed_region
;      395:       83E908           SUB ECX, 8
;      398: L7:   C7010A010000     MOV DWORD PTR [ECX], 266
;      39E:       8D4907           LEA ECX, [ECX+7]
;      3A1:       8951FD           MOV [ECX-3], EDX
;      3A4:       C605AC02000500   MOV BYTE PTR [#x50002AC], 0
;      3AB:       803DC402000500   CMP BYTE PTR [#x50002C4], 0
;      3B2:       7402             JEQ L8
;      3B4:       CC09             BREAK 9                    ; pending
interrupt trap
;      3B6: L8:   E974FFFFFF       JMP L0
;      3BB: L9:   C605AC02000504   MOV BYTE PTR [#x50002AC], 4
;      3C2:       B908000000       MOV ECX, 8
;      3C7:       030D20EA5100     ADD ECX, [#x51EA20]        ;
_boxed_region
;      3CD:       3B0D24EA5100     CMP ECX, [#x51EA24]
;      3D3:       7607             JBE L10
;      3D5:       E84A74E7F5       CALL #x412824              ;
_alloc_overflow_ecx
;      3DA:       EB09             JMP L11
;      3DC: L10:  890D20EA5100     MOV [#x51EA20], ECX        ;
_boxed_region
;      3E2:       83E908           SUB ECX, 8
;      3E5: L11:  C7010A010000     MOV DWORD PTR [ECX], 266
;      3EB:       8D4907           LEA ECX, [ECX+7]
;      3EE:       8951FD           MOV [ECX-3], EDX
;      3F1:       C605AC02000500   MOV BYTE PTR [#x50002AC], 0
;      3F8:       803DC402000500   CMP BYTE PTR [#x50002C4], 0
;      3FF:       7402             JEQ L12
;      401:       CC09             BREAK 9                    ; pending
interrupt trap
;      403: L12:  E943FFFFFF       JMP L2


Pascal Bourguignon wrote:
> "K.S.Sreeram" <·········@gmail.com> writes:
>
> > Tim Bradshaw wrote:
> >> K.S.Sreeram wrote:
> >>
> >> >
> >> > Is lisp fast *only* if you add type annotations? Or are there any
> >> > language features which make it inherenly easier to generate effecient
> >> > native code? Take python for instance, there have been attempts to
> >> > write native code compilers for it, but none of them have worked well.
> >> > What language design features make lisp more suitable for compilers?
> >>
> >> CL also made some good decisions about types & classes - everything is
> >> an object, but built-in classes (like numbers, conses, arrays) have
> >> restrictions that allow for good implementation.  Compare with the `you
> >> can subclass floats' that some languages do, or the alternative `floats
> >> are not objects' that, say, Java does.
> >
> > Take a simple expression like (+ a b). Every symbol involved here has
> > to be looked up from the environment, and then the '+' function has to
> > be called.
> >
> > Here is the rough list of steps that need to be performed at runtime:
> >
> > 1) Lookup '+' from the environment, (returns a function)
> > 2) Lookup 'a' from the environment  (return a number)
> > 3) Lookup 'b' from the environment  (returns another number)
> > 4) Call the function '+' and return the result
>
> How wrong you are!
>
>
> * (disassemble (compile (defun f (a b) (the fixnum (+ (the fixnum a) (the fixnum b))))))
> STYLE-WARNING: redefining F in DEFUN
>
> ; 0AF3ED56:       01FA             ADD EDX, EDI               ; no-arg-parsing entry point
> ;       58:       8D65F8           LEA ESP, [EBP-8]
> ;       5B:       F8               CLC
> ;       5C:       8B6DFC           MOV EBP, [EBP-4]
> ;       5F:       C20400           RET 4
> ;       62:       90               NOP
> ;       63:       90               NOP
> ;       64:       90               NOP
> ;       65:       90               NOP
> ;       66:       90               NOP
> ;       67:       90               NOP
> ;
> NIL
> *
>
> > An equivalent expression in C 'a + b', will require the following
> > steps:
> > 1) mov eax, [a]   (load value from address-of-a into accumulator)
> > 2) add eax, [b]   (add value from address-of-b to accumulator)
> > 3) return eax
>
> sbcl generates better code because it's able to pass arguments in
> registers which C cannot do.
>
>
> > If these were the steps required at runtime.. how can lisp *EVER* have
> > speed that is comparable to C???
>
> Who said they were required at runtime?
>
>
> > It looks like lisp will be around a
> > couple of orders of magnitude slower than C!
> >
> > I guess i must be missing something about how the lisp runtime behaves.
> > Please enlighten me!
>
> Basically, the difference is in the type system.
>
>
> Imagine you'd have a C compiler able to generate code from such a program:
>
>      fact(n){
>        if(n<=1){ return(1); }
>        else{ return(n*fact(n-1)); }
>
> that is, no type declaration.  First, this C compiler would have to add types:
>
>      typedef struct object {
>          int tag;
>          union {
>             char   c;
>             short  s;
>             long   l;
>             float  f;
>             double d;
>             char*  string;
>          } data;
>      } object;
>
>
>      object fact(object n){
>         switch(n.tag){
>         case 0: if(n.data.c<=1){goto then;}else{goto else;}
>         case 1: if(n.data.s<=1){goto then;}else{goto else;}
>         case 2: if(n.data.l<=1){goto then;}else{goto else;}
>         case 3: if(n.data.f<=1){goto then;}else{goto else;}
>         case 4: if(n.data.d<=1){goto then;}else{goto else;}
>         case 5: error("Cannot compare strings");
>         default: error("Invalid object type");
>         }
>       then:
>         return(1);
>       else:
>         switch(n.tag){
>         case 0: return(object(0,n.data.c*fact(object(0,n.data.c-1))));
>         case 1: return(object(1,n.data.s*fact(object(1,n.data.s-1))));
>         case 2: return(object(2,n.data.l*fact(object(2,n.data.l-1))));
>         case 3: return(object(3,n.data.f*fact(object(3,n.data.f-1e0))));
>         case 4: return(object(4,n.data.d*fact(object(4,n.data.d-1d0))));
>         case 5: error("Cannot multiply strings");
>         default: error("Invalid object type");
>         }}
>
> Note that the * generated in the case 0 is not the same as the *
> generated in the other cases by the C compiler.  In case 0, it can by
> a byte*byte->short multiply. In case 4, it's a double floating point
> multiplicate.
>
>
> Well, in Lisp it's the same.
> If you write:
>
>    (defun fact (n)
>      (declare (fixnum n))
>      (if (<= n 1)
>          1
>         (the fixnum (* n (fact (- n 1))))))
>
> you get the same (buggy) code as in C with types, and if you write:
>
>    (defun fact (n)
>      (if (<= n 1)
>          1
>          (* n (fact (- n 1)))))
>
> you get the correct code, which contrarily to C is able to give
> correct results for more than 13 values, and both for floating point
> arguments or integers, even if it's slower because it has to make some
> run-time type checking and polymorphic operations.
>
>
>
> And it can even produce symbolic results:
>
>    (shadow '(*))
>    (defun * (a &rest b) `(* ,a ,@b))
>    (defun fact (n)
>      (if (<= n 1)
>          1
>          (* n (fact (- n 1)))))
>    (fact 10)
>    --> (* 10 (* 9 (* 8 (* 7 (* 6 (* 5 (* 4 (* 3 (* 2 1)))))))))
>
> Try to do that in C!
>
>
> --
> __Pascal Bourguignon__                     http://www.informatimago.com/
>
> COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
> protons, etc.) comprising this product are exactly the same in every
> measurable respect as those used in the products of other
> manufacturers, and no claim to the contrary may legitimately be
> expressed or implied.
From: Christophe Rhodes
Subject: Re: why is lisp fast?
Date: 
Message-ID: <sq64grxyta.fsf@cam.ac.uk>
"K.S.Sreeram" <·········@gmail.com> writes:

> Thanks for the detailed explanation!
>
> I managed to get sbcl 0.9.15 compiled on win32, and when i tried the
> following:
> (disassemble (compile (defun f (a b) (the fixnum (+ (the fixnum a) (the
> fixnum b))))))
> I got 3 pages of output! Are optimizations not enalbed on sbcl-win32,
> or is it something else?

You are probably compiling under a high-safety policy, under which
SBCL will treat your declarations as assertions to be checked.  Under
lower safety compilation policies, the system will trust your
declarations completely.

(defun f (a b)
  (declare (optimize speed (safety 0)))
  (the fixnum (+ (the fixnum a) (the fixnum b))))

will perform a fast addition with no typecheck; however, there will
still be error code at the end of this function, because of the
argument count checking required.  To remove this, you need

(locally
  (declare (optimize speed (safety 0)))
  (defun f (a b)
    (the fixnum (+ (the fixnum a) (the fixnum b)))))

Christophe
From: Pascal Bourguignon
Subject: Re: why is lisp fast?
Date: 
Message-ID: <87ac63mqgv.fsf@thalassa.informatimago.com>
"K.S.Sreeram" <·········@gmail.com> writes:

> Thanks for the detailed explanation!
>
> I managed to get sbcl 0.9.15 compiled on win32, and when i tried the
> following:
> (disassemble (compile (defun f (a b) (the fixnum (+ (the fixnum a) (the
> fixnum b))))))
> I got 3 pages of output! Are optimizations not enalbed on sbcl-win32,
> or is it something else?

Oops!  It seems I stayed silent on the declarations.

You can put a global:

(declaim (optimize (speed 3) (space 0) (safety 0) (debug 0)))

Or you can do it function per function:

(defun f (a b)
  (declare (optimize (speed 3) (space 0) (safety 0) (debug 0))
           (type fixnum a b))
  ...)

You can try various combinations of speed, space, safety and debug
optimizations (values between 0 and 3), and see in each case what the
compiler generates.


Note that by default, I have in my initialization files:

(declaim (optimize (speed 0) (space 0) (safety 3) (debug 3)))

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
From: Thomas Lindgren
Subject: Re: why is lisp fast?
Date: 
Message-ID: <8764grie2l.fsf@anatidae.i-did-not-set--mail-host-address--so-shoot-me>
"K.S.Sreeram" <·········@gmail.com> writes:

> Take a simple expression like (+ a b). Every symbol involved here has
> to be looked up from the environment, and then the '+' function has to
> be called.
> 
> Here is the rough list of steps that need to be performed at runtime:
> 
> 1) Lookup '+' from the environment, (returns a function)
> 2) Lookup 'a' from the environment  (return a number)
> 3) Lookup 'b' from the environment  (returns another number)
> 4) Call the function '+' and return the result

In addition to what others have said, do note that the underlying idea
is that most of the steps you mention can be performed and optimized
*at compile time*. This is why the runtime costs can be less than one
might at first think.

Thus, '+ is found by the compiler to be a function with a known
definition; a and b are found in registers or on the stack (at known
offsets from a stack pointer) or perhaps on the heap (at known offsets
from a closure pointer), all depending on the surrounding context
(known at compile-time); and finally the expression (+ a b) can often
itself be drastically simplified, particularly when given type
information and other declarations.

(Naturally, the full story of writing a fast Lisp system is richer,
more complex, and has more shades of grey than this, but I'll leave
that explanation to the literature.)

Best,
                                Thomas
-- 
Thomas Lindgren
From: John Thingstad
Subject: Re: why is lisp fast?
Date: 
Message-ID: <op.tecdexq8pqzri1@pandora.upc.no>
On Tue, 15 Aug 2006 22:05:48 +0200, K.S.Sreeram <·········@gmail.com>  
wrote:

> Most lispers claim that lisp speed is close to that of C/C++. See this
> page for instance:
> http://www.norvig.com/python-lisp.html
>
> Is lisp fast *only* if you add type annotations? Or are there any
> language features which make it inherenly easier to generate effecient
> native code? Take python for instance, there have been attempts to
> write native code compilers for it, but none of them have worked well.
> What language design features make lisp more suitable for compilers?
>
> [sreeram;]++
>

In a nutshell LR0.
That is you don't need to look ahead to know what state you are in.
(command arg1 arg2 ...)
This makes it easier to write macro's.
Macro's can use the entire lisp language to write a reduced form.
The compiler then just has to worry about a compiling a few
form's to assembly.

'Lisp in small pieces'
http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html
ought to give you some idea.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
From: Rob Thorpe
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155726366.609654.106640@h48g2000cwc.googlegroups.com>
John Thingstad wrote:
> On Tue, 15 Aug 2006 22:05:48 +0200, K.S.Sreeram <·········@gmail.com>
> wrote:
>
> > Most lispers claim that lisp speed is close to that of C/C++. See this
> > page for instance:
> > http://www.norvig.com/python-lisp.html
> >
> > Is lisp fast *only* if you add type annotations? Or are there any
> > language features which make it inherenly easier to generate effecient
> > native code? Take python for instance, there have been attempts to
> > write native code compilers for it, but none of them have worked well.
> > What language design features make lisp more suitable for compilers?
> >
> > [sreeram;]++
> >
>
> In a nutshell LR0.
> That is you don't need to look ahead to know what state you are in.
> (command arg1 arg2 ...)
> This makes it easier to write macro's.
> Macro's can use the entire lisp language to write a reduced form.
> The compiler then just has to worry about a compiling a few
> form's to assembly.
>
> 'Lisp in small pieces'
> http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html
> ought to give you some idea.

This just makes it easier to write a simple lisp compiler.  It only
affects the front end of the process, the parsing.

Almost all compilers or interpreters bring to source form into a tree
of commands, fundamentally similar to a lisp program after it's been
through the reader.

The real issue is the semantics of the language, and whether they're
amenable to compiling.  Whether variables can be allocated on the stack
or must always be looked up from a hash for example.
From: Rob Thorpe
Subject: Re: why is lisp fast?
Date: 
Message-ID: <1155719636.408630.195840@i42g2000cwa.googlegroups.com>
K.S.Sreeram wrote:
> Most lispers claim that lisp speed is close to that of C/C++. See this
> page for instance:
> http://www.norvig.com/python-lisp.html
>
> Is lisp fast *only* if you add type annotations? Or are there any
> language features which make it inherenly easier to generate effecient
> native code? Take python for instance, there have been attempts to
> write native code compilers for it, but none of them have worked well.
> What language design features make lisp more suitable for compilers?

In addition to what Tim Bradshaw has said:

* Lisp has had compilers for almost as long as interpreters, the Lisp
1.5 compiler is said to have worked fairly well.  As a result over the
years language features have been picked that can be implemented easily
in compiled code. Ones that could only work in the interpreter have
always been seen as less useful.

* There is a lot of knowledge on how to write Lisp compilers because
it's been done for so long.  The implementations of the popular CLs,
even simple ones like ECL, are more sophisticated in terms of
optimization that the standard Python or Perl implementations.

It's worth mentioning that there are a few specific cases where Python
can beat some CL implementations.  Normally when something useful is
implemented in the C parts of Python.