Page 1 of 2

pushing links, not elements

Posted: Thu Mar 05, 2009 4:12 pm
by beren
Hi there,

I am just starting with lisp and I can't figure out the following issue:

I want to push *not* elementos into a list, but its *references*, for example, if I write

Code: Select all

(let (
      (a '())
      (b '()))
  (push 1 a)
  (push a b)
  (push 2 a)
  (print a)
  (print b))
I get

Code: Select all

(2 1)                                                                     
((1))
and I would like

Code: Select all

(2 1)                                                                     
((2 1))
so, each time I modify a, b has to change too.
Is there a way to achieve that?

thanks!!

Re: pushing links, not elements

Posted: Thu Mar 05, 2009 7:05 pm
by schoppenhauer
In general, I see no way to achieve this.

Assume a=(0). When you push 1 to a, you will exchange a by (1 . (0)), then you replace b by ((1 . (0)) . b) and then you replace a by (2 . (1 . (0))).

You have to try it in a different way. One thing I could think of is to write an own push-macro which pushes the values on both lists. You could try to use structs which point to another object, and set this pointer to another value. Or to implement a similar data structure by your own.

I think there is no "trivial" way to do this.

Re: pushing links, not elements

Posted: Thu Mar 05, 2009 7:53 pm
by nuntius
Lisp is doing exactly as you ask... but not what you want.

Unfortunately, push *prepends* an object onto the list; you want appending behavior.

If [xy] is a cons cell and _ is nil, then a trace of your code looks like
a=_
b=_
a=[1a]=[1_]
b=[ab]=[[1_]_]
a=[2a]=[2[1_]]
where the lisp printer hides nil when it ends a list.

In the last step, A now points to a different object; B still points to the old A. If you want B to see the new definition of A, you must change the structure A refers to, not simply bind a new value to A...

Compare the following snippets
(let ((list (list 1 2))) (push 3 list))
(let ((list (list 1 2))) (nconc list (cons 3 nil)))

Try defining a push-back macro based on the second snippet...

- Daniel

Re: pushing links, not elements

Posted: Thu Mar 05, 2009 8:27 pm
by Harleqin
Let's look at how the cons cells point after each part:

Code: Select all

(let ((a '())
      (b '()))

Code: Select all

       
a --->  nil


b --->  nil

Code: Select all

  (push 1 a)

Code: Select all

        _______
a ---> |  1 | ---> nil
        ~~~~~~~

b ---> nil

Code: Select all

  (push a b)

Code: Select all

        _______
a ---> |  1 | ---> nil
        ~~~~~~~
          ^
        __|____
b ---> |  ! | ---> nil
        ~~~~~~~

Code: Select all

  (push 2 a)

Code: Select all

        _______     _______
a ---> |  2 | ---> |  1 | ---> nil
        ~~~~~~~     ~~~~~~~
                      ^
                    __|____
            b ---> |  ! | ---> nil
                    ~~~~~~~

Code: Select all

  (print a)
  (print b))
Now the output should be no surprise.

Re: pushing links, not elements

Posted: Fri Mar 06, 2009 1:59 am
by beren
Thank you for your replys,

I am sorry for the confusion, I know that I am getting what I am suppose, my question was if there is a way to handle something like pointers in C, which is normally done using * and &.
I guess you achieve that by a correct use of car's and cdr's. Because as nuntilus (aka daniel) suggest, doing

Code: Select all

(let (
      (a (list 1 2))
      (b '(bb)))
  (nconc b a)
  (nconc a '(1 2 3))
  (print a)
  (print b)
  )
gives

Code: Select all

(1 2 1 2 3)                                                                                                                                                  
(BB 1 2 1 2 3)
which is exactly what I wanted.
TY!!!!

Re: pushing links, not elements

Posted: Fri Mar 06, 2009 2:02 am
by Jasper
No references/pointers, although, often you should not be using them, i think lisp should have them. I have a project where i am working on a lisp with (among others) a better typing system, and i will put references/pointers in there.

Re: pushing links, not elements

Posted: Fri Mar 06, 2009 8:55 pm
by qbg
You can create/hack pointers and references in. For example, you could do something like: (untested)

Code: Select all

(defmacro make-pointer (variable)
  (let ((op (gensym))
        (value (gensym)))
    `(lambda (,op &optional ,value)
       (if (eql ,op 'set)
         (setf ,variable ,value)
         ,variable))))

(defun deref (pointer)
  (funcall pointer 'read))

(defun (setf deref) (value pointer)
  (funcall pointer 'set value))

Re: pushing links, not elements

Posted: Sat Mar 07, 2009 4:32 pm
by Jasper
Cool, didn't think of that, how does that compare performance-wise? You happen to know how loop/dolist do references?

Btw greatly miss with-gensyms, it should be in standard library, imo. (Same as a lot more macros/functions.)

Re: pushing links, not elements

Posted: Sat Mar 07, 2009 7:28 pm
by gugamilare
I think the better here would be to use a one-field structure

Code: Select all

(defstruct (pointer (:conc-name nil))
  ref)
Or to make it look like C (in a good way)

Code: Select all

(defstruct (pointer (:conc-name nil))
  &)

(let ((x (make-pointer :& 10)))
  (print (& x)) ; prints 10
  (setf (& x) 20)
  (& x)) ==> 20
I believe using structures would be much more clean and have better performance.

Anyway, a list is lisp is in fact a pointer, just like it would be written in C. I don't know if this is right, it's been a while...

Code: Select all

defstruct cons_cell {
  int car;
  cons_cell *cdr;
};

deftype cons_t *cons_cell;

cons_t cons(int a, cons_t b) {
  ... malloc (something); ...
}

int main() {

  cons_t a = NULL;
  cons_t b = NULL;

  a = cons(1, a);      // a points to a cons (1, NULL)
  b = cons(a, b);      // the car of b points to the same cons above
  a = cons(2, a);      // the car of b doesn't change, it still points to the same cons as before

}

Re: pushing links, not elements

Posted: Sat Mar 07, 2009 7:36 pm
by Jasper
Hmm while i was looking for a way to find the arguments of a macro i stumbled upon symbol-macrolet, the following should be able to prevent people needing to deref: (untested)

Code: Select all

(defmacro these-deref ((&rest vars) &rest body)
  `(symbol-macrolet (,@(loop for v in vars collect `(,v (deref ,v)))) ,@body)
(defmacro pointerize ((&rest vars)) ;Rest here is just handy fluff.
  `(let (,@(loop for v in vars collect (if (listp v) `(,(car v) (make-pointer ,(cadr v))) `(,v (make-pointer nil))))
      (these-deref (,@(loop for v in vars collect (if (listp v) (car v) v)))
         ,@body))
(defmacro pointerize-var ((&rest vars) &body body)
  `(pointerize (,@(loop for v in vars collect `(,v ,v)) ,@body)) 
@gugamilare: i associate using the first element of a list as a reference with pain. That might be because programming non-functionally can cause trouble, or just because i was not as good a programmer back then, though.