3 ms·

Analysis of pointer "rotation" (1982) [pdf]

1 points by trealira 2y ago

trealira 2y ago
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)))
- kazinator 2y ago
  In TXR Lisp you can do: 1> (let ((s (copy "dog: bit person?"))) (rotate [s 0..3] [s 5..8] [s 9..15]) s) "bit: person dog?"
  - trealira 2y ago
    That does seem handy for string manipulation.
    - kazinator 2y ago
      Less than you might think, though. We usually want to be doing complex string transformation functionally (destructuring the original string and synthesizing the new one). 1> (let ((s "dog: bit person?")) (match `@a: @b @c?` s `@b: @c @a?`)) "bit: person dog?" Or by hard positions like before: 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?"

1 points by trealira 2y ago

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

kazinator 2y ago
In TXR Lisp you can do: 1> (let ((s (copy "dog: bit person?"))) (rotate [s 0..3] [s 5..8] [s 9..15]) s) "bit: person dog?"
- trealira 2y ago
  That does seem handy for string manipulation.
  - kazinator 2y ago
    Less than you might think, though. We usually want to be doing complex string transformation functionally (destructuring the original string and synthesizing the new one). 1> (let ((s "dog: bit person?")) (match `@a: @b @c?` s `@b: @c @a?`)) "bit: person dog?" Or by hard positions like before: 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?"