News for hackers. Stuff that matters.
Re:Python Lists vs. Tuples by colanderman on Friday August 19, 2016 @11:22PM (#12325006)
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.
Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @12:20AM (#12325184)
Of course, some other common operations on singly-linked lists, notably concatenation, are O(n).

There are better choices for general-purpose functional lists.

Re:Python Lists vs. Tuples by catnaroek on Friday August 19, 2016 @11:31PM (#12325042)
Lists aren't immutable in Lisp, though. More precisely, Lisp doesn't have lists: it has chains of mutable cons cells.
Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @12:18AM (#12325178)
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.

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @12:43AM (#12325253)
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.
Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @03:52PM (#12328064)
I doubt that. I think it would take too long to work out the meaning of every piece of code you see from first principles. I think any competent programmer has a large collection of unconscious heuristics they use to understand code. Learning to write code in such a way that the reader's heuristics will not mislead them is, I think, a big part of becoming a software engineer.

I was just trying to describe the state of practice in the Lisp world. I do agree that Lisp benefits from more functional data structures -- that's why I wrote FSet [0]! I would point out, though, that since Lisp lacks any kind of access control, there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures. It would be a stupid thing to do, and everybody knows that, but the language doesn't prevent it. So the situation is not that different with FSet collections than it is with lists of unknown provenance.

Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection. Most people know that they should play games like that only in very specific circumstances.

[0] https://github.com/slburson/fset

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @04:11PM (#12328127)
> I think it would take too long to work out the meaning of every piece of code you see from first principles.

Just as in mathematics, once you've proven something, you can reuse the result as often as you want. But “the community always does this” isn't a proof.

> I do agree that Lisp benefits from more functional data structures (...) there's nothing besides common sense and convention that prevents FSet client code from mucking about inside the guts of the FSet data structures.

Then Lisp doesn't have functional data structures. That's no surprise, Lisp has no more compound values than Python or Ruby do - that is, none.

> Even in languages that nominally support access control, like C++ and Java, you can usually still get around it with casting or reflection.

Standard ML actually has type abstraction, and, once you've made something abstract, there's no way clients can inspect it. No downcasts, no reflection, no anything - abstract means abstract.

Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @05:10PM (#12328322)
> Then Lisp doesn't have functional data structures. That's no surprise, Lisp has no more compound values than Python or Ruby do - that is, none.

Ah, the arrogance of youth.

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @05:35PM (#12328382)
It isn't arrogance, it's just the semantics of the programming languages in question. Programming languages being such fundamental tools, you would think every programmer should understand them well, but that is far from being the case. It is tempting to blame programmers, but the real culprit is the subtlety and depth of the topic. Two great resources to get started are https://www.amazon.com/dp/0262201755/ and https://www.amazon.com/dp/0262690764/

Anyway. A value is something you can bind to a variable. Unfortunately, you can't bind the list [1,2,3] (or whatever syntax you might prefer) to a variable in either Python or Lisp, because those languages simply don't have lists (or any other kind of compound value).

Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @07:23PM (#12328741)
I read back through your recent comments. I notice you get downvoted a lot. Does this bother you?
Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @07:47PM (#12328818)
I don't particularly mind.
Re:Python Lists vs. Tuples by jholman on Saturday August 20, 2016 @12:25AM (#12325200)
In my understanding, in LISP-59, the only list-modification symbols are FIRST and REST. This makes me want to claim that in the one true Lisp, there are no mutable cells.

Actual useful implementations of Lisp, of course, may vary.

edit: s/list/Lisp/ in a particular place

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @12:45AM (#12325262)
Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction.

Yet somehow it lets you distinguish between “this (list 1 2 3)” and “that (list 1 2 3)”. Distinguishing between copies of the same value isn't “useful”, it's a pain, because you need to jump to a metalanguage (say, Hoare logic) to get the values you actually want.

Re:Python Lists vs. Tuples by ScottBurson on Saturday August 20, 2016 @04:02PM (#12328095)
> Does it make sense to distinguish between “this 2” and “that 2”? Of course not! And indeed Lisp doesn't let you make that silly distinction.

It does, actually, if the integer is large enough:

  > (ash 1 100)
  1267650600228229401496703205376    ; 2 ^ 100
  > (eq (ash 1 100) (ash 1 100))
  NIL
This is why you should use 'eql', not 'eq', to compare integers. But again: Lisp programmers have to know that. We're back to culture and convention.

So much the worse for Lisp, I suppose you would say, and perhaps you have a point. Lisp is not Haskell.

I don't entirely disagree with you; it would be nice if Lisp had an immutable list type. (Like FSet seqs [0].) But again, in practice, it's not as much of a deficiency as you seem to think.

[0] https://github.com/slburson/fset

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @05:06PM (#12328308)
> It does, actually, if the integer is large enough: (snippet)

Wow, this is even more broken than I previously thought.

> Lisp is not Haskell.

Haskell is broken too, only in a different way: Since when does it make sense to have a value that's simultaneously a number, a string, a function and pretty much anything else imaginable? (`undefined`)

> But again, in practice, it's not as much of a deficiency as you seem to think.

It causes difficulties when you want to reason rigorously about your code.

Re:Python Lists vs. Tuples by lispm on Saturday August 20, 2016 @05:25PM (#12328356)
> It causes difficulties when you want to reason rigorously about your code

That's what he said. In practice it doesn't matter.

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @05:37PM (#12328392)
> In practice it doesn't matter.

I reason rigorously about my code in practice.

Re:Python Lists vs. Tuples by tome on Saturday August 20, 2016 @07:22PM (#12328738)
I still haven't fully grasped what aspect of Haskell means you can't rigorously reason about your code.

I'm pretty sure you don't mean space leaks, and I'm pretty sure you don't mean global coherence of type classes, which are the two most popular complaints about reasoning about Haskell.

Other than that, can't you just say "this piece of code is at least as defined as the equivalent in a strict language" and leave it at that? What can go wrong?

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @07:49PM (#12328823)
> I still haven't fully grasped what aspect of Haskell means you can't rigorously reason about your code.

Oh, that particular criticism wasn't aimed at Haskell, but rather at languages without compound values. And I never said you can't reason rigorously about code written in such languages. You can, but it isn't very pleasant.

> I'm pretty sure you don't mean global coherence of type classes, which are the two most popular complaints about reasoning about Haskell.

Far more serious one: Haskell doesn't have a type whose value inhabitants are the integers and nothing else. I would like to say “even Lisp has that”, but nope, it doesn't either: https://news.ycombinator.com/item?id=12328095

Re:Python Lists vs. Tuples by tome on Sunday August 21, 2016 @03:26AM (#12329839)
> Haskell doesn't have a type whose value inhabitants are the integers and nothing else

Sure, I get that, but I don't get the practical consequences for reasoning. In Haskell, if you write

    myIntFunction !x = expression
then within expression x is an integer and nothing else, the same as if you'd written

    let myIntFunction x = expression
in OCaml. So I understand how it differs theoretically. I don't understand how it differs practically.

What's an example of something you wanted to prove in Haskell but couldn't, because it wasn't strict?

Re:Python Lists vs. Tuples by catnaroek on Sunday August 21, 2016 @09:26AM (#12330849)
> Sure, I get that, but I don't get the practical consequences for reasoning.

(0) In a language without compound values, you need to manually prove that object states faithfully represent the compound values you care about.

(1) In a dynamically typed language, you need to manually prove that computations produce the classes of values that their continuations expect.

(2) In a lazy language, you need to manually prove that variables will never be substituted with nonterminating computations.

> What's an example of something you wanted to prove in Haskell but couldn't, because it wasn't strict?

All the usual type class laws, without the pesky addendum “assuming no free variables are ever substituted with bottom, globally”. (In all fairness, strictness alone doesn't fix the problem either. At least not when laws have free variables of function type.) Redefining what variables can be substituted with is redefining the language's operational semantics, which in turn is effectively creating a new programming language. You would have to prove all the usual things from scratch: that type checking is decidable, that the type system is sound, etc.

In practice, I can still prove the things I want, but the proofs themselves are less modular in a lazy language. The problem manifests itself when you build large computations from smaller ones:

(0) In a strict language, whether any of the subcomputations terminates is a local issue, and doesn't affect the other subcomputations.

(1) In a lazy language, failure of one computation to be productive may be observed as a termination problem in a different computation.

Re:Python Lists vs. Tuples by lispm on Saturday August 20, 2016 @06:53PM (#12328615)
I don't.
Re:Python Lists vs. Tuples by ScottBurson on Sunday August 21, 2016 @03:23PM (#12332299)
> Wow, this is even more broken than I previously thought.

I don't agree [#]. Providing a predicate that tests for identity of implementation enables a useful class of optimizations. For example, if you know two sets are implemented by the same object, you don't need to compare their contents to know they're equal. The fact that the information can be misused doesn't make it useless. Non-leakiness of abstractions isn't an unalloyed good.

In fact, because all computations take time and space, no abstraction can be perfectly leak-free.

[#] Except if you want to make the point that the Lisp builtin function currently called 'eql' should have been called 'eq', and the function currently called 'eq' should have been called 'identical-objects-p' or some such long and explicit name. Formally this makes no difference, of course, but as a practical matter it makes erroneous usage of the latter much less likely and easier to spot.

> It causes difficulties when you want to reason rigorously about your code.

In practice, these are relatively minor. Consider for example my FSet collections library. One of the preconditions in the contract of each FSet operation is, of course, that the invariant required for correct operation holds on the object(s) on which the operation is invoked. Suppose we have proven, for each operation, that it correctly implements its contract: if the invariant holds on the argument(s), it holds on the return value.

So now we have an application, a complete program that uses FSet as a library. Among the many things we need to prove is that the preconditions of each FSet operation used in the application are satisfied. Because we've already proven that the FSet operations maintain the required invariant, we need to prove that nothing else in the program breaks that invariant. In a language with unbreakable access control, this would be trivial: no other code has access to the internals of these data structures. In Common Lisp, we have a little more work to do. We have to show that no other code invokes the FSet internal accessors by name; a few calls to 'grep' suffice for this. Then we have to show that there's no chance the code uses Lisp's reflective features to invoke these accessors indirectly: specifically, that no calls to 'intern' exist in the program that could return a symbol that names one of these accessors. This is probably easy. If the program calls 'intern' at all, it probably passes a constant string as the name of the package to intern into, so all we need to show is that that string is not equal to "FSET". If the package name is not constant, this starts to get a little harder, but (a) this is a rare case, and (b) if we can't easily prove that the possible package names come from a small, restricted set, the program probably has a security vulnerability and needs to be fixed anyway.

That's nonzero effort, I concede. But on the scale of all the things we have to do to verify our application, it's fairly trivial.

By way of contrast, let's look at what happens in languages where the default integer type has bounded precision. Now, to figure out the range of inputs over which some procedure satisfies its desired contract, we have to work backwards from each integer operation, looking at the range of values that would cause it to overflow, and figuring out what constraints that places on the inputs. This task can be quite difficult in complicated cases, and even in simple ones, the need to do it is easily overlooked (as shown by a famous example [0]).

I note that even your beloved SML doesn't mandate arbitrary-precision integers [1]. I can't even find, on its Web site, anything saying whether SML/NJ has them or not. Perhaps they are now considered a de facto requirement for a usable SML implementation -- in which case, you see, culture matters.

Look. Formal verifiability is a concern of mine too, and I understand where you're coming from. But this is not a black-and-white world, and practical considerations are also relevant. While language (mis)features do sometimes contribute to the difficulty of verification, most of that difficulty, I strongly suspect, comes from the complexity of the code itself. We could verify machine language programs if we wanted to, and though it would be harder, I can't believe it would be overwhelmingly harder.

[0] https://research.googleblog.com/2006/06/extra-extra-read-all...

[1] http://sml-family.org/Basis/integer.html

Re:Python Lists vs. Tuples by catnaroek on Sunday August 21, 2016 @08:47PM (#12333468)
> I don't agree [#]. Providing a predicate that tests for identity of implementation enables a useful class of optimizations. For example, if you know two sets are implemented by the same object, you don't need to compare their contents to know they're equal. The fact that the information can be misused doesn't make it useless. Non-leakiness of abstractions isn't an unalloyed good.

You can have identity equality in Standard ML (resp. Haskell) too, it's just a matter of using the right types: a `foo` (resp. `Foo`) has structural equality, but a `foo ref` (resp. `IORef Foo`) has object identity equality. More precisely, equality is always structural, and identity equality is the right notion of structural equality for reference cells. So absolutely nothing is lost w.r.t. what you have in Lisp or Python. And you gain actual compound values.

> In practice, these are relatively minor. Consider for example my FSet collections library. One of the preconditions in the contract of each FSet operation is, of course, that the invariant required for correct operation holds on the object(s) on which the operation is invoked. Suppose we have proven, for each operation, that it correctly implements its contract: if the invariant holds on the argument(s), it holds on the return value.

Have you ever actually proving things about code? It's far from a “minor thing” when every operation has unchecked preconditions that you need to manually verify every time you call a function. The only reason why I can prove things about my code at a reasonable scale is that I arrange things so that I have to manually prove relatively little, and the rest automatically follows from type safety and parametricity.

> (next paragraph)

You use the word “probably” a lot. An argument that uses the word “probably” can't convince me that a proposition is true in all of the cases.

> I note that even your beloved SML doesn't mandate arbitrary-precision integers [1].

Hand-rolling big integers using machine integers as the starting point is easy in Standard ML. The final step is very important: Using abstract types, I hide the representation of big integers from the rest of the program. As far as clients care, they are using big integers, not lists of machine integers, vectors of machine integers, or whatever. Unfortunately, this final step is impossible to perform in Lisp.

> I can't even find, on its Web site, anything saying whether SML/NJ has them or not.

I don't use SML/NJ, because it has a lot of broken extensions that are difficult to reason about, and it uses a questionable external language to automate builds, rather than SML itself. Instead I use Poly/ML and Moscow ML. Both have big integers.

> Perhaps they are now considered a de facto requirement for a usable SML implementation -- in which case, you see, culture matters.

Big integers are great help, but they aren't considered a de facto requirement. The only requirements are those in the Definition of Standard ML and the Standard ML Basis Library. As I said above, using abstract types, you can roll your own non-leaky big integer abstraction.

> While language (mis)features do sometimes contribute to the difficulty of verification, most of that difficulty, I strongly suspect, comes from the complexity of the code itself.

And the complexity of the code itself comes from the discrepancy between your problem domain and what you can readily express in your programming language.

> We could verify machine language programs if we wanted to, and though it would be harder, I can't believe it would be overwhelmingly harder.

Well, you are overwhelmingly wrong, unless you hand-wave away a significant chunk of your proof obligation.

Re:Python Lists vs. Tuples by jholman on Saturday August 20, 2016 @12:50AM (#12325277)
I don't understand what this has to do with whether or not lists are mutable in lisp.

It's possible that you were misled by a silly typo in my comment, which I have just fixed.

With that in mind, could you clarify?

Re:Python Lists vs. Tuples by catnaroek on Saturday August 20, 2016 @12:50AM (#12325282)
> I don't understand what this has to do with whether or not lists are mutable in lisp.

Lists aren't mutable in any language. A list is a sequence of elements. A different sequence is a different list. Some languages simply don't have lists.

Re:Python Lists vs. Tuples by autokad on Friday August 19, 2016 @11:35PM (#12325054)
no, how do they manage to O(1) by making them immutable? the only way to add to a list would be to create a new one with the extra value added? I'd be very surprised if they had the same performance as a mutable list
Re:Python Lists vs. Tuples by colanderman on Saturday August 20, 2016 @12:10AM (#12325161)
Singly-linked lists are a fundamental computational structure. A singly-linked list is simply an item and a pointer to another singly-linked list. To add an item, simply create a new singly-linked list with that item and a pointer to the old list. Since you are not copying data, this is O(1).

Read more here: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list...

If this interests you, read also about tree structures such as red-black trees. These kinds of structures support all operations that mutable structures support in O(log n) time. Of course mutable structures can always be faster, but immutable structures are far better than linear time.

Re:Python Lists vs. Tuples by jholman on Saturday August 20, 2016 @12:22AM (#12325194)
Singly-linked lists are a fundamental computational structure, and I'm not disagreeing with anything in the spirit of your comment, but I want to point out that linked lists are pretty much never the right implementation choice for an application programmer unless you're working in a language with no decent stdlib and you also care hugely about every byte of RAM/storage/etc. Which does happen, but is not very common, in practice.

For the benefit of the GP, what might be non-obvious about the way colanderman describes this, is that if you want lists that are cell-immutable but are resizeable with O(1) push() and pop(), you do your pushing and popping off the front of the list. So the pointer to the old list is still a valid pointer to its previous state. And at this point, yeah, go off and read the WP link. :)