This is a tricky one! Turns out you're absolutely right, actually, this is sort of a bug (if you expect a different behavior of the function insert-sorted).
You're right in thinking that x and y share the same reference, like
The thing is, the only real way to get at pointers in Arc is to use sref, scar and scdr. Those will actually mutate the cons cell sitting in memory. We can verify this, plus the fact that x and y share the same reference, by using (say) scar:
arc> (= y (= x '(1 3 5)))
(1 3 5)
arc> x
(1 3 5)
arc> y
(1 3 5)
arc> (macex '(= (car x) 2)) ; '= expands into a form that uses 'scar
((fn () (atwith (gs1731 x gs1732 2) ((fn (val) (scar gs1731 val)) gs1732))))
arc> (= (car x) 2)
2
arc> x
(2 3 5)
arc> y
(2 3 5)
The problem is that insort doesn't truly mutate the cons cell of its argument. It's a lazy-man's "destructive", because it uses the zap macro to reassign x to a separate, insorted version of the list:
arc> (= y (= x '(1 3 5)))
(1 3 5)
arc> (macex '(insort < 2 x))
(atomic-invoke
(fn ()
(withs (gs1736 x
gs1735 [insert-sorted < 2 _])
((fn (gs1737) (assign x gs1737))
(gs1735 gs1736)))))
Notice how the expansion calls insert-sorted on x, then uses (assign x ...) to change where x points. insert-sorted is just a normal, FP-style function that doesn't mutate its arguments, instead consing together a new list in memory:
Then the free-floating cons-cell from the insert-sorted, the old car (the 1), and the old cdr (the (3 5)) would all be garbage-collected eventually. (Modulo implementation details, of course, like the numbers actually sharing the same spots in memory instead of being duplicated. But it makes the diagram cleaner.)
Hmm, I think the confusion has to do with the assignment in the first step rather than the call to insort itself.
arc> (insort < 2 x)
(1 2 3 5)
arc> x
(1 2 3 5)
Here, x was modified in place. Does that seem as expected?
The real confusion is that y and x are not aliases. They just happen to be bound to the same value (cons cell) at the start. A destructive change to one doesn't affect the other.
Or, put another way, 'destructive' doesn't mean the original list is guaranteed to be destroyed. Just that it _can_ be modified. It would be destroyed if nothing else was using it and it got garbage-collected. The GC is the only entity actually doing destruction.
Am I addressing your question? This is a clarifying process to myself, at any rate :)
arc> (= y (= x '(1 3 5)))
(1 3 5)
arc> (insort < 2 x)
(1 2 3 5)
arc> x
(1 2 3 5)
arc> y
(1 2 3 5)
arc> (insort < 0 x)
(0 1 2 3 5)
arc> x
(0 1 2 3 5)
arc> y
(0 1 2 3 5)
arc> (insort < 6 x)
(0 1 2 3 5 6)
arc> x
(0 1 2 3 5 6)
arc> y
(0 1 2 3 5 6)
arc> (= y (= x nil))
nil
arc> (insort < 1 x)
nil
arc> x
nil
arc> y
nil
Here's a version I wrote for my own edification (basically, a more complicated version of yours):
(def destructive-cons (elt seq)
; Note: (push elt seq) won't work, because push is a macro on the "place",
; and seq isn't the proper "place" to mutate (push will just mutate the local
; binding of seq). This function will actually mutate the cons cell being
; pointed at by seq.
(let (first . rest) seq
(scar seq elt)
(scdr seq (cons first rest)))
seq)
(def insorter (test elt seq)
(if (no seq)
(list elt)
(test elt (car seq))
(destructive-cons elt seq)
(do1 seq
((afn (prev cell)
(if (or (no cell) (test elt (car cell)))
(scdr prev (cons elt cell))
(self cell (cdr cell))))
seq (cdr seq)))))
(mac insorted (test elt seq)
`(zap [insorter ,test ,elt _] ,seq))
Writing it made me realize the issues with making a "truly destructive" insort:
arc> (= y (= x '(1 3 5)))
(1 3 5)
arc> (insorted < 2 x)
(1 2 3 5)
arc> x
(1 2 3 5)
arc> y
(1 2 3 5)
arc> (insorted < 0 x)
(0 1 2 3 5)
arc> x
(0 1 2 3 5)
arc> y
(0 1 2 3 5)
arc> (insorted < 6 x)
(0 1 2 3 5 6)
arc> x
(0 1 2 3 5 6)
arc> y
(0 1 2 3 5 6)
arc> (= y (= x nil))
nil
arc> (insorted < 1 x)
(1)
arc> x
(1)
arc> y
nil
No matter how you try, there's still the edge case with nil, on which you can't scar/scdr.
arc> (= x nil)
nil
arc> (scar x 1)
Error: "set-car!: expected argument of type <pair>; given nil"
arc> (scdr x '(2))
Error: "set-cdr!: expected argument of type <pair>; given nil"
So it appears Arc's model of "places" can't really handle references/aliases that well. Indeed, push, swap, rotate, pop, pushnew, pull, togglemem, and the like are "broken", too, if we expect them to modify the _content_ of their arguments instead of simply where the arguments point. E.g.,
arc> (= y (= x '(a b c)))
(a b c)
arc> (= z (= w '(1 2 3)))
(1 2 3)
arc> (swap x w)
(a b c)
arc> x
(1 2 3)
arc> y
(a b c)
arc> z
(1 2 3)
arc> w
(a b c)
In a way, I can see that being the right behavior for swap, but not for insort. I suppose it's at least somewhat consistent: just alter your expectations of "destructive" operators, since they'll all (near as I can tell) just modify where their input "places" are pointing. Not that I'm ready to write off the issue that way, it's just I don't have a solution and think it gets complicated depending on the operators in question. :)
"..just alter your expectations of destructive operators.."
Yeah, I agree with this. I weakly think (without evidence) that arc's destructive ops are more functional, and it encourages a better style to not constantly make assumptions about precisely which cons cells go where.
On the other hand, a set of 'alias-friendly' functions could coexist with the existing primitives.
Hmm, I wonder if the notion of boxes would help build alias-friendly operations.
