Programming With Types

I am a student of the design your data structures first school of programming¹. My first proper language was C and in that language pretty much all you had was typedef struct and a handful of primitive types.

Despite the fact that I now spend most of my time programming with dynamic languages (emacs lisp and perl), I still believe it is important to think about your types before you start programming. Eh, but what’s that? Dynamic languages don’t have types? Au contraire mon ami. Not having static type-checking is not the same as not having types.

So, enough handwaving, what about a real example?

Extensible Vectors

In C++, one of the data structures I use most is the STL vector. But in emacs lisp, the vector is a very different animal as it doesn’t automatically extend. If I want an extensible vector type (an evector), I have to implement it myself (or find a library containing one, but that wouldn’t make a good example).

So, first of all, I need to know what pieces of information each evector will need. There will be the vector itself, plus the current end of the vector and the current size before we need to resize it. If we want to use fibonacci to get the next size of vector we need another slot for the fibonacci counter. So each evector will look like this:

['evector [...] <end position> <fib counter>]

The constructor is generally called make-<typename> so the implementation (assuming we want a vector that starts with 8 slots) is:

(defun make-evector ()
  (vector 'evector (make-vector 8 nil) 0 5))

We also need a predicate for checking if a variable is of type evector.

(defun evectorp (object)
  (eq (aref object 0) 'evector))

What does the push-back operation look like?

(defun evector-push-back (object elem)
  (let* ((vec (aref object 1))
         (pos (aref object 2))
         (len (length vec)))
    ;; increase the size of the vector if necessary
    (when (<= len pos)
      (let* ((new-size (+ len (aref object 3)))
             (new-vec (make-vector new-size nil))
             (i 0))
        ;; copy the original vector into the new one
        (while (< i len)
          (aset new-vec i (aref vec i))
          (incf i))
        (setq vec new-vec)
        (setf (aref object 1) vec)
        (setf (aref object 3) len)))
    ;; set the vector element and update end position
    (aset vec pos elem)
    (incf (aref object 2))))

Hmmm… referring to the member variables by position looks error prone and inflexible. What can we do about that?

If you’re thinking accessors, you’re on the right lines. Fortunately, because of setf, you only need a getter.

(edit: fixed, thanks Jisang)

(defsubst evector-data (object) (aref object 1))
(defsubst evector-end-position (object aref object 2))
(defsubst evector-fib-var (object aref object 3))

defstruct

But even better, there is a macro that does defines your constructor, predicate and accessors for you, defstruct.

(defstruct evector
  (data (make-vector 8 nil))
  (end-pos 0)
  (fib-var 5))

Yet another advantage of using defstruct, is that the error messages are clearer than with my basic accessors.

(evector-fib-var 'x)

[basic accessor]
Debugger entered--Lisp error: (wrong-number-of-arguments (lambda (object aref object 3)) 1)

[defstruct accessor]
Debugger entered--Lisp error: (error "evector-fib-var accessing a non-evector")
  signal(error ("evector-fib-var accessing a non-evector"))
  error("evector-fib-var accessing a non-evector")
...

edit: apologies to those who arrived from ironman perl. This isn’t a perl related post so I hadn’t tagged it as such. I didn’t realise that posts that mention perl anywhere get picked up.

---

1. Although it might not come across in my examples

About these ads