Re: RAD vs. performance

Robbert Haarman wrote:
Of course, there are counterarguments as well: static typing as a
measure of correctness is both an overapproximation and an
underapproximation. Just because the type checker accepts a program
doesn't mean it's correct,

Very true. However, it is not uncommon to write thousands of lines of ML
code and, as soon as it passes the type checker, have it work properly
first time. No need to waste your time unit testing...

and type checkers will also make it
impossible to write programs that would have worked flawlessly in the
absence of static typing (of course, these programs aren't _correct_,
because they violate the typing rules).

Your statement is a little vague. You can write any program in a statically
typed language, but not necessarily in the same way that you could in a
dynamically typed language. Polymorphic recursion is the obvious example.
However, these situations are rare in practice.

(* Suppose that foo and bar are instances of two different classes,
but both support the print method. *)
let rec print_all xs = match xs with
[] -> ()
| x::xs -> x#print; print_newline (); print_all xs
in
print_all [foo; bar];;

Most type checkers will reject this program, because they won't allow
you to put objects of different types in a single list. However, under
dynamic typing, this program would have worked fine.

The print_all function already works in OCaml:

# let rec print_all foo bar xs = match xs with
[] -> ()
| x::xs -> x#print; print_newline (); print_all foo bar xs;;
val print_all : 'a -> 'b -> < print : 'c; .. > list -> unit = <fun>

So you need to pass it a "< print : 'c; .. > list".

Yet CLs performance is far worse than that of most modern,
statically-typed languages (e.g. MLs). Putting more effort into
optimisation is no substitute for designing a language that will run
fast.

What is "far worse"? According to the Shootout, the difference in speed
between the fastest open source Common Lisp implementation and the
fastest C compiler is about a factor 2 (or so it was last I checked). Is
that a lot? Java is statically typed, but most Java implementations
score a lot worse. On the other hand, a lot of effort and money has been
put into optimizing the C compilers and Java implementations at the top
of the ranking. Maybe optimization matters more than you think. Of
course, the Shootout allows everyone to see what they want to see.

Then don't use the shootout.

All languages have adjustable typing and execution. AFAIK, it is
prohibitively difficult to reap the rewards of static typing
(particularly performance) with an implementation within Lisp.
Consequently, I suspect such things are also an academic curiosity.

I don't see why getting could performance out of a Lisp program with
type declarations should be a problem.

If I write, in Ocaml:

let rec fac_rec n r =
if n <= 1 then r
else fac_rec (n - 1) (n * r);;

The compiler will infer that n and r are integers, and fac_rec returns
an integer.

If I write, in Common Lisp:

(declaim (ftype (function (fixnum fixnum) fixnum) fac-rec))
(defun fac-rec (n r)
(if (<= 1 n) r (fac-rec (- n 1) (* n r))))

The compiler will have the exact same type information. Why wouldn't it
be able to generate code that was just as fast?

For non-trivial examples, Lisp certainly seems to be a lot slower (e.g.
2x). I'm not sure why. Slow GC was one reason that came up.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/ocaml_for_scientists/chapter1.html
.

Relevant Pages

  • Re: More static type fun.
    ... >> Lisp is very hard to type. ... Is "foo" a valid value of type foo? ... So a static type checker for the CL-native type system would either ...
    (comp.lang.lisp)
  • Re: RAD vs. performance
    ... code and, as soon as it passes the type checker, have it work properly ... implementations of various programming languages on various benchmarks, ... discussing whether or not the Shootout is good as it is to be put into ... and Lisp implementers don't spend their efforts optimizing ...
    (comp.lang.misc)
  • Re: Id spend a week evaluating, but I would rather waste your time: LW vs. ACL Prolog vs Norvig vs?
    ... The idea of Qi was that people could borrow or use it for their Lisp ... In your app you could use the Qi Prolog to generate the bits of Lisp ... challenges for the type checker which I posted in an unanswered post on ... But generally Qi/tk will allow dependencies and the type ...
    (comp.lang.lisp)
  • Re: Python from Wise Guys Viewpoint
    ... In a language such as Haskell, there are no constructs that 'would run ... In Lisp too, there are no programs that 'would run correctly' after ... failing type-checking, because a type checker for Lisp would have to ...
    (comp.lang.lisp)
  • Re: Python from Wise Guys Viewpoint
    ... In a language such as Haskell, there are no constructs that 'would run ... In Lisp too, there are no programs that 'would run correctly' after ... failing type-checking, because a type checker for Lisp would have to ...
    (comp.lang.python)