newbie: does lisp copy all arguments?
Thomas Conner Annandale
requires that I modify a minimax evaluation function (for the
"Isolation" game) to make it "as efficient as possible". The function is
passed a list of lists that represent a 2D board (which can be quite
large) and some other information. The function calls itself
recursively. My question: Is the entire board copied at every
function call? Only a single change is made to the board at every
recursive call. Would I be saving anything if I changed it so that there
was only a single global board, and the function made its single change
to the board and then undid the change before returning? Or does lisp
operate in such a way that this would be a useless "optimization"?
--
Thomas
www.boredatheist.com
Christopher Browne
By and large, Lisp does "call by reference," which means that what
would be passed to the function is a _reference_ to the board. A
pointer, although you likely never get to look at what address it
contains.
You're certainly asking a good question; it's one with no
straightforward single answer, though.
-> Sometimes it may be preferable to create additional boards,
throwing them away when they are no longer needed. In _PAIP_, this
is the approach taken in Chapter 18 on an Othello player.
-> Sometimes it may be preferable to just pass around a data structure
of "changes" to apply to the single original board.
Thus, in an Othello game, what you might pass around wouldn't be
the board, but rather the sequence of moves, which would get
constructed into an assessment of what's on the board. Probably a
bad choice for Othello, where recomputing board contents would be
pretty expensive, but it may be useful for other games.
-> Sometimes it may be preferable to apply the changes to the global
board, and have each function undo its changes when it's done.
All of these representations are legitimate, implementable, and, under
differing circumstances, any of them may be to be preferred over the
others.
Which strategy is to be preferred isn't a question of what the
language can do; it's an _application_ question that _you_ have to
address.
--
(concatenate 'string "cbbrowne" "@canada.com")
http://www3.sympatico.ca/cbbrowne/
Why does the word "lisp" have an "s" in it?
Russell Wallace
<gte...@prism.gatech.edu> wrote:
>I'm a newbie lisp programmer. My current assignment in my AI class
>requires that I modify a minimax evaluation function (for the
>"Isolation" game) to make it "as efficient as possible". The function is
>passed a list of lists that represent a 2D board (which can be quite
>large) and some other information. The function calls itself
>recursively. My question: Is the entire board copied at every
>function call?
No, Lisp generally passes compound data structures by reference.
The big slowdown is probably from using lists at all. Lists are a very
slow data structure for random access (which board games need) -
suppose you want to access the 10th element of a list, the generated
code has to do 10 pointer hops (the slowest operation on modern CPUs)
to get there. If you reimplement the board as a 2D array (so any
element can be accessed directly in a single operation) you should see
a big speedup.
--
"Mercy to the guilty is treachery to the innocent."
mailto:r...@eircom.net
http://www.esatclear.ie/~rwallace
Thomas A. Russ
>
> I'm a newbie lisp programmer. My current assignment in my AI class
> requires that I modify a minimax evaluation function (for the
> "Isolation" game) to make it "as efficient as possible". The function is
> passed a list of lists that represent a 2D board (which can be quite
> large) and some other information.
Well, for starters, changing the list of lists into a 2D array would
help. Based on the text below, it would seem that the function wants to
have random access to the board, and a list of lists approach doesn't
give you efficient random access.
Also, for large enough structures, a 2D array will use less memory,
which means less GC if you throw them away, which translates into faster
runtime.
> The function calls itself
> recursively. My question: Is the entire board copied at every
> function call?
No.
> Only a single change is made to the board at every
> recursive call. Would I be saving anything if I changed it so that there
> was only a single global board, and the function made its single change
> to the board and then undid the change before returning?
Whether the changes are local or affect a global board would depend in
part on exactly how the changes are done. With a list representation,
you would make global changes using destructive list operations (setting
things like the car and cdr of lists, using nconc instead of append,
etc.)
Now, on the other hand, Lisp is very good at allowing you to share
common substructures of lists, so for example, if you had the following:
((a b c d)
(d f g h)
(i j k l)
(m n o p))
and you wanted to change it to
((a b c d)
(d f g h)
(Z j k l) ;; First element of this line changed.
(m n o p))
You could have a lot of shared structure, namely
(a b c d)
(d f g h)
(j k l)
(m n o p)
could all be shared between the results, so you would only have to
allocate a new list of length 4 and one additional cons cell for the
head of the new third sub-list.
This ability to share structure can result in a lot of compactness, and
is, in fact, the very opposite of a copying sort of scheme. Whether
shared structure or arrays is better can't usually be determined except
by testing.
> Or does lisp
> operate in such a way that this would be a useless "optimization"?
Well, the only way to really tell whether your changes will improve
things is to do profiling of the code. You first need to see where your
algorithm is spending its time before you can intelligently try to speed
things up.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Erik Naggum
| By and large, Lisp does "call by reference," which means that what
| would be passed to the function is a _reference_ to the board.
This is slightly misleading. The usual terminology is "call by value",
"call by name", and "call by reference", which refer to how the arguments
in the function call are passed to the function.
1 A call by value means that the value yielded by the argument is passed to
the function. This means that the expression is fully computed and only
the value is passed along to the function with no trace of its origins.
2 A call by name means that the expression in the function call is passed
to the function, such that the called function evaluates it itself.
3 A call by reference means that a place that holds the value of the
argument is passed to the function. Typically, the variable that holds
the value is passed to the function so the function can write back into
the variable.
All Lisps are strict call-by-value languages. Macros are in a sense
call-by-name "functions". But in no sense does Lisp offer a call by
reference concept.
Other languages have different semantics. E.g., Ada has the very elegant
in/out parameter specification: in parameters are call-by-value, out are
_effectively_, but need not actually be, call-by-name or -reference.
Fortran is generally call-by-reference. C++ is usually call-by-value,
but you may request call-by-reference.
Whether you pass a pointer to an object or the object itself is entirely
orthogonal to the call-by-value or call-by-reference issue.
Common Lisp offers object identity as one of its basic features as well
as the ability to store any kind of object in a Lisp "storage cell"
location, meaning a variable, structure or class slot, array cell, the
car and cdr of a cons, etc, etc. This naturally means that Lisp must
pass around some kind of references to objects, as no other mechanism can
store any kind of value in equal amounts of space. However, this does
not mean that Common Lisp provides the kind of pointers that C/C++
offers, although some Lisps have provided "locatives" which refer to
sub-elements of structured objects, like an individual array cell, class
or structure slot, and the like. They would still be passed by value,
however.
///
--
In a fight against something, the fight has value, victory has none.
In a fight for something, the fight is a loss, victory merely relief.
Erann Gat
> All Lisps are strict call-by-value languages.
...
> C++ is usually call-by-value, but you may request call-by-reference.
I think it's worth pointing out that even though Lisp and C++ are both
call-by-value the actual behavior you get from Lisp's calling convention
more resembles (but is not identical to) what you get from
call-by-reference in C++. For example, consider:
class C {
public:
int x;
};
void f(C c) { c.x++; } // c is passed "by value" -- sort of
main() {
C c;
c.x=0;
f(c);
cout << c.x;
}
and the Common Lisp equivalent:
(defclass C () (x))
(defun f (c) (incf (slot-value c 'x)))
(defun main ()
(let ( (c (make-instance 'C)) )
(setf (slot-value c 'x) 0)
(f c)
(print (slot-value c 'x))))
The output of the C++ version is '0' while the Lisp version output is
'1'. (On the other hand, if you changed f in the C++ version to be f(C
&c) then it too would output '1'.) The difference arises because:
> Common Lisp offers object identity as one of its basic features as well
> as the ability to store any kind of object in a Lisp "storage cell"
> location, meaning a variable, structure or class slot, array cell, the
> car and cdr of a cons, etc, etc. This naturally means that Lisp must
> pass around some kind of references to objects, as no other mechanism can
> store any kind of value in equal amounts of space.
This is a subtle but really crucial point. In C++ call-by-value really
means something more like "call-by-copy-of-value" whereas in Lisp
call-by-value means call-by-actual-value. There really is nothing in C++
that mimics the true semantics of Lisp's calling convention. It's a
substantial amount of work to reproduce all aspects of Lisp's argument
passing semantics in C++.
E.