Assignment in Lisp

Question

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?

Do you have experience programming in any other languages? I don't ask to be patronizing, but if you've whitened with other languages, sometimes it's easier to express an analogy in one of those. Eg,would you see why int x = someArray[3]; x = 42; wouldn't update any values in the array? — Joshua Taylor
– Joshua Taylor, Commented Oct 17, 2015 at 15:38
Well, I've programmed in Scheme before, but it's some years ago. In language like C++, it's much more clear to me how the assignment works. I find it more difficult in Scheme and Lisp. — JNevens
– JNevens, Commented Oct 17, 2015 at 15:40
did my example get the point across though? I.e., that array[i] = 42; updates the array, whereas int x = array[i]; x = 42; doesn't? It's essentially the same thing; you're updating the value of a variable, the place that you originally read a value from. — Joshua Taylor
– Joshua Taylor, Commented Oct 17, 2015 at 17:44

Rainer Joswig · Accepted Answer · 2015-10-18 00:14:16Z

4

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...

edited Oct 18, 2015 at 0:14

answered Oct 17, 2015 at 16:10

Rainer Joswig

140k11 gold badges230 silver badges357 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

JNevens Over a year ago

I am considering to change my-object to a struct. Is it possible to have a slot of a struct be another struct, e.g. a node with a slot 'left' that's also a node, or my-object with a slot that's a node?

Rainer Joswig Over a year ago

@JNevens: you can put anything into a slot.

Joshua Taylor · Accepted Answer · 2015-10-18 01:08:52Z

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)

Collectives™ on Stack Overflow

Assignment in Lisp

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related