Arc Forum | Hmm, I think the confusion has to do with the assignment in the first step rathe...

Arc Forum

1 point by akkartik 4177 days ago | link | parent

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 :)

2 points by dram 4177 days ago | link

The first assignment has no confusion.

I think insort should modify the list, not merely assign a new list.

Some demo code:

  (def insort1 (test elt seq)
    (if (no seq)
         (list elt)
        (test elt (car seq))
         (with (first (car seq) rest (cdr seq))
          (scar seq elt)
          (scdr seq (cons first rest)))
        (no (cdr seq))
          (scdr seq (list elt))
        (insort1 test elt (cdr seq))))
  
  (mac insort (test elt seq)
    `(do (insort1 ,test ,elt ,seq) ,seq))

-----

3 points by fallintothis 4176 days ago | link

Your version doesn't quite work as-is:

  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. :)

-----

2 points by dram 4176 days ago | link

Good catch.

About the nil problem, maybe we should nil terminate list this way: (1 2 nil), instead of (1 2 . nil). just a joke. :)

Anyway, mutable pair is just a mess, I feel I have some understanding why Racket get rid of set-car! and set-cdr!.

-----

1 point by akkartik 4176 days ago | link

"..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.

-----