Summary of UNCOL references

I got quite a lot of references, more than I'd anticipated. Thanks to
all who sent them in.


Regards,
John Levine, comp.compilers moderator
johnl@iecc.cambridge.ma.us or {spdcc|ima|world}!iecc!johnl


From: mitchell wand <wand@corwin.ccs.northeastern.edu>


Denotational semantics can be viewed as using lambda-calculus as a universal
intermediate language. Here's a blatantly skewed list of references:


Steele, G.L. ``Rabbit: A Compiler for Scheme,'' MIT AI TR No.~ 474 (May,
1978).


Wand, M. ``Semantics-Directed Machine Architecture'' {\it Conf. Rec. 9th ACM
Symp. on Principles of Prog. Lang.} (1982), 234--241.


Wand, M. ``Deriving Target Code as a Representation of
Continuation Semantics'' {\it ACM Trans. on Prog. Lang. and Systems 4}, 3
(July, 1982) 496--517.


Clinger, W. ``The Scheme 311 Compiler: An Exercise in Denotational
Semantics,'' {\it Conf. Rec. 1984 ACM Symposium on Lisp and Functional
Programming} (August, 1984), 356--364.


The next few references describe some implementations using this idea:


Kranz, D.A., Kelsey, R., Rees, J.A., Hudak, P., Philbin, J., and Adams, N.I.,
``Orbit: An Optimizing Compiler for Scheme,'' {\it Proc. SIGPLAN '86 Symp. on
Compiler Construction}, {\it {SIGPLAN Notices 21}\/}(7), July, 1986, 219-223.


Appel, A.W., and Jim, T., ``Continuation-Passing, Closure-Passing Style,''
{\it {Conf. Rec. 16th ACM Symp. on Principles of Programming Languages}\/}
(1989), 293--302.


Kelsey, R., and Hudak, P. ``Realistic Compilation by Program Transformation,''
{\it {Conf. Rec. 16th Ann. ACM Symp. on Principles of Programming
Languages}\/} (1989), 281--292.


Appel, A. W., {\it Compiling by CPS Transformation} Cambridge University
Press?, 1992?


[And last, a shameless plug for our new textbook, which should be available by
January 1. It actually is on point here, though]:


Friedman, D.P., Wand, M., and Haynes, C.T. {\em Essentials of Programming
Languages}, MIT Press/McGraw-Hill, 1992.


--Mitch


Mitchell Wand
College of Computer Science, Northeastern University
360 Huntington Avenue #161CN, Boston, MA 02115 Phone: (617) 437 3539
Internet: wand@{corwin|flora}.ccs.northeastern.edu Fax: (617) 437 5121


From: Debora Weber-Wulff <dww@inf.fu-berlin.de>


A UNCOL called CAT (Common Abstract Tree Language) was developed at
the University of Kiel in West Germany. It was bought by the Norwegian
Computer Company Norsk Data, and used to make "real" compilers that
were used in "real" products. There were front-ends made for pascal,
c, and BASIC (Fortran was planned but never developed); back-ends
for NS16000, M680xx, ND-100, ND-500, ND-5000 (Norsk Data CPUs) and
a Siemens machine I've forgotten the name of. Reinhard Voeller is
still with Norsk Data in Kiel, Uwe Schmidt is professor at the FH in
Wedel, in Germany.


Doctoral dissertations:


Reinhard Voeller, Entwicklung einer maschinenunabhaengigen Zwischensprache
und zugehoeriger Uebersetzeroberteile fuer ein Mehrsprachen-
uebersetzersystem mit Hilfe von VDM. Technical Report, University of
Kiel, Dept. of Computer Science, 3/83 (December 1983).


Uwe Schmidt, Ein neuartiger, auf VDM basierender Codegenerator-
Generator. Technical Report, Univ. of Kiel, Dept. of Computer Science
4/83. (December 1983).




Papers:


Uwe Schmidt, Reinhard Voeller: A Multi-Language Compiler System with
Automatically Generated Codegenerators, in: Proceedings of the
SIGPLAN '84 Symposium on COmpiler COnstruction, pp.202-212.
ACM SIGPLAN NOtices, 19 (6) 1984


