Hi
I'm trying to evaluate for myself the usefulness of Lisp, specifically
CMUCL, for Artificial Neural Networks programming. ANN algorithms involve
plenty of
-passing of large objects by reference (e.g. to update the weights
matrix),
-BLAS 1 and BLAS 2 routines (dot products, matrix-vector products),
-and sometimes 1 and 2-dimensional convolutions.
This is where most of the CPU time is spent.
I'm looking at MatLisp built with CMUCL, because MatLisp provides a matrix
class and BLAS/LAPACK interface. I'm worried about efficiency however.
For instance, would
(setf my-matrix (make-complex-matrix 1000 1000))
first create a 1000x1000 matrix and then copy the whole thing to a
different location in "setf" ?
What about passing by reference? Can, for example,
M += s * V*V_traspose (M - matrix, V - vector, s - scalar)
be implemented efficiently with Lisp, i.e. without unnecessary copying?
Thanks
Oleg
In article <············@newsmaster.cc.columbia.edu>,
Oleg <·····@to.the.newsgroup.please> wrote:
>What about passing by reference? Can, for example,
>M += s * V*V_traspose (M - matrix, V - vector, s - scalar)
>be implemented efficiently with Lisp, i.e. without unnecessary copying?
Lisp *never* copies structured objects unless you call a copying function
explicitly. All argument passing is done by passing object references
(i.e. it's almost all pointers under the covers).
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Barry Margolin wrote:
> In article <············@newsmaster.cc.columbia.edu>,
> Oleg <·····@to.the.newsgroup.please> wrote:
>>What about passing by reference? Can, for example,
>>M += s * V*V_traspose (M - matrix, V - vector, s - scalar)
>>be implemented efficiently with Lisp, i.e. without unnecessary copying?
>
> Lisp *never* copies structured objects unless you call a copying function
> explicitly. All argument passing is done by passing object references
> (i.e. it's almost all pointers under the covers).
The above example, M = M + s*V*(V^t), is part of BLAS 2 subroutine called
DGER/SGER. M is both its argument and the returned value. Passing it by
reference modifies M in place.
I understand that what a Lisp programmer can do is define a function
M + s*V*(V^t) -> A, and then assign its result to M, so copying will take
place. Correct me if I'm wrong.
Is this the kind of case where macros need to be used?
Thanks
Oleg
Oleg wrote:
>
> Barry Margolin wrote:
>
> > In article <············@newsmaster.cc.columbia.edu>,
> > Oleg <·····@to.the.newsgroup.please> wrote:
> >>What about passing by reference? Can, for example,
> >>M += s * V*V_traspose (M - matrix, V - vector, s - scalar)
> >>be implemented efficiently with Lisp, i.e. without unnecessary copying?
> >
> > Lisp *never* copies structured objects unless you call a copying function
> > explicitly. All argument passing is done by passing object references
> > (i.e. it's almost all pointers under the covers).
>
> The above example, M = M + s*V*(V^t), is part of BLAS 2 subroutine called
> DGER/SGER. M is both its argument and the returned value. Passing it by
> reference modifies M in place.
>
> I understand that what a Lisp programmer can do is define a function
> M + s*V*(V^t) -> A, and then assign its result to M, so copying will take
> place. Correct me if I'm wrong.
You are wrong, but correction will be difficult if, as it seems,
"*never* copies...unless..." did not work. :)
I think you must be confusing Lisp with pure functional programming
(FP). Not that I am an expert on the latter, but one idea there I think
is not to alter function arguments. So in your case the function would
have to copy M, transform it and then return the copy to the caller who
would indeed need to capture the new (copy) reference.
In Lisp you will be able to operate destructively on M, such that the
caller need not capture it (tho as a convenience destructive functions
usually return the modified instance).
>
> Is this the kind of case where macros need to be used?
No need for macros; Lisp can do what you want, modifying things in
place. You were given bad information, or, i suspect, confusing Lisp
with FP.
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
"Harvey has overcome not only time and space but any objections."
Elwood P. Dowd
Kenny Tilton wrote:
> I think you must be confusing Lisp with pure functional programming
> (FP). Not that I am an expert on the latter, but one idea there I think
> is not to alter function arguments. So in your case the function would
> have to copy��M,�transform�it�and�then�return�the�copy�to�the�caller�who
> would indeed need to capture the new (copy) reference.
>
> In Lisp you will be able to operate destructively on M, such that the
> caller need not capture it (tho as a convenience destructive functions
> usually return the modified instance).
Hello Kenny,
Is it possible to define destructive functions (not macros)? For example,
can you define a function that, say, destructively increments every tenth
element of a Lisp array passed to it as an argument?
(increment-every-tenth-elt a)
It was my impression that, whatever you do within the body of the function,
arguments will remain unaltered outside of the function, i.e.
(setf a (increment-every-tenth-elt a))
will work, but inefficiently (compared to other languages), while
(increment-every-tenth-elt a)
will not change a. Is this true?
Thanks
Oleg
Oleg <·····@to.the.newsgroup.please> writes:
> Kenny Tilton wrote:
>
> > I think you must be confusing Lisp with pure functional programming
> > (FP). Not that I am an expert on the latter, but one idea there I think
> > is not to alter function arguments. So in your case the function would
> > have to copy��M,�transform�it�and�then�return�the�copy�to�the�caller�who
> > would indeed need to capture the new (copy) reference.
> >
> > In Lisp you will be able to operate destructively on M, such that the
> > caller need not capture it (tho as a convenience destructive functions
> > usually return the modified instance).
>
> Hello Kenny,
>
> Is it possible to define destructive functions (not macros)? For example,
> can you define a function that, say, destructively increments every tenth
> element of a Lisp array passed to it as an argument?
>
> (increment-every-tenth-elt a)
Yes. The object that A is bound to is passed directly to
INCREMENT-EVERY-TENTH-ELT. It cannot cause A to be bound to a
different object, but it can change things in the object that it is
passed.
You might want to read the page on the Emacs Wiki on list
modification, it covers the issues you're having trouble with here.
Elisp is a different dialect, but the issues are the same (only we
don't have add-to-list in CL, we have PUSHNEW).
<http://www.emacswiki.org/cgi-bin/wiki.pl?ListModification>
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
"Oleg" <·····@to.the.newsgroup.please> wrote in message
·················@newsmaster.cc.columbia.edu...
> Kenny Tilton wrote:
>
> > I think you must be confusing Lisp with pure functional programming
> > (FP). Not that I am an expert on the latter, but one idea there I think
> > is not to alter function arguments. So in your case the function would
> > have to copy M, transform it and then return the copy to the caller who
> > would indeed need to capture the new (copy) reference.
> >
> > In Lisp you will be able to operate destructively on M, such that the
> > caller need not capture it (tho as a convenience destructive functions
> > usually return the modified instance).
>
> Hello Kenny,
>
> Is it possible to define destructive functions (not macros)?
Yes. Lisp *never* copies structured objects unless you call a copying
function explicitly.
> For example,
> can you define a function that, say, destructively increments every tenth
> element of a Lisp array passed to it as an argument?
>
> (increment-every-tenth-elt a)
Yes. It would take special effort to make that non-destructive.
>
> It was my impression that, whatever you do within the body of the
function,
> arguments will remain unaltered outside of the function, i.e.
This is mistaken.
>
> (setf a (increment-every-tenth-elt a))
>
> will work, but inefficiently (compared to other languages), while
>
> (increment-every-tenth-elt a)
>
> will not change a. Is this true?
No. Lisp *never* copies structured objects unless you call a copying
function explicitly.
CL-USER 2 > (defvar *a* (make-array 10 :initial-element 1))
*A*
CL-USER 3 > (defun increment-every-third-elt (arr)
(loop for elt across arr
for i upfrom 1 do
(when (= 0 (mod i 3))
(incf (aref arr (1- i))))))
INCREMENT-EVERY-THIRD-ELT
CL-USER 4 > (increment-every-third-elt *a*)
NIL
CL-USER 5 > *a*
#(1 1 2 1 1 2 1 1 2 1)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
Oleg <·····@to.the.newsgroup.please> writes:
> Is it possible to define destructive functions (not macros)? For example,
> can you define a function that, say, destructively increments every tenth
> element of a Lisp array passed to it as an argument?
>
> (increment-every-tenth-elt a)
>
> It was my impression that, whatever you do within the body of the function,
> arguments will remain unaltered outside of the function, i.e.
(defun increment-every-tenth-elt (list)
(do ((rest list (nthcdr 10 rest)))
((null rest) list)
(incf (first rest))))
* (defvar *a* (make-list 25 :initial-element 0))
*A*
* *a*
(0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
* (increment-every-tenth-elt *a*)
(1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0)
* *a*
(1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0)
Common Lisp is call-by-value, i.e. a function cannot change the
binding of a passed variable, since not the variable, but its value is
passed:
(defun redefine-me (list)
(setq list (list 4 5 6)))
* (defvar *b* (list 1 2 3))
*B*
* *b*
(1 2 3)
* (redefine-me *b*)
(4 5 6)
* *b*
(1 2 3)
This is the same as in ANSI C, which is also call-by-value.
However a function can of course modify (mutate) the value passed in,
which is why the first function had a lasting effect on *a*: *a* is
still bound to the same list it was first bound to, it's just that the
contents of that list has been changed.
> will work, but inefficiently (compared to other languages), while
>
> (increment-every-tenth-elt a)
>
> will not change a. Is this true?
Only if you define increment-every-tenth-elt to copy the passed in
list, i.e. you define a non-destructive version like
(defun increment-every-tenth-elt (list)
(do* ((result-list (copy-list list))
(rest result-list (nthcdr 10 rest)))
((null rest) result-list)
(incf (first rest))))
But if you choose to destructively modify the passed in list, you are
of course free to do so. Only when you want to influence the binding
of
If you are coming from a C background, it might help to think of the
Lisp "value type" being defined like
typedef union tag_lispobj {
/* Immediate immutable objects, like fixnums, characters, ... */
unsigned int fixnum;
unsigned int character;
/* Non-immediate objects */
struct bignum *bignum;
struct cons *cons;
struct symbol *symbol;
struct vector *vector;
/* etc. */
} lispobj;
Now cons might be defined as
struct cons {
lispobj car;
lispobj cdr;
};
And symbol might be defined as:
struct symbol {
lispobj header;
lispobj value;
lispobj hash;
lispobj plist;
lispobj name;
lispobj package;
};
etc.
So a function that takes and returns one argument in Lisp might be
declared like this:
lispobj myfunc(lispobj a);
Let's examine the evaluation of the form
(myfunc *a*)
In CL, what happens is that (since myfunc names a normal function), we
first evaluate the arguments, in this case the form *a*, and pass
the resulting values to the called function. In a hypothetical CL
implementation, the equivalent of the following code might be
executed:
/* Locate the symbol named *A*. Note that this normally happens
at read-time in a real CL implementation, not at eval-time.
Still this is all for illustrative purposes. */
lispobj the_a_symbol = find_symbol("*A*");
/* Evaluating the form *A* is equivalent here to getting its
value in the dynamic environment. We assume here a shallow
binding strategy, which stores the current value in the
symbol's value cell. */
lispobj fun_arg1 = the_a_symbol.symbol->value;
/* Now call the function with this argument: */
myfunc(fun_arg1);
So, what can myfunc do with its argument? It can't, of course, modify
the_a_symbol.symbol.value, since it has no knowledge of the fact that
this is the provenance of its argument. It can however modify the
"contents" of the passed value however it likes.
At no point is a non-immediate object ever copied in this sequence of
events (and the copying of immediate objects isn't problematic, since
those are immutable, and hence have no identity besides their value).
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
On Sat, 18 May 2002 18:36:13 -0300, Pierre R. Mai wrote:
> Oleg <·····@to.the.newsgroup.please> writes:
>
>> Is it possible to define destructive functions (not macros)? For
>> example, can you define a function that, say, destructively increments
>> every tenth element of a Lisp array passed to it as an argument?
>>
>> (increment-every-tenth-elt a)
>>
>> It was my impression that, whatever you do within the body of the
>> function, arguments will remain unaltered outside of the function, i.e.
>
> (defun increment-every-tenth-elt (list)
> (do ((rest list (nthcdr 10 rest)))
> ((null rest) list)
> (incf (first rest))))
>
> * (defvar *a* (make-list 25 :initial-element 0)) *A*
>
>
This does not compute on CMUCL for Debian Woody
* *a*
> (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0)
>
> * (increment-every-tenth-elt *a*)
(cut)
> * (defvar *b* (list 1 2 3))
> *B*
This does not compute on CMUCL for Debian Woody.
* Does it ? *
**--- why ? ---**
TIA
Regs
Henry
__________________________________________________________________
Micro$oft-Free Human 100% Debian GNU/Linux
KMFMS "Bring the genome to the people!
···········@debian-rs.org
www.debian.org - www.debian-br.cipsga.org.br - www.debian-rs.org
synthespian wrote:
>> (defvar *a* (make-list 25 :initial-element 0))
>>
> This does not compute on CMUCL for Debian Woody
>
>> (defvar *b* (list 1 2 3))
>
> This does not compute on CMUCL for Debian Woody.
Both of these compute on my CMUCL on Debian Woody. When Pierre cut-n-pasted
the code, he also included the prompt, "*". You should, of course, skip
that.
Oleg
P.S. Debian rules!
>>>>> "Pierre" == Pierre R Mai <····@acm.org> writes:
Pierre> At no point is a non-immediate object ever copied in this
Pierre> sequence of events (and the copying of immediate objects
Pierre> isn't problematic, since those are immutable, and hence
Pierre> have no identity besides their value).
How does a system implementer decide which objects to represent
immediately? Is it just what one can fit into a machine word? Must
an immediate type be the size of a machine word (I'm assuming it
would)? Are there types the size of (or smaller than) a machine word
that aren't represented immediately? How much of a machine word does
one dedicate to tagging?
I'm also assuming that "immediately" means "not as a pointer to
another location in memory". Is this correct?
--
Matthew X. Economou <········@irtnog.org> - Unsafe at any clock speed!
I'm proud of my Northern Tibetian Heritage! (http://www.subgenius.com)
From: Pierre R. Mai
Subject: Re: Choosing immediate types (was "Re: Lisp for ANN programming")
Date:
Message-ID: <87u1p4f57l.fsf@orion.bln.pmsf.de>
"Matthew X. Economou" <···············@irtnog.org> writes:
> >>>>> "Pierre" == Pierre R Mai <····@acm.org> writes:
>
> Pierre> At no point is a non-immediate object ever copied in this
> Pierre> sequence of events (and the copying of immediate objects
> Pierre> isn't problematic, since those are immutable, and hence
> Pierre> have no identity besides their value).
>
> How does a system implementer decide which objects to represent
> immediately? Is it just what one can fit into a machine word? Must
> an immediate type be the size of a machine word (I'm assuming it
> would)? Are there types the size of (or smaller than) a machine word
> that aren't represented immediately? How much of a machine word does
> one dedicate to tagging?
There are many ways that one can go about designing an implementation,
and there are few restrictions mandated by ANSI CL. One of those is
that you can only represent as immediate values anything that has no
identity besides its value, or in other words: Everything that is
mutable (and arguably even some things that aren't), can't be
represented as an immediate value. Since immediate objects are going
to be copied implicitly all the time, they would otherwise loose their
identity. Since Common Lisp is really identity based, most objects
do have identity different from their current value.
I.e. one could get the idea of implementing very small bitvectors as
immediate words, since those could be made to fit into a word.
Howevery, you can't do this, since bitvectors, like all other vectors,
are mutable, and have an identity different from their current value,
so that you can't just randomly copy them all over the place. That
said, given the frequency of use of <24bit bitvectors, making them
immediate values is likely not a generally useful optimization,
anyway, so this isn't an accident.
Everything else is up to the implementor to decide, and depends on the
implementation language, the hardware, and various trade-offs.
That said, for CL implementations that do native-compilation direct to
assembly/machine-code (i.e. not via C) on current general purpose 32bit
hardware, some trends have established themselves:
* Uniform size of "lispval"
You really, really want to have a uniform size of what you consider
a lispval, since that enables many operations to work with lispvals
without having to first find out the type of the lispval in
question (which would have to happen at run-time, unless the user
declared the types in question, and a safety-level of 0, which is
rare for CL). Examples are function calling, list building, etc.
You'll usually want to use the largest size that your platform is
able to handle efficiently, and that most of your code is going to
make use off, which means 32bits for 32bit architectures, and
usually 64bits for 64bit architectures, though historically that
was a slightly tougher call to make (nowadays, with low-cost
memory and wide busses, the trend is probably to go 64bit, without
much hesitation).
Below this point, word means "lispval-sized word".
* Tagging
You use the 2-3 lower-most bits of a word for your primary tagging
mechanism, since those are wasted due to alignment anyway. The 2
lower-most bits are wasted because you really want 32bit-aligned
memory on 32bit machines. And since the smallest non-immediate
objects in CL usually require at least 2 words anyway, you lose not
much by going to 8 byte alignment, which gives you 3 bits for
tagging. (Add +1 for 64bit machines, mostly)
This tagging regime is made possible both by the alignment issues,
and by the existence of cheap fixed-offset indirect addressing
modes in current CPUs, so that (using Intel syntax)
MOV EDX, [EAX] ; Load word at addr EAX into EDX
and
MOV EDX, [EAX-3] ; Load word at addr EAX-3 into EDX
cost the same, so that for pointers the tag bits can be masked out
on the fly by the address calculation unit, instead of requiring
additional instructions and cycles. If your platform also supports
hardware traps for non-aligned accesses, you can even punt a
bit of your type-checking work to the hardware (ideally, from a
Lisp POV, the hardware traps would be cheap, going directly to
user-space, and would allow for a user-settable alignment size, so
that you could get traps for 8 byte alignment on 32bit machines).
Since you really want to have the widest size of fixnums possible,
you use 2 tags for fixnums, one for even and one for odd fixnums,
overlapping the least significant bit of the fixnum and the most
significant bit of the tag. So in effect you only decrease the
size of fixnums by 2 bits, but still have 6 tags left for other
primary types (with a pure 2bit tagging scheme, you'd have only 3
tags left, and with a pure 3bit tagging scheme you'd have smaller
fixnums).
Now you'll have to decide which types to assign their own primary
tags, and which are lumped together in their primary tag, and
require a secondary tag and/or header-word to disambiguate. As
discussed here recently, there are different ways of approaching
this issue. CMUCL/SBCL use:
000 -- even fixnum
001 -- function pointer
010 -- even other immediate
(header-words, characters, symbol-value trap value, etc.)
011 -- list pointer
100 -- odd fixnum
101 -- structure pointer
110 -- odd other immediate
111 -- other-pointer to data-blocks
(other than conses, structures, and functions)
Fixnums are an obvious candidate for their own tag, as are
list or cons/nil. Having a shared tag for all other immediates is
also common, since those are usually small enough to leave room for
an extended tag in their word (in CMUCL 8bit-wide, overlapping the
3bit normal tag).
Aside: Having the tag for fixnums be [01]00, is sensible for two
reasons: a) This allows addition/subtraction to work on tagged
fixnums, and requires only some shifting for multiplication and
division. b) Since most indexing is word-based (e.g. vectors,
structures, etc.), you can use the tagged fixnum directly for index
calculations, without detagging or shifting.
> I'm also assuming that "immediately" means "not as a pointer to
> another location in memory". Is this correct?
Yes, as in immediate addressing (though that doesn't necessarily come
into play here).
The internals documentation (fragments) of CMUCL, and the additional
notes in the SBCL Internals <http://ww.telent.net/sbcl-internals/>, as
well as many of the postings on c.l.l by Duane Rettig, will give you
more of an insight into some of the implementation decisions.
Regs, Pierre.
--
Pierre R. Mai <····@acm.org> http://www.pmsf.de/pmai/
The most likely way for the world to be destroyed, most experts agree,
is by accident. That's where we come in; we're computer professionals.
We cause accidents. -- Nathaniel Borenstein
Oleg <·····@to.the.newsgroup.please> writes:
> Barry Margolin wrote:
>
> > In article <············@newsmaster.cc.columbia.edu>,
> > Oleg <·····@to.the.newsgroup.please> wrote:
> >>What about passing by reference? Can, for example,
> >>M += s * V*V_traspose (M - matrix, V - vector, s - scalar)
> >>be implemented efficiently with Lisp, i.e. without unnecessary copying?
> >
> > Lisp *never* copies structured objects unless you call a copying function
> > explicitly. All argument passing is done by passing object references
> > (i.e. it's almost all pointers under the covers).
>
> The above example, M = M + s*V*(V^t), is part of BLAS 2 subroutine called
> DGER/SGER. M is both its argument and the returned value. Passing it by
> reference modifies M in place.
>
> I understand that what a Lisp programmer can do is define a function
> M + s*V*(V^t) -> A, and then assign its result to M, so copying will take
> place. Correct me if I'm wrong.
There are tricks you can use. I do not know if matlisp uses them.
Essentially you can write your functions using the following style:
(defun complex-matrix-stuff (m1 m2
&optional
(result
(make-appropriate-result-matrix-for m1 m2)))
... compute storing the results in `result'.
(return-from complex-matrix-stuff result))
Then you have it both ways. You can "make up results" on the fly as
in
(setf some-matrix (complex-matrix-stuff A B))
or reuse (destructively) previously allocated matrices.
(complex-matrix-stuff A B some-appropriate-matrix-I-built-before)
or
(setf some-other-matrix
(complex-matrix-stuff A B some-appropriate-matrix-I-built-before))
in which case, you'll end up with
(eq some-other-matrix some-appropriate-matrix-I-built-before)
==> T
>
> Is this the kind of case where macros need to be used?
>
As I showed you, not necessarily.
Now that I think about it, this may be one for the CookBook. :)
Cheers
--
Marco Antoniotti ========================================================
NYU Courant Bioinformatics Group tel. +1 - 212 - 998 3488
719 Broadway 12th Floor fax +1 - 212 - 995 4122
New York, NY 10003, USA http://bioinformatics.cat.nyu.edu
"Hello New York! We'll do what we can!"
Bill Murray in `Ghostbusters'.
Hello Oleg,
I coded up 12 NN learning paradigms in 1987
for SAIC's commercial ANSim product. In almost
all cases, I prototyped everything in MAC
Common Lisp (Coral back then?) - the usual
advantages of Lisp apply to experimenting with
artificial neural networks: ability to run
programs piecemeal - look at data, repeat, etc.
(BTW, for ANSim, I recoded in C for the product.)
That said, you might be better of starting with exisitng code
in C or C++ as it will probably be marginally more efficient.
Really, unless you are experimenting with your own
NN architectures and learning rules, why not use exisitng code?
-Mark
Oleg wrote:
> Hi
>
> I'm trying to evaluate for myself the usefulness of Lisp, specifically
> CMUCL, for Artificial Neural Networks programming. ANN algorithms involve
> plenty of
> .............