Analysis of pointer "rotation" (1982) [pdf] (dl.acm.org)

This paper talks about how rotation of pointers can result in simpler (and potentially less error-prone) programs than sequential assignment when implementing algorithms that mutate linked structures; they go on to talk about some properties of rotations. They first talk about reversing linked lists, since that's the simplest example, but also other algorithms.

For example, to reverse a linked list in C, you could implement it like this:

  struct node *reverse(struct node *head) {
      struct node *prev, *cur, *next;

      prev = NULL;
      for (cur = head; cur != NULL; cur = next) {
          next = cur->next;
          cur->next = prev;
          prev = cur;
      }
      return prev;
  }

But given some macro for a left rotation (for 3 pointer variables) it could be implemented like this in C:

  struct node *reverse(struct node *head) {
      struct node *prev = NULL, *cur;

      cur = HEAD;
      while (cur != NULL)
          LEFT_ROTATE_3(cur->next, prev, cur);
      return prev;
  }

(The fact that they mentioned this was pretty cool to me, as just recently, I had realized on my own that you could implement a list reversal function in Common Lisp using the rotatef macro, which does the same thing; implementation is below [1]);

They also show off how you could write the Deutsch-Schorr-Waite List Marking algorithm. In case it's hard to understand their code, which is in Guarded Command Language [0], I translated their DSW algorithm into pseudo-C.

  // root points to the root of the list structure to be marked
  // x points to a parent of z
  DSW(root) {
      z = root;
      x = NULL;
      while (true) {
          if (z != NULL && z->m == 0) {
              z->m = 1;
              LEFT_ROTATE_3(z, z->head, x);
          } else if (x != NULL && x->fl == 0) {
              x->fl = 1;
              LEFT_ROTATE(x->head, z, x->tail);
          } else if (x != NULL && x->fl == 1) {
              LEFT_ROTATE_3(x, x->tail, z);
          } else {
              break;
          }
      }
  }

[0]: https://en.wikipedia.org/wiki/Guarded_Command_Language

[1]: List reversal in Common Lisp using the rotatef macro:

  (defun destructive-reverse-list (list)
    (do ((prev nil) 
         (cur list))
        ((null cur) prev)
      (rotatef (cdr cur) prev cur)))

  1> (let ((s (copy "dog: bit person?")))
       (rotate [s 0..3] [s 5..8] [s 9..15])
       s)
  "bit: person dog?"

  1> (let ((s "dog: bit person?"))
       (match `@a: @b @c?` s
         `@b: @c @a?`))
  "bit: person dog?"

  2> (let ((s "dog: bit person?"))
       (match `@{a 3}@{q 2}@{b 3} @{c 6}@p` s
         `@b@q@c @a@p`))
  "bit: person dog?"