Hi,
I have a couple of questions about types and classes that would probably
best be answered by looking at other code - please feel free to suggest
specific examples (I have looked at some samples from the Ohio
repository, but didn't see anything that answered the following):
1) How do I write a method which is selected based on the class of an
argument *in a list*. For example, consider two methods that take
lists, one of objects of class A and the other objects of class B, where
A is a subset of B. Is this possible (it seems like the method needs to
be selected on type rather than class...)? If not, what is the standard
solution - to have different "list" classes for A and B?
2) This really is just a case of needing examples: I have some code
that, sometime soon, I'd like to specify the types of various items to
see if I can get an increase in speed. I can get a few simple examples
to compile, but soon get stuck. Rather than post specific questions, a
good pointer for examples would be appreciated (Norvig's book doesn't go
into enough detail and CLTL just seems to go in one eyeball and out the
other...).
Thanks,
Andrew
http://www.andrewcooke.free-online.co.uk
I have a similar problem. I haven't worked it out yet but
I think the immediate solution is vie the EQL specializers.
Please let me know if you work something out.
Tunc
Andrew Cooke wrote:
>
> Hi,
>
> I have a couple of questions about types and classes that would probably
> best be answered by looking at other code - please feel free to suggest
> specific examples (I have looked at some samples from the Ohio
> repository, but didn't see anything that answered the following):
>
> 1) How do I write a method which is selected based on the class of an
> argument *in a list*. For example, consider two methods that take
> lists, one of objects of class A and the other objects of class B, where
> A is a subset of B. Is this possible (it seems like the method needs to
> be selected on type rather than class...)? If not, what is the standard
> solution - to have different "list" classes for A and B?
>
> 2) This really is just a case of needing examples: I have some code
> that, sometime soon, I'd like to specify the types of various items to
> see if I can get an increase in speed. I can get a few simple examples
> to compile, but soon get stuck. Rather than post specific questions, a
> good pointer for examples would be appreciated (Norvig's book doesn't go
> into enough detail and CLTL just seems to go in one eyeball and out the
> other...).
>
> Thanks,
> Andrew
> http://www.andrewcooke.free-online.co.uk
In article <·················@andrewcooke.free-online.co.uk>,
Andrew Cooke <······@andrewcooke.free-online.co.uk> wrote:
>1) How do I write a method which is selected based on the class of an
>argument *in a list*. For example, consider two methods that take
>lists, one of objects of class A and the other objects of class B, where
>A is a subset of B. Is this possible (it seems like the method needs to
>be selected on type rather than class...)? If not, what is the standard
>solution - to have different "list" classes for A and B?
You can't do this directly in CLOS -- there's only one LIST class, and you
can't specialize based on the types of objects in the list.
What you can do is write a wrapper function that extracts the first element
of the list and then calls a generic function with that as an explicit
argument, i.e.
(defmethod foo-method ((item A) list-of-As)
...)
(defmethod foo-method ((item B) list-of-Bs)
...)
(defun foo-fun (list-of-things)
(foo-method (car list-of-things) (cdr list-of-things)))
>2) This really is just a case of needing examples: I have some code
>that, sometime soon, I'd like to specify the types of various items to
>see if I can get an increase in speed. I can get a few simple examples
>to compile, but soon get stuck. Rather than post specific questions, a
>good pointer for examples would be appreciated (Norvig's book doesn't go
>into enough detail and CLTL just seems to go in one eyeball and out the
>other...).
In general, the only significant speed boots you can expect are if you
declare variables that can only hold fixnum of specific float types, as the
implementation can avoid boxing and unboxing numbers. But as the other
poster said, don't waste lots of time on this unless you've determined that
this is really your bottleneck.
If you use CMUCL, it has a good type inferencer and can also generate lots
of warnings about places where it wasn't able to generate type-specific
code.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, 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.
OK, thanks to everyone who replied. With some email replies as well I think I have
enough to go on - I had a big confusion over types and classes which, although not
clear, I can now sort out. As I am intending to switch to CMUCL when I update my
Linux (when *is* the next Debian release coming out ?! :-) I'll leave this 'til
then (besides which, past a certain point, I'm wary of optimising on one compiler
when I'll be running mainly on another).
Cheers + Thanks again to all who replied,
Andrew
Barry Margolin wrote:
> [...]In general, the only significant speed boots you can expect are if you
> declare variables that can only hold fixnum of specific float types, as the
> implementation can avoid boxing and unboxing numbers. But as the other
> poster said, don't waste lots of time on this unless you've determined that
> this is really your bottleneck.
>
> If you use CMUCL, it has a good type inferencer and can also generate lots
> of warnings about places where it wasn't able to generate type-specific
> code.
* Barry Margolin wrote:
> You can't do this directly in CLOS -- there's only one LIST class, and you
> can't specialize based on the types of objects in the list.
> What you can do is write a wrapper function that extracts the first element
> of the list and then calls a generic function with that as an explicit
> argument, i.e.
This is a very clever trick, but it might give you the wrong answer, I
think. If I have two conceptual types, list-of-a and list-of-b, and b
is a subclass of a, then things which are of type list-of-a can have
bs in them too, so dispatching on a particular element might actually
invoke the list-of-b method rather than the list-of-a one.
--tim
I believe we only have to bite the bullet. In CL there is no way to
say
(deftype intlist () '(list integer))
or
(deftype intlistlist () '(list (list integer)))
I do not see any way out of this.
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
* Marco Antoniotti wrote:
> I believe we only have to bite the bullet. In CL there is no way to
> say
> (deftype intlist () '(list integer))
Actually, I think there is a way of saying this:
(deftype list-of-integer ()
'(or null (cons integer list-of-integer)))
-- at least if my reading of the hyperspec is correct (CONS x y) is a
type specifier for a cons whose car is a x and cdr is a y. Neither
Allegro nor CMUCL seem to allow CONS as a compound type specifier
though.
Even if this is wrong (or if this is a bug in those implementations?),
you can define the type like this:
(defun list-of-integer-p (x)
(typecase x
(null t)
(cons
(and (typep (car x) 'integer)
(list-of-integer-p (cdr x))))))
(deftype list-of-integer ()
'(satisfies list-of-integer-p))
This latter definition makes it immediately apparent why declaring a
type like this might not be a useful for a type system that might ever
have to do dynamic type dispatch -- it's really only a useful type if
the compiler can prove that some object is of this type and do any
dispatch at compile time.
--tim
Tim Bradshaw wrote:
> Actually, I think there is a way of saying this:
>
> (deftype list-of-integer ()
> '(or null (cons integer list-of-integer)))
>
> -- at least if my reading of the hyperspec is correct
I don't think this is allowed by the hyperspec. It says:
"Recursive expansion of the type specifier returned as the expansion must
terminate, including the expansion of type specifiers which are nested within
the expansion."
See also the RECURSIVE-DEFTYPE issue, which gives an example similar to
yours.
> (CONS x y) is a type specifier for a cons whose car is a x and cdr is a y.
> Neither Allegro nor CMUCL seem to allow CONS as a compound type specifier
> though.
Lispworks has no problems with (CONS x y) type specifiers.
--
Arthur Lemmens
Tim Bradshaw <···@tfeb.org> writes:
> * Marco Antoniotti wrote:
> > we only have to bite the bullet. In CL there is no way to say
> > (deftype intlist () '(list integer))
>
> Actually, I think there is a way of saying this:
>
> (deftype list-of-integer ()
> '(or null (cons integer list-of-integer)))
>
> -- at least if my reading of the hyperspec is correct (CONS x y) is a
> type specifier for a cons whose car is a x and cdr is a y. Neither
> Allegro nor CMUCL seem to allow CONS as a compound type specifier
Yes, that's the meaning of compound type CONS and LispWorks
understands it. Unfortunately, your LIST-OF-INTEGER has a
non-terminating expansion, and this is forbidden by the definition of
DEFTYPE (recursive types plus unlimited AND/OR lead to difficulties).
An extension of the LIST type with an element type, such as Antoniotti
proposes, would be useful for compiler optimizations, though not for
CLOS dispatching. Undoubtedly, a clever metaclass could be written
manage a hierarchy of collection classes, but the instances could not
be lists.
--
Pekka P. Pirinen
Adaptive Memory Management Group, Harlequin Limited
Technology is powerful magic, so we all need to become powerful magicians.
- Christopher M. Stahnke <cstahnke_worldbank.org>
* Pekka P Pirinen wrote:
> Yes, that's the meaning of compound type CONS and LispWorks
> understands it. Unfortunately, your LIST-OF-INTEGER has a
> non-terminating expansion, and this is forbidden by the definition of
> DEFTYPE (recursive types plus unlimited AND/OR lead to
> difficulties).
I realised this momentarily after posting (should have read more
carefully).
Even if it could work (which the SATISFIES one does I guess) there are
obvious termination problems in actually *doing* the type check -- you
need an occurs check I guess.
--tim
> * Marco Antoniotti wrote:
> > I believe we only have to bite the bullet. In CL there is no way to
> > say
>
> > (deftype intlist () '(list integer))
[examples snipped]
Tim Bradshaw <···@tfeb.org> concludes:
> This latter definition makes it immediately apparent why declaring a
> type like this might not be a useful for a type system that might ever
> have to do dynamic type dispatch -- it's really only a useful type if
> the compiler can prove that some object is of this type and do any
> dispatch at compile time.
There are a couple of other reasons one might want to say something
about the contents of lists. One is to use for defensive programming
by calling CHECK-TYPE on arguments passed to a function.
And one might hope that certain operations could be made more efficient
if there were type information like that available:
Assuming X and Y were of type (LIST FIXNUM), one could hope that fixnum
addition could be used for (+ (first X) (first y)), or even for (+ I J)
in the following (allowing for overflow caveats, etc.).
(dolist (i x)
(dolist (j y)
... (+ i j) ))
Now, one can achieve the same result by declaring the types of the
variables or using (THE FIXNUM ...) forms, but having a single place to
make the declaration is convenient -- although in practice, probably
only CMUCL would actually do the type inference ;}
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
> Even if this is wrong (or if this is a bug in those implementations?),
> you can define the type like this:
>
> (defun list-of-integer-p (x)
> (typecase x
> (null t)
> (cons
> (and (typep (car x) 'integer)
> (list-of-integer-p (cdr x))))))
Or simply:
(defun list-of-integer-p (x)
(and (listp x) (every #'integerp x)))
> (deftype list-of-integer ()
> '(satisfies list-of-integer-p))
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
Tim Bradshaw <···@tfeb.org> writes:
> * Marco Antoniotti wrote:
> > I believe we only have to bite the bullet. In CL there is no way to
> > say
>
> > (deftype intlist () '(list integer))
>
> Actually, I think there is a way of saying this:
>
> (deftype list-of-integer ()
> '(or null (cons integer list-of-integer)))
>
> -- at least if my reading of the hyperspec is correct (CONS x y) is a
> type specifier for a cons whose car is a x and cdr is a y. Neither
> Allegro nor CMUCL seem to allow CONS as a compound type specifier
> though.
One for CMUCL bugs? I get an "unknown type specifier (CONS INTEGER
INTEGER)" when I try a simple (TYPEP '(1 . 2) '(cons integer integer))
>
> Even if this is wrong (or if this is a bug in those implementations?),
> you can define the type like this:
...
> (deftype list-of-integer ()
> '(satisfies list-of-integer-p))
>
> This latter definition makes it immediately apparent why declaring a
> type like this might not be a useful for a type system that might ever
> have to do dynamic type dispatch -- it's really only a useful type if
> the compiler can prove that some object is of this type and do any
> dispatch at compile time.
Yep. Of course you can do this, but, to the best of my knowledge, no
CL compiler takes advantage of SATISFIES specifiers as of today.
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
* Marco Antoniotti wrote:
> Tim Bradshaw <···@tfeb.org> writes:
> Yep. Of course you can do this, but, to the best of my knowledge, no
> CL compiler takes advantage of SATISFIES specifiers as of today.
The point was that in order to check the purely declarative DEFTYPE
you need to do exactly ther same amount of work (namely walk down the
list checking every element).
--tim
Andrew Cooke wrote:
> I have some code that, sometime soon, I'd like to specify the types of
> various items to see if I can get an increase in speed.
I'm not sure I am in a position to give you a sensible answer to this, since
I have very little experience in optimising CL. ('whereof one does not
thereof one should not speak' and all that). But I have some experience is
optimising in other languages. SO here goes.
First: what and why do you need to optimise? is this a 'lets optimise
because it's fun?' or because the completed system is genuinely too slow? (I
am assuming that you are optimising for speed. But I may be wrong. You could
want to optimise for other things: disk space, memory usage, network traffic
&c &c. So you should be clear about what you do want to optimise.
Particularly if these properties are mutually exclusive e.g. memory usage vs
speed).
Second: A very wise man once said: 'premature optimisation is the root of
all evil.' Make sure the system does the job you want it to first and then
optimise. To try and change an optimised system to do more or different
things is much harder that if you still have an un-optimised system.
Third: Remember the 80-20 rule. 20% of effort will result in 80% of the
speed up. 80% of the effort is then required to produce a 20% speed up. Do
you want to get every ounce of speed? or just to get it to go faster? and if
so how much faster? This should be decided when you start. Write it down
somewhere. Otherwise the black hole of mucking about forever will swallow up
the rest of your life. Taking up the time when you should be doing other
things like drinking yourself to insensibility.
Finally: Do you have an profiler? If you do, run the profiler and then spend
your time and effort on optimising the bits that need optimising. For
example: Some software was running slowly. I ran the optimiser and found
that the slowest bits were the database connections accross a network. A
marked improvement in speed was achieved by tuning the sql and moving the
box on which the GUI ran onto the same network hub as the database server.
If I had spent my time optimising the code in the GUI, I would have been
wasting my time.
I hope this helps.
Best Regards,
:) will
Hi,
I agree with everything you said (how do I say "I may be new to Lisp, but I earn
my living programing computers and have argued the same thing with my employers
many times" without sounding ungracious? ;-). The code in question will be in
the inner loop of a fairly large computation, and I'm already doing / plan to do
a bunch of improvements (tends to be an iterative process of getting something
working and then making the slowest bit more complicated but faster - like
caching results, delaying caclulations that may not bee needed, etc - so
breaking the code, then fixing it and iterating). But (and it's a big but) at
some point I have to at least *try* defining a few types to see if it makes a
difference (I hope to save memory on some fairly large arrays, as well as some
time) and I can't even see if it makes a difference if I can't do it....
So, thanks for the wise words (and yes, I probably was getting a bit carried
away with optimising everything so they made me take stock), but still - can
anyone point me to some code that has a plethora of type declarations that I can
learn from?
Thanks,
Andrew
PS Much of the code was written in a linear hierarchy of classes to keep things
conceptually simple. I suspect that collapsing all the methods into one class
(and then switching from class to structure and method to functions) might also
help - but I have no idea how much. I plan on writing some test code to see,
but if anyone has any ball-park figures on how expensive generic function calls
are, they would be nice too....
PPS If I can't find any code I'll wait 'til I'm doing it then post annoying
individual questions when I get stuck... :-)
William Deakin wrote:
> Andrew Cooke wrote:
>
> > I have some code that, sometime soon, I'd like to specify the types of
> > various items to see if I can get an increase in speed.
>
> I'm not sure I am in a position to give you a sensible answer to this, since
> I have very little experience in optimising CL. ('whereof one does not
> thereof one should not speak' and all that). But I have some experience is
> optimising in other languages. SO here goes.
[good advice snipped]
Andrew Cooke <······@andrewcooke.free-online.co.uk> writes:
> So, thanks for the wise words (and yes, I probably was getting a bit
> carried away with optimising everything so they made me take stock),
> but still - can anyone point me to some code that has a plethora of
> type declarations that I can learn from?
There are two trivial examples at
http://www.thoughtstuff.com/rme/lisp.html. See the DCT speed section,
and the CRC-32 section. The DCT code uses declarations to get the
floating-point operations to open code, and the CRC-32 code does
bit-bashing.
The examples work best in CMUCL and ACL, which both do a fair amount
of type inferencing.
-matt
From: Christopher R. Barry
Subject: Re: (newbie) types, classes, code examples
Date:
Message-ID: <87iu4nyr14.fsf@2xtreme.net>
Andrew Cooke <······@andrewcooke.free-online.co.uk> writes:
> help - but I have no idea how much. I plan on writing some test code
> to see, but if anyone has any ball-park figures on how expensive
> generic function calls are, they would be nice too....
This varies widely among implementations depending on what you are
trying to do. If you are using Allegro CL, there is documentation of
some of the CLOS optimizations it can perform provided you provide the
correct circumstances. Find this in the doc/ directory of the
distribution.
If you don't _have_ to use CLOS, then it may be better to avoid it if
efficiency is a _really_ big issue and you have basically already
solved the problem, you just need to program the solution. But, don't
be afraid of CLOS, or associate CLOS with inefficiency....
Christopher