Re: RAD vs. performance

On Wed, Jun 28, 2006 at 09:39:59AM -0700, Dr Jon D Harrop wrote:
Robbert Haarman wrote:
On Wed, Jun 28, 2006 at 12:08:12PM +0100, Jon Harrop wrote:
We do not live in an ideal world. Computers cannot do infinite-precision
arithmetic.

Indeed. But they can do better than 31-bit arithmetic.

No, they can't. They can do differently. 64-bit arithmetic is not
inherently "better".

They can also do better than claiming 1 / 3 = 0.

Again, they can't. They can offer different semantics but none of them
will be equivalent to mathematics.

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 aware that the Perl community, everybody who writes Scheme
compilers, all these folks working on compilers for Python and Ruby,
etc. etc. are working on getting decent performance out of dynamically
typed languages, are you?

Yes but look at the results.

I did just refute your claim that "virtually nobody does this".

No, you didn't. All of the implementations are either slow to compile
or produce slow code. Sure, "people are working on it" but they're a
long way off.

I seem to have mistaken your meaning.

You are also aware that if a language has the same types and operations
as Ocaml (e.g. ints and floats using + and +.), then doing type
inference (for purposes of generating efficient code) is going to be
exactly the same for a dynamically typed language as it is for Ocaml?

To the extent that your statement is true, it is meaningless.

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.

If you accept that (which, of
course, I think you must), then it follows that dynamic typing does NOT
make your compiler or generated code slow.

Run-time checks make your code slow.

They do, which is why you elide them in those cases where you can prove
they will always pass.

And that the only cases in which you wouldn't be able to infer the type,
and thus would fall back to boxing and run-time dispatch, is when Ocaml
would reject your program?

That is definitely not true. Look at rectypes, polymorphic recursion etc.

So you're saying that Ocaml accepts (some) programs for which it cannot
infer the types?

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.

Common Lisp would be a different story, because Common Lisp does mandate
that you have a full numeric tower. So if the compiler cannot prove that
you will only ever need fixnums, it will need to emit less efficient
code.

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.

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.

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.

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?

Your answers seem to be: (1) the burden of static typing is not much,
whereas the burden for dynamic typing is prohibitive

For the majority of my work, yes. I do not believe that is generally
true.

Fair enough.

(2) you'd rather
have the programmer do a little extra work each time he needs dynamic
typing, than have the compiler do extra work to generate efficient code
from a higher level language.

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.

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.

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?

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.

Regards,

Bob

---
An astronaut in space in 1970 was asked by a reporter, "How do you feel?"

"How would you feel," the astronout replied, "if you were stuck here, on
top of 20,000 parts each one supplied by the lowest engineering bidder?"



.

Relevant Pages

  • Re: RAD vs. performance
    ... exactly the same for a dynamically typed language as it is for Ocaml? ... general philosophy behind dynamic typing, ... it doesn't matter if it complains at compile time. ...
    (comp.lang.misc)
  • Re: RAD vs. performance
    ... Then you're implementing static typing. ... type checking work to compile time as possible. ... that it is possible to invent dynamically typed languages that compile ...
    (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: dynamic vs. static: the age-old debate
    ... static typing, ... whereas dynamic typing means no such restriction is imposed. ... E.g. many languages have ...
    (comp.lang.misc)
  • Re: ADA Popularity Discussion Request
    ... creative imagination do not face immediate real-word risks; ... First, for static typing, let's repeat that "Ada is for problem space". ... I guess that dynamic typing provides description of "event space", that is, ...
    (comp.lang.ada)