The Implementation of Icon and Unicon

Contents......Page 3
Preface......Page 16
Compendium Intro......Page 17
Implementation of Icon......Page 19
Introduction......Page 20
Implementing Programming Languages......Page 21
The Background for Icon......Page 22
Icon Language Overview......Page 24
Data Types......Page 25
Expression Evaluation......Page 27
Csets and Strings......Page 34
String Scanning......Page 36
Lists......Page 37
Sets......Page 39
Records......Page 40
Procedures......Page 41
Co-Expressions......Page 46
Diagnostic Facilities......Page 48
Language Features and the Implementation......Page 50
Organization of the Implementation......Page 54
Components of the Implementation......Page 55
The Translator......Page 56
The Linker......Page 57
The Run-Time System......Page 58
Values & Variables......Page 61
Descriptors......Page 62
Strings......Page 63
Integers......Page 64
Blocks......Page 65
Variables......Page 66
Operations on Variables......Page 67
Trapped Variables......Page 68
Keyword Variables......Page 69
Descriptors......Page 70
Blocks......Page 71
Defined Constants......Page 72
RTL Coding......Page 74
Strings & Csets......Page 78
Representation of Strings......Page 79
Concatenation......Page 80
Substrings......Page 83
Assignment to Subscripted Strings......Page 84
Mapping......Page 86
Csets......Page 90
Structures for Lists......Page 93
Queue and Stack Access......Page 97
Positional Access......Page 105
Arrays (Unicon only)......Page 108
Sets & Tables......Page 111
Data Organization for Sets......Page 112
Set Operations......Page 114
Data Organization for Tables......Page 115
Hashing Functions......Page 118
Stack-Based Evaluation......Page 126
Virtual Machine Instructions......Page 127
Constants......Page 128
Identifiers......Page 129
Operators......Page 137
Functions......Page 139
Self-Modifying Instructions......Page 140
The Interpreter Loop......Page 141
Interpreter State Variables......Page 143
Expression Evaluation......Page 145
Bounded Expressions......Page 146
Expression Frames......Page 148
Failure......Page 150
Generators and Goal-Directed Evaluation......Page 153
Alternation......Page 166
Repeated Alternation......Page 168
Limitation......Page 169
Iteration......Page 170
String Scanning......Page 171
Invocation Expressions......Page 177
Procedure Blocks......Page 178
Argument Processing......Page 181
Function Invocation......Page 182
Procedure Invocation......Page 185
Co-Expressions......Page 187
Storage Management......Page 195
Memory Layout......Page 197
Allocation......Page 200
Strings......Page 201
Garbage Collection......Page 202
The Basis......Page 203
The Location Phase......Page 204
Pointer Adjustment and Compaction......Page 214
Collecting Co-Expression Blocks......Page 224
Multiple Regions......Page 225
Storage Requirements during Garbage Collection......Page 226
Predictive Need......Page 227
Type Checking and Conversion......Page 233
Dereferencing and Assignment......Page 238
Dereferencing......Page 239
Assignment......Page 241
Files......Page 247
Reading and Writing Data......Page 248
Diagnostic Facilities......Page 249
Optimizing Compiler for Icon......Page 252
Preface......Page 253
Motivation......Page 254
Type Inferencing......Page 255
Liveness Analysis......Page 256
Analyzing Goal-Directed Evaluation......Page 257
Translation Model......Page 259
Intermediate Results......Page 260
Executable Code......Page 261
Motivation......Page 268
Abstract Interpretation......Page 269
Collecting Semantics......Page 272
Model 1: Eliminating Control Flow Information......Page 275
Model 2: Decoupling Variables......Page 277
Model 3: A Finite Type System......Page 280
Liveness Analysis of Intermediate Values......Page 284
Implicit Loops......Page 285
Liveness Analysis......Page 286
An Attribute Grammar......Page 290
Primary Expressions......Page 291
Operations with Subexpressions......Page 292
Control Structures......Page 294
Components of the Compiler......Page 297
The Run-time System......Page 298
The Implementation Language......Page 299
Standard and Tailored Operation Implementations......Page 302
Compiler Phases......Page 304
Naive Optimizations......Page 306
Code Generation for Procedures......Page 307
The Representation of Types and Stores......Page 308
A Full Type System......Page 309
Procedure Calls and Co-Expression Activations......Page 314
The Flow Graph and Type Computations......Page 316
Code Generation......Page 320
Translating Icon Expressions......Page 323
Signal Handling......Page 327
Temporary Variable Allocation......Page 330
Naive Code Generation......Page 338
Success Continuations......Page 339
Iconc's Peephole Optimizer......Page 341
Invocation of Procedures......Page 345
Invocation and In-lining of Built-in Operations......Page 346
Heuristic for Deciding to In-line......Page 348
In-lining Success Continuations......Page 349
Parameter Passing Optimizations......Page 351
Assignment Optimizations......Page 354
Expression Optimizations......Page 357
Program Execution Speed......Page 360
Code Size......Page 362
Scalable Type Inferencing......Page 364
The Type Representation......Page 365
Type Inferencing......Page 366
A Copy-on-Write Type Vector Pool......Page 367
Bit Vector Hashing......Page 368
Hash Halving......Page 369
Space......Page 373
Time......Page 374
Measuring the Techniques......Page 375
Collision Rates......Page 376
Conclusions......Page 377
Areas Where Iconc Can Be Improved......Page 379
Intermediate Code Representation......Page 380
How Code is Generated......Page 381
Redundant Function Calls......Page 384
Tended Descriptor Tables......Page 385
Analyzing Literal Assignments......Page 386
New Functions......Page 390
Loop Unrolling......Page 392
Results......Page 393
Execution Speed......Page 394
Code Size......Page 395
Analysis of Intermediate Code Optimizations......Page 396
Conclusion and Future Optimizations......Page 397
Summary of Part II......Page 402
Future Work......Page 403
Implementation of Unicon......Page 405
Lexical Analysis......Page 406
Error Handling and Debugging......Page 407
Big-inhale Input......Page 408
Semicolon Insertion......Page 409
The Real Lexical Analyzer Function, yylex2()......Page 411
Unicon Parser......Page 413
Unicon Preprocessor......Page 415
Semantic Analysis......Page 417
Object oriented Facilities......Page 422
Implementing Multiple Inheritance in Unicon......Page 425
Unicon's Progend() revisited......Page 429
Other OOP Issues......Page 430
On Public Interfaces and Runtime Type Checking......Page 431
Simultaneous Input from Different File Types......Page 432
The Discipline......Page 433
Exception Handling......Page 434
Organization......Page 438
ISQLFile type......Page 439
Graphics Source Files Summary......Page 441
Structures Defined in graphics.h......Page 443
Window Manipulation in rxwin.ri and rmswin.ri......Page 444
Event Processing......Page 445
Color Management......Page 446
3D Facilities Requirements......Page 447
Textures......Page 448
Texture Coordinates......Page 449
Graphics Facilities Porting Reference......Page 450
Installing, Configuring, and Compiling the Source Code......Page 460
Overview......Page 462
Design Considerations......Page 463
Translation Model......Page 465
Syntax Analysis......Page 466
Semantic Analysis......Page 470
Syntax Analysis......Page 471
Semantic Analysis......Page 474
Representation of Class Instances......Page 477
The Proposed Optimization......Page 482
Invocations......Page 483
The Proposed Optimization......Page 486
Results......Page 487
Results......Page 489
Invocations......Page 490
Space Savings In Compiled Targets......Page 492
General Programs......Page 493
Limitations......Page 495
Scalability......Page 496
Lack of Introspection......Page 497
Disambiguation......Page 498
Potential Improvements......Page 499
Conclusion......Page 500
Concurrency & Thread-Safety......Page 506
Critical Regions and Mutexes......Page 507
Thread Communication......Page 510
Send and Receive Operators......Page 511
Inbox/Outbox and the Attrib() Function......Page 512
Blocking Send and Receive......Page 513
Self-Modifying Instructions......Page 515
Input/Output Sub-system......Page 516
Allocation and Separate Heaps......Page 517
Garbage Collection......Page 518
Dynamic Loading and the Program State......Page 520
Filtering: Event Masks and Value Masks......Page 525
Instrumented vs. Uninstrumented Run-time Functions......Page 527
--- Appendices......Page 0
Values......Page 529
Long Integers......Page 530
Csets......Page 531
Lists......Page 532
Tables......Page 533
Procedures......Page 534
Trapped Variables......Page 536
Co-Expressions......Page 537
Virtual Machine Instructions......Page 540
Identifiers......Page 546
Keywords......Page 547
Operators......Page 548
Calls......Page 550
Compound Expressions & Conjunction......Page 551
Selection Expressions......Page 552
Generative Control Structures......Page 553
Loops......Page 555
String Scanning......Page 557
Procedure Returns......Page 558
Co-Expression Creation......Page 559
File Organization......Page 560
Adding Functions......Page 561
Returning from a Function......Page 562
Type Checking and Conversion......Page 564
Constructing New Descriptors......Page 565
Storage Allocation......Page 566
D.2.7 Storage Management Considerations......Page 568
Header Files......Page 569
Adding Data Types......Page 570
Structures......Page 571
D.3.3 Information Needed for Storage Management......Page 572
Changes to Existing Code......Page 573
Defined Constants and Macros......Page 574
Macros......Page 575
Comparison......Page 576
Type Conversion......Page 577
Allocation......Page 578
Operations on Structures......Page 579
Miscellaneous Operations......Page 580
Debugging......Page 581
The Type Specification System......Page 582
Simple Value Types......Page 583
Aggregate Types......Page 585
Keyword Variable Types......Page 586
The Complete Grammar for the Type Specification System......Page 589
A check list for adding types(on one page for easy photocopying)......Page 590
Solutions......Page 591
Operation Documentation......Page 599
Types of Operations......Page 600
Actions......Page 602
Type Checking and Conversions......Page 603
Scope of Conversions......Page 606
Type Names......Page 607
Including C Code......Page 608
Abstract Type Computations......Page 609
C Extensions......Page 613
Declarations......Page 614
Return Statements......Page 616
Symbols......Page 619
Refs......Page 641
Index......Page 644