From: Mark Greenaway
Subject: Priority queue insert into a list
Date:
Message-ID: <874911437.842822@cabal>
I am trying to write a priority queue insert which takes a priority queue,
an atom and a comparison operator as arguments and returns the priority
queue with the atom inserted in the correct position. Here is my latest
attempt:
(defun priority-queue-insert (priority-queue
element
&optional
(comparison #'>))
;; This is just a wrapper function for pq-insert
(pq-insert priority-queue element comparison priority-queue))
(defun pq-insert (priority-queue
element
comparison
whole-list)
(if (funcall comparison (first priority-queue) element)
;; Insert element after current list position
(setf priority-queue
(cons element
(cons (first priority-queue)
(rest priority-queue))))
(setf whole-list (pq-insert (rest priority-queue)
element
comparison whole-list))))
Currently, it just returns the original list. I have traced and stepped
through the function, and have found that whole-list is not being modified
as I expect. The original value seems to be being retained.
I'm probably displaying my ignorance here, but:
1) How exactly are paremeters passed in LISP? Is it simply by reference?
2) Is it (as some other posts seem to imply) different for
structures/objects and atoms?
I want to use side effects and list surgery for speed reasons. It's a
simple enough matter to write a version of the above function which simply
conses all of the sub-lists back together, but this would defeat the
purpose of the exercise.
Mark
--
Mark
Certified Waifboy And when they come to ethnically cleanse me
Will you speak out? Will you defend me?
http://www.st.nepean.uws.edu.au/~mgreenaw - Ich bin ein Auslander, PWEI
In article <················@cabal>,
Mark Greenaway <········@st.nepean.uws.edu.au> wrote:
>I am trying to write a priority queue insert which takes a priority queue,
>an atom and a comparison operator as arguments and returns the priority
>queue with the atom inserted in the correct position. Here is my latest
>attempt:
Be careful about posting indented text that uses tabs. Not everyone has
their tab stops the same as yours (it seems like many systems that people
use these days have 4-column tabs, but most Unix software uses 8), and it's
very difficult to read.
>1) How exactly are paremeters passed in LISP? Is it simply by reference?
Parameters are passed by value. When a function assigns to one of its
parameter variables it has no effect on the value of the variable that was
used in the call. E.g.
(defun try-to-change-a (a)
(setq a (1+ a)))
(setq x 1) => 1
(try-to-change-a x) => 2
x => 1
>2) Is it (as some other posts seem to imply) different for
>structures/objects and atoms?
No. However, if you pass a structure, you can modify the contents of the
slots of that structure. Similarly, if you pass a cons, you can modify its
car or cdr. The "value" that's passed in Lisp is an object -- there's no
copying of data. But it's not a reference to the variable used at the
point of call, which is what's traditionally meant by the phrase "call by
reference" (the form of parameter passing used in Fortran and PL/I).
>I want to use side effects and list surgery for speed reasons. It's a
>simple enough matter to write a version of the above function which simply
>conses all of the sub-lists back together, but this would defeat the
>purpose of the exercise.
Use a structure or CLOS object.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
Support the anti-spam movement; see <http://www.cauce.org/>
Please don't send technical questions directly to me, post them to newsgroups.
In article <·········@pasilla.bbnplanet.com> Barry Margolin <······@bbnplanet.com> writes:
> Parameters are passed by value. When a function assigns to one of its
> parameter variables it has no effect on the value of the variable that was
> used in the call.
Hmmm. This is true, but it's worth noting that the programming
language community is overloaded on its use of the term "by value".
In PL/I passing by value meant copying the entire structure and ALSO
ended up making the second sentence above, true. Lisp doesn't copy
the structure, and for people who are struggling to get a foothold on
other languages, I prefer the term "by pointer" or (if you don't like
thinking about pointers in Lisp) then just "by object". Every object
in Lisp is a pointer to an object and so we normally don't use the
word pointer. But it's critical for people coming in to Lisp to
understand that NO copying occurs, so side-effects on OBJECTS will
have an effect visible to the caller, but side-effects on variables
will not.
Oops. I see my reply only duplicates what Barry said in answer to a
different question. Sorry, Barry. I should have been more trusting.
Oh well, saying it twice can't hurt.
From: William Paul Vrotney
Subject: Re: Priority queue insert into a list
Date:
Message-ID: <vrotneyEH1JIy.MvC@netcom.com>
In article <···············@world.std.com> ······@world.std.com (Kent M
Pitman) writes:
>
> In article <·········@pasilla.bbnplanet.com> Barry Margolin <······@bbnplanet.com> writes:
>
> > Parameters are passed by value. When a function assigns to one of its
> > parameter variables it has no effect on the value of the variable that was
> > used in the call.
>
> Hmmm. This is true, but it's worth noting that the programming
> language community is overloaded on its use of the term "by value".
> In PL/I passing by value meant copying the entire structure and ALSO
> ended up making the second sentence above, true. Lisp doesn't copy
> the structure, and for people who are struggling to get a foothold on
> other languages, I prefer the term "by pointer" or (if you don't like
> thinking about pointers in Lisp) then just "by object". Every object
> in Lisp is a pointer to an object and so we normally don't use the
> word pointer. But it's critical for people coming in to Lisp to
> understand that NO copying occurs, so side-effects on OBJECTS will
> have an effect visible to the caller, but side-effects on variables
> will not.
"Call by value" overloaded indeed. In Winston/Horn Lisp II they write
"We say that Lisp obeys the conventions of *call by value*. [footnote]
Although Lisp is a call-by-value language, the value of an argument can be
changed by a change to a parameter if that change is done by certain
surgical primitives ..."
So far, I like your term "Call by object". It provides the abstraction
(versus "call by pointer") and provides a visualization for what is going on
here. However, that visualization, as you say, does not seem to imply the
NO-copying concept as Lisp relates to other languages. "Call by object
pointer" seems to hit it right on the head, but still uses that undesirable
"pointer". Also some objects like small integers may not actually be passed
as pointers. I wonder if there is some more universally accepted term "Call
by _____" that fills in the blank.
--
William P. Vrotney - ·······@netcom.com
In article <·················@netcom.com>
·······@netcom.com (William Paul Vrotney) writes:
> So far, I like your term "Call by object". It provides the abstraction
> (versus "call by pointer") and provides a visualization for what is going on
> here. However, that visualization, as you say, does not seem to imply the
> NO-copying concept as Lisp relates to other languages. "Call by object
> pointer" seems to hit it right on the head, but still uses that undesirable
> "pointer". Also some objects like small integers may not actually be passed
> as pointers. I wonder if there is some more universally accepted term "Call
> by _____" that fills in the blank.
"Reference".
-- Tim Olson
From: William Paul Vrotney
Subject: Re: Priority queue insert into a list
Date:
Message-ID: <vrotneyEH25G6.F1s@netcom.com>
In article <············@news.jumpnet.com> ···@jumpnet.com (Tim Olson) writes:
>
> In article <·················@netcom.com>
> ·······@netcom.com (William Paul Vrotney) writes:
>
> > So far, I like your term "Call by object". It provides the abstraction
> > (versus "call by pointer") and provides a visualization for what is going on
> > here. However, that visualization, as you say, does not seem to imply the
> > NO-copying concept as Lisp relates to other languages. "Call by object
> > pointer" seems to hit it right on the head, but still uses that undesirable
> > "pointer". Also some objects like small integers may not actually be passed
> > as pointers. I wonder if there is some more universally accepted term "Call
> > by _____" that fills in the blank.
>
>
> "Reference".
>
No no, "call by reference" is already reserved, and Lisp certainly is not
that.
--
William P. Vrotney - ·······@netcom.com
> No no, "call by reference" is already reserved, and Lisp certainly is not
> that.
Yes, you are of course correct; it's more like "call by value", but
where all values are references.
-- Tim Olson
···@jumpnet.com (Tim Olson) writes:
> > ·······@netcom.com (William Paul Vrotney) writes: [...]
> > Also some objects like small integers may not actually be passed
> > as pointers.
This is a special optimization. It is not part of the standard conceptual
model and should not clutter the choice of term. (When it happens, you get
a different kind of calling sequence which appropriately has its own name,
and in fact is correctly modeled by conventional call-by-value.)
> > I wonder if there is some more universally accepted term "Call
> > by _____" that fills in the blank.
>
> "Reference".
No, in a call by reference language you are passing the location of the object.
Consider the following pseudocode for two functions f and g.
define f () define g (x)
x := 3; x := x+1;
g(x); return nothing_special;
return x;
Doing f() in a call-by-reference language would pass g the location of
f's x, and make f's x subject to side-effect, so that f() would return 4.
In Lisp, the equivalent program is:
(defun f () (let ((x 3)) (g x) x))
(defun g (x) (setq x (1+ x)) nil)
and this does NOT pass the location of the VARIABLE X but of the OBJECT 3.
Assigning g's x does not change f's x. The result of (f) is 3.
Lisp does not have typed variables, it has typed objects. A variable
in Lisp is a place to put a pointer to an object. It is not (at least
conceptually) storage in which to allocate the object (which, at least
conceptually, is allocated on the heap--any attempt to allocate it
elsewhere is an optimization permissible by the compiler only where it
doesn't violate the conceptual model).
All this to say that call-by-reference is definitely NOT what lisp does.
William Paul Vrotney <·······@netcom.com> wrote:
+---------------
| So far, I like [Pitman's] term "Call by object". [...but] does not seem
| to imply the NO-copying concept as Lisp relates to other languages.
| "Call by object pointer" seems to hit it right on the head, but still
| uses that undesirable "pointer".
+---------------
How about "call by object reference"? [As distinguished from traditional
"call by reference" which is really "call by variable reference"...]
+---------------
| Also some objects like small integers may not actually be passed as pointers.
+---------------
That's a non-issue, IMHO. As far as copying goes, *all* mutable objects
are "call by object reference". So the fact that a given implementation
may choose for some subset of non-mutable objects (e.g., small numbers,
chars, t, nil, etc.) to actually use "call by copy of object" instead of
"call by object reference" is non-observable to the program [except possibly
by its effect on the garbage collector].
And when you say ((lambda (foo) (setf foo 43923876)) 27), you're mutating
the *variable* [well, the binding], not the objects 27 or 43923876, which
are immutable whether or not they are "small" or "large", and whether or not
their values are conveyed by copying the entire object or just copying a
reference (pointer).
[I *do* hope I got that right...]
-Rob
-----
Rob Warnock, 7L-551 ····@sgi.com http://reality.sgi.com/rpw3/
Silicon Graphics, Inc. Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd. FAX: 650-933-4392
Mountain View, CA 94043 PP-ASEL-IA
In article <················@cabal>,
Mark Greenaway <········@st.nepean.uws.edu.au> wrote:
>I am trying to write a priority queue insert which takes a priority queue,
>an atom and a comparison operator as arguments and returns the priority
>queue with the atom inserted in the correct position. Here is my latest
>attempt:
>
Most simple stuff (and a lot more) is already present in the
form of built-in functions in CL. Your priority-queue-insert could
be:
(defun priority-queue-insert (priority-queue element &optional (comparison #'>))
(merge 'list priority-queue (list element) comparison))
But then you don't want to implement a priority queue with a sorted list,
right?
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence ········@ai.univie.ac.at
········@st.nepean.uws.edu.au (Mark Greenaway) writes:
>
> I am trying to write a priority queue insert which takes a priority queue,
> an atom and a comparison operator as arguments and returns the priority
> queue with the atom inserted in the correct position. Here is my latest
> attempt:
>
Shameless plug. :)
In the AI.Repository at CMU
http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/lang/lisp/ext/0.html
There is a package called 'trees' which contains a working implementation of
a priority queue.
--
Marco Antoniotti
==============================================================================
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472