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 defstruct:

> (defstruct state score children val something-else)
STATE
> (setq initial-state (make-state :score 0 :children nil :val 0 :something-else nil))
#S(STATE :SCORE 0 :CHILDREN NIL :VAL 0 :SOMETHING-ELSE NIL)
> (state-score initial-state) ; current score
0
> (setf (state-score initial-state) 10) ; set new score
10
> (state-score initial-state) 
10

Answer 2

This happens because setf is a macro. When you define state-score as a macro, setf sees:

(setf (nth 2 state) value)

And knows what to do since it can use nth as a place to store values. On the other hand, when state-score is a function, setf just sees a value returned, and can't do anything about it.

Read more about how setf works and its concept of places for a deeper understanding. Here's an interesting tutorial that says:

The setf special form uses its first argument to define a place in memory, evaluates its second argument, and stores the resulting value in the resulting memory location

Answer 3

You can use something like this:

(defun get-score (state)
  (nth 0 state)) ; This corresponds to the comments in the init function

(defun set-score (state new-value)
  (setf (nth 0 state) new-value))

(defsetf get-score set-score)

This way, any time you write (setf (get-score something) else) it will be translated to (set-score something else).

Answer 4

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.