Jeffery C.The implementation of Icon and Unicon.2004

The

Implementation of

Icon and Unicon

a Compendium

Clinton Jeffery, editor

ii

The Implementation

of Icon and Unicon

Ralph and Madge T. Griswold

Kenneth W. Walker

Clinton L. Jeffery

ii

Copyright © 2004 Clinton Jeffery

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front­Cover Texts, and no Back­ Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License".

Portions of this document ("The Implementation of the Icon Programming Language") are in the public domain and not subject to the above copyright or license.

Portions of this document ("An Optimizing Compiler for Icon") are copyrighted by Kenneth Walker and appear in edited form in this document with the express permission of the author.

This is a draft manuscript dated 11/8/2004. Send comments and errata to [e-mail].

This document was prepared using OpenOffice.org 1.1.

		iii
Contents
Preface................................................................................................................................		xi
Organization of This Book.............................................................................................		xi
Acknowledgements.........................................................................................................		xi
Compendium Introduction...................................................................................................		1
How Many Compilers?....................................................................................................		1
Part I: The Implementation of the Icon Programming Language........................................		3
Chapter 1: Introduction........................................................................................................		5
1.1	Implementing Programming Languages....................................................................	5
1.2	The Background for Icon...........................................................................................	6
Chapter 2: Icon Language Overview...................................................................................		9
2.1	The Icon Programming Language.............................................................................	9
2.2	Language Features and the Implementation............................................................	31
EXERCISES..............................................................................................................		33
Chapter 3: Organization of the Implementation................................................................		35
3.1	The Icon Virtual Machine........................................................................................	35
3.2	Components of the Implementation.........................................................................	36
3.3	The Translator..........................................................................................................	37
3.4	The Linker................................................................................................................	38
3.4.1 Scope Resolution..............................................................................................		38
3.4.2 Construction of Run­Time Structures...............................................................		38
3.5	The Run­Time System.............................................................................................	38
EXERCISES..............................................................................................................		39
Chapter 4: Values and Variables........................................................................................		41
4.1	Descriptors...............................................................................................................	42
4.1.1 Strings...............................................................................................................		43
4.1.2 The Null Value..................................................................................................		43
4.1.3 Integers..............................................................................................................		43
4.3	Variables..................................................................................................................	45
4.3.1 Operations on Variables....................................................................................		46
4.3.2 Trapped Variables.............................................................................................		47
4.4	Descriptors and Blocks in C....................................................................................	48
4.4.1 Descriptors........................................................................................................		48
4.4.2 Blocks...............................................................................................................		49
4.4.3 Defined Constants.............................................................................................		50
4.4.4 C Coding Conventions......................................................................................		51
EXERCISES..............................................................................................................		53
Chapter 5: Strings and Csets..............................................................................................		54
5.1	Strings......................................................................................................................	54
5.1.1 Representation of Strings..................................................................................		54
5.1.2 Concatenation...................................................................................................		55
5.1.3 Substrings..........................................................................................................		57
5.1.4 Assignment to Subscripted Strings...................................................................		58
5.1.5 Mapping............................................................................................................		59
5.2	Csets.........................................................................................................................	61
EXERCISES..............................................................................................................		62
Chapter 6: Lists..................................................................................................................		64
6.1	Structures for Lists...................................................................................................	64
6.2	Queue and Stack Access..........................................................................................	67

