Feeds:
Posts
Comments

Posts Tagged ‘defstruct’

Of the languages I know, emacs-lisp is unusual in that when you need to access the field of a structure, you need to know the name of the type1.

(defstruct person age name)
(defvar dave (make-person))
(setf (person-age dave) 20) ;; getter specifies the type!
(setf (person-name dave) "David Jones")
(message (person-name dave)) ;; -- David Jones

Notice I can't say (age dave) here, it has to be (person-age ...).

The underlying reason for this is that structures are really vectors. (person-age object) translates into (aref object 1) which should hopefully be pretty fast. Another structure doesn't need to keep its age member at an offset of 1, so I can't say it is (generic-structure-age object).

In basic perl objects, because they are really just a hash reference, I don't need to specify the type. When it is needed, the VM figures it out at runtime.

package Person;

sub new
{
    bless {}, $_[0];
}

package main;

my $dave = Person->new(); # Type specified here
$dave{'age'} = 20;        # but not here
$dave{'name'} = 'David Jones';

print $dave{'name'}, "\n";
$ perl t.pl
David Jones

In many statically typed languages, the fact that the compiler knows what the type is enables it to generate efficient code. I still don't need to specify it explicitly.

#include 
#include 

using namespace std;

struct person
{
    int age;
    string name;
};

int main()
{
    person dave;

    dave.age = 20;             // No type explicitly specified here
    dave.name = "David Jones"; // or here

    cout << "Name: " << dave.name << "\n";
}
$ g++ t.cpp
$ ./a.exe
Name: David Jones
$

For objects created using the new version of defstruct* I've defunned a get-field and set-field that don't require the type to be specified. Error checking is, as usual, elided

(defsubst get-index (object field)
  (cdr (assoc field (symbol-value (aref object 1)))))

(defun get-field (object field)
  (aref object (get-index object field)))

(defun set-field (object field value)
  (setf (aref object (get-index object field)) value))

(get-field dave 'name)
(set-field dave 'name "Simon Smith")

Although by this time we're probably both wondering why I didn't just use a hash like all the (other) scripting languages.


1. To be more accurate, you need to tell the computer what the type is. Obviously, if you want to do something useful with an object, you generally need to know what type it is anyway.

Read Full Post »

I am a student of the design your data structures first school of programming1. 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 :)

Read Full Post »

Follow

Get every new post delivered to your Inbox.