Re: RAD vs. performance

Robbert Haarman wrote:
On Tue, Jun 20, 2006 at 10:53:11AM +0100, Jon Harrop wrote:
You're beating a straw man. I am not assuming that my code is correct
because it passes the static type checker.

You did say that "it's not uncommon to have code that passes the type
checker run correctly the first time. No need to waste time unit
testing.", IIRC. When I questioned the wisdom of not doing actual
testing (how do you even know your code is correct if you haven't tested
it?),

Actual testing or unit testing? I tend not to unit test OCaml code
unless I have reason to believe it may be buggy (e.g. it uses dynamic
typing) because experience suggests that OCaml code that compiles tends
to pass unit tests, i.e. static checking is often a substitute for unit
testing. I beta test all code, of course.

you said you think static typing can eliminate the need for some testing.

Yes.

To me, it really looks like you are assuming correctness based
on the results of the type checker.

Yes.

I am saying that code which
passes a static type checker tends to pass unit tests, whereas code written
in dynamically typed languages like Lisp tends to fail lots of unit tests
and require a lot more work before you have something that you can have
faith in.

Doesn't that just mean your tests are wrong?

No, it means that dynamically typed code that compiles is more error
prone that statically checked code.

What you actually want to
test is if your functions produce the right results, so that's what you
should test, no matter if your language is statically or dynamically
typed.

Yes.

If your types are wrong, you will get wrong results, so your
tests will catch that.

Hopefully, after enough testing. Or you could use static checking and
find most of the bugs immediately.

I can't see how tests that are passed by programs
written in statically typed languages but failed by programs in
dynamically typed languages can be useful.

The tests are useful because they're telling you that the code you
wrote in the dynamically typed language is wrong.

Perhaps what you're really saying is that a static type checker will
catch programming errors before you even get to the unit tests, and this
will save you time.

Exactly. The compile-debug cycle is much faster than the
compile-test-debug cycle and it fixes a significant proportion of the
bugs.

This may or may not be true, depending on a number
of things, e.g. the amount of code you have to write in your statically
typed language vs. your dynamically typed language,

OCaml tends to be significantly more concise than Lisp.

the time it takes to do static type checking,

A fraction of a second.

the time it takes to run unit tests, the number
of mistakes that lead to type errors that you make, etc.

Actually, I'd say that the time taken to design and write the unit
tests and the nature of the task were the most important factors. Some
tasks simply require lots of dynamic typing (I mean run-time tests of
some kind here), e.g. GUI work.

However, I see your point in this case.

Right. In my experience, static type checking can save an enormous
amount of time. That is not to say that all statically typed languages
will save an enormous amount of time.

Neither, I'd say. As you say, Lisp has had many things (like OOP)
retrofitted to it. However, there is no substitute for careful design. You
can't expect a language with a multitude of ad-hoc supplemental features to
work as well as a language designed from the ground up to support them.

I think we're going to have to disagree on this one. I maintain that, if
a language doesn't produce fast programs, it _must_ be due to either
features of the language that prevent certain optimizations, or an
implementation issue. Apparently, you think otherwise.

No. I agree. I was saying the former.

I would also disagree with your notion of Common Lisp having features
like OOP ad-hoc retrofitted on them. It seems to me that when OOP came
around, Lispers designed and experimented with various object systems,
and eventually integrated one into the language, including an overhaul
of the type system so that pre-CLOS types are also CLOS classes. To me,
that's reworking your language with the object system integrated, not
just bolting an object system on a language that otherwise doesn't have
one (like C++, and many languages that imitate it).

True.

I don't think so. If you write your program in such a way that types can
be determined statically,

That would require you to manually monomorphise your code, which is a
non-trivial step taken by whole program optimising compilers. I'm not about
to start executing compiler optimisations by hand.

If you write your code exactly the same way you would have written it in
a statically typed language, the compiler should be able to make the
same optimizations.

In theory, if that was possible then yes. In practice, I don't think
that is possible and current compilers don't seem to do that. Try
writing a Lisp implementation of my ray tracer that is "exactly the
same" as my OCaml, for example. I'm not even sure that it can be done
in theory, let alone in practice... :-)