Uwe Schmidt, Reinhard Voeller: Experience with VDM in Norsk Data,
in: Bjoerner, D. et al (eds.) VDM - A formal method at work,
Proceedings of the VDM-Europe Symposium 1987, pp. 49-62,
LNCS 252, Springer, 1987.


There have been other papers, but I am no longer with ND and forgot to
take a copy of the "official Bibliography" with me. This is all that I
can find in the piles of paper at the moment!


From: wardrb@cs.utexas.edu (Richard Byron Ward)


Here are a couple references:


Strong, J., Wegstein, J., Tritter, A., Olsztyn, J., Mock, O. and Steel, T.
The problem of programming communication with changing machines: a proposed
solution, Communications of the ACM 1,8 (August 1959)


Steel, T. B., A First Version of UNCOL, Proceedings of the Western Joint
Computer Conference, May 1961


Architecture Neutral Distribution Format: A White Paper, Open Software
Foundation, Cambridge, MA, November 1990


Davidson, J., Benitez, M., et al, ANDF: Finally an UNCOL after 30 Years,
Computer Science Report No. TR-91-05, March, 1991
This is an extended abstract from a group from UVa and HP.


Steel, T.B., "UNCOL: The Myth and the Fact", Annual Review in Automated
Programming 2 (1961)


Steel, T.B., "UNCOL", Datamation 6:1 (1960)


Holt, A.W. and Turanski, W.J., "Man-to-Machine Communication and Automatic
Code Translation", Proceedings of Western Joint Computer Conference 17 (May
1960)


Related stuff: (half way between UNCOL and compiler-compiler)


Donegan, M.K., Noonanok, R.E. and Feyock, S., "A Code Generator Generator
Language", Sigplan Notices 14:8 (August 1979)


Cattell, R. G., Newcomer, J. M. and Leverett, B. W., "Code Generation in a
Machine-Independent Compiler", Sigplan Notices 14:8 (August 1979)


Glanville, R. S. and Graham, S. L., "A New Method for Compiler Code
Generation", 5th Annual ACM Symposium on Principles of Programming Languages
(Jan. 1978)


Glanville, R. S., "A Machine-independent Algorithm for Code Generation and its
use in Retargetable Compilers", Ph.D. thesis UCB (1977)


Here are a couple more references for the ANDF project, they are
descriptions of the scheme that OSF chose.


TDF Specification Part 1 & 2 (Oct. 1991)
United Kingdom's Defense Research Agency
RSRE, Malvern


Part 1 is the description of the specification that OSF accepted, part 2 is
a description of extensions.


for more info:
Dr. N. E. Peeling
Defense Research Agency
RSRE
St. Andrews Rd.
Malvern
Worcestershire
United Kingdom WR14 3PS


Tel. +44 684 895314
Fax +44 684 894303
Internet peeling%uk.mod.hermes@relay.mod.uk


From: dalamb@umiacs.UMD.EDU (David Lamb)


I took a copy of the PQCC project bibliography when I left CMU (about
1983), but all I could find in it was the following:


%f inproceedings
%s UNCOL
%A T. B. Steel
%T A First Version of UNCOL
%B Proceedings of the Western Joint Computer Conference
%I AFIPS
%P 371-377
%D 1961


TCOL was supposed to be a family of tree-based intermediate languages,
each specialized, but the whole family meant to be universal.


%f TechReport
%s RevTcolAda
%A J. M. Newcomer
%A D. A. Lamb
%A B. W. Leverett
%A D. Levine
%A A. H. Reiner
%A M. Tighe
%A W. A. Wulf
%T TCOL.Ada: Revised Report on An Intermediate Representation for the DOD Standard Programming Language
%I CMUCSD
%D June 1979
%R CMU-CS-79-128


I thought about mentioning DIANA, to which TCOL contributed, but it
wasn't intended to be universal.


From: Lutz Hilken <hilken.bln@sni-usa.com>


