About me

About me

Feeds

RSS feed

Pitfalls of destructive operations

31st August 2017

Suppose you want to implement a two-dimensional arrays using lists. For example, you might want to represent data as a two-dimensional array in a dialect of Lisp that doesn't include native support for arrays, such as Scheme, or my uLisp interpreter for the Arduino.

A non-destructive approach

First we need a function to construct an empty array. Here is a function makearray that recursively creates an x by y array and returns it. It uses a helper function makelist:

(defun makearray (x y e)
  (makelist x (makelist y e)))

(defun makelist (n e)
  (if (zerop n) nil (cons e (makelist (1- n) e))))

The third parameter, e, specifies the initial value of each element. Here's an example of its use:

> (setq c (makearray 3 4 0))
((0 0 0 0) (0 0 0 0) (0 0 0 0))

To access an arbitrary element of a two-dimensional array we use arrayref:

(defun arrayref (a x y)
  (nth y (nth x a)))

Changing an arbitrary element is a bit trickier. Here's one way using a function changearrayref, which uses a recursive helper function changenth:

(defun changearrayref (a x y n)
  (changenth a x
             (changenth (nth x a) y n)))

(defun changenth (list x n)
  (if (null list) nil
    (cons 
     (if (zerop x) n (car list))
     (changenth (cdr list) (1- x) n))))

Here's an example of its use on the array c we defined above:

> (changearrayref c 1 2 7)
((0 0 0 0) (0 0 7 0) (0 0 0 0))

Note that this is non-destructive; c still has its original value:

> c
((0 0 0 0) (0 0 0 0) (0 0 0 0))

The destructive alternative

We can write a destructive version of changearrayref much more easily, and this was my original attempt at solving this problem:

(defun setarrayref (a x y n)
  (setf (nth y (nth x a)) n))

I've called it setarrayref to distinguish it from the non-destructive version.

Trying this out:

> (setq d (makearray 3 4 0))
((0 0 0 0) (0 0 0 0) (0 0 0 0))

> (setarrayref d 1 2 7)
7

> d
((0 0 7 0) (0 0 7 0) (0 0 7 0))

Now something's gone seriously wrong – we wanted to change one element but we've ended up changing three. What's the explanation?

The answer is that makearray creates a list with shared structure; each occurrence of (0 0 0 0) in the result is actually a pointer to the same list, so changing one element of this list appears to change three occurrences in d.

One solution would be to use destructive operations, but to disallow creating lists with shared structure; however, shared list structure is one of the aspects of Lisp that makes it highly efficient in list and tree processing tasks.

Therefore the traditional approach to programming in Lisp is to avoid destructive operations, and only use them cautiously only when there's a significant performance benefit in doing so. As I found to my cost in this example, using them can introduce puzzling errors that are hard to track down.

By the way, the modification to makearray to ensure that it doesn't create a list with shared structure is:

(defun makearray2 (x y e)
  (mapcar #'copy-list (makelist x (makelist y e))))

I'd be interested in comments, or suggestions for improvements to the non-destructive version of changenth.


blog comments powered by Disqus