A thread on efficient matrix arithmetic in Common Lisp started at the
same time that I was trying to improve some of my own code implementing
a matrix class.
I noticed some limitations in Common Lisp that seem to be arbitrary and
rather unfortunate in this process and I was hoping someone could
provide me with an explanation. Lisp seems to avoid these kinds of
limitations more than most languages.
The first has to do with the appropriate place for a matrix type in the
class hierarchy. It should be a descendent of the number class. This
seems obvious to me. It should support the same set of methods that are
supported by numbers. Functions such as #'+ and #'* should accept a
matrix as an argument and if possible return the correct answer.
Here's the problem.
1) It is not legal to derive a class from a built-in-class.
2) There is no way to extend built in functions like #'+ to handle new
types of numbers.
3) There is no way to declare a method with a variable number of
arguments that are all members of some subset of the existing classes.
This isn't available in any other language I know of either but it
certainly seems to have its uses. It would allow a developer to
declare methods that specialize on a theoretically infinite number of
arguments. The performance hit may be optimized out by the compiler in
many instances. Even better would be something like a regular
expression syntax that specified the classes of the arguments. I know
this might be a bit on the excessive side.. :-)
I am sure that these limitations are not arbitrary, but what cost is
associated with them? Why were they left out of the language?
Thanks,
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------
The strongest reason for the people to retain their right to keep and
bear arms is, as a last resort, to protect themselves against tyranny
in government. -- Thomas Jefferson
Just some comments on your questions:
"Kenneth P. Turvey" wrote:
[snip]
> The first has to do with the appropriate place for a matrix type in the
> class hierarchy. It should be a descendent of the number class. This
> seems obvious to me. It should support the same set of methods that are
> supported by numbers. Functions such as #'+ and #'* should accept a
> matrix as an argument and if possible return the correct answer.
>
> Here's the problem.
>
> 1) It is not legal to derive a class from a built-in-class.
>
I would not worry too much about the location of the matrix class. Let
alone
I wouldn't go for a class implemenation. Using structures may be more
efficient
and simpler for both the implementor and user.
> 2) There is no way to extend built in functions like #'+ to handle new
> types of numbers.
Even if there were ways to extend the function #'+ there would be other
problems. In CMUCL when you say (+ a b) the compiler would actually
inline an addition function if it were to infer the types of a and b.
If you start extending the function #'+ then you may confuse the
compiler
and lose optimization.
[snip]
My general view towards matrices is that they allow for compact
representations
of many mathematical objects, I don't see them as programming
constructs.
As such, the capabilities of the matrix package should really be tuned
for numerical performance. My experience with lisp number crunching
has lead me to beleive that a system like LAPACK should be ported to
say CMUCL via the FFI interface (there should be no need to reinvent the
wheel).
As for other lisps I don't have too much experience with so I'll refrain
from
making any comments.
Tunc
> --
> Kenneth P. Turvey <······@SprocketShop.com>
> --------------------------------------------
> The strongest reason for the people to retain their right to keep and
> bear arms is, as a last resort, to protect themselves against tyranny
> in government. -- Thomas Jefferson
From: Marco Antoniotti
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <lw66xuuen8.fsf@parades.rm.cnr.it>
······@SprocketShop.com (Kenneth P. Turvey) writes:
> A thread on efficient matrix arithmetic in Common Lisp started at the
> same time that I was trying to improve some of my own code implementing
> a matrix class.
>
> I noticed some limitations in Common Lisp that seem to be arbitrary and
> rather unfortunate in this process and I was hoping someone could
> provide me with an explanation. Lisp seems to avoid these kinds of
> limitations more than most languages.
>
> The first has to do with the appropriate place for a matrix type in the
> class hierarchy. It should be a descendent of the number class. This
> seems obvious to me.
Why? It is not obvious to me.
> It should support the same set of methods that are
> supported by numbers. Functions such as #'+ and #'* should accept a
> matrix as an argument and if possible return the correct answer.
>
> Here's the problem.
>
> 1) It is not legal to derive a class from a built-in-class.
>
> 2) There is no way to extend built in functions like #'+ to handle new
> types of numbers.
(defpackage "GENERIC-MATH" (:use)
(:export "+" "-" "*" "/" "EXPT" "LOG" #|...|#))
(in-package "GENERIC-MATH")
(defclass matrix () (...))
(defgeneric + (arg1 &rest args))
(defgeneric +/arity2 (arg1 arg2))
(defmethod + ((arg1 number) &rest numbers)
(reduce #'+/arity2 :initial-value arg1))
(defmethod +/arity2 ((arg1 matrix) (arg2 matrix))
(matrix-multiply-with-green-numbers-flowing-down-the-screen arg1 arg2))
(defmethod +/arity2 ((arg1 matrix) (arg2 (eql 0)))
arg1)
(defmethod +/arity2 ((arg1 (eql 0)) (arg2 matrix))
arg2)
(defmethod +/arity2 ((arg1 number) (arg2 number))
(common-lisp:+ arg1 arg2))
I believe you get the idea. This is just an example...
> 3) There is no way to declare a method with a variable number of
> arguments that are all members of some subset of the existing classes.
> This isn't available in any other language I know of either but it
> certainly seems to have its uses. It would allow a developer to
> declare methods that specialize on a theoretically infinite number of
> arguments. The performance hit may be optimized out by the compiler in
> many instances.
The "sufficiently smart compiler" is very difficult to come by.
> Even better would be something like a regular
> expression syntax that specified the classes of the arguments. I know
> this might be a bit on the excessive side.. :-)
>
>
> I am sure that these limitations are not arbitrary, but what cost is
> associated with them? Why were they left out of the language?
I will leave this answer to other people :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
On 20 Dec 1999 10:48:11 +0100, Marco Antoniotti <·······@parades.rm.cnr.it> wrote:
>······@SprocketShop.com (Kenneth P. Turvey) writes:
[Snip]
>> The first has to do with the appropriate place for a matrix type in the
>> class hierarchy. It should be a descendent of the number class. This
>> seems obvious to me.
>
>Why? It is not obvious to me.
A matrix is simply another type of number.. just as complex numbers are
just another type of number.
>> 1) It is not legal to derive a class from a built-in-class.
Even if you disagree with me about the matrix class and its proper
location in the class hierarchy, certainly you must believe that there
exist other classes that would properly fit into the built-in class
hierarchy.
>> 2) There is no way to extend built in functions like #'+ to handle new
>> types of numbers.
>
>(defpackage "GENERIC-MATH" (:use)
> (:export "+" "-" "*" "/" "EXPT" "LOG" #|...|#))
>
>(in-package "GENERIC-MATH")
[Snip]
Thanks..
>I believe you get the idea. This is just an example...
>
>> 3) There is no way to declare a method with a variable number of
>> arguments that are all members of some subset of the existing classes.
>> This isn't available in any other language I know of either but it
>> certainly seems to have its uses. It would allow a developer to
>> declare methods that specialize on a theoretically infinite number of
>> arguments. The performance hit may be optimized out by the compiler in
>> many instances.
>
>The "sufficiently smart compiler" is very difficult to come by.
Yes.... the theory and the reality are often different.
>> Even better would be something like a regular
>> expression syntax that specified the classes of the arguments. I know
>> this might be a bit on the excessive side.. :-)
>>
>>
>> I am sure that these limitations are not arbitrary, but what cost is
>> associated with them? Why were they left out of the language?
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------
Duct tape is like the force. It has a light side, and a dark side,
and it holds the universe together ...
-- Carl Zwanzig
From: Tim Bradshaw
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <ey3ln6h37o3.fsf@cley.com>
* Kenneth P Turvey wrote:
> A matrix is simply another type of number.. just as complex numbers are
> just another type of number.
No no *no*. If anything, numbers are a kind of matrix (1x1
matrices). Matrices are *not* kinds of numbers because they do not
support all the operations numbers do -- specifically they do not
support division.
--tim
Actually, "number" is not a well defined expression in modern mathematics.
You could argue for example that numbers are elements of Dedekind domains...
I think, to say that a matrix is just another type of number is neither
wrong nor right; it has simply no meaning, at least not in mathematics.
In LISP however, if I understood that correctly, is "number" a well defined
concept and then matrices are not numbers in the LISP sense.
I hope I am not hurting anybody's feelings.
Janos Blazi
Tim Bradshaw <···@cley.com> schrieb in im Newsbeitrag:
···············@cley.com...
> * Kenneth P Turvey wrote:
> > A matrix is simply another type of number.. just as complex numbers are
> > just another type of number.
>
> No no *no*. If anything, numbers are a kind of matrix (1x1
> matrices). Matrices are *not* kinds of numbers because they do not
> support all the operations numbers do -- specifically they do not
> support division.
>
> --tim
From: Tim Bradshaw
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <ey34sddwywv.fsf@cley.com>
* Kenneth P Turvey wrote:
> The first has to do with the appropriate place for a matrix type in the
> class hierarchy. It should be a descendent of the number class. This
> seems obvious to me. It should support the same set of methods that are
> supported by numbers. Functions such as #'+ and #'* should accept a
> matrix as an argument and if possible return the correct answer.
I think in order to do this you'd need a much more principled class
graph of `numerical' types. For instance, there is no division for
(square) matrices because they are only a ring, while real numbers,
say, are a field. So logically speaking numbers should be further
*down* the graph.
But this is obviously wrong because something like `being an X' where
X is ring or group or field is not really the sort of thing that fits
well into an OO paradigm. Really, `being a group', say, says that you
support an operation, say *, with some properties, but just because
class A is a group and class B is a group does not mean that A*B makes
any kind of sense.
So I don't understand how this should work, but I think it's not
simple (or perhaps it just seems non-simple because I have 'flu...).
--tim
Nice point, but of course the group class would not support "*". Instead it
would have methods like "subgroup" to return a list of all subgroups,
"normal" to test if a group is a normal subgroup of another group, or even
the predicate "solvable-p", hahaha.
As far as matrices are concerned they can be easily represented in LISP via
lists (to mention the most trivial representation only) and then all
computations are as simple or as complicated as in C. LISP does not offer
any advantages over C or even FORTRAN when it is used to perform numerical
computations. It offers an advantage however when it comes to symbolic
computations.
Janos Blazi
Tim Bradshaw <···@cley.com> schrieb in im Newsbeitrag:
···············@cley.com...
> * Kenneth P Turvey wrote:
>
> > The first has to do with the appropriate place for a matrix type in the
> > class hierarchy. It should be a descendent of the number class. This
> > seems obvious to me. It should support the same set of methods that are
> > supported by numbers. Functions such as #'+ and #'* should accept a
> > matrix as an argument and if possible return the correct answer.
>
> I think in order to do this you'd need a much more principled class
> graph of `numerical' types. For instance, there is no division for
> (square) matrices because they are only a ring, while real numbers,
> say, are a field. So logically speaking numbers should be further
> *down* the graph.
>
> But this is obviously wrong because something like `being an X' where
> X is ring or group or field is not really the sort of thing that fits
> well into an OO paradigm. Really, `being a group', say, says that you
> support an operation, say *, with some properties, but just because
> class A is a group and class B is a group does not mean that A*B makes
> any kind of sense.
>
> So I don't understand how this should work, but I think it's not
> simple (or perhaps it just seems non-simple because I have 'flu...).
>
> --tim
"Janos Blazi" <······@netsurf.de> writes:
[clip]
> LISP does not offer
> any advantages over C or even FORTRAN when it is used to perform numerical
> computations. It offers an advantage however when it comes to symbolic
> computations.
But the ability to easily perform symbolic computations is a great
advantage in numerical computation! For example, right now I'm working
on very large sparse matrices with relatively complicated structure, and
Lisp makes it practical to symbolically manipulate the structure of
matrix products in preparation for numerical methods.
Hannu Rummukainen
Janos Blazi wrote:
> Nice point, but of course the group class would not support "*". Instead it
> would have methods like "subgroup" to return a list of all subgroups,
> "normal" to test if a group is a normal subgroup of another group, or even
> the predicate "solvable-p", hahaha.
I don't see any reason why "solvable-p" is a silly idea. And why
shouldn't A*B be the direct product of A and B? :-)
> As far as matrices are concerned they can be easily represented in LISP via
> lists (to mention the most trivial representation only) and then all
> computations are as simple or as complicated as in C. LISP does not offer
> any advantages over C or even FORTRAN when it is used to perform numerical
> computations. It offers an advantage however when it comes to symbolic
> computations.
Lisp does offer advantages over C and FORTRAN for doing numerical
calculations. I don't understand why you think it doesn't. (It
also has minor disadvantages: the old syntax issue matters more
when most of your program consists of mathematical expressions,
and Lisp compilers still don't usually make quite such fast code
as C and FORTRAN compilers.)
--
Gareth McCaughan ················@pobox.com
sig under construction
"solvable-p" is probably not a silly idea but I simply do not know how
something like this should be done. I do not know any literature about
computational group theory (I mean a text book) and I'd be interested in the
subject. ANY ADVICE? Of course I know MAGMA and I saw a Springer Lecture
Note concerning computational permutation groups (maybe by BUTLER. I do not
remember).
As far as numerical computations are concerned LISP has no "**" operator
like FORTRAN and I think this is a very serious shortcoming from a numerical
analyst's point of view. I'd be interested in being told about the
advantages of LISP concerning numerical computations.
Janos Blazi
Gareth McCaughan <················@pobox.com> schrieb in im Newsbeitrag:
··············@g.local...
> Janos Blazi wrote:
>
> > Nice point, but of course the group class would not support "*". Instead
it
> > would have methods like "subgroup" to return a list of all subgroups,
> > "normal" to test if a group is a normal subgroup of another group, or
even
> > the predicate "solvable-p", hahaha.
>
> I don't see any reason why "solvable-p" is a silly idea. And why
> shouldn't A*B be the direct product of A and B? :-)
>
> > As far as matrices are concerned they can be easily represented in LISP
via
> > lists (to mention the most trivial representation only) and then all
> > computations are as simple or as complicated as in C. LISP does not
offer
> > any advantages over C or even FORTRAN when it is used to perform
numerical
> > computations. It offers an advantage however when it comes to symbolic
> > computations.
>
> Lisp does offer advantages over C and FORTRAN for doing numerical
> calculations. I don't understand why you think it doesn't. (It
> also has minor disadvantages: the old syntax issue matters more
> when most of your program consists of mathematical expressions,
> and Lisp compilers still don't usually make quite such fast code
> as C and FORTRAN compilers.)
>
> --
> Gareth McCaughan ················@pobox.com
> sig under construction
From: Johan Kullstam
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <m2vh5s75h0.fsf@sophia.axel.nom>
"Janos Blazi" <······@netsurf.de> writes:
> As far as numerical computations are concerned LISP has no "**"
> operator like FORTRAN and I think this is a very serious shortcoming
> from a numerical analyst's point of view.
what is expt?
> I'd be interested in being told about the advantages of LISP
> concerning numerical computations.
what is lisp good at? it has nice handling of variable sized objects.
lisp is very good at computations involving allocating (potentially)
unbounded memory. lisp is good for implementing a romberg integration
tableau for example.
--
J o h a n K u l l s t a m
[········@ne.mediaone.net]
Don't Fear the Penguin!
From: Tim Bradshaw
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <ey37li85r4o.fsf@cley.com>
* Janos Blazi wrote:
> As far as numerical computations are concerned LISP has no "**" operator
> like FORTRAN and I think this is a very serious shortcoming from a numerical
> analyst's point of view.
It's called EXPT, in fact. OK, 2 more characters to type I know, but
you may be able to work out how to define something called ** which
does the same thing.
If you mean `lisp has no *infix* ** operator'. Well, Lisp has *no*
infix operators. If you want infix in Lisp use an infix package,
which very likely include an infix exponentiation operator (defined to
expand to EXPT).
--tim
From: Marco Antoniotti
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <lwyaaocnts.fsf@parades.rm.cnr.it>
Tim Bradshaw <···@cley.com> writes:
> If you mean `lisp has no *infix* ** operator'. Well, Lisp has *no*
> infix operators. If you want infix in Lisp use an infix package,
> which very likely include an infix exponentiation operator (defined to
> expand to EXPT).
* (load "HOME:lang;cl;lisp-utilities;infix.bytef")
; Loading #p"/users/marcoxa/lang/cl/lisp-utilities/infix.bytef".
;;; *************************************************************************
;;; Infix notation for Common Lisp.
;;; Version 1.3 28-JUN-96.
;;; Written by Mark Kantrowitz, CMU School of Computer Science.
;;; Copyright (c) 1993-95. All rights reserved.
;;; May be freely redistributed, provided this notice is left intact.
;;; This software is made available AS IS, without any warranty.
;;; *************************************************************************
T
* (defvar i #C(0 1))
I
* #I( i^^2 )
-1
* (macroexpand +)
(EXPT I 2)
NIL
*
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
(1)
Tim Bradshaw <···@cley.com> schrieb in im Newsbeitrag:
···············@cley.com...
>
> It's called EXPT, in fact. OK, 2 more characters to type I know, but
> you may be able to work out how to define something called ** which
> does the same thing.
>
Of course I knew that it was possible to compute powers in CL! But I EXPT is
a function that takes its arguments at runtime and evaluates them at
runtime. On the other hand in FORTRAN as far as I know the "**" operator can
be dealt with at compile time if the exponent is constant and then the
compiler can choose the "best" strategy for the computation (or at least a
very good strategy). FORTRAN offers this built-in operator and C/C++ does
not. Neither does CL as far as I know.
(2)
Somebody mentioned that CL has rationals. I do not think that rationals are
very important in numerical computations (numerical in the classical sense).
When you use rationals you want to have *exact* answers and this is what I
referred to as *symbolic*. Clearly, for several reasons CL is a superior
tool for this kind of computation. The only tool I know that paralells the
power of CL in this field is something like MAPLE V. But using MAPLE V
instead of CL would have other disadvantages.
(3)
Again: C is nothing sinister. It was a very good language to read hardware
ports, drive floppies and for other assembly language type chores. It had
never been intended to solve problems you would solve with CL. The problems
began when C++ was created.
(4)
I think we should always use the right tool, sine ira et studio. For some
problems it is still C or even assembly language, for other problems CL, for
simple scripting jobs PERL or Python, etc.
Janos Blazi
Janos Blazi <······@netsurf.de> wrote in message
····································@broadway.news.is-europe.net...
> Of course I knew that it was possible to compute powers in CL! But I EXPT
is
> a function that takes its arguments at runtime and evaluates them at
> runtime. On the other hand in FORTRAN as far as I know the "**" operator
can
> be dealt with at compile time if the exponent is constant and then the
> compiler can choose the "best" strategy for the computation (or at least a
> very good strategy). FORTRAN offers this built-in operator and C/C does
> not. Neither does CL as far as I know.
Well, it does. Things that appear as functions in the source code don't
actually have to be implemented as functions at runtime. For instance, most
C compilers for the PC generate the code for strcpy, strcmp, etc. inline,
using the x86's specialized string handling instructions. A lot of FORTRAN
IV compilers in their heyday defined (in addition to the ** operator)
exponential function calls that were often specially noticed by the compiler
if called with an integer power parameter larger than the basic word size
and inlined (at least he DEC, and IBM compilers had these).
What does this have to do with Lisp? Well, first of all, most Lisp code
these days isn't interpreted. It's compiled. I don't know of ANY deployed
Lisp system that's running interpreted. In fact, some Lisp systems don't
even have interpreters - they just compile the input from the REP loop,
execute the code, and print the result. And, most CL compilers know very
well how to do all of the constant expression manipulation that Fortran
compilers do and most convert products like (expt x i) into product trees.
In fact, even most interpreters check for this special case and transform
the product into multiplications.
BTW, not many FORTRAN compilers actually choose the "best" product tree
(last I heard, that was still an NP complete problem). Most of them do the
same thing that the Lisp compilers do (or is that the other way around?) -
statically unfolding the exponentiation in powers of two or three with the
odd multiplication thrown in occasionally.
The one place where FORTRAN compilers do have an easier time is determining
when an exponent is actually an integer. But even compiled Lisps can be
told that the parameter in question is an integer and compile the same code.
faa
From: Tim Bradshaw
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <ey3g0wv47s8.fsf@cley.com>
* Janos Blazi wrote:
> (1)> Of course I knew that it was possible to compute powers in CL! But I EXPT is
> a function that takes its arguments at runtime and evaluates them at
> runtime. On the other hand in FORTRAN as far as I know the "**" operator can
> be dealt with at compile time if the exponent is constant and then the
> compiler can choose the "best" strategy for the computation (or at least a
> very good strategy). FORTRAN offers this built-in operator and C/C++ does
> not. Neither does CL as far as I know.
This is getting annoying. Not only can lisp, just obviously, do
optimizations like this too, many implementations -- including some
free ones -- actually do them. In fact, Lisp goes further than that
-- you can define compiler macros *yourself* in the language which
can do a lot of this kind of work for your own idiosyncratic
functions. You can't do that in Fortran.
Compile this in CMUCL and see what it says:
(defun trivial (x)
(declare (type fixnum x))
(values
(expt x 2)
(locally (declare (optimize speed))
(expt x 2))
(locally (declare (optimize speed))
(the fixnum (expt x 2)))
(locally (declare (optimize speed (safety 0)))
(the fixnum (expt x 2)))))
It seems that the good old traditions of people making bald assertions
about Lisp without any effort to check facts or try things in an
implementation are not dying out.
--tim
Tim Bradshaw <···@cley.com> writes:
> It seems that the good old traditions of people making bald assertions
> about Lisp without any effort to check facts or try things in an
> implementation are not dying out.
It is like that all over Usenet, on all topics...
Stig Hemmer,
Jack of a Few Trades.
From: Erik Naggum
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <3154866774070002@naggum.no>
* Tim Bradshaw
| It seems that the good old traditions of people making bald assertions
| about Lisp without any effort to check facts or try things in an
| implementation are not dying out.
* Stig Hemmer <····@pvv.ntnu.no>
| It is like that all over Usenet, on all topics...
but most of the time, it's new people who make this mistake, not people
who have hung around for a while and received _billions_and_billions_ of
hints as to how they are annoying people and how to stop annoying people.
most people learn from experience, but some learn to be _more_ annoying.
#:Erik
From: Marco Antoniotti
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <lw7li75kab.fsf@parades.rm.cnr.it>
"Janos Blazi" <······@netsurf.de> writes:
> (1)
>
> Tim Bradshaw <···@cley.com> schrieb in im Newsbeitrag:
> ···············@cley.com...
> >
> > It's called EXPT, in fact. OK, 2 more characters to type I know, but
> > you may be able to work out how to define something called ** which
> > does the same thing.
> >
>
> Of course I knew that it was possible to compute powers in CL! But I EXPT is
> a function that takes its arguments at runtime and evaluates them at
> runtime. On the other hand in FORTRAN as far as I know the "**" operator can
> be dealt with at compile time if the exponent is constant and then the
> compiler can choose the "best" strategy for the computation (or at least a
> very good strategy). FORTRAN offers this built-in operator and C/C++ does
> not. Neither does CL as far as I know.
What if your FORTRAN or C/C++ *compiler* decided to implement the **
(or equivalent) operator as a function call? What if your CL
*compiler* decided to inline a call to the EXPT function based on the
type information?
Here is what CMUCL does at the highest optimization settings on a Sparc.
* (defun power (x n)
(declare (type fixnum x n))
(expt x n))
POWER
* (compile 'power)
POWER
NIL
NIL
* (disassemble 'power)
07341478: .ENTRY POWER(x n) ; (FUNCTION (FIXNUM FIXNUM)
RATIONAL)
90: ADD -18, %CODE
94: ADD %CFP, 32, %CSP
98: MOVE %OCFP, %NFP
9C: MOVE %LRA, %A3 ; No-arg-parsing entry point
A0: LD [%CODE+13], %CNAME
A4: ADD %ZERO, 8, %NARGS
A8: LD [%CNAME+5], %A2
AC: MOVE %NFP, %OCFP
B0: MOVE %A3, %LRA
B4: J %A2+23
B8: MOVE %A2, %CODE
BC: UNIMP 0
*
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
From: Raymond Toy
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <4nd7rz2h2s.fsf@rtp.ericsson.se>
>>>>> "Marco" == Marco Antoniotti <·······@parades.rm.cnr.it> writes:
Marco> Here is what CMUCL does at the highest optimization settings on a Sparc.
Marco> * (defun power (x n)
Marco> (declare (type fixnum x n))
Marco> (expt x n))
Marco> POWER
Marco> * (compile 'power)
Marco> POWER
Marco> NIL
Marco> NIL
Marco> * (disassemble 'power)
Marco> 07341478: .ENTRY POWER(x n) ; (FUNCTION (FIXNUM FIXNUM)
Marco> RATIONAL)
Marco> 90: ADD -18, %CODE
Marco> 94: ADD %CFP, 32, %CSP
Marco> 98: MOVE %OCFP, %NFP
Marco> 9C: MOVE %LRA, %A3 ; No-arg-parsing entry point
Marco> A0: LD [%CODE+13], %CNAME
Marco> A4: ADD %ZERO, 8, %NARGS
Marco> A8: LD [%CNAME+5], %A2
Marco> AC: MOVE %NFP, %OCFP
Marco> B0: MOVE %A3, %LRA
Marco> B4: J %A2+23
Marco> B8: MOVE %A2, %CODE
Marco> BC: UNIMP 0
Marco> *
Umm, I don't think this is really what you wanted to show, since this
just calls the generic expt routine (the J at B4). I think this might
be a better example of what you wanted to show:
* (defun power (x)
(declare (type (double-float 0d0) x)
(optimize (speed 3) (safety 0) (debug 0)))
(expt x 7/2))
* (compile 'power)
* (disassemble 'power)
0720E3D8: .ENTRY POWER() ; FUNCTION
3F0: ADD -18, %CODE
3F4: ADD %CFP, 32, %CSP
3F8: LDDF [%A0+1], %F0
3FC: FSQRTD %F0, %F2 ; No-arg-parsing entry point
400: FMULD %F2, %F2, %F0
404: FMULD %F2, %F0, %F0
408: FMULD %F0, %F0, %F0
40C: FMULD %F2, %F0, %F0
[snip the stuff to allocate space for the result]
Instructions at 400-40c are computing the 7'th power of (sqrt x) via
the binary method.
(Note: this example includes my patch to the compiler to enable this
transformation. The stock CMUCL doesn't do this.)
Ray
From: Raymond Toy
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <4ng0wv2hgx.fsf@rtp.ericsson.se>
>>>>> "Janos" == Janos Blazi <······@netsurf.de> writes:
Janos> Of course I knew that it was possible to compute powers in
Janos> CL! But I EXPT is a function that takes its arguments at
Janos> runtime and evaluates them at runtime. On the other hand in
Janos> FORTRAN as far as I know the "**" operator can be dealt
Janos> with at compile time if the exponent is constant and then
Janos> the compiler can choose the "best" strategy for the
Janos> computation (or at least a very good strategy). FORTRAN
Janos> offers this built-in operator and C/C++ does not. Neither
Janos> does CL as far as I know.
CMUCL can convert (expt x n) for n = +/- 1, +/- 2, +/- 3 to the
obvious set of multiplications and divisions. (expt x 1/2) gets
converted to (sqrt x), and (expt x 1/4) becomes (sqrt (sqrt x)).
In addition, I have a patch that extends this so that if n = p/q where
p and q are integers, q = 1, 2, or 3, and p is sufficiently small,
(expt x n) gets converted into a series of sqrt's, cube roots, and
multiplications (using the binary method). This change to the
compiler was quite easy.
This, of course, only happens if the type of x is known at
compile-time and if n is a constant, known at compile-time, as you
wanted.
Ray
From: Erik Naggum
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <3154854543007221@naggum.no>
* "Janos Blazi" <······@netsurf.de>
| Of course I knew that it was possible to compute powers in CL! But I
| EXPT is a function that takes its arguments at runtime and evaluates them
| at runtime.
why can't you just QUIT posting your ignorant drivel, Janos Blazi?
a Common Lisp compiler is free to inline or transform any call to a
function in the COMMON-LISP package, including pre-computing its value if
the arguments are all compile-time constants. this freedom is OBVIOUSLY
not dependent on the number or kind of characters in the name of the
function, which you seem to think it is.
| When you use rationals you want to have *exact* answers and this is what
| I referred to as *symbolic*.
is the rest of the janos-speak dictionary available on the Net?
| I think we should always use the right tool, sine ira et studio.
the right tool is surprisingly often the brain. if it doesn't work, it
may be most appropriate to abstain from posting USENET articles, but it
may also be acceptable to ask questions instead of posting assumptions.
#:Erik
From: Marco Antoniotti
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <lw3dswe31h.fsf@parades.rm.cnr.it>
"Janos Blazi" <······@netsurf.de> writes:
> "solvable-p" is probably not a silly idea but I simply do not know how
> something like this should be done. I do not know any literature about
> computational group theory (I mean a text book) and I'd be interested in the
> subject. ANY ADVICE? Of course I know MAGMA and I saw a Springer Lecture
> Note concerning computational permutation groups (maybe by BUTLER. I do not
> remember).
>
> As far as numerical computations are concerned LISP has no "**" operator
> like FORTRAN and I think this is a very serious shortcoming from a numerical
> analyst's point of view.
Are we having a bad case of RTFM? :)
EXP and EXPT are there for you.
* (defvar i #C(0 1))
I
* (expt i 2)
-1
> I'd be interested in being told about the
> advantages of LISP concerning numerical computations.
I just showed you one. :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
Janos Blazi wrote:
> "solvable-p" is probably not a silly idea but I simply do not know how
> something like this should be done. I do not know any literature about
> computational group theory (I mean a text book) and I'd be interested in the
> subject. ANY ADVICE? Of course I know MAGMA and I saw a Springer Lecture
> Note concerning computational permutation groups (maybe by BUTLER. I do not
> remember).
I don't know anything non-trivial about computational group theory
either. Sorry.
> As far as numerical computations are concerned LISP has no "**" operator
> like FORTRAN
but it does have an EXPT function that does exactly the same thing
> and I think this is a very serious shortcoming from a numerical
> analyst's point of view. I'd be interested in being told about the
> advantages of LISP concerning numerical computations.
Much the same as its advantages for other kinds of work.
- Readily extensible, with a good object system, so that
if you find that you want to work with quaternions or
rank-3 tensors or something then it needn't be too painful
to do so.
- Interactive: great for exploratory work, where you're not
sure whether the approach you're trying is quite right.
You can plug in some typical inputs and try things out
without needing to keep recompiling things.
- A good language for expressing complicated algorithms,
such are often needed for efficient numerical work.
- Automatic memory management: you can create whatever
complex objects you need to, and pass them around in
functional style, without worrying about where they're
going to get deallocated.
And there are a few that are specifically useful for numerical
stuff.
- Complex numbers.
- Rational numbers, so that you can (when you need to) do
(some) calculations to whatever precision you require.
- Carefully thought out mathematical functions, with due
attention given to branch points.
- Half-decent facilities for getting at the underlying FP
representations of your hardware (DECODE-FLOAT and all
that). Not as good as FORTRAN offers, if I understand
aright, but certainly better than C.
- Multiple values make for neater interfaces to functions
that compute (say) an approximation to a number and a
bound on the error, or the minimum value of a function
and a point at which it's attained, or whatever.
There are probably lots more.
--
Gareth McCaughan ················@pobox.com
sig under construction
From: Raymond Toy
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <4niu1r2hs2.fsf@rtp.ericsson.se>
>>>>> "Gareth" == Gareth McCaughan <················@pobox.com> writes:
Gareth> And there are a few that are specifically useful for numerical
Gareth> stuff.
Gareth> - Complex numbers.
Unfortunately, for heavy-duty numerical computations on complex
numbers, most lisps will cons to death, since they must box up complex
numbers. They only Lisp I know of that doesn't box up complex numbers
is CMUCL, which has unboxed (complex single-float) and
(complex double-float).
Ray
On Mon, 20 Dec 1999 21:09:53 +0100, "Janos Blazi" <······@netsurf.de>
wrote:
> computations are as simple or as complicated as in C. LISP does not offer
> any advantages over C or even FORTRAN when it is used to perform numerical
> computations. It offers an advantage however when it comes to symbolic
See:
"Fast Floating Point Processing in Common Lisp"
(K.A. Broughan, D. Rettig, R.J. Fateman, D.K. Willcock)
ftp://peoplesparc.berkeley.edu/pub/papers/lispfloat.ps
Paolo
--
EncyCMUCLopedia * Extensive collection of CMU Common Lisp documentation
http://cvs2.cons.org:8000/cmucl/doc/EncyCMUCLopedia/
From: Erik Naggum
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <3154816073744645@naggum.no>
* Kenneth P. Turvey
| I noticed some limitations in Common Lisp that seem to be arbitrary and
| rather unfortunate in this process and I was hoping someone could
| provide me with an explanation.
you seem to ignore the obvious solution to your problems, and that makes
you believe you have a limitation in Common Lisp when you actually don't.
| Lisp seems to avoid these kinds of limitations more than most languages.
indeed.
| The first has to do with the appropriate place for a matrix type in the
| class hierarchy. It should be a descendent of the number class. This
| seems obvious to me.
it seems obviously wrong to me. if I were implementing matrices in C++,
however, it would seem obviously right, but that's because C++ has a very
different class concept that IMNSHO is an insurmountable liability for
that language alone and should not impact any other languages.
| It should support the same set of methods that are supported by numbers.
| Functions such as #'+ and #'* should accept a matrix as an argument and
| if possible return the correct answer.
this, however, seems reasonable, but methods are not members of classes
in CLOS, and class hierarchies are less tightly coupled with method
selection than in C++. in brief, you don't need to be a subclass to
implement methods whose meaning is defined for some other classes.
| Here's the problem.
|
| 1) It is not legal to derive a class from a built-in-class.
whether a built-in-class is a superclass of a class or the class of a
slot in a class is largely an implementation detail.
| 2) There is no way to extend built in functions like #'+ to handle new
| types of numbers.
this is both true and false. it's true in the trivial sense that if you
try to do it directly, you can't. it's false in that you _can_ get the
effect you want. at issue is _which_ + you refer to. Common Lisp does
not do overloading the way C++ does, and does not do namespaces like C++,
either, but you can shadow the symbols whose meaning you want to change,
and _completely_ change their meaning if you so wish. in other words,
you can use functions named MATRIX:+ instead of COMMON-LISP:+, but what
your code contains may still be +, depending on the value of *PACKAGE*.
getting the compiler to be as efficient with MATRIX:+ as with CL:+ may be
hard, but it's doable, and if you need very high performance you will
most probably get help from the vendor in achieving it.
| 3) There is no way to declare a method with a variable number of
| arguments that are all members of some subset of the existing classes.
"declare"? my bogometer indicates that you're really programming in some
other language and trying to force Common Lisp into your mindset. this
won't work. the limitations you experience are due to friction you see
when you attempt the impossible.
Common Lisp programmers are generally aware that the functions they
define do a lot of work behind the scenes and that lambda lists aren't
free, that method combination and dispatch aren't free, and that if they
need special powers, that _they_ are free to define new macros or other
forms that do similar expensive operations behind the scene. in your
case, you need do no more than define a macro to define methods that
accept _one_ argument of the appropriate class, then, perhaps depending
on some optimization settings, checks to see if the rest of the arguments
are of the same class as whatever made that method be selected. this is
a fairly trivial extension to the existing features in the language.
| I am sure that these limitations are not arbitrary, but what cost is
| associated with them? Why were they left out of the language?
a more appropriate question is: why didn't you program them back in when
you needed them? this is Common Lisp, the programmable programming
language. C++ is the language you sit around and wait to evolve yet
another feature that might be used "close enough" to what you need.
your complaints reduce to syntactic issues. you can do all you want to
do, but you might need to be more verbose to make it perform well. this
is not a _semantic_ language limitation in my book, which is what you
imply that this is. since the syntax of Common Lisp is eminently
customizable, your complaints reduce to a question of how to program the
syntax to fit your preconceptions of what the syntax should look like.
I'm sure this can be achieved, but if you limit _yourself_ to particular
ways of doing things, such as remaining stuck in the C++ world, that's
where you need to make some changes first.
incidentally, asking why things are "left out of the language" is a good
sign that the asker is fairly clueless. first of all, it's a question
that can be asked only in retrospect, and as such it's an anachronistic
accuation, meaning: you think somebody is at fault for not having done
what you think they should have done because you need something since you
can't (easily) do what you want and that must be somebody's fault.
second, anything is possible, so leaving something out of a language is a
fairly meaningless thing to do in the first place. the matter at hand is
_convenience_. all you actually ask is "why isn't _this_ convenient?".
it's hard to answer that question without answering the implied general
question: "why haven't all programming problems been solved already?"
#:Erik
On 22 Dec 1999 01:47:53 +0000, Erik Naggum <····@naggum.no> wrote:
I'm not going to respond to your whole post... This is pretty much what
I expect from you.
>* Kenneth P. Turvey
>| 1) It is not legal to derive a class from a built-in-class.
>
> whether a built-in-class is a superclass of a class or the class of a
> slot in a class is largely an implementation detail.
It is still illegal to derive from a built-in-class... what does it buy
us?
>| 2) There is no way to extend built in functions like #'+ to handle new
>| types of numbers.
>
> this is both true and false. it's true in the trivial sense that if you
> try to do it directly, you can't. it's false in that you _can_ get the
> effect you want. at issue is _which_ + you refer to. Common Lisp does
> not do overloading the way C++ does, and does not do namespaces like C++,
> either, but you can shadow the symbols whose meaning you want to change,
> and _completely_ change their meaning if you so wish. in other words,
> you can use functions named MATRIX:+ instead of COMMON-LISP:+, but what
> your code contains may still be +, depending on the value of *PACKAGE*.
>
> getting the compiler to be as efficient with MATRIX:+ as with CL:+ may be
> hard, but it's doable, and if you need very high performance you will
> most probably get help from the vendor in achieving it.
I'll buy this argument. Another poster mentioned this and provided some
example code.
>| 3) There is no way to declare a method with a variable number of
>| arguments that are all members of some subset of the existing classes.
>
> "declare"? my bogometer indicates that you're really programming in some
> other language and trying to force Common Lisp into your mindset. this
> won't work. the limitations you experience are due to friction you see
> when you attempt the impossible.
Would you be happier if I used the word "define". It doesn't change the
meaning nor does it remove the limitation.
[Snip]
>
>| I am sure that these limitations are not arbitrary, but what cost is
>| associated with them? Why were they left out of the language?
>
> a more appropriate question is: why didn't you program them back in when
> you needed them? this is Common Lisp, the programmable programming
> language. C++ is the language you sit around and wait to evolve yet
> another feature that might be used "close enough" to what you need.
>
[Snip]
>
> incidentally, asking why things are "left out of the language" is a good
> sign that the asker is fairly clueless. first of all, it's a question
> that can be asked only in retrospect, and as such it's an anachronistic
> accuation, meaning: you think somebody is at fault for not having done
> what you think they should have done because you need something since you
> can't (easily) do what you want and that must be somebody's fault.
> second, anything is possible, so leaving something out of a language is a
> fairly meaningless thing to do in the first place. the matter at hand is
> _convenience_. all you actually ask is "why isn't _this_ convenient?".
> it's hard to answer that question without answering the implied general
> question: "why haven't all programming problems been solved already?"
Translation:
I have offended Erik by asking a about a limitation in Common Lisp.
--
Kenneth P. Turvey <······@SprocketShop.com>
--------------------------------------------
Reasonable people adapt themselves to the world. Unreasonable people
attempt to adapt the world to themselves. All progress, therefore,
depends on unreasonable people. -- George Bernard Shaw
From: Erik Naggum
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <3155616264280562@naggum.no>
* Kenneth P. Turvey
| Translation:
|
| I have offended Erik by asking a about a limitation in Common Lisp.
well, it doesn't surprise me that you can't translate, either.
there are lots of limitations in Common Lisp. your "limitation" isn't
one of them, it's a limitation with you, only. this is very often the
sorry state of affairs with (stupid) complainers. the case for an actual
limitation in the language has to be made by people who (1) know the
language well, (2) are creative in using it, and (3) don't give up and
above all don't blame the language when they fail. I'll settle for two
out of three. let me know how many requirements you think you satisfy.
the day when somebody on comp.lang.lisp is able to address a limitation
in Common Lisp (and not only in himself) will be a remarkable day. no,
make that comp.lang.*, not just c.l.l.
#:Erik
From: Tim Bradshaw
Subject: Re: Matrix type... question on Lisp implementation..
Date:
Message-ID: <ey31z83e3z6.fsf@cley.com>
* Kenneth P Turvey wrote:
>> | 3) There is no way to declare a method with a variable number of
>> | arguments that are all members of some subset of the existing classes.
>>
>> "declare"? my bogometer indicates that you're really programming in some
>> other language and trying to force Common Lisp into your mindset. this
>> won't work. the limitations you experience are due to friction you see
>> when you attempt the impossible.
> Would you be happier if I used the word "define". It doesn't change the
> meaning nor does it remove the limitation.
I would be convinced it was a limitation if someone could demonstrate
a reasonably efficient implementation technique for such a thing, or a
reasonably convincing use for it. (Of course, CL is a language such
that if you *can* demonstrate a reasonable implementation technique,
then you can probably produce a syntactically-reasonable
implementation rather rapidly).
In the case of arithmetic -- which seems to be the issue here -- I
think such a thing would be almost useless even if you had it. I'm
not expert on computer arithmetic, but even I can see that the kind of
thing you want to do is:
Reduce everything to binary operations -- which are what the
machine supports in any case.
Possibly reorder the objects you're operating on in such a way
as to reduce conversions and precision loss.
So if you have something like:
(* fixnum (matrix float) (matrix fixnum) float)
You probably actually want to evaluate something like:
(* (* (matrix float) float) (FLOAT (* (matrix fixnum) fixnum)))
(apologies for the appalling notation. Things in CAPS are meant to be
operators, in lc indications of type).
If you're doing purely symbolic stuff then you don't have the
precision problems but you have other ones to do with intermediate
expression explosion which lead you to be just as careful -- you
typically want to order your operations carefully and also compile
code that looks like:
(simplify (op a (simplify (op b c))))
I think, in general, that the whole arithmetic thing fits really
poorly into any kind of OO paradigm. You can see this because the
moment you try doing things like defining methods for arithmetic
operations you end up defining an awful lot of them at an awful lot of
different places in the class graph, and you end up with lots of
strange cases. Certainly even I can see that very few of the rather
facile `matrices should be a subclass of x and + should be generic'
claims that get made here (and doubtless elsewhere) make any kind of
sense at all.
--tim