Re: RAD vs. performance

Robbert Haarman wrote:
On Wed, Jun 28, 2006 at 09:39:59AM -0700, Dr Jon D Harrop wrote:
And they can do better than claiming that 1*2^36 + 1 = 1*2^36.

Again, this is a tradeoff so there is no clear notion of "better".

I submit that "better" is tricky to define in general, but I regard 1 /
3 = 0 and 1*2^36 + 1 = 1*2^36 as _incorrect_, and 1 / 3 = 1/3 and
1*2^36 + 1 = 68719476737 as correct. It seems indisputable to me that
getting correct answers is better than getting incorrect ones.

You are implying that Euclidean quotient and modulo arithmetic are
"incorrect". Provided we state up front that "a div b" denotes the
former and "a*b" is done in the latter, I am happy. Particularly given
that these operations are supported in hardware and run vastly faster.

On the contrary. This is the heart of the issue. You keep claiming that
type inference can't be done both efficiently and effectively in dynamic
languages; my statement asserts that it can be done using the exact same
methods that are used for statically typed languages, with the same
efficiency, and the same effectiveness.

Then you're implementing static typing.

In a sense. It's an optimization, where you try to shift the as much
type checking work to compile time as possible. In this sense, it's like
static typing. However, there is one important difference: if you cannot
determine a valid typing at compile time, you generate run time type
checks. This preserves the semantics of dynamic typing, and differs from
static typing, where you would reject the program.

Ok. Do you have access to the inferred types, as you do in OCaml? If
so, what type would be inferred for, say, a polymorphically recursive
function.

No, I am saying that you have incorrectly assumed that OCaml can't
infer more because it is not "smart" enough. In fact, OCaml can infer
more but chooses not to because it weakens the type system and allows
significantly more bugs to creep in. You can control the amount of
inference in OCaml and good OCaml programmers deliberately choose not
to infer everything because it slows development and makes for less
reliable software.

Perhaps you could give some example code to clarify things.

Sure. Consider this OCaml function:

let rec f x = x, f;;

Although it is a perfectly "valid" function, the ordinary OCaml type
checker rejects this function because its type lies outside the type
system:

# let rec f x = x, f;;
This expression has type 'a * ('a -> 'a * 'b) but is here used with
type
'a * 'b

However, the OCaml type system can be extended using a simple
command-line argument to allow "recursive types". This function then
type checks:

$ ocaml -rectypes
....
# let rec f x = x, f;;
val f : 'b -> 'b * 'a as 'a = <fun>

Although it may seem that the -rectypes is great because it extends the
type system to allow a wider variety of functions to pass type
checking, this option is rarely used in practice because the functions
that it allows to pass are usually wrong (i.e. not what the programmer
intended).

Avoiding -rectypes, the above function can be altered to pass the type
checker. For example, by boxing the function result in a polymorphic
variant type constructor:

