Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/5/84; site reed.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!tektronix!reed!mdr
From: mdr@reed.UUCP (Mike Rutenberg)
Newsgroups: net.lang.st80
Subject: Re: Native code Smalltalk compilers
Message-ID: <3482@reed.UUCP>
Date: Fri, 16-May-86 20:38:48 EDT
Article-I.D.: reed.3482
Posted: Fri May 16 20:38:48 1986
Date-Received: Mon, 19-May-86 06:45:57 EDT
References: <418@vger.UUCP> <9000005@uiucdcsp>
Reply-To: textronix!BAtkinson.pa@Xerox.arpa
Organization: Reed College, Portland, Oregon
Lines: 76

In article <9000005@uiucdcsp> johnson@uiucdcsp.CS.UIUC.EDU writes:
>
>The best paper on Smalltalk implementations is the one by Peter Deutsch
>and Allan Schiffman in the 10'th POPL conference.  There is also a paper
>by Suzuki and Terada in that same proceedings that talks about
>implementation issues.  One of the things that is apparent from the
>Deutsch and Schiffman paper is that interpretation alone is not the
>reason why Smalltalk is slow, so just compiling Smalltalk to machine
>language will not improve the speed much.  However, certain optimizations
>can make a big difference.  In order to optimize Smalltalk programs the
>compiler must know the particular methods that are being invoked by a given
>message.  A type system is necessary to do this. Suzuki describes one type
>system in the 8'th POPL conference proceedings, while Borning and Ingalls
>described a more complete type system in the 9'th POPL conference proceedings.

What Ralph says above hits the nail right on the head.  By far, the 
largest overhead in Smalltalk 80 is the extremely late binding of 
procedures or methods.  Do optimization without a type system
can not be absolutely ruled out, but it is by far a much more difficult
task.  A fellow by the name of Pavel Curtis at Cornell is doing his
PhD on a formal type system that attempts to handle polymorphism, so
you might want to get in touch with him if you want to know more.
(Pavel.pa@Xerox.com on the arpanet will work, I think)

The two type systems mentioned above are really quite different.  However,
they both are not well founded in that they produce incorrect results.
Borning and Ingalls approach can be modified to some degree to produce
a workable and correct system that will support an optimizing compiler
capable of statically determining the identity of called methods.
I spent eight months last year creating such a compiler, which I named
Hurricane.  I am presenting a paper on it at OOPSLA in October.  If 
anyone is interested, and the response is not TOO great, I could send
you an advance copy of the paper.

>I am having a paper in the Object-oriented Programming Languages, 
>Applications, and Systems conference next October that explains why these
>type systems are not suficient for code-optimization and that presents a
>type system for Smalltalk that (I claim) is.  There will probably be a lot of

I am very interested to see how close Ralph's type system is to mine.
Should be a fun conference!

>papers on compilation and other implementation techniques at this conference,
>so anyone who is interested in implementing object-oriented languages should
>certainly attend.
>
>I have been looking at optimizing Smalltalk programs for a couple of years
>and am in the early stages of an implementation of an optimizing compiler.
>Smalltalk was not really designed to be optimized because it is typeless.
>Retrofitting a type system to Smalltalk is tricky and inevitably requires

Tricky is quite an understatement!  Especially if you take the point of 
view as I did that you want to do any optimiziations completely transparently.
That is, to not change the semantics of the language at all.

>some modification to some of the primitives.  It might be better to just
>start over and design a language that is well integrated with a type system.
>Building an optimizing compiler for Smalltalk is interesting research but
>it is by no means obvious that such a project will be a success.

Depending on your point of view, Hurricane was quite successful.  My feeling
at this point is that if you really use the paradigm provided by
Smalltalk effectively, then there is virtually no leverage to be gained 
by optimization that can do static method bindings.  However, if you
pretend you are writing Pascal say, but instead use Smalltalk, we can probably
do a lot for you, and there is no fundamental reason why the code should 
not run as fast as if you had actually used Pascal.
>
>Ralph Johnson

	bob atkinson

	BAtkinson.pa@Xerox.com	arpanet
	BAtkinson.pa%Xerox.com@csnet-relay.csnet or something like that
		on csnet
	503-293-4318