Arc Forumnew | comments | leaders | submitlogin
4 points by nex3 6138 days ago | link | parent

I don't see lists in Lisp as just sequences. Rather, I don't see cons cells as just sequences. They're so much more versatile than that, which is part of what gives Lisp its power (cue "hundred operations on one data structure" quote). They can be used as maps, trees, etc. I think it would be a mistake to say, "these are mostly the same as arrays, let's implement them as arrays most of the time." Cons cells aren't the same as arrays.

I guess you're right in that arrays have more-or-less a subset of the functionality that cons cells do. Maybe it would be a good idea to have lists as the default and switch to arrays under some circumstances (lots of indexing or index-assignment?). But I'm skeptical about this as well.

Also, I foresee some unexpected behavior if the transition between conc cells and arrays is entirely behind-the-scenes. For example:

  ; Suppose foo is an array acting like a cons cell
  (= bar (cons 'baz (cdr foo)))
  (scdr (cdr bar) 'baz)
Now we'd need to somehow update the foo variable to point to a cons cell rather than array. You could imagine this getting even more tricky, even incurring large unexpected cost, with many variables pointing at different parts of an array-list and one of them suddenly scdr-ing.


2 points by almkglor 6138 days ago | link

All of that solved by the unrolled-list mockup. It works, and works with scdr, no matter how many pointers point in the middle of otherwise-proper lists, and even works with lists split by scdr, handling both the parts before and after the scdr-split seamlessly. Costs are also not very large - mostly the added cost is in the search through cdr-table for the next highest key. That said the added cost is O(n) where n is the number of individual cons cells scdr has been used on.

So yes, the above code you show will add cost. But how often is it used in actual coding anyway? The most common use of cons cells is straight sequences, and quite a bit of arcn can't handle improper lists (quasiquote comes to mind) - yet arc is useful enough to write news.yc.

Edit: Come to think of it, for the common case where scdr completely trashes the old cdr of a cons cell (i.e. no references to it are kept), the linear lookup through cdr-table will still end up being O(1), since keys are sorted, and the earlier cdr-table entry gets found first.

-----