.\" ==================================================
.IP "[AG84]"
Alfred V. Aho, Mahadevan Ganapathi,
.br
"Efficient Tree Pattern Matching: an Aid to Code Generation" in
\fIProceedings of the 12th ACM Symposium on Principals of Programming
Languages\fP,
ACM, New York, S. 334-340, 1985.
.\" ==================================================
.IP "[AGT89]"
Alfred V. Aho, Mahadevan Ganapathi, Steven W. K. Tjiang,
.br
"Code Generation Using Tree Matching and Dynamic Programming" in
\fIACM Transactions on Programming Languages and Systems\fP,
Volume 11, No. 4, S. 491-516, Oktober 1989.
.\" ==================================================
.IP "[AJ76]"
Alfred V. Aho, S. C. Johnson,
.br
"Optimal Code Generation For Expression Trees" in
\fIJournal of the ACM\fP,
Volume 23, No. 3, S. 488-501, July 1976.
.\" ==================================================
.IP "[BEZ88]"
Rudolf Berghammer, Herbert Ehler, Hans Zierer,
.br
"Towards an Algebraic Specification of Code Generation" in
\fIScience of Computer Programming\fP,
No. 11, S. 45-63, 1988.
.\" ==================================================
.IP "[BH91]"
Michael Bouschen, Lutz Hilken,
.br
\fI-AIR- Another Intermediate Representation, Entwurf einer portablen
Zwischensprache f\*ur den Syntheseteil eines \*Ubersetzers der
Programmiersprache CooL,\fP
Studienarbeit, Technische Universit\*at Berlin,
Fachbereich Informatik, April 1991.
.\" ==================================================
.IP "[Cat80]"
R. G. G. Cattell,
.br
"Automatic Derivation of Code Generators from Machine Descriptions" in
\fIACM Transactions on Programming Languages and Systems\fP,
Volume 2, No. 2, S. 173-190, April 1980.
.\" ==================================================
.IP "[CHK84]"
Thomas W. Christopher, Philip J. Hatcher, Ronald C. Kukuk,
.br
"Using dynamic programming to generate optimized code in a
Graham-Glanville style code generator" in
\fISIGPLAN Notices\fP,
Volume 19, No. 6, S. 25-36, Juni 1984.
.\" ==================================================
.IP "[Emm89]"
Helmut Emmelmann,
.br
\fIAutomatische Erzeugung effizienter Codegeneratoren\fP,
GMD-Studien Nr. 158,
Sankt Augustin, Gesellschaft f\*ur Mathematik und Datenverarbeitung mbH, 1989
.\" ==================================================
.IP "[GF82]"
Mahadevan Ganapathi, Charles N. Fischer,
.br
"Description-Driven Code Generation using Attribute Grammars" in
\fIProceedings of the 9th Annual ACM Symposium on Principals of Programming
Languages\fP,
Albuquerque, New Mexico, S. 108-119, 25-27 Januar 1982.
.\" ==================================================
.IP "[GF84]"
Mahadevan Ganapathi, Charles N. Fischer,
.br
"Attributed Linear Intermediate Representations for Retargetable Code
Generators" in
\fISoftware-Practice and Experience\fP,
Volume 14, No. 4, S. 347-364, April 1984.
.\" ==================================================
.IP "[GFH84]"
Mahadevan Ganapathi, Charles N. Fischer, John L. Hennessy,
.br
"Retargetable Compiler Code Generation" in
\fIComputing Surveys\fP,
Volume 14, No. 4, S. 573-592, Dezember 1982.
.\" ==================================================
.IP "[GG78]"
R. Steven Glanville, Susan L. Graham,
.br
"A New Method for Compiler code generation" in
\fIProceedings of the 5th ACM Symposium on Principals of Programming
Languages\fP,
Tucson, Arizona, S. 231-240, 23-25 Januar 1978.
.\" ==================================================
.IP "[Gra80]"
Susan L. Graham,
.br
"Table-Driven Code Generation" in
\fIIEEE Computer\fP,
No. 13, S. 25-34, August 1980.
.\" ==================================================
.IP "[Jan85]"
Hans-Stephan Jansohn,
.br
\fIAutomated generation of optimized code\fP,
GMD-Bericht Nr. 154,
M\*unchen/Wien, R. Oldenbourg Verlag, 1985.
.\" ==================================================
.IP "[Joh78]"
S. C. Johnson,
.br
"A Portable Compiler: Theory and Practice" in
\fIProceedings of the 5th ACM Symposium on Principals of Programming
Languages\fP,
Tucson, Arizona, S. 97-104, 23-25 Januar 1978.
.\" ==================================================
.IP "[Ste61]"
T. B. Steel, Jr.
.br
"A first version of UNCOL" in
\fIProceedings of the Western Joint Computer Conference\fP,
Los Angeles, California, S. 371-378, 9.-11. Mai 1961.
.\" ==================================================
.IP "[Str58]"
J. Strong, et al.,
.br
"The Problem of Programming Communication with Changing Machines:
A Proposed Solution" in
\fICommunications of the ACM,\fP
Volume 1, No. 8, S. 12-18, August 1958, Volume 1, No. 9, S. 9-15,
September 1958.
.\" ==================================================