it's possible to elide all run-time type
checks and method dispatches, completely eliminating any overhead from
dynamic typing.

Statically-determined type information (e.g. immutability) is used by
compiler optimisers, so you have not regained the lost ground.

Depends. Again, if the compiler can figure out that you're not
modifying certain data structures (and there certainly are dynamic type
systems where this could be the case), it can make the same
optimizations.

Yes, but do real compilers figure that out? Benchmarks suggest not.

If the compiler can't figure it out, there are two
options: either you would have to write type declarations (both in the
statically typed language and in the dynamically typed one),

You never have to write type declarations in OCaml.

or you couldn't have written the program in a statically typed language.

You can write any program in a statically typed language by resorting
to dynamic typing when you have to.

If the compiler doesn't do that, it's an implementation issue.

No, it isn't. It is a design issue. It is silly to assume that you can take
an ancient language and bolt on an uber-optimiser to get the performance of
a modern language. There are sound theoretical reasons why that is silly
(they underpin the design of languages like ML) and there is an
overwhelming amount of practical evidence that it simply doesn't work. What
more do you want?

It's a design issue inasmuch as there are features that bar
optimizations.

Yes, exactly.

One such feature would be the ability to redefine
functions at runtime. You trade flexibility for speed, or the other way
around. Besides features that stand in the way of optimization, there
are implementation issues. A compiler that doesn't do type inferencing
and the optimizations that it enables is simply not giving you code that
is as fast as it could be.

Yes, but it is still fundamentally limited by the language's design.

I'm curious how the speed of the code
generated by the commercial Lisp compilers compares to that of the open
source compilers.

I've heard that they can be a lot faster but I doubt they come close to
OCaml/MLton, for example. Stalin does but it has some serious
disadvantages, primarily compile time.

There is one main advantage of Lisp as I see it: EVAL. This could let you
write a compiler/interpreter that is simpler and gives better performance
than you could in a language without EVAL. That's a tiny niche though.

Eval is one of those things that are hard to do in a statically typed
language.

MetaOCaml does that. I've played with it a bit but you end up doing a
lot of unnecessary boxing to keep the static type system happy in the
intermediate stages. That gives you all of the slow and buggy
disadvantages of dynamic typing without the advantage of raw OCaml
performance. Also, you can't fully leverage OCaml's pattern match
compiler in meta-compiled code.

It's also probably a major performance killer (after all, it
limits the assumptions that a compiler can make about your program).
Again, it's a trade-off between speed and power.

In theory, MetaOCaml gives you the best of both worlds. In practice,
I'm not sure. I'd like to write an interpreter equivalently in both
Lisp and MetaOCaml and see how performance compares. I expect MetaOCaml
would be much faster.

Cheers,
Jon.

.

Relevant Pages

  • Re: "STL from the Ground Up"
    ... high-level intermediate language than can interoperate with many other ... If your language lacks expressive features then you cannot write code ... memory management in comparison. ... Mostly because type errors mean that the programmer and compiler disagree ...
    (comp.programming)
  • Re: Beyond CL?
    ... around in the internals of the language. ... as the programmable programming language; ... Eventually a bank of many users' optimizations could be ... approach the fabled "sufficiently smart compiler". ...
    (comp.lang.lisp)
  • Re: A note on computing thugs and coding bums
    ... It would handle international characters if the execution character ... method I used in "Build Your Own .Net Language and Compiler". ... work areas and counting on Nul is an illusion. ...
    (comp.programming)
  • Re: WaitForSingleObject() will not deadlock
    ... represent an incorrect implementation of the language. ... the *compiler* does not guarantee this. ... but to state it in terms of the execution instead of the formal semantics of the language ... as long as the optimizations do not change the semantics of the language). ...
    (microsoft.public.vc.mfc)
  • Re: Teaching new tricks to an old dog (C++ -->Ada)
    ... Because the run-time check code required by the language will require ... > Because the compiler checks that there is static matching ... of a feature rich language like Ada, ... into the optimizations. ...
    (comp.lang.ada)