Jeffery C.The implementation of Icon and Unicon.2004

x

xi

Preface

This book is a compendium of all documents that describe the implementation of the Icon and Unicon programming languages, an implementation that started with Icon version 3 on a PDP­11 sometime near the year 1980.

Organization of This Book

This book consists of four parts. The first part, Chapters 1­12, present the core of the implementation, focusing on the Icon virtual machine interpreter and runtime system. This material was formerly published as the Implementation of the Icon Programming Language, by Ralpha and Madge T. Griswold; at that time it documented Icon Version 6. Many of the details in this book became obsolete with the rewriting of the runtime system for Icon Version 8. In editing this work, I have attempted to preserve the authors' style and intent, while updating it to document Icon Version 9.4. I have specifically avoided introducing Unicon implementation material in these chapters, and use blue­colored text when necessary to discuss Unicon issues and differences, so that Part I should remain useful to people who prefer to use the Icon implementation, not just those working with Unicon.

Part II, in Chapters 13­19, describes the optimizing compiler, iconc, and the structuring of the runtime system to support it. This work is the brainchild of Ken Walker, whose dissertation is presented here, along with his technical reports describing the runtime language RTL and its translator, rtt.

Part III describes the implementation of Unicon and the many extensions that transformed the language from a string­and­list­processing language into a modern object­oriented, network­savvy, graphics­rich applications language. Part IV consists of essential reference material presented in several Appendixes.

Acknowledgements

This book would not be possible without the generous contributions and consent of the primary authors of the Icon language implementation documents, Ralph and Madge Griswold, and Kenneth Walker. Ralph Griswold re­scanned and corrected his Icon implementation book manuscript in order to place it in the public domain on the web, a large, selfless, thankless, and valuable undertaking. Ken Walker found and shared his original nroff dissertation source files.

Susie Jeffery provided crucial assistance in the OCR reconstruction of Icon implementation book manuscript from the public domain scanned images. Mike Kemp was a valuable volunteer proofreader in that effort. Responsibility for remaining typographical errors rests with me.

Thanks to the rest of the people who contributed code to the Icon Project over a period of many years and many Ph.D. and M.S. degrees.

The editor wishes to acknowledge generous support from the National Library of Medicine. This work was also supported in part by the National Science Foundation

xii

under grants CDA­9633299, EIA­0220590 and EIA­9810732, and the Alliance for Minority Participation.

Clinton Jeffery, Las Cruces, November 2004

Acknowledgements for Chapters 1-12

The implementation of Icon described in Part I owes much to previous work and in particular to implementations of earlier versions of Icon. Major contributions were made by Cary Coutant, Dave Hanson, Tim Korb, Bill Mitchell, a Steve Wampler. Walt Hansen, Rob McConeghy, and Janalee O'Bagy also made significant contributions to this work.

The present system has benefited greatly from persons who have installed Icon on a variety of machines and operating systems. Rick Fonorow, Bob Goldberg, Chris Janton, Mark Langley, Rob McConeghy, Bill Mitchell, Janal O'Bagy, John Polstra, Gregg Townsend, and Cheyenne Wills have made substantial contributions in this area.

The support of the National Science Foundation under Grants MCS7 01397, MCS79­ 03890, MCS81­0l916, DCR­8320138, DCR­840183I, at DCR­8502015 was instrumental in the original conception of Icon and has bee invaluable in its subsequent development.

A number of persons contributed to this book. Dave Gudeman, Dave Ha son, Bill Mitchell, Janalee O'Bagy, Gregg Townsend, and Alan Wendt contr buted to the exercises that appear at the ends of chapters and the projects given

Appendix E. Kathy Cummings, Bill Griswold, Bill Mitchell, Katie Morse, Mil Tharp, and Gregg Townsend gave the manuscript careful readings and made numerous suggestions. Janalee O'Bagy not only read the manuscript but also supplied concepts for presenting and writing the material on expression evaluation.

Finally, Dave Hanson served as an enthusiastic series editor for this book. His perceptive reading of the manuscript and his supportive and constructive suggestions made a significant contribution to the final result.

Acknowledgements for Chapters 13-24

I would like to thank Ralph Griswold for acting as my research advisor. He provided the balance of guidance, support, and freedom needed for me to complete this research. From him I learned many of the technical writing skills I needed to compose this dissertation. I am indebted to him and the other members of the Icon Project who over the years have contributed to the Icon programming language that serves as a foundation of this research. I would like to thank Peter Downey and Saumya Debray for also serving as members on my committee and for providing insightful criticisms and suggestions for this dissertation. In addition, Saumya Debray shared with me his knowledge of abstract interpretation, giving me the tool I needed to shape the final form of the type inferencing system.

I have received help from a number of my fellow graduate students both while they were still students and from some after they graduated. Clinton Jeffery, Nick Kline, and Peter Bigot proofread this dissertation, providing helpful comments. Similarly, Janalee O'Bagy, Kelvin Nilsen, and David Gudeman proofread earlier reports that served as a basis for several of the chapters in this dissertation. Janalee O'Bagy's own work on compiling Icon provided a foundation for the compiler I developed. Kelvin Nilsen applied my liveness

xiii

analysis techniques to a slightly different implementation model, providing insight into dependencies on execution models.

1

Compendium Introduction

The implementation of Icon is now very old. It inherits ideas from earlier languages, and introduces many of its own. The implementation documentation traditionally revolved around the virtual machine and its runtime system; other parts of the implementation were documented in scattered technical reports or not at all, other than the source code. This volume changes all that, by bringing all the implementation documents together in a single volume.

Icon's public­domain implementation is fairly efficient; for example Keith Waclena of the University of Chicago documented a factor of 4 or more speed advantage of Icon versus Python on multiple benchmarks, and that was for the Icon virtual machine interpreter; the Icon optimizing compiler adds another factor of 2­5 or more in faster execution speed. The design decisions that achieve Icon's very­high level language features (such as generators and goal­directed evaluation) with acceptable performance make for an interesting study. This book is intended for those wanting to learn the implementation in order to add features, improve performance, learn about compilers in general, or glean ideas for their own independent programming language efforts.

Icon traditionally consisted of a virtual machine translator, a linker, and a virtual machine interpreter. This early organization was later supplemented with several additional components, while some of the existing components were merged. The trends I hope to see in the future are: merger of components, and gradual replacement of C­based components with ones written in Unicon.

How Many Compilers?

The figure below shows two symmetrically­organized sets of tools. The tools on the left are the compilers end­users employ to translate Icon or Unicon into executable machine code, while the tools on the right show how the underlying run­time system needed in order to execute those programs is built. Of the six rectangles, four are compilers that perform distinct tasks specific to this programming language family. The front­end translation tool, named unicon, is a preprocessor that translates Unicon code into Icon code. Its primary functions are to translate object­orientation (classes, single and multiple inheritance, and packages) down to underlying imperative constructs. Unicon is written in Unicon. Icont and iconc compile Icon code down to virtual machine and C code, respectively. They share a few common front­end components, but are largely independent. Iconx is the name of the Icon (and Unicon) virtual machine, which mostly consists of a large collection of complex high­level data structure and I/O facilities which are built­in to these languages. Most of the source code for iconx is also used in rt.a, the runtime library that is linked to Icon programs compiled with iconc.

Figure CI­1: three compilers for users (left), one (rtt) for the language implementors

2

3

Part I: The Implementation of the Icon

Programming Language

by Ralph Griswold and Madge Griswold

4