[ruby-core:32645] Re: Proposal for Optional Static Typing for Ruby

On Wed, Sep 29, 2010 at 3:40 PM, Charles Oliver Nutter
<[e-mail]> wrote:
> On Wed, Sep 29, 2010 at 8:03 AM, Bill Kelly <[e-mail]> wrote:
>> As an aside -- it's been pointed out to me on occasion that
>> dynamic languages don't theoretically have to be slow; that one
>> could conceivably perform sophisticated run-time analysis and
>> optimize certain dynamic code paths to native instructions.
>>
>> But in practical terms, if types are known at compile time,
>> generation of efficient native code is a well understood
>> problem.
>
> This is the crux of the problem. Ruby is dynamic to a great enough
> extent that global optimization is not always possible (or at least
> not feasible) since anything, anywhere in the system can change. Not
> only can new types be introduced, but existing types can be modified,
> and even individual objects only give soft guarantees about what type
> they are (singletonizing an object is almost a limited "become" from
> Smalltalk, and defeats most dynamic optimizations completely).
>
> And the unfortunate truth is that those features which make Ruby hard
> to optimize are also some of the nicest features. I use them myself,
> knowing that no implementation can cope with them perfectly.

This is more my decision as to where to jump into this discussion, and
not really a reply to Charles, but his comment here seems a useful
place to hang my two cents.

There are (at least) two ideas playing around in this thread.  One is
the desire to somehow use types to make a program written in a
dynamically run-time typed language like ruby, the other is to use
type information to improve the performance of programs written in
such languages.

The first idea seems most popular among those coming to a dynamically
typed language from a language like C++ or Java which expresses types
via class/interface hierarchies or DAGs.  Since both Ruby and C++ are
"object oriented" what's good for one must be good for another.  The
truth is that there are two very different notions of what "object
oriented" means which confuses discussions. I won't go into that too
much here, but I'll cover it at length in my upcoming talk at Ruby
Conf.

Both ideas have a long history, which is somewhat intertwined. I can
give a bit of a Smalltalk oriented perspective.  Several folks worked
on project to add type declarations to Smalltalk in the late 1980s
early 1998s. Some of these were experienced Smalltalkers who knew the
power of dynamic typing, folks like Dan Ingalls (the original
implementor of Smalltalk from it's inception through Smalltalk-80) and
who went on to later be one of the driving forces behind Squeak. Alan
Borning of UW, and Ralph Johnson of UI-UC.  Another effort was a
project code named Woody at Knowledge Systems Corp here in the
Triangle area, led by Steve Burbeck and Sam Adams who had considerable
Smalltalk implementation and usage background.

Most of these efforts eventually stalled out, probably because of a
realization of the difficulties of adding an expressive enough
'statlc' type system, even as an optional annotation to a language
like Smalltalk.

Not that the work was completely fruitless. Ralph also led his
graduate students to build the first (semi) automatic refactoring
tools, using the Smalltalk development environment.  One of the
complaints about modern-day dynamically typed languages is that they
don't tend to have such refactoring tools.  Such tools are a bit easer
in a language like Java where type-checking can help drive the
refactorings. In the early days of VisualAge for Java (the precursor
to today's Eclipse), there was crude refactoring support from having
changes which caused type violations turn on little red x's on the
classes affected, giving a kind of to-do list for manually refactoring
something. Of course today's Java IDE are more like Ralph's original
Smalltalk refactory.

And as my one of my friends and personal heroes, Ward Cunningham, has
been heard to say, "It's a good thing that Java has good refactoring
tools, because you have to do a lot more of it."  In a dynamically
typed language you aren't forced to immediately change things just to
keep the type system in line.  Instead you can proceed faster and
refactor somewhat more infrequently to pay off technical debt.  Using
Test Driven development is a much more flexible and pleasant work flow
for those of us who have gotten used to the dynamically typed
philosophy.

And Ruby inherited a lot of the same blessings and curses of the
Smalltalk view of computation via objects, rather than objects as
abstract data types.  What it lacks is the kind of development
environment that Smalltalk has on the whole I can live without the ide
though.

On he performance side, there's been a long history of utilizing type
information, either heuristically 'hard coded' or gathered at run-time
to improve performance.

In the vein of "heuristic hardcoding" early Smalltalk implementations
(and maybe most if not all current ones) do things like cheating on
the implementation of control flow.  In Smalltalk if 'statements' are
implemented as message sends to boolean objects which selectively then
evaluate a block argument corresponding to whether the receiver is
true or false.  In most implementations this was implemented as a test
and branch rather than a message send, with some treating a
non-boolean 'receiver' on an exception basis.  Another example was
assuming that most "+" messages are sent with a SmallInteger
(Smalltalks equivalent to FixNum) with a SmallInteger argument.  So +
gets implemented as simply adding the two object references together,
and detecting whether or not the result is still a SmallInteger after
a bit of bit manipulation.  If it is you're done, if not you do the
actual message send.

A careful selection of the representation of a SmallInteger can make
it easy to do this with a bit of bit manipulation.  For example, if
you take an MRI style VALUE as a machine integer, I think if you xor
one of the two arguments with 1 and add, then if the resulting integer
is odd and you haven't generated an overflow, then you know that both
the arguments and the result are FixNums.  This might not be exactly
correct for Ruby's representation, but most Smalltalk's picked an
implementation which allowed such tricks.

Another family of tricks was caching method lookups either globally or
at the call site, with clever techniques to detect and react to a
cache miss. Terms like Polymorphic Inline Cache came into being.

Such trickiness disturbed some Smalltalkers, in particular David
Ungar, who had done his PhD dissertation at UC Berkeley on the
measurement and improvement of Berkeley's Smalltalk implementation,
decided to try to take tricks like hard compiling ifTrue:ifFalse: and
make a language like Smalltalk, but even more dynamic, the result was
Self, which has features like removing the distinction between
instance variable and methods, both are simply named slots looked up
dynamically, the difference being that a method slot is marked so that
instead of returning it's contents, it evaluates it.  Self also did
away with explicit classes let alone class inheritance, instead it
used a prototype based scheme similar to that 'built in' to JavaScript
these days.

Then Dave and his Self guys worked to get the performance back by
gathering on-the-fly information about 'types' and generating
optimized code again into a cache so that it could be flushed and
recomputed as facts on the ground changed.

The work on Self eventually fed into the Java Hotspot VM.

-- 
Rick DeNatale

Blog: http://talklikeaduck.denhaven2.com/
Github: http://github.com/rubyredrick
Twitter: @RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale