Contents

1 : Introduction

1.1 Evolution Of Language Systems
1.2 The Java Scheme: Bytes
1.3 A New Approach: Trees
1.4 Trees Or Bytes?

2 : A Reduced Java Model

2.1 Concrete Lexicon and Syntax
2.2 Identifiers

2.2.1 Qualified Identifiers

2.3 Literals
2.4 Types And Values

2.4.1 Primitive Types And Values
2.4.2 Operators On Integral Values
2.4.3 Operators On Boolean Values
2.4.4 Structured Types, Objects And Structured Values
2.4.5 Operators On Objects

2.5 Variables

2.5.1 Initial Values Of Variables

2.6 Conversions And Promotions
2.7 Names And Packages

2.7.1 Names
2.7.2 Packages
2.7.3 Members
2.7.4 The Members Of A Class Type

2.8 Classes

2.8.1 Class Identifiers
2.8.2 Class Modifiers
2.8.3 Superclasses And Subclasses
2.8.4 The Class Members

2.9 Fields

2.9.1 Field Modifiers

2.10 Methods And Constructors

2.10.1 Formal Parameters
2.10.2 Method Modifiers

2.11 Static Initializers
2.12 Interfaces
2.13 Arrays
2.14 Blocks

2.14.1 Local Variable Declarations

2.15 Statements

2.15.1 Conditional Statement
2.15.2 Iteration Statement
2.15.3 Expression Statements
2.15.4 Empty Statement
2.15.5 Escape Statements
2.15.6 Managed Statement
2.15.7 Unreachable Statements

2.16 Instructions

2.16.1 Unconditional Branch Instruction
2.16.2 Conditional Branch Instructions
2.15.3 Data Transfer Instructions
2.16.4 Class Instance Creation Instruction
2.16.5 Arithmetic And Logic Instructions
2.16.6 Method Invocation Instruction

2.17 Expressions

2.17.1 Variables As Values
2.17.2 Type Of An Expression
2.17.3 Evaluation Order
2.17.4 Constant Generation Statements
2.17.5 Class Instance Creation Statement
2.17.6 Method Invocation Statement
2.17.7 Unary Operator Statements
2.17.8 Binary Operator Statements
2.17.9 Assignment Statement

2.18 Definite Assignment
2.19 Exceptions
2.20 Execution

2.20.1 Interpreter Start-Up
2.20.2 Instantiation Of A Class
2.20.3 Interpreter Exit

2.21 Threads


3 : Building a Tree-Based Interpreter

3.1 Design Requirements

3.1.1 Symbol Table Requirements
3.1.2 Interpreter State Requirements
3.1.3 Program Tree Requirements

3.2 Design Choices

3.2.1 Symbol Table Design
3.2.2 Interpreter State Design

3.2.3 Program Tree Design

3.3 Implementation Overview

3.3.1 Symbol Table Implementation
3.3.2 Interpreter State Implementation
3.3.3 Program Tree Implementation

3.4 Implementation Details

3.4.1 Implementation Of Identifiers
3.4.2 Implementation Of Types And Values
3.4.3 Implementation Of Symbol Dictionaries
3.4.4 Implementation Of Symbol Stacks
3.4.5 Implementation Of The Return Variable
3.4.6 Implementation Of Concrete Listing Generation
3.4.7 Implementation Of Other Symbol Table Methods
3.4.8 Implementation Of The Compilation Unit
3.4.9 Implementation Of Classes
3.4.10 Implementation Of Methods
3.4.11 Implementation Of Blocks
3.4.12 Implementation Of Flow Control Statements
3.4.13 Implementation Of Constant Expressions
3.4.14 Implementation Of Unary And Binary Operations
3.4.15 Implementation Of Data Transfer Statements
3.4.16 Implementation Of Method Invocation Statements
3.4.17 Implementation Of Class Instance Creation Statements

4 : A Comparable Code-Based Interpreter

4.1 Design Requirements

4.1.1 Symbol Table Requirements
4.1.2 Interpreter State Requirements
4.1.3 Program Tree Requirements

4.2 Design Choices

4.2.1 Symbol Table Design
4.2.2 Interpreter State Design

4.2.3 Program Tree Design

4.3 Implementation Overview

4.3.1 Symbol Table Implementation
4.3.2 Interpreter State Implementation
4.3.3 Program Tree Implementation

4.4 Implementation Details

4.4.1 Implementation Of Identifiers
4.4.2 Implementation Of Types And Values
4.4.3 Implementation Of Symbol Dictionaries
4.4.4 Implementation Of Symbol Stacks
4.4.5 Implementation Of The Return Variable
4.4.6 Implementation Of Concrete Listing Generation
4.4.7 Implementation Of Operand Stack And Program Counter
4.4.8 Implementation Of The Compilation Unit
4.4.9 Implementation Of Classes
4.4.10 Implementation Of Methods
4.4.11 Implementation Of Blocks
4.4.12 Implementation Of Flow Control Instructions
4.4.13 Implementation Of Constant Value Generation
4.4.14 Implementation Of Unary And Binary Operations
4.4.15 Implementation Of Data Transfer Instructions
4.4.16 Implementation Of Method Invocation Instructions
4.4.17 Implementation Of Class Instance Creation Instructions

5 : A Basis For Comparison

5.1 Stacking Tree Interpreter

5.1.1 Inclusion Of Operand Stack
5.1.2 Modified Implementation Of Methods
5.1.3 Modified Implementation Of Blocks
5.1.4 Modified Implementation Of Flow Control Statements
5.1.5 Modified Implementation Of Constant Value Expressions
5.1.6 Modified Implementation Of Unary And Binary Operations
5.1.7 Modified Implementation Of Data Transfer Statements
5.1.8 Modified Implementation Of Method Invocation Statements
5.1.9 Modified Implementation Of Class Instance Creation Statements

5.2 Notes On The Three Interpreter Paradigms

5.2.1 The Picojava Code Interpreter
5.2.2 The Picojava Tree Interpreter
5.2.3 The Picojava Stacking Tree Interpreter

5.3 Benchmark Programs Overview

5.3.1 Empty Loop Overview
5.3.2 Deep Empty Loop Overview
5.3.3 Field Access Overview
5.3.4 Method Call Overview
5.3.5 Often True Overview
5.3.6 Fibonacci Overview

5.4 Code Implementation Of Benchmarks

5.4.1 Empty Loop Code Implementation
5.4.2 Deep Empty Loop Code Implementation
5.4.3 Field Access Code Implementation
5.4.4 Method Call Code Implementation
5.4.5 Often True Code Implementation
5.4.6 Fibonacci Code Implementation

5.5 Tree Implementation Of Benchmarks

5.5.1 Empty Loop Tree Implementation
5.5.2 Deep Empty Loop Tree Implementation
5.5.3 Field Access Tree Implementation
5.5.4 Method Call Tree Implementation
5.5.5 Often True Tree Implementation
5.5.6 Fibonacci Tree Implementation

6 : Trees Compared To Code

6.1 Empty Loop Results
6.2 Deep Empty Loop Results
6.3 Field Access Results
6.4 Method Call Results
6.5 Often True Results
6.6 Fibonacci Results
6.7 Summary

7 : Conclusion And Future Work

7.1 Trees Over Code
7.2 Building On The Results
7.3 Related Questions

7.3.1 A Compact Representation For Trees
7.3.2 Faster Generation Of Portable Code
7.3.3 Manipulating Abstract Trees
7.3.4 Better JIT Compilers

A : Picojava Source Language Abstract Grammar
B : Picojava Assembly Language Abstract Grammar
Bibliography

  First Chapter     Top of Contents