CODEWITHSUNDEEP
lispcommon-lispassign
JNevens
JNevens

Reputation: 12012

Assignment in Lisp

I have the following setup in Common Lisp. my-object is a list of 5 binary trees.

(defun make-my-object ()
    (loop for i from 0 to 5
          for nde = (init-tree)
          collect nde))

Each binary tree is a list of size 3 with a node, a left child and a right child

(defstruct node
    (min 0)
    (max 0)
    (ctr 0))

(defun vals (tree)
    (car tree))

(defun left-branch (tree)
    (cadr tree))

(defun right-branch (tree)
    (caddr tree))

(defun make-tree (vals left right)
    (list vals left right))

(defun init-tree (&key (min 0) (max 1))
    (let ((n (make-node :min min :max max)))
        (make-tree n '() '())))

Now, I was trying to add an element to one of the binary trees manually, like this:

(defparameter my-object (make-my-object))
(print (left-branch (car my-object))) ;; returns NIL
(let ((x (left-branch (car my-object))))
    (setf x (cons (init-tree) x)))
(print (left-branch (car my-object))) ;; still returns NIL

The second call to print still returns NIL. Why is this? How can I add an element to the binary tree?

Upvotes: 0

Views: 637

Answers (2)

Joshua Taylor
Joshua Taylor

Reputation: 85913

Most of the code in this question isn't essential to the real problem here. The real problem comes in with the misunderstanding of this code:

(let ((x (left-branch (car my-object))))
  (setf x (cons (init-tree) x)))

We can see the same kind of behavior without user-defined structures of any kind:

(let ((cell (cons 1 2)))
  (print cell)            ; prints (1 . 2)
  (let ((x (car cell)))
    (setf x 3)
    (print cell)))        ; prints (1 . 2)

If you understand why both print statements produce (1 . 2), then you've got enough to understand why your own code isn't doing what you (previously) expected it to do.

There are two variables in play here: cell and x. There are three values that we're concerned with 1, 2, and the cons-cell produced by the call (cons 1 2). Variables in Lisp are often called bindings; the variable, or name, is bound to a value. The variable cell is bound to the the cons cell (1 . 2). When we go into the inner let, we evaluate (car cell) to produce the value 1, which is then bound to the variable x. Then, we assign a new value, 3, to the variable x. That doesn't modify the cons cell that contains the value that x was originally bound to. Indeed, the value that was originally bound to x was produced by (car cell), and once the call to (car cell) returned, the only value that mattered was 1.

If you have some experience in other programming languages, this is directly analogous to something like

int[] array = ...;
int x = array[2];    // read from the array; assign result to x
x = 42;              // doesn't modify the array

If you want to modify a structure, you need to setf the appropriate part of the structure. E.g.:

(let ((cell (cons 1 2)))
  (print cell)            ; prints (1 . 2)
  (setf (car cell) 3)
  (print cell))           ; prints (3 . 2)

Upvotes: 2

Rainer Joswig
Rainer Joswig

Reputation: 139411

The first function is just:

(defun make-my-object ()
  (loop repeat 5 collect (init-tree)))

Now you define a structure for node, but you use a list for the tree and my-object? Why aren't they structures?

Instead of car, cadr and caddr one would use first, second, third.

(let ((x (left-branch (car my-object))))
   (setf x (cons (init-tree) x)))

You set the local variable x to a new value. Why? After the let the local variable is also gone. Why aren't you setting the left branch instead? You would need to define a way to do so. Remember: Lisp functions return values, not memory locations you can later set. How can you change the contents in a list? Even better: use structures and change the slot value. The structure (or even CLOS classes) has following advantages over plain lists: objects carry a type, slots are named, accessors are created, a make function is created, a type predicate is created, ...

Anyway, I would define structures or CLOS classes for node, tree and object...

Upvotes: 4

Related Questions