10 ms·

So, I've long since argued the importance of what Ned terms the "cultural difference", or the difference between dynamic homogeneous structures (lists/relationa

• nedbat 10y ago
  Can you say more about the important performance ramifications?
  • colanderman 10y ago
    Dynamic homogeneous structures (lists) have uniform structure, but must be able to resize dynamically. The former helps performance (run-time type info can be hoisted out of the structure), the latter harms it (extra runtime machinery needed). Static heterogeneous structures (tuples) have a non-uniform structure, but need not resize. The former harms performance (run-time type info must be kept for each element, though usually few); the latter helps it (most accesses can be compiled to simple pointer arithmetic). On the other hand, dynamic heterogeneous structures (Python's lists) do not have uniform structure, and must be able to resize. So run-time type info must be preserved (adding memory/access overhead), and accesses can't be optimized at compile time (more runtime machinery). It is to avoid these issues that things like numpy and JavaScript's typed arrays exist. There is almost never a reason to use a dynamic heterogeneous structure, so they are best avoided. A dynamic heterogeneous collection can neither support indexing a priori known components (since it is dynamic), nor support iteration (since it is heterogeneous). (Note that a collection of objects of different types but with a shared interface is in fact a homogeneous collection of objects with that interface.) (The final combination is static homogeneous, but these are a subset of both the first two cases, and do not occur often. The only example I can think of are sets of statistics: all statistics have the same type, but there are a fixed number of them which are known at compile time. They can be optimized very well.)
    • pdonis 10y ago
      Python only has what you call "dynamic heterogeneous" structures because Python is a dynamic language. The ramifications of that are by no means limited to lists and tuples. It seems like you basically don't like dynamic languages. Some of your comments make no sense even given the above, however. For example, Python lists and tuples certainly support iteration.
      • colanderman 10y ago
        Erlang (one of my favorite languages) is dynamically typed, yet did not (until the recent addition of maps) have dynamic heterogeneous structures. You cannot iterate over or resize tuples, and the static analyzer discourages heterogeneous lists. Both are immutable (functional). I apologize that I have hopped between use and implementation a bit in my above post. Yes, the implementation of Python lists and tuples support iteration, but it would be nonsensical to write code which iterated over a list or tuple containing heterogeneous data. (What could you possibly do identically to each element, if they had nothing in common?) Hence my assertion that implementing a dynamic heterogeneous structure is inefficient, if it nonsensical to truly use it as such.
        • markrages 10y ago
          > it would be nonsensical to write code which iterated over a list or tuple containing heterogeneous data. There are Python functions that take any type like repr() or id()
          • colanderman 10y ago
            See my other comment; it does make sense to have a list of objects which share some interface. In the case you suggest, it is a very trivial and not-very-useful interface, but an interface nonetheless. You can do this with objects even in strictly-typed languages like OCaml or Mercury; code which iterates over the list is simply restricted to use only those methods which all elements have in common. Of course in languages which don't support a universal "object" type (say OCaml or C) you cannot do this -- numbers and strings have no interface in common. Those languages take advantage of this by not storing type information in collections (e.g. OCaml's float arrays, or any array in C), thus resulting in more compact memory footprints. If they instead allowed heterogeneous collections, the memory footprint of such collections would double.
• deleted 10y ago
  [deleted]
• Waterluvian 10y ago
  But be careful not to obsess over it. I've seen some worry about the runtime complexity of collections in Python for a handful of elements.
  • colanderman 10y ago
    Oh, of course. In Python's case, I'd advocate to just get rid of tuples and be done with it. (Maybe replace it with a nice immutable adaptor class; I'm sure one already exists.) It's a dynamically typed interpreted language, neither performance nor type-correctness is its strong point.
    • pdonis 10y ago
      > In Python's case, I'd advocate to just get rid of tuples and be done with it. That would be a bad idea for at least two reasons: sometimes you want containers to be immutable, and mutable containers can't be used as dictionary keys.
      • kazinator 10y ago
        You mean in Python or in computer science? Because I'm pretty sure that it's possible to use mutable objects as keys in general. The users just have to observe restrictions: like don't insert the keys into the dictionary and then mutate them while they are in the dictionary and expect the dictionary to still work fine. (Objects can also be used as keys even if they are mutated while in the dictionary, if identity-based equality is used for the dictionary; i.e. two keys are equal if they are acually one and the same object, and not just two similar objects.)
        • kilink 10y ago
          This is a Python specific restriction. Ruby for example allows mutable keys in dictionaries.
          • catnaroek 10y ago
• autokad 10y ago
  "here's no reason that "cultural" lists need be mutable, or "cultural" tuples need be immutable." er, yes there is. if a list is not mutable, doing list.append(something) in a loop would re-initialize the list every loop iteration. the same reason you shouldn't add to a string in a loop, as strings are imitable. to me, an immutable list is not a list.
  • colanderman 10y ago
    Have you used a functional language? (Lisp, OCaml, Erlang, etc.) Lists are immutable, yet appending items is O(1). That is achievable with even a basic singly-linked list implementation.
    • catnaroek 10y ago
      Lists aren't immutable in Lisp, though. More precisely, Lisp doesn't have lists: it has chains of mutable cons cells.
      • ScottBurson 10y ago
        They're not technically immutable, but culturally Lisp programmers are not in the habit of mutating lists unless they know where and for what purpose the list was created. Mutating some list whose provenance you don't know -- maybe you got it by calling some library function that doesn't explicitly promise to return a freshly consed list -- is a bad idea, and experienced Lisp programmers know this instinctively. So in practice you can often get away with pretending the lists you create are immutable, if that's what you want to do.
        • catnaroek 10y ago
          Culture isn't something I can take into account when reasoning about what a piece of code means. The actual semantics of the programming language in question is all I really have.
          • 10y ago
• xapata 10y ago
  > Why Python chose lists (and only lists!) to have both immutable and mutable flavors, with otherwise identical semantics, is beyond me. It didn't. There's frozenset as well. There's been discussion of an immutable dict every so often, but the conclusion is generally that it's unnecessary. The reason to have an immutable sequence is mostly to serve as dict keys. Same with an immutable set. If you use a mutable sequence as a dict key, you create ambiguity over whether you care about the memory location or the value of the sequence.
  • colanderman 10y ago
    I didn't know about frozenset, thank you!
  • jholman 10y ago
    https://pypi.python.org/pypi/frozendict https://pypi.python.org/pypi/frozendict of course
• pron 10y ago
  > TLA+ totally conflates tuples with lists, but its type system is rich enough to enforce the difference (and as a bonus, allows for the elusive static homogeneous structure). 1. TLA+ doesn't conflate the two at all. On the contrary: it has neither. TLA+'s data is based on set theory, and has syntax sugar for mathematical sequences, defined in TLA+ as functions from a prefix of the natural numbers to some set. I don't know what either "lists" or "tuples" are mathematically (in terms of set theory), and neither does TLA+. Like ordinary formal math, TLA+ has only sets (and functions, which are theoretically also encoded sets). Everything else can be defined in those terms. If, you come up with a mathematical definition of either or both, you can use it in TLA+. If the definition is the same for both, they won't will be the same; if it isn't -- they won't. 2. Like "ordinary" math, TLA+ has no type system at all. But you're right that any program property can be described in its simple logic. E.g., you can have a sequence whose all elements are natural numbers, except the prime indices, which are strings: ∀ n ∈ DOMAIN seq : seq[n] ∈ (IF IsPrime(n) THEN STRING ELSE Nat) Of course, for simple cases of constant-length sequences, you can have: seq ∈ Nat × STRING × Real or whatever.