iv
6.3	Positional Access.....................................................................................................	73
Chapter 7: Sets and Tables.................................................................................................		76
7.1	Sets...........................................................................................................................	76
7.1.1 Data Organization for Sets................................................................................		76
7.1.2 Set Operations...................................................................................................		78
7.2	Tables.......................................................................................................................	79
7.2.1 Data Organization for Tables............................................................................		79
7.3	Hashing Functions...................................................................................................	82
EXERCISES..............................................................................................................		84
Chapter 8: The Interpreter..................................................................................................		87
8.1	Stack­Based Evaluation...........................................................................................	87
8.2	Virtual Machine Instructions...................................................................................	88
8.2.1 Constants...........................................................................................................		88
8.2.2 Identifiers..........................................................................................................		89
8.3	Operators..................................................................................................................	96
8.2.4 Functions...........................................................................................................		97
8.3	The Interpreter Proper..............................................................................................	98
8.3. 1 The Interpreter Loop........................................................................................		98
Chapter 9: Expression Evaluation......................................................................................		99
9.1	Bounded Expressions...............................................................................................	99
9.1.1 Expression Frames..........................................................................................		101
9.2	Failure....................................................................................................................	102
9.3	Generators and Goal­Directed Evaluation.............................................................	105
9.4	Generative Control Structures...............................................................................	114
9.4.1 Alternation......................................................................................................		114
9.4.2 Repeated Alternation......................................................................................		116
9.4.3 Limitation........................................................................................................		116
9.5	Iteration..................................................................................................................	117
9.6	String Scanning......................................................................................................	118
Chapter 10: Functions, Procedures, and Co­Expressions................................................		123
10.1 Invocation Expressions........................................................................................		123
10.2 Procedure Blocks.................................................................................................		124
10.3 Invocation............................................................................................................		125
10.3.1 Argument Processing....................................................................................		125
10.3.2 Function Invocation......................................................................................		127
10.3.3 Procedure Invocation....................................................................................		128
10.4 Co­Expressions....................................................................................................		130
EXERCISES............................................................................................................		135
Chapter 11: Storage Management....................................................................................		137
11.1 Memory Layout...................................................................................................		138
11.2 Allocation.............................................................................................................		140
11.2.1 The Static Region..........................................................................................		140
11.2.2 Blocks...........................................................................................................		141
11.2.3 Strings...........................................................................................................		141
11.3 Garbage Collection..............................................................................................		142
11.3.1 The Basis.......................................................................................................		142
11.3.2 The Location Phase.......................................................................................		143
11.3.3 Pointer Adjustment and Compaction............................................................		149
11.3.4 Collecting Co­Expression Blocks.................................................................		156
11.3.5 Expansion of the Allocated Regions.............................................................		156

		v
11.3.6 Storage Requirements during Garbage Collection		.......................................157
11.4	Predictive Need....................................................................................................	157
EXERCISES............................................................................................................		160
Chapter 12: Run­Time Support Operations.....................................................................		164
12.1	Type Checking and Conversion...........................................................................	164
12.2	Dereferencing and Assignment............................................................................	167
12.2.1 Dereferencing................................................................................................		168
12.2.2 Assignment...................................................................................................		170
12.3	Input and Output..................................................................................................	174
12.3.1 Files...............................................................................................................		175
12.3.2 Reading and Writing Data............................................................................		176
12.4	Diagnostic Facilities............................................................................................	176
EXERCISES............................................................................................................		177
Part II: An Optimizing Compiler for Icon.......................................................................		179
Preface to Part II..........................................................................................................		180
Chapter 13: The Optimizing Compiler............................................................................		181
13.1	Motivation............................................................................................................	181
13.2	Type Inferencing..................................................................................................	181
13.3	Liveness Analysis ...............................................................................................	183
13.4	Analyzing Goal­Directed Evaluation...................................................................	183
Chapter 14: The Translation Model.................................................................................		185
14.1	Data Representation.............................................................................................	185
14.2	Intermediate Results............................................................................................	186
14.3	Executable Code..................................................................................................	187
Chapter 15: The Type Inferencing Model.......................................................................		193
15.1	Motivation............................................................................................................	193
15.2	Abstract Interpretation ........................................................................................	194
15.3	Collecting Semantics...........................................................................................	195
15.4	Model 1: Eliminating Control Flow Information................................................	198
15.5	Model 2: Decoupling Variables...........................................................................	200
15.6	Model 3: A Finite Type System...........................................................................	202
Chapter 16: Liveness Analysis of Intermediate Values...................................................		205
16.1	Implicit Loops......................................................................................................	205
16.2	Liveness Analysis................................................................................................	207
16.3	An Attribute Grammar.........................................................................................	210
16.4	Primary Expressions............................................................................................	211
16.5	Operations with Subexpressions..........................................................................	211
16.6	Control Structures................................................................................................	213
Chapter 17: Overview of the Compiler............................................................................		216
17.1	Components of the Compiler...............................................................................	216
17.2	The Run­time System..........................................................................................	216
17.3	The Implementation Language ...........................................................................	217
17.4	Standard and Tailored Operation Implementations.............................................	220
Chapter 18: Organization of Iconc...................................................................................		221
18.1	Compiler Phases..................................................................................................	221
18.2	Naive Optimizations............................................................................................	222
18.3	Code Generation for Procedures..........................................................................	223
Chapter 19: The Implementation of Type Inferencing....................................................		225
19.1	The Representation of Types and Stores.............................................................	225
19.2	A Full Type System.............................................................................................	226

