Lists, empty lists, mutation, and their vicissitudes

In trying to understand what insert does I looked at its help. Pretty embarrassing since there are least two changes since that help was created:

And it doesn't explain that a random place in a list can be after its end.

It is also sad that "insert item at random of output" is a very confusing "sentence".

I think quite a few blocks are confusing (due to the need to keep the text in the blocks as short as possible) and that experimenting with them is the best way to see exactly what they do

Also, keeping documentation up to do date has always been one of the three hardest problems in computer science :slight_smile:

There will be a big boost in the quality of the help screens when Jens pulls Dylan's help internationalization feature. But yes, I should spend less time playing kenken and more time working on documentation.

Another reason I was mystified by the insert solutions was that I thought that list() reported THE empty list. But

image

This is a surprise to anyone familiar with Lisp or Scheme.

And I just checked the manual and there are a couple references to "the empty list" instead of "an empty list".

The idea of performing side effects on an empty list is something that should be documented. It is impossible with linked lists but maybe it is better to think of Snap!'s lists as arrays.

When you and I were young, it was more or less a rule that the empty list had to be represented with a zero pointer. But later implementations used a pointer to an actual (unique) node as the empty list, because that turned out to be useful sometimes, and because a zero pointer can be caught as an error. But still, yes, in Lisp it's standard that all empty lists are EQ.

When we made linked lists -- and they're not arrays, except in the sense that each pair is an array of length 2 -- the question came up as to how to represent a/the empty list. At that time we were not contemplating mutation of linked lists (which is still the case; if you INSERT into a linked list it is turned into a dynamic array) and if mutation is ruled out, it doesn't really matter if empty lists are EQ. We provide an EMPTY? predicate that's true for empty lists and false for all other lists, whether linked or otherwise. (It throws an error for non-lists, also different from Lisp NULL?.) And I think that would be good enough even if we did mutate linked lists, apart from the part about surprising old people like us.

EDIT: Re-reading, I'm not sure I'm being clear. The point is, if we did allow mutation of linked lists, and you did an INSERT into an empty list, you'd get a (linked) list of length 1, which by definition would no longer be EQ to an empty list even in Lisp.

Right. But that is what is so strange about examples like page 36 of the manual:

image

result is initially an empty list and then add changes it to a list (which is a dynamic array).

This program can't be translated to Scheme if we think that list() is like () in Scheme or Lisp.

If there was one empty list, i.e.

, then I can set var a to [1, 2, 3] and var b to ["Alpha", "Bravo", "Charlie"];
they are different lists, even if they were to have the same items.
Adding/inserting an item to one list does not affect the other.
What if I cleared list a and list b?
Would they become the same identical list?
Would adding an item to one affect the other, or would the variable point to another list? If we did the same thing with two variables that point to the same list, would they end up not pointing to the same list?

list() is like (list). I don't think that's where your issue lies. It's with add, which isn't like anything in Lisp. It certainly isn't just set-cdr! (or rplacd if you're in that tribe). If you wanted to write something like it in Scheme, you'd have to do this:

(define (last-pair data)  ; from SICP
  (if (null? (cdr data))
      data
      (last-pair (cdr data))))

(define (add-to value data)
  (if (null? data)
      (cons value '())
      (set-cdr! (last-pair data) (cons value '()))))

The code looks a little unfamiliar because a Lispian would put the new value at the front, which doesn't require the last-pair business.

The SICP way to avoid special-casing the empty list is to start the list with a sentinel node:

(define (init-data)
  (set! data (cons 'sentinel '())))
(define (add-to value data)
  (set! data (cons value data)))
(define (values data)
  (cdr data))

But I still don't see what any of this has to do with requiring all empty lists to be EQ, because you can't set-cdr! an empty list.

Yes, clearly, if there's only one empty list.

The trouble is that you're asking about Snap!, whereas Ken and I are talking (mostly) about Lisp. In Lisp (any dialect), the word "list" means linked list. Linked lists can, as you know, share memory. In Lisp, if you mutate a list and two things point there, then yes, they both see the change you made. But mutation of lists is really frowned upon. Modern Lisps also provide arrays, which work just the way you expect.

In Snap!, though, we have essentially merged the concepts of "list" and "array." This terminological looseness started in Scratch, which uses the name "list" for what isn't really a list at all, but an array. (This also explains why INSERT and ADD are separate blocks, instead of, for example, having an option "before" or "after" in INSERT. Adding to an array is a straightforward concept, whereas inserting is a little complicated.) Our goal is to present users with a single data structure, named "list," that can be represented internally in two different ways. We don't really teach users the different ways (unless they ask awkward questions :~P); all we do is tell them that for any particular list, they should either mutate it Scratch-style or deal with it functionally, but not both (because that would do a lot of conversion between linked list and dynamic array internally).

So what really happens is that empty lists aren't EQ. Even for linked lists, the empty list at the end is a dynamic array of length zero.