Safe mutation of a circular list

Learning
1

For part 2 of today’s (day 17) of Advent of Code, although there’s a much smarter way to do it, I replaced some slow Array-backed code with fast-insert code using a circular list. Which required mutation. Which resulted in a bug: my initial test code gave correct answers, but subsequent uses of this code started to lie.

…

I’m giving you this time so that you can emotionally prepare yourself, after hearing “circular list” and “mutation”. There will also be OO objects.

…

class spinlock steps =
  object (self)
    val mutable buffer = (let rec list = 0 :: list in list)
    val mutable zero = []
    val mutable n = 1
    val steps = steps
    method buffer = buffer
    method zero = zero
    method show =
      Printf.printf "(%d)" (List.hd buffer);
      for i = 1 to 3 do
        Printf.printf " %d" (List.nth buffer i);
      done; print_newline ()
    method step = for i = 1 to steps do buffer <- List.tl buffer done
    method insert =
      self#step;
      Obj.set_field (Obj.repr buffer) 1 (Obj.repr (n :: (List.tl buffer)));
      buffer <- List.tl buffer;
      n <- n + 1
    initializer zero <- buffer
  end
  
let part0 =
  let p = new spinlock 3 in
  p#show;
  p#insert;
  p#show;
  p#insert;
  p#show;
  p#insert;
  p#show;
  p

let part1 =
  let p = new spinlock 301 in
  for i = 1 to 2017 do
    p#insert
  done;
  p#show;
  p

part1 gives different output depending on whether part0 happens (as it does above) or not (as when it is commented out).

I guessed that buffer was getting shared between the spinlocks and was able to avoid the bug, getting correct answers, by passing an initial value:

class spinlock steps init =
  object (self)
    val mutable buffer = (let rec list = init :: list in list)
...

But this seems like something that only accidentally works. Is there a more reliable way to ensure that each spinlock is mutating its own private list?

2

First, I need to voice few advices:

  • avoid objects
  • forget the very existence of Obj

More precisely, objects in OCaml are mostly useful for inheritance and open recursion, and you are not using any of the object features in your code, so you should stick with records. Similarly, you should consider the Obj module as a license for the compiler to break your code in any way it likes. Particularly mutatings immutable datatype is a very bad idea; and this is the source of your issue. If you want a mutable circular list type, you should define it yourself, for instance

let 'a eventually_cycle = { elt: 'a; mutable next: 'a eventually_cycle }

Replacing your buffer with this type solves your problem by avoiding mutating a global immutable shared state.

5 Likes
3

Thanks. I’m embarrassed to say that making my own type occurred to me very early in the process. I guess I found the magic method too quickly and went with it, since it’s slightly fun in itself and this was just some quick contest code.

I rewrote the code with a record type and it’s just as fast, no longer has the bug, and the code is even cleaner-looking. So lesson learned :slight_smile:

1 Like