# let rec f x = x, `F f;;
val f : 'b -> 'b * [> `F of 'a ] as 'a = <fun>

So, it is not always "smart" to make a more powerful type system in
order to allow more programs to pass type checking. On the contrary, it
can be smart to shrink the set of functions that pass type checking
when the rejected functions are wrong.

Even if you litter the source with type declarations to evade that
problem, SBCL and CMUCL still produce much slower code. IIRC, a slow GC
was a major reason but even with lots more code to alleviate the GC,
Lisp was still much slower than the statically-typed languages and
Stalin-compiled Scheme.

There are other issues at work as well. Common Lisp allows you to
redefine functions at run time, even built-in functions. This could be a
source of slowdowns. There could also be implementation issues. You
already mentioned the slow GC; it could also be that SBCL and CMUCL
unnecessarily box the floats you're using (you are using floats,
right?). Finally, note that CMUCL and SBCL treat type declarations as
assertions by default, which means that simply declaring types does
_not_ eliminate run time checks.

There were discussions by many people, including some of the compiler
authors, about the various reasons for Lisp's poor performance.
Versions of SBCL released since the ray tracer are much better.

You think that someone can write a Scheme compiler that generates code
that is almost as efficient whilst taking a reasonable time to compile?

I am not sure. Scheme has various features that could make it hard to
compile to efficient code; call/cc, assignments and being allowed to
redefine procedures at runtime being some of them. However, I _am_ sure
that it is possible to invent dynamically typed languages that compile
to efficient code in reasonable time.

From your definition, you could alter an ML compiler to emit type
warnings rather than errors and call it dynamically typed. However, I'm
not sure what happens to the inferred types when a type "warning" is
emitted - the remaining types will be wrong.

Yes, of the one's I've tried, they're all much slower than g++,
ocamlopt, MLton...

I believe you. However, it still proves only that the programs you
benchmarked were slow on the implementations you benchmarked. You jump
from there to conclusions, but that doesn't mean your conclusions are
right.

Of course, I only have finite information. However, _all_ of that
information points in one direction. What am I to think?

Note that the problem of implementing dynamic typing in a statically typed
language like OCaml is solved but the problem of compiling away unnecessary
run-time checks in Lisp/Scheme/Perl/Python/Ruby to get competitive
performance is unsolved without sacrificing compile-time.

Nothing ever comes for free. You _can't_ determine where you need or
don't need run-time checks without analysing the program.

You can't determine all of the places where you don't need run-time
checks by analysing the program.

Not in general, indeed. What is the point you're trying to make here?

Surely it is more practical to use static typing.

Dynamic typing is not "higher level". It is a special case of static
typing.

Dynamic typing is a fundamentally different approach to typing. Dynamic
typing detects type errors at run time, static typing detects type
errors at compile time.

For two different definitions of "type", yes. Static type systems have
a deliberately constrained notion of types. That doesn't mean that you
can't implement functions that don't type. So I don't think the
difference is "fundamental". Indeed, I don't even think the difference
is clear any more. Statically typed languages often emit lots of
run-time checks (e.g. Java) and dynamically typed languages often
perform lots of static checks (e.g. SBCL).

The reason I said dynamic typing is higher level is that, in those cases
where types aren't decided at compile time, the compiler will generate
run time type checks for you, whereas, in static typing, you would have
to write these checks yourself (as you did in the command1, command2
example). Perhaps I abused the terminology.

That is certainly true to an extent. However, OOP, pattern matching,
polymorphism etc. all blur this. For example:

# let is_empty = function [] -> true;;
Warning P: this pattern-matching is not exhaustive.
Here is an example of a value that is not matched:
_::_
val is_empty : 'a list -> bool = <fun>

The OCaml compiler emitted a warning that the pattern match did not
account for all eventualities and, consequently, had to insert a
run-time check. That was based on its knowledge of the type 'a list. Is
it a type check? Is it dynamic?

You can argue for a more powerful type system. I'd like type classes
and performance...

Meaning? You get to put values that support a common interface in a
container, and you can then apply functions from this interface to the
values without run time dispatch?

Yes.

Finally we can agree on something. ;-)

I think we agree on several things. Just not on what dynamic typing is
and whether it does or doesn't necessarily degrade run time or compile
time performance.

Dynamically typed languages certainly have a reputation for being slow.
Do you think that is wrong?

Objectively, can you write a dynamically typed implementation of my ray
tracer benchmark that beats ocamlopt/g++ in terms of run-time and
compile-time performance? I'd have thought it would be easy given that
the program is self-contained (i.e. you can't help but do whole-program
analysis) and, yet, none of the dynamically typed languages come close.

Cheers,
Jon.

.

Relevant Pages

  • Re: Obstacles for Tcl/Tk commercial application development ?
    ... I'm hoping readers are smart enough to be able to generalize to complex systems they've worked on and see that static typing doesn't mean you have no type-induced errors in your code. ... Show me how to write that in the language *you* like, in a way that makes it impossible to forget to update the "distance" function when you add a third dimension. ... how does the strong typing find at compile time the fact that this is wrong? ...
    (comp.lang.tcl)
  • Re: RAD vs. performance
    ... All of the implementations are either slow to compile ... exactly the same for a dynamically typed language as it is for Ocaml? ... Then you're implementing static typing. ... course, I think you must), then it follows that dynamic typing does NOT ...
    (comp.lang.misc)
  • Why I dont believe in static typing
    ... relative merits of static versus dynamic typing I thought I'd spoil it all ... delivered by an ad server, which was already up and running. ... to part of the system, compile it, and the compiler errors would point you ... The introduction of credit card billing ...
    (comp.lang.lisp)
  • Re: Whats the best language to learn...
    ... Debugging is much faster when errors are caught at compile time by a static ... with generic typing and unspecific typing more efficiently than with ... do after you finished programming. ... and there's no reason to force me to specify ...
    (comp.programming)
  • Re: Which programming language is better to start
    ... >>> It may happen that some features in LISP render slower implementations ... >> work is done at compile time. ... >> In that kind of situations, static typing gets in the programmer's way ...
    (comp.programming)