This paper talks about how rotation of pointers can result in simpler (and potentially less error-prone) programs than sequential assignment when implementing a

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