Python's Lisp heritage

[Tim Peters]

[Andrew Dalke, on cons cells vs contiguous vectors for list storage]
> ...
> So algorithms which might run fast under Lisp do not under Python,
> and vice versa.  The decision for this difference was made after
> observations in ABC that most list use was through indexing, and not
> through a direct decision to be different from Lisp.

All lists in ABC were sorted -- you couldn't stop that.  If you wanted to
retain the order of insertion, you needed to insert explicit (index, value)
pairs, or build a dict explicitly mapping index to value.  ABC used balanced
binary trees (AVL style) under the covers for list storage.  So it was
neither Lisp-like nor Python-like in this respect.  It aimed at log N
worst-case time for all common list operations (whether indexing or
searching), but at the cost of log N expected-case time too.  Overall, ABC
didn't have "bad cases", but it was hard for anyone save a theoretician to
guess that since *everything* ran at bad-case speed <wink>.

doubting-that-cons-cells-were-even-considered-ly y'rs  - tim