How can I SETF an element in a tree by an accessor?

Question

We've been using Lisp in my AI course. The assignments I've received have involved searching and generating tree-like structures. For each assignment, I've ended up writing something like:

(defun initial-state ()
  (list 
    0    ; score
    nil  ; children
    0    ; value
    0))  ; something else

and building my functions around these "states", which are really just nested lists with some loosely defined structure.

To make the structure more rigid, I've tried to write accessors, such as:

(defun state-score ( state )
  (nth 2 state))

This works for reading the value (which should be all I need to do in a nicely functional world. However, as time crunches, and I start to madly hack, sometimes I want a mutable structure). I don't seem to be able to SETF the returned ...thing (place? value? pointer?).

I get an error with something like:

(setf (state-score *state*) 10)

Sometimes I seem to have a little more luck writing the accessor/mutator as a macro:

(defmacro state-score ( state )
  `(nth 2 ,state))

However I don't know why this should be a macro, so I certainly shouldn't write it as a macro (except that sometimes it works. Programming by coincidence is bad).

What is an appropriate strategy to build up such structures?

More importantly, where can I learn about whats going on here (what operations affect the memory in what way)?

Answer 1

Use CLOS for data structures

The best way out of this is to quickly learn the basics of CLOS.

(defclass state ()
  ((score    :accessor state-score    :initform 0)
   (children :accessor state-children :initform nil)
   (value    :accessor state-value    :initform 0)))

(defun make-initial-state ()
  (make-instance 'state))

(defparameter *state* (make-initial-state))

(setf (state-score *state*) 10)

For most application code avoid structures

For most code avoid structures - use them only when you need them and know why. Use CLOS classes instead.

DEFSTRUCT also works with lists

If you really want to use lists, one option is to use the DEFSTRUCT macro with lists and have it define all the functions:

(defstruct (state (:type list))
  (score 0)
  (children nil)
  (value 0))

Above, the :type option tells DEFSTRUCT to use a list instead a structure.

? (defparameter *state* (make-state))
*STATE*
? (setf (state-score *state*) 10)
10

(make-state) returns a list of three items.

We can write setter functions

If you want to write code by hand, then you can write setter functions:

(defun get-my-score (state)
  (first state))

(defun (setf get-my-score) (score state)
  (setf (first state) score))

Above defines a SETF function. The name of the function is actually a list. The parameters for this function have to be first the new-value and then the thing to set.

? (setf *state* (list 0 nil 0))
(0 NIL 0)
? (setf (get-my-score *state*) 10)
10
? *state*
(10 NIL 0)

The Common Lisp HyperSpec defines what places are and how to work with them. I would guess that this is not the best source to learn from and possibly it is best explained in some introductory Lisp book.