Jeffery C.The implementation of Icon and Unicon.2004
.pdfThe
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 FrontCover 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 jeffery@cs.nmsu.edu.
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 RunTime Structures............................................................... |
38 |
|
3.5 |
The RunTime 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 |
StackBased 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 GoalDirected 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 CoExpressions................................................ |
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 CoExpressions.................................................................................................... |
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 CoExpression 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: RunTime 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 GoalDirected 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 Runtime 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 CoExpression 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 Inlining of Builtin Operations.................................................. |
253 |
22.3 |
Heuristic for Deciding to Inline.......................................................................... |
255 |
22.4 |
Inlining 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 PlatformIndependence.................................................... |
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 CoExpressions............................................................................................ |
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 CoExpression 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 RunTime Language .................................................................. |
388 |
G.1 Operation Documentation .................................................................................... |
388 |
G.2 Types of Operations ............................................................................................. |
388 |
G.3 Declare Clause...................................................................................................... |
390 |
G.4 Actions ................................................................................................................. |
391 |