vi
19.3	Procedure Calls and Co­Expression Activations.................................................	230
19.4	The Flow Graph and Type Computations............................................................	231
Chapter 20: Code Generation...........................................................................................		235
20.1	Translating Icon Expressions...............................................................................	237
20.2	Signal Handling...................................................................................................	240
20.3	Temporary Variable Allocation...........................................................................	242
Chapter 21: Control Flow Optimizations.........................................................................		248
21.1	Naive Code Generation........................................................................................	248
21.2	Success Continuations.........................................................................................	248
21.3	Iconc's Peephole Optimizer.................................................................................	250
Chapter 22: Optimizing Invocations................................................................................		253
22.1	Invocation of Procedures.....................................................................................	253
22.2	Invocation and In­lining of Built­in Operations..................................................	253
22.3	Heuristic for Deciding to In­line..........................................................................	255
22.4	In­lining Success Continuations..........................................................................	256
22.5	Parameter Passing Optimizations........................................................................	257
22.6	Assignment Optimizations...................................................................................	259
Chapter 23: Performance of Compiled Code...................................................................		262
23.1	Expression Optimizations....................................................................................	262
23.2	Program Execution Speed....................................................................................	264
23.3	Code Size.............................................................................................................	265
Chapter 24: Future Work on the Compiler......................................................................		267
24.1 Summary..............................................................................................................		267
24.2	Future Work.........................................................................................................	267
Chapter 25: Optimizing the Icon Compiler.....................................................................		271
25.1	Introduction..........................................................................................................	271
Areas Where Iconc Can Be Improved.....................................................................		271
Changes to the Compiler Source..............................................................................		272
25.2	Optimizing the Type Representation...................................................................	273
New Type Representation........................................................................................		274
How Type Allocation Works...................................................................................		275
Reorganizing the Code.............................................................................................		276
New Functions.........................................................................................................		276
Other Changes..........................................................................................................		277
Results of Type Optimization..................................................................................		278
25.3	Optimizing the Generated Code..........................................................................	278
Intermediate Code Representation...........................................................................		278
Redundant Function Calls........................................................................................		281
Icon Literals and Constant Propagation...................................................................		282
New Functions.........................................................................................................		286
Variable Initialization..............................................................................................		287
Loop Unrolling.........................................................................................................		287
Results of Code Generation Optimizations..............................................................		288
25.4	Results..................................................................................................................	288
Type Representation................................................................................................		289
Code Generation......................................................................................................		290
Analysis of Intermediate Code Optimizations.........................................................		292
Future Optimizations...............................................................................................		293
Part III: The Implementation of Unicon..........................................................................		297
Chapter 26: The Unicon Translator.................................................................................		299

		vii