Reply-To: <ceriel@cs.vu.nl> Ceriel Jacobs, Vrije Universiteit


Here are some references for the Amsterdam Compiler Kit.


%T The design of very fast portable compilers
%A A.S. Tanenbaum
%A M.F. Kaashoek
%A K.G. Langendoen
%A C.J.H. Jacobs
%J SIGPLAN Notices
%V 24
%N 11
%P 125-131
%D November 1989


%T Language- and Machine-independent Global Optimization on Intermediate Code
%A H.E. Bal
%A A.S. Tanenbaum
%J Computer Languages
%V 11
%N 2
%P 105-121
%D April 1986


%T Does anybody out there want to write HALF of a compiler?
%A A.S. Tanenbaum
%A E.G. Keizer
%A H. van Staveren
%J SIGPLAN Notices
%V 19
%N 8
%P 106-108
%D August 1984


%T A Practical Toolkit for Making Portable Compilers
%A A. S. Tanenbaum
%A H. van Staveren
%A E. G. Keizer
%A J. W. Stevenson
%J Communications of the ACM
%V 26
%N 9
%P 654-660
%D September 1983


%T A Unix Toolkit for Making Portable Compilers
%A A.S. Tanenbaum
%A H. van Staveren
%A E.G. Keizer
%A J.W. Stevenson
%J Proceedings USENIX conf.
%C Toronto, Canada
%V 26
%D July 1983
%P 255-261


%T Using Peephole Optimization on Intermediate Code
%A A.S. Tanenbaum
%A J.M. van Staveren
%A J.W. Stevenson
%J TOPLAS
%V 4
%N 1
%P 21-36
%D January 1982


From: Charlie Farnum <cfarnum@valhalla.cs.wright.edu>


Not all of these directly describe UNCOLs, but I feel they are
relevant to the subject. Each is followed by some brief comments.


%A Charles Farnum
%T Pattern-based Languages for Prototyping of Compiler Optimizers
%I |UCB|
%R |TR| UCB/CSD 90/608
%D |DEC| 1990
%K thesis


This is my dissertation. Chapter 3 describes a lambda-calculus based
IL schema. It briefly argues for the use of continuation captures and
applications as opposed to continuation passing style.


%A J. Strong
%A J. Olzatyn
%A J. Wegstein
%A O. Mock
%A A. Tritter
%A T. Steel
%T The Problem of Programming Communications with Changing Machines
%J |CACM|
%V 1
%N 8
%D |AUG| 1958
%P 12--18
%K UNCOL


The earliest UNCOL paper I know of, although they state the idea is
``nothing new''.


%A T. B. Steel~Jr.
%T A First Version of UNCOL
%J Western Joint Computer Conference
%D 1961


An early UNCOL paper describing an actual UNCOL, rather than just the
concept. Very interesting to see what they thought the problems would
be. One of the problems they spend a lot of time on is character sets.


%A Guy Lewis Steele~Jr.
%A Gerald Jay Sussman
%T LAMBDA: The Ultimate Imperative
%R AI Memo No. 353
%I |MIT| Artificial Intelligence Laboratories
%D March 1976


%A Guy Lewis Steele~Jr.
%T LAMBDA: The Ultimate Declarative
%R AI Memo No. 379
%I |MIT| Artificial Intelligence Laboratories
%D November 1976


Two fantastic papers that should be read as a group. Perhaps they
only preach to the converted, but I believe they argue very
successfully that lambda-based intermediate languages are the way to
go.


%A B. K. Haddon
%A W. M. Waite
%T Experience with the Universal Intermediate Language Janus
%J |SPE|
%V 8
%P 601-616
%D 1978
%K ir


