Re: incremental compilation via shared library

dave@yost.com (Dave Yost) writes:
>[Is it time to make compilation as easy as a subroutine call?]


Various languages have offered related facilities for years. Without
going in to a lot of detail (or being very precise :-), LISP
[McCarthy78] data and code use the same structure, so programs can
generate code on the fly; LC^2 [Mitchell70] allowed programs to
generate strings and then call routines to convert them to executable
code; SNOBOL-4 [GPP71] allowed programs to execute strings; there is no
command interpreter in Smalltalk-80 [GR83], instead all input
expressions are compiled and then executed. Most extensible systems
either use some kind of dynamic compilation or translate extension code
in to a form that could be compiled but is instead interpreted [NG87].


>[It would be great to have code objects w/ various source
> representations; a library with a symbolic database (mapping between
> source representations and code), compilers, linkers, disassemblers,
> debugging.]


I'm an advocate of dynamic compilation and, yes, these services sound
like services you (I) want [KEH91]. Some issues include:


  . The problem of mapping from an arbitrary source language to an
      arbitrary machine language is generally regarded as unsolvable
      [Conway 58]. In conventional compilers, much or all of the
      translation from source to executable can be tailored to the
      particular language being represented. As compilers are increasigly
      fragmented and the components are used more widely, it is harder to
      make them generate good code because e.g., an intermediate step may
      fail to pass through alias information needed for good back-end
      optimization. As a practical matter we can do "pretty well", but
      there will be applications that need better information than can be
      passed through a generic IR with a fixed set of operators. (This is
      an instance of a more general reuse problem [Kiczales92].)


  . Some systems want specialized, application-specific code generators
      to minimize compile times [KEH91]. Thus, an ideal system also
      allows partial evaluation of the code generation library w.r.t. the
      application. This facility will take a while to appear; here, I'm
      merely pointing out that it should be kept in mind when designing
      the system.


  . Static (batch) compilers probably won't be implemented "simply" as
      calls to the code generation routines because static compilers can
      afford to spend a lot of time performing analysis and optimizations
      that a dynamic compiler can't. The static compiler can, of course,
      take advantage of the dynamic compiler service.


  . Many services, such as dynamic compilers, dynamic linkers (e.g.,
      [GLDW87, SF89, HO90, Sabatella90, SysV-ABI90), code patching tools
      and code-patching debuggers (e.g., [Kessler90]) and symbol table
      services ([FST90]) are distinguished from their static counterparts
      largely in that we have a process/address space compartmentalization
      (e.g., Un*x and VMS). In a number of other operating systems (e.g.,
      Multics, and Psyche [GBK+92]), the standard tools simply operate on
      objects ("things"; I don't necessarily mean objects in the O-O
      sense) and the OS model doesn't distinguish between procedures and
      programs or between the manipulation of code and the manipulation of
      data (except that some coherency operation may be needed before
      modified code is executed [Keppel91]). In short, then, many
      services already exist except that they assume a heavyweight
      boundary between the tool and the data that it manipulates. Indeed,
      many of the dynamic tools continue this distinction; for example,
      dynamic linkers often link files but are unable to dynamically link
      code that is already in-core.


  . Dynamic code tools should provide representations for inter-language
      data references, so that users of an application can provide code
      written in language A even though the application was written in
      languge B. Note that some kinds of references cannot be resolved;
      FORTRAN and C use mutually incompatible array layouts. Other
      references can use the same layout for all references by all
      languages; structures can usually use the most generic layout. Some
      references want mapping; e.g., pointers in LISP may be best
      represented with tags and in C without and conversion is always
      possible.


  . Dynamic code manipulation is both a language construct and an
      implementation technique, and you don't necessarily need both at the
      same time. For example, LISP and other systems provide a
      programming model in which code can be created on-the-fly, but there
      is no requirement that the implementation generate code dynamically.
      An interpreter implementation is adequate. Likewise, a number of
      tools use dynamic code generation as an optimization technique but
      no hint of the implementation is exported even to the tool's
      immediate caller (the |bitblt| graphics operation is a particularly
      famous one [PLR85]).


Along the way it's also worth considering that there are a farily wide
variety of applications that might want dynamic code generation to
improve performance [KEH91], flexibility or extensability [NG87] and
interoperability. Often the needs of any one tool overlap some with
the needs of some other tools. However, the span of all tools covers a
pretty wide design space, making it hard to design a tool that does a
good job for everybody. Thus, I expect that many of the tools will
initially have specific limitations that make them faster and easier to
build and use, and that more widely applicable tools will come only
with time.


Although there are some deep and long-term issues to be dealt with, my
general "take" on the situation is that much of the technology of
retargetable code generators, code patching tools, etc., is already
mature enough, but that inertia (Good static tools already exist, why
write new tools?) and perspective (Who really wants the dynamic tool?
What is a good interface?) along with all the usual problems with time,
space, and money, limit their rate of development.


;-D on ( The dynamic code system of program building ) Pardo


More references than you care to read:


%L Conway58
%A M. E. Conway
%T A Proposal For An UNCOL
%J Communications of the ACM
%V 1
%N 10
%D October 1958
%P 5-8


%L FST90
%A Alastair Fyfe
%A Ivan Soleimanipour
%A Vijay Tatkar
%T Compiling from Saved State: Fast Incremental Compilation with
Trditional Unix Compilers
%J USENIX
%D Winter 1991
%C Dallas, Texas
%P 161-171


%L GBK+92
%A William E. Garrett
%A Ricardo Bianchini
%A Leonidas Kontothanassis
%A R. Andrew McCallum
%A Jeffery Thomas
%A Robert Wisniewski
%A Michael L. Scott
%T Dynamic Sharing and Backward Compatability on 64-bit Machines
%R TR 418, University of Rochester
%D April 1992


%L GLDW87
%A Robert A. Gingell
%A Meng Lee
%A Xuong T. Dang
%A Mary S. Weeks
%T Shared Libraries in SunOS
%J Summer USENIX
%D 1987
%P 131-145


%L GR83
%A Adele Goldberg
%A David Robson
%T Smalltalk-80: The Language And Its Implementation
%I Addison-Wesley
%D 1983


%L GPP71
%A Ralph E. Griswold
%A J. F. Page
%A I. P. Polonsky
%T The SNOBOL4 Programming Language (2nd Ed.)
%I Bell Telephone Laboratories, Incorporated
%P Prentice-Hall, Incorporated
%D 1971


%L HR93
%A Paul Haar
%A Byron Rakizis
%T Es: A Shell with Higher-Order Functions
%J Proceedings of the 1993 Winter USENIX
%D January 1993
%P 53-62


%L HO90
%A W. Wilson Ho
%A Rondald A Olsson
%T An Approach to Genuine Dynamic Linking
%J Software-Practice and Experience
%V 21
%N 4
%P 375-390
%D April 1991


%L KEH91
%A David Keppel
%A Susan J. Eggers
%A Robert R. Henry
%T A Case for Runtime Code Generation
%R UWCSE 91-11-04
%I University of Washington Department of Computer Science and
Engineering
%D November 1991


%L Keppel91
%A David Keppel
%T A Portable Interface for On-The-Fly Instruction Space Modification
%J Proceedings of the Fourth International Conference on
Architectural Support for Programming Languages and Operating Systems
(ASPLOS-IV)
%D April 1991
%P 86-95


%L Kessler90
%A Peter Kessler
%T Fast Breakpoints: Design and Implementation
%J Proceedings of the ACM SIGPLAN '90 Conference on Programming
Language Design and Implementation; SIGPLAN Notices
%V 25
%N 6
%D June 1990
%P 78-84


%L Kiczales92
%A Gregor Kiczales
%T Towards a New Model of Abstraction in Software Engineering
%J Proceedings of the International Workshop on Reflection and
Meta-Level Architecture
%D November 1992
%C Tokyo, Japan
%E Akinori Yonezawa
%E Brian Cantwell Smith
%P 1-11


%L McCarthy78
%A John McCarthy
%T History Of LISP
%J Preprints for the History of Programming Languages Conference;
ACM SIGPLAN Notices
%V 13
%N 8
%D August 1978
%P 217-223


%L Mitchell70
%A J. G. Mitchell
%T The Design and Construction of Flexible and Efficient Interactive
Programming Systems
%R Ph.D. Dissertaion
%D 1970
%I Carnegie-Mellon University
%N Also appears as: Outstanding Dissertaions in the Computer Sciences;
Garland Publishing, New York; 1978.


%L NG87
%A David Notkin
%A William G. Griswold
%T Enhancement through Extension: The Extension Interpreter
%D June 1987
%J Procedings of the ACM SIGPLAN '87 Symposium on Interpreters and
Interpretive Techniques
%P 45-55


%L PLR85
%A Rob Pike
%A Bart N. Locanthi
%A John F. Reiser
%T Hardware/Software Trade-offs for Bitmap Graphics on the Blit
%J Software - Practice and Experience
%V 15
%N 2
%P 131-151
%D February 1985


%L Sabatella90
%A Marc Sabatella
%T Issues in Shared Libraries Design
%J USENIX Summer Conference Proceedings
%D June 1990
%P 11-23


%L SF89
%A M. E. Segal
%A O. Frieder
%T Dynamic Program Updating: A Software Maintenance Technique for
Minimizing Software Downtime
%J Software Maintenance: Research and Practice
%I John Wiley and Sons, Ltd.
%V 1
%P 59-79
%D 1989


%L SysV-ABI:90
%Q AT&T
%T System V Application Binary Interface
%D 1990
%I Prentice-Hall
%K Unix System V ABI
%P 5-12 to 5-21
--

Return to the comp.compilers page.
Search the comp.compilers archives again.