26.1	Overview..............................................................................................................	299
26.2	Lexical Analysis..................................................................................................	299
26.3	The Unicon Parser...............................................................................................	305
Syntax Error Handling ............................................................................................		306
26.4	The Unicon Preprocessor.....................................................................................	306
26.5	Semantic Analysis................................................................................................	308
26.6	Object Oriented Facilities ...................................................................................	312
Implementing Multiple Inheritance in Unicon .......................................................		315
Unicon's Progend() revisited ...................................................................................		317
Other OOP Issues.....................................................................................................		318
An Aside on Public Interfaces and Runtime Type Checking .................................		318
Chapter 27: Portable 2D and 3D Graphics......................................................................		320
27.1	Window Systems and Platform­Independence....................................................	320
27.2	Structures Defined in graphics.h..........................................................................	321
27.3	Platform Macros and Coding Conventions..........................................................	322
27.4	Window Manipulation in rxwin.ri and rmswin.ri................................................	323
Window Creation and Destruction...........................................................................		323
Event Processing......................................................................................................		324
Resource Management.............................................................................................		324
Memory Management and r*rsc.ri Files..................................................................		325
Color Management...................................................................................................		325
Font Management....................................................................................................		325
27.6	External Image Files and Formats......................................................................	325
27.7	Implementation of 3D Facilities..........................................................................	325
3D Facilities Requirements .....................................................................................		326
Files..........................................................................................................................		326
Redrawing Windows................................................................................................		326
Textures....................................................................................................................		326
Texture Coordinates.................................................................................................		327
27.8	Graphics Facilities Porting Reference................................................................	328
26.9	The X Implementation.........................................................................................	337
26.10 The MS Windows Implementation....................................................................		337
Installing, Configuring, and Compiling the Source Code........................................		338
Chapter 28: Networking, Messaging and the POSIX Interface.......................................		340
28.1	Networking Facilities...........................................................................................	340
28.2	Messaging Facilities............................................................................................	340
The Transfer Protocol Library.................................................................................		340
Libtp Architecture....................................................................................................		340
The Discipline..........................................................................................................		340
Exception Handling.................................................................................................		341
Part IV: Appendixes.........................................................................................................		344
Appendix A: Data Structures...........................................................................................		346
A.1 Descriptors............................................................................................................		346
A.1.1 Values.............................................................................................................		346
A.1.2 Variables........................................................................................................		347
A.2 Blocks...................................................................................................................		347
A.2.1 Long Integers.................................................................................................		347
A.2.2 Real Numbers.................................................................................................		347
A.2.3 Csets...............................................................................................................		347
A.2.4 Lists................................................................................................................		348

viii
A.2.5 Sets.................................................................................................................	349
A.2.6 Tables.............................................................................................................	350
A.2.7 Procedures......................................................................................................	350
A.2.8 Files................................................................................................................	352
A.2.9 Trapped Variables..........................................................................................	352
A.2.10 Co­Expressions............................................................................................	353
Appendix B: Virtual Machine Instructions......................................................................	357
Appendix C: Virtual Machine Code................................................................................	361
C.1 Identifiers..............................................................................................................	361
C.2 Literals...................................................................................................................	361
C.3 Keywords..............................................................................................................	362
C.4 Operators...............................................................................................................	362
C.5 Calls.......................................................................................................................	364
C.6 Compound Expressions and Conjunction.............................................................	364
C.7 Selection Expressions............................................................................................	365
C.8 Negation................................................................................................................	366
C.9 Generative Control Structures...............................................................................	366
C.10 Loops...................................................................................................................	368
C.11 String Scanning...................................................................................................	369
C.12 Procedure Returns...............................................................................................	370
C.13 Co­Expression Creation......................................................................................	370
Appendix D: Adding Functions and Data Types.............................................................	372
D.1 File Organization..................................................................................................	372
D.2 Adding Functions..................................................................................................	372
D.2.1 Function Declarations....................................................................................	373
D.2.2 Returning from a Function.............................................................................	373
D.2.3 Type Checking and Conversion.....................................................................	375
D.2.4 Constructing New Descriptors.......................................................................	376
D.2.5 Default Values................................................................................................	376
D.2.6 Storage Allocation..........................................................................................	377
D.2.7 Storage Management Considerations.............................................................	378
D.2.8 Error Termination..........................................................................................	378
D.2.9 Header Files...................................................................................................	379
D.2.10 Installing a New Function............................................................................	379
D.3 Adding Data Types...............................................................................................	379
D.3.1 Type Codes....................................................................................................	380
D.3.2 Structures.......................................................................................................	380
D.3.3 Information Needed for Storage Management...............................................	380
D.3.4 Changes to Existing Code..............................................................................	381
D.4.1 Defined Constants..........................................................................................	383
D.4.2 Macros............................................................................................................	383
D.5 Support Routines...................................................................................................	384
D.5.1 Comparison....................................................................................................	384
Appendix E: Projects.......................................................................................................	386
Appendix F: Solutions to Selected Exercises..................................................................	387
Appendix G: The RTL Run­Time Language ..................................................................	388
G.1 Operation Documentation ....................................................................................	388
G.2 Types of Operations .............................................................................................	388
G.3 Declare Clause......................................................................................................	390
G.4 Actions .................................................................................................................	391