pushing links, not elements

Discussion of Common Lisp

pushing links, not elements

Postby beren » Thu Mar 05, 2009 4:12 pm

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!!
beren
 
Posts: 11
Joined: Thu Mar 05, 2009 4:08 pm

Re: pushing links, not elements

Postby schoppenhauer » Thu Mar 05, 2009 7:05 pm

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.
Sorry for my bad english.
Visit my blog http://blog.uxul.de/
schoppenhauer
 
Posts: 99
Joined: Sat Jul 26, 2008 2:30 pm
Location: Germany

Re: pushing links, not elements

Postby nuntius » Thu Mar 05, 2009 7:53 pm

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
User avatar
nuntius
 
Posts: 500
Joined: Sat Aug 09, 2008 10:44 am
Location: Burlington, MA

Re: pushing links, not elements

Postby Harleqin » Thu Mar 05, 2009 8:27 pm

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.
"Just throw more hardware at it" is the root of all evil.
Svante
Harleqin
 
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: pushing links, not elements

Postby beren » Fri Mar 06, 2009 1:59 am

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!!!!
beren
 
Posts: 11
Joined: Thu Mar 05, 2009 4:08 pm

Re: pushing links, not elements

Postby Jasper » Fri Mar 06, 2009 2:02 am

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.
Jasper
 
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands

Re: pushing links, not elements

Postby qbg » Fri Mar 06, 2009 8:55 pm

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))
qbg
 
Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

Re: pushing links, not elements

Postby Jasper » Sat Mar 07, 2009 4:32 pm

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.)
Jasper
 
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands

Re: pushing links, not elements

Postby gugamilare » Sat Mar 07, 2009 7:28 pm

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

}
gugamilare
 
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil

Re: pushing links, not elements

Postby Jasper » Sat Mar 07, 2009 7:36 pm

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.
Jasper
 
Posts: 209
Joined: Fri Oct 10, 2008 8:22 am
Location: Eindhoven, The Netherlands

Next

Return to Common Lisp

Who is online

Users browsing this forum: No registered users and 1 guest