a potential lisp convert, and interpreting the shootout
Henry Bigelow
i am writing to get an idea whether lisp would be useful. so far, i
think it would be ideal as a mode of expression, but i'm not sure
whether it has (or i would be able to write) memory efficient or
sufficiently fast code with it.
i have zero lisp experience. i started with perl, then c++, then
o'caml. a few days ago i read paul graham's summary of john mccarthy's
paper, and then started reading the original, and On Lisp. i'm
completely wowed, and would love to use it to write my programs.
i'm a bioinformatics student, writing a bayesian network software with
a very demanding memory requirement, and potentially long running time
for training. it predicts protein structure, and must have hundreds of
nodes for each protein, each with a matrix storing relationships
between amino acids and structural states. if this is done
efficiently, it certainly fits in a 2GB machine.
but i'm not sure why certain lisp programs in the shootout are so
large. how do i interpret the results of the shootout? for example,
lisp fannkuch is 26 times slower than the c version, and lisp chameneos
is 120x larger.
i'm surprised to see such large discrepancy actually. is it possible
to improve on these numbers? so far, the idea of macros and
code-as-data and mini-compilers is completely fantastic and foreign to
me, and seems to hold much promise for writing code with an eye on
memory and speed efficiency. but the shootout isn't encouraging in
certain cases.
TIA
henry
chameneos -1.2 -120 1.2
fannkuch -26 -2.5 -1.2
k-nucleotide -8.1 -3.1 1.4
n-body -1.4 -92 -1.2
pidigits -5.7 -51 -1.1
regex-dna 139 -7.7 2.0 300,000 (yay)
Paolo Amoroso
> i'm a bioinformatics student, writing a bayesian network software with
See:
BioBike
http://nostoc.stanford.edu/Docs/
KnowOS: A Knowledge Operating System
http://nostoc.stanford.edu/Docs/KnowOS.html
Bio-Informatics
http://www.cl-user.net/asp/tags/bio-informatics
Paolo
--
Why Lisp? http://wiki.alu.org/RtL%20Highlight%20Film
The Common Lisp Directory: http://www.cl-user.net
pbu...@gmail.com
Henry Bigelow wrote:
> i have zero lisp experience. i started with perl, then c++, then
> o'caml. a few days ago i read paul graham's summary of john mccarthy's
> paper, and then started reading the original, and On Lisp. i'm
> completely wowed, and would love to use it to write my programs.
Welcome here!
> but i'm not sure why certain lisp programs in the shootout are so
> large. how do i interpret the results of the shootout? for example,
> lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> is 120x larger.
It would be useful to post a link to the actual data page -- at least
to see what they count as "program size". Unless one does lisp -> C ->
executable conversion (which is totally possible with some less popular
lisp dialects), I'd assume that resulting lisp executable is a complete
image, which would include all of the library AND compiler.
> is it possible to improve on these numbers?
Minimize consing, use lisp arrays, make sure to declare your variables
(to let compiler know what it is allowed to optimize) -- at the end
memory requirements should not be much worse with lisp than for C or
Fortran (except for the above-mentioned constant additon of having
compiler and library "always there", which is a bonus ;-) ).
As to speed -- this is the required reading:
http://www.flownet.com/gat/papers/lisp-java.pdf ;-)
Of course one would want to use compiled version of lisp, check out
SBCL...
Just my $0.02,
Paul B.
Javier
Henry Bigelow ha escrito:
> hi,
>
> i am writing to get an idea whether lisp would be useful. so far, i
> think it would be ideal as a mode of expression, but i'm not sure
> whether it has (or i would be able to write) memory efficient or
> sufficiently fast code with it.
It depends on the implementation you choose, and the plattform you are
going to develop for, but it usually is very fast.
> i have zero lisp experience. i started with perl, then c++, then
> o'caml. a few days ago i read paul graham's summary of john mccarthy's
> paper, and then started reading the original, and On Lisp. i'm
> completely wowed, and would love to use it to write my programs.
Why not first start learning with Practical Common Lisp? On Lisp is
more advanced and focused on macros.
http://www.gigamonkeys.com/book/
> i'm a bioinformatics student, writing a bayesian network software with
> a very demanding memory requirement, and potentially long running time
> for training. it predicts protein structure, and must have hundreds of
> nodes for each protein, each with a matrix storing relationships
> between amino acids and structural states. if this is done
> efficiently, it certainly fits in a 2GB machine.
Lisp helps you when need to develop complex algorithm and big
appliations.
> but i'm not sure why certain lisp programs in the shootout are so
> large. how do i interpret the results of the shootout? for example,
> lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> is 120x larger.
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=sbcl&id=0
120x larger?
It ocupes 1.2 more when gziped, but acctually the Lisp version is
shorter in number of lines. Take in count that Lisp uses long named
statments, for example:
(defun call-with-permutations (fun initial-permutation)
(call-with-permutations-rec fun initial-permutation
(array-dimension initial-permutation 0)))
But I believe that the Lisp version is more manteinable and clear to
read (once you are used to Lisp, of course).
For what I can observe, the Lisp algorith is very different from the C
one. If you make it the same way, I'm pretty sure that the SBCL version
would be very similar in speed.
> i'm surprised to see such large discrepancy actually.
I insist: this is due to the difference in selecting the algorith used.
Using similar code, SBCL should not be more than 20% slower than C.
Javier
Henry Bigelow ha escrito:
> hi,
>
> i am writing to get an idea whether lisp would be useful. so far, i
> think it would be ideal as a mode of expression, but i'm not sure
> whether it has (or i would be able to write) memory efficient or
> sufficiently fast code with it.
It depends on the implementation you choose, and the plattform you are
going to develop for, but it usually is very fast.
> i have zero lisp experience. i started with perl, then c++, then
> o'caml. a few days ago i read paul graham's summary of john mccarthy's
> paper, and then started reading the original, and On Lisp. i'm
> completely wowed, and would love to use it to write my programs.
Why not first start learning with Practical Common Lisp? On Lisp is
more advanced and focused on macros.
http://www.gigamonkeys.com/book/
> i'm a bioinformatics student, writing a bayesian network software with
> a very demanding memory requirement, and potentially long running time
> for training. it predicts protein structure, and must have hundreds of
> nodes for each protein, each with a matrix storing relationships
> between amino acids and structural states. if this is done
> efficiently, it certainly fits in a 2GB machine.
Lisp helps you when need to develop complex algorithm and big
appliations.
> but i'm not sure why certain lisp programs in the shootout are so
> large. how do i interpret the results of the shootout? for example,
> lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> is 120x larger.
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=sbcl&id=0
120x larger?
It ocupes 1.2 more when gziped, but acctually the Lisp version is
shorter in number of lines. Take in count that Lisp uses long named
statments, for example:
(defun call-with-permutations (fun initial-permutation)
(call-with-permutations-rec fun initial-permutation
(array-dimension initial-permutation 0)))
But I believe that the Lisp version is more manteinable and clear to
read (once you are used to Lisp, of course).
For what I can observe, the Lisp algorith is very different from the C
one. If you make it the same way, I'm pretty sure that the SBCL version
would be very similar in speed.
> i'm surprised to see such large discrepancy actually.
I insist: this is due to the difference in selecting the algorith used.
Henry Bigelow
> > large. how do i interpret the results of the shootout? for example,
> > lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> > is 120x larger.
>
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=sbcl&id=0
>
> 120x larger?
sorry for the confusion. by "larger" i meant memory use. here are the
stats for Chameneos:
SBCL: 62,656 MB
GCC C: 524 MB
see:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=chameneos&lang=sbcl
http://shootout.alioth.debian.org/gp4/benchmark.php?test=chameneos&lang=gcc
Henry Bigelow
pbu...@gmail.com wrote:
> Welcome here!
thank you.
>
> > but i'm not sure why certain lisp programs in the shootout are so
> > large. how do i interpret the results of the shootout? for example,
> > lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> > is 120x larger.
>
> It would be useful to post a link to the actual data page -- at least
> to see what they count as "program size". Unless one does lisp -> C ->
> executable conversion (which is totally possible with some less popular
> lisp dialects), I'd assume that resulting lisp executable is a complete
> image, which would include all of the library AND compiler.
>
sorry for the confusion, by "larger" i meant memory use.
here's the link:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
> > is it possible to improve on these numbers?
>
> Minimize consing, use lisp arrays, make sure to declare your variables
> (to let compiler know what it is allowed to optimize) -- at the end
> memory requirements should not be much worse with lisp than for C or
> Fortran (except for the above-mentioned constant additon of having
> compiler and library "always there", which is a bonus ;-) ).
>
> As to speed -- this is the required reading:
> http://www.flownet.com/gat/papers/lisp-java.pdf ;-)
thanks for the link. looks very encouraging.
a more important question is:
is this shootout really definitive? are all the programs up there
written such that one would consider them both elegant and efficient,
or are some very poorly written?
is it a popular shootout, or are there other benchmarks that people
like better?
thanks,
henry
Robert Dodier
> i'm a bioinformatics student, writing a bayesian network software with
> a very demanding memory requirement, and potentially long running time
> for training. it predicts protein structure, and must have hundreds of
> nodes for each protein, each with a matrix storing relationships
> between amino acids and structural states. if this is done
> efficiently, it certainly fits in a 2GB machine.
My advice to you is to use R (http://www.r-project.org).
It is a pleasant programming language, and there is a lot of
contributed code, which includes Bayesian stuff and bioinformatics
(not sure if it includes the intersection of the two).
In any event R has a large, active user community and chances
are good you'll find people with similar interests.
I say this after having written a lot of statistical code (including
Bayesian inference) in a variety of languages.
It's not clear to me that Lisp's particular strength (code = data)
is going to be much of a win for you. If you were writing a general
purpose Bayesian inference package, probably so. But I'm guessing
that what you are going to do is derive some equations by hand,
code them, and then run them on enormous data sets. I don't
see much scope for code = data there. YMMV.
Lisp isn't a bad choice in this context; it is probably better than C
or Perl.
FWIW
Robert Dodier
pbu...@gmail.com
http://shootout.alioth.debian.org/gp4/miscfile.php?file=benchmarking&title=Flawed%20Benchmarks
and the first link off it is quite educational... ;-)
> a more important question is:
>
> is this shootout really definitive? are all the programs up there
> written such that one would consider them both elegant and efficient,
> or are some very poorly written?
> is it a popular shootout, or are there other benchmarks that people
> like better?
This is the first time I've heard of this particular competition (and
set of benchmarks) -- it looks rather cool! I doubt it has the same
clout as SPEC though... :-)
Hey, while you are at learning lisp, why not debug that 120x memory
program to see why this happens? profile and time are your friends...
;-)
CL-USER>CL-USER> (time (main 5000000))
10000000
Evaluation took:
34.466 seconds of real time
12.708794 seconds of user run time
21.369335 seconds of system run time
[Run times include 0.044 seconds GC run time.]
0 page faults and
79,975,616 bytes consed.
NIL
CL-USER>
-- yes, almost 80 MB consed -- but why the heck threading overherad is
so high? (most of runtime is in system time, uh-huh...)
Paul B.
JShr...@gmail.com
recommendation of R if all you need to do is crunch a bunch of numbers
that represent a bayes net. R has a quasi-reasonable quasi-Lisp
programming language and numerous packages to support mathematical and
statistical computing (incl. extensive bayesian machinery). BioBike is
designed for knowledge-based, not numbers-based biocomputing.
(Although, of course, it can do both, but why try to shoe-horn every
kind of computation into the same programming language even if you
could, esp. when it's so easy to make multiple languages live happily
together?) To do most "typical" biocomputing -- sequence processing,
stats, bayes nets, and those sorts of off-the-shelf numerical things --
we call down to non-Lisp (R-based or C-based) code and just interface
them up to BioBike's Lisp so that you can use Lisp to do the more
difficult knowledge processing that Lisp is good at.
If you are interested in using BioBike to do knowledge processing on
top of your bayes net machinery I'm sure that the BioBike support team
will be happy to help you out.
Javier
Henry Bigelow ha escrito:
> > 120x larger?
>
>
> sorry for the confusion. by "larger" i meant memory use. here are the
> stats for Chameneos:
>
> SBCL: 62,656 MB
> GCC C: 524 MB
Let see the differences (I hope some corrections from others if I'm
wrong):
1) SBCL loads the entire CL and extra libraries, including
documentation, the debugger and the compiler. Just starting SBCL eats
nearly 30Mb on my system (OSX), on Linux it may be even larger
(depending on the memoy model used, which I think OSX is better for
this). A similar thing happens with the Java virtual machine.
2) The memory used may be actually a "fake" because SBCL takes more
memory that it really need. For example, on my system it reserves 3Gb
of virtual memory just at startup. Of course, it doesn't mean that it
is ever going to use it all.
3) SBCL is not the only implementation. Try ECL, CLISP, and the
evaluation versions of Allegro and LispWorks. They all are probably
going to consume much less memory.
Henry Bigelow
> My advice to you is to use R (http://www.r-project.org).
> It is a pleasant programming language, and there is a lot of
> contributed code, which includes Bayesian stuff and bioinformatics
> (not sure if it includes the intersection of the two).
> In any event R has a large, active user community and chances
> are good you'll find people with similar interests.
> I say this after having written a lot of statistical code (including
> Bayesian inference) in a variety of languages.
>
thanks robert. i'll check it out. i've heard R mentioned many times,
and i'd tried 'bayes net toolbox' written in matlab, but it didn't look
fast enough for my purposes. but mostly i just wanted to write one
myself, if just to get a better understanding of the algorithms.
> It's not clear to me that Lisp's particular strength (code = data)
> is going to be much of a win for you. If you were writing a general
> purpose Bayesian inference package, probably so. But I'm guessing
> that what you are going to do is derive some equations by hand,
> code them, and then run them on enormous data sets. I don't
> see much scope for code = data there. YMMV.
>
this is encouraging, but i would still like to see the huge memory and
speed differences in some of those benchmarks fixed, if possible.
thanks again,
henry
Nicolas Neuss
> but i'm not sure why certain lisp programs in the shootout are so
> large. how do i interpret the results of the shootout? for example,
> lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> is 120x larger.
>
Lisp functions should be started and used in a Lisp environment and not
inside a C environement (Unix). Then compiled functions are usually as
small or smaller as their C counterpart.
Nicolas
Henry Bigelow
thanks paul! by the way, i read the paper analyzing a lisp fannkuch
benchmark for efficiency, and it mentioned the use of 'aref' and
several other things. i looked at the actual benchmark, and was hoping
to find some telltale sign that it didn't use any of these ideas, but i
didn't. i have no idea whether the shootout fannkuch lisp benchmark is
written the way this paper describes.
can i interest you or anyone else to optimize one or more of these
benchmarks, so they aren't such negative publicity for lisp?
BTW for those reading, the shootout is:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
and the offending benchmarks are called fannkuch and chameneos.
henry
>
> Paul B.
Henry Bigelow
Nicolas Neuss wrote:
> "Henry Bigelow" <hrbi...@gmail.com> writes:
>
> > but i'm not sure why certain lisp programs in the shootout are so
> > large. how do i interpret the results of the shootout? for example,
> > lisp fannkuch is 26 times slower than the c version, and lisp chameneos
> > is 120x larger.
> >
>
> Lisp functions should be started and used in a Lisp environment and not
> inside a C environement (Unix).
what do you mean exactly? how can you avoid running your program in an
operating system?
> Then compiled functions are usually as
> small or smaller as their C counterpart.
when i said 120x larger, i should have said 'uses 120x as much memory
during runtime'. the actual binary is probably not much larger than
the c binary for these benchmarks, and the size of source code is all
within a factor of 2 or 3.
>
> Nicolas
Henry Bigelow
i took a look at SPEC--it seems definitive, indeed, but for comparing
computer systems, not languages. is that right? would you be able to
point me in a direction to compare languages? i have a hunch that
there is something very wrong with the lisp benchmark which is about
100 times more memory/ or slower than a c program, but it'd be very
difficult for me to rewrite it more efficiently.
it's possible that for various reasons, people don't care enough about
the shootout
http://shootout.alioth.debian.org/
to fix the benchmarks. or, it's possible that the lisp ones are indeed
written to be as memory/speed efficient as possible.
what do you think is going on here?
thanks,
henry
> This is the first time I've heard of this particular competition (and
> set of benchmarks) -- it looks rather cool! I doubt it has the same
> clout as SPEC though... :-)
>
> Hey, while you are at learning lisp, why not debug that 120x memory
> program to see why this happens? profile and time are your friends...
> ;-)
you're overestimating my skill here!
Javier
Henry Bigelow ha escrito:
> hi paul,
> i took a look at SPEC--it seems definitive, indeed, but for comparing
> computer systems, not languages. is that right? would you be able to
> point me in a direction to compare languages? i have a hunch that
> there is something very wrong with the lisp benchmark which is about
> 100 times more memory/ or slower than a c program, but it'd be very
> difficult for me to rewrite it more efficiently.
>
> it's possible that for various reasons, people don't care enough about
> the shootout
>
> http://shootout.alioth.debian.org/
>
> to fix the benchmarks. or, it's possible that the lisp ones are indeed
> written to be as memory/speed efficient as possible.
>
> what do you think is going on here?
We have already said that:
1) Lisp loads the entire compiler/debugger/documentation among with the
program. As you can imagine, it is impossible to compite to C in memory
ussage in this situation (imagine that you would have to load GCC with
your C program, it would be much bigger, don't think so?). But please,
take also in count that, while in a program written in C it does not
count the memory shared with the C library (it is linked dinamically),
in Lisp you have the Lisp library loaded with you, so the C library is
already consuming memory from your system, but the program which you
use to see that memory doesn't take that in count.
2) It is not 100x slower. Please take a look at:
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
That demonstrates that, except for some bechmarks in which algorithms
differ a lot, SBCL is almost as fast as C.
3) SBCL is not the only implementation. There are other implementations
which even run faster, and which consumes less memory.
Henry Bigelow
Javier wrote:
>
> We have already said that:
>
> 1) Lisp loads the entire compiler/debugger/documentation among with the
> program.
i didn't know that. but, if so, why aren't all the other benchmarks
100x more memory? k-nucleotide is only 3.1x more memory.
As you can imagine, it is impossible to compite to C in memory
> ussage in this situation (imagine that you would have to load GCC with
> your C program, it would be much bigger, don't think so?). But please,
> take also in count that, while in a program written in C it does not
> count the memory shared with the C library (it is linked dinamically),
> in Lisp you have the Lisp library loaded with you, so the C library is
> already consuming memory from your system, but the program which you
> use to see that memory doesn't take that in count.
> 2) It is not 100x slower. Please take a look at:
> http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
> That demonstrates that, except for some bechmarks in which algorithms
> differ a lot, SBCL is almost as fast as C.
agreed. fannkuch is 27x slower, and chameneos requires 120x more
memory. i'm not contesting anything besides 'fannkuch' for speed. i'm
not really concerned about 'startup' because it's amortized.
> 3) SBCL is not the only implementation. There are other implementations
> which even run faster, and which consumes less memory.
yes, but the use of SBCL here is obviously not why the fannkuch
benchmark is 26 times slower, instead of 3 or 5 times slower.
thanks in advance,
henry
Javier
Henry Bigelow ha escrito:
> Javier wrote:
>
> >
> > We have already said that:
> >
> > 1) Lisp loads the entire compiler/debugger/documentation among with the
> > program.
>
> i didn't know that. but, if so, why aren't all the other benchmarks
> 100x more memory? k-nucleotide is only 3.1x more memory.
Because that algorithm uses a lot of memory, even in C.
If you don't believe me, download and install SBCL. Start it. Only
starting it, requires about 6Mb.
Now define a function:
(defun jj () (format t "hello"))
Now it requires about 11Mb, which means that the compiler has been
loaded and compiled your function in real time. If you start to do
things, like using the debugger, the documentation, extra libraries,
etc, your application can grow in memory very fast.
A similar thing happens with Java.
In C, you are not compiling code in real time, and your program uses
the libraries on your system, so this makes the ilussion that your C
program uses very little memory. But it probably no. What is happening
is that your C program uses libraries that are already loaded in memory
(for example stdlib).
You can see that this is always happening even in C. Take for example
Mozilla, Open Office, the X server, GCC... all of them are using a lot
of memory because they need libraries which are not already dinamically
loaded.
> > 2) It is not 100x slower. Please take a look at:
> > http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
> > That demonstrates that, except for some bechmarks in which algorithms
> > differ a lot, SBCL is almost as fast as C.
>
> agreed. fannkuch is 27x slower, and chameneos requires 120x more
> memory. i'm not contesting anything besides 'fannkuch' for speed. i'm
> not really concerned about 'startup' because it's amortized.
A good measure of how well is SBCL doing is disassembling:
(disassemble 'jj)
; 1160AD7A: BA27000008 MOV EDX, 134217767 ;
no-arg-parsing entry point
; 7F: 8B3D14AD6011 MOV EDI, [#x1160AD14] ; "hello"
; 85: 8B0518AD6011 MOV EAX, [#x1160AD18] ;
#<FDEFINITION object for FORMAT>
; 8B: B908000000 MOV ECX, 8
; 90: FF75F8 PUSH DWORD PTR [EBP-8]
; 93: FF6005 JMP DWORD PTR [EAX+5]
; 96: 90 NOP
; 97: 90 NOP
; 98: 0F0B0A BREAK 10 ; error
trap
; 9B: 02 BYTE #X02
; 9C: 18 BYTE #X18 ;
INVALID-ARG-COUNT-ERROR
; 9D: 4D BYTE #X4D ; ECX
; 9E: 0F0B0A BREAK 10 ; error
trap
; A1: 02 BYTE #X02
; A2: 18 BYTE #X18 ;
INVALID-ARG-COUNT-ERROR
; A3: 4D BYTE #X4D ; ECX
If you understand some asemssembler you can see that SBCL is actually
very clever compiling things. :-)
(For example, it is using a jump in line 93 instead of function call to
avoid some overhead. Not all C compilers are able to do so.)
Juho Snellman
> hi paul,
> i took a look at SPEC--it seems definitive, indeed, but for comparing
> computer systems, not languages. is that right? would you be able to
> point me in a direction to compare languages? i have a hunch that
> there is something very wrong with the lisp benchmark which is about
> 100 times more memory/ or slower than a c program, but it'd be very
> difficult for me to rewrite it more efficiently.
>
> it's possible that for various reasons, people don't care enough about
> the shootout
As far as I can tell, the lifecycle of a shootout benchmark goes like
this:
1. A new benchmark is added, nobody cares
2. A newbie with 2 hours of Lisp experience notices that there's
no implementation for the benchmark. He thinks that a crappy
implementation is better than no implementation, and proceeds
to write something embarrasingly slow and hideously ugly.
3. People who mistakenly think that the Shootout has any validity
bitch and moan about Lisp being slow on that benchmark.
4. Someone who knows how to optimize Lisp code gets tired of the
moaning, and either rewrites the whole program (if it was
sufficiently hideous) or makes a few obvious but critical
improvements (if the program was salvageable). A huge speedup
results, the people from step 3 start whining about something else.
5. The requirements for the benchmark are modified, and the optimized
Lisp implementation gets deleted. There's no sign of it ever
having existed.
6. Return to step 2
The fannkuch benchmark is currently at step 3, having been at step 5
at least once. The old fannkuch program was about 10 times faster than
what is currently up on the shootout site.
--
Juho Snellman
Henry Bigelow
juho, thanks for your response. i took a look at the benchmarks, and
saw that you'd modified several of them. is this your comment, by the
way, from the spectral-norm benchmark? :
Note that sbcl is at least 10 times faster than either clisp or gcl
;; on this program, running with an argument of 500. It would be nice
;; to know why the others are so slow.
if so, did you ever figure out the cause of the discrepancy? i don't
know whether it's true of c or c++ that different compilers can give
drastically different code speeds.
it looks like you have a lot of experience. so, benchmark politics
aside, do you find lisp to be fast enough to do heavy-duty computing,
(in my case, a bayesian network with hundreds of nodes and lots of
floating point addition, but also written in a very extensible,
abstract style)
thanks,
henry
p.s. what would you say to changing the shootout such that multiple
programs can be submitted, and the results shown based on whatever
selection criteria wanted? who moderates it?
>
> --
> Juho Snellman
Wade Humeniuk
I do not have the patience to code it like C, so....
(defvar *fannkuch-prints* nil)
(defvar *fannkuch-max-flips* 0)
(declaim (inline flip make-fannkuch init-fannkuch print-fannkuch
copy-fannkuch permute-fannkuch count-flips))
(defun make-fannkuch (n)
(make-array n :element-type '(unsigned-byte 8)))
(defun init-fannkuch (fannkuch end)
(loop for n from 1
for i from 0 below end
do (setf (aref fannkuch i) n))
fannkuch)
(defun copy-fannkuch (from to start end)
(declare (type (simple-array (unsigned-byte 8) (*)) from to)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(loop for i from start below end
do (setf (aref to i) (aref from i))))
(defun permute-fannkuch (fannkuch n)
(declare (type (simple-array (unsigned-byte 8) (*)) fannkuch)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(let ((first (aref fannkuch 0)))
(loop for i from 0 below (1- n)
do (setf (aref fannkuch i) (aref fannkuch (1+ i))))
(setf (aref fannkuch (1- n)) first)
fannkuch))
(defun print-fannkuch (permutation)
(declare (type (simple-array (unsigned-byte 8) (*)) permutation)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(when (< *fannkuch-prints* 30)
(loop for i across permutation do
(princ i))
(terpri)
(incf *fannkuch-prints*)))
(defun flip (permutation)
(declare (type (simple-array (unsigned-byte 8) (*)) permutation)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(let ((n (aref permutation 0)))
(when (> n 1)
(loop for start from 0
for end downfrom (1- n)
while (< start end) do
(rotatef (aref permutation start)
(aref permutation end))))))
(defun count-flips (permutation)
(declare (type (simple-array (unsigned-byte 8) (*)) permutation)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(let ((flips 0))
(loop until (= (aref permutation 0) 1)
do (flip permutation)
(incf flips))
(setf *fannkuch-max-flips* (max flips *fannkuch-max-flips*))
flips))
(defun fanndance (fannkuch len &aux (first (first fannkuch)) (next (second fannkuch)))
(declare (type (simple-array (unsigned-byte 8) (*)) first next)
(type fixnum len)
(optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0)))
(copy-fannkuch first next 0 (length first))
(if (= len 1)
(progn (count-flips next) (print-fannkuch first))
(progn
(dotimes (i (1- len))
(fanndance (cdr fannkuch) (1- len))
(permute-fannkuch next len))
(fanndance (cdr fannkuch) (1- len)))))
(defun fannkuch (n)
(let ((*fannkuch-prints* 0) (*fannkuch-max-flips* 0)
(fannkuch (loop repeat (1+ n) collect (make-fannkuch n))))
(init-fannkuch (car fannkuch) n)
(format t "~A"
(with-output-to-string (*standard-output*)
(fanndance fannkuch n)))
(format t "Pfannkuchen(~D) = ~D" n *fannkuch-max-flips*)))
#+ignore(defun main ()
(fannkuch (parse-integer (second *posix-argv*))))
CL-USER 49 > (time (fannkuch 10))
Timing the evaluation of (FANNKUCH 10)
12345678910
21345678910
23145678910
32145678910
31245678910
13245678910
23415678910
32415678910
34215678910
43215678910
42315678910
24315678910
34125678910
43125678910
41325678910
14325678910
13425678910
31425678910
41235678910
14235678910
12435678910
21435678910
24135678910
42135678910
23451678910
32451678910
34251678910
43251678910
42351678910
24351678910
Pfannkuchen(10) = 38
user time = 2.874
system time = 0.000
Elapsed time = 0:00:03
Allocation = 3792 bytes standard / 4554 bytes conses
0 Page faults
Calls to %EVAL 34
NIL
CL-USER 50 >
Juho Snellman
> juho, thanks for your response. i took a look at the benchmarks, and
> saw that you'd modified several of them. is this your comment, by the
> way, from the spectral-norm benchmark? :
>
> Note that sbcl is at least 10 times faster than either clisp or gcl
> ;; on this program, running with an argument of 500. It would be nice
> ;; to know why the others are so slow.
>
> if so, did you ever figure out the cause of the discrepancy?
No, that's not my comment. But different implementations are naturally
going to have different performance characteristics. As an obvious
example, clisp is a bytecode interpreter. Why would someone expect it
to perform as well as a native code compiler on computationally heavy
code?
Likewise the compiler technology that SBCL uses is completely
different from that of GCL. It'd be more surprising if they actually
did perform equally well on some program.
> i don't
> know whether it's true of c or c++ that different compilers can give
> drastically different code speeds.
It's true, there's just less room for a clever compiler to make a
difference over a mediocre one than in Lisp.
For example a few years ago Sun released a new version of their C
compiler which resulted in a 10x speedup on one of the SpecFP 2000
programs (179.art). It did that by statically detecting a memory
access pattern that was unfriendly to caches, and rearranging some
loops in the code to make the access pattern more efficient while
preserving the same semantics.
> it looks like you have a lot of experience. so, benchmark politics
> aside, do you find lisp to be fast enough to do heavy-duty computing,
> (in my case, a bayesian network with hundreds of nodes and lots of
> floating point addition, but also written in a very extensible,
> abstract style)
Many people seem to find CMUCL and SBCL fast enough for real-world
numerical computing.
> p.s. what would you say to changing the shootout such that multiple
> programs can be submitted, and the results shown based on whatever
> selection criteria wanted?
Sounds like a horrible idea. You want *more* crappy programs for
people to whine about? :-)
--
Juho Snellman
Jon Harrop
> 2) It is not 100x slower. Please take a look at:
>
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=sbcl&lang2=gcc
> That demonstrates that, except for some bechmarks in which algorithms
> differ a lot, SBCL is almost as fast as C.
According to the page you cite SBCL is certainly not "almost as fast as C".
Just look at the graph.
Moreover, as a HLL, Lisp should be relatively better than C when algorithms
are allowed to differ (many algorithms are prohibitively complicated to
write in C).
--
Dr Jon D Harrop, Flying Frog Consultancy
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists
Jon Harrop
> 1. A new benchmark is added, nobody cares
> 2. A newbie with 2 hours of Lisp experience notices that there's
> no implementation for the benchmark. He thinks that a crappy
> implementation is better than no implementation, and proceeds
> to write something embarrasingly slow and hideously ugly.
> 3. People who mistakenly think that the Shootout has any validity
> bitch and moan about Lisp being slow on that benchmark.
> 4. Someone who knows how to optimize Lisp code gets tired of the
> moaning, and either rewrites the whole program (if it was
> sufficiently hideous) or makes a few obvious but critical
> improvements (if the program was salvageable). A huge speedup
> results, the people from step 3 start whining about something else.
> 5. The requirements for the benchmark are modified, and the optimized
> Lisp implementation gets deleted. There's no sign of it ever
> having existed.
> 6. Return to step 2
It is interesting to compare the Lisp lifecycle with the OCaml lifecycle:
1. A new benchmark is added to the shootout.
2. An elite OCaml programmer knocks up a tiny, lightning-fast solution and
submits it to the shootout.
3. The shootout maintainers either ignore the submission or deem that its
Zen feels too dissimilar to the C program.
4. The shootout maintainers claim that the submission never existed, despite
the fact that it is still on their site.
5. Despite never having existed, the requirements for the benchmark change.
6. Repeat from step 1.
Don't even get me started on Wikipedia. ;-)
Henry Bigelow
Wade Humeniuk wrote:
> Speaking of which. By modifying the original somewhat (I do not have SBCL)
> I do not have the patience to code it like C, so....
>
wow, thanks wade!
i'm going to test this out and compare it to the original too. so far
i've just downloaded slime and sbcl and am stumbling my way around it
all.
what sort of things do you use lisp for, by the way? and do you use
other languages too?
cheers,
henry
Henry Bigelow
Juho Snellman wrote:
> Henry Bigelow <hrbi...@gmail.com> wrote:
> > juho, thanks for your response. i took a look at the benchmarks, and
> > saw that you'd modified several of them. is this your comment, by the
> > way, from the spectral-norm benchmark? :
> >
> > Note that sbcl is at least 10 times faster than either clisp or gcl
> > ;; on this program, running with an argument of 500. It would be nice
> > ;; to know why the others are so slow.
> >
> > if so, did you ever figure out the cause of the discrepancy?
>
> No, that's not my comment. But different implementations are naturally
> going to have different performance characteristics.
> As an obvious
> example, clisp is a bytecode interpreter. Why would someone expect it
> to perform as well as a native code compiler on computationally heavy
> code?
right. i actually assumed we're talking all native, when comparing
speeds. i didn't know that clisp doesn't generate native code! so
then i'm not surprised. but, did they mean sbcl native is 10x faster
than gcl native, or than gcl bytecode?
>
> Likewise the compiler technology that SBCL uses is completely
> different from that of GCL. It'd be more surprising if they actually
> did perform equally well on some program.
>
> > i don't
> > know whether it's true of c or c++ that different compilers can give
> > drastically different code speeds.
>
> It's true, there's just less room for a clever compiler to make a
> difference over a mediocre one than in Lisp.
that's interesting. it makes intuitive sense that this is the case,
but i'd never thought about it. so what's your favorite compiler?
more broadly, do you think theoretically, either gcl or sbcl or some
other compiler has approached the maximum speed possible, or is there a
lot more room for growth?
>
> For example a few years ago Sun released a new version of their C
> compiler which resulted in a 10x speedup on one of the SpecFP 2000
> programs (179.art). It did that by statically detecting a memory
> access pattern that was unfriendly to caches, and rearranging some
> loops in the code to make the access pattern more efficient while
> preserving the same semantics.
wow! has anything like that happened with lisp compilers recently? or
do you think anything like that is likely to happen?
>
> > it looks like you have a lot of experience. so, benchmark politics
> > aside, do you find lisp to be fast enough to do heavy-duty computing,
> > (in my case, a bayesian network with hundreds of nodes and lots of
> > floating point addition, but also written in a very extensible,
> > abstract style)
>
> Many people seem to find CMUCL and SBCL fast enough for real-world
> numerical computing.
>
> > p.s. what would you say to changing the shootout such that multiple
> > programs can be submitted, and the results shown based on whatever
> > selection criteria wanted?
>
> Sounds like a horrible idea. You want *more* crappy programs for
> people to whine about? :-)
yes! :)
>
> --
> Juho Snellman
Henry Bigelow
hi mr. harrop! i was surprised to see your post over here on c.l.l!
did you start on lisp before o'caml? so, is that shootout the best one
available, despite the grim lifecycle descriptions? from your and
juho's descriptions, the owners sound a bit deceitful!
henry
ig...@yahoo.com
That seems to be a more-or-less reasonable summary to me - although I
don't understand what you think the benefit of displaying optimized
Lisp implementations that don't give the expected result would be (#5).
> The fannkuch benchmark is currently at step 3, having been at step 5
> at least once. The old fannkuch program was about 10 times faster than
> what is currently up on the shootout site.
The expected result for the fannkuch benchmark was changed slightly
back in 2005, to print out the first 30 of the permutations.
>
> --
> Juho Snellman
Wade Humeniuk
> Wade Humeniuk wrote:
>> Speaking of which. By modifying the original somewhat (I do not have SBCL)
>> I do not have the patience to code it like C, so....
>>
>
> wow, thanks wade!
You're welcome. The fastest version I have tried (so far) of fannkuch
is the algorithm I translated (yesterday) from the GCC entry (most
others use the same approach).
(defun fannkuch (n)
(declare (optimize (speed 3) (safety 0) (debug 0) #+lispworks(fixnum-safety 0))
(type (integer 0 128) n))
(if (< n 1) (return-from fannkuch 0))
(let ((perm (make-array n :element-type '(integer 0 128)))
(perml (make-array n :element-type '(integer 0 128)))
(count (make-array n :element-type '(integer 0 128)))
(flips 0) (flipsmax 0) (r n) (nl (1- n)) (perm0 0)
(check 0)
(k 0) (i 0))
(declare (type (simple-array (integer 0 128) (*)) perm perml count)
(type (integer 0 256) flips flipsmax nl perm0 check k i)
(type (integer 0 128) r))
(loop for i from 0 below n do (setf (aref perml i) i))
(loop
(when (< check 30)
(loop for i from 0 below n do (princ (1+ (aref perml i))))
(terpri)
(incf check))
(loop while (> r 1) do
(setf (aref count (1- r)) r)
(decf r))
(unless (or (= (aref perml 0) 0) (= (aref perml nl) nl))
(setf flips 0)
(loop for i fixnum from 0 below n do (setf (aref perm i) (aref perml i)))
(setf k (aref perml 0))
(loop while (/= k 0) do
(loop for j fixnum downfrom (1- k)
for i fixnum from 1
while (< i j) do (rotatef (aref perm i) (aref perm j)))
(incf flips)
(rotatef k (aref perm k)))
(when (< flipsmax flips)
(setf flipsmax flips)))
(loop do
(when (= r n) (return-from fannkuch flipsmax))
(setf i 0 perm0 (aref perml 0))
(loop while (< i r) do
(setf k (1+ i)
(aref perml i) (aref perml k)
i k))
(setf (aref perml r) perm0)
(when (> (decf (aref count r)) 0) (loop-finish))
(incf r)))))
I finally loaded SBCL 0.9.17 onto one of my FreeBSD machines.
On the lowly PIIIx2 500MHz (time (fannkuch 10))
SBCL 0.9.17 3.01s
LWL 4.3.7 4.75s
gcc 1.80s
(from the Shootout Site gcc -O3 -fomit-frame-pointer -march=pentium3)
Scaling that to the results on the shootout site puts gcc=0.47,
LW=1.24 and SBCL=0.79.
Why the shootout site would have removed the previous faster Lisp
version is beyond me.
Wade
>
> i'm going to test this out and compare it to the original too. so far
> i've just downloaded slime and sbcl and am stumbling my way around it
> all.
>
> what sort of things do you use lisp for, by the way? and do you use
> other languages too?
>
Not anything numerically intensive. Currently at work I use it to write
testers/emulators. At home, my first CL program written and delivered as
a complete app was... (I did it to learn CL). If you want to learn CL
I would suggest you try something non-trivial like that. Nothing like
getting your feet wet and to to see how CL makes development so much easier.
http://www.download.com/The-Runner-s-Log/3000-2136_4-6893549.html?tag=lst-0-1
Wade
ig...@yahoo.com
If you have a week to waste, you could go back and read through the old
shootout mailing list archives and try to match it to what Jon Harrop
now says.
Isaac Gouy
Henry Bigelow wrote:
> Juho Snellman wrote:
-snip-
> > > p.s. what would you say to changing the shootout such that multiple
> > > programs can be submitted, and the results shown based on whatever
> > > selection criteria wanted?
> >
> > Sounds like a horrible idea. You want *more* crappy programs for
> > people to whine about? :-)
>
> yes! :)
Multiple programs can be submitted, and the results for all those
programs are shown. Occasionally we go through and throw-out slower
programs (unless they seem interesting).
And then there's "FAQ: Who's working on similar projects?"
http://shootout.alioth.debian.org/gp4/faq.php#similar
Jon Harrop
> hi mr. harrop! i was surprised to see your post over here on c.l.l!
> did you start on lisp before o'caml?
I started on SML and moved to OCaml. Then I toyed with some of the other
FPLs, including Lisp.
> so, is that shootout the best one
> available, despite the grim lifecycle descriptions?
Yes, AFAIK.
> from your and juho's descriptions, the owners sound a bit deceitful!
Only Isaac Gouy has tried to deceive people, AFAIK.
I have two fundamental disagreements with the shootout:
1. Benchmarks should be a function of a non-trivial input to obviate
arbitrary precomputation, e.g. computing the digits of pi is a stupid
benchmark.
2. Program selection should be objective to evade any notion of "cheating",
e.g. see the "Note"s in binary-trees.
If I were to create a shootout, I would use benchmarks with variable inputs
and I would try to remove all subjective criteria.
For example, to test the performance and implementation of balanced binary
trees in different languages I would try to define a benchmark that was
best solved using such trees, rather than trying to force programmers to
use trees. This might be something like: "use the given random number
generator with seed "x" to generate "n" sets of "m" random numbers in
different ranges and then compute the intersection of the sets,
with "x", "n" and "m" given on the command line". (When the overlap of two
sets is small, set-theoretic operations are faster with trees than with
hash tables.)
Unfortunately, my constructive criticisms fell on one of Isaac's deaf
ears. ;-)
Isaac Gouy
Jon Harrop wrote:
> Henry Bigelow wrote:
> > hi mr. harrop! i was surprised to see your post over here on c.l.l!
> > did you start on lisp before o'caml?
>
> I started on SML and moved to OCaml. Then I toyed with some of the other
> FPLs, including Lisp.
>
> > so, is that shootout the best one
> > available, despite the grim lifecycle descriptions?
>
> Yes, AFAIK.
>
> > from your and juho's descriptions, the owners sound a bit deceitful!
>
> Only Isaac Gouy has tried to deceive people, AFAIK.
That is no more than malicious personal abuse - you contributed similar
baseless personal attacks to the shootout mailing-list.
> I have two fundamental disagreements with the shootout:
>
> 1. Benchmarks should be a function of a non-trivial input to obviate
> arbitrary precomputation, e.g. computing the digits of pi is a stupid
> benchmark.
>
> 2. Program selection should be objective to evade any notion of "cheating",
> e.g. see the "Note"s in binary-trees.
>
> If I were to create a shootout, I would use benchmarks with variable inputs
> and I would try to remove all subjective criteria.
>
> For example, to test the performance and implementation of balanced binary
> trees in different languages I would try to define a benchmark that was
> best solved using such trees, rather than trying to force programmers to
> use trees. This might be something like: "use the given random number
> generator with seed "x" to generate "n" sets of "m" random numbers in
> different ranges and then compute the intersection of the sets,
> with "x", "n" and "m" given on the command line". (When the overlap of two
> sets is small, set-theoretic operations are faster with trees than with
> hash tables.)
>
> Unfortunately, my constructive criticisms fell on one of Isaac's deaf
> ears. ;-)
I heard them the first and second time, but stopped listening as they
were repeated month after month.
Jack Andrews created "The shootin" partly in response to criticisms of
the shootout. I think it's sad that in the past year you haven't taken
the opportunity to be constructive and contribute to "The shootin".
http://shootin.sourceforge.net/
Henry Bigelow
Isaac Gouy wrote:
> Henry Bigelow wrote:
> > Juho Snellman wrote:
> -snip-
>
> > > > p.s. what would you say to changing the shootout such that multiple
> > > > programs can be submitted, and the results shown based on whatever
> > > > selection criteria wanted?
> > >
> > > Sounds like a horrible idea. You want *more* crappy programs for
> > > people to whine about? :-)
> >
> > yes! :)
>
> Multiple programs can be submitted, and the results for all those
> programs are shown. Occasionally we go through and throw-out slower
> programs (unless they seem interesting).
hi isaac,
thanks for your reply. and thanks especially for maintaining the
shootout. it was a very enlightening day when i first came across it a
few years ago.
i think the territory of benchmarks and contests is unavoidably
contentious. and in some ways this is a positive thing. (although in
others, unfortunately, negative)
to mitigate the frustration of having a benchmark deleted, (even if it
becomes invalid due to a change in requirements), would you consider a
CVS tree, one for each benchmark/language combination? or would that
be impractical?
the branches or leaves could be labeled by benchmark criteria, and
whether they satisfy it, and the running statistics, and possibly even
the version of the compiler that compiled it. that way, it would be
plain to everyone who wants to know whether a given version was
producing the correct output, and in certain cases, what tweaks made
something run faster. that would be interesting to me at least.
of course, it would have the drawback of accumulating 'dead' leaves,
maybe even spam. depending on how prevalent it was, i suppose this
approach would become impractical. i don't know.
also, i feel the concept of a shootout and shootin are orthgonal. i'd
be interested to follow the development of both.
thanks in advance,
henry
Isaac Gouy
It's not clear to me what problem your suggestion is supposed to solve.
I think the place to understand "what tweaks made something run faster"
is within a particular language community like this:
http://www.haskell.org/hawiki/ShootoutEntry
The old Doug Bagley benchmarks were mostly replaced by new benchmarks
during autumn/winter 2005 - I haven't been keeping track but I don't
think the benchmarks have been changed this year.
Henry Bigelow
> It's not clear to me what problem your suggestion is supposed to solve.
>
description of the "life cycle" of a benchmark entry:
jon: "the shootout maintainers claim the program never existed." etc.
juho:
>5. The requirements for the benchmark are modified, and the optimized
> Lisp implementation gets deleted. There's no sign of it ever
> having existed.
and wade:
>Why the shootout site would have removed the previous faster Lisp
>version is beyond me.
if several people could all contribute their versions, there might not
be any bone of contention as to which implementation of a given
benchmark was or is best. they'd all be up there with the results side
by side.
but, my hope is not just to solve a 'problem' with the shootout, but to
make it even more useful. it would be interesting to see what the
running time difference would be between a lisp fannkuch imperatively
written, and lisp fannkuch functional version would be, for example.
saying this, i realize it might be a lot more work for the maintainers,
and possibly create problems. but i took a look at the 'shootin' site,
and the author seems to promote the idea of a 'wiki but with a
community-rated account system'. perhaps commit privileges for CVS
could be regulated similarly, and it might then distribute the workload
and the accountability.
does this answer your question, or was it something else?
thanks,
henry
Ralph Richard Cook
>> it's possible that for various reasons, people don't care enough about
>> the shootout
>
...
I tried submitting code to the shootout around June 2005, but
apparently I wasn't putting the right code and makes in the right
little dialog boxes, so it didn't go through their automatic build. I
tried to get clarifications but a reply to my e-mails took about a
week to get back, so I just gave up.
Isaac Gouy
Henry Bigelow wrote:
> >
> > It's not clear to me what problem your suggestion is supposed to solve.
> >
> the problem CVS will solve was mentioned by jon, juho and wade in their
> description of the "life cycle" of a benchmark entry:
>
> jon: "the shootout maintainers claim the program never existed." etc.
As I said, for this go read the shootout mailing-list archive.
> juho:
>
> >5. The requirements for the benchmark are modified, and the optimized
> > Lisp implementation gets deleted. There's no sign of it ever
> > having existed.
>
> and wade:
>
> >Why the shootout site would have removed the previous faster Lisp
> >version is beyond me.
The shootout site removed "the previous faster Lisp version" of
Fannkuch because it no longer had any measured time to display, it no
longer gave the correct answer, it was broken, it stayed down at the
bottom of the table showing 'Error' (I don't know how many months
passed before it was finally removed - maybe we waited until someone
contributed a working program).
(When Fannkuch was changed back in 2005, I went through the contributed
Fannkuch programs in the tracker and emailed the people who had
provided an email address to let them know that the spec had been
changed. Within a short time we received fixed programs for most of the
programming languages.)
> if several people could all contribute their versions, there might not
> be any bone of contention as to which implementation of a given
> benchmark was or is best. they'd all be up there with the results side
> by side.
>
> but, my hope is not just to solve a 'problem' with the shootout, but to
> make it even more useful. it would be interesting to see what the
> running time difference would be between a lisp fannkuch imperatively
> written, and lisp fannkuch functional version would be, for example.
I guess you haven't noticed the 2 Scala programs we show for fannkuch
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=scala&id=2
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=scala&id=0
> saying this, i realize it might be a lot more work for the maintainers,
> and possibly create problems.
You seem to be suggesting that we should show every program that has
ever been contributed, for ever. Do you understand that we continually
update the language implementations and re-measure the programs?
> but i took a look at the 'shootin' site,
> and the author seems to promote the idea of a 'wiki but with a
> community-rated account system'. perhaps commit privileges for CVS
> could be regulated similarly, and it might then distribute the workload
> and the accountability.
If you think "the shootin" has promise then help make something happen
with "the shootin".
Henry Bigelow
hi ralph,
i see. well, i suppose it's possible that the maintainers are not
very motivated, since it's a free service after all. or, they might be
overwhelmed with emails. is there any way you can think to make the
submission process more reliable or easier?
and, what do you think of the idea of having a community-moderated CVS
submission of code?
thanks,
henry
Henry Bigelow
i didn't notice that. i'm just talking about eliminating the
controversy caused by deleting old submissions, even if they are
non-working. the fact that they are non-working is important
information too.
>
> > saying this, i realize it might be a lot more work for the maintainers,
> > and possibly create problems.
>
> You seem to be suggesting that we should show every program that has
> ever been contributed, for ever. Do you understand that we continually
> update the language implementations and re-measure the programs?
i was suggesting keeping the history of edits for each program, but not
necessarily displaying the results for each. and, not to remeasure the
entire history of all versions--that would obviously be impractical.
so, for each benchmark, a CVS history of edits. and with each leaf on
the version, whatever test results were performed, with whatever
language implementation etc. some versions would be retested with
newer compiler implementations, or against newer algorithm requirements
and assigned 'error', or whatever, just the way you normally do it.
the only difference would be that this information would be recorded,
and you wouldn't have to make a decision whether to delete it or not.
so, what i propose doesn't require any more computation than you
already do, just more diskspace.
i don't know, maybe there really isn't any way to remedy this
situation. anyone have any other ideas?
henry
Isaac Gouy
Why do you think the fact that broken programs are important
information for the computer language shootout - we deal in working
programs, that's why we provide example output files for people to diff
against.
Did you notice that we accept programs contributed as file attachements
to our tracking system - we don't delete from the tracking system.
>
> >
> > > saying this, i realize it might be a lot more work for the maintainers,
> > > and possibly create problems.
> >
> > You seem to be suggesting that we should show every program that has
> > ever been contributed, for ever. Do you understand that we continually
> > update the language implementations and re-measure the programs?
>
> i was suggesting keeping the history of edits for each program, but not
> necessarily displaying the results for each. and, not to remeasure the
> entire history of all versions--that would obviously be impractical.
>
> so, for each benchmark, a CVS history of edits. and with each leaf on
> the version, whatever test results were performed, with whatever
> language implementation etc. some versions would be retested with
> newer compiler implementations, or against newer algorithm requirements
> and assigned 'error', or whatever, just the way you normally do it.
> the only difference would be that this information would be recorded,
> and you wouldn't have to make a decision whether to delete it or not.
I think you are starting to define a project - go do! ;-)
Isaac Gouy
Was it an implementation for Fasta?
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fasta&lang=sbcl&id=0
Juho Snellman
> That seems to be a more-or-less reasonable summary to me - although I
> don't understand what you think the benefit of displaying optimized
> Lisp implementations that don't give the expected result would be (#5).
The benefit would obviously be that someone who decides to implement
that program can start working from the old version, instead of
writing it from scratch. I'd expect that it's going to be easier to
make the existing optimized program conform to the new specification
than re-implement an equally optimized one from scratch.
Also, please note that it was absolutely not my intention to accuse
Isaac, or anyone else involved with the Shootout, of being deceitful
or having an anti-Lisp agenda. Or actually to accuse them of anything.
My point was just that people really shouldn't be using the Shootout
for making decisions about what languages to use, since it's not
unlikely that a program for Blub has been submitted by someone who is
still a newbie at programming Blub.
--
Juho Snellman
Isaac Gouy
Juho Snellman wrote:
> ig...@yahoo.com <ig...@yahoo.com> wrote:
> > That seems to be a more-or-less reasonable summary to me - although I
> > don't understand what you think the benefit of displaying optimized
> > Lisp implementations that don't give the expected result would be (#5).
>
> The benefit would obviously be that someone who decides to implement
> that program can start working from the old version, instead of
> writing it from scratch. I'd expect that it's going to be easier to
> make the existing optimized program conform to the new specification
> than re-implement an equally optimized one from scratch.
[ #302423 ] Lisp SBCL fannkuch Juho Snellman 2005-10-26
http://alioth.debian.org/tracker/index.php?func=detail&aid=302423&group_id=30402&atid=411646
> Also, please note that it was absolutely not my intention to accuse
> Isaac, or anyone else involved with the Shootout, of being deceitful
> or having an anti-Lisp agenda. Or actually to accuse them of anything.
>
> My point was just that people really shouldn't be using the Shootout
> for making decisions about what languages to use, since it's not
> unlikely that a program for Blub has been submitted by someone who is
> still a newbie at programming Blub.
Oh it's worse that that, sometimes we get programs that even I as a
newbie Blub programmer can write better ;-)
Thomas A. Russ
> it looks like you have a lot of experience. so, benchmark politics
> aside, do you find lisp to be fast enough to do heavy-duty computing,
> (in my case, a bayesian network with hundreds of nodes and lots of
> floating point addition, but also written in a very extensible,
> abstract style)
Well, I have one anecdote to relate, told to me by a professor who took
his sabbatical to work on Bayesian networks. He and another programmer
began working on code to do Bayesian netork analysis of genetic factors
for genetic counselors. The professor used Lisp and the other
programmer C.
The Lisp version (no surprise) was completed much more quickly. It also
exploited lisp's run-time compiler by taking a particular family tree
and generating a program for evaluating the resulting Bayesian network
analysis. This program was then compiled and used for the analysis.
That alone made it faster than the C program. And with the extra time
available, the professor was able to include some additional features
(like a nicer user inteface) and some algorithmic improvements that the
C programmer never had time to get to, because they were still working
on getting the basic code for evaluating the Bayesian network for a
network defined at runtime to work.
--
Thomas A. Russ, USC/Information Sciences Institute
Jon Harrop
> it looks like you have a lot of experience. so, benchmark politics
> aside, do you find lisp to be fast enough to do heavy-duty computing,
> (in my case, a bayesian network with hundreds of nodes and lots of
> floating point addition, but also written in a very extensible,
> abstract style)
You may be interested in my ray tracer benchmarks:
http://www.ffconsultancy.com/free/ray_tracer/languages.html
On my computer, those benchmarks show Lisp to be roughly twice as slow and
twice as verbose as OCaml. However, the benchmark is quite specific. It
only tests data structures (trees) and floating point performance (ray
sphere). Also, timings vary considerably between architectures. Now that
Intel has a decent CPU, I'll be interested to see a Core Duo version of
this benchmark.
Jon Harrop
> Jon Harrop wrote:
>> Only Isaac Gouy has tried to deceive people, AFAIK.
>
> That is no more than malicious personal abuse -
From my point of view, you implied that I had plagiarised the ray tracer
(following Alex Goldman) and then revoked my access.
> you contributed similar baseless personal attacks to the shootout
> mailing-list.
I don't believe so.
> Jack Andrews created "The shootin" partly in response to criticisms of
> the shootout. I think it's sad that in the past year you haven't taken
> the opportunity to be constructive and contribute to "The shootin".
Fortunately, my business is sufficiently busy that I don't have spare time
to invest in such projects. Indeed, I have little time to improve my own
benchmarking site.
I think we'll all agree that benchmarking "across the board" is very
difficult. You've tried. I disagree with the fundamental approach taken by
your shootout (particularly the unnecessary subjectivity). I tried. Juho
kindly contributed a lot of Lisp code to my ray tracer benchmark but, I
believe, he disagrees with the way I presented the results. So it goes
on...
Jon Harrop
>> saying this, i realize it might be a lot more work for the maintainers,
>> and possibly create problems.
>
> You seem to be suggesting that we should show every program that has
> ever been contributed, for ever. Do you understand that we continually
> update the language implementations and re-measure the programs?
Why don't you reinstate the ray tracer benchmark? I still think it is the
best designed benchmark on the shootout (spectral-norm is my second
favourite).
PS: If your answer is going to be "because the different language's
implementations use different algorithms" then I'll repeat "so do several
of your other benchmarks".
Isaac Gouy
Let no one accuse you of modesty.
Jon Harrop
> My point was just that people really shouldn't be using the Shootout
> for making decisions about what languages to use, since it's not
> unlikely that a program for Blub has been submitted by someone who is
> still a newbie at programming Blub.
Given that poor (slow) implementations get replaced, the lack of a good
implementation can be taken to imply either an unwillingness or inability
of that community.
I'm not saying that is a good idea, but it is all the reader has to go on.
On the other hand, maybe Lispers think that the shootout is biased and,
consequently, will not bother working on it whereas the D programmer might
love the shootout because it is a low-cost advertisement.
Isaac Gouy
Incidentally, if you would like this program or any variant you might
author from Juho Snellman's program to appear on the computer language
shootout, you should follow the FAQ instructions
http://shootout.alioth.debian.org/gp4/faq.php#help
Wade Humeniuk
Sure,
I submitted a slightly modified version. It is only 30% slower than the gcc
version.
Wade
;;; The Computer Language Shootout
;;; http://shootout.alioth.debian.org/
;;; Contributed by Wade Humeniuk
;;;
;;; fannkuch for Lisp (SBCL)
;;;
;;; Compile: sbcl --load fannkuch.lisp --eval "(save-lisp-and-die \"fannkuch.core\"
:purify t :toplevel (lambda () (main) (quit)))"
;;;
;;; Run: sbcl --noinform --core fannkuch.core %A
(defun write-permutation (perm)
(loop for i across perm do
(princ (1+ i)))
(terpri))
(defun fannkuch (n)
(declare (optimize (speed 3) (safety 0) (debug 0)) (fixnum n))
(assert (< 1 n 128))
(let ((perm (make-array n :element-type 'fixnum))
(perm1 (make-array n :element-type 'fixnum))
(count (make-array n :element-type 'fixnum))
(flips 0) (flipsmax 0) (r n) (check 0) (k 0)
(i 0) (perm0 0))
(declare ((simple-array fixnum (*)) perm perm1 count)
(fixnum flips flipsmax check k r i perm0))
(dotimes (i n) (setf (aref perm1 i) i))
(loop
(when (< check 30)
(write-permutation perm1)
(incf check))
(loop while (> r 1) do
(setf (aref count (1- r)) r)
(decf r))
(unless (or (= (aref perm1 0) 0)
(= (aref perm1 (1- n)) (1- n)))
(setf flips 0)
(dotimes (i n) (setf (aref perm i) (aref perm1 i)))
(setf k (aref perm1 0))
(loop while (/= k 0) do
(loop for j fixnum downfrom (1- k)
for i fixnum from 1
while (< i j) do (rotatef (aref perm i) (aref perm j)))
(incf flips)
(rotatef k (aref perm k)))
(setf flipsmax (max flipsmax flips)))
(loop do
(when (= r n)
(return-from fannkuch flipsmax))
(setf i 0 perm0 (aref perm1 0))
(loop while (< i r) do
(setf k (1+ i)
(aref perm1 i) (aref perm1 k)
i k))
(setf (aref perm1 r) perm0)
(when (> (decf (aref count r)) 0) (loop-finish))
(incf r)))))
(defun main ()
(let ((n (parse-integer (second *posix-argv*))))
(format t "Pfannkuchen(~D) = ~D~%" n (fannkuch n))))
Henry Bigelow
> You may be interested in my ray tracer benchmarks:
>
> http://www.ffconsultancy.com/free/ray_tracer/languages.html
thank you! very enlightening. i read the analysis. i have a few
questions about this excerpt
"However, the designers of the ML family of languages (including OCaml
and SML) deliberately avoided some of the functionality provided by
Lisp in order to facilitate static type checking and improve
performance."
i guess i misunderstood something. does lisp not have any type
inference? or does it have partial type inference if you explicitly
declare the types for some variables and not others?
"Specifically, Lisp provides macros to customise syntax and allows them
to be entwined with ordinary code, and provides run-time code
manipulation. SML provides neither macros nor run-time code
generation."
"OCaml provides camlp4 macros, a limited form that are separate from
the language, and the derived language MetaOCaml also provides run-time
code generation"
are camlp4 macros as powerful as lisp macros?
and, is the run-time code generation of MetaOCaml as powerful as lisp's
'compile' function?
in the bigger picture, do you foresee any advancements to either lisp
or ocaml that would improve either of them, maybe by sharing ideas?
thanks,
henry
>
> On my computer, those benchmarks show Lisp to be roughly twice as slow and
> twice as verbose as OCaml.
while i'm not surprised lisp is slower for this benchmark, i am
confused why it would be more verbose.
Wade Humeniuk
Lisp SBCL #2 is now 5th on
http://shootout.alioth.debian.org/gp4/benchmark.php?test=fannkuch&lang=all
However there seems to be a problem getting it going on the
Debian AMD Sempron test. Something is different about getting
SBCL and CMUCL execed's (unexec'd) on those platforms. I assume
it is Debian preventing execution.
http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=sbcl&id=2
http://shootout.alioth.debian.org/debian/benchmark.php?test=fannkuch&lang=cmucl&id=2
Wade
Isaac Gouy
We ask for push everything to go through the tracker, so we can um keep
track of things... There's a bug tracker
http://alioth.debian.org/tracker/?atid=411002&group_id=30402&func=browse
Rahul Jain
> hi jon,
>
>> You may be interested in my ray tracer benchmarks:
>>
>> http://www.ffconsultancy.com/free/ray_tracer/languages.html
>
> thank you! very enlightening. i read the analysis. i have a few
> questions about this excerpt
>
> "However, the designers of the ML family of languages (including OCaml
> and SML) deliberately avoided some of the functionality provided by
> Lisp in order to facilitate static type checking and improve
> performance."
>
> i guess i misunderstood something. does lisp not have any type
> inference? or does it have partial type inference if you explicitly
> declare the types for some variables and not others?
What do you mean by "Lisp"? The standard does not require type
inference, as it's merely a way to optimize code by eliding type
dispatches at run time and allowing the inlining of the implementation
of the operator for that specific type.
Lisp has a much richer type system than any of the MLs. CMUCL, for
example, can do type inference to determine whether the arcsin of a
value rounded off to the nearest integer will fit in a machine word or
whether it might need to have a bignum (MLs don't have bignums as part
of the language).
For example, if we compile the following:
(defun test (x y)
(declare (type (integer 5 100) x)
(type (integer 1 5) y))
(expt x y))
CMUCL tells us (among other things):
Function: #<Function TEST {582F61C9}>
Function arguments:
(x y)
Its defined argument types are:
((INTEGER 5 100) (INTEGER 1 5))
Its result type is:
(INTEGER 5 10000000000)
Therefore, it has figured out that an integer from 5 to 100 raised to
the power of an integer from 1 to 5 gives us an integer from 5 to
10000000000. It can then use this information to determine whether to
return a boxed (with type information if the result can overflow a
register) or unboxed (raw value in a register) value.
As an exmaple of this, we can compile the following:
(defun test (x y)
(declare (optimize speed (safety 0))
(type (integer 5 1000000) x)
(type (integer 1 5000000) y))
(* x y))
and the compiler tells us:
; Note: Forced to do GENERIC-* (cost 30).
; Unable to do inline fixnum arithmetic (cost 4) because:
; The result is a (INTEGER 5 5000000000000), not a FIXNUM.
; Unable to do inline (signed-byte 32) arithmetic (cost 5) because:
; The result is a (INTEGER 5 5000000000000), not a (SIGNED-BYTE 32).
; etc.
Delete a few zeroes from each of the upper bounds and the note goes
away, as the * can be inlined (in the dissasembly, we see:
C9: IMUL EDX, EDI
instead of:
7E: CALL #x100002D0 ; #x100002D0: GENERIC-*
This topic is VERY, VERY important to optimizing Lisp numeric code, so
be SURE to study it carefully.
--
Rahul Jain
rj...@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain
> Much as I appreciate Paolo's nod to BioBike, let me second Robert's
> recommendation of R if all you need to do is crunch a bunch of numbers
> that represent a bayes net. R has a quasi-reasonable quasi-Lisp
> programming language and numerous packages to support mathematical and
> statistical computing (incl. extensive bayesian machinery).
I'm sure you know this, but the OP might find it interesting:. it's not
by accident a quasi-Lisp. It's an open source C port of S, which was
written in Lisp, according to what I gather.
Rahul Jain
> Henry Bigelow ha escrito:
>> i have zero lisp experience. i started with perl, then c++, then
>> o'caml. a few days ago i read paul graham's summary of john mccarthy's
>> paper, and then started reading the original, and On Lisp. i'm
>> completely wowed, and would love to use it to write my programs.
>
> Why not first start learning with Practical Common Lisp? On Lisp is
> more advanced and focused on macros.
>
> http://www.gigamonkeys.com/book/
Personally, I would recommend PAIP for the subject matter he's dealing
with. PAIP deals more with information processing. PCL is much broader
and covers parts of what both PAIP and On Lisp cover, in addition to
general application building. That said, PCL is a great book, and would
probably complement PAIP nicely for him.
Henry Bigelow
Rahul Jain wrote:
> > "However, the designers of the ML family of languages (including OCaml
> > and SML) deliberately avoided some of the functionality provided by
> > Lisp in order to facilitate static type checking and improve
> > performance."
> >
> > i guess i misunderstood something. does lisp not have any type
> > inference? or does it have partial type inference if you explicitly
> > declare the types for some variables and not others?
>
> What do you mean by "Lisp"? The standard does not require type
> inference, as it's merely a way to optimize code by eliding type
> dispatches at run time and allowing the inlining of the implementation
> of the operator for that specific type.
i don't know what i mean by lisp. :) or what the standard defines.
does the standard require that "lisp can be written in itself" as paul
graham says (whatever that means)?
and, is that why
somehow has a drawback that aggressive type inference can't be done,
with any compiler of lisp.
>
> Lisp has a much richer type system than any of the MLs. CMUCL, for
> example, can do type inference to determine whether the arcsin of a
> value rounded off to the nearest integer will fit in a machine word or
> whether it might need to have a bignum (MLs don't have bignums as part
> of the language).
yes, but it's been mentioned several times that, in order to get lisp
code to run fast, you have to "litter it with type declarations". so,
it seems, there isn't much type inference going on.
also, i got that idea from this wikipedia page:
http://en.wikipedia.org/wiki/Type_system
about halfway down it mentions this:
Static typing usually results in compiled code that executes more
quickly. When the compiler knows the exact data types that are in use,
it can produce machine code that just does the right thing. Further,
compilers in statically typed languages can find shortcuts more easily.
Some dynamically-typed languages such as Common Lisp allow optional
type declarations for optimization for this very reason. Static typing
makes this pervasive. See optimization.
>
> For example, if we compile the following:
> (defun test (x y)
> (declare (type (integer 5 100) x)
> (type (integer 1 5) y))
> (expt x y))
>
> CMUCL tells us (among other things):
> Function: #<Function TEST {582F61C9}>
> Function arguments:
> (x y)
> Its defined argument types are:
> ((INTEGER 5 100) (INTEGER 1 5))
> Its result type is:
> (INTEGER 5 10000000000)
>
> Therefore, it has figured out that an integer from 5 to 100 raised to
> the power of an integer from 1 to 5 gives us an integer from 5 to
> 10000000000. It can then use this information to determine whether to
> return a boxed (with type information if the result can overflow a
> register) or unboxed (raw value in a register) value.
>
that is neat. i'd never heard of that before.
>
> As an exmaple of this, we can compile the following:
> (defun test (x y)
> (declare (optimize speed (safety 0))
> (type (integer 5 1000000) x)
> (type (integer 1 5000000) y))
> (* x y))
>
> and the compiler tells us:
> ; Note: Forced to do GENERIC-* (cost 30).
> ; Unable to do inline fixnum arithmetic (cost 4) because:
> ; The result is a (INTEGER 5 5000000000000), not a FIXNUM.
> ; Unable to do inline (signed-byte 32) arithmetic (cost 5) because:
> ; The result is a (INTEGER 5 5000000000000), not a (SIGNED-BYTE 32).
> ; etc.
>
> Delete a few zeroes from each of the upper bounds and the note goes
> away, as the * can be inlined (in the dissasembly, we see:
> C9: IMUL EDX, EDI
> instead of:
> 7E: CALL #x100002D0 ; #x100002D0: GENERIC-*
>
>
> This topic is VERY, VERY important to optimizing Lisp numeric code, so
> be SURE to study it carefully.
i see. that's pretty cool. so, what is your programming style? do
you first prototype something without any type declarations, and then
add in a few in the compute-intensive code?
thanks,
henry
Jon Harrop
> Lisp has a much richer type system than any of the MLs.
I'm not sure what you mean by that. ML does lots of things that Lisp does
not and vice-versa.
> CMUCL, for
> example, can do type inference to determine whether the arcsin of a
> value rounded off to the nearest integer will fit in a machine word or
> whether it might need to have a bignum
ML doesn't have a numeric tower. You have to explicitly state that you want
an int, float, bignum and so on.
> (MLs don't have bignums as part of the language).
OCaml, SML and F# all have bignums as part of the language.
> This topic is VERY, VERY important to optimizing Lisp numeric code, so
> be SURE to study it carefully.
In contrast, succinct ML is typically fast ML.
Rahul Jain
> does the standard require that "lisp can be written in itself" as paul
> graham says (whatever that means)?
It doesn't explicitly require that, but it defines a turing-complete
language, so yeah... you can write a lisp compiler and interpreter in
lisp, as you can in C or Perl. The difference, I think, that PG is
getting at is that the most basic lisp data is code itself. Thinking
about code in an abstract manner is just second nature when you're
programming in lisp.
> and, is that why
>
> somehow has a drawback that aggressive type inference can't be done,
> with any compiler of lisp.
I don't see how those two statements could possibly correlate, and later
I demonstrate more aggressive type inference being done than any other
language I've heard of.
>> Lisp has a much richer type system than any of the MLs. CMUCL, for
>> example, can do type inference to determine whether the arcsin of a
>> value rounded off to the nearest integer will fit in a machine word or
>> whether it might need to have a bignum (MLs don't have bignums as part
>> of the language).
>
> yes, but it's been mentioned several times that, in order to get lisp
> code to run fast, you have to "litter it with type declarations". so,
> it seems, there isn't much type inference going on.
No, you "litter" it where needed. It depends from compiler to compiler.
C and Java code is so littered with type declarations, the highway
police would arrest the programmer if he hadn't already run into a
lamppost because his code crashed.
> also, i got that idea from this wikipedia page:
>
> http://en.wikipedia.org/wiki/Type_system
>
> about halfway down it mentions this:
>
> Static typing usually results in compiled code that executes more
> quickly. When the compiler knows the exact data types that are in use,
> it can produce machine code that just does the right thing. Further,
> compilers in statically typed languages can find shortcuts more easily.
> Some dynamically-typed languages such as Common Lisp allow optional
> type declarations for optimization for this very reason. Static typing
> makes this pervasive. See optimization.
Haha! I just modified that paragraph last month to fix the way it
described "Lisp". But yes, Common Lisp can be as static or dynamic as
you want it to be.
> i see. that's pretty cool. so, what is your programming style? do
> you first prototype something without any type declarations, and then
> add in a few in the compute-intensive code?
That's the third rule of optimization applied to type declarations. So
yes. :)
Remember not to conflate type declarations with type checks. (Although
code declared to be safe will always check types when it calls standard
lisp functions.)
Rahul Jain
> Rahul Jain wrote:
>> Lisp has a much richer type system than any of the MLs.
>
> I'm not sure what you mean by that. ML does lots of things that Lisp does
> not and vice-versa.
Hmm. I'm not sure about that. All I can think of is inference of
parametrized array types (non-upgraded) across functions. Lisp just
doesn't _require_ those things to be done. If someone cared, they could
augment a compiler to do it.
What I'm talking about, to clarify, is for an array declared to have an
element type of (integer 1 100), a function that returns an element of
it should have an inferred return type of (integer 1 100).
For:
(defun test (x)
(declare (type (array (integer 1 100) (*)) x))
(aref x 1))
CMUCL inferrs a return type of:
Its result type is:
(UNSIGNED-BYTE 8)
So it has upgraded the element type to what it's actually going to store
in memory. Dunno why it doesn't just propagate the element type
defintion directly.
>> CMUCL, for
>> example, can do type inference to determine whether the arcsin of a
>> value rounded off to the nearest integer will fit in a machine word or
>> whether it might need to have a bignum
>
> ML doesn't have a numeric tower. You have to explicitly state that you want
> an int, float, bignum and so on.
>
>> (MLs don't have bignums as part of the language).
>
> OCaml, SML and F# all have bignums as part of the language.
Interesting. Some self-proclaimed ocaml genius claimed that it didn't
have bignums. Maybe he meant that you need to explicitly... um...
declare (?!?) a number to be a bignum? That would fit in with the lack
of a numeric tower.
>> This topic is VERY, VERY important to optimizing Lisp numeric code, so
>> be SURE to study it carefully.
>
> In contrast, succinct ML is typically fast ML.
Yeah, but you don't know if it's going to be correct unless you manually
perform the kind of type inference that CMUCL does. :)
On a more serious note, you still end up with the problem that your code
is either slow but tolerant of different architectures or it's fast on
some architectures and incorrect on others. Sure, you could maintain two
parallel versions of the codebase, but don't programmers like
abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be
happy writing machine code if they could still get paid enough for their
time.)
Javier
Rahul Jain ha escrito:
> Hmm. I'm not sure about that. All I can think of is inference of
> parametrized array types (non-upgraded) across functions. Lisp just
> doesn't _require_ those things to be done. If someone cared, they could
> augment a compiler to do it.
> What I'm talking about, to clarify, is for an array declared to have an
> element type of (integer 1 100), a function that returns an element of
> it should have an inferred return type of (integer 1 100).
>
> For:
> (defun test (x)
> (declare (type (array (integer 1 100) (*)) x))
> (aref x 1))
> CMUCL inferrs a return type of:
> Its result type is:
> (UNSIGNED-BYTE 8)
>
> So it has upgraded the element type to what it's actually going to store
> in memory. Dunno why it doesn't just propagate the element type
> defintion directly.
One important thing I miss from Lisp compared to ML, is for example the
ability to test at compile time about the type of something. For
example you can define a list type in the style of Lisp:
type 'a lisp_list = Nil | List of 'a list
so now every variable using this type can be either Nil or a list
itself. Or even binary trees:
type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
I found this feature very usefull.
> Interesting. Some self-proclaimed ocaml genius claimed that it didn't
> have bignums.
It does:
http://caml.inria.fr/pub/docs/manual-ocaml/libref/Big_int.html
If you don't like those function names, you can rename the operators:
let ( +$ ) = add_big_int
> Maybe he meant that you need to explicitly... um...
> declare (?!?) a number to be a bignum? That would fit in with the lack
> of a numeric tower.
I don't understand what you're talking about, but you can always
convert any int or string to big_int and viceversa.
> >> This topic is VERY, VERY important to optimizing Lisp numeric code, so
> >> be SURE to study it carefully.
> >
> > In contrast, succinct ML is typically fast ML.
>
> Yeah, but you don't know if it's going to be correct unless you manually
> perform the kind of type inference that CMUCL does. :)
I think that if you are a good programmer, you must know the type of
anything you are writing, even if it is writen in Lisp. And ML does
allow you to use "generic" or arbitray types when you need. Just take
the example of the binary tree above.
> On a more serious note, you still end up with the problem that your code
> is either slow but tolerant of different architectures or it's fast on
> some architectures and incorrect on others.
> Sure, you could maintain two
> parallel versions of the codebase, but don't programmers like
> abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be
> happy writing machine code if they could still get paid enough for their
> time.)
Static inference always produce faster code compared with dynamic
inference, for an equivalent code base. But you usually need to declare
things on dynamic languages to help the inferer, while in statically
infered ones you don't, so you save a lot of time on both writing and
profiling.
You don't need to maintain parallel versions of the codebase, or if you
do, you would also do in Lisp (this is not language specific, but the
kind of algorithm/implementation you choose).
Jon Harrop
> Jon Harrop <j...@ffconsultancy.com> writes:
>> Rahul Jain wrote:
>>> Lisp has a much richer type system than any of the MLs.
>>
>> I'm not sure what you mean by that. ML does lots of things that Lisp does
>> not and vice-versa.
>
> Hmm. I'm not sure about that. All I can think of is inference of
> parametrized array types (non-upgraded) across functions. Lisp just
> doesn't _require_ those things to be done. If someone cared, they could
> augment a compiler to do it.
Sure, you can augment a compiler to do anything.
>> OCaml, SML and F# all have bignums as part of the language.
>
> Interesting. Some self-proclaimed ocaml genius claimed that it didn't
> have bignums. Maybe he meant that you need to explicitly... um...
> declare (?!?) a number to be a bignum? That would fit in with the lack
> of a numeric tower.
Yes. More than just declare though, you have to annotate every literal and
use different operators.
>> In contrast, succinct ML is typically fast ML.
>
> Yeah, but you don't know if it's going to be correct unless you manually
> perform the kind of type inference that CMUCL does. :)
>
> On a more serious note, you still end up with the problem that your code
> is either slow but tolerant of different architectures or it's fast on
> some architectures and incorrect on others. Sure, you could maintain two
> parallel versions of the codebase, but don't programmers like
> abstraction? (yeah, I know, the mainstream abhors abstraction. They'd be
> happy writing machine code if they could still get paid enough for their
> time.)
In practice, I have never had a problem caused by fixed-precision integers.
However, I have lots of problems caused by floating point precision. Does
CMUCL's type inference do anything to help with that?
Joe Marshall
Javier wrote:
>
> Static inference always produce faster code compared with dynamic
> inference, for an equivalent code base.
http://www.hpl.hp.com/techreports/1999/HPL-1999-77.pdf
``Contrary to intuition, we demonstrate that it is possible to
use a piece of software to improve the performance of a
native, statically optimized program binary, while it is
executing. Dynamo not only speeds up real application
programs, its performance improvement is often quite
significant. For example, the performance of many +O2
optimized SPECint95 binaries running under Dynamo is
comparable to the performance of their +O4 optimized
version running without Dynamo.''
Javier
Joe Marshall ha escrito:
In practice, you can almost reach the speed of a statically program,
but then the compiler must create multiple versions of the functions to
acommodate to the varius types it may use. This is the case of Psyco
(for Python).
SBCL is not, as far as I know, able to do so, and you must declare
everything which is not so susceptible to be inferred at compile time.
Even in the case that some implementation is able to do so, you have
got the penalty of the compiler being compiling everything in real time
for every new variable type encountered, so meanwhile it is compiling,
you are wasting CPU cycles. And of course, you also waste CPU cache
hits, because the code is more fragmented and much bigger. And of
course, you waste more memory too.
So I still believe that dynamic inference does always have less
performance for a similar codebase and compilers of similar qualities.
Rahul Jain
> One important thing I miss from Lisp compared to ML, is for example the
> ability to test at compile time about the type of something. For
> example you can define a list type in the style of Lisp:
>
> type 'a lisp_list = Nil | List of 'a list
>
> so now every variable using this type can be either Nil or a list
> itself. Or even binary trees:
>
> type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
>
> I found this feature very usefull.
How can you not declare types in Lisp? I don't see how this has anything
to do with "testing" anything at compile time.
>> Maybe he meant that you need to explicitly... um...
>> declare (?!?) a number to be a bignum? That would fit in with the lack
>> of a numeric tower.
>
> I don't understand what you're talking about, but you can always
> convert any int or string to big_int and viceversa.
Yes, but how do _I_ know when I need to use bignums or not?
> I think that if you are a good programmer, you must know the type of
> anything you are writing, even if it is writen in Lisp. And ML does
> allow you to use "generic" or arbitray types when you need. Just take
> the example of the binary tree above.
But you may not know what that type _means_ because that type is not
defined to mean anything. A machine word is a different size on
different processors. I can't tell ad-hoc whether a value will fit into
"the" machine word of "the" processor it might run on at any time in the
future. On the other hand, Lisp allows me to say what size the values
will have and the compiler figures out whether it will necessarily fit
into a machine word or not and emits the appropriate machine code for
that inference.
> Static inference always produce faster code compared with dynamic
> inference, for an equivalent code base.
Huh? Dynamic "inference" doesn't make sense in the context of any Lisp
system I know of. Are you talking about recompiling the codepath each
time it's run with different types... or what?
> But you usually need to declare things on dynamic languages to help
> the inferer, while in statically infered ones you don't, so you save a
> lot of time on both writing and profiling.
Huh? No way. You need (theoretically) to declare just as much in Lisp as
you do in ML. Some compilers aren't as good about type inference, and
some programmers want to keep their codebase dynamic so they can load
fixes into a live system that might change the datatypes involved in
some codepaths.
> You don't need to maintain parallel versions of the codebase, or if you
> do, you would also do in Lisp (this is not language specific, but the
> kind of algorithm/implementation you choose).
No. Because Lisp types are more closely related to the actual
mathematical types as opposed to ML types which are more closely related
to the things the computer happens to use at the moment.
I don't need to write one version with integer declarations and another
with fixnum declarations. I just define the ranges of the inputs and the
type inferer takes care of figuring out whether that architecture on
that implementation can use fixnums or needs to do generic arithmetic.
Please refer to the examples I gave. If I compiled the code on a 64 bit
machine, I wouldn't get the efficiency note. If I wanted to have that
code optimized in ML, I'd need to write one bignum version, one int
version, write code for what the CMUCL type inferer would compute, and
have that run at compile-time to determine whether I want to use the
bignum or int version given the processor's machine word size. In Lisp,
I just write the code in the way I think about it, mathematically.
Rahul Jain
> Rahul Jain wrote:
>> Jon Harrop <j...@ffconsultancy.com> writes:
>>> Rahul Jain wrote:
>>>> Lisp has a much richer type system than any of the MLs.
>>>
>>> I'm not sure what you mean by that. ML does lots of things that Lisp does
>>> not and vice-versa.
>>
>> Hmm. I'm not sure about that. All I can think of is inference of
>> parametrized array types (non-upgraded) across functions. Lisp just
>> doesn't _require_ those things to be done. If someone cared, they could
>> augment a compiler to do it.
>
> Sure, you can augment a compiler to do anything.
In ML, you _can't_ augment the compiler to do this without creating a
different dialect, because it doesn't _have_ the types needed to express
what I wrote in Lisp. If I'm wrong, please show me SML code that will
automatically switch to using bignums when the type inferer determines
that the values won't fit in a machine word.
> In practice, I have never had a problem caused by fixed-precision integers.
You've never needed a 2 GB file?
> However, I have lots of problems caused by floating point precision. Does
> CMUCL's type inference do anything to help with that?
Um, no. How could it change your hardware to conform to your idea of how
FP should work? Maybe it could, if there were a language for describing
your precision requirements. Hmm... actually, it might be able to figure
out based on the ranges of values whether you'd hit one of the FP
lossage situations and rearrange the expression until it doesn't. You'd
need to be _very_ careful in defining the ranges of values, tho, to
avoid it seeing a problem that won't exist when run on real data.
Pascal Costanza
> So I still believe that dynamic inference does always have less
> performance for a similar codebase and compilers of similar qualities.
Perform a few benchmarks, and you'll be surprised.
Pascal
--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
Rahul Jain
> And of course, you also waste CPU cache hits, because the code is
> more fragmented and much bigger.
Not so. Dynamo dynamically defragments the code.
Dr Jon D Harrop
> Jon Harrop <j...@ffconsultancy.com> writes:
> > Sure, you can augment a compiler to do anything.
>
> In ML, you _can't_ augment the compiler to do this without creating a
> different dialect, because it doesn't _have_ the types needed to express
> what I wrote in Lisp.
Yes. Doesn't that sword cut both ways though? If you supplement Lisp
with features of ML then you've created a "different dialect" as well.
Doesn't Qi do something like that?
> If I'm wrong, please show me SML code that will
> automatically switch to using bignums when the type inferer determines
> that the values won't fit in a machine word.
I don't know how to do that. MLton may already try to do this. I doubt
it though. I can't imagine that being a bottleneck for many people. ;-)
> > In practice, I have never had a problem caused by fixed-precision integers.
>
> You've never needed a 2 GB file?
Yes. Maybe I will in the future, but I'm already on 64-bit. :-)
> > However, I have lots of problems caused by floating point precision. Does
> > CMUCL's type inference do anything to help with that?
>
> Um, no. How could it change your hardware to conform to your idea of how
> FP should work?
I just want the same functionality that CMUCL already provides for
ints: use machine-precision where possible and arbitrary-precision
otherwise.
> Maybe it could, if there were a language for describing
> your precision requirements. Hmm... actually, it might be able to figure
> out based on the ranges of values whether you'd hit one of the FP
> lossage situations and rearrange the expression until it doesn't. You'd
> need to be _very_ careful in defining the ranges of values, tho, to
> avoid it seeing a problem that won't exist when run on real data.
Yes. I haven't really thought about how you could do it statically...
Cheers,
Jon.
Javier
Rahul Jain ha escrito:
> > type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
> >
> > I found this feature very usefull.
>
> How can you not declare types in Lisp? I don't see how this has anything
> to do with "testing" anything at compile time.
Basically, in ML every type must me known at compile time. If you use
the binary tree definition above, which is an arbitray one, then you
must provide a context to it. For example:
# let my_tree = Empty;;
=> val my_tree : 'a btree = Empty
but, if you assign a real value:
# let my_tree = Node (5, Empty, Empty);;
=> val my_tree : int btree = Node (5, Empty, Empty)
the compiler is able to create a new type called "int btree" from the
generic one.
The good thing about this is that, while being able to use a "dynamic"
type like a btree for storing any kind of data you want to, you also
are enforzed to not mix int with strings or floats in that tree if you
don't intentionally desire that.
This means that your code will always be type safe, avoiding some
annoying bugs.
In Lisp, if you create a binary tree, it may contain data of several
types, which is not safe. Or you can start declaring things, but then
you end up with not elegant spaggetti code, much like if it where made
in C.
> >> Maybe he meant that you need to explicitly... um...
> >> declare (?!?) a number to be a bignum? That would fit in with the lack
> >> of a numeric tower.
> >
> > I don't understand what you're talking about, but you can always
> > convert any int or string to big_int and viceversa.
>
> Yes, but how do _I_ know when I need to use bignums or not?
You must know, you are a programmer. Even in Lisp you must know the
type you are using for every variable.
> > I think that if you are a good programmer, you must know the type of
> > anything you are writing, even if it is writen in Lisp. And ML does
> > allow you to use "generic" or arbitray types when you need. Just take
> > the example of the binary tree above.
>
> But you may not know what that type _means_ because that type is not
> defined to mean anything.
It does mean. Even in mathemathics does mean. It is not the same to do
arithmetic with natural numbers than with real or complex ones. On
computers, this is important too.
> A machine word is a different size on
> different processors. I can't tell ad-hoc whether a value will fit into
> "the" machine word of "the" processor it might run on at any time in the
> future.
> On the other hand, Lisp allows me to say what size the values
> will have and the compiler figures out whether it will necessarily fit
> into a machine word or not and emits the appropriate machine code for
> that inference.
In respect to word size, you are right, dynamic ilanguagges allows you
to write less and more standard code. But the cost of this is that the
rest of the system may be unsafe if you don't declare things.
> > Static inference always produce faster code compared with dynamic
> > inference, for an equivalent code base.
>
> Huh? Dynamic "inference" doesn't make sense in the context of any Lisp
> system I know of. Are you talking about recompiling the codepath each
> time it's run with different types... or what?
I meant dynamic languages in comparison with stong ones having static
inference. Sorry if I was not clear.
> > But you usually need to declare things on dynamic languages to help
> > the inferer, while in statically infered ones you don't, so you save a
> > lot of time on both writing and profiling.
>
> Huh? No way. You need (theoretically) to declare just as much in Lisp as
> you do in ML. Some compilers aren't as good about type inference, and
> some programmers want to keep their codebase dynamic so they can load
> fixes into a live system that might change the datatypes involved in
> some codepaths.
Normaly, when a data type is changed, some side effects are happening
somewhere in your code. For example, you cannot change the type of an
important variable from an integer to a string and pretend that nothing
would happen in you code.
Your statement is only true for interchanging integers and float of
different word size, in which I recognise Lisp is more concise than ML.
But not much better, you can still use different types into one single
variable in ML:
# type number = Int of int | Float of float | Big of Big_int.big_int;;
type number = Int of int | Float of float | Big of Big_int.big_int
# let n = Float 9.4;;
val n : number = Float 9.4
# match n with
| Float n -> print_string "It is a float"
| Int n -> print_string "It is an integer"
| Big n -> print_string "It is a big number";;
=> It is a float
- : unit = ()
Rahul Jain
> Rahul Jain wrote:
>> Jon Harrop <j...@ffconsultancy.com> writes:
>> > Sure, you can augment a compiler to do anything.
>>
>> In ML, you _can't_ augment the compiler to do this without creating a
>> different dialect, because it doesn't _have_ the types needed to express
>> what I wrote in Lisp.
>
> Yes. Doesn't that sword cut both ways though? If you supplement Lisp
> with features of ML then you've created a "different dialect" as well.
> Doesn't Qi do something like that?
Qi sounds familiar, but I don't know anything specific about it. What ML
features do you think you need to achieve what I just demonstrated? Type
inference? Nothing in the CL spec forbids that.
>> If I'm wrong, please show me SML code that will
>> automatically switch to using bignums when the type inferer determines
>> that the values won't fit in a machine word.
>
> I don't know how to do that. MLton may already try to do this. I doubt
> it though. I can't imagine that being a bottleneck for many people. ;-)
>
>> > In practice, I have never had a problem caused by fixed-precision integers.
>>
>> You've never needed a 2 GB file?
>
> Yes. Maybe I will in the future, but I'm already on 64-bit. :-)
Ah, so you don't want me to use your software because my processor is
too old. Fair enough. :)
>> > However, I have lots of problems caused by floating point precision. Does
>> > CMUCL's type inference do anything to help with that?
>>
>> Um, no. How could it change your hardware to conform to your idea of how
>> FP should work?
>
> I just want the same functionality that CMUCL already provides for
> ints: use machine-precision where possible and arbitrary-precision
> otherwise.
How would it know what precision you need? You _can_ introspect the
floating point types as far as their precision, etc. I don't know of
anyone that has come up with a language to express your precision
requirements that can then be used to compute which FP type is best for
you. Also, 80 bit floats are the fastest way to compute using an x87
FPU. Should that matter, too?
>> Maybe it could, if there were a language for describing
>> your precision requirements. Hmm... actually, it might be able to figure
>> out based on the ranges of values whether you'd hit one of the FP
>> lossage situations and rearrange the expression until it doesn't. You'd
>> need to be _very_ careful in defining the ranges of values, tho, to
>> avoid it seeing a problem that won't exist when run on real data.
>
> Yes. I haven't really thought about how you could do it statically...
Well, then what are you asking us for? :P
Rahul Jain
> Rahul Jain ha escrito:
>
>
>> > type 'a btree = Empty | Node of 'a * 'a btree * 'a btree
>> >
>> > I found this feature very usefull.
>>
>> How can you not declare types in Lisp? I don't see how this has anything
>> to do with "testing" anything at compile time.
>
> Basically, in ML every type must me known at compile time. If you use
> the binary tree definition above, which is an arbitray one, then you
> must provide a context to it. For example:
>
> # let my_tree = Empty;;
> => val my_tree : 'a btree = Empty
>
> but, if you assign a real value:
>
> # let my_tree = Node (5, Empty, Empty);;
> => val my_tree : int btree = Node (5, Empty, Empty)
>
> the compiler is able to create a new type called "int btree" from the
> generic one.
Lisp has parametrized types, too. You can't tell the compiler how to
propagate your parameters through various operators, because that's not
in the standard. But you can do it given a specific compiler.
> The good thing about this is that, while being able to use a "dynamic"
> type like a btree for storing any kind of data you want to, you also
> are enforzed to not mix int with strings or floats in that tree if you
> don't intentionally desire that.
Yes, that can be done for arrays in Lisp. As I said before, custom data
types don't have their parameters inferred automatically because there's
no good way to tell what each parameter actually means.
> This means that your code will always be type safe, avoiding some
> annoying bugs.
Oh jeez. Shouldn't this kind of discussion be in comp.programming?
I believe that's where these kinds of pointless discussions abound.
> In Lisp, if you create a binary tree, it may contain data of several
> types, which is not safe.
Wrong. By your logic, the Lisp code is not a "safe" data structure.
> Or you can start declaring things, but then
> you end up with not elegant spaggetti code, much like if it where made
> in C.
I don't see where the term "spaghetti" comes from. The code would be
easy enough to follow, and type inference allows you to not need to
declare much.
>> > I don't understand what you're talking about, but you can always
>> > convert any int or string to big_int and viceversa.
>>
>> Yes, but how do _I_ know when I need to use bignums or not?
>
> You must know, you are a programmer. Even in Lisp you must know the
> type you are using for every variable.
That doesn't jive. I know the type, but that's only _because_ I'm using
Lisp, and that's the reason why the _actual_ type exists. I don't care
about how that needs to be implemented on different hardware.
>> > I think that if you are a good programmer, you must know the type of
>> > anything you are writing, even if it is writen in Lisp. And ML does
>> > allow you to use "generic" or arbitray types when you need. Just take
>> > the example of the binary tree above.
>>
>> But you may not know what that type _means_ because that type is not
>> defined to mean anything.
>
> It does mean. Even in mathemathics does mean. It is not the same to do
> arithmetic with natural numbers than with real or complex ones. On
> computers, this is important too.
Um, huh? The reals are an analytic continuation of the naturals (with
the integers as a waypoint). Same with complex and reals. That means
that arithmetic with the "complex" operators is the same as with the
"natural" operators, except for cases where you're using that analytic
continuation and the result is a complex number.
Give me the Lisp Integer type declaration that is the same as "int" in
SML.
> In respect to word size, you are right, dynamic ilanguagges allows you
> to write less and more standard code. But the cost of this is that the
> rest of the system may be unsafe if you don't declare things.
Or not. You seem to insist that CMUCL doesn't exist. You also seem to
insist that a Lisp compiler itself must be an unsafe program because it
can take arbitrary data.
>> > Static inference always produce faster code compared with dynamic
>> > inference, for an equivalent code base.
>>
>> Huh? Dynamic "inference" doesn't make sense in the context of any Lisp
>> system I know of. Are you talking about recompiling the codepath each
>> time it's run with different types... or what?
>
> I meant dynamic languages in comparison with stong ones having static
> inference. Sorry if I was not clear.
Strong languages? You're not getting clearer. :)
Do you mean strongly-typed? That's Lisp. And it has static inference if
the compiler so chooses.
Being a dyanamic language does nothing to preclude anything from being
in the type system.
>> > But you usually need to declare things on dynamic languages to help
>> > the inferer, while in statically infered ones you don't, so you save a
>> > lot of time on both writing and profiling.
>>
>> Huh? No way. You need (theoretically) to declare just as much in Lisp as
>> you do in ML. Some compilers aren't as good about type inference, and
>> some programmers want to keep their codebase dynamic so they can load
>> fixes into a live system that might change the datatypes involved in
>> some codepaths.
>
> Normaly, when a data type is changed, some side effects are happening
> somewhere in your code. For example, you cannot change the type of an
> important variable from an integer to a string and pretend that nothing
> would happen in you code.
Sometimes I can. I could be dealing with generic operators that will
just adapt to the new types. I change what I need to change and don't
change what I don't need to. Lisp is not ML.
> Your statement is only true for interchanging integers and float of
> different word size, in which I recognise Lisp is more concise than ML.
> But not much better, you can still use different types into one single
> variable in ML:
>
> # type number = Int of int | Float of float | Big of Big_int.big_int;;
> type number = Int of int | Float of float | Big of Big_int.big_int
> # let n = Float 9.4;;
> val n : number = Float 9.4
> # match n with
> | Float n -> print_string "It is a float"
> | Int n -> print_string "It is an integer"
> | Big n -> print_string "It is a big number";;
> => It is a float
> - : unit = ()
But you still can't choose statically, for all architectures which of
them you get your input as. If you choose wrong, you get an incorrect
answer or a slow program. And since word sizes are different on
different processors, you will always be wrong no matter what you choose
in some cases.
Thomas A. Russ
> Rahul Jain ha escrito:
> >
> > Yes, but how do _I_ know when I need to use bignums or not?
>
> You must know, you are a programmer. Even in Lisp you must know the
> type you are using for every variable.
Actually, this is not true in the case of certain distinctions such as
the (arbitrary) one between FIXNUMs and BIGNUMs. Since the point at
which these values roll over from one type to another is
implementation-dependent, it is hardly reasonable to expect that one
need to know in advance exactly which implementation the code is being
run on. And to have to produce different code for each such
implementation.
You should only need to know this if you are trying to do something very
specific where the exact type is important to you.
If all you care about is the more general type of INTEGER or NUMBER,
then it hardly seems convenient to need to declare or even know exactly
which type of number you are getting. If you want to, say, write code
to find equational roots using the Newton method, why do you need to
care whether the equation returns fixnum, bignum, single floats or
double floats?
> In respect to word size, you are right, dynamic ilanguagges allows you
> to write less and more standard code. But the cost of this is that the
> rest of the system may be unsafe if you don't declare things.
Well, safety is always relative. Just because there is compile-time
type safety doesn't help you when there is interactive input. Nor does
it protect you against algorithmic bugs, divide by zero (unless you make
rather heroic assumptions about the cleverness of the type system and
what it can figure out.)
> > > Static inference always produce faster code compared with dynamic
> > > inference, for an equivalent code base.
> >
> > Huh? Dynamic "inference" doesn't make sense in the context of any Lisp
> > system I know of. Are you talking about recompiling the codepath each
> > time it's run with different types... or what?
>
> I meant dynamic languages in comparison with stong ones having static
> inference. Sorry if I was not clear.
Well, if we need to argue generalizations, then how about dynamic
languages always let you write your code faster than statically typed
languages?
Besides, a statically typed language is not always superior in execution
speed. If what you are doing requires type dispatch, the compiler,
especially if it has specially-tweaked mechanisms for this is probably a
lot more efficient than whatever you have to add to your program to get
the same effect and flexibility. (Greenspun's 10th rule, etc.)
> # type number = Int of int | Float of float | Big of Big_int.big_int;;
> type number = Int of int | Float of float | Big of Big_int.big_int
> # let n = Float 9.4;;
> val n : number = Float 9.4
> # match n with
> | Float n -> print_string "It is a float"
> | Int n -> print_string "It is an integer"
> | Big n -> print_string "It is a big number";;
> => It is a float
> - : unit = ()
So why would this sort of construct be any more efficient than a dynamic
dispatch, when the runtime system knows it needs to handle this?
--
Thomas A. Russ, USC/Information Sciences Institute
Jon Harrop
> If you want to, say, write code
> to find equational roots using the Newton method, why do you need to
> care whether the equation returns fixnum, bignum, single floats or
> double floats?
Precision and computational complexity.
> Just because there is compile-time
> type safety doesn't help you when there is interactive input.
No. Look at the OCaml top-level, for example.
> Nor does
> it protect you against algorithmic bugs,
Static type checking facilitates pattern match exhaustiveness checking, for
example.
> Well, if we need to argue generalizations, then how about dynamic
> languages always let you write your code faster than statically typed
> languages?
I see no evidence of that.
> Besides, a statically typed language is not always superior in execution
> speed.
Can you give an example of a program written in a dynamically typed language
for which there is no faster equivalent written in a statically typed
language?
> If what you are doing requires type dispatch, the compiler,
> especially if it has specially-tweaked mechanisms for this is probably a
> lot more efficient than whatever you have to add to your program to get
> the same effect and flexibility. (Greenspun's 10th rule, etc.)
Maybe. Can you give an example?
>> # type number = Int of int | Float of float | Big of Big_int.big_int;;
>> type number = Int of int | Float of float | Big of Big_int.big_int
>> # let n = Float 9.4;;
>> val n : number = Float 9.4
>> # match n with
>> | Float n -> print_string "It is a float"
>> | Int n -> print_string "It is an integer"
>> | Big n -> print_string "It is a big number";;
>> => It is a float
>> - : unit = ()
>
> So why would this sort of construct be any more efficient than a dynamic
> dispatch, when the runtime system knows it needs to handle this?
It is probably less efficient. It is certainly more verbose. Very few ML
programs use a numeric tower, e.g. very few OCaml programs use the numeric
tower provided by the Num module.
Javier
Thomas A. Russ ha escrito:
> "Javier" <jav...@gmail.com> writes:
>
> > Rahul Jain ha escrito:
> > >
> > > Yes, but how do _I_ know when I need to use bignums or not?
> >
> > You must know, you are a programmer. Even in Lisp you must know the
> > type you are using for every variable.
>
> Actually, this is not true in the case of certain distinctions such as
> the (arbitrary) one between FIXNUMs and BIGNUMs.
Yes, but you still need to know what type are you using for most of the
variables. For example you must know that you are using a list, and
cannot trat it as if it were an integer, or you'll get an error.
> > # type number = Int of int | Float of float | Big of Big_int.big_int;;
> > type number = Int of int | Float of float | Big of Big_int.big_int
> > # let n = Float 9.4;;
> > val n : number = Float 9.4
> > # match n with
> > | Float n -> print_string "It is a float"
> > | Int n -> print_string "It is an integer"
> > | Big n -> print_string "It is a big number";;
> > => It is a float
> > - : unit = ()
>
> So why would this sort of construct be any more efficient than a dynamic
> dispatch, when the runtime system knows it needs to handle this?
It is not more efficent, but it is true that you only use dispatch when
you need, while in Lisp the compiler is probably doing it almost all
the time.
CL-USER> (defun sum-to-nums (a b) (+ a b))
SUM-TO-NUMS
CL-USER> (disassemble 'sum-to-nums)
; 11CB50A1: 8B55F4 MOV EDX, [EBP-12] ;
no-arg-parsing entry point
; A4: 8B7DF0 MOV EDI, [EBP-16]
; A7: E894B034EF CALL #x1000140 ;
GENERIC-+
; AC: 7302 JNB L0
; AE: 8BE3 MOV ESP, EBX
; B0: L0: 8D65F8 LEA ESP, [EBP-8]
; B3: F8 CLC
; B4: 8B6DFC MOV EBP, [EBP-4]
; B7: C20400 RET 4
It is doing a call to the generic-+, which I don't have acess to it,
but + outputs this code:
CL-USER> (disassemble '+)
; 106DFB68: .ENTRY +(&REST ARGS) ;
(FUNCTION
; # *)
; B80: 8F45F8 POP DWORD PTR [EBP-8]
; B83: E337 JECXZ L1
; B85: 8D5DE0 LEA EBX, [EBP-32]
; B88: 29CB SUB EBX, ECX
; B8A: 8BE3 MOV ESP, EBX
; B8C: 8BD9 MOV EBX, ECX
; B8E: 83E90C SUB ECX, 12
; B91: 7612 JBE L0
; B93: 57 PUSH EDI
; B94: 56 PUSH ESI
; B95: 8D7C2408 LEA EDI, [ESP+8]
; B99: 8BF5 MOV ESI, EBP
; B9B: 29DE SUB ESI, EBX
; B9D: C1E902 SHR ECX, 2
; BA0: FC CLD
; BA1: F2 REPNE
; BA2: A5 MOVSD
; BA3: 5E POP ESI
; BA4: 5F POP EDI
; BA5: L0: 8BCB MOV ECX, EBX
; BA7: 8955DC MOV [EBP-36], EDX
; BAA: 83F904 CMP ECX, 4
; BAD: 7410 JEQ L2
; BAF: 897DD8 MOV [EBP-40], EDI
; BB2: 83F908 CMP ECX, 8
; BB5: 7408 JEQ L2
; BB7: 8975D4 MOV [EBP-44], ESI
; BBA: EB03 JMP L2
; BBC: L1: 8D65E0 LEA ESP, [EBP-32]
; BBF: L2: 894DF0 MOV [EBP-16], ECX
; BC2: 8B4DF0 MOV ECX, [EBP-16]
; BC5: 8D740CFC LEA ESI, [ESP+ECX-4]
; BC9: BB0B000008 MOV EBX, 134217739
; BCE: E35F JECXZ L7
; BD0: 8D144D00000000 LEA EDX, [ECX*2]
; BD7: 800D2403000804 OR BYTE PTR [#x8000324], 4 ;
unboxed_region
; BDE: 0315D0BB3100 ADD EDX, [#x31BBD0] ;
_boxed_region
; BE4: 3B15D4BB3100 CMP EDX, [#x31BBD4] ;
boxed_region
; BEA: 7607 JBE L3
; BEC: E80F4393EF CALL #x13F00 ;
_alloc_overflow_edx
; BF1: EB12 JMP L4
; BF3: L3: 3315D0BB3100 XOR EDX, [#x31BBD0] ;
_boxed_region
; BF9: 3115D0BB3100 XOR [#x31BBD0], EDX ;
_boxed_region
; BFF: 3315D0BB3100 XOR EDX, [#x31BBD0] ;
_boxed_region
; C05: L4: 8D5203 LEA EDX, [EDX+3]
; C08: C1E902 SHR ECX, 2
; C0B: FD STD
; C0C: 8BDA MOV EBX, EDX
; C0E: EB06 JMP L6
; C10: L5: 83C208 ADD EDX, 8
; C13: 8952F9 MOV [EDX-7], EDX
; C16: L6: AD LODSD
; C17: 8942FD MOV [EDX-3], EAX
; C1A: E2F4 LOOP L5
; C1C: C742010B000008 MOV DWORD PTR [EDX+1], 134217739
; C23: 80352403000804 XOR BYTE PTR [#x8000324], 4 ;
unboxed_region
; C2A: 7403 JEQ L7
; C2C: 0F0B09 BREAK 9 ; pending
interrupt trap
; C2F: L7: 81FB0B000008 CMP EBX, 134217739
; C35: 745A JEQ L14
; C37: 8B4B01 MOV ECX, [EBX+1]
; C3A: 8B53FD MOV EDX, [EBX-3]
; C3D: F6C203 TEST DL, 3
; C40: 740F JEQ L8
; C42: 8BC2 MOV EAX, EDX
; C44: 2407 AND AL, 7
; C46: 3C07 CMP AL, 7
; C48: 753A JNE L13
; C4A: 8A42F9 MOV AL, [EDX-7]
; C4D: 3C22 CMP AL, 34
; C4F: 7733 JNBE L13
; C51: L8: EB1F JMP L11
; C53: L9: 8BC1 MOV EAX, ECX
; C55: 2407 AND AL, 7
; C57: 3C03 CMP AL, 3
; C59: 753D JNE L15
; C5B: 8BC1 MOV EAX, ECX
; C5D: 8B4001 MOV EAX, [EAX+1]
; C60: 8945F4 MOV [EBP-12], EAX
; C63: 8B79FD MOV EDI, [ECX-3]
; C66: E8D50492F0 CALL #x1000140 ;
GENERIC-+
; C6B: 7302 JNB L10
; C6D: 8BE3 MOV ESP, EBX
; C6F: L10: 8B4DF4 MOV ECX, [EBP-12]
; C72: L11: 81F90B000008 CMP ECX, 134217739
; C78: 75D9 JNE L9
; C7A: L12: 8D65F8 LEA ESP, [EBP-8]
; C7D: F8 CLC
; C7E: 8B6DFC MOV EBP, [EBP-4]
; C81: C20400 RET 4
; C84: L13: 8B0560FB6D10 MOV EAX, [#x106DFB60] ; 'NUMBER
; C8A: 0F0B0A BREAK 10 ; error
trap
; C8D: 03 BYTE #X03
; C8E: 1F BYTE #X1F ;
OBJECT-NOT-TYPE-ERROR
; C8F: 8E BYTE #X8E ; EDX
; C90: 0E BYTE #X0E ; EAX
; C91: L14: 31D2 XOR EDX, EDX
; C93: EBE5 JMP L12
; C95: 90 NOP
; C96: 90 NOP
; C97: 90 NOP
; C98: L15: 0F0B0A BREAK 10 ; error
trap
; C9B: 02 BYTE #X02
; C9C: 02 BYTE #X02 ;
OBJECT-NOT-LIST-ERROR
; C9D: 4E BYTE #X4E ; ECX
;
NIL
which I think is the code to decompose &rest, and then call the
generic-+ function (which would contain even more code). This is not
very much efficent.
Of course, you can declare sum-to-nums to just sum integers, but then,
what is the benefit of using a dynamic language?
Javier
> > In respect to word size, you are right, dynamic ilanguagges allows you
> > to write less and more standard code. But the cost of this is that the
> > rest of the system may be unsafe if you don't declare things.
>
> Well, safety is always relative. Just because there is compile-time
> type safety doesn't help you when there is interactive input. Nor does
> it protect you against algorithmic bugs, divide by zero (unless you make
> rather heroic assumptions about the cleverness of the type system and
> what it can figure out.)
I'll put here an example:
(defun sum-list (lst)
(cond
((null lst) nil)
(t (+ (car lst) (sum-list (cdr lst))))))
This compiles on SBCL without give up a single warning. But if you try
to exec it:
CL-USER> (sum-list (list 1 2 3))
=> Error Argument Y is not a NUMBER: NIL
[Condition of type SIMPLE-TYPE-ERROR]
If you try to write the same function on ML:
# let rec sum_list lst =
match lst with
[]->[]
| h::t -> h + (sum_list t);;
Characters 67-83:
| h::t -> h + (sum_list t);;
^^^^^^^^^^^^^^^^
=> This expression has type int but is here used with type 'a list
The compiler inmediatly gives you an error and do not let you to
compile and use it.
This error may be self evident as it is very simple. But imagine the
same kind of error on a big system, or in a function which is 100 lines
long with several conditions. On Lisp, your application may run fine
for ages until some day the bug appear. Just imagine what would happen
If the life of people depends on this kind of application (for example
for controlling train or flight traffics), or if it is used to manage
bank accounts...
Stefan Nobis
> This error may be self evident as it is very simple.
Yes.
> But imagine the same kind of error on a big system, or in a function
> which is 100 lines long with several conditions.
That's what Thomas tried to say: In these cases there are so many ways
to put errors in your code of which only (very) few can be caught be a
static type system. So you have to do something about the other types
of errors anyway and you can't rely only on your static type system.
In fact the difference is not very big (in Lisp you have to do a
little bit more to also catch type errors but the hard work are test
cases or the like for all the other bugs) but on the other hand Lisp
is much more flexible and fun -- so why bother with static type
systems. :)
--
Stefan.
Javier
Stefan Nobis ha escrito:
> "Javier" <jav...@gmail.com> writes:
>
> > This error may be self evident as it is very simple.
>
> Yes.
>
> > But imagine the same kind of error on a big system, or in a function
> > which is 100 lines long with several conditions.
>
> That's what Thomas tried to say: In these cases there are so many ways
> to put errors in your code of which only (very) few can be caught be a
> static type system. So you have to do something about the other types
> of errors anyway and you can't rely only on your static type system.
In fact it is not only the type system. :)
For example, in ML the null keyword does not exist, and so nothing
equivalent. Everything must have a correct value. The combination of
static type checking and not null arithmetic becomes to a safer system.
Your application may present incorrect solutions to the problems, but
at least it is going to get running in most cases.
> In fact the difference is not very big (in Lisp you have to do a
> little bit more to also catch type errors but the hard work are test
> cases or the like for all the other bugs) but on the other hand Lisp
> is much more flexible and fun -- so why bother with static type
> systems. :)
Sure, there is probably more fun on Lisp (this is just a personal
taste).
I would like a mixture of both worlds. For example, I'd like Lisp to be
strong in most cases (for example, to not allow to mix integers and
lists), but still tolerant with compatible ones (for example, to mix
bignums and integers). As far as I know, this doesn't exist at the
moment.
Jon Harrop
> That's what Thomas tried to say: In these cases there are so many ways
> to put errors in your code of which only (very) few can be caught be a
> static type system.
In my experience, the vast majority are caught by the static type system.
This is really what the static vs dynamic debate boils down to: a
difference in belief.
> Lisp is much more flexible and fun
What makes Lisp more flexible and fun compared to OCaml?
Pascal Costanza
> Stefan Nobis wrote:
>> That's what Thomas tried to say: In these cases there are so many ways
>> to put errors in your code of which only (very) few can be caught be a
>> static type system.
>
> In my experience, the vast majority are caught by the static type system.
How do you know that? Do you write all your programs both in
dynamically- and statically-typed languages, and keep a log of how many
errors have been caught in which way?
> This is really what the static vs dynamic debate boils down to: a
> difference in belief.
So what is it? Experience or belief?
Jon Harrop
> Jon Harrop wrote:
>> Stefan Nobis wrote:
>>> That's what Thomas tried to say: In these cases there are so many ways
>>> to put errors in your code of which only (very) few can be caught be a
>>> static type system.
>>
>> In my experience, the vast majority are caught by the static type system.
>
> How do you know that? Do you write all your programs both in
> dynamically- and statically-typed languages, and keep a log of how many
> errors have been caught in which way?
When I moved from dynamically typed languages to statically typed ones, I
noticed the compiler picking up lots of errors that I would have had to
debug at runtime (and hope that I happened to stumble upon them before
selling the software).
>> This is really what the static vs dynamic debate boils down to: a
>> difference in belief.
>
> So what is it? Experience or belief?
Both I guess. In my experience, this is quite task specific. Certain tasks
(e.g. GUI work) are quite dynamic by nature, so static typing is less
useful and dynamic typing is likely to be more concise.
Ken Tilton
Jon Harrop wrote:
> Pascal Costanza wrote:
>
>>Jon Harrop wrote:
>>
>>>Stefan Nobis wrote:
>>>
>>>>That's what Thomas tried to say: In these cases there are so many ways
>>>>to put errors in your code of which only (very) few can be caught be a
>>>>static type system.
>>>
>>>In my experience, the vast majority are caught by the static type system.
>>
>>How do you know that? Do you write all your programs both in
>>dynamically- and statically-typed languages, and keep a log of how many
>>errors have been caught in which way?
>
>
> When I moved from dynamically typed languages to statically typed ones, I
> noticed the compiler picking up lots of errors that I would have had to
> debug at runtime
Unresponsive! Of /course/ C++ (for example) nags you to death at
compile-time, of /course/ CL frequently has to tell me '+ does not know
what do with "your mama!"'. We knooooooowwwwww /that/.
The question is specifically about bugs that make it into production. Of
those that do in a Lisp app, how many would have been caught by a
C++-like compiler. And vice versa: how often do C++ apps fail /because
of/ type rigidity (see "Ariane 5"). And then we can look at trade-offs,
bugs caught-not-caught vs cost of development, and consider how Lisp's
overall lower cost of development leaves more $$$ for testing, and how
Lisp's superior reflectivity makes possible better testing.
Now I concede that that would be a terribly difficult research
undertaking, so it is probably easier to find a really good programmer
and just ask them which language is better.
Hi. I am Kenny. Lisp is better.
I did enjoy having C++ slap me around when I ported Cells to C++, such
that by the time I got a clean compile the thing worked, so I see the
advantage. But that was porting something, not inventing/discovering it.
The "discovering" is important. I simply would not have stumbled onto
Cells (and stumble I did) in anything other than Lisp. And that is why
Lisp is better.
hth, kt
--
Cells: http://common-lisp.net/project/cells/
"I'll say I'm losing my grip, and it feels terrific."
-- Smiling husband to scowling wife, New Yorker cartoon
jayessay
> production. Of those that do in a Lisp app, how many would have been
> caught by a C++-like compiler.
Or even *ML compilers. IME, such logic bugs are not caught at all by
type systems. The two are orthogonal.
> And vice versa: how often do C++ apps fail /because of/ type
> rigidity (see "Ariane 5").
I agree with your basic position, but this is a category error in a
couple ways...
BTW: How 'bout those Yankees? <cough cough - choke> ;-)
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
Javier
Thomas A. Russ ha escrito:
> > In respect to word size, you are right, dynamic ilanguagges allows you
> > to write less and more standard code. But the cost of this is that the
> > rest of the system may be unsafe if you don't declare things.
>
> Well, safety is always relative. Just because there is compile-time
> type safety doesn't help you when there is interactive input. Nor does
> it protect you against algorithmic bugs, divide by zero (unless you make
> rather heroic assumptions about the cleverness of the type system and
> what it can figure out.)
I'll put here an example:
(defun sum-list (lst)
(cond
((null lst) nil)
(t (+ (car lst) (sum-list (cdr lst))))))
This compiles on SBCL without give up a single warning. But if you try
to exec it:
CL-USER> (sum-list (list 1 2 3))
=> Error Argument Y is not a NUMBER: NIL
[Condition of type SIMPLE-TYPE-ERROR]
If you try to write the same function on ML:
# let rec sum_list lst =
match lst with
[]->[]
| h::t -> h + (sum_list t);;
Characters 67-83:
| h::t -> h + (sum_list t);;
^^^^^^^^^^^^^^^^
=> This expression has type int but is here used with type 'a list
The compiler inmediatly gives you an error and do not let you to
compile and use it.
This error may be self evident as it is very simple. But imagine the
same kind of error on a big system, or in a function which is 100 lines
Jon Harrop
> Jon Harrop wrote:
>> When I moved from dynamically typed languages to statically typed ones, I
>> noticed the compiler picking up lots of errors that I would have had to
>> debug at runtime
>
> Unresponsive! Of /course/ C++ (for example) nags you to death at
> compile-time, of /course/ CL frequently has to tell me '+ does not know
> what do with "your mama!"'. We knooooooowwwwww /that/.
>
> The question is specifically about bugs that make it into production. Of
> those that do in a Lisp app, how many would have been caught by a
Sure. The same is probably true of Lisp vs Java but that has nothing to do
with dynamic vs static typing.
Ken Tilton
jayessay wrote:
> Ken Tilton <kent...@gmail.com> writes:
>
>
>>production. Of those that do in a Lisp app, how many would have been
>>caught by a C++-like compiler.
>
>
> Or even *ML compilers. IME, such logic bugs are not caught at all by
> type systems. The two are orthogonal.
>
>
>>And vice versa: how often do C++ apps fail /because of/ type
>>rigidity (see "Ariane 5").
>
>
> I agree with your basic position, but this is a category error in a
> couple ways...
>
>
> BTW: How 'bout those Yankees? <cough cough - choke> ;-)
Go Mets! Go Giants!
Anybody know a few pitchers George can buy? You can take A-Rod...please!
Rahul Jain
> I'll put here an example:
>
> (defun sum-list (lst)
> (cond
> ((null lst) nil)
> (t (+ (car lst) (sum-list (cdr lst))))))
>
> This compiles on SBCL without give up a single warning.
If you actually asked it to, it would.
Stefan Nobis
> I'll put here an example:
That's not the point. Yes, in trivial examples there are quite some
bugs a static type system does help with.
But in non-trivial applications the (static) type system is not
enough, you need more tools (like unit/regression tests) to
find/eleminate all bugs. So if you are writing excessive tests anyway,
such simple type errors would be caught and your static type systems
buys you (nearly) nothing... or at least the advantages in this area
are much small than your example would suggest and the disadvantages
of the static type system possibly become more weighty.
--
Stefan.
Alan Crowe
> Thomas A. Russ ha escrito:
>
> > > In respect to word size, you are right, dynamic ilanguagges allows you
> > > to write less and more standard code. But the cost of this is that the
> > > rest of the system may be unsafe if you don't declare things.
> >
> > Well, safety is always relative. Just because there is compile-time
> > type safety doesn't help you when there is interactive input. Nor does
> > it protect you against algorithmic bugs, divide by zero (unless you make
> > rather heroic assumptions about the cleverness of the type system and
> > what it can figure out.)
>
> I'll put here an example:
>
> (defun sum-list (lst)
> (cond
> ((null lst) nil)
> (t (+ (car lst) (sum-list (cdr lst))))))
>
Imagine that the compiler spots this and you rush to fix it
as the telephone rings.
(defun sum-list (list)
(cond
((null list) 1)
(t (+ (car list)(sum-list (cdr list))))))
After the phone call you compile it; since it passes the
static type checks you press on to the next piece of code.
Have you won or lost? Why?
I've been working on some code so that I can do
CL-USER> (defun sum-list (lst)
(declare (test (((5 7)) 12)))
(cond
((null lst) nil)
(t (+ (car lst) (sum-list (cdr lst))))))
arglist = ((5 7)), required result = 12, actual result NIL.
((NESTUIT::UNEXPECTED-SIGNAL #<SIMPLE-TYPE-ERROR {481F15ED}>))
0.00% passed.
SUM-LIST
CL-USER> (defun sum-list (lst)
(declare (test (((5 7)) 12)))
(cond
((null lst) 1)
(t (+ (car lst) (sum-list (cdr lst))))))
arglist = ((5 7)), required result = 12, actual result 13.
((NESTUIT::WRONG-ANSWER :EXPECTED 12 :RECEIVED 13))
0.00% passed.
SUM-LIST
CL-USER> (defun sum-list (lst)
(declare (test (((5 7)) 12)))
(cond
((null lst) 0)
(t (+ (car lst) (sum-list (cdr lst))))))
arglist = ((5 7)), required result = 12, actual result 12.
All passed.
SUM-LIST
It shadows defun, uses the declaration declaration to tell
CL about TEST, and uses eval-when to get the declared tests
run a compile time.
The code is online at
http://www.cawtech.demon.co.uk/nestuit/current.lisp
so that you can see that I really have conforming code that
does this, but I've been tinkering and it is in a mess with
bits broken, and I've got three bits of documentation, all
obselete, all disagreeing.
If I press on with this, will I really use it, will I find
it worthwhile?
I don't think it is possible to think clearly about this
issue if you use the word "correct" for code that passes the
static type checks. I propose "typeck" as a neologism for
code that passes the static type checks. You need a
vocabularly that permits you to say that
(defun sum-list (list)
(cond
((null list) 1)
(t (+ (car list)(sum-list (cdr list))))))
is typeck but incorrect.
If you are stuck with a terminology that forces you to say
that it is correct but incorrect, you will just get in a
muddle.
Alan Crowe
Edinburgh
Scotland
Raffael Cavallaro
> I propose "typeck" as a neologism for
> code that passes the static type checks. You need a
> vocabularly that permits you to say that
>
> (defun sum-list (list)
> (cond
> ((null list) 1)
> (t (+ (car list)(sum-list (cdr list))))))
>
> is typeck but incorrect.
I think that "type correct" is a usage I've seen before and says what
you mean maybe a little more clearly than a neologism.
>
> If you are stuck with a terminology that forces you to say
> that it is correct but incorrect, you will just get in a
> muddle.
I am very much in agreement with you here. Maybe we need to distinguish
between "type correct" on the one hand and "logically correct," or
"algorithmically incorrect" on the other. Then we can point at programs
which are "type correct" but "algorithmically incorrect."
Thomas A. Russ
> I'll put here an example:
>
> (defun sum-list (lst)
> (cond
> ((null lst) nil)
> (t (+ (car lst) (sum-list (cdr lst))))))
>
> This compiles on SBCL without give up a single warning. But if you try
> to exec it:
>
> CL-USER> (sum-list (list 1 2 3))
> => Error Argument Y is not a NUMBER: NIL
> [Condition of type SIMPLE-TYPE-ERROR]
Well, it looks like Common Lisp found the error pretty quickly.
> If you try to write the same function on ML:
>
> # let rec sum_list lst =
> match lst with
> []->[]
> | h::t -> h + (sum_list t);;
> Characters 67-83:
> | h::t -> h + (sum_list t);;
> ^^^^^^^^^^^^^^^^
> => This expression has type int but is here used with type 'a list
>
> The compiler inmediatly gives you an error and do not let you to
> compile and use it.
So in this example, the only claim is really that ML flags the error at
compile time, whereas Common Lisp flags it at run time. Now, perhaps if
one were using a language without dynamic function redefinition and
linking, there might be some large advantage to having such a detection
at compile time.
After all, if you have to go through a long edit-compile-link cycle,
then you really do need to have lots of errors caught at compile time,
since it is more efficient than finding them at run time.
In Common Lisp, though, you can very easily work on small pieces of the
code, so after finding the error in the SUM-LIST function, one just
needs to correct that function, re-compile just the function (and every
reasonable lisp development environment such as the commercial IDEs,
Slime, iLisp, etc. supports this nicely in the editor buffer) and
proceed with the testing.
In fact, with the standard debugger support, you can even recompile the
function and continue out of the error case without having to restart
the entire system.
Consider the following example interaction (ACL 5.0):
USER> (defun sum-list (lst)
(cond ((null lst) nil)
(t (+ (car lst) (sum-list (cdr lst))))))
SUM-LIST
USER> (defun test (sample-lists)
(dolist (sample sample-lists)
(format t "Sum of ~S = ~S~%" sample (sum-list sample))))
TEST
;; Run a test:
USER> (test '((1 1 1) (2 2 2) (1 2 3 4) (3 4 5)))
Error: `NIL' is not of the expected type `NUMBER'
[condition type: TYPE-ERROR]
Restart actions (select using :continue):
0: Return to Top Level (an "abort" restart)
1: Abort #<PROCESS Initial Lisp Listener>
;; Look at where the error occurs. It is in this expression.
[1] USER> :frame
Expression: (+ 1 NIL)
;; Find and fix bug in the code, adopting the convention that
;; the sum of the empty list is zero. Matches semantics of the
;; built-in + function.
;; Redefine code here at run-time. (In real operation done in
;; source through IDE, but it works the same way)
[1] USER> (defun sum-list (lst)
(cond ((null lst) 0)
(t (+ (car lst) (sum-list (cdr lst))))))
SUM-LIST
;; Continue from the error. Since the error frame was (+ 1 NIL)
;; at this point we substitute the proper value for NIL and have
;; our function return (+ 1 0) while still on the call stack in
;; the debugger. Note that we only have to do this once, since
;; subsequent iterations in the test loop know use the redefined
;; SUM-LIST function, through the magic of dynamic linking.
[1] USER> :return (+ 1 0)
Sum of (1 1 1) = 3
Sum of (2 2 2) = 6
Sum of (1 2 3 4) = 10
Sum of (3 4 5) = 12
NIL
USER>
The point of this is to show that there isn't really any big savings in
finding this sort of error at compile time. The workflow is a bit
different in Common Lisp, since the overhead of editting, compiling and
linking is very low. For compiling and linking single functions, it is
virtually non-existent, so it doesn't matter much that the error is
detected at run-time rather than compile-time.
Thomas A. Russ
> I'll put here an example:
>
> (defun sum-list (lst)
> (cond
> ((null lst) nil)
> (t (+ (car lst) (sum-list (cdr lst))))))
>
> This compiles on SBCL without give up a single warning. But if you try
> to exec it:
>
> CL-USER> (sum-list (list 1 2 3))
> => Error Argument Y is not a NUMBER: NIL
> [Condition of type SIMPLE-TYPE-ERROR]
>
> If you try to write the same function on ML:
>
> # let rec sum_list lst =
> match lst with
> []->[]
> | h::t -> h + (sum_list t);;
> Characters 67-83:
> | h::t -> h + (sum_list t);;
> ^^^^^^^^^^^^^^^^
> => This expression has type int but is here used with type 'a list
>
> The compiler inmediatly gives you an error and do not let you to
> compile and use it.
OK, I must admit that I'm not really up on ML, but does the ML
equivalent of the following slightly modified version of SUM-LIST
compile properly, or does it give an error as well:
(defun sum-list (lst)
(cond ((null lst) nil)
((null (cdr lst)) (car lst))
(t (+ (car lst) (sum-list (cdr lst))))))
(sum-list '(1 2 3)) => 6
(sum-list '(2)) => 2
(sum-list '()) => NIL
Joel Reymont
How do you do this in SLIME?
Thanks, Joel
Javier
Alan Crowe ha escrito:
> I've been working on some code so that I can do
> The code is online at
>
> http://www.cawtech.demon.co.uk/nestuit/current.lisp
This is very nice, thanks for the code.
> I don't think it is possible to think clearly about this
> issue if you use the word "correct" for code that passes the
> static type checks. I propose "typeck" as a neologism for
> code that passes the static type checks. You need a
> vocabularly that permits you to say that
>
> (defun sum-list (list)
> (cond
> ((null list) 1)
> (t (+ (car list)(sum-list (cdr list))))))
>
> is typeck but incorrect.
Yes, you are right. But if you eliminate both null exceptions and type
errors, I think that you are probably going to avoid at least 50% of
the bugs.
Your test system can really help to avoid all of this kind of error.
Rahul Jain
> What I always wanted to know:
>
> How do you do this in SLIME?
I see a command caled sldb-return-from-frame here.
Javier
> equivalent of the following slightly modified version of SUM-LIST
> compile properly, or does it give an error as well:
>
> (defun sum-list (lst)
> (cond ((null lst) nil)
> ((null (cdr lst)) (car lst))
> (t (+ (car lst) (sum-list (cdr lst))))))
>
>
> (sum-list '(1 2 3)) => 6
> (sum-list '(2)) => 2
> (sum-list '()) => NIL
No, it doesn't if you translate expresion by expresion, because you are
still mixing lists with integers.
But, if you want something similar, you can use type variants:
type lisp_value = Nil | Number of int
# let rec sum_list lst = match lst with
| [] -> 0
| h::t -> match h with
Nil -> sum_list t
| Number n -> n + (sum_list t)
=> val sum_list : lisp_value list -> int = <fun>
# sum_list [Number 6; Number 3; Nil; Number 9];;
=> - : int = 18
But on ML, Nil has nosense. It is never possible to accidentally mix
something with a null value, just because a null value does not exists.
Elsewhere, you can simulate null like the example above if you wish.
Raffael Cavallaro
<raffaelcavallaro@pas-d'espam-s'il-vous-plait-mac.com> said:
> Maybe we need to distinguish between "type correct" on the one hand and
> "logically correct," or "algorithmically incorrect" on the other.
That "incorrect" should be "correct" of course.