[PRL] Bob Harper's new blog

William D Clinger will at ccs.neu.edu
Thu Mar 17 14:12:20 EDT 2011


Dave Herman wrote:
> Now *this* I really have to question.
>
> First, with the popularity of combinator libraries like
> Parsec (ok, you could arguably claim Haskell isn't
> mostly-functional, but regardless, combinator libraries
> are everywhere). Second, you aren't clear whether you
> mean 90% of static occurrences of calls or 90% of
> dynamic evaluations of calls (I question the figure
> either way).

I meant 90% of dynamic evaluations.  The static percentage
is less, but even the static percentage of calls whose code
could be identified statically is usually much higher in
mostly-functional languages than in OO languages.

Combinator-heavy programming in Haskell could be an
exception to my claim.  I haven't studied Haskell programs.
My claim is based on my personal measurements of Scheme
programs, some of which were translated quite literally
from programs written in other mostly functional languages
such as Standard ML.  My claim is supported by similar
results as reported by other researchers.

> But finally, the claim that OO languages don't optimize
> inheritance is the most dubious.

I never said that implementations of OO languages don't
optimize inheritance.  What I said is that, for most of
the calls in OO programs, most current compilers are
unable to identify the callee's code.  That's true, and
it stands in clear opposition to the situation for mostly
functional languages, where current compilers are able to
identify the callee's code for a (dynamic) majority of
calls.

> For example, most JS
> engines use the dynamic optimization of Polymorphic
> Inline Caches (PIC's) to short-cut method lookups. This
> technique goes back at least to the 90's if not 80's.

True, but it's a dynamic (run-time) optimization, and
despite its importance it is not quite as efficient as
identifying the callee's code at compile time.

> And that's only in the last few years that JS engines
> have begun seriously optimizing. JVM technology has over
> a decade of optimization (over a century of person-years
> of work, I'm told) on top of that. I don't know their
> particular techniques, but the idea that they wouldn't
> optimize dynamic dispatch -- the number one control
> abstraction in the whole Java language -- just doesn't
> pass the smell test.

I never claimed that OO implementations do not optimize
dynamic method calls.  That's your straw man, and it has
nothing to do with what I have actually written.  If you
had heard Allen Wirfs-Brock's invited talk at DLS 2010,
you'd know that many of the dynamic optimizations that
are just now beginning to be used in JS/Java/C# systems
were pioneered long ago in languages like Lisp and
Smalltalk.

I see that Joe Marshall has already responded to Matthias
while I was writing this, but I'll post what I've written
before I read Joe's response in detail.

Matthias Felleisen wrote:
> [I am with Dave, I have read his reply.]
>
> On Mar 17, 2011, at 11:44 AM, will at ccs.neu.edu wrote:
> >    In current OO languages, loops are expressed without using calls.
>
> I don't understand this reason.

In mostly-functional languages, the dynamic percentage of
calls for which the callee's code can be determined at
compile time is greatly inflated by the use of procedure
calls to express loops.

> [a bit out of order]
>
> > In most programs that are written in mostly-functional languages,
> > well over 90% of the procedure calls are made to functions whose
> > code could be determined at compile time.
>
> >    Most of the currently available OO compilers don't even try to
> >    determine the target of a dynamic method call, mainly because
> >    the mere possibility of inheritance usually defeats that kind
> >    of optimization.
>
>
> Now we're getting to the heart of the issue. I doubt we know
> enough here to evaluate this point:
>
> 1. I am told that several of Sun's compilers do a good job
> determining the target of dynamic method calls. Indeed, in
> certain conference circles the argument goes like this:
>
>  -- FP is bad because they can't analyze method calls target
>         as precisely as we can
>
>  -- our type system gives us a stepping point that helps
>         program analysis more than FP compilers
>
> I find this equally wrong and challenge it when I hear it.

If you look at the class files produced by Sun's javac
compiler, you will find that the targets of dynamic method
calls have not been identified.  The compilers you're hearing
about are JIT compilers, which can take advantage of dynamic
knowledge about which classes have been subclassed and which
methods have been overridden in any subclasses that may exist.
These JIT-techniques are similar to the method caches to which
Dave Herman referred, and can go beyond method caches by using
techniques such as link-snapping, which was used in the Orbit
compiler for T (Scheme) circa 1983 and had been used in MacLisp
long before that.  (See Zorn and Hilfinger, LASC 3, 13-20, 1990.)
The system must be prepared to undo these optimizations when
new subclasses are loaded dynamically.

I agree with you that the first part of the argument you're
hearing is bogus: FP isn't any worse than OO, and objective
measurements appear to show it's better in this respect, but
those results are hard to interpret because the programming
styles are so different.

IMO, the second part of that argument (about the value of
type systems) has some validity, but mainly because the type
systems of Java and similar OO languages enforce an artificial
distinction between reference types and primitive (or value)
types.  Any subtyping that applies to primitive types is
resolved at compile time, and the receiver of a dynamic method
call cannot be an expression of primitive type.

> 2. I am also told that OO programmers actually don't use
> inheritance enough (from an SE perspective) and that the
> use of inheritance is tolerable. That's from academic
> compiler guys who parallelize for a living. Perhaps the
> problem is 'academic' in that sentence.

I think you're reporting a garbled message.  If parallelism
is the issue, then the cost of dynamic method dispatch is
pretty far down in the noise.  What matters for concurrency
are the side effects, and OO style definitely encourages
more concurrency-killing side effects than does FP style.

One exception to that is the concurrency-killing monad
style of Haskell and related languages.  That may be even
more harmful (for concurrency) than a straightforwardly
imperative style.

> 3. The final question is of course
>
>         if you are correct, is it just a question of
>         finding the right kind of analysis for OOPLs?
>
> For all we know a 'applicative' OOPL could be equipped with the
> same kind of analysis an FPL has to compute call targets. Perhaps
> this is a worthwhile research topic and -- if successful --
> would help promote 'applicative' programming and -- if a failure --
> would scientifically establish the inferiority of a certain class
> of OOPLs.
>
> Either way it sounds like a worthwhile exercise for scientists.

Agreed.

> Warning: purely social conventions will probably ensure that this
> research is irrelevant for the future of compilers.

Agreed.

Will



More information about the PRL mailing list