Python from Wise Guy's Viewpoint

[Adam Warner]

Hi Fergus Henderson,

> Yes, we covered that already.  But that's not what is happening in
> the scenario that I was describing.  The scenario that I'm describing is
> 
> 	Collection c;
> 
> 	...
> 	foreach x in c do
> 		use(x);
> 
> where use(x) might be a method call, a field access, or similar.
> For example, perhaps the collection is a set of integers, and you
> are computing their sum, so use(x) would be "sum += x".
> 
> I think that in these situations, dynamically typed language
> implementations will do O(N) dynamic type checks, where N is the number
> of elements in "c".  In theory it is possible to optimize these away,
> but I don't know of any such implementations that do, and I would be
> suprised if there are any (except perhaps in limited cases, e.g. when
> the collection is an array or is implemented using an array).

I've implemented a collection of integers as a list:

* (disassemble
    (compile nil
      (lambda ()
        (declare (optimize (safety 0)))
        (let ((c '(1 2 3 4 5 6 7 8 9 10)))
          (loop for x of-type (integer 1 10) in c
                sum x of-type fixnum)))))

; Compiling lambda nil:
; Compiling Top-Level Form:
 
482C1160:       .entry "lambda nil"()        ; (function nil fixnum)
      78:       pop     dword ptr [ebp-8]
      7B:       lea     esp, [ebp-32]
      7E:       xor     eax, eax             ; No-arg-parsing entry point
      80:       mov     ecx, [#x482C1158]    ; '(1 2 3 4 ...)
      86:       xor     edx, edx
      88:       jmp     L1
      8A: L0:   mov     eax, [ecx-3]
      8D:       mov     ecx, [ecx+1]
      90:       add     edx, eax
      92: L1:   cmp     ecx, #x2800000B      ; nil
      98:       jne     L0
      9A:       mov     ecx, [ebp-8]
      9D:       mov     eax, [ebp-4]
      A0:       add     ecx, 2
      A3:       mov     esp, ebp
      A5:       mov     ebp, eax
      A7:       jmp     ecx

No type checks. And 32-bit assembly arithmetic (but the type bits are
still present. most-positive-fixnum is 536,870,911).

>>Regarding your earlier question, though, the great trick in Self was
>>to remember the result of a check and thus avoid doing it again
>>whenever possible.  If you do "y := x + 1", and you determine that "x"
>>is a floating point number, then you know that "y" will also be a
>>floating point number immediately afterwards.
> 
> Sure.  That helps an implementation avoid checking the type of the collection
> "c" at every element access.  But it doesn't help the implementation avoid
> checking the type of the element "x" at each iteration of the loop.

Lisp provides standard ways to supply declarations. Some implementations
will trust those declarations in order to optimise the code at compile
time.

>>This points to a general observation.  Dealing with the #1 style
>>dynamic type errors is a subset of dealing with dynamic dispatch in
>>general.  [....] any optimizations that get rid of these dynamic lookups,
>>will also get rid of type checks just by their nature.
> 
> That's true.  But the difference between dynamically typed languages and
> statically typed languages is that in dynamically typed languages, *every*
> data access (other than just copying data around) involves a dynamic dispatch.
> Sure, implementations can optimize a lot of them away.  But generally you're
> still left lots that your implementation can't optimize away, but which
> would not be present in a statically typed language, such as the O(N)
> dynamic type checks in the example above.

Again, Lisp provides standard ways to supply declarations. Some
implementations will trust those declarations in order to optimise the
code at compile time. And use the declarations for type inference.

Followup-To is set as comp.lang.lisp.

Regards,
Adam