What the title says.


%A Frances E. Allen
%A J. L. Carter
%A J. Fabri
%A Jeanne Ferrante
%A William H. Harrison
%A P. G. Loewner
%A L. H. Trevillyan
%T The Experimental Compiling System
%J |IBMJRD|
%V 24
%N 6
%D 1980
%P 695-715
%W ENGI TK7800.I14
%K ecs


The ECS project at IBM had a generic IL schema (based primarily on
procedure calls) that could be specialized to various machines and
source languages. This paper has a good explanation of the concept of
a ``schema''.


%A William Harrison
%T Formal Semantics of a Schematic Intermediate Language
%R |RC| 6271
%I |IBM| Yorktown Heights
%D |NOV| 1976
%K ir


The schema used in IBM's Experimental Compiler Systems project.


%A Bruce W. Leverett
%A Roderic G. G. Cattell
%A Steven O. Hobbs
%A Joseph M. Newcomer
%A Andrew H. Reiner
%A Brice R. Schatz
%A William A. Wulf
%T An Overview of the Production-Quality Compiler-Compiler Project
%J |IEEEC|
%D |AUG| 1980
%P 38-48
%X also |CMUCS| |TR|-79-105 |FEB| 1979
%K pqcc


PQCC was supposed to be a generic, complete compiler-compiler system,
and also used the schema idea (using a heavily-parameterized
intermediate language that could be specialized to certain
languages/machines).


%A Richard Andrews Kelsey
%T Compilation by Program Transformation
%I Yale University
%R PhD |DISS|
%D |MAY| 1989
%K thesis


Validates use of a lambda calculus based IL for normal language
(Pascal) compilation.


%A Matthias Felleisen
%T The Calculi of Lambda-v-CS Conversion: A Syntactic Theory of Control
and State in Imperative Higher-order Programming Languages
%I Indiana University
%R PhD |DISS|
%D |AUG| 1987
%K thesis


This is sort of off the topic, but strongly argues that explict
imperative control and storage concepts can be successfully added to
lambda calculus without destroying nice theoretical properties.


From: cwf@research.att.com (Chris Fraser)


The reference


Jack W. Davidson and Christopher W. Fraser. Code selection through
object code optimization. TOPLAS 6(4):505-526, 10/84.


is not about UNCOL per se, but Section 2.1 contains some material that
may interest those who are interested in UNCOL.


From: wjw@eb.ele.tue.nl (Willem Jan Withagen)


The reference is rather vague, since I' recieved a copy of a manuscript
created at stanford in the M.J. Flynn lab, it has nothing what so ever
of author/origin info in it, but it is the definition of Ucode
a variant of P-code they use in their Architects WorkBench, a tool
for modeling processor and systems.
Unfortunatly I do not have the complete document, and I haven't
found a person yet to ask for a more complete version.


@techreport( UcodeManual
,title = "U-code Manual"
,abstract= " The purpose of this document is to describe the
intermediate language emmited by the Pascal, Pascal*, and fortran compilers
developed or the S-1 project at Stanford University. This language can be
interpreted, but is ussually translated into machine code of a target
machine; this document is primarily geared towrad the latter. The language
is called U-code, and is a descendant of the venerable P-code emitted by
many other Pascal compilers. It comes in to forms: a text format, and a
binary format.


This document contains six parts:
1) A U-code primer
2) An alphabetical listing of U-code instructions
3) A definition of the symbol table file used with
the U-code system.
4) A definition of binary U-code
5) A description of a U-code reader/writer
6) A quick reference guide for U-code
"
)


From: pardo@cs.washington.edu (David Keppel)


3 Citations Follow:
%A M. E. Conway
%T Proposal for an UNCOL
%J CACM
%V 1
%N 10
%D OCT 1958
%P 5-8


%A T. B. Steel
%T UNCOL: The Myth and the Fact
%K uncol
%J Annual Review Automatic Programming
%E R. Goodman
%V 2
%P 325-344
%D 1960
%K intermediate representation


%A T. B. Steel
%T A First Version of UNCOL
%J WJCC
%V 19
%P 371-378
%D 1961
%K intermediate representation


--

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