Look at the following codes , running on ARC xlisp-stat:
> (defvar *stk1* (coerce "This is a test." 'list))
*STK1*
> *stk1*
(#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t
#\.)
> (pop *stk1*)
#\T
> *stk1*
(#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
> (defun a-letter (stk)
(pop stk))
A-LETTER
> (a-letter *stk1*)
#\h
> *stk1*
(#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
You can see that the function pop changes the stack content when
outside the function ,
but it doesn't change the stack content inside the function.
What can I do to write a function that can pop the content for using it
and can change the stack at the same time ?
Many thanks!!
You cannot.
Lisp pass the variable by value. To be precise, in this case, it pass a
VALUE of the REFERENCE to original list to A-LETTER function.
POP set the value of stk to point to the next cdr in the list. But the
original *stk* is still the reference to header of the list.
If you want something that act like POP macro, which can change the
reference of the original variable. you have to use macro. That's why
POP is a macro not a function.
On 2005-11-19 18:09:33 +0000, "Pisin Bootvong" <··········@gmail.com> said:
> You cannot.
>
> Lisp pass the variable by value. To be precise, in this case, it pass a
> VALUE of the REFERENCE to original list to A-LETTER function.
> POP set the value of stk to point to the next cdr in the list. But the
> original *stk* is still the reference to header of the list.
>
> If you want something that act like POP macro, which can change the
> reference of the original variable. you have to use macro. That's why
> POP is a macro not a function.
I was surprised to see that you are right:
CL-USER 1 > (defvar *stk1* (coerce "This is a test." 'list))
*STK1*
CL-USER 2 > *stk1*
(#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
CL-USER 6 > (defun my-pop(stk)
(let ((x (car stk)))
(setf stk (cdr stk))
x))
MY-POP
CL-USER 7 > (my-pop *stk1*)
#\T
CL-USER 8 > *stk1*
(#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
Why is it that the setf doesn't change the binding of the passed in
value, since that value *was* declared special ?
It seems that, like the OP, I've still got a fundamental misunderstanding
of the binding rules :(
--
JFB ()
verec <·····@mac.com> writes:
> On 2005-11-19 18:09:33 +0000, "Pisin Bootvong" <··········@gmail.com> said:
>
>> You cannot.
>> Lisp pass the variable by value. To be precise, in this case, it
>> pass a
>> VALUE of the REFERENCE to original list to A-LETTER function.
>> POP set the value of stk to point to the next cdr in the list. But the
>> original *stk* is still the reference to header of the list.
>> If you want something that act like POP macro, which can change the
>> reference of the original variable. you have to use macro. That's why
>> POP is a macro not a function.
>
> I was surprised to see that you are right:
>
>
> CL-USER 1 > (defvar *stk1* (coerce "This is a test." 'list))
> *STK1*
>
> CL-USER 2 > *stk1*
> (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> CL-USER 6 > (defun my-pop(stk)
> (let ((x (car stk)))
> (setf stk (cdr stk))
> x))
> MY-POP
>
> CL-USER 7 > (my-pop *stk1*)
> #\T
>
> CL-USER 8 > *stk1*
> (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> Why is it that the setf doesn't change the binding of the passed in
> value, since that value *was* declared special ?
> It seems that, like the OP, I've still got a fundamental misunderstanding
> of the binding rules :(
Because what you wrote is equivalent to:
cons* stk_star=list('T','h','i',...'.',0);
char my_pop(cons* stk){
char x=car(stk);
stk=cdr(stk);
return(x);}
my_pop(stk_star); /* careful! */
If you want:
char my_pop(cons** stk){
char x=car(*stk);
*stk=cdr(*stk);
return(x);}
my_pop(&stk_star); /* careful! */
then you have to write it explicitly in lisp as you do in C, with all
these * and &.
The 'special' property of symbols have nothing to do with this.
--
__Pascal Bourguignon__ http://www.informatimago.com/
The world will now reboot. don't bother saving your artefacts.
On 2005-11-19 19:11:01 +0000, Pascal Bourguignon <····@mouse-potato.com> said:
>> CL-USER 6 > (defun my-pop(stk)
>> (let ((x (car stk)))
>> (setf stk (cdr stk))
>> x))
>> MY-POP
> Because what you wrote is equivalent to:
>
> cons* stk_star=list('T','h','i',...'.',0);
>
> char my_pop(cons* stk){
> char x=car(stk);
> stk=cdr(stk);
> return(x);}
>
> my_pop(stk_star); /* careful! */
>
>
> If you want:
>
> char my_pop(cons** stk){
> char x=car(*stk);
> *stk=cdr(*stk);
> return(x);}
>
> my_pop(&stk_star); /* careful! */
>
> then you have to write it explicitly in lisp as you do in C, with all
> these * and &.
Thanks for the analogy, I grok that :-)
But it can only be pushed so far ... Am I now correct in assuming that
the semantical equivalent of C's & would be a lisp macro, so that the
*actual* argument to setf would be *stk1*, through macro-expansion:
CL-USER 8 > *stk1*
(#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
CL-USER 22 > (defmacro mypop (stk)
`(let ((x (car ,stk)))
(setf ,stk (cdr ,stk))
x))
MYPOP
CL-USER 23 > (mypop *stk1*)
#\T
CL-USER 24 > *stk1*
(#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
(ignoring the issue of bad writing because I didn't use gensym for x,
though it doesn't seem to apply in this case)
Is there any other way than a macro such as this one?
> The 'special' property of symbols have nothing to do with this.
Its rather difficult to come to terms with those notions of dynamic
extent/lexical scope when coming from the Java/C/C++ land.
As far as I understand things this far, a lexically scoped variable
may have dynamic extent (lifetime that survives the return of the
bit of code that created it), but this isn't always true and it can
also "die" as soon as the function returns.
In my flawed attempt at the top, both x and stk were lexically scoped,
stk died just before the return, and x lived for as long as the
caller was doing anything with it?
Because none of them was "captured" by a returned proc that would have
referred to them, and thus kept them alive indefinitely?
Unless that proc, itself, became "semantic garbage" (not being referred
to anymore) and thus elligible for GC'ing?
Am I already off-track?
Many Thanks.
--
JFB ()
verec <·····@mac.com> writes:
> Thanks for the analogy, I grok that :-)
>
> But it can only be pushed so far ... Am I now correct in assuming that
> the semantical equivalent of C's & would be a lisp macro, so that the
> *actual* argument to setf would be *stk1*, through macro-expansion:
No. I've show you how to implement the semantic equivalent in lisp,
with closures, in a previous post.
A macro is a shortcut, that can be expedient, but it has its own problems.
> CL-USER 8 > *stk1*
> (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> CL-USER 22 > (defmacro mypop (stk)
> `(let ((x (car ,stk)))
> (setf ,stk (cdr ,stk))
> x))
> MYPOP
>
> CL-USER 23 > (mypop *stk1*)
> #\T
For example, with this macro:
(defparameter *sa* (make-array 8
:initial-contents (mapcar (lambda (x) (coerce x 'list))
'("Arrivederchi"
"Bonjour"
"Ciao"
"Dzień dobry"
"Evening"
"Fin"
"Goddag"
"Hello"))))
(defparameter *i* 0)
(mypop (aref *sa* (incf *i*))) --> #\B ; !
(mypop (aref *sa* (incf *i*))) --> #\E ; !!
*i* --> 6 ; !!!
> CL-USER 24 > *stk1*
> (#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> (ignoring the issue of bad writing because I didn't use gensym for x,
> though it doesn't seem to apply in this case)
>
> Is there any other way than a macro such as this one?
Use closures and defsetf and setf expanders.
But the best way to deal with it is to avoid assignment and write in
a more functional style.
The second best way is to use "objects". Then you don't change the
identity of the object bound to the outside variable, but you can
change the state of the object.
(defparameter *n* 42)
(defun increment-integer (x) (incf x))
(progn (increment-integer *n*) *n*) --> 42 ; bad
Note that:
(let ((sav *n*))
(incf *n*)
(not (eql sav *n*))) --> T
(defstruct integer-object value)
(defparameter *n* (make-integer-object :value 42))
(defun increment-integer-object (o) (incf (integer-object-value o)))
(progn (increment-integer-object *n*) (integer-object-value *n*)) --> 43
Note that:
(let ((sav *n*))
(increment-integer-object *n*)
(eql sav *n*)) --> T
The "object" can be as simple as a cons cell, or as complex as a CLOS object.
>> The 'special' property of symbols have nothing to do with this.
>
> Its rather difficult to come to terms with those notions of dynamic
> extent/lexical scope when coming from the Java/C/C++ land.
You can think of special variables as symbol structures with a value
slot, while the normal lexical variables are memory locations,
identified at compilation time by symbol names.
The symbol structure of special variables is available both at
compilation time and at run time, and is available in a dynamic scope
(between the interning of the symbol and its eventual uninterning).
The lexical variable (the memory location) is only available inside
the lexical scope of its closure.
When you use LET on a special variable, it save the old value and set
the new value in the value slot of the structure. It is therefore
available to all code that refers to that structure.
Lexical variables on the other hand are like the auto variables in C,
they're only accessible to the local scope.
> As far as I understand things this far, a lexically scoped variable
> may have dynamic extent (lifetime that survives the return of the
> bit of code that created it), but this isn't always true and it can
> also "die" as soon as the function returns.
It doesn't survive the bit of code. What happens is that some bits of
code survive longer than you think in CL. It's the closures:
(defparameter *c* (let ((x 1)) (lambda (y) (incf x y))))
Here, the variable x survives, because it's a free variable in the
anonymous function. So it gets enclosed in a closure along with the
function. This allows you to call it:
(funcall *c* 3) --> 4
(funcall *c* -2) --> 2
(funcall *c* 0) --> 2
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
verec <·····@mac.com> writes:
> CL-USER 6 > (defun my-pop(stk)
> (let ((x (car stk)))
> (setf stk (cdr stk))
> x))
> MY-POP
>
> CL-USER 7 > (my-pop *stk1*)
> #\T
>
> CL-USER 8 > *stk1*
> (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> Why is it that the setf doesn't change the binding of the passed in
> value, since that value *was* declared special ?
One way to approach this is to look at what does work:
CL-USER> (defun my-pop (symbol)
(pop (symbol-value symbol)))
MY-POP
CL-USER> (defparameter *stack* (coerce "abcde" 'list))
*STACK*
CL-USER> (my-pop (quote *stack*))
#\a
CL-USER> *stack*
(#\b #\c #\d #\e)
CL-USER> (my-pop (quote *stack*))
#\b
CL-USER> *stack*
(#\c #\d #\e)
I'm writing (quote *stack*) instead of '*stack* for
emphasis.
You can get (very close to) the effect of passing dynamic
bindings to functions by passing the symbols the that name
them. However, you seldom see this done.
Another approach is to explain the failure of what doesn't
work, but I think it is more interesting to point out that
the issue tends to recede into the background when there is
work to be done. Consider, as a toy example, a structure
holding two stacks:
CL-USER> (defstruct double-stack ying yang)
DOUBLE-STACK
CL-USER> (defparameter *ds* (make-double-stack
:ying (coerce "fire" 'list)
:yang (coerce "ice" 'list)))
*DS*
CL-USER> (defun pop-ying (two)
(check-type two double-stack)
(pop (double-stack-ying two)))
POP-YING
CL-USER> *ds*
#S(DOUBLE-STACK :YING (#\f #\i #\r #\e) :YANG (#\i #\c #\e))
CL-USER> (pop-ying *ds*)
#\f
CL-USER> *ds*
#S(DOUBLE-STACK :YING (#\i #\r #\e) :YANG (#\i #\c #\e))
CL-USER> (pop-ying *ds*)
#\i
CL-USER> *ds*
#S(DOUBLE-STACK :YING (#\r #\e) :YANG (#\i #\c #\e))
It works but why?
There are TWO addresses to think about.
Where is *ds* stored?
Where is the two-element structure stored?
In CL these two addresses are distinct. When the CPU goes to
*ds*'s address and retrieves a value, the value it retrieves
is a pointer, telling it the address at which the
two-element structure is stored.
When pop-ying is called, it is passed the value of
*ds*. pop-ying never sees the address in which the value of
*ds* is stored. pop-ying only sees the value that was
retrieved from that location and passed to it.
However, that value is itself a pointer, so pop-ying gets to
see the address of the memory locations in which the
components of the structure are stored, not just a copy of
the data that was stored there. So an accessor, such as
double-stack-ying, can serve as a place for pop.
You could say "CL only has value parameters, but it seldom
matters because everything is a pointer and every access a
dereference."
Three little details from the hyper-spec
1)From adjust-array
If adjust-array is applied to an array that is actually
adjustable, the array returned is identical to array
2)From 7.2 Changing the Class of an Instance
Note that changing the class of an instance may cause
slots to be added or deleted. Changing the class of an
instance does not change its identity as defined by the
eq function.
3)From 4.3.6 Redefining Classes
Updating an instance does not change its identity as
defined by the function eq. The updating process may
change the slots of that particular instance, but it does
not create a new instance.
Implicit in these three little details is a vision of how
imperative programming is supposed to work in CL. Usually
you are changing parts of an object, so you only need the
address of the object, ie the object, not the address of the
variable holdinging it. CL's "everything is a pointer"
version of call by value works OK for this.
Sometimes you want to make bigger changes, adjusting an
array, changing a class definition, or changing an object
into an object of a different class. CL is carefully
specified to preserve object identity so that these changes
work as expected without needing call-by-value. As far as
the variables holding the array or the object know, it is
still the same old thing; they don't have to be told that it
changed underneath them because object identity was preserved.
Imagine that original poster had attempted something
slightly ambitious, deciding that it was bad that asking the
number of items on a stack involving counting them anew, and
resolving to write his own stack primitives that kept track
of the number of items on the stack. He could do it in a
cons, with the left entry keeping the count and the right
keeping the stack.
CL-USER> (defun make-stack ()(cons 0 nil))
MAKE-STACK
CL-USER> (defun stack-push (item stack)
(incf (car stack))
(push item (cdr stack)))
STACK-PUSH
CL-USER> (defun stack-pop (stack)
(when (zerop (car stack))
(error "Pop of empty stack"))
(decf (car stack))
(pop (cdr stack)))
STACK-POP
CL-USER> (defun stack-length (stack)
(car stack))
STACK-LENGTH
CL-USER> (defparameter *stack* (make-stack))
*STACK*
CL-USER> (dolist (x '(a b c) *stack*)
(stack-push x *stack*))
(3 C B A)
CL-USER> (stack-pop *stack*)
C
CL-USER> *stack*
(2 B A)
See how the problem has vanished, without needing to be
solved.
Alan Crowe
Edinburgh
Scotland
On 2005-11-19 21:34:33 +0000, Alan Crowe <····@cawtech.freeserve.co.uk> said:
> One way to approach this is to look at what does work:
[...]
I cheated and copied and pasted your code to my REPL, and tried
it.
> It works but why?
> There are TWO addresses to think about.
> Where is *ds* stored?
> Where is the two-element structure stored?
OK. I get it now.
Many thanks. That's one of the most illuminating explanations
I've read this far! Well done.
[...]
> See how the problem has vanished, without needing to be
> solved.
That's always what I thought: the most efficient way to solve
a problem, is to get rid of it :-)
One most excellent post!
--
JFB ()
(message (Hello 'verec)
(you :wrote :on '(Sat, 19 Nov 2005 18:26:45 +0000))
(
v> CL-USER 6 > (defun my-pop(stk)
v> (let ((x (car stk)))
v> (setf stk (cdr stk))
v> x))
v> MY-POP
you can also do
(defun my-pop (stk)
(let ((x (car stk)))
(setf (car stk) (cdar stk)) ;rplaca
(setf (cdr stk) (cddr stk)) ;rplacd
x))
you can find return values are correct:
CL-USER> (let ((stk (loop for i from 1 to 8 collect i)))
(loop repeat 10 do (print (my-pop stk))))
1
2
3
4
5
6
7
8
NIL
NIL
but you end up having (NIL) instead of NIL..
)
(With-best-regards '(Alex Mizrahi) :aka 'killer_storm)
"People who lust for the Feel of keys on their fingertips (c) Inity")
··········@bbs.ee.ncu.edu.tw writes:
> Look at the following codes , running on ARC xlisp-stat:
>
>> (defvar *stk1* (coerce "This is a test." 'list))
> *STK1*
>> *stk1*
> (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t
> #\.)
>> (pop *stk1*)
> #\T
>> *stk1*
> (#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>> (defun a-letter (stk)
> (pop stk))
> A-LETTER
>> (a-letter *stk1*)
> #\h
>> *stk1*
> (#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s #\t #\.)
>
> You can see that the function pop changes the stack content when
> outside the function ,
> but it doesn't change the stack content inside the function.
> What can I do to write a function that can pop the content for using it
> and can change the stack at the same time ?
> Many thanks!!
This is because arguments in lisp are passed by value, not by reference.
You can either:
- write functions intead of procedures:
(defun a-letter (stk) (values (car stk) (cdr stk)))
(multiple-value-bind (letter stk) (a-letter stk)
(print letter)
(print stk))
- pass references instead of values:
(defmacro make-reference (place)
;; This is not correct, you should use setf-expanders to parse
;; correctly the place, but it'll do to explain the principle.
`(cons (lambda () ,place)
(lambda (v) (setf ,place v))))
(defun referenced (reference) (funcall (car reference)))
(defun (setf referenced) (value reference)
(funcall (cdr reference) value))
(defun a-letter (stk) (pop (referenced stk)))
(let ((var '(a b c)))
(a-letter (make-reference var)))
It's easier to decompose the functionnality and to write two functions:
(defun first-letter (stk) (car stk))
(defun remaining-letters (stk) (cdr stk))
Or just use FIRST and REST, or directly use POP, perhaps thru a macro:
(defmacro a-letter (place) `(pop ,place))
Note that POP is a macro!
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?
From: Wade Humeniuk
Subject: Re: changing or not changing , that's the question of pop
Date:
Message-ID: <7KNff.205737$ir4.34325@edtnps90>
You have to do what is commonly referred to as boxing, then you
can pass the box around and change its contents.
(defstruct box
list)
CL-USER 1 > (defvar *stk1* (make-box :list (coerce "This is a test."
'list)))
*STK1*
CL-USER 2 > *stk1*
#S(BOX :LIST (#\T #\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t
#\e #\s #\t #\.))
CL-USER 3 > (defun a-letter (box)
(pop (box-list box)))
A-LETTER
CL-USER 6 > (pop (box-list *stk1*))
#\T
CL-USER 7 > *stk1*
#S(BOX :LIST (#\h #\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e
#\s #\t #\.))
CL-USER 8 > (a-letter *stk1*)
#\h
CL-USER 9 > *stk1*
#S(BOX :LIST (#\i #\s #\Space #\i #\s #\Space #\a #\Space #\t #\e #\s
#\t #\.))
CL-USER 10 >
Wade
On 2005-11-19 22:32:35 +0000, Wade Humeniuk
<····················@telus.net> said:
> You have to do what is commonly referred to as boxing, then you
> can pass the box around and change its contents.
Waahhooo!
I'm going to have to stop counting the variations on the same
topic. :-)
To the OP: I'm very sorry I somehow managed to hijack your
thread, but it seems that the number of thoughtful alternative
answers we got to the orginal question outweights my having
stepped on your toes...
Now we've got a neat collection of examples!
Many thanks to all.
--
JFB ()