Path: utzoo!censor!geac!torsqnt!lethe!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!samsung!sdd.hp.com!wuarchive!uwm.edu!ux1.cso.uiuc.edu!uicbert.eecs.uic.edu!wilson
From: wilson@uicbert.eecs.uic.edu (Paul Wilson)
Newsgroups: comp.arch
Subject: Re: What the compiler won't do you for you
Message-ID: <1991Mar1.171549.11638@uicbert.eecs.uic.edu>
Date: 1 Mar 91 17:15:49 GMT
References: <8787@exodus.Eng.Sun.COM> <24280:Feb2802:55:4991@kramden.acf.nyu.edu> <8808@exodus.Eng.Sun.COM> <1991Feb28.181948.26958@rice.edu> <1991Mar1.094249.27890@jarvis.csri.toronto.edu>
Organization: University of Illinois at Chicago
Lines: 44

thomson@hub.toronto.edu (Brian Thomson) writes:

>I seem to remember running across a reference, about 10 years ago
>(that's when I saw it, not necessarily when it was published),
>that dealt with recognizing common sequences of operations in APL
>and compiling them into particularly efficient code.
>I think they called it "recognition of programming idioms" or something
>of the sort.  Does this ring a bell with anyone?

I'm not sure we're talking about the same thing, but it rings bells with
me.  The Hewlett-Packard APL 3000 compiler did snazzy dynamic compilation,
allowing it to do optimizations of program fragments that actually
get executed, as opposed to working that hard on all of the dynamically
possible sequences.  (See Van Dyke, E.J., "A dynamic incremental compiler
for an interpretive language," Hewlett-Packard Journal, July 1977, pp.17-24.)

This is philosophically similar to Chambers & Ungar's recent work on
the Self compiler, which uses aggressive inlining and interprocedural
optimization.  It comes up with "customized" versions of code for
different kinds of call sites.  This and the inlining allow a lot
more type analysis of code for a (*very*) dynamically-typed
language.  That lets them optimize away most of the dynamic type
checks, and (importantly) optimize across things they otherwise
couldn't optimize across.  Self is very, very fast for a dynamically-typed
language.

(Self is like Smalltalk, only more so.  It doesn't even have classes,
like Smalltalk; it uses prototypes intead.  The implementation has
an analogue of classes to get back the efficiency advantages.  See 
Chambers & Ungar, "Customization: optimizing compiler technology
for Self, a dynamically-typed object-oriented language," Proc. SIGPLAN
'89, pp. 146-160.)

It seems likely that some of the stuff from the APL 3000 compiler could
also be generalized to do a good job optimizing operations on parameterized
types and homogeneous collection types in a strongly-typed polymorphic
language like Modula-3 or Eiffel. 

  -- Paul
-- 
Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@bert.eecs.uic.edu
Box 4348   Chicago,IL 60680