FACULTY OF SCIENCE
UNIVERSITY OF COPENHAGEN

Master’s Thesis
arXiv:1707.07845v1 [cs.PL] 25 Jul 2017

Tue Haulund - qvr916@alumni.ku.dk

Design and Implementation of a Reversible
Object-Oriented Programming Language

Main Supervisor: Torben Ægidius Mogensen
Co-Supervisor: Robert Glück
Submitted: November 8, 2016

Abstract
High-level reversible programming languages are few and far between and in general offer only
rudimentary abstractions from the details of the underlying machine. Modern programming
languages offer a wide array of language constructs and paradigms to facilitate the design of
abstract interfaces, but we currently have a very limited understanding of the applicability of
such features for reversible programming languages.
We introduce the first reversible object-oriented programming language, ROOPL, with support
for user-defined data types, class inheritance and subtype-polymorphism. The language extends
the design of existing reversible imperative languages and it allows for effective implementation
on reversible machines.
We provide a formalization of the language semantics, the type system and we demonstrate the
computational universality of the language by implementing a reversible Turing machine simulator.
ROOPL statements are locally invertible at no extra cost to program size or computational
complexity and the language provides direct access to the inverse semantics of each class method.
We describe the techniques required for a garbage-free translation from ROOPL to the
reversible assembly language PISA and provide a full implementation of said techniques. Our
results indicate that core language features for object-oriented programming carries over to the
field of reversible computing in some capacity.

Abstract

1 of 111

Preface

“A language that doesn’t affect the way you think
about programming, is not worth knowing“
– Alan J. Perlis, Epigrams on Programming [39]

The present thesis constitutes a 30 ECTS workload and is submitted in partial fulfillment of
the requirements for the degree of Master of Science in Computer Science at the University of
Copenhagen (UCPH), Department of Computer Science (DIKU).
The thesis report consists of 111 numbered pages, a title page and a ZIP archive containing
source code developed as part of the thesis work. The thesis was submitted for grading on
November 8, 2016 and will be subject to an oral defense no later than December 6, 2016.
I would like to express my sincerest appreciation for the invaluable direction and encouragement
of my primary academic supervisor, Torben Mogensen. I would also like to thank my co-supervisor
Robert Glück, for introducing me to the fascinating field of reversible computing and for his help
with the thesis subject. Finally - a heartfelt appreciation is owed to my loving partner Matilde,
without whom this thesis would not have been possible.
Copenhagen, Autumn 2016
Tue Haulund

Preface

2 of 111

Table of Contents

1 Introduction
1.1 Reversible Computing . . . . .
1.2 Object-Oriented Programming
1.3 Motivation . . . . . . . . . . . .
1.4 Thesis Statement . . . . . . . .
1.5 Outline . . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

7
7
10
10
11
11

Languages
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

12
12
14
15
18
20

Roopl Language
Syntax . . . . . . . . . . . . . . . . . . . . . .
Argument Aliasing . . . . . . . . . . . . . . .
Parameter Passing Schemes . . . . . . . . . .
Object Model . . . . . . . . . . . . . . . . . .
Object Instantiation . . . . . . . . . . . . . .
Inheritance Semantics . . . . . . . . . . . . .
Type System . . . . . . . . . . . . . . . . . .
3.7.1 Preliminaries . . . . . . . . . . . . . .
3.7.2 Expressions . . . . . . . . . . . . . . .
3.7.3 Statements . . . . . . . . . . . . . . .
3.7.4 Programs . . . . . . . . . . . . . . . .
3.8 Language Semantics . . . . . . . . . . . . . .
3.8.1 Preliminaries . . . . . . . . . . . . . .
3.8.2 Expressions . . . . . . . . . . . . . . .
3.8.3 Statements . . . . . . . . . . . . . . .
3.8.4 Programs . . . . . . . . . . . . . . . .
3.9 Program Inversion . . . . . . . . . . . . . . .
3.9.1 Invertibility of Statements . . . . . . .
3.9.2 Type-Safe Statement Inversion . . . .
3.10 Language Extensions . . . . . . . . . . . . . .
3.10.1 Local Variables . . . . . . . . . . . . .
3.10.2 Class Constructors and Deconstructors
3.10.3 Expression Arguments . . . . . . . . .
3.10.4 Method Reversal . . . . . . . . . . . .
3.10.5 Short Form Control Flow . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

22
23
24
25
25
26
27
28
29
29
30
31
32
32
32
33
36
37
38
39
42
42
42
44
44
44

2 Reversible Programming
2.1 Janus . . . . . . . . .
2.2 Unstructured Janus . .
2.3 R . . . . . . . . . . . .
2.4 PISA . . . . . . . . . .
2.5 BobISA . . . . . . . .
3 The
3.1
3.2
3.3
3.4
3.5
3.6
3.7

Table of Contents

.
.
.
.
.

.
.
.
.
.

3 of 111

3.11 Language Idioms . . . . . . . .
3.11.1 Zero-Cleared Copying .
3.11.2 Mutators and Accessors
3.11.3 Abstract Methods . . .
3.11.4 Call-Uncall . . . . . . .
3.11.5 Linked Lists . . . . . . .
3.12 Computational Strength . . . .
3.12.1 RTM Representation . .
3.12.2 Tape Representation . .
3.12.3 RTM Simulation . . . .
4 Compilation
4.1 Preliminaries . . . . .
4.2 Memory Layout . . . .
4.3 Dynamic Dispatch . .
4.4 Object Layout . . . . .
4.5 Program Structure . .
4.6 Class Methods . . . .
4.7 Method Invocations .
4.8 Object Blocks . . . . .
4.9 Local Blocks . . . . . .
4.10 Control Flow . . . . .
4.11 Reversible Updates . .
4.12 Expression Evaluation
4.13 Error Handling . . . .
4.14 Implementation . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.

45
45
45
46
46
47
49
50
51
51

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

53
53
53
54
55
56
57
58
60
61
61
62
63
63
64

5 Conclusion
66
5.1 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
References
Appendix A Rooplc Source
A.1 AST.hs . . . . . . . . .
A.2 PISA.hs . . . . . . . . .
A.3 Parser.hs . . . . . . . . .
A.4 ClassAnalyzer.hs . . . .
A.5 ScopeAnalyzer.hs . . . .
A.6 TypeChecker.hs . . . . .
A.7 CodeGenerator.hs . . . .
A.8 MacroExpander.hs . . .
A.9 ROOPLC.hs . . . . . . .

68
Code
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

72
72
74
77
81
84
88
91
100
102

Appendix B Example Output
103
B.1 LinkedList.rpl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
B.2 LinkedList.pal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

Table of Contents

4 of 111

List of Figures

1.1

Flowcharts of reversible and irreversible variants of a conditional statement . . .

2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11

EBNF grammar for Janus . . . . . . . . . . . . . . . . . .
Flowchart of a reversible loop statement . . . . . . . . . .
√
Example Janus program for computing b nc . . . . . . . .
Unstructured Janus program computing the product of two
EBNF grammar for R . . . . . . . . . . . . . . . . . . . . .
Example R program for computing the nth Fibonacci pair .
Syntax domains and EBNF grammar for PISA . . . . . . .
PISA inversion rules . . . . . . . . . . . . . . . . . . . . . .
Example PISA program for simulating free-falling objects .
EBNF grammar for BobISA . . . . . . . . . . . . . . . . .
BobISA inversion rules . . . . . . . . . . . . . . . . . . . .

3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12a
3.12b
3.13
3.14
3.15
3.16
3.17
3.18
3.19
3.20
3.21
3.22
3.23
3.24a
3.24b
3.24c

Example ROOPL program computing the nth Fibonacci pair . . . . .
Syntax domains and EBNF grammar for ROOPL . . . . . . . . . . .
Simple example program illustrating the mechanics of an object block
Definition of function gen . . . . . . . . . . . . . . . . . . . . . . . . .
Definition of functions for modelling class inheritance . . . . . . . . .
Typing rules for ROOPL expressions . . . . . . . . . . . . . . . . . .
Typing rules for ROOPL statements . . . . . . . . . . . . . . . . . . .
Typing rules for ROOPL methods, classes and programs . . . . . . .
Semantic values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Semantic inference rules for evaluation of ROOPL expressions . . . .
Definition of the functions J⊗K . . . . . . . . . . . . . . . . . . . . . .
Semantic inference rules for execution of ROOPL statements . . . . .
Semantic inference rules for execution of ROOPL statements (cont.) .
Semantic inference rule for execution of ROOPL programs . . . . . .
Statement inverter for ROOPL statements . . . . . . . . . . . . . . .
Program and class inverters for ROOPL . . . . . . . . . . . . . . . . .
Modified statement inverter for ROOPL statements . . . . . . . . . .
Class constructor/deconstructor extension . . . . . . . . . . . . . . .
ROOPL class representing a calendar date . . . . . . . . . . . . . . .
Language extension for expressions as method arguments . . . . . . .
Language extension for single-statement method reversals . . . . . . .
Syntactic sugar for short form conditionals and loops . . . . . . . . .
Basic mutator and accessor methods in ROOPL . . . . . . . . . . . .
Example of an interface in ROOPL . . . . . . . . . . . . . . . . . . .
Example of recursively defined linked lists in ROOPL . . . . . . . . .
Example of recursively defined linked lists in ROOPL (cont.) . . . . .
Example of recursively defined linked lists in ROOPL (cont.) . . . . .

List of Figures

. . . . . . . .
. . . . . . . .
. . . . . . . .
odd numbers
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

8

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

12
13
14
15
16
17
18
19
20
20
21

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

22
23
27
28
28
29
30
31
32
32
33
34
35
36
37
38
38
42
43
44
44
44
45
46
47
48
49

5 of 111

3.25 Method for executing a single TM transition . . . . . . . . . . . . . . . . . . . .
3.26 Main RTM simulation method . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51
52

4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8
4.9
4.10
4.11
4.12
4.13
4.14

53
54
54
55
56
57
58
59
60
60
61
62
62
64

Definition of pseudoinstructions SUBI, PUSH and POP . . . . .
Memory layout of a ROOPL program . . . . . . . . . . . . . .
Virtual function table layout . . . . . . . . . . . . . . . . . . .
Illustration of object memory layout . . . . . . . . . . . . . . .
Overall layout of a translated ROOPL program . . . . . . . .
PISA translation of a ROOPL method . . . . . . . . . . . . .
PISA translation of local method invocations . . . . . . . . . .
PISA translation of a non-local method invocation . . . . . . .
PISA translation of a non-local reverse method invocation . .
PISA translation of an object block . . . . . . . . . . . . . . .
PISA translation of a local block . . . . . . . . . . . . . . . . .
PISA translation of control flow statements . . . . . . . . . . .
PISA translation of variable updates and variable swapping . .
PISA translation of a local block, with run time error checking

List of Figures

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.

6 of 111

CHAPTER

1

Introduction
Reversible computing is the study of time-invertible, two-directional models of computation. At
any point during a reversible computation, there is at most one previous and one subsequent
computational state, both of which are uniquely determined by the current state. The computational process follows a deterministic trajectory of these states in either direction of execution
and carefully avoids erasing information such that previous states remain reachable and unique.
As a result of this perfect preservation of information, reversible computing offers a possible
solution to the heat dissipation problems faced by manufacturers of microprocessors [28].
To realize a fully reversible computing system, we need reversibility at every level of abstraction.
Much headway has been made at the circuit and gate level, such as the realization of the reversible
Pendulum architecture [42] based on the reversible universal Fredkin and Toffoli gates [19]. Highlevel reversible programming languages are also actively researched, most notably the imperative
reversible language Janus [30, 49, 46], the procedural reversible language R [18, 17] and the
functional reversible languages RFUN [48] and Inv [37]. Recently, translation of these languages
to low-level reversible assembly languages has been the subject of some work [2, 25]. A reversible
self-interpreter for the reversible imperative language R-WHILE was shown in [23].
Throughout this existing body of research, a reversible object-oriented language has yet to be
formalized. The present thesis discusses the design of such a language as well as the techniques
required to perform a clean (i.e. garbage-free) and correct translation from such a language to a
low-level reversible assembly language. As is the case for any programming paradigm, reversible
object-oriented programming has its own programming techniques and pitfalls, which we will
explore in detail. The language will implement traditional OOP concepts such as encapsulation,
subtype polymorphism and dynamic dispatch, albeit in a reversible context.

1.1

Reversible Computing

A great deal of effort is expended on minimizing the power consumption of modern microprocessors,
to the point where it is now considered a first-class design constraint. However a theoretical lower
limit does exist for our current model of computation. Known since the early 1960’s, Landauer’s
principle holds that:
[. . .] any logically irreversible manipulation of information, such as the erasure of a bit
or the merging of two computation paths, must be accompanied by a corresponding
entropy increase in non-information-bearing degrees of freedom of the informationprocessing apparatus or its environment. [28]
Put simply, Landauer’s principle states that the erasure of information in a system is always
accompanied by an increase in energy consumption. The exact amount of energy required to
Chapter 1 Introduction

7 of 111

erase n bits of information is n · kB · T · ln 2, where T is the temperature of the circuit in kelvin
and kB is the Boltzmann constant (approximately 1.38 · 10−23 J/K) [8].
This theoretical limit is known as the von Neumann-Landauer limit and it places a lower
bound on the energy consumption of any computation involving the erasure of information. In a
reversible computation, information is never erased, which means reversible computing systems
are not subject to the von Neumann-Landauer limit1 .
The naive approach to achieving reversibility is based on the idea of reversibilization of a
regular irreversible program. As the program is executing, intermediate values are preserved
in a program history trace. Known as a Landauer embedding, this technique achieves perfect
preservation of information [28]. Bennett showed that such an embedding can be created for any
irreversible program [6], however the space requirements for this technique grows proportionally
to the length of time the program has been running. Given an irreversible program with running
time T and space complexity S, a semantically equivalent reversible program with running time
O(T 1 +  ) and space complexity O(S ln T ) can be constructed for some  > 0 [9]. These space
requirements make this approach completely impractical for general purposes.
The Landauer embedding is an example of injectivization of the function that our program
computes. As we cannot accept the generation of this extraneous garbage data, we must limit
ourselves to programs that compute functions that are already injective (i.e. one-to-one functions).
Reversible programming languages are made up of individually reversible execution steps, each
of which must also be injective when viewed as a mapping from one computational state to
the next. This one-to-one mapping ensures that the language is both forwards and backwards
deterministic, there is always at most one state the computation can transition to, regardless of
the direction of execution.
s1

t

s3

e
f

t

s2

s1

e1
f

t
e2

s2

s3

f

Figure 1.1: Flowcharts of irreversible and reversible variants of a conditional statement followed by some other
statement s3 . The reversible variant uses the assertion e2 to join the two paths of computation reversibly - if the
control flow reaches e2 from the true-edge then e2 must evaluate to true and vice versa, otherwise the statement
is undefined. [47]

In irreversible programming languages, this mapping can be a many-to-one (non-injective)
function since we are then only concerned with forward determinism. The inverse of such a
function is a one-to-many relation (sometimes called a multivalued function) which means such
languages are backwards non-deterministic, as it is impossible to uniquely determine the previous
state of computation2 .
Every reversible program has exactly one corresponding inverse program in which every
1

Aside from its relationship to reversible computing, Landauer’s principle also represents a compelling argument
that Maxwell’s Demon does not violate the second law of thermodynamics [7]

2

Some languages are both forwards and backwards non-deterministic by design - the logic programming language
Prolog is an example of such a language.

Chapter 1 Introduction

8 of 111

execution step is inverted and performed in reverse order of the original program. Since each
execution step is locally invertible, as opposed to requiring a full-program analysis, the inversion
can be achieved with straightforward recursive descent over the components of the program.
Furthermore, given that each single execution step has a single-step inverse, the process of
inverting a reversible program bears no additional cost in terms of program size.
Reversible programming languages may provide direct access to the inverse semantics of a
code segment, in Janus this is exemplified by the uncall statement which invokes the inverse
computation of a given procedure [49], while low-level reversible languages typically make use of
a direction bit to invoke inverse semantics and reverse execution [41]. This direct access has given
rise to some clever programming methodologies. One example is known as the Lecerf-Bennet
reversal 3 which makes use of uncomputation to reversibly purge the variable store of undesired
intermediate values after a computation.
For some computations, having direct and inexpensive access to the exact inverse computation
can be useful from a software development perspective. For example, implementing a compression
algorithm in a reversible language4 immediately yields the equivalent decompression routine by
inversion of the program. Additionally, any effort that has gone into verifying the correctness of
the compression algorithm, e.g. testing or perhaps even formal verification techniques such as
model checking, can serve as an equally valid testament to the correctness of the inverse program
(assuming the process of inversion is itself correct).
Besides the primary motivation of potentially improving the energy efficiency of computers
beyond the von Neumann-Landauer limit, the field of reversible computing shows promise in a
number of other areas:
Quantum Computing A quantum logic gate represents a transformation which can be applied
to an isolated quantum system. For the resulting system to be consistent, the transformation
matrix must be unitary. Such transformations are inherently reversible, and indeed any reversible
boolean function can be converted to a corresponding unitary transformation [12]. As such, the
field of quantum computing could stand to benefit from an increased understanding of reversible
computing.
Program Debugging Traditional program debugging involves stepping through code line by
line, inspecting intermediate results and memory contents accordingly. Recently, vendors have
added support for reverse debugging, which involves stepping through code in reverse or restoring
earlier program states from within a debugging session. This is usually implemented with a
continous execution trace but on a reversible computing platform, such functionality is supported
as a fundamental property of the system. A reversible extension to the Erlang programming
language, for the purpose of supporting reverse debugging was suggested in [38].
Error Recovery In parallel or pipeline-based systems, recovery from an unforeseen error
condition often involves undoing recent related changes made to the state of the system. As an
example, this is a primary features of most DBMS and it is implemented with special-purpose
error recovery logic. On a reversible system however, this can be achieved by simple reverse
execution back to the point where the error condition first arose. A reversible DSL for error
recovery on robotic assembly lines was presented in [40].
3

Also known as the local Bennett’s method [49], or the compute-copy-uncompute paradigm. It was first proposed by
Lecerf [29] and later rediscovered by Bennett [6].

4

The futility of attempting to implement a lossy compression algorithm within a language paradigm that forbids
the erasure of information should not be lost on the reader at this point.

Chapter 1 Introduction

9 of 111

Discrete Event Simulation The simulation of systems with asynchronous discrete update
events lends itself well to concurrent execution. Suggested in [27], the Dynamic Time Warp
(DTW) algorithm is commonly used to synchronize event updates across execution threads. DTW
uses update rollbacks to restore the simulation to a synchronized state, in case an event has
been committed prematurely. Reversible computation can be used to realize event rollback while
avoiding the high overhead of storing execution traces or simulation checkpoints [14].

1.2

Object-Oriented Programming

Like reversible computing, object-oriented programming (OOP) originated in the early 1960’s,
with the advent of the Simula language [10]. Unlike reversible computing, OOP enjoys immense
popularity in the software industry, as can be observed by the widespread use of object-oriented
languages such as Java and C++. The OOP paradigm attempts to break a problem into many
small manageable pieces of related state and behaviour called objects. An object may model an
actual object in the problem domain, or it may represent a more abstract grouping of related
entities within a program. A distinction is made between a particular kind or type of object,
called a class, and specific instances of these classes, known simply as objects.
OOP is based on the concept of encapsulation: Only the methods of an object has unrestricted
access to the components of that object, thereby protecting the integrity of the internal state
and reducing the overall system complexity. Encapsulation is closely related to the principle of
information hiding, which holds that compartmentalization of design decisions made in one part
of a program can be used to avoid extensive modification of other parts of that program if the
design is altered [20, Chapter 1].
A fundamental aspect of OOP is class inheritance, which allows one class to inherit the fields
and methods of another class. Most OOP languages also use inheritance to establish an "is-a"
relationship between two objects such that one may be substituted for the other by subtypepolymorphism. OOP lends itself well to code-reuse and maintainability of source code, and is
often used in combination with imperative or procedural programming paradigms. In general,
OOP is a set of techniques for intuitively structuring imperative code - it is a programming
methodology rather than a model of computation.

1.3

Motivation

After more than two dozen iterations of Moore’s Law [36], the semiconductor industry is fast
approaching the von Neumann-Landauer limit. Reversible computing may be a viable solution,
but it represents a significant paradigm shift from the currently prevailing irreversible models of
computation.
The practicality of reversible computing hinges, inter alia, on the presence of high-level
reversible programming languages that can be compiled to low-level reversible assembly code
without significant overhead. Ideally, these languages should provide the same tools and features
for producing abstract models and interfaces as are available for modern irreversible languages.
Object-oriented programming is immensely popular in the industry but the combination of
OOP and reversible computing is entirely uncharted territory. The work presented in this thesis
is motivated by the scarcity of high-level reversible programming languages and in particular, by
the absence of any reversible object-oriented programming languages.

Chapter 1 Introduction

10 of 111

1.4

Thesis Statement

An effective implementation of a reversible object-oriented programming language is both possible
and practical, provided the design of the language observes the limitations required for execution
on reversible machines.

1.5

Outline

This thesis consists of 5 chapters, the first of which is this introductory chapter. The remaining
4 chapters are summarised as follows:
Chapter 2 is a brief survey of existing reversible imperative programming languages and
instruction sets.
Chapter 3 presents the reversible object-oriented programming language ROOPL, along with a
formalization of the language and a discussion of the most significant elements of its design.
Chapter 4 presents the techniques required for a garbage-free and correct compilation from
ROOPL source code to PISA instructions.
Chapter 5 contains conclusions and proposals for future work.
The appendix contains the source code listings for the ROOPL compiler, an example ROOPL
program and the equivalent translated PISA program.

Chapter 1 Introduction

11 of 111

CHAPTER

2

Reversible Programming Languages
The following chapter contains a survey of reversible instruction sets and reversible imperative
programming languages. Given that OOP is an approach for naturally organizing imperative
code, it is clear that such languages are of special interest when designing a reversible OOP
language. Indeed, the design of our reversible OOP language draws heavily from the design of
the languages and instruction sets presented in this section.

2.1

Janus

The reversible programming language Janus (named after the two-faced Greco-Roman god
of beginnings and endings) was created by Cristopher Lutz and Howard Derby for a class at
Caltech in 1982 [30]. It was later rediscovered and formalized in [49] and some modifications
were suggested in [46] - the following section deals with this modified version of the language.
Janus Grammar

prog

::=

pmain p∗

t

::=

int | stack

(program)
(data type)
?

∗

pmain

::=

procedure main () (int x([n]) | stack x) s

p

::=

procedure q(t x, . . . , t x) s

s

::=

x

=e

(assignment)

|

if e then s else s fi e

(conditional)

|

from e do s loop s until e

|

push(x, x) | pop(x, x)

|

local t x = e s delocal t x = e

|

call q(x, . . . , x) | uncall q(x, . . . , x)

|

skip | s s

::=

n | x | x[e] | e ⊗ e | empty(x) | top(x) | nil

::=

+|-|^

e
⊗

::=

= e | x[e]

(main procedure)
(procedure definition)

(loop)
(stack modification)
(local variable block)
(procedure invocation)
(statement sequence)

| * | / | % | & | | | && | || | < | > | = | != | <= | >=

(expression)
(operator)
(operator)

Figure 2.1: EBNF grammar for Janus [46]

Chapter 2 Reversible Programming Languages

12 of 111

Janus is a procedural language with locally-invertible program statements and direct access
to inverse semantics. There are 3 data types in Janus: plain integers, fixed-size integer arrays
and dynamically-sized integer stacks. Integer variables and integer stacks may be declared locally
or statically in the global scope, while integer arrays can only be declared statically.
A Janus program consists of a main procedure followed by any number of secondary procedures.
The main procedure acts as the starting point of the program and is preceded by declarations of
static variables, which serve as the program output upon termination. Secondary procedures
may specify parameters which are passed to the callee by reference. Procedures can not return a
value but may use output parameters to achieve similar effects. Procedure bodies are made up of
one or more program statements, which may be one of several different forms.
A conditional statement in Janus has both a branch condition and an exit assertion, both
of which are expressions. The branch condition determines which branch of the conditional
is executed, while the exit assertion is used to reversibly join the two paths of computation.
If the branch condition evaluates to true, the then-branch is executed upon which the exit
assertion should also evaluate to true. If the branch condition evaluates to false, the else-branch
is executed after which the exit assertion should evaluate to false. If the exit assertion does
not match the branch condition, the statement is undefined. See Figure 1.1 in Chapter 1 for a
flowchart illustrating the mechanics of reversible conditionals.
A loop statement has both an entry assertion and an exit condition, both of which are
expressions. Initially, the entry assertion must evaluate to true after which the do-statement is
executed. If the exit condition is then true, the loop terminates, otherwise the loop-statement is
executed upon which the entry assertion must now evaluate to false. When executed in reverse,
the exit condition serves as the entry assertion and vice versa. Figure 2.2 shows a flowchart
illustrating the mechanics of reversible loops.
s1
t e
1
f

s1
e2

s2

t

f

t e
1
f

e2 t
s2

f

Figure 2.2: Flowcharts of a reversible loop statement, in both directions of execution [47, 49]

The stack modification statements, push and pop are used to manipulate integer stacks in
the usual fashion, the only difference being that pushing a variable onto a stack zero-clears the
contents of the variable while popping a value into a variable presupposes that the variable is
zero-cleared. This means that push and pop are inversions of each other.
A reversible variable update in Janus works by updating a variable in the current scope in
such a way that the original store remains reachable by subsequent uncomputation. Only updates
that are injective in their first argument and have precisely defined inverses are allowed and it is
a requirement that the expression being updated with does not in any way depend on the value
of the variable being updated (to avoid loss of information). To ensure such an update cannot
occur, it is not allowed for the variable identifier on the left side of the update to occur anywhere
on the right-hand side. This also mandates a further restriction: no two identifiers may refer to
the same location in memory in the same scope (a situation known as aliasing) as this would
Chapter 2 Reversible Programming Languages

13 of 111

otherwise be a way to circumvent the aforementioned requirement.
The local variable block, denoted by the local/delocal statement, defines a block scope
wherein a new local variable is declared and initialized. After the block statement has executed
with the new variable in scope, the variable is cleared by means of an exit expression which
must evaluate to the value of the variable (otherwise the statement is undefined as it becomes
impossible to reversibly clear the memory occupied by the variable).
The call and uncall statements are used to invoke procedures in the forwards and backwards
direction. Arguments are passed by reference and it is a requirement that the same variable is
not passed twice in the same procedure invocation to avoid aliasing of the arguments.
An expression in Janus can either be a numeric literal, a variable identifier, an array element,
a binary expression or a stack expression. Janus uses 0 to represent the boolean value false, and
non-zero to represent true.
1
2
3
4
5

procedure main()
int n
int root
n += 25
call root(n, root)

6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

procedure root(int n, int roo) //root := floor (sqrt(n))
local int bit = 1
from bit = 1
do skip
loop call doublebit(bit)
until (bit * bit) > n
from (bit * bit) > n
do uncall doublebit(bit)
if ((root + bit) * (root + bit)) <= n
then root += bit
fi (root / bit) % 2 != 0
loop skip
until bit=1
delocal int bit = 1
n -= root * root

22
23
24
25
26

procedure doublebit(int bit)
local int z = bit
bit += z
delocal int z = bit / 2

√
Figure 2.3: Example Janus program for computing b nc from [30]

Janus is known to be r-Turing complete as it is able to simulate any reversible Turing
machine [46]. An efficient and clean translation from Janus to PISA (See Section 2.4) was
presented in [2] and a partial evaluator for Janus was presented in [34]. The reversible control
flow constructs used by Janus was explored in detail in [47].

2.2

Unstructured Janus

An unstructured version of Janus was used in [34] as an intermediate language for polyvariant
partial evaluation. Specialization of a program written in an imperative programming language
is usually accomplished with polyvariant partial evaluation, which is most suitable for programs
with unstructured control flow.

Chapter 2 Reversible Programming Languages

14 of 111

A precursor to the unstructured version of Janus was first presented in [47] as a reversible
flowchart language. Mogensen suggests a simple transformation from Janus to a modified version
of this flowchart language, before the partial evaluation is applied.
The language uses paired jumps to organize the unstructured control flow in a reversible
manner: Every jump statement must jump to a from-statement which uniquely identifies the
origin of the jump, thus reversibly joining the control flow. The language also supports conditional
jumps which must then target a conditional from-statement, again for the purpose of reversibly
joining the two paths of computation.
Unstructured Janus programs are arranged into a series of basic blocks, each consisting
of a label, a from statement, a series of reversible assignments and finally a jump. The first
block always starts with a start statement and the end of the program is marked with a return
statement. The language is locally invertible, just like its structured counterpart.
The structured reversible program theorem, by Yokoyama et al. in [47] proves that such a
language is computationally equivalent to its structured counterpart. Figure 2.4 shows a program
for multiplying two odd integers using unstructured Janus.
1
2

start:
goto f_2

3
4
5

if 0 = prod from f_2 a_2:
if odd(a) goto t1_3 e1_3

6
7
8
9

t1_3:
prod += b; t += a / 2; a -= t + 1; t -= a
goto t2_3

10
11
12
13

e1_3:
t += a / 2; a -= t; t -= a
goto e2_3

14
15
16

if !(prod < b) from t2_3 e2_3:
if a = 0 goto f_11 l_2

17
18
19
20

l_2:
v += b; b += v; v -= b/2
goto a_2

21
22
23
24

if prod < b + b from f_11 a_11:
v += b / 2; b -= v; v -= b
if odd(b) goto u_11 a_11

25
26
27

u_11:
return

Figure 2.4: Unstructured Janus program computing the product of two odd numbers, from [34]

2.3

R

The reversible programming language R (not to be confused with the statistical programming
language of the same name) is an imperative reversible language developed at MIT in 1997 [18].
The syntax of R is a blend of LISP and C - with programs arranged as nested S-expressions but
with support for C-like arrays and pointer arithmetics. R is a compiled language, with the only
available compiler targeting the Pendulum reversible instruction set (see Section 2.4).
Chapter 2 Reversible Programming Languages

15 of 111

R Grammar

prog
s

::=
::=

s∗

(program)
∗

(defmain progname s )

(main routine)
∗

∗

|

(defsub subname (name ) s )

|

(defword name n)

(global variable)

|

∗

(global array)

(defarray name n )
∗

(subroutine)

|

(call subname e )

(call subroutine)

|

∗

(reverse-call subroutine)

|

(rcall subname e )
∗

(if e then s )

(conditional)
∗

(loop)

|

(let (name <- e) s )

(variable binding)

|

(printword e) | (println)

|

(loc ++) | (- loc)

|

(loc <-> loc) | (loc

loc

::=

e

::=

name | (* e) | (e _ e)
loc | (e ⊗ e) | n

::=

+= | -= | ^= | <=< | >=>

::=

+ | - | & | << | >> | */
= | < | > | <= | >= | !=

|

⊗

|

(for name = e to e s )
∗

(output)
(increment/negate)

e)

(swap/update)
(location)
(expression)
(update operator)
(expression operator)
(relational operator)

Figure 2.5: EBNF grammar for R, based on the rules presented in [17, Appdx. C]

Figure 2.5 shows a formal grammar describing the syntax rules of R. An R program consists
of any number of statements, but should contain exactly one main routine, defined with the
defmain statement. The main routine may invoke subroutines which are defined with the defsub
statement. Also a program may make use of globally scoped variables and arrays, defined with
the defword and defarray statement. These four types of statements may appear anywhere in
a program, but only have an actual effect when appearing as top-level statements.
The call and rcall statements are used to invoke a subroutine in either direction of execution,
and correspond to the call and uncall statements of Janus. Arguments are passed by reference,
but only parameters bound to variables or memory references may be modified by the callee.
Parameters bound to an expression or a constant should retain their value throughout the body
of the subroutine to avoid undefined or irreversible behaviour.
The if statement is used for conditional execution. It is a requirement that the value of
the conditional expression is the same before and after the conditional statement is executed,
otherwise undefined or irreversible behaviour may occur. This limitation guarantees that the
condition can be used to determine which branch of computation to follow in either direction of
execution. It is equivalent to a Janus conditional with the same expression used as entry condition
and exit assertion. A version with an else-branch was also proposed but never implemented in
the compiler.

Chapter 2 Reversible Programming Languages

16 of 111

The for statement is used for definite iteration. The iteration variable is given an initial value
matching the first expression and is then incremented upon each iteration until the termination
value is reached. Both expressions must have the same value before and after the loop is executed
to guarantee correct behaviour in both directions of execution. The for-loop may also be used
for indefinite iteration by modifying the value of the iteration variable in the loop body - which
allows the number of iterations to be determined dynamically as the loop proceeds.
A let statement creates a new local variable, limited in scope to the statements within the
let-block. The local variable is initialized to the value of the let-expression and after the block
statements have been executed the value of the let-expression should still match the value of the
local variable (although they are not required to have the same value as they did initially). This
is a requirement for the program to be able to reversibly zero-clear the local variable before it is
reclaimed by the system - it is functionally equivalent to a Janus local/delocal block where the
entry and exit expressions are the same.
The printword and println statements are used for program output. A printword statement will output the value of the given expression, while the println statement outputs a single
line-break delimiter.
1
2
3
4

(defsub fib (x1 x2 n)
(if (n = 0) then
(x1 += 1)
(x2 += 1) )

5
6
7
8
9
10
11

(if (n != 0) then
(n -= 1)
(call fib x1 x2 n)
(x1 += x2)
(x1 <-> x2)
(n += 1) ) ) ; Restore value of n for conditional

12
13
14
15
16

(defword
(defword
(defword
(defmain

x1 0)
x2 0)
n 4)
fibprog (call fib x1 x2 n))

Figure 2.6: Example R program for computing the nth Fibonacci pair, adapted from example program in [46]

Memory modification in R is done by the increment, negate, swap and update statements.
These statements operate on memory locations which may be represented either by variable
identifiers, by expressions referring to memory addresses or by expressions referring to specific
elements of an array (with an underscore representing array indexing). The update statements
are subject to the same restrictions as in Janus, namely that the value of the expressions being
updated with must not at the same time depend on the memory location being updated. This is
necessary to ensure that the update does not erase information. The <=< and >=> operators
represent arithmetic left and right rotations.
Expressions in R can be either memory locations, numeric literals or binary operations. The
supported operators are numerical addition, subtraction and bitwise conjunction (+, -, &), logical
left and right shifts (<<, >>), relational operators5 (=, <, <=, !=, >, >=) and fractional product
(*/), which is the product of a signed integer and a fixed-precision fraction between −1 and 1.
5

As described in [17, Appdx. C], the R compiler only supports the use of relational operators in conditional
expressions but this can be considered a limitation of the implementation, not of the language.

Chapter 2 Reversible Programming Languages

17 of 111

2.4

PISA

The Pendulum microprocessor and the Pendulum ISA (PISA) is a logically reversible computer
architecture created at MIT by Carlin James Vieri [42, 43, 17, 44]. The Pendulum architecture
resembles a mix of PDP-8 and RISC and it was the first reversible programmable processor and
instruction set.
PISA is a MIPS-like assembly language that has gone through several incarnations. The
version presented in this section is known as the PISA Assembly Language (PAL) and it is
compatible with the Pendulum virtual machine, PendVM [16].
PISA Grammar

prog

::=

((l :)? i)+

i

::=

ADD r r | ADDI r c | ANDX r r r | ANDIX r r c

|

NORX r r r | NEG r | ORX r r r | ORIX r r r | RL r c

|

RLV r r | RR r c | RRV r r | SLLX r r c | SLLVX r r r

|

SRAX r r c | SRAVX r r r | SRLX r r c | SRLVX r r r

|

SUB r r | XOR r r | XORI r c | BEQ r r l | BGEZ r l

|

BGTZ r l | BLEZ r l | BLTZ r l | BNE r r l | BRA l

|

EXCH r r | SWAPBR r | RBRA l | START | FINISH

|

DATA c

::=

· · · | -1 | 0 | 1 | · · ·

c

(program)
(instruction)

(immediate)

Syntax Domains

prog ∈ Programs
r ∈ Registers

i ∈ Instructions
l ∈ Labels

Figure 2.7: Syntax domains and EBNF grammar for PISA

In a conventional processor, the rules governing control flow are quite simple: After each
instruction, add 1 to the program counter. In case of a jump, set the program counter to
the address of the label being jumped to. In a reversible processor like Pendulum, these rules
are much more involved since simply overwriting the contents of the program counter would
constitute a loss of information which break reversibility.
The Pendulum processor uses three special-purpose registers for control flow logic:
1. The program counter (PC) for storing the address of the current instruction
2. The branch register (BR) for storing jump offsets
3. The direction bit (DIR) for keeping track of the execution direction

Chapter 2 Reversible Programming Languages

18 of 111

After each instruction, if the branch register is zero, we simply add the direction bit to the
program counter. The direction bit is either 1 or −1 depending on the direction of execution so
this corresponds to regular stepwise execution in either direction.
If the branch register is not zero, the product of the branch register and the direction bit
is added to the program counter. When a PISA program is assembled to machine code, the
target labels of each of the jump instructions are replaced with relative offsets. When a jump
instruction is then executed, the relative offset is placed in the branch register and when the PC
is updated, control flow jumps to the target label. Using paired branches, the PISA programmer
can clear the branch register after a jump by always jumping only to jump instruction that points
back to the original jump. This has the effect of adding the negation of the relative offset to the
branch register, thereby zero-clearing it.
Aside from the usual conditional jump instructions (Branch-if-equal, branch-if-zero et cetera),
PISA also contains the unconditional jump instruction BRA and the unconditional reverse-jump
instruction RBRA which also flips the direction bit and can therefore be used to implement uncall
or reverse-call functionality. When the direction bit is −1, the instructions are inverted so that
addition becomes subtraction, left-rotation becomes right-rotation and so on. See Figure 2.8 for
a table illustrating how PISA instructions are inverted when the execution direction is flipped.
i

i−1

ADD r1 r2
SUB r1 r2
ADDI r c
RL r c
RR r c
RLV r1 r2
RRV r1 r2

SUB r1 r2
ADD r1 r2
ADDI r −c
RR r c
RL r c
RRV r1 r2
RLV r1 r2

Figure 2.8: Inversion rules for PISA instructions, all other instructions are self-inverse

PISA also has the SWAPBR instruction which affords direct control over the contents of the
branch register (but crucially, not the PC directly) and makes it possible to implement dynamic
jumps such as switch/case structures or function pointers. SWAPBR can also be used to allow
incoming jumps from more than one location.
The special instructions START and FINISH are used to mark the beginning and end of a
PISA program while the memory exchange instruction EXCH provides simultaneous reversible
memory-read and memory-write functionality. The DATA instruction stores an immediate value
in the corresponding memory cell and can be used to mark the static storage space of a program.
The remaining instructions are similar to those of other RISC processors and implement
various register update functionality (bitwise-AND, bitwise-XOR and so on) albeit in a reversible
manner. For example, bitwise-AND is performed with the ANDX instruction which XORs the
resulting value into a third register to ensure reversibility.
Figure 2.9 shows an example PISA program. The design of the Pendulum control flow logic
is based in part on work by Cezzar [15] and Hall [24]. A complete formalization of the PISA
language and the Pendulum machine was given in [4] and a translation from Janus to PISA was
presented in [2]. PISA is also the target language of the R compiler [18, 17] and in this thesis we
use PISA as the target language for the translation presented in Chapter 4.

Chapter 2 Reversible Programming Languages

19 of 111

1
2
3
4

;; Call Fall:
10: ADDI $4 1000
11: ADDI $5 5
12: BRA 16

;h += 1000
;tend += 5
;call

5
6
7
8
9
10

;; Uncall Fall:
18: ADDI $6 40
19: ADDI $7 4
20: ADDI $5 4
21: RBRA 7

;v += 40

;uncall

11
12
13
14
15
16
17
18
19
20
21
22

;; Subroutine Fall:
27: BRA 9
28: SWAPBR $8
;br <=> rtn
29: NEG $8
;rtn=-rtn
30: BGTZ $7 5
;t > 0?
31: ADDI $6 10
;v += 10
32: ADDI $4 5
;h += 5
33: SUB $4 $6
;h -= v
34: ADDI $7 1
;t += 1
35: BNE $7 $5 -5
;t != tend?
36: BRA -9

Figure 2.9: Example PISA program for simulating free-falling objects, from [4]

2.5

BobISA

The reversible computer architecture Bob and its instruction set BobISA were created at the
University of Copenhagen by Thomsen et al. [41, 13]. Bob is a Harvard architecture which is
characterized by having separate storage for instructions and data6 .
BobISA was designed to be sufficiently expressive to serve as the target for high-level compilers
while still being relatively straightforward to implement in hardware. BobISA consists of 17
instructions and is known to be r-Turing complete [41].
BobISA Grammar

prog

::=

i+

i

::=

ADD r r | SUB r r | ADD1 r | SUB1 r

|

NEG r | XOR r r | XORI r c | MUL2 r

|

DIV2 r | BGEZ r o | BLZ r o | BEVN r o

|

BODD r o | BRA o | SWBR r | RSWB r

|

EXCH r r

c

::=

· · · | -1 | 0 | 1 | · · ·

o

::=

-128 | · · · | 0 | · · · | 127

(program)
(instruction)

(immediate)
(offset)

Figure 2.10: EBNF grammar for BobISA

6

As opposed to a von Neumann architecture which does not distinguish between program instructions and data.

Chapter 2 Reversible Programming Languages

20 of 111

The control flow logic of Bob is identical to that of PISA, with a few caveats:
– There are only 8-bits to store jump offsets, so a plain jump cannot be of more than 127
lines.
– The SWBR instruction which is similar to the SWAPBR instruction of PISA, can be used for
jump offsets longer than 127.
– BobISA also has the RSWB instruction which flips the direction bit in addition to swapping
out the branch register.
While the jump targets in the BobISA grammar in Figure 2.10 are represented in terms of
offsets, a construction similar to that of PISA could be used, where jumps are specified with
instruction labels that are then converted to offsets during program assembly.
The remaining instructions are self-explanatory and most of them have PISA equivalents,
with the exception of MUL2 and DIV2. These instructions operate on 4-bit two’s-complement
numbers and will either double or halve the value of a given register. To avoid overflow and
division of odd numbers, these instructions are only well-defined for a subset of the representable
values as illustrated in Figure 2.11. Input values outside of this subset are mapped to output in
such a way that reversibility is preserved. Figure 2.11 also shows the inversion rules for those
BobISA instructions that are not self-inverse. Like PISA, the inverse semantics of each instruction
is used when the processor is running in reverse.

x

MUL2(x)

x

DIV2(x)

i

i−1

-4
-3
-2
-1
0
1
2
3

-8
-6
-4
-2
0
2
4
6

-8
-6
-4
-2
0
2
4
6

-4
-3
-2
-1
0
1
2
3

ADD r1 r2
SUB r1 r2
ADD1 r
SUB1 r
MUL2 r
DIV2 r

SUB r1 r2
ADD r1 r2
SUB1 r
ADD1 r
DIV2 r
MUL2 r

Figure 2.11: Tables showing well-defined inputs and outputs for MUL2 and DIV2 instructions as well as the
inversion rules for BobISA instructions

A complete low-level design with schematics and HDL programs was developed for the Bob
architecture. Only 473 reversible gates are required to construct a Bob processor, totalling only
6328 transistors [41]. A translation from the reversible functional language RFUN to BobISA
was presented in [25].

Chapter 2 Reversible Programming Languages

21 of 111

CHAPTER

3

The Roopl Language
The Reversible Object-Oriented Programming Language (ROOPL) is, to our knowledge, the first
reversible programming language with built-in support for object-oriented programming and
user-defined types. ROOPL is statically typed and supports inheritance, encapsulation and
subtype-polymorphism via dynamic dispatch. ROOPL is purely reversible, in the sense that no
computation history is required for backwards execution. Rather, each component of a ROOPL
program is locally invertible at no extra cost to program size. The basic components of the
language, such as control flow structures and variable updates draw heavy inspiration from the
reversible imperative language Janus [49, 46], however the overall structure of a ROOPL program
differs vastly from that of a Janus program.
1
2
3

class Program
int result
int n

4
5
6

method main()
n ^= 4

7
8
9
10
11
12
13

construct Fib f
//Compute-copy-uncompute
call f::fib(n)
call f::get(result)
uncall f::fib(n)
destruct f

14
15
16
17

class Fib
int x1
int x2

18
19
20
21
22
23
24
25
26
27
28

method fib(int n)
if n = 0 then
x1 ^= 1
x2 ^= 1
else
n -= 1
call fib(n)
x1 += x2
x1 <=> x2
fi x1 = x2

29
30
31

method get(int out)
out ^= x2

Figure 3.1: Example ROOPL program computing the nth Fibonacci pair, adapted from example program in [46]

Chapter 3 The Roopl Language

22 of 111

3.1

Syntax

A ROOPL program consists of one or more class definitions, each of which may contain any
number of member variables and one or more methods. Each program should contain exactly one
class with a nullary method named main which acts as the program entry point. This class will
be instantiated when the program starts, and the fields of this object will act as the output of the
program in much the same way that the variable store acts as the output of a Janus program.
Roopl Grammar
prog

::=

cl+

cl

::=

class c (inherits c)? (t x)∗ m+

t

::=

int | c

m

::=

method q(t x, . . . , t x) s

s

::=

x

= e | x <=> x

(assignment)

|

if e then s else s fi e

(conditional)

|

from e do s loop s until e

|

construct c x s destruct x

|

call q(x, . . . , x) | uncall q(x, . . . , x)

|

call x::q(x, . . . , x) | uncall x::q(x, . . . , x)

|

skip | s s

::=

n | x | nil | e ⊗ e

::=

+|-|ˆ

e
⊗

::=

(program)
(class definition)
(data type)
(method)

(loop)
(object block)
(local method invocation)
(method invocation)
(statement sequence)
(expression)
(operator)

| * | / | % | & | | | && | || | < | > | = | != | <= | >=

(operator)

Syntax Domains

prog ∈ Programs

s ∈ Statements

n ∈ Constants

cl ∈ Classes

e ∈ Expressions

x ∈ VarIDs

t ∈ Types
m ∈ Methods

∈ ModOps
⊗ ∈ Operators

q ∈ MethodIDs
c ∈ ClassIDs

Figure 3.2: Syntax domains and EBNF grammar for ROOPL

A class definition consists of the keyword class followed by the class name. If the class is a
subclass of another, it is specified with the keyword inherits followed by the name of the base
class. Next, any number of class fields are declared, each of which may be either integers or
references to other objects (these are the only types in ROOPL). Finally, each class definition
contains at least one method which is defined with the keyword method followed by the method
name, a comma-separated list of parameters and the method body. A class must have at least
one method, as method calls are the only mechanism of interfacing with an object.
Chapter 3 The Roopl Language

23 of 111

A reversible assignment in ROOPL uses the same C-like syntax as a reversible assignment in
Janus. A variable can be updated either through addition (+=), subtraction (-=) or bitwise XOR
(^=). It is only possible to reversibly update the value of some variable x by some expression e in
this manner, if the value of e does not depend, in any way, on the value of x. We can enforce this
limitation by explicitly disallowing any occurrences of the identifier x in the expression e, but
this is only sufficient if we can also guarantee that no other identifiers refer to the same location
in memory as x (See Section 3.2).
A variable swap denoted by the token <=> swaps the value of two integer variables or two
object references. This was supported in Janus as syntactic sugar for the statement sequence:
x1 ^= x2

x2 ^= x1

x1 ^= x2

which achieves the same effect as x1 <=> x2 , given that x1 and x2 are both integers [49]. In
ROOPL, we might wish to swap two object references, for which the XOR operation is undefined,
so the swap statement has been made explicit in the language.
Loops and conditional statements are syntactically (and semantically) identical to Janus
loops and Janus conditionals. The use of assertions at control flow join points ensure that we
can execute these statements in reverse, in a deterministic manner.
An object block denotes the instantiation and lifetime of a ROOPL object. The statement
consist of the keyword construct followed by a class name and a variable identifier. Then follows
the block statement s within which the newly created object will be accessible, and finally the
keyword destruct followed by the object identifier signifies the end of the object block.
A method invocation may refer either to a local method or to a method in another object
- both variants can be both called and uncalled. An expression may be either a constant, a
variable, the special value nil or a binary expression.

3.2

Argument Aliasing

To avoid situations where multiple identifiers refer to the same memory location within the same
scope, known as aliasing, we must place some restrictions on method invocations. One source of
aliasing occurs when the same identifier is passed to more than one parameter of a method:
1
2

method foo(int a)
call bar(a, a)

3
4
5

method bar(int x, int y)
x -= y //Irreversible update!

Such situations are easily avoided by prohibiting method calls with the same identifier passed
to more than one parameter, which is the same approach used in Janus. Another, similar source
of aliasing is when a field of an object is passed to a parameter of a method of that same object:
1
2

class Object
int a

3
4
5
6

method main()
a += 5
call foo(a)

7
8
9

method foo(int b)
a -= b //Irreversible update!

Chapter 3 The Roopl Language

24 of 111

In this case we can disallow object fields as arguments to local methods, and since the object
field is already in scope in the callee, there is little point in also passing it as an argument. ROOPL
uses two separate statements to distinguish between local and non-local method invocations, so
it is a simple matter of prohibiting object fields as arguments to local call statements.
Finally, we must make sure that non-local method invocations are indeed non-local, which
might not be the case if an object has obtained a reference to itself. We can avoid such a situation
by disallowing non-local method calls to some object x which also passes x as an argument.

3.3

Parameter Passing Schemes

The most common parameter passing modes and their implications for reversible languages were
briefly discussed in [46] while a more in-depth investigation was performed in [32]. The common
call-by-value scheme is generally not suitable for reversible languages since the values accumulated
in the function parameters after a function has executed, must be disposed of somehow when the
function returns, which would result in a loss of information. It is also difficult to reconstruct
multiple arguments given only a single return value, which is the main reason that Janus uses
the call-by-reference strategy. With this approach, a function can simply store results in the
parameter variables and sidestep traditional single return values altogether. The values in the
parameters are handed back to the caller instead of being erased.
Another approach, which is likely simpler to implement in practice, is call-by-value-result
presented in [32]. Call-by-value-result involves swapping the function arguments into local
variables in the called procedure, and copying them back after the body has been executed.
This approach hinges upon the callee not being able to alter the argument variables other than
through the local copies, which can only occur if more than one identifier, referring to the same
argument, is in scope.
Call-by-reference and call-by-value-result are semantically equivalent parameter passing
schemes in the absence of aliasing [32], and therefore either scheme can be used. The operational
semantics of ROOPL (Section 3.8) uses call-by-reference.

3.4

Object Model

ROOPL is a class-based programming language, it is based on the notion of classes that serve as
blueprints for specific objects or class instances. Alternatively, a language may allow objects to
serve as blueprints for other objects - this is known as prototype-based programming. Prototypebased programming is dominated by dynamically-typed7 , interpreted languages (examples include
JavaScript and Lua). While there is no immediate reason to believe that dynamic typing is not a
feasible strategy for a reversible programming language, it is as of yet an unexplored notion.
Some OOP languages have very intricate object models - Java includes support for access
modifiers, static methods and fields, final classes (that may not be subclassed), final methods
(that cannot be overridden in a subclass) and both implementation inheritance and interface
inheritance. C++ supports friend classes, virtual and non-virtual methods, abstract methods,
private inheritance and multiple inheritance.
These features facilitate the creation of very rich models and interfaces but they are less
interesting from our perspective: implementation on a reversible machine. The rules imposed
7

For an example of a statically typed language with a prototype-based object model, see Omega [11].

Chapter 3 The Roopl Language

25 of 111

by these features on the classes of a program are generally enforced at compile-time - wholly
independently from the target architecture and its limitations (with the exception of dynamic
dispatch which has to be handled at runtime).
The object model of ROOPL is therefore very simple compared to these languages - introducing
access modifiers or static methods to ROOPL is possible but would be a meaningless venture as
the implementation of such features would be identical for an irreversible language. The ROOPL
object model is based on the following key points:
– All class fields are protected, they may be accessed only from within class methods and
subclass methods
– All class methods are public, they may be accessed from other objects
– All class methods are virtual and may be overridden in a subclass (but only by a method
with the same type signature, there is no support for method overloading)
– A class may inherit only from a single base class (single inheritance)
– Any method that takes an object reference of some type τ also works when passed a
reference of type τ 0 if τ 0 is a subclass of τ (subtype polymorphism)
– Local method calls are statically dispatched (closed recursion), only method calls to other
objects are dynamically dispatched
Note that the single inheritance object model of ROOPL still allows for inheritance hierarchies
of arbitrary depth (known as multi-level inheritance).

3.5

Object Instantiation

In irreversible OOP languages, object instantiation is typically accomplished in two or three
general steps:
1. A suitable amount of memory is reserved for the object
2. All fields are initialized to some neutral value
3. The class constructor is executed, establishing the class invariants of the object
When the program (or the garbage collector) deallocates the object, the memory is (typically)
simply marked as unused. Any leftover values from the internal state of the object will be
irreversibly overwritten if/when another object is initialized in the same part of memory later
on. In a reversible language we cannot clear leftover values in memory like this as that would
constitute a loss of information.
Instead we require unused memory to already be zero-cleared at the time of object creation,
so the fields of each new object have a known initial value. The only way to achieve this reversibly
is to uncompute all the state accumulated inside an object before it is deallocated, returning all
fields to the value zero. This cannot be done automatically so this responsibility lies with the
program itself.

Chapter 3 The Roopl Language

26 of 111

1
2

class Object
int data

3

method add5()
data += 5

4
5
6

method get(int out)
out ^= data

7
8
9
10
11

class Program
int result

12

method main()
construct Object obj
call obj::add5()
call obj::get(result)
uncall obj::add5()
destruct obj

13
14
15
16
17
18

//Allocate object
//Perform computation
//Fetch result
//Uncompute internal state
//Reversibly deallocate object

Figure 3.3: Simple example program illustrating the mechanics of an object block

A ROOPL object exists only within a construct/destruct block. Consider the statement:
construct c x s destruct x
the mechanics of such a statement are as follows:
1. Memory for an object of class c is allocated. All fields are automatically zero-initialized by
virtue of residing in already zero-cleared memory.
2. The block statement s is executed, with the name x representing a reference to the newly
allocated object.
3. The reference x may be modified by swapping its value with that of other references of
the same type, but it should be restored to its original value within the statement block s,
otherwise the meaning of the object block is undefined.
4. Any state that is accumulated within the object should be cleared or uncomputed before
the end of the statement is reached, otherwise the meaning of the object block is undefined.
5. The zero-cleared memory is reclaimed by the system.
If the fields of the object are not zero-cleared after the block statement, it becomes impossible
for the system to reversibly reclaim the memory occupied by the object. It is up to the program
to maintain this invariant.

3.6

Inheritance Semantics

Before we can define the type system and formal semantics of the language, we need a precise
definition of the object model as described in Section 3.4 and Section 3.5. Given the dynamic
type of some object, we wish to determine the class fields and class methods of the object such
that inherited fields and methods are included, unless overridden by the derived class.

Chapter 3 The Roopl Language

27 of 111

Γ

p

}|
{
z
gen(cl1 , . . . , cln )

=



= c

α class c · · ·

z

}|
{
α(cl1 ) 7→ β(cl1 ), . . . , α(cln ) →
7
β(cln )

β cl



=

fields(cl), methods(cl)



Figure 3.4: Definition of function gen, for constructing the class map of a given program

To this end, we define the class map Γ of a program p as a finite map from class identifiers
(type names) to tuples of the method and field declarations of that class. The application of
a class map Γ to some class identifier cl is denoted Γ(cl). Figure 3.4 shows the definition of
function gen, which is used to construct the class map of a program.
(


η(cl)
if cl ∼ class c · · ·



fields(cl) =
η(cl) ∪ fields α−1 (c0 )
if cl ∼ class c inherits c0 · · ·

(
methods(cl) =

A ] B



δ(cl)
if cl ∼ class c · · ·



δ(cl) ] methods α−1 (c0 )
if cl ∼ class c inherits c0 · · ·

def

= A ∪

n

ζ(m0 ) = ζ(m) ∧ m0 ∈ A

o

m ∈ B

@ m0

= q

z
}|
{

η class c · · · t1 f1 · · · tn fn · · ·
= fs

fs

ζ method q ( · · · ) s



ms

z
}|
{

δ class c · · · method q1 ( · · · ) s1 · · · method qn ( · · · ) sn · · ·
= ms
Figure 3.5: Definition of functions for modelling class inheritance

Figure 3.5 shows the definition of the functions fields and methods which determines the class
fields and class methods for a given class. The set operation ] implements method overriding by
dropping methods from the base class if a method with the same name exists in the derived class.

3.7

Type System

The type system of ROOPL is specified by the syntax-directed typing rules shown in the following
sections. There are three main type judgments covering expressions, statements and whole
ROOPL programs. The inference rules are presented in the style of Winskell [45] and are
arranged in such a way that a complete type derivation can only be constructed for well-typed
programs. The next section establishes the notation and presents auxiliary definitions.

Chapter 3 The Roopl Language

28 of 111

3.7.1

Preliminaries

The set of types in ROOPL is given by the grammar:
τ ::= int c ∈ ClassIDs
A type environment Π is a finite map from variable identifiers to types. The application of a
type environment Π to some identifier x is denoted by Π(x). Update Π0 = Π[x 7→ τ ] defines a
type environment Π0 s.t. Π0 (x) = τ and Π0 (y) = Π(y) if y 6= x. The empty type environment
is written [ ]. The function vars : Expressions → VarIDs, is given by the following recursive
definition:
vars(n)

= ∅

vars(nil)

= ∅

vars(x)

= {x}

vars(e1 ⊗ e2 ) = vars(e1 ) ∪ vars(e2 )
To facilitate support for subtype polymorphism, we also define a binary subtype relation c1 ≺: c2
for classes:
1. c1 ≺: c2 if c1 inherits from c2
2. c ≺: c (reflexivity)
3. c1 ≺: c3 if c1 ≺: c2 and c2 ≺: c3 (transitivity)

3.7.2

Expressions

The type judgment:
Π `expr e : τ
defines the type of expressions. We say that under environment Π, expression e has type τ .

Π `expr n : int

T-Con

Π(x) = τ
T-Var
Π `expr x : τ

τ 6= int
T-Nil
Π `expr nil : τ

Π `expr e1 : int
Π `expr e2 : int
T-BinOpInt
Π `expr e1 ⊗ e2 : int

Π `expr e1 : τ
Π `expr e2 : τ
Π `expr e1
e2 : int

∈ {=, !=}

T-BinOpObj

Figure 3.6: Typing rules for ROOPL expressions

The type rules T-Con, T-Var and T-Nil defines the types of simple expressions. Numeric
literals are always of type int, the type of some variable x depends on its type in the type
environment Π and the nil-literal can have any non-integer type. All binary operations are
defined for integers, while the equality and inequality comparisons are also defined for object
references.
Chapter 3 The Roopl Language

29 of 111

3.7.3

Statements

The type judgment:
hΠ, ci `Γstmt s
defines the well-typed statements. We say that under type environment Π within class c, the
statement s is well-typed with class map Γ.
x ∈
/ vars(e)

Π `expr e1 : int

Π `expr e1 : int

Π `expr e : int
Π(x) = int
T-AssVar
Γ
hΠ, ci `stmt x
=e

hΠ, ci `Γstmt s1
hΠ, ci `Γstmt s2
hΠ, ci `Γstmt if e1 then s1 else s2 fi e2

hΠ, ci `Γstmt s2
hΠ, ci `Γstmt s1
T-Seq
Γ
hΠ, ci `stmt s1 s2





f ields, methods

x1 , . . . , xn

Γ(Π(x0 )) =



T-If

hΠ, ci `Γstmt s1
hΠ, ci `Γstmt s2
Π `expr e2 : int
T-Loop
Γ
hΠ, ci `stmt from e1 do s1 loop s2 until e2

hΠ[x 7→ c0 ], ci `Γstmt s
T-ObjBlock
hΠ, ci `Γstmt construct c0 x s destruct x

Γ(c) =

Π `expr e2 : int





hΠ, ci `Γstmt skip

T-Skip

Π(x1 ) = Π(x2 )
T-SwpVar
hΠ, ci `Γstmt x1 <=> x2

method q(t1 y1 , . . . , tn yn ) s



∈ methods

∩ f ields = ∅
i 6= j =⇒ xi 6= xj
Π(x1 ) ≺: t1 · · · Π(xn ) ≺: tn
T-Call
Γ
hΠ, ci `stmt call q(x1 , . . . , xn )

f ields, methods





method q(t1 y1 , . . . , tn yn ) s

i 6= j =⇒ xi 6= xj
Π(x1 ) ≺: t1 · · · Π(xn ) ≺: tn
hΠ, ci `Γstmt call x0 ::q(x1 , . . . , xn )
hΠ, ci `Γstmt call q(x1 , . . . , xn )
T-UC
hΠ, ci `Γstmt uncall q(x1 , . . . , xn )



∈ methods
T-CallO

hΠ, ci `Γstmt call x0 ::q(x1 , . . . , xn )
T-UCO
hΠ, ci `Γstmt uncall x0 ::q(x1 , . . . , xn )

Figure 3.7: Typing rules for ROOPL statements

The type rule T-AssVar defines well-typed variable assignments as only those where both
sides of the assignment are of type int and the assignee identifier x does not occur in the expression
e. Rules T-If and T-Loop define the set of well-typed conditionals and loop statements - the
entry and exit conditions must be integers, while the branch and loop statements should be
Chapter 3 The Roopl Language

30 of 111

well-typed themselves. An object block is well-typed if the block statement is, with the new object
x bound in the type environment. The skip statement is always well-typed while a statement
sequence is well-typed provided each of its constituent statements are as well. A variable swap
statement is well-typed only if both of its operands have the same type.
A local method invocation is well-typed, in accordance with type rule T-Call, only if:
– The number of arguments matches the arity of the method
– No class fields are passed as arguments to the method (See Section 3.2)
– There are no duplicate arguments (See Section 3.2)
– Each argument is a subtype of the type of the equivalent formal parameter
The type rule T-CallO establishes similar conditions for foreign method invocations, for
which there is no restriction on class fields being used as arguments. There is however, the
condition that the callee object x0 is not also passed as an argument. The type rules T-UC and
T-UCO describe the conditions for uncalling methods and they are both defined in terms of
their inverse counterparts.

3.7.4

Programs

hΠ[x1 7→ t1 , . . . , xn 7→ tn ], ci `Γstmt s
T-Method
hΠ, ci `Γmeth method q(t1 x1 , . . . , tn xn ) s
f ields

methods

 z
}|
{ z
}|
{ 
Γ(c) = {ht1 , f1 i, . . . , hti , fi i}, {m1 , . . . , mn }
Π = [f1 7→ t1 , . . . , fi 7→ ti ]



hΠ, ci `Γmeth m1
`Γclass c

method main() s



∈

n
[

···

hΠ, ci `Γmeth mn

T-Class

methods(ci )

i=1

Γ = gen(c1 , . . . , cn )
`Γclass c1
`prog c1 · · · cn

···

`Γclass cn

T-Prog

Figure 3.8: Typing rules for ROOPL methods, classes and programs

The type rules T-Prog, T-Class and T-Method defines the set of well-typed programs,
classes and methods respectively.
A class is well-typed iff each of its methods are well-typed with all class fields bound to their
respective types in the type environment. A method is well-typed iff its body is well-typed with
all parameters bound to their respective types in the type environment. A ROOPL program is
well-typed iff all of its classes are well-typed and there exists a nullary method named main. See
Figure 3.5 for the definition of function methods.
Chapter 3 The Roopl Language

31 of 111

3.8

Language Semantics

The operational semantics of ROOPL are specified by the syntax-directed inference rules shown
in the following sections. There are three main judgments: the evaluation of ROOPL expressions,
the execution of ROOPL statements and the execution of ROOPL programs. The next section
establishes the notation and presents some auxiliary definitions.

3.8.1

Preliminaries

Let N0 be the set of non-negative integers. A memory location l ∈ N0 refers to a single location in
program memory. An environment γ is a partial function mapping variable identifiers to memory
locations. A store µ is a partial function mapping memory locations to values. An object is a
tuple consisting of the class name of the object and an environment mapping the object fields to
memory locations. A value v is either an integer, an object or a memory location.
The application of an environment γ to some variable identifier x is denoted by γ(x). Update
0
γ = γ[x 7→ l] defines an environment γ 0 such that γ 0 (x) = l and γ 0 (y) = γ(y) if y 6= x. The
empty environment is written [ ]. The same notation is used for stores.

l ∈ Locs

=

N0

γ ∈ Envs

=

VarIDs * Locs

µ ∈ Stores

=

Locs * Values

Objects =
v ∈ Values

=

{ hcf , γf i | cf ∈ ClassIDs ∧ γf ∈ Envs }
Z ∪ Objects ∪ Locs
Figure 3.9: Semantic values

3.8.2

Expressions

The judgment:
hγ, µi `expr e ⇒ v
defines the meaning of expressions. We say that under environment γ and store µ, expression e
evaluates to the value v.

hγ, µi `expr n ⇒ n

Con

hγ, µi `expr x ⇒ µ(γ(x))

hγ, µi `expr e1 ⇒ v1
hγ, µi `expr e2 ⇒ v2
hγ, µi `expr e1 ⊗ e2 ⇒ v

Var

hγ, µi `expr nil ⇒ 0

J⊗K(v1 , v2 ) = v

Nil

BinOp

Figure 3.10: Semantic inference rules for evaluation of ROOPL expressions

There are no side effects on the store when evaluating a ROOPL expression. Like in Janus,
the logic value true is represented by any non-zero integer, while false is represented by zero.
Chapter 3 The Roopl Language

32 of 111

For the sake of simplicity, nil evaluates to 0, which can never be the value of a non-nil reference,
thereby ensuring that the equality and inequality operators behave as expected.

J+K(v1 , v2 ) = v1 + v2

J%K(v1 , v2 ) = v1 mod v2

J*K(v1 , v2 ) = v1 × v2

J|K(v1 , v2 ) = v1 or v2

J/K(v1 , v2 ) =

JˆK(v1 , v2 ) = v1 xor v2

J-K(v1 , v2 ) = v1 − v2

J&&K(v1 , v2 ) =
J||K(v1 , v2 ) =
J<K(v1 , v2 ) =
J>K(v1 , v2 ) =

v1
v2
(
0
1
(
0
1
(
1
0
(
1
0

J&K(v1 , v2 ) = v1 and v2

if v1 = 0 ∨ v2 = 0
otherwise

J<=K(v1 , v2 ) =

if v1 = v2 = 0
otherwise

J>=K(v1 , v2 ) =

if v1 < v2
otherwise

J=K(v1 , v2 ) =

if v1 > v2
otherwise

J!=K(v1 , v2 ) =

(
1
0
(
1
0
(
1
0
(
1
0

if v1 ≤ v2
otherwise
if v1 ≥ v2
otherwise
if v1 = v2
otherwise
if v1 6= v2
otherwise

Figure 3.11: Definition of the functions J⊗K, where ⊗ represents any of the binary expression operators

The inference rules Con, Var and Nil defines the meaning of expressions containing simple
values or variables, while BinOp defines the meaning of expressions containing any of the
arithmetic operators {+, -, *, /, %}, bitwise operators {&, |, ^}, logical operators {&&, ||}
or relational operators {<, >, =, !=, <=, >=}, all of which are defined in Figure 3.11.

3.8.3

Statements

The judgment:
hl, γi `Γstmt s : µ

µ0

defines the meaning of statements. We say that under environment γ and object l, statement s
with class map Γ reversibly transforms store µ to store µ0 . The location l is simply the location
in the store µ of the current object. It is equivalent to the value of the this or self keywords of
other OOP languages but cannot be referred to explicitly in ROOPL. Figure 3.12a on page 34
and Figure 3.12b on page 35 shows the operational semantics of ROOPL statements.
Rule Skip defines the meaning of the skip statement which has no effect on the store µ. Rule
Seq defines the meaning of statement sequences and rule AssVar defines reversible assignments.
The rules LoopMain, LoopBase and LoopRec defines the meaning of loops. If assertion
e1 holds, the loop is entered by rule LoopMain. Then the loop iterates by rule LoopRec
until e2 does not hold, terminating the loop by rule LoopBase. Since conditionals and loops in
ROOPL are comparable to those in Janus, these rules are similar to those presented in [46].
The semantics of conditional statements are given by rules IfTrue and IfFalse. If the entry
condition evaluates to true (non-zero), then the then-branch is executed and the exit assertion

Chapter 3 The Roopl Language

33 of 111

hl, γi `Γstmt skip : µ

µ

Skip

hl, γi `Γstmt s1 : µ
µ0
hl, γi `Γstmt s2 : µ0
hl, γi `Γstmt s1 s2 : µ
µ00

µ00

Seq

hγ, µi `expr e ⇒ v
J K(µ(γ(x)), v) = v 0
AssVar
Γ
hl, γi `stmt x = e : µ
µ[γ(x) →
7
v0 ]
µ(γ(x1 )) = v1
hl, γi `Γstmt x1 <=> x2 : µ

hγ, µi `expr e1 6⇒ 0
hl, γi

µ(γ(x2 )) = v2
SwpVar
µ[γ(x1 ) 7→ v2 , γ(x2 ) 7→ v1 ]
µ0

hl, γi `Γstmt s1 : µ

hl, γi `Γloop (e1 , s1 , s2 , e2 ) : µ0
µ00
from e1 do s1 loop s2 until e2 : µ

`Γstmt

hl, γi

hγ, µi `expr e2 6⇒ 0
(e1 , s1 , s2 , e2 ) : µ

`Γloop

µ

µ00

LoopBase

hγ, µi `expr e2 ⇒ 0

hl, γi `Γstmt s2 : µ

µ0

hγ, µ0 i `expr e1 ⇒ 0

hl, γi `Γstmt s1 : µ0

µ00

hl, γi `Γloop (e1 , s1 , s2 , e2 ) : µ00
hl, γi `Γloop (e1 , s1 , s2 , e2 ) : µ

LoopMain

µ000
µ000

LoopRec

hγ, µi `expr e1 6⇒ 0
hl, γi `Γstmt s1 : µ
µ0
hγ, µ0 i `expr e2 6⇒ 0
IfTrue
Γ
hl, γi `stmt if e1 then s1 else s2 fi e2 : µ
µ0
µ0
hγ, µ0 i `expr e2 ⇒ 0
hγ, µi `expr e1 ⇒ 0
hl, γi `Γstmt s2 : µ
IfFalse
hl, γi `Γstmt if e1 then s1 else s2 fi e2 : µ
µ0
Figure 3.12a: Semantic inference rules for execution of ROOPL statements

should also evaluate to true. If the entry condition evaluates to false, the else-branch is executed
and the exit assertion should evaluate to false.
Rule Call defines the meaning of invoking a method local to the current object. The method
q in the current class c should have exactly n formal parameters y1 , . . . , yn , matching the n
arguments x1 , . . . , xn . The resulting store µ0 is the store obtained from executing the method
body s in the object environment γ 0 with the arguments bound to the formal parameters.
Rule Uncall essentially reverses the direction of execution by requiring the input store of a
Chapter 3 The Roopl Language

34 of 111


f ields, methods


method q(t1 y1 , . . . , tn yn ) s
∈ methods
µ(l) = hc, γ 0 i

Γ(c) =



hl, γ 0 [y1 7→ γ(x1 ), . . . , yn 7→ γ(xn )]i `Γstmt s : µ
hl, γi `Γstmt call q(x1 , . . . , xn ) : µ
µ0
hl, γi `Γstmt call q(x1 , . . . , xn ) : µ0
hl, γi `Γstmt uncall q(x1 , . . . , xn ) : µ

µ0
Call

µ
Uncall
µ0



l0 = µ(γ(x0 ))
µ(l0 ) = hc, γ 0 i
Γ(c) = f ields, methods


method q(t1 y1 , . . . , tn yn ) s
∈ methods
hl0 , γ 0 [y1 7→ γ(x1 ), . . . , yn 7→ γ(xn )]i `Γstmt s : µ
hl, γi `Γstmt call x0 ::q(x1 , . . . , xn ) : µ
µ0
hl, γi `Γstmt call x0 ::q(x1 , . . . , xn ) : µ0
hl, γi `Γstmt uncall x0 ::q(x1 , . . . , xn ) : µ

µ0
CallOBj

µ
UncallObj
µ0

f ields

 z

}|
{
Γ(c) = {ht1 , f1 i, . . . , htn , fn i}, methods
γ 0 = [f1 7→ a1 , . . . , fn 7→ an ]
 0
 0
l , r, a1 , . . . , an
∩ dom(µ) = ∅
l , r, a1 , . . . , an
= n + 2
"
#
Γ
0
a1 7→ 0, . . . , an 7→ 0
hl, γ[x 7→ r]i `stmt s : µ
µ00
µ0 = µ 0
l 7→ hc, γ 0 i, r 7→ l0
µ00 (a1 ) = 0 · · · µ00 (an ) = 0
hl, γi `Γstmt construct c x

s destruct x : µ

µ00 dom(µ)

ObjBlock

Figure 3.12b: Semantic inference rules for execution of ROOPL statements (cont.)

call statement to serve as the output store of the inverse uncall statement. A similar technique
was used in [49, 46].
Rule CallObj governs invocation of methods not local to the current object. The resulting
store µ0 is the store obtained from executing the method body s in the environment γ 0 of the
object x0 , with the arguments bound to the formal parameters. The inverse rule UncallObj is
defined using the same approach used for rule Uncall.
Even if x0 has been upcast to a base class (as allowed by the type system, see Section 3.7)
earlier in the program, the class name c refers to the dynamic type of x0 . As a result, the method
lookup will correctly yield the appropriate method from the derived class - in accordance with
the concept of subtype-polymorphism (the actual mechanism used to achieve dynamic dispatch,
virtual lookup tables, are considered an implementation detail at this point). Method dispatch
in ROOPL depends only on the name of the method and the type of the callee object, not on
the number of arguments nor their individual types (single dispatch).
Chapter 3 The Roopl Language

35 of 111

Rule ObjBlock defines the meaning of a construct/destruct block and the semantics of
object construction and destruction. The construct/destruct blocks of ROOPL are similar
to the local/delocal blocks of Janus. In both cases, it is the program itself that is responsible
for reversibly returning the memory to a state where it can be reclaimed by the system and in
the presence of recursion, there is no upper bound on the size the store can grow to. Like in
Janus, if x is already in scope when a block scope is entered, that variable is shadowed by the
new object x within the statement block (static lexical scoping).
The new memory locations l0 , r and a1 , . . . , an should be unused in the store µ and they
should all represent distinct memory locations. The identifiers f1 , . . . , fn representing the fields
of the new object are bound to the unused memory locations a1 , . . . , an in the new object
environment γ 0 . Next, we let µ0 be the updated store containing:
– The location l mapped to the object tuple hc, γ 0 i
– The object reference r mapped to the location l
– The n new object fields mapped to 0
The result store µ00 (restricted to the domain of µ) is the store obtained from executing the
block statement s in store µ0 under environment γ mapping x to the object reference r, provided
all object fields are zero-cleared in µ00 afterwards (otherwise the statement is undefined).

3.8.4

Programs

The judgment:
`prog p ⇒ σ
defines the meaning of ROOPL programs. Whichever class in p contains the main method is
instantiated and the main method body is executed. The result is a partial function σ mapping
identifiers to values, corresponding to the class fields of the main class.
f ields

 z

}|
{
Γ(c) = {ht1 , f1 i, . . . , hti , fi i}, methods

Γ = gen(c1 , . . . , cn )


method main() s
∈ methods

γ = [f1 7→ 1, . . . , fi 7→ i]

µ = [1 7→ 0, . . . , i 7→ 0, i + 1 →
7
hc, γi]
hi + 1, γi `Γstmt s : µ
`prog c1 · · · cn ⇒ (µ0 ◦ γ)

µ0
Main

Figure 3.13: Semantic inference rule for execution of ROOPL programs

Rule Main defines the meaning of a ROOPL program. The fields f1 , . . . , fi of the class c
containing the main method are bound in a new environment γ to the first i memory addresses
(excluding address 0 which is reserved for nil). The first i memory addresses are then initialized
to 0 in a new environment µ as well as the address i + 1 which maps to the new instance of the
main object. The modified store µ0 is obtained from executing the body s of the main method.
The composite function (µ0 ◦ γ), which maps each class field to its final value, serves as the
output of executing p.
Chapter 3 The Roopl Language

36 of 111

3.9

Program Inversion

A common formulation of the Church-Turing thesis states that a function f is computable iff
there exists some Turing Machine that computes it. By extension, if some program p, written in
a Turing-equivalent programming language8 , computes a function f then f is computable.
Program inversion is the process of determining an inverse program of p, computing the
function f −1 . Given a computable function f : X → Y , we wish to find a program computing
the function f 0 : Y → X such that:
f (x) = y

⇔

f 0 (y) = x

Since f is computable, we can compute f 0 (y) by simulating f on all inputs x ∈ X until the
result is y. This is a variation of McCarthy’s generate-and-test technique [31], which implies that
we can always find the inverse program if f is computable. Unfortunately, this is a completely
impractical approach to program inversion. McCarthy himself described his approach in the
following terms:
[. . .] this procedure is extremely inefficient. It corresponds to looking for a proof of a
conjecture by checking in some order all possible English essays. [31]
Recently, more practical methods for automatic program inversion of irreversible programs
have superseded the generate-and-test algorithm [22]. In the context of reversible programming
languages, program inversion is both simple and efficient. Reversible languages like Janus and
ROOPL support local inversion of program statements - no contextual information or wholeprogram analysis is needed [21]. This is a property of reversible languages that follows from
the nature of their design and the constraints they impose on the programmer. The statement
inverter I in Figure 3.14 maps ROOPL statements to their inverse counterparts.
I JskipK = skip

I Js1 s2 K = IJs2 K IJs1 K

I Jx += eK = x -= e

I Jx -= eK = x += e

I Jx ^= eK = x ^= e

I Jx1 <=> x2 K = x1 <=> x2

I Jcall q( . . . )K = uncall q( . . . )

I Jcall x::q( . . . )K = uncall x::q( . . . )

I Juncall q( . . . )K = call q( . . . )

I Juncall x::q( . . . )K = call x::q( . . . )

I Jif e1 then s1 else s2 fi e2 K

= if e1 then IJs1 K else IJs2 K fi e2

I Jfrom e1 do s1 loop s2 until e2 K

= from e1 do IJs1 K loop IJs2 K until e2

I Jconstruct c x

= construct c x

s destruct xK

IJsK destruct x

Figure 3.14: Statement inverter for ROOPL statements

In ROOPL, statement inversion does not change the size of statements and as a consequence,
a ROOPL program is exactly the same size as its own inverse. Furthermore, provided that every
statement has the same computational complexity as its inverse, it follows that ROOPL programs
have the same computational complexity as their inverted counterparts.
8

or indeed any algorithm specified in a Turing-equivalent model of computation

Chapter 3 The Roopl Language

37 of 111

u
w
w
Ic w
w
v

class c · · ·

}

class c · · ·

method q1 ( . . . ) s1 

 =
..

~
.
method qn ( . . . ) sn

method q1 ( . . . ) I 0 Js1 K
..
.
method qn ( . . . ) I 0 Jsn K

Iprog Jcl1 · · · cln K = Ic Jcl1 K · · · Ic Jcln K
Figure 3.15: Program and class inverters for ROOPL

Whole-program inversion is accomplished by straightforward recursive descent over the
components and statements of the program. Figure 3.15 shows the definition of the ROOPL
program inverter Iprog , which inverts each method in each class to produce the inverse program.
The program inverter Iprog is an involution, so inverting a program twice will yield the original
program.
I 0 Jcall q( . . . )K = call q( . . . )

I 0 Juncall q( . . . )K = uncall q( . . . )

I 0 Jcall x::q( . . . )K = call x::q( . . . )

I 0 Juncall x::q( . . . )K = uncall x::q( . . . )

I 0 JsK = IJsK

Figure 3.16: Modified statement inverter for ROOPL statements

Because calling a method is equivalent to uncalling the same method inverted, if we change
call-statements into uncall-statements and vice-versa, the inversion of the method body is
cancelled out.
To fix this issue, we use a modified version of the statement inverter for the whole-program
inversion, that does not invert calls and uncalls. Figure 3.16 shows the modified statement
inverter I 0 .

3.9.1

Invertibility of Statements

Theorem 3.1 shows that I is in fact a statement inverter. If executing statement s in store µ
yields µ0 , then executing statement IJsK in store µ0 should yield µ.
Theorem 3.1. (Invertibility of statements)
S

z
}|
hl, γi `Γstmt s : µ

S0

{
z
}|
µ0 ⇐⇒ hl, γi `Γstmt IJsK : µ0

{
µ

Proof. The proof is by structural induction on the semantic derivation of S but is omitted. It
suffices to show that S implies S 0 - since this can also serve as proof that S 0 implies S because I
is an involution.

Chapter 3 The Roopl Language

38 of 111

3.9.2

Type-Safe Statement Inversion

When given a well-typed statement, the statement inverter I should always produce a well-typed
(inverse) statement. This is an important property of the language as it prevents situations where
some method can be called successfully, but uncalling the same method produces an error or
undefined behaviour. The following theorem expresses this property:
Theorem 3.2. (Inversion of well-typed statements)
T0

T

z
}|
{
z
}|
{
Γ
Γ
hΠ, ci `stmt s =⇒ hΠ, ci `stmt IJsK
Proof. By structural induction on T :

Case T =

C1

E

C2

}|
{
z
x ∈
/ vars(e)

}|
{
z
Π `expr e : int
hΠ, ci `Γstmt x
=e

z
}|
{
Π(x) = int

AssVar

In this case, IJx
= eK = x 0 = e for some 0 , so T 0 will also be a derivation of rule
AssVar. Therefore we can just reuse the expression derivation E and the conditions C1
and C2 to construct T 0 :
C1

T0 =

Case T =

C2

E

}|
{
z
x ∈
/ vars(e)

z
}|
{
z
}|
{
Π `expr e : int
Π(x) = int
hΠ, ci `Γstmt x 0 = e

Π(x1 ) = Π(x2 )
T-SwpVar
hΠ, ci `Γstmt x1 <=> x2

Since IJx1 <=> x2 K = x1 <=> x2 , we can just use the derivation of T for T 0 :
T0 =

Π(x1 ) = Π(x2 )
hΠ, ci `Γstmt x1 <=> x2
S1

E1

Case T =

z
}|
{
Π `expr e1 : int

We have:

I Jif e1 then s1 else s2 fi e2 K = if e1 then IJs1 K else IJs2 K fi e2

By the induction hypothesis on S1 we get:
By the induction hypothesis on S2 we get:
Using E1 , S10 , S20 and E2 we can construct T 0 :
E1

T

0

=

S2

E2
z
}|
{ z
}|
{ z
}|
{
Γ
Γ
hΠ, ci `stmt s1
hΠ, ci `stmt s2
Π `expr e2 : int
T-If
hΠ, ci `Γstmt if e1 then s1 else s2 fi e2

z
}|
Π `expr e1

S10

S10 = hΠ, ci `Γstmt IJs1 K

S20 = hΠ, ci `Γstmt IJs2 K
S20

E2
}|
{ z
}|
{ z
{ z
}|
{
Γ
Γ
: int hΠ, ci `stmt IJs1 K hΠ, ci `stmt IJs2 K Π `expr e2 : int
hΠ, ci `Γstmt if e1 then IJs1 K else IJs2 K fi e2

Chapter 3 The Roopl Language

39 of 111

S1

S2

E1
E2
}|
{ z
}|
{ z
}|
{ z
}|
{
z
Γ
Γ
Π `expr e1 : int hΠ, ci `stmt s1
hΠ, ci `stmt s2
Π `expr e2 : int
T-Loop
Case T =
hΠ, ci `Γstmt from e1 do s1 loop s2 until e2

We have:

I Jfrom e1 do s1 loop s2 until e2 K = from e1 do IJs1 K loop IJs2 K until e2
S10 = hΠ, ci `Γstmt IJs1 K

By the induction hypothesis on S1 we get:
By the induction hypothesis on S2 we get:
Using E1 , S10 , S20 and E2 we can construct T 0 :

S20 = hΠ, ci `Γstmt IJs2 K

S10

T0

S20

E1
E2
}|
{ z
}|
{ z
z
}|
{ z
}|
{
Γ
Γ
Π `expr e1 : int hΠ, ci `stmt IJs1 K hΠ, ci `stmt IJs2 K Π `expr e2 : int
=
hΠ, ci `Γstmt from e1 do IJs1 K loop IJs2 K until e2
S1

S2

z
}|
{
z
}|
{
hΠ, ci `Γstmt s1
hΠ, ci `Γstmt s2
Case T =
T-Seq
hΠ, ci `Γstmt s1 s2

We have:

I Js1 s2 K = IJs2 K IJs1 K

By the induction hypothesis on S1 we get:
By the induction hypothesis on S2 we get:
Using S10 and S20 we can construct T 0 :
S20

T0

S10 = hΠ, ci `Γstmt IJs1 K

S20 = hΠ, ci `Γstmt IJs2 K

S10

z
}|
{
}|
{
z
hΠ, ci `Γstmt IJs2 K
hΠ, ci `Γstmt IJs1 K
=
hΠ, ci `Γstmt IJs2 K IJs1 K

Case T =

hΠ, ci `Γstmt skip

T-Skip

Since I JskipK = skip, and T-Skip is axiomatic, we can choose T as:
T0 =

hΠ, ci `Γstmt skip
S

z
}|
{
hΠ[x 7→ c0 ], ci `Γstmt s
Case T =
T-ObjBlock
hΠ, ci `Γstmt construct c0 x s destruct x

We have:

I Jconstruct c x s destruct xK = construct c x IJsK destruct x

By the induction hypothesis on S we get:

S 0 = hΠ[x 7→ c0 ], ci `Γstmt IJsK

Which we can use to construct T 0 :
S0

T0

z
}|
{
hΠ[x 7→ c0 ], ci `Γstmt IJsK
=
hΠ, ci `Γstmt construct c0 x IJsK destruct x

Chapter 3 The Roopl Language

40 of 111

Case T =

···
T-Call
hΠ, ci `Γstmt call q(x1 , . . . , xn )

We have:

I Jcall q( . . . )K = uncall q( . . . )

Which means T 0 must be of the form:
S

T0

z
}|
{
hΠ, ci `Γstmt call q(x1 , . . . , xn )
=
hΠ, ci `Γstmt uncall q(x1 , . . . , xn )

Where we can simply use the derivation of T in place of S.
Case T =

hΠ, ci

We have:

`Γstmt

···
T-CallO
call x0 ::q(x1 , . . . , xn )

I Jcall x::q( . . . )K = uncall x::q( . . . )

Which means T 0 must be of the form:
S

T0

z
}|
{
hΠ, ci `Γstmt call x0 ::q(x1 , . . . , xn )
=
hΠ, ci `Γstmt uncall x0 ::q(x1 , . . . , xn )

Where we can simply use the derivation of T in place of S.
S

z
}|
{
hΠ, ci `Γstmt call q(x1 , . . . , xn )
Case T =
T-UC
hΠ, ci `Γstmt uncall q(x1 , . . . , xn )

We have:

I Juncall q( . . . )K = call q( . . . )

Which means we can just use the derivation S as T 0 .
S

z
}|
{
hΠ, ci `Γstmt call x0 ::q(x1 , . . . , xn )
Case T =
T-UCO
hΠ, ci `Γstmt uncall x0 ::q(x1 , . . . , xn )

We have:

I Juncall x::q( . . . )K = call x::q( . . . )

Which means we can just use the derivation S as T 0 .

Using Theorem 3.2, we can show that well-typedness is also preserved over inversion of methods.
By type rule T-Method (See Figure 3.8, page 31), we see that a method is well-typed iff its
body is well-typed.
The class inverter Ic (See Figure 3.15) defines the inverse of a method q with body s, as the
same method with the body IJsK. By Theorem 3.2, we know that if s is well-typed, then so is
IJsK - by extension, if q is well-typed then so is the inverse of q.
By the definition of the class inverter and the program inverter, it is clear that this result
also extends to inversion of classes and inversion of programs.

Chapter 3 The Roopl Language

41 of 111

3.10

Language Extensions

The language extensions introduced in this section are not part of the core language, but are
used in the ROOPL programs we present in subsequent sections and chapters.

3.10.1

Local Variables

Due to the restriction prohibiting member variables being passed to methods of the same object,
it is sometimes necessary to create proxy objects or needlessly complicated structures to achieve
relatively simple tasks. The restriction only serves to avoid aliasing situations, so we can make the
life of a ROOPL programmer easier by adding the local/delocal blocks from Janus to ROOPL:
local int x = e1

s delocal x = e2

Unlike in Janus, only integers can be allocated this way. If x is already in scope at the time
this statement occurs, the new x shadows the definition of the existing x, just as is the case for
object blocks. The semantics of this statement were already covered in [46] and do not differ in
any noticeable way in ROOPL.

3.10.2

Class Constructors and Deconstructors

In OOP, a class invariant is a constraint placed on the internal state of an object. Consider a
Date class representing a specific day of the year, with member variables denoting the day of the
month and the month of the year as integers. An obvious invariant for this class is that the day
of the month should always be between 1 and 31 inclusively and the month should always be
between 1 and 12 inclusively. Class invariants are an instance of contract programming 9 that is
especially relevant for OOP, where we wish to hide the internal constraints of a class behind the
public interface.
In ROOPL, all newly created objects are always zero-initialized, which is directly at odds
with the notion of class invariants. In our example, this means that all Date objects start out
representing day 0 of month 0 which is outside of our established invariant and inconsistent with
the rules of the system we are modelling. If we, instead, allow the programmer to specify how an
object should be initialized, we can make sure that class invariants are enforced throughout an
objects’ lifetime.
construct c x
construct c x(x1 , . . . , xn )
s
destruct x(z1 , . . . , zn )

def

=

call x::constructor(x1 , . . . , xn )
s
uncall x::constructor(z1 , . . . , zn )
destruct x

Figure 3.17: Class constructor/deconstructor extension

9

Popularized by languages such as Eiffel and D, which both include support for automatically verifying class
invariants at runtime.

Chapter 3 The Roopl Language

42 of 111

Figure 3.17 shows a new form of the construct/destruct statement, which automatically
invokes the special method constructor when a new object is created, establishing the class invariants of the object. After the block statement is executed, the constructor is then automatically
uncalled (we call this the deconstructor call) before the object is then finally deallocated. The
purpose of the deconstructor is to uncompute the state accumulated within the object by the
constructor (and possibly by other method invocations within s).
Ideally the compiler should be able to enforce that the default constructor (which zeroinitializes the object) is only ever invoked when the class in question does not specify its own
constructor. The proposed implementation only shows how to implement class constructors/deconstructors in terms of the core language.
1
2
3

class Date
int day
int month

//Invariant:
//Invariant:

1 <= day <= 31
1 <= month <= 12

4
5
6
7
8
9
10

method constructor(int d, int m)
if d <= 0 then
day += 1
else
day += d % 31
fi d <= 0

11
12
13
14
15
16

if m <= 0 then
month += 1
else
month += m % 12
fi m <= 0

17
18
19
20
21
22
23
24

method nextDay()
if day = 31 then
day -= 30
call nextMonth()
else
day += 1
fi day = 1

25
26
27
28
29
30
31

method nextMonth()
if month = 12 then
month -= 11
else
month += 1
fi month = 1

32
33
34

method getDay(int out)
out ^= day

35
36
37

method getMonth(int out)
out ^= month

Figure 3.18: ROOPL class representing a calendar date

Note that there is no requirement that the constructor and deconstructor are given the
same arguments. The only requirements are that the class invariants are established after the
constructor call and that the internal state of the object is zero-cleared after the deconstructor
call. Figure 3.18 shows how an implementation of a simplified Date class might look in ROOPL,
with accessors and constructor/deconstructor method included.

Chapter 3 The Roopl Language

43 of 111

3.10.3

Expression Arguments

Like in both Janus and R, we permit expressions to be used as arguments to a method provided
the method does not directly alter the value of the parameter in any way. If the value of the
expression parameter is altered by the callee, the meaning of the call is undefined.
local int x0 = e

def

=

call q( . . . , e, . . . )

call q( . . . , x0 , . . . )
delocal x0 = e

Figure 3.19: Language extension for expressions as method arguments

3.10.4

Method Reversal

Because arguments are passed by reference, a method invocation can bring about changes to
many or all of the argument variables in the caller. On top of this, ROOPL methods are impure
and can result in alterations being made to the internal state of one or more objects.

def

reversal q(x1 , x2 ) s

=

call q(x1 , x2 )
s
uncall q(x1 , x2 )

Figure 3.20: Language extension for single-statement method reversals

A common pattern for reversibly dealing with side effects and extra data is to sandwich the
statement block handling the result between a call and an uncall of the method in question. This
allows the programmer to copy the result or utilize it in some computation without worrying
about the subsequent clean up. Figure 3.20 shows a language extension that conveniently reduces
this pattern to a single statement.

3.10.5

Short Form Control Flow

For the sake of convenience, we introduce short forms for conditionals and loops.

if e1 then s fi e2
from e1 do s until e2
from e1 loop s until e2

def
=
def
=
def
=

if e1 then s else skip fi e2
from e1 do s loop skip until e2
from e1 do skip loop s until e2

Figure 3.21: Syntactic sugar for short form conditionals and loops

Chapter 3 The Roopl Language

44 of 111

3.11

Language Idioms

Like in conventional programming languages, specific program patterns are used, in ROOPL,
to express recurring tasks or constructs that are not built-in features of the language. Such
programming idioms are discussed in the following sections.

3.11.1

Zero-Cleared Copying

Care must be taken when copying and clearing values in a reversible language. Copying the
value of one variable to another can only be done reversibly if the destination variable is zerocleared, otherwise the value of the destination variable must be overwritten, resulting in a loss of
information. Likewise, clearing the value of some variable is only possible if the same value is
stored elsewhere at the same point in time, also to prevent loss of information. In ROOPL, both
copying and clearing can be achieved with an XOR-assignment:
x ^= y
If x = y before the above statement, then x is zero-cleared. If x = 0 before the assignment,
then the value of y is copied into x. This technique was first described in [49].

3.11.2
1
2

Mutators and Accessors

class Object
int data

3
4
5

method get(int out)
out ^= data

6
7
8

method swap(int in)
data <=> in

9
10
11

method sub(int val)
data -= val

12
13
14

method add(int val)
data += val

15
16
17

method xor(int val)
data ^= val

Figure 3.22: Basic mutator and accessor methods in ROOPL

In accordance with the principle of encapsulation, the member variables of a ROOPL object
are not directly accessible from outside the methods of that object. To facilitate access, we can
implement special accessor and mutator methods (colloquially known as getters and setters).
The semantics of accessors and mutators are slightly different in a reversible language. In
conventional OOP languages, a mutator will simply assign a new value to the member variable,
overwriting the existing value. In ROOPL we are limited to reversible mutators, exemplified by
the methods swap, sub, add and xor in Figure 3.22.
The swap mutator works mostly like a conventional mutator, but rather than irreversibly
overwriting the existing value, it places that value in the parameter, leaving the caller responsible
for uncomputing or clearing it.
Chapter 3 The Roopl Language

45 of 111

Since ROOPL does not support return values, we must supply the accessor method get with
an output parameter. Provided the argument variable is zero-cleared before invocation, the value
of the member variable is copied into the argument and thereby made accessible to the caller,
outside of the object.

3.11.3

Abstract Methods

An abstract method is a method with only a method signature but no method body. If a class
contains an abstract method, it cannot be instantiated. Instead a subclass can override the
abstract method and provide a method body, in which case the subclass can be instantiated.
Abstract methods are used as a way to define interfaces - the base class contains a number of
abstract methods that all subclasses must implement.
1
2
3
4

//Shape interface
class Shape
method resize(int scale)
skip //Abstract method

5
6
7

method translate(int x, int y)
skip //Abstract method

8
9
10

method draw()
skip //Abstract method

11
12
13

method getArea(int out)
skip //Abstract method

Figure 3.23: Example of an interface in ROOPL

ROOPL does not have any special facilities for supporting abstract methods (See Section 3.4)
but we can simulate abstract methods and class interfaces by using the skip statement as a
method body for the abstract methods of an interface. Figure 3.23 shows an example of a class
interface defined in this manner.

3.11.4

Call-Uncall

A core tenet of modern software development is the DRY-principle [26], short for Don’t Repeat
Yourself. It holds that duplication in logic should be eliminated via abstraction, which usually
entails using methods and procedures to facilitate code reuse in a program10 .
In a reversible language like ROOPL, however, every statement has two distinct meanings
depending on the direction of execution and therefore twice as many possible applications for
the programmer to consider. As such, the potential for code reuse in ROOPL programs is
considerable - many common programming tasks have an equally common inverse (the canonical
examples are the push and pop operations of a stack), but in ROOPL such inversions are free in
terms of programming effort and code size.
Another idiomatic use of the uncall mechanism is the compute-copy-uncompute technique,
which reversibly uncomputes intermediate values left over after a computation, retaining only
the desired results.
10

In fact the DRY-principle also holds that duplication in process and testing should be eliminated by automation.
In the absence of DRY, a software project is said to become WET (Write Everything Twice), which is generally
considered a very error-prone approach to software development.

Chapter 3 The Roopl Language

46 of 111

3.11.5

Linked Lists

While Janus included built-in support for arrays [49] and stacks [46], ROOPL does not support
any data structures or collections as language primitives11 . Using recursion and recursively
defined data types, we can define a linked list in ROOPL even without built-in support for arrays
or other types of collections.
1
2
3

class Node //Represents a single node in the list
int data
Node next //Reference to next node in the list

4
5
6
7
8

//Constructor method
method constructor(int d, Node n)
data ^= d
next <=> n

9
10
11
12

//Accessor & mutator methods
method add(int out)
out += data

13
14
15

method sub(int out)
out -= data

16
17
18

method xor(int out)
out ^= data

19
20
21

method swap(int out)
out <=> data

22
23
24

method swapNext(Node out)
out <=> next

25
26
27
28
29
30

method length(int out) //Finds the length of the list
out += 1
if next != nil then
call next::length(out)
fi next != nil

31
32
33
34
35
36
37
38

method insert(int n, Node new) //Inserts a (single) new node in the list
if n = 0 then
next <=> new
else
if n = 1 then
next <=> new
fi n = 1

39
40
41
42
43
44
45

if next != nil then
n -= 1
call next::insert(n, new)
n += 1
fi next != nil
fi n = 0

Figure 3.24a: Example of recursively defined linked lists in ROOPL

Figure 3.24a shows the definition of a Node class which contains a single integer and a
reference to the next node in the list, which is always nil for the last node in a list. The node
11

There is no inherent reason such language constructs could not be added to ROOPL, and they would likely
improve the expressiveness of the language. However, they are not especially noteworthy nor interesting from an
OOP perspective and were therefore not included.

Chapter 3 The Roopl Language

47 of 111

provides a constructor and a variety of accessors to both the data and the next node.
The Node class also implements a method length for recursively computing the length of
the list. The method insert is used to insert a single node into the list at a given index, or
alternatively, extracting a node from the list when uncalled.
1
2

class Iterator //Iterator interface
int result

3
4
5
6

//Abstract method
method run(Node head, Node next)
skip

7
8
9
10

//Accessor
method get(int out)
out <=> result

11
12
13
14
15

class ListBuilder
int n //The length of the list to build
Iterator it //The iterator instance to run
Node empty //Helper node

16
17
18
19
20

//Constructor method
method constructor(int len, Iterator i)
n += len
it <=> i

21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

method build(Node head)
if n = 0 then
if head != nil
//List is done, run the iterator
call it::run(head, empty)
fi head != nil
else
//Not yet done, construct next node
construct Node next(n, head)
n -= 1
call build(next)
n += 1
destruct next(n, head)
fi n = 0

Figure 3.24b: Example of recursively defined linked lists in ROOPL (cont.)

The ListBuilder class defined in Figure 3.24b is used to recursively construct lists of arbitrary
length from back to front. As a Node is constructed, it is passed its own (1-based) index in the
list and a reference to the next node in the list. When the list has been built, an iterator is
invoked on the head of the list (working front-to-back). When the iterator finally returns, the
list is deconstructed.
The class Sum in Figure 3.24c on page 49, is an example of a class that implements the
Iterator interface. It iterates over the nodes in a list, summing up the value of their contents.
The class Program illustrates how to use ListBuilder and Sum to build a linked-list and iterate
over it. By using the Iterator interface we make the list builder more generic - it doesn’t care
what kind of operation we want to perform on the list, it only cares that the iterator object it is
given conforms to the interface that it knows about.
The list is created by recursively entering a construct/destruct block. When the desired
length is reached, the recursion halts, the iterator is invoked and then the list is deconstructed
simply by unwinding the call stack, one call (and one corresponding list node) at a time.
Chapter 3 The Roopl Language

48 of 111

1
2

class Sum inherits Iterator
int sum

3

method run(Node head, Node next)
call head::add(sum)
call head::swapNext(next)
if next = nil then
result += sum //Finished
else
call run(next, head) //More work to do
fi next = nil
uncall head::swapNext(next) //Return list to original state
uncall head::add(sum)

4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Program
int result //Final result
Node empty //Helper node

18
19
20
21
22
23
24
25
26
27

method main()
local int n = 5 //List length
construct Sum it //Construct iterator
construct ListBuilder lb(n, it) //Construct list builder
call lb::build(empty) //Build & iterate
destruct lb(n, it)
call it::get(result) //Fetch result
destruct it
delocal n = 5

Figure 3.24c: Example of recursively defined linked lists in ROOPL (cont.)

This style of programming is similar to continuation-passing style (CPS) - the iterator acts as
a continuation that the builder can pass the list on to after it has been constructed. There is no
way for the builder to return the list back to the initial caller, as that would involve unwinding
the call stack and thus deconstructing the list in the process. The main difference between this
approach and CPS is that CPS is usually accomplished by passing the continuation directly as
a function, but since ROOPL does not support higher-order functions we are limited to using
objects.

3.12

Computational Strength

A programming language is said to be computationally universal or Turing complete if it is
capable of simulating any single-taped Turing Machine, which in turn means it is capable of
computing any of the computable functions. Reversible programming languages like Janus
and ROOPL are not Turing complete since they are only capable of computing exactly those
computable functions that are also injective.
Yokoyama et al. suggests simulation of the reversible Turing machines as the computational
benchmark for reversible programming languages [46]. A reversible Turing machine (RTM) is any
Turing machine computing an injective function [6, 47]. If a reversible programming language
is able to cleanly simulate any RTM, then we say that it is reversibly universal or r-Turing
complete.
The original versions of Janus [30, 49] were not r-Turing complete since they only supported
static fixed-size storage. The latest version of the language adds support for dynamic storage and
was proven to be r-Turing complete by construction of an RTM interpreter [46]. In the following

Chapter 3 The Roopl Language

49 of 111

sections, we present techniques for constructing a similar RTM interpreter using ROOPL. The
intepreter serves as a proof that ROOPL is also reversibly universal.

3.12.1

RTM Representation

We use the same Turing machine formalism as used in [46], with state transitions represented by
quadruples:
Definition 3.1. (Quadruple Turing Machine)
A TM T is a tuple (Q, Γ, b, δ, qs , qf ) where
Q is the finite, non-empty set of states
Γ is the finite, non-empty set of tape alphabet symbols
b ∈ Γ is the blank symbol
δ : (Q × Γ × Γ × Q) ∪ (Q × {/} × {L, R} × Q) is the partial function representing
the transitions
qs ∈ Q is the starting state
qf ∈ Q is the final state
The symbols L and R represent the tape head shift-directions left and right. A quadruple is either
a symbol rule of the form (q1 , s1 , s2 , q2 ) or a shift rule of the form (q1 , /, d, q2 ) where q1 ∈ Q,
q2 ∈ Q, s1 ∈ Γ, s2 ∈ Γ and d being either L or R.
A symbol rule (q1 , s1 , s2 , q2 ) means that in state q1 , when reading s1 from the tape, write
s2 to the tape and change to state q2 . A shift rule (q1 , /, d, q2 ) means that in state q1 , move
the tape head in direction d and change to state q2 .
Definition 3.2. (Reversible Turing Machine)
A TM T is a reversible TM iff, for any distinct pair of quadruples (q1 , s1 , s2 , q2 ) ∈ δT and
(q10 , s01 , s02 , q20 ) ∈ δT , we have
q1 = q10 =⇒ (t1 6= /

∧

t01 6= /

∧

t1 6= t01 ) (forward determinism)

q2 = q20 =⇒ (t1 6= /

∧

t01 6= /

∧

t2 6= t02 ) (backward determinism)

In ROOPL we can represent the set of states {q1 , . . . , qn } and the tape alphabet Γ as integers.
The shift rule symbol / and the direction symbols L and R are then represented by the integer
variables SLASH, LEFT and RIGHT respectively.
With this representation, we can model a transition rule as an object containing four integers
q1, s1, s2 and q2 where s1 equals SLASH for shift rules. A linked list of such transition rules
serves as the full transition table δ. Using the techniques described in Section 3.11.5 we can look
up the appropriate transition rule at each step of the simulation, with an index variable that
rolls around to 0 whenever it exceeds the length of the transition table.
Since states are numbers in our simulation, we can use a single integer variable which is
updated as the simulation runs, to keep track of the current state of the RTM. After each iteration
of the RTM simulation - the current state is compared to the final state Qf, if they are the same
the simulation stops.
Chapter 3 The Roopl Language

50 of 111

3.12.2

Tape Representation

The tape of an RTM has to be able to grow unboundedly in both directions12 . With the tape
alphabet being represented by integers, we can use a simple object containing just an integer to
model a tape cell. The full tape is represented by a linked list of such cells.
The position of the tape head of the RTM determines which tape cell is currently being
inspected or modified. In our simulation we can use an integer variable to store the position of
the tape head as an index into the list of tape cells. Initially, the tape should contain just the
input and the tape head should be at index 0. After each simulated step of the RTM we:
1. Calculate the current length of the tape.
2. If the position of the tape head is less than zero: The tape head has moved off the left end
of the tape. We allocate a new cell, prepend it to the list and zero-clear the tape head
position.
3. If the position of the tape head exceeds the current length of the tape: The tape head has
moved off the right end of the tape. We allocate a new cell and append it to the tape list.
Our model of the tape can now also grow unboundedly in both directions.

3.12.3

RTM Simulation

Figure 3.25 shows the method inst which executes a single instruction given a reference to the
head of the tape, the position of the tape head, the current state of the RTM and four integers
representing the transition rule to be executed.
1
2
3

method inst(Cell tape, int pos, int state, int q1, int s1, int s2, int q2)
local int symbol = 0
call tape::lookup(pos, symbol) //Fetch current symbol

4
5
6
7
8
9

if state = q1 && s1 = symbol then //SYMBOL RULE
state += q2 - q1 //Update state to q2
symbol += s2 - s1 //Update symbol to s2
call tape::add(pos, s2 - s1) //Update tape cell to s2
fi state = q2 && s2 = symbol

10
11
12

uncall tape::lookup(pos, symbol) //Zero-clear symbol
delocal symbol = 0

13
14
15

if state = q1 && s1 = SLASH then //SHIFT RULE
state += q2 - q1 //Update state to q2

16
17
18
19

if s2 = RIGHT then
pos += 1 //Move tape head right
fi s2 = RIGHT

20
21
22
23
24

if s2 = LEFT then
pos -= 1 //Move tape head left
fi s2 = LEFT
fi state = q2 && s1 = SLASH

Figure 3.25: Method for executing a single TM transition
12

The term linear bounded automaton is used to denote TM-like automatons with an upper bound on the size of
the tape.

Chapter 3 The Roopl Language

51 of 111

Figure 3.26 shows the recursively defined simulate method which is the main method responsible for running the RTM simulation. It extends the tape in either direction when necessary,
fetches the transition quadruple, updates the program counter and copies the result when the
RTM halts.
1
2
3

method simulate(Cell tape, int pos, int state, int pc)
local int len = 0
call tape::length(len) //Calculate length of tape

4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

if pos > len then //Append new tape cell
construct Cell new(BLANK, empty)
call tape::insert(pos, len)
call simulate(tape, pos, state, pc) //Continue simulation
uncall tape::insert(pos, len)
destruct new(BLANK, empty)
else
if pos < 0 then //Prepend new tape cell
construct Cell new(BLANK, tape)
tape <=> new
pos += 1
call simulate(tape, pos, state, pc) //Continue simulation
pos -= 1
tape <=> new
destruct new(BLANK, tape)
else
local int q1 = 0, s1 = 0, s2 = 0, q2 = 0
call incPc(pc, PC_MAX) //Increment pc
call RTM::get(pc, q1, s1, s2, q2) //Fetch transition quadruple

24
25

call inst(tape, pos, state, q1, s1, s2, q2)

26
27
28
29
30
31

if state
call
else
call
fi state

= Qf then //If RTM simulation is finished
tape::get(result) //Copy result of simulation
simulate(tape, pos, state, pc) //Continue simulation
= Qf

32
33

uncall inst(tape, pos, state, q1, s1, s2, q2)

34
35
36
37
38
39

uncall RTM::get(pc, q1, s1, s2, q2) //Clear transition quadruple
uncall incPc(pc, PC_MAX) //Decrement pc
delocal q1 = 0, s1 = 0, s2 = 0, q2 = 0
fi pos < 0
fi pos > len

40
41
42

uncall tape::length(len) //Clear length of tape
delocal len = 0

Figure 3.26: Main RTM simulation method

Unlike the RTM simulator created with Janus, which uses a pair of stack primitives to
represent the RTM tape, the ROOPL RTM simulator cannot finish with the TM tape as the
program output. Whenever a tape cell is created, the simulator invokes the next operation
recursively - but when the TM halts, the call stack of the simulation must unwind before the main
method and the program can finally terminate, which results in the tape cells being deallocated
one by one. The program must even ensure that the tape cells are zero-cleared before they are
deallocated which can only be done reversibly by uncomputing the simulation. When the TM
halts, the entire simulation therefore runs again in reverse to return the tape cells to their original
state as the simulator proceeds down the call stack.
Chapter 3 The Roopl Language

52 of 111

CHAPTER

4

Compilation
This chapter presents the code generation schemes used to translate ROOPL source code to
PISA Assembly Language (PAL). The translated programs are semantically equivalent to the
source programs and generate no additional garbage data. Due to the syntactic and semantic
similarities between Janus and ROOPL, some of the techniques presented here are similar to
those presented in [2] which describes the translation from Janus to PAL.

4.1

Preliminaries

See Section 2.4 in Chapter 2 for a brief description of the PISA instruction set that we target in
this chapter. A more in-depth presentation of PISA and the Pendulum architecture can be found
in [42]. For presentation purposes, we will make use of the three pseudoinstructions defined in
Figure 4.1.

i

def
=

ADDI r

−i

PUSH r

def
=

h
EXCH r

rsp ,

POP r

def
=

h
SUBI rsp

SUBI r

1,

ADDI rsp
EXCH r

1

i

rsp

i

Figure 4.1: Definition of pseudoinstructions SUBI, PUSH and POP

Our translation uses virtual function tables and object layout prefixing to implement subtype
polymorphism. Every class method of the source program is translated to a series of PISA
instructions. The translated methods accept an extra hidden parameter for the object pointer,
which points to the object that the method is associated with and is used to access the instance
variables of that object.

4.2

Memory Layout

We use a series of labelled load-time DATA instructions at the beginning of each translated
program to initialize a portion of memory with virtual function tables and other static data that
the translated program needs. We refer to this portion of program memory as static storage
because it is statically sized and initialized.
Chapter 4 Compilation

53 of 111

(unused memory)
Program

Static Data

Stack

p

0

stack grows

sp

231 − 1

←− Address Space −→
Figure 4.2: Memory layout of a ROOPL program

Figure 4.2 shows the full layout of a ROOPL program in memory:
1. The static storage segment begins at address 0 and contains static data initialised with
DATA instructions.
2. The program segment is placed just after the static storage segment and contains the actual
program instructions which consists mainly of translated class methods.
3. The program stack is placed after the program segment at address p. The stack is a LIFO
structure which grows and shrinks as the program executes.
The program stack is used to store activation records, objects and local variables. The stack
is accessed with the stack pointer sp and initially sp = p.

4.3

Dynamic Dispatch

Dynamic dispatch is a mechanism for selecting which implementation of a method to invoke,
based on the type of the associated object at run time.
class Shape
int x
int y

l_Shape_vt :

DATA 90

; Shape::getArea

DATA 106 ; Shape::resize
DATA 124 ; Shape::translate

method
method
method
method

getArea(int out)
resize(int scale)
translate(int x, int y)
draw()

DATA 140 ; Shape::draw
l_Rectangle_vt : DATA 74

; Rectangle::getArea

DATA 106 ; Shape::resize
DATA 124 ; Shape::translate

class Rectangle inherits Shape
int a
int b

DATA 140 ; Shape::draw
l_Circle_vt :

DATA 26

; Circle::getArea

DATA 106 ; Shape::resize
method getArea(int out)
class Circle inherits Shape
int radius

DATA 124 ; Shape::translate
DATA 140 ; Shape::draw
DATA 42

; Circle::getRadius

method getArea(int out)
method getRadius(int out)

Figure 4.3: Virtual function table layout for a simple class hierarchy with overridden methods

Chapter 4 Compilation

54 of 111

Since ROOPL allows an object of type τ to be passed to a method expecting an object of
type τ 0 if τ ≺: τ 0 , any method calls invoked on the object must be dispatched to the correct
implementation in case τ overrides a method in τ 0 . This can only be done at run time since it is
impossible to determine the actual type of an object at compile time.
There are several ways to implement dynamic dispatch but the most common implementation
uses virtual function tables (vtables) to determine which implementation to dispatch to. Every
class in a translated ROOPL program has a vtable which is used to map method names to the
memory addresses of the method implementation for that class. Figure 4.3 shows how vtables in
ROOPL are arranged for a simple class hierarchy:
– The Shape class has no base class and therefore the vtable entries all point to the original
(non-overriden) method implementations.
– The Rectangle class inherits from Shape and overrides the getArea method but does
not override any other methods. Correspondingly, the vtable points to the overriding
implementation of getArea but points to the original implementations for the other methods
resize, translate and draw.
– The Circle class is similar to Rectangle but also adds a method getRadius which is added
to the vtable after the entries for the methods inherited from Shape.
When a method is invoked on an object, the vtable is inspected at some statically determined
offset. In our example, offset 0 is used for invocations of method getArea, offset 1 is used for
method resize, offset 2 for translate and offset 3 for draw.
Placing the vtable entry for getRadius after the entries for the inherited methods ensures
that the inherited methods are placed at the same offsets in the vtable for all subclasses of Shape.
Therefore if a method is invoked on an object of type Shape, the same offset is used to look
up the address in the vtable regardless of the actual, dynamic type of the callee object. This
technique is known as prefixing and it greatly simplifies the translation of polymorphic behaviour.
We also utilize prefixing in the memory layout of ROOPL objects for similar benefits.

4.4

Object Layout

Each ROOPL object consists of a pointer to the class vtable followed by a number of memory
cells corresponding to the number of instance variables.
Shape

addr(vtable)
x
y
radius

+0
+1
+2
+3
+4

addr(vtable)
x
y
a
b

rrect

+0
+1
+2
+3

rcirc

addr(vtable)
x
y

rshape

+0
+1
+2

Rectangle

Circle

Figure 4.4: Illustration of prefixing in the memory layout of 3 ROOPL objects

Chapter 4 Compilation

55 of 111

Figure 4.4 illustrates the layout of 3 objects based on the class hierarchy from Figure 4.3.
When a statement or expression refers to an instance variable, the variable offset is added to the
hidden object pointer which is then dereferenced (using EXCH) to fetch the value of the instance
variable. Again we utilize prefixing to ensure the variable offsets are identical across subclasses
of the same type.
Because the class vtable pointer is always stored at offset 0, a vtable lookup is accomplished
simply by dereferencing the pointer to the callee object, adding the method offset and then dereferencing the resulting address which yields the memory address of the method implementation.

4.5

Program Structure

The overall structure of a translated ROOPL program is illustrated in Figure 4.5. After the
static storage segment follows a series of translated class methods in turn followed by a section
of code which acts as the starting point of the program.
(1)

······

; Static data declarations

(2)

······

; Code for program class methods

START

; Program starting point

(3)

start :

(4)

ADDI

rsp

p

; Initialize stack pointer

(5)

XOR

rm

rsp

; Store address of main object in rm

(6)

XORI

rv

labelvt

; Store address of vtable in rv

(7)

EXCH

rv

rsp

; Push address of vtable onto stack

(8)

ADDI

rsp

sizem

; Allocate space for main object

(9)

PUSH

rm

; Push ’this’ onto stack

(10)

BRA

labelm

; Call main procedure

(11)

POP

rm

; Pop ’this’ from stack

(12)

SUBI

rsp

sizem

; Deallocate space of main object

(13)

EXCH

rv

rsp

; Pop vtable address into rv

(14)

XORI

rv

labelvt

; Clear rv

(15)

XOR

rm

rsp

; Clear rm

(16)

SUBI

rsp

p

; Clear stack pointer

(17) f inish : FINISH

; Program exit point

Figure 4.5: Overall layout of a translated ROOPL program

This section is responsible for initializing the stack pointer, allocating an instance of the
object containing the main method, calling the main method, deallocating the main object and
finally clearing the stack pointer:
The stack pointer is initialized simply by adding the base address of the stack to whichever
register rsp should contain the stack pointer. The base address of the stack varies with the size
of the translated program but is always known at compile-time - in Figure 4.5 the base address
of the stack is simply denoted p. After the stack is in place, we allocate an instance of the main
object on the stack by pushing the address of the vtable (denoted labelvt ) onto the stack and
adding the size of the object to the stack pointer (denoted sizem ). We then push the address
of this object onto the stack and unconditionally branch to the main method at labelm . The
address of the main object is popped off the stack by the callee and serves as the object pointer.

Chapter 4 Compilation

56 of 111

After the main method returns, we pop the address of the main object from the stack,
deallocate the object and clear the stack pointer. This is done by inverting the steps taken to
initialize the stack and the object. After the program terminates, the values of the main object
member variables will be left in memory where the stack used to be. This is clearly not an ideal
location for the program output to reside, we address this concern in Section 4.14.

4.6

Class Methods

The calling convention described in [2] is a generalized version of the PISA calling convention
presented in [17], modified to support recursion. The ROOPL translation uses a similar approach
with added support for method parameters (including the hidden object pointer) with pass-byreference semantics.
BRA

mbot

(2)

qtop :

POP

rro

; Load return offset

(3)

PUSH

rx2

; Restore argument x2

(4)

PUSH

rx1

; Restore argument x1

PUSH

rthis

; Restor this-pointer

(1)

(5)
(6)

labelq : SWAPBR rro

(7)

NEG

rro

; Negate return offset

(8)

POP

rthis

; Load this-pointer

(9)

POP

rx1

; Load argument x1

(10)

POP

rx2

; Load argument x2

(11)

PUSH

rro

; Store return offset

(12)

······

(13) qbot :

BRA

; Method entry and exit point

; Code for method body qbody
mtop

Figure 4.6: PISA translation of a ROOPL method

Figure 4.6 shows the PISA translation of a ROOPL method taking two parameters x1 and
x2 , with method body qbody . The caller transfers control to instruction (6) after which the
object-pointer and method arguments are popped off the stack, the return offset is stored and
the body is executed. The method prologue works identically for both directions of execution
and it works with local method calls (which are simple static branch instructions) and with
method calls invoked on other objects (which are dynamically dispatched). This avoids the need
for multiple translations of the same method to support reverse execution, which would greatly
increase the size of the translated programs.
The SWAPBR instruction is used here to facilitate incoming jumps from more than one location,
which would otherwise be impossible to achieve with PISA’s paired-branch instructions. The
return offset is swapped into register rro , negated (since the return offset is simply the negation
of the incoming jump offset) and is then stored on the stack. When the method body finishes,
the return offset is swapped back into the branch register, thereby returning the flow of execution
to the caller. The arguments and offsets that are accumulated on the program stack during a
(possibly nested or recursive) method invocation are cleared as the stack unwinds and the method
returns. When the main method call eventually returns, just before the program terminates, the
stack will have been returned to its initial, empty state.
Chapter 4 Compilation

57 of 111

4.7

Method Invocations

In ROOPL, method invocations on the current object are always statically dispatched. This
behaviour is known as closed recursion. The effect of this is that local method invocations in a
base class, will always dispatch to the method within that class, even if it has been overridden in
a derived class. Using dynamic dispatch semantics for local method invocations (open recursion)
leads to increased program size, increased execution time and it makes program behaviour harder
to reason about13 .
Figure 4.7 shows the translation of local method invocations. The arguments are pushed on
the stack in reverse order, followed by the object pointer. The jump itself is performed with an
unconditional branch instruction to a statically determined label. After the method returns, the
object pointer and the arguments are popped off the stack.

call q(x1 , x2 )

uncall q(x1 , x2 )

(1) PUSH rx2

; Push x2 onto stack

(1) PUSH rx2

; Push x2 onto stack

(2) PUSH rx1

; Push x1 onto stack

(2) PUSH rx1

; Push x1 onto stack

(3) PUSH rt

; Push ’this’ onto stack

(3) PUSH rt

; Push ’this’ onto stack
; Reverse jump to method

(4) BRA

labelq

; Jump to method

(4) RBRA labelq

(5) POP

rt

; Pop ’this’ from stack

(5) POP

rt

; Pop ’this’ from stack

(6) POP

rx1

; Pop x1 from stack

(6) POP

rx1

; Pop x1 from stack

(7) POP

rx2

; Pop x2 from stack

(7) POP

rx2

; Pop x2 from stack

Figure 4.7: PISA translation of local method invocations

Uncalling a method is accomplished with the reverse branch instruction which flips the
direction of execution after jumping to the method. Note that since we are using pass-byreference semantics, we are in fact passing memory addresses as arguments to the method,
which in turn points to the locations of the values of x1 and x2 . The callee is responsible for
dereferencing the arguments when they are used in the method body, using the EXCH instruction.
Translation of non-local method calls always uses dynamic dispatch, which is slightly more
involved than just jumping to a statically determined instruction label. The steps for dynamically
dispatching to a method associated with a different object are:
1. Look up the address of the method in the object vtable and create a local copy
2. Calculate the relative jump offset from the method invocation to the method prologue
3. Push the arguments on the stack along with the new object pointer
4. Perform the jump
5. Pop the arguments from the stack
6. Undo the jump offset calculation, to reobtain the absolute address of the method
7. Look up the address of the method in the class vtable again, to clear the local copy
13

Open recursion also breaks encapsulation and has been identified as the root cause of the fragile base class
problem [1]

Chapter 4 Compilation

58 of 111

Figure 4.8 shows the translation of a dynamic method call. The first step is to dereference
the callee-object to obtain the address of the class vtable. We then look up the address of the
method by adding the vtable offset (offset q ) to the vtable address.
Note how this lookup involves swapping the address stored in the vtable in static memory
with the value of a register. This means the vtable is in fact altered and we need to return it to
its original state before we perform the jump, since the callee might need to lookup the same
method address later on. We can restore the vtable with a Lecerf-reversal by creating a copy of
the method address in a register, and then undoing the lookup thereby swapping the original
method address back into the vtable.
call x::q(x1 , x2 )
(1)

EXCH

rv

rx

; Get address of vtable

(2)

ADDI

rv

offset q

; Lookup q in vtable

(3)

EXCH

rt

rv

; Get address of q

(4)

XOR

rtgt

rt

; Copy address of q

(5)

EXCH

rt

rv

; Place address back in vtable

(6)

SUBI

rv

offset q

; Restore vtable pointer

(7)

EXCH

rv

rx

; Restore object pointer

(8)

PUSH

rx2

; Push x2 onto stack

(9)

PUSH

rx1

; Push x1 onto stack

(10)

PUSH

rx

(11)

SUBI

rtgt

; Push new ’this’ onto stack
labeljmp

(12) labeljmp : SWAPBR rtgt

; Calculate jump offset
; Jump to method

(13)

NEG

rtgt

(14)

ADDI

rtgt

; Restore rtgt to original value

(15)

POP

rx

; Pop new ’this’ from stack

(16)

POP

rx1

; Pop x1 from stack

(17)

POP

rx2

(18)

EXCH

rv

rx

; Get address of vtable

(19)

ADDI

rv

offset q

; Lookup q in vtable

(20)

EXCH

rt

rv

; Get address of q

(21)

XOR

rtgt

rt

; Clear address of q

(22)

EXCH

rt

rv

; Place address back in vtable

(23)

SUBI

rv

offset q

; Restore vtable pointer

(24)

EXCH

rv

rx

; Restore object pointer

labeljmp

; Restore absolute jump value

; Pop x2 from stack

Figure 4.8: PISA translation of a non-local method invocation

Since the usual branch instructions (BRA, RBRA, et cetera) can only jump to static instruction
labels, we must use the SWAPBR instruction to swap the jump offset into the branch register.
Because the vtable only stores absolute method addresses, we have to calculate the jump offset
manually for each method call. We can accomplish this by subtracting the memory address of
the SWAPBR instruction from the method address.
After the method returns, we negate the jump offset (to cancel out the negation done by the

Chapter 4 Compilation

59 of 111

callee in the method prologue) and add the address of the SWAPBR instruction to the jump offset
to obtain the original absolute value of the method. To avoid leaving this method address in a
register or on the stack as garbage data, we repeat the vtable lookup to clear the local method
address copy. In total, the vtable is consulted 4 times per method invocation.
uncall x::q(x1 , x2 )
(11)

SUBI

rtgt

(12) topjmp

RBRA

botjmp

labeljmp

; Flip direction

(13) labeljmp : SWAPBR rtgt
(14)

NEG

rtgt

(15) botjmp

BRA

topjmp

(16)

ADDI

rtgt

; Calculate jump offset
; Jump to method
; Restore rtgt to original value
; Paired branch

labeljmp

; Restore absolute jump value

Figure 4.9: PISA translation of a non-local reverse method invocation

Uncalling a non-local method is analogous to calling a non-local method, with the added
caveat that the direction of execution should be reversed before the jump occurs. Unlike BobISA
(which has the RSWB instruction, see Section 2.5 in Chapter 2), PISA does not have a single
instruction which swaps the branch register and flips the direction bit simultaneously. Figure 4.9
shows how this is instead accomplished with an RBRA/BRA pair. The vtable lookup and cleanup
is identical to the approach used in Figure 4.8.

4.8

Object Blocks

Since the stack is maintained over (but not during) execution of a statement, we can store
ROOPL objects on the program stack. The execution of an object block begins with allocation
of a new object on the top of the stack. Then the block statement is executed, after which the
object will again be on the top of the stack, ready for deallocation.
construct c x s destruct x
rsp

; Store address of new object x in rx

(2) XORI rv

labelvt

; Store address of vtable in rv

(3) EXCH rv

rsp

; Push address of vtable onto stack

(4) ADDI rsp

sizec

; Allocate space for new object

(1) XOR

(5)

rx

······

; Code for statement s

(6) SUBI rsp

sizec

; Deallocate space occupied by zero-cleared object

(7) EXCH rv

rsp

; Pop vtable address into rv

(8) XORI rv

labelvt

; Clear rv

rsp

; Clear rx

(9) XOR

rx

Figure 4.10: PISA translation of an object block

Figure 4.10 illustrates how this is accomplished in practice. The immediate labelvt is the
address of the vtable for class c and sizec is the size of the class. The size of a class is the number
Chapter 4 Compilation

60 of 111

of instance variables plus 1, for accomodating the vtable pointer. Within the block statement s,
the register rx contains the address of the new object x.

4.9

Local Blocks

Figure 4.11 shows the translation of a local integer block. Local blocks are not part of the core
language (See Section 3.10.1 in Chapter 3), but are included as a language extension, borrowed
from Janus.
local int x = e1

s delocal x = e2

(1)

······

(2)

XOR

rx

rsp

(3)

XOR

rt

re

(4)

PUSH rt

; Push value of e1 onto stack

(5)

······

; Inverse of (1)

(6)

······

; Code for statement s

(7)

······

(8)

POP

rt

(9)

XOR

rt

re

; Clear value of rt with re

(10) XOR

rx

rsp

; Clear reference to x

(11)

······

; Code for re ← Je1 K

; Store address of new integer x in rx
; Copy value of e1 into rt

; Code for re ← Je2 K

; Pop value of x into rt

; Inverse of (7)

Figure 4.11: PISA translation of a local block

Again, the translation can take advantage of the fact that the program stack is preserved over
statement execution. This means we can place the local integers on the stack and pop them off
after the block statement has been executed. Local integers are initialized with some expression
e1 and zero-cleared with another expression e2 . Evaluation of an irreversible expression in a
reversible assembly language is bound to generate some amount of garbage data so we use a
Lecerf-reversal to uncompute this garbage data after initializing the local variable with e1 , and
again after clearing the local variable with e2 .

4.10

Control Flow

At the level of assembly language, control flow statements are usually realized via direct alteration
of the program counter, which is clearly not an option for a translation targeting a reversible
instruction set such as PISA. Another complication arises in the evaluation of the expressions
acting as entry and exit conditions, since ROOPL expressions are irreversible.
Axelsen suggests a simple approach for arranging the translation of Janus CFOs in such
a way that the garbage data produced by evaluation of the entry and exit expressions can be
uncomputed without significant code duplication [2]. Since Janus (and ROOPL) uses the value 0
for the boolean value false and non-zero for the boolean value true, we can safely reduce the
result of evaluating the entry and exit expressions to either 0 or 1 while still preserving the
semantics of the source program.

Chapter 4 Compilation

61 of 111

if e1 then s1 else s2 fi e2
(1)

······

(2)

XOR

(4)

; Code for re ← Je1 Kc

rt re

; Copy value of e1 into rt

······

(3)
test :

rt r0 testf alse

BEQ

from e1 do s1 loop s2 until e2
XORI rt 1

(1)
(2)

entry :

; Set rt = 1

rt r0 assert ; Receive jump

BEQ

; Inverse of (1)

(3)

······

; Jump if e1 = 0

(4)

XOR

; Code for re ← Je1 Kc

rt re

; Clear rt

(5)

XORI rt 1

; Clear rt

(5)

······

; Inverse of (3)

(6)

······

; Code for statement s1

(6)

······

; Code for statement s1

(7)

XORI rt 1

; Set rt = 1

(7)

······

(8)

asserttrue : BRA

assert

; Jump

(8)

XOR

(9)

testf alse :

test

; Receive jump

(9)

······

; Code for statement s2

(10) test :

BNE

; Receive jump

(11)

······

; Code for re ← Je2 Kc

(12) assert : BRA

BRA

(10)

······

(11) assert :

BNE

(12)

······

(13)

XOR

(14)

······

rt r0 asserttrue
rt re

; Clear rt

; Code for re ← Je2 Kc

rt re

; Copy value of e2 into rt
; Inverse of (7)

rt r0 exit

; Code for statement s2
entry

; Jump to top

XORI rt 1

(13)

; Exit if e2 = 1

; Clear rt

; Inverse of (12)

Figure 4.12: PISA translation of conditonals (left) and loops (right), from [2]

This allows us to perform the uncomputation of the expression evaluation (which clears
extraneous garbage data) before the branch is executed, while still being able to subsequently clear
the register holding the result of the evaluation. Conditional statements and loops in ROOPL
are essentially identical to those in Janus and this approach is therefore perfectly suitable for our
ROOPL to PISA translation. Figure 4.12 shows the translation of both conditional statements
and loops.

4.11

Reversible Updates

Figure 4.13 shows the translation of reversible variable updates and variable swapping. Since
PISA does not have a built-in register swap instruction, we use the classic XOR-swap to exchange
the contents of the two registers reversibly.
x1 <=> x2

x
······

(1) XOR rx1

rx2

(1)

(2) XOR rx2

rx1

(3) XOR rx1

rx2

(2) J Ki
(3)

rx

re

······

=e
; Code for re ← JeK
; Assign e to x

; Inverse of (1)

Figure 4.13: PISA translation of variable updates and variable swapping

Variable updates are accomplished with one of three instructions as well as an expression
evaluation which is reversed after the update, in order to clear any accumulated garbage data.
The update instruction in (2) is given by the function J Ki : ModOps → Instructions:
J+Ki = ADD

J-Ki = SUB

JˆKi = XOR

See Section 3.1 in Chapter 3 and Section 2.4 in Chapter 2 for the ROOPL and PISA syntax
domains.

Chapter 4 Compilation

62 of 111

4.12

Expression Evaluation

When implementing evaluation of irreversible expressions in a reversible language, we have to
accept the generation of some garbage data. Since ROOPL expressions are irreversible, every
evaluation of an expression must be accompanied by a subsequent unevaluation in order to clear
any accumulated garbage data in registers and memory. This technique keeps the translation
clean at the statement-level.
Code generation for evaluation of expressions is done by recursive descent over the structure
of the expression tree. Numerical constants, variables and nil-nodes represent the base cases
while binary expressions represent the recursive cases. A few of the binary operators supported in
ROOPL (such as addition and bitwise exclusive-or) have single-instruction equivalents in PISA,
but most operators are translated to more than one PISA instruction.
We consider the issue of register allocation for expression evaluation to be outside the scope
of our translation. See [2, Section 4.5] for an examination of reversible register allocation in
PISA. A novel approach for reducing register pressure, by leveraging reversible computations to
recompute registers instead of spilling them to memory, is presented in [5].

4.13

Error Handling

Aside from being syntactically correct and well-typed, a ROOPL program is required to meet a
number of conditions that cannot, in general, be determined at compile time:
– If the entry expression of a conditional is true, then the exit assertion should also be true
after executing the then-branch.
– If the entry expression of a conditional is false, then the exit assertion should also be false
after executing the else-branch.
– The entry expression of a loop should initially be true.
– If the exit assertion of a loop is false, then the entry expression should also be false after
executing the loop-statement.
– All instance variables should be zero-cleared within an object block, before the object is
deallocated.
– The value of a local variable should always match the value of the delocal-expression
after the block statement has executed.
It is entirely up to the programmer to make sure these conditions are met by the program. If
either of these conditions are not met, the program will silently continue with erroneous execution.
To avoid such a situation, we can insert run time error checks that terminates the program or
jumps to some error handler in case of programmer error.
Figure 4.14 shows the translation of a local integer block with added dynamic error checks.
In case the value of the local integer vi does not match the value of the delocal-expression ve ,
the register rt will contain the non-zero value vi ⊕ ve at instruction (13). If this is the case, we
jump to an error routine at labelerror .
The error check at (1) serves the same purpose as its counterpart, when the flow of execution
is reversed, but has no effect otherwise since rt is empty before the statement is executed.
Chapter 4 Compilation

63 of 111

local int x = e1
rt

r0

labelerror

s delocal x = e2

(1)

BNE

(2)

······

(3)

XOR

rx

rsp

(4)

XOR

rt

re

(5)

PUSH rt

; Push value of e1 onto stack

(6)

······

; Inverse of (1)

(7)

······

; Code for statement s

(8)

······

(9)

POP

rt

(10) XOR

rt

re

; Clear value of rt with re

(11) XOR

rx

rsp

; Clear reference to x

rt

r0

(12)

; Code for re ← Je1 K

; Store address of new integer x in rx
; Copy value of e1 into rt

; Code for re ← Je2 K

; Pop value of x into rt

······

(13) BNE

; Dynamic error check

; Inverse of (7)
labelerror

; Dynamic error check

Figure 4.14: PISA translation of a local block, with run time error checking

Dynamic error checks for conditionals, loops and object blocks can be implemented using a
similar technique.

4.14

Implementation

We implemented a ROOPL compiler (ROOPLC), utilizing the techniques presented in the preceding sections. The compiler serves as a proof-of-concept and does not perform any optimization
of the target programs whatsoever. ROOPLC is written in Haskell (GHC, version 7.10.3) and
the output was tested using the PendVM Pendulum simulator [16].
Appendix A contains the source code listings for the ROOPL compiler and Appendix B
contains an example ROOPL program and the corresponding translated PISA program. The
source code for the ROOPL compiler, additional test programs and the C source code for the
PendVM simulator are also included in the enclosed ZIP archive.
The ROOPL compiler follows the PISA conventions that register r0 is preserved as 0, r1
contains the stack pointer and r2 stores return offsets for method invocations. Additionally,
the compiler will always use r3 to store the object pointer. The remaining 28 general purpose
registers are used for variables, parameters and intermediate expression evaluation results.
In ROOPL, the class fields of the main class act as the program output. The program prelude,
as described in Section 4.5, leaves the value of these variables on the program stack after the
program terminates. For the sake of convenience, the compiler instead copies these values from
the program stack to static memory before termination. The compiler is structured as 6 separate
compilation phases:
1. Parsing The parsing phase transforms the input program from textual representation to an
abstract syntax tree. The parser was implemented using the monadic parser combinators from
the Text.Parsec library. See Section 3.1 for details on the ROOPL syntax.
2. Class Analysis The class analysis phase verifies a number of properties of the classes in
Chapter 4 Compilation

64 of 111

the program: Inheritance cycle detection, duplicate method names, duplicate field names and
unknown base classes. The class analysis phase also computes the size of each class and constructs
tables mapping class names to methods, instance variables et cetera.
3. Scope Analysis The scope analysis phase maps every occurrence of every identifier to
a unique variable or method declaration. The scope analysis phase is also responsible for
constructing the class virtual tables and the symbol table.
4. Type Checking The type checker uses the symbol table and the abstract syntax tree to
verify that the program satisfies the ROOPL type system, as described in Section 3.7.
5. Code Generation The code generation phase translates the abstract syntax tree to a series
of PISA instructions in accordance with the code generation schemes presented in this chapter.
Rudimentary register allocation is also handled during code generation.
6. Macro Expansion The macro expansion phase is responsible for expanding macros left in
the translated PISA program after code generation and for final processing of the output.
The size blowup from ROOPL to PISA is by a factor of 10 to 15 in terms of LOC. The
nature of the target programs suggest that basic peephole optimization could reduce program
size drastically.

Chapter 4 Compilation

65 of 111

CHAPTER

5

Conclusion
We described and formalized the reversible object-oriented programming language ROOPL and
we discussed the considerations that went into its design. The language extends the design of
existing imperative reversible languages in the literature and represents the first effort towards
introducing OOP methodology to the field of reversible computing.
The combination of reversible computing and object-oriented programming is entirely uncharted territory and we identified the most interesting or novel points of intersection between
the two disciplines, such as reversible class mutators and the proposed constructor/deconstructor
extension.
Since ROOPL is the first imperative reversible language with non-trivial user-defined data
types, we presented a complete static type system for the language and proved that well-typedness
is preserved over statement inversion. We also demonstrated the computational strength of the
language by implementing a reversible Turing machine simulator.
Finally, we established the techniques required for a clean translation from ROOPL to the
reversible low-level machine language PISA and we demonstrated the feasibility of supporting core
OOP features such as class inheritance and subtype polymorphism in a reversible programming
language, by means of object layout prefixing and virtual function tables. We created a proof-ofconcept compiler which fully implements our translation techniques.
If reversible computing is to contend with conventional computing models, we need reversibility
at every level of abstraction. To this end, much has been accomplished at the circuit, gate and
machine levels but aside from the work on reversible functional programming, there is little on
offer in terms of high level languages and abstractions. The work presented in this thesis is a step
in the direction of reconciling the abstraction techniques of conventional programming languages
with the reversible programming paradigm. With ROOPL we have demonstrated that reversible
object-oriented programming languages are both possible and practical.

5.1

Future Work

In order to move away from the syntactically coupled allocation and deallocation mechanics
used in ROOPL, more work is needed on the topics of reversible memory heaps and reversible
dynamic memory management. Some work has already been done on these topics with regards
to reversible functional languages [3, 35, 33].
ROOPL offers only the minimal toolset necessary for object-oriented programming. Advanced
OOP features such as mixins, traits and generic classes could also prove to be useful in a reversible
programming language and the implementation of such features could be the subject of further
work.

Chapter 5 Conclusion

66 of 111

Compilation of reversible languages is still in its infancy and the existing body of work focuses
exclusively on correctness and avoiding garbage data. The practicality of reversible languages
depends in part on compilation techniques that are not only correct but also performant, both in
terms of execution time and program size. In particular, optimization techniques that utilize the
bidirecitonal nature of reversible programs to reduce code size shows promise and there is need
for general and well-performing solutions to the reversible register allocation problem.

Chapter 5 Conclusion

67 of 111

References
[1] Aldrich, J. “Selective Open Recursion: Modular Reasoning about Components and Inheritance”. In: FSE 2004 Workshop on Specification and Verification of Component-Based
Systems. 2004.
[2] Axelsen, H. B. “Clean Translation of an Imperative Reversible Programming Language”.
In: Proceedings of the 20th International Conference on Compiler Construction: Part of
the Joint European Conferences on Theory and Practice of Software. Springer-Verlag, 2011,
pp. 144–163.
[3] Axelsen, H. B. and Glück, R. “Reversible Representation and Manipulation of Constructor
Terms in the Heap”. In: Proceedings of the 5th International Conference on Reversible
Computation. Springer-Verlag, 2013, pp. 96–109.
[4] Axelsen, H. B., Glück, R., and Yokoyama, T. “Reversible Machine Code and Its Abstract
Processor Architecture”. In: Computer Science – Theory and Applications: Second International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russia,
September 3-7, 2007. Proceedings. Ed. by Diekert, V., Volkov, M. V., and Voronkov, A.
Springer Berlin Heidelberg, 2007, pp. 56–69.
[5] Bahi, M. and Eisenbeis, C. “Rematerialization-based Register Allocation Through Reverse
Computing”. In: Proceedings of the 8th ACM International Conference on Computing
Frontiers. ACM, 2011, 24:1–24:2.
[6] Bennet, C. H. “Logical Reversibility of Computation”. In: IBM Journal of Research and
Development 17.6 (1973), pp. 525–532.
[7] Bennet, C. H. “Notes on Landauer’s Principle, Reversible Computation, and Maxwell’s
Demon”. In: Studies in History and Philosophy of Modern Physics 34 (2003), pp. 501–510.
[8] Bennet, C. H. “The Thermodynamics of Computation - a Review”. In: International Journal
of Theoretical Physics 21.12 (1982), pp. 905–940.
[9] Bennet, C. H. “Time/Space Trade-offs for Reversible Computation”. In: SIAM Journal on
Computing 18.4 (1989), pp. 766–776.
[10] Birtwistle, G. M. et al. SIMULA BEGIN. Philadelphia, PA: AUERBACH Publishers, 1973.
[11] Blaschek, G. “Type-Safe Object-Oriented Programming with Prototypes - The Concepts of
Omega”. In: Structured Programming 12 (1991), pp. 217–225.
[12] Bocharov, A. and Svore, K. M. “From Reversible Logic Gates to Universal Quantum Bases”.
In: European Association of Theoretical Computer Science. Vol. 110. 2013, pp. 79–85.
[13] Carøe, M. K. “Design of Reversible Computing Systems”. PhD Thesis. University of
Copenhagen, DIKU, 2012.
[14] Carothers, C. D., Perumalla, K. S., and Fujimoto, R. M. “Efficient Optimistic Parallel
Simulations Using Reverse Computation”. In: ACM Transactions on Modeling and Computer
Simulations 9.3 (1999), pp. 224–253.

References

68 of 111

[15] Cezzar, R. “Design of a Processor Architecture Capable of Forward and Reverse Execution”.
In: vol. 2. 1991, pp. 885–890.
[16] Clark, C. R. Improving the Reversible Programming Language R and its Supporting Tools.
Senior Project. 2001. url: http : / / www . cise . ufl . edu / research / revcomp /
users/cclark/pendvm-fall2001/.
[17] Frank, M. P. “Reversibility for Efficient Computing”. PhD Thesis. Massachusetts Institute
of Technology, 1999.
[18] Frank, M. P. “The R Programming Language and Compiler”. MIT Reversible Computing
Project Memo #M8. 1997.
[19] Fredkin, E. and Toffoli, T. “Conservative Logic”. In: International Journal of Theoretical
Physics 21.3 (1982), pp. 219–253.
[20] Gamma, E. et al. Design Patterns: Elements of Reusable Object-oriented Software. Boston,
MA: Addison-Wesley Longman Publishing, 1995.
[21] Glück, R. and Kawabe, M. “A Program Inverter for a Functional Language with Equality and
Constructors”. In: Programming Languages and Systems: First Asian Symposium, APLAS
2003, Beijing, China, November 27-29, 2003. Proceedings. Ed. by Ohori, A. Springer Berlin
Heidelberg, 2003, pp. 246–264.
[22] Glück, R. and Kawabe, M. “Derivation of Deterministic Inverse Programs Based on LR
Parsing”. In: Functional and Logic Programming: 7th International Symposium, FLOPS
2004, Nara, Japan, April 7-9, 2004. Proceedings. Ed. by Kameyama, Y. and Stuckey, P. J.
Springer Berlin Heidelberg, 2004, pp. 291–306.
[23] Glück, R. and Yokoyama, T. “A Linear-Time Self-Interpreter of a Reversible Imperative
Language”. In: vol. 33. 3. Japan Society for Software Science and Technology, 2016, pp. 108–
128.
[24] Hall, J. “A Reversible Instruction Set Architecture and Algorithms”. In: Physics and
Computation, 1994. PhysComp ’94, Proceedings., Workshop on (1994), pp. 128–134.
[25] Hansen, J. S. K. “Translation of a Reversible Functional Programming Language”. Master’s
Thesis. University of Copenhagen, DIKU, 2014.
[26] Hunt, A. and Thomas, D. The Pragmatic Programmer: From Journeyman to Master.
Boston, MA: Addison-Wesley Longman Publishing, 1999.
[27] Jefferson, D. and Sowizral, H. A. “Fast Concurrent Simulation Using the Time Warp
Mechanism: Part I, Local Control”. In: (1982).
[28] Landauer, R. “Irreversibility and Heat Generation in the Computing Process”. In: IBM
Journal of Research and Development 5.3 (1961), pp. 183–191.
[29] Lecerf, Y. “Machines de Turing réversibles. Insolubilité récursive en n ∈ N de l’équation
u = Θn u, où Θ est un "isomorphisme de codes"”. In: Comptes Rendus Hebdomadaires des
Séances de L’académie des Sciences 257 (1963), pp. 2597–2600.
[30]

Lutz, C. “Janus: a time-reversible language”. Letter to R. Landauer. 1986.

[31] McCarthy, J. “The Inversion of Functions Defined by Turing Machines”. In: Automata
Studies, Annals of Mathematical Studies. Ed. by Shannon, C. E. and McCarthy, J. 34.
Princeton University Press, 1956, pp. 177–181.
References

69 of 111

[32] Mogensen, T. Æ. “An Investigation of Scoping and Parameter-Passing in Janus-Like
Languages”. University of Copenhagen, DIKU. 2016.
[33] Mogensen, T. Æ. “Garbage Collection for Reversible Functional Languages”. In: Reversible
Computation: 7th International Conference, RC 2015, Grenoble, France, July 16-17, 2015,
Proceedings. Ed. by Krivine, J. and Stefani, J.-B. Springer International Publishing, 2015,
pp. 79–94.
[34] Mogensen, T. Æ. “Partial Evaluation of the Reversible Language Janus”. In: Proceedings
of the 20th ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation.
ACM, 2011, pp. 23–32.
[35] Mogensen, T. Æ. “Reference Counting for Reversible Languages”. In: Reversible Computation: 6th International Conference, RC 2014, Kyoto, Japan, July 10-11, 2014. Proceedings.
Ed. by Yamashita, S. and Minato, S.-i. Springer International Publishing, 2014, pp. 82–94.
[36] Moore, G. E. “Cramming More Components onto Integrated Circuits”. In: Electronics 38.8
(1965), pp. 114–117.
[37] Mu, S.-C., Hu, Z., and Takeichi, M. “An Injective Language for Reversible Computation”. In:
Mathematics of Program Construction: 7th International Conference, MPC 2004, Stirling,
Scotland, UK, July 12-14, 2004. Proceedings. Ed. by Kozen, D. Springer Berlin Heidelberg,
2004, pp. 289–313.
[38] Nishida, N., Palacios, A., and Vidal, G. “Towards Reversible Computation in Erlang”.
In: LOPSTR’16: 26th International Symposium on Logic-based Program Synthesis and
Transformation. 2016.
[39]

Perlis, A. J. “Epigrams on Programming”. In: SIGPLAN Notices 17.9 (1982), pp. 7–13.

[40] Schultz, U. P. et al. “Towards a Domain-Specific Language for Reversible Assembly Sequences”. In: Reversible Computation: 7th International Conference, RC 2015, Grenoble,
France, July 16-17, 2015, Proceedings. Ed. by Krivine, J. and Stefani, J.-B. Springer
International Publishing, 2015, pp. 111–126.
[41] Thomsen, M. K., Axelsen, H. B., and Glück, R. “A Reversible Processor Architecture and
Its Reversible Logic Design”. In: Reversible Computation: Third International Workshop,
RC 2011, Gent, Belgium, July 4-5, 2011. Revised Papers. Ed. by Vos, A. D. and Wille, R.
Springer Berlin Heidelberg, 2011, pp. 30–42.
[42] Vieri, C. J. “Pendulum: A Reversible Computer Architecture”. Master’s Thesis. University
of California at Berkeley, 1993.
[43] Vieri, C. J. “Reversible Computer Engineering and Architecture”. PhD Thesis. Massachusetts Institute of Technology, 1999.
[44] Vieri, C. J. et al. “A Fully Reversible Asymptotically Zero Energy Microprocessor”. In:
Proceedings of the ISCA Workshop (1998).
[45] Winskel, G. The Formal Semantics of Programming Languages: An Introduction. Cambridge,
MA: MIT Press, 1993.
[46] Yokoyama, T., Axelsen, H. B., and Glück, R. “Principles of a Reversible Programming
Language”. In: Proceedings of the 5th Conference on Computing Frontiers. ACM, 2008,
pp. 43–54.

References

70 of 111

[47] Yokoyama, T., Axelsen, H. B., and Glück, R. “Reversible Flowchart Languages and the
Structured Reversible Program Theorem”. In: Automata, Languages and Programming: 35th
International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings,
Part II. Ed. by Aceto, L. et al. Springer Berlin Heidelberg, 2008, pp. 258–270.
[48] Yokoyama, T., Axelsen, H. B., and Glück, R. “Towards a Reversible Functional Language”.
In: RC 11: Proceedings of the Third International Conference on Reversible Computation.
Ed. by Vos, A. D. and Wille, R. Springer Berlin Heidelberg, 2011, pp. 14–29.
[49] Yokoyama, T. and Glück, R. “A Reversible Programming Language and its Invertible
Self-Interpreter”. In: PEPM 2007: Proceedings of the Workshop on Partial Evaluation and
Program Manipulation. ACM, 2007, pp. 144–153.

References

71 of 111

APPENDIX

A

Rooplc Source Code
A.1
1

AST.hs

module AST where

2
3

{−− AST P r i m i t i v e s −−}

4
5
6

type TypeName = String
type MethodName = String

7
8
9
10
11

data DataType = I n t e g e r T y p e
| ObjectType TypeName
| NilType
deriving (Show)

12
13
14
15
16
17
18
19

instance Eq DataType where
IntegerType
== I n t e g e r T y p e
=
NilType
== NilType
=
NilType
== ( ObjectType _) =
( ObjectType _) == NilType
=
( ObjectType t 1 ) == ( ObjectType t 2 ) =
_
== _
=

True
True
True
True
t 1 == t 2
False

20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

data BinOp =
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
deriving

Add
Sub
Xor
Mul
Div
Mod
BitAnd
BitOr
And
Or
Lt
Gt
Eq
Neq
Lte
Gte
(Show, Eq, Enum)

data ModOp =
|
|
deriving

ModAdd
ModSub
ModXor
(Show, Eq, Enum)

38
39
40
41
42
43
44

{−− G e n e r i c AST D e f i n i t i o n s −−}

45
46
47

−−E x p r e s s i o n s
data GExpr v = Constant Integer

Appendix A Rooplc Source Code

72 of 111

48
49
50
51

| Variable v
| Nil
| Binary BinOp ( GExpr v ) ( GExpr v )
deriving (Show, Eq)

52
53
54
55
56
57
58
59
60
61
62
63
64
65

−−S t a t e m e n t s
data GStmt m v = A s s i g n v ModOp ( GExpr v )
| Swap v v
| C o n d i t i o n a l ( GExpr v ) [ GStmt m v ] [ GStmt m v ] ( GExpr v )
| Loop ( GExpr v ) [ GStmt m v ] [ GStmt m v ] ( GExpr v )
| O b j e c t B l o c k TypeName v [ GStmt m v ]
| L o c a l B l o c k v ( GExpr v ) [ GStmt m v ] ( GExpr v )
| LocalCall m [ v ]
| LocalUncall m [ v ]
| O b j e c t C a l l v MethodName [ v ]
| O b j e c t U n c a l l v MethodName [ v ]
| Skip
deriving (Show, Eq)

66
67
68
69

−−F i e l d / Parameter d e c l a r a t i o n s
data GDecl v = GDecl DataType v
deriving (Show, Eq)

70
71
72
73

−−Method : Name , p a r a m e t e r s , body
data GMDecl m v = GMDecl m [ GDecl v ] [ GStmt m v ]
deriving (Show, Eq)

74
75
76
77

−−C l a s s : Name , b a s e c l a s s , f i e l d s , methods
data GCDecl m v = GCDecl TypeName (Maybe TypeName ) [ GDecl v ] [ GMDecl m v ]
deriving (Show, Eq)

78
79
80
81

−−Program
data GProg m v = GProg [ GCDecl m v ]
deriving (Show, Eq)

82
83

{−− S p e c i f i c AST D e f i n i t i o n s −−}

84
85
86
87
88
89
90
91
92

−−P l a i n AST
type I d e n t i f i e r = String
type E x p r e s s i o n = GExpr I d e n t i f i e r
type Statement = GStmt MethodName I d e n t i f i e r
type V a r i a b l e D e c l a r a t i o n = GDecl I d e n t i f i e r
type M e t h o d D e c l a r a t i o n = GMDecl MethodName I d e n t i f i e r
type C l a s s D e c l a r a t i o n = GCDecl MethodName I d e n t i f i e r
type Program = GProg MethodName I d e n t i f i e r

93
94
95
96
97
98
99
100

−−Scoped AST
type S I d e n t i f i e r = Integer
type S E x p r e s s i o n = GExpr S I d e n t i f i e r
type SStatement = GStmt S I d e n t i f i e r S I d e n t i f i e r
type S V a r i a b l e D e c l a r a t i o n = GDecl S I d e n t i f i e r
type S M e t h o d D e c l a r a t i o n = GMDecl S I d e n t i f i e r S I d e n t i f i e r
type SProgram = [ ( TypeName , GMDecl S I d e n t i f i e r S I d e n t i f i e r ) ]

101
102

{−− Other D e f i n i t i o n s −−}

103
104

type O f f s e t = Integer

105
106
107
108
109
110

data Symbol = L o c a l V a r i a b l e DataType I d e n t i f i e r
| C l a s s F i e l d DataType I d e n t i f i e r TypeName O f f s e t
| MethodParameter DataType I d e n t i f i e r
| Method [ DataType ] MethodName
deriving (Show, Eq)

111
112
113

type SymbolTable = [ ( S I d e n t i f i e r , Symbol ) ]
type Scope = [ ( I d e n t i f i e r , S I d e n t i f i e r ) ]

Appendix A Rooplc Source Code

73 of 111

A.2
1

PISA.hs

{−# LANGUAGE F l e x i b l e I n s t a n c e s , TypeSynonymInstances #−}

2
3

module PISA where

4
5
6

import Data . L i s t ( i n t e r c a l a t e )
import C o n t r o l . Arrow

7
8

import AST ( TypeName , MethodName )

9
10

type L a b e l = String

11
12
13

data R e g i s t e r = Reg Integer
deriving (Eq)

14
15

{−− G e n e r i c PISA D e f i n i t i o n s −−}

16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

data G I n s t r i = ADD R e g i s t e r R e g i s t e r
| ADDI R e g i s t e r i
| ANDX R e g i s t e r R e g i s t e r R e g i s t e r
| ANDIX R e g i s t e r R e g i s t e r i
| NORX R e g i s t e r R e g i s t e r R e g i s t e r
| NEG R e g i s t e r
| ORX R e g i s t e r R e g i s t e r R e g i s t e r
| ORIX R e g i s t e r R e g i s t e r i
| RL R e g i s t e r i
| RLV R e g i s t e r R e g i s t e r
| RR R e g i s t e r i
| RRV R e g i s t e r R e g i s t e r
| SLLX R e g i s t e r R e g i s t e r i
| SLLVX R e g i s t e r R e g i s t e r R e g i s t e r
| SRAX R e g i s t e r R e g i s t e r i
| SRAVX R e g i s t e r R e g i s t e r R e g i s t e r
| SRLX R e g i s t e r R e g i s t e r i
| SRLVX R e g i s t e r R e g i s t e r R e g i s t e r
| SUB R e g i s t e r R e g i s t e r
| XOR R e g i s t e r R e g i s t e r
| XORI R e g i s t e r i
| BEQ R e g i s t e r R e g i s t e r L a b e l
| BGEZ R e g i s t e r L a b e l
| BGTZ R e g i s t e r L a b e l
| BLEZ R e g i s t e r L a b e l
| BLTZ R e g i s t e r L a b e l
| BNE R e g i s t e r R e g i s t e r L a b e l
| BRA L a b e l
| EXCH R e g i s t e r R e g i s t e r
| SWAPBR R e g i s t e r
| RBRA L a b e l
| START
| FINISH
| DATA i
| SUBI R e g i s t e r i −−Pseudo
deriving (Eq)

53
54

data GProg i = GProg [ ( Maybe Label , G I n s t r i ) ]

55
56

{−− Macro PISA D e f i n i t i o n s −−}

57
58
59
60
61
62
63

data Macro =
|
|
|
|
deriving

Immediate Integer
AddressMacro L a b e l
SizeMacro TypeName
O f f s e t M a c r o TypeName MethodName
ProgramSize
(Show, Eq)

Appendix A Rooplc Source Code

74 of 111

64
65
66

type M I n s t r u c t i o n = G I n s t r Macro
type MProgram = GProg Macro

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

i n v e r t I n s t r u c t i o n s : : [ ( Maybe Label , M I n s t r u c t i o n ) ] −> [ ( Maybe Label ,
MInstruction ) ]
i n v e r t I n s t r u c t i o n s = reverse . map ( s e c o n d i n v e r t I n s t r u c t i o n . f i r s t ( fmap (++ "
_i " ) ) )
where i n v e r t I n s t r u c t i o n (ADD r 1 r 2 ) = SUB r 1 r 2
i n v e r t I n s t r u c t i o n (SUB r 1 r 2 ) = ADD r 1 r 2
i n v e r t I n s t r u c t i o n (ADDI r i ) = SUBI r i
i n v e r t I n s t r u c t i o n ( SUBI r i ) = ADDI r i
i n v e r t I n s t r u c t i o n (RL r i ) = RR r i
i n v e r t I n s t r u c t i o n (RLV r 1 r 2 ) = RRV r 1 r 2
i n v e r t I n s t r u c t i o n (RR r i ) = RL r i
i n v e r t I n s t r u c t i o n (RRV r 1 r 2 ) = RLV r 1 r 2
i n v e r t I n s t r u c t i o n (BEQ r 1 r 2 l ) = BEQ r 1 r 2 $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BGEZ r l ) = BGEZ r $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BGTZ r l ) = BGTZ r $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BLEZ r l ) = BLEZ r $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BLTZ r l ) = BLTZ r $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BNE r 1 r 2 l ) = BNE r 1 r 2 $ l ++ " _i "
i n v e r t I n s t r u c t i o n (BRA l ) = BRA $ l ++ " _i "
i n v e r t I n s t r u c t i o n (RBRA l ) = RBRA $ l ++ " _i "
invertInstruction inst = inst

87
88

{−− Output PISA D e f i n i t i o n s −−}

89
90
91

type I n s t r u c t i o n = G I n s t r Integer
type Program = GProg Integer

92
93
94

instance Show R e g i s t e r where
show ( Reg r ) = " $ " ++ show r

95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

instance
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show
show

Show I n s t r u c t i o n where
(ADD r 1 r 2 ) = unwords [ "ADD
" , show r1 , show r 2 ]
(ADDI r i ) = unwords [ "ADDI " , show r , show i ]
(ANDX r 1 r 2 r 3 ) = unwords [ "ANDX " , show r1 , show r2 , show r 3 ]
(ANDIX r 1 r 2 i ) = unwords [ "ANDIX " , show r1 , show r2 , show i ]
(NORX r 1 r 2 r 3 ) = unwords [ "NORX " , show r1 , show r2 , show r 3 ]
(NEG r ) = unwords [ "NEG
" , show r ]
(ORX r 1 r 2 r 3 ) = unwords [ "ORX
" , show r1 , show r2 , show r 3 ]
(ORIX r 1 r 2 i ) = unwords [ "ORIX " , show r1 , show r2 , show i ]
(RL r i ) = unwords [ "RL
" , show r , show i ]
(RLV r 1 r 2 ) = unwords [ "RLV
" , show r1 , show r 2 ]
(RR r i ) = unwords [ "RR
" , show r , show i ]
(RRV r 1 r 2 ) = unwords [ "RRV
" , show r1 , show r 2 ]
(SLLX r 1 r 2 i ) = unwords [ "SLLX " , show r1 , show r2 , show i ]
(SLLVX r 1 r 2 r 3 ) = unwords [ "SLLVX " , show r1 , show r2 , show r 3 ]
(SRAX r 1 r 2 i ) = unwords [ "SRAX " , show r1 , show r2 , show i ]
(SRAVX r 1 r 2 r 3 ) = unwords [ "SRAVX " , show r1 , show r2 , show r 3 ]
(SRLX r 1 r 2 i ) = unwords [ "SRLX " , show r1 , show r2 , show i ]
(SRLVX r 1 r 2 r 3 ) = unwords [ "SRLVX " , show r1 , show r2 , show r 3 ]
(SUB r 1 r 2 ) = unwords [ "SUB
" , show r1 , show r 2 ]
(XOR r 1 r 2 ) = unwords [ "XOR
" , show r1 , show r 2 ]
(XORI r i ) = unwords [ "XORI " , show r , show i ]
(BEQ r 1 r 2 l ) = unwords [ "BEQ
" , show r1 , show r2 , l ]
(BGEZ r l ) = unwords [ "BGEZ " , show r , l ]
(BGTZ r l ) = unwords [ "BGTZ " , show r , l ]
(BLEZ r l ) = unwords [ "BLEZ " , show r , l ]
(BLTZ r l ) = unwords [ "BLTZ " , show r , l ]
(BNE r 1 r 2 l ) = unwords [ "BNE
" , show r1 , show r2 , l ]
(BRA l ) = unwords [ "BRA
", l]
(EXCH r 1 r 2 ) = unwords [ "EXCH " , show r1 , show r 2 ]
(SWAPBR r ) = unwords [ "SWAPBR" , show r ]
(RBRA l ) = unwords [ "RBRA " , l ]

Appendix A Rooplc Source Code

75 of 111

128
129
130
131

show
show
show
show

START = "START "
FINISH = "FINISH"
(DATA i ) = unwords [ "DATA " , show i ]
( SUBI r i ) = unwords [ "ADDI " , show r , show $ − i ] −−Expand pseudo

132
133
134
135
136
137
138

showProgram : : Program −> String
showProgram ( GProg p ) = " ; ; pendulum p a l f i l e \n" ++ i n t e r c a l a t e " \n" (map
showLine p )
where showLine ( Nothing , i ) = s p a c e s 25 ++ show i
showLine ( Just l , i ) = l ++ " : " ++ s p a c e s ( 2 4 − length l ) ++ show i
s p a c e s : : ( Int −> String )
s p a c e s n = [ 1 . . n ] >> " "

139
140
141

writeProgram : : String −> Program −> IO ( )
writeProgram f i l e p = writeFile f i l e $ showProgram p

Appendix A Rooplc Source Code

76 of 111

A.3
1

Parser.hs

module P a r s e r ( p a r s e S t r i n g ) where

2
3
4
5

import C o n t r o l .Monad. Except
import Data . Functor . I d e n t i t y
import Data . B i f u n c t o r

6
7
8
9
10
11

import
import
import
import
import

Text . P a r s e c
Text . P a r s e c . String
Text . P a r s e c . Expr
Text . P a r s e c . Language
q u a l i f i e d Text . P a r s e c . Token a s Token

12
13

import AST

14
15

{−− Language D e f i n i t i o n −−}

16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

keywords : : [ String ]
keywords =
[" class " ,
" inherits " ,
" method " ,
"call" ,
" uncall " ,
" construct " ,
" destruct " ,
" skip " ,
" from " ,
" do " ,
" loop " ,
" until " ,
" int " ,
"nil" ,
"if",
" then " ,
"else" ,
"fi",
"local" ,
" delocal " ]

39
40
41
42
43
44
45
46
47
48
49
50
51

−−O p e r a t o r p r e c e d e n c e i d e n t i c a l t o C
o p e r a t o r T a b l e : : [ [ ( String , BinOp ) ] ]
operatorTable =
[ [ ( " ∗ " , Mul ) , ( " / " , Div ) , ( "%" , Mod) ] ,
[ ( "+" , Add) , ( "−" , Sub ) ] ,
[ ( "<" , Lt ) , ( "<=" , Lte ) , ( ">" , Gt ) , ( ">=" , Gte ) ] ,
[ ( "=" , Eq) , ( " != " , Neq ) ] ,
[ ( "&" , BitAnd ) ] ,
[ ( "^" , Xor ) ] ,
[ ( " | " , BitOr ) ] ,
[ ( "&&" , And) ] ,
[ ( " | | " , Or ) ] ]

52
53
54
55
56
57
58
59
60
61
62

l a n g u a g e D e f : : Token . LanguageDef s t
languageDef =
emptyDef {
Token . commentLine
= " // " ,
Token . nestedComments = False ,
Token . i d e n t S t a r t
= letter ,
Token . i d e n t L e t t e r
= alphaNum <|> oneOf "_’ " ,
Token . reservedOpNames = concatMap (map f s t ) o p e r a t o r T a b l e ,
Token . reservedNames
= keywords ,
Token . c a s e S e n s i t i v e
= True }

63

Appendix A Rooplc Source Code

77 of 111

64
65

t o k e n P a r s e r : : Token . TokenParser s t
t o k e n P a r s e r = Token . makeTokenParser l a n g u a g e D e f

66
67

{−− P a r s e r P r i m i t i v e s −−}

68
69
70

i d e n t i f i e r : : P a r s e r String
i d e n t i f i e r = Token . i d e n t i f i e r t o k e n P a r s e r

71
72
73

r e s e r v e d : : String −> P a r s e r ( )
r e s e r v e d = Token . r e s e r v e d t o k e n P a r s e r

74
75
76

r e s e r v e d O p : : String −> P a r s e r ( )
r e s e r v e d O p = Token . r e s e r v e d O p t o k e n P a r s e r

77
78
79

i n t e g e r : : P a r s e r Integer
i n t e g e r = Token . i n t e g e r t o k e n P a r s e r

80
81
82

symbol : : String −> P a r s e r String
symbol = Token . symbol t o k e n P a r s e r

83
84
85

p a r e n s : : P a r s e r a −> P a r s e r a
p a r e n s = Token . p a r e n s t o k e n P a r s e r

86
87
88

c o l o n : : P a r s e r String
c o l o n = Token . c o l o n t o k e n P a r s e r

89
90
91

commaSep : : P a r s e r a −> P a r s e r [ a ]
commaSep = Token . commaSep t o k e n P a r s e r

92
93
94

typeName : : P a r s e r TypeName
typeName = i d e n t i f i e r

95
96
97

methodName : : P a r s e r MethodName
methodName = i d e n t i f i e r

98
99

{−− E x p r e s s i o n P a r s e r s −−}

100
101
102

constant : : Parser Expression
c o n s t a n t = Constant <$> i n t e g e r

103
104
105

variable : : Parser Expression
v a r i a b l e = V a r i a b l e <$> i d e n t i f i e r

106
107
108

n i l : : Parser Expression
n i l = N i l <$ r e s e r v e d " n i l "

109
110
111
112
113

expression : : Parser Expression
e x p r e s s i o n = b u i l d E x p r e s s i o n P a r s e r opTable $ c o n s t a n t <|> v a r i a b l e <|> n i l
where binop ( t , op ) = I n f i x ( Binary op <$ r e s e r v e d O p t ) A s s o c L e f t
opTable = (map . map) binop o p e r a t o r T a b l e

114
115

{−− Statement P a r s e r s −−}

116
117
118
119
120

modOp : : P a r s e r ModOp
modOp = ModAdd <$ symbol "+="
<|> ModSub <$ symbol "−="
<|> ModXor <$ symbol "^="

121
122
123

a s s i g n : : P a r s e r Statement
a s s i g n = A s s i g n <$> i d e n t i f i e r <∗> modOp <∗> e x p r e s s i o n

124
125
126

swap : : P a r s e r Statement
swap = Swap <$> i d e n t i f i e r <∗ symbol "<=>" <∗> i d e n t i f i e r

127
128
129

c o n d i t i o n a l : : P a r s e r Statement
conditional =

Appendix A Rooplc Source Code

78 of 111

130
131
132
133
134
135
136
137
138

reserved " i f "
>> C o n d i t i o n a l
<$> e x p r e s s i o n
<∗ r e s e r v e d " then "
<∗> b l o c k
<∗ r e s e r v e d " e l s e "
<∗> b l o c k
<∗ r e s e r v e d " f i "
<∗> e x p r e s s i o n

139
140
141
142
143
144
145
146
147
148
149
150

l o o p : : P a r s e r Statement
loop =
r e s e r v e d " from "
>> Loop
<$> e x p r e s s i o n
<∗ r e s e r v e d " do "
<∗> b l o c k
<∗ r e s e r v e d " l o o p "
<∗> b l o c k
<∗ r e s e r v e d " u n t i l "
<∗> e x p r e s s i o n

151
152
153
154
155
156
157

l o c a l C a l l : : P a r s e r Statement
localCall =
reserved " c a l l "
>> L o c a l C a l l
<$> methodName
<∗> p a r e n s ( commaSep i d e n t i f i e r )

158
159
160
161
162
163
164

l o c a l U n c a l l : : P a r s e r Statement
localUncall =
reserved " uncall "
>> L o c a l U n c a l l
<$> methodName
<∗> p a r e n s ( commaSep i d e n t i f i e r )

165
166
167
168
169
170
171
172
173
174

o b j e c t C a l l : : P a r s e r Statement
objectCall =
reserved " c a l l "
>> O b j e c t C a l l
<$> i d e n t i f i e r
<∗ c o l o n
<∗ c o l o n
<∗> methodName
<∗> p a r e n s ( commaSep i d e n t i f i e r )

175
176
177
178
179
180
181
182
183
184

o b j e c t U n c a l l : : P a r s e r Statement
objectUncall =
reserved " uncall "
>> O b j e c t U n c a l l
<$> i d e n t i f i e r
<∗ c o l o n
<∗ c o l o n
<∗> methodName
<∗> p a r e n s ( commaSep i d e n t i f i e r )

185
186
187
188
189
190
191
192
193
194
195

l o c a l B l o c k : : P a r s e r Statement
localBlock =
reserved " local "
>> r e s e r v e d " i n t "
>> L o c a l B l o c k
<$> i d e n t i f i e r
<∗ symbol "="
<∗> e x p r e s s i o n
<∗> b l o c k
<∗ r e s e r v e d " d e l o c a l "

Appendix A Rooplc Source Code

79 of 111

196
197
198

<∗ i d e n t i f i e r
<∗ symbol "="
<∗> e x p r e s s i o n

199
200
201
202
203
204
205
206
207
208

o b j e c t B l o c k : : P a r s e r Statement
objectBlock =
reserved " construct "
>> O b j e c t B l o c k
<$> typeName
<∗> i d e n t i f i e r
<∗> b l o c k
<∗ r e s e r v e d " d e s t r u c t "
<∗ i d e n t i f i e r

209
210
211

s k i p : : P a r s e r Statement
s k i p = S k i p <$ r e s e r v e d " s k i p "

212
213
214
215
216
217
218
219
220
221
222
223
224

s t a t e m e n t : : P a r s e r Statement
s t a t e m e n t = try a s s i g n
<|> swap
<|> c o n d i t i o n a l
<|> l o o p
<|> try l o c a l C a l l
<|> try l o c a l U n c a l l
<|> o b j e c t C a l l
<|> o b j e c t U n c a l l
<|> l o c a l B l o c k
<|> o b j e c t B l o c k
<|> s k i p

225
226
227

b l o c k : : P a r s e r [ Statement ]
b l o c k = many1 s t a t e m e n t

228
229

{−− Top L e v e l P a r s e r s −−}

230
231
232

dataType : : P a r s e r DataType
dataType = I n t e g e r T y p e <$ r e s e r v e d " i n t " <|> ObjectType <$> typeName

233
234
235

variableDeclaration : : Parser VariableDeclaration
v a r i a b l e D e c l a r a t i o n = GDecl <$> dataType <∗> i d e n t i f i e r

236
237
238
239
240
241
242
243

methodDeclaration : : Parser MethodDeclaration
methodDeclaration =
r e s e r v e d " method "
>> GMDecl
<$> methodName
<∗> p a r e n s ( commaSep v a r i a b l e D e c l a r a t i o n )
<∗> b l o c k

244
245
246
247
248
249
250
251
252

c l a s s D e c l a r a t i o n : : Parser ClassDeclaration
classDeclaration =
reserved " class "
>> GCDecl
<$> typeName
<∗> optionMaybe ( r e s e r v e d " i n h e r i t s " >> typeName )
<∗> many v a r i a b l e D e c l a r a t i o n
<∗> many1 m e t h o d D e c l a r a t i o n

253
254
255

program : : P a r s e r Program
program = s p a c e s >> GProg <$> many1 c l a s s D e c l a r a t i o n <∗ e o f

256
257
258

p a r s e S t r i n g : : String −> Except String Program
p a r s e S t r i n g s = ExceptT ( I d e n t i t y $ f i r s t show $ p a r s e program " " s )

Appendix A Rooplc Source Code

80 of 111

A.4
1

ClassAnalyzer.hs

{−# LANGUAGE G e n e r a l i z e d N e w t y p e D e r i v i n g , F l e x i b l e C o n t e x t s #−}

2
3

module C l a s s A n a l y z e r ( c l a s s A n a l y s i s , CAState ( . . ) ) where

4
5
6

import Data .Maybe
import Data . L i s t

7
8
9
10

import C o n t r o l .Monad
import C o n t r o l .Monad. S t a t e
import C o n t r o l .Monad. Except

11
12

import AST

13
14

type S i z e = Integer

15
16
17
18
19
20
21
22
23
24

data CAState =
CAState {
c l a s s e s : : [ ( TypeName , C l a s s D e c l a r a t i o n ) ] ,
s u b C l a s s e s : : [ ( TypeName , [ TypeName ] ) ] ,
s u p e r C l a s s e s : : [ ( TypeName , [ TypeName ] ) ] ,
c l a s s S i z e : : [ ( TypeName , S i z e ) ] ,
c l a s s M e t h o d s : : [ ( TypeName , [ M e t h o d D e c l a r a t i o n ] ) ] ,
m a i n C l a s s : : Maybe TypeName
} deriving (Show, Eq)

25
26
27

newtype C l a s s A n a l y z e r a = C l a s s A n a l y z e r { runCA : : StateT CAState ( Except String )
a }
deriving ( Functor , A p p l i c a t i v e , Monad, MonadState CAState , MonadError String )

28
29
30
31
32
33

g e t C l a s s : : TypeName −> C l a s s A n a l y z e r C l a s s D e c l a r a t i o n
g e t C l a s s n = g e t s c l a s s e s >>= \ c s −>
case lookup n c s of
( Just c ) −> return c
Nothing −> t h r o w E r r o r $ "ICE : Unknown c l a s s " ++ n

34
35
36
37

g e t B a s e C l a s s : : TypeName −> C l a s s A n a l y z e r (Maybe TypeName )
g e t B a s e C l a s s n = g e t C l a s s n >>= g e t B a s e
where g e t B a s e ( GCDecl _ b _ _) = return b

38
39
40
41
42

c h e c k D u p l i c a t e C l a s s e s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
c h e c k D u p l i c a t e C l a s s e s ( GCDecl n _ _ _) = g e t s c l a s s e s >>= \ c s −>
when ( count c s > 1 ) ( t h r o w E r r o r $ " M u l t i p l e d e f i n i t i o n s o f c l a s s " ++ n )
where count = length . f i l t e r ((== n ) . f s t )

43
44
45
46
47
48
49

c h e c k B a s e C l a s s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
c h e c k B a s e C l a s s ( GCDecl _ Nothing _ _) = return ( )
c h e c k B a s e C l a s s ( GCDecl n ( Just b ) _ _) =
do when ( n == b ) ( t h r o w E r r o r $ " C l a s s " ++ n ++ " c an no t i n h e r i t from i t s e l f "
)
c s <− g e t s c l a s s e s
when ( isNothing $ lookup b c s ) ( t h r o w E r r o r $ " C l a s s " ++ n ++ " c an no t
i n h e r i t from unknown c l a s s " ++ b )

50
51
52
53
54

c h e c k D u p l i c a t e F i e l d s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
c h e c k D u p l i c a t e F i e l d s ( GCDecl n _ f s _) = mapM_ c h e c k F i e l d f s
where count v = length . f i l t e r ( \ ( GDecl _ v ’ ) −> v ’ == v ) $ f s
c h e c k F i e l d ( GDecl _ v ) = when ( count v > 1 ) ( t h r o w E r r o r $ " M u l t i p l e
d e c l a r a t i o n s o f f i e l d " ++ v ++ " i n c l a s s " ++ n )

55
56
57
58
59

c h e c k D u p l i c a t e M e t h o d s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
c h e c k D u p l i c a t e M e t h o d s ( GCDecl n _ _ ms ) = mapM_ checkMethod ms ’
where ms ’ = map ( \ ( GMDecl n ’ _ _) −> n ’ ) ms
count m = length . f i l t e r (== m) $ ms ’

Appendix A Rooplc Source Code

81 of 111

60

checkMethod m = when ( count m > 1 ) ( t h r o w E r r o r $ " M u l t i p l e d e f i n i t i o n s
o f method " ++ m ++ " i n c l a s s " ++ n )

61
62
63
64
65
66
67
68
69

c h e c k C y c l i c I n h e r i t a n c e : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
c h e c k C y c l i c I n h e r i t a n c e ( GCDecl _ Nothing _ _) = return ( )
c h e c k C y c l i c I n h e r i t a n c e ( GCDecl n b _ _) = c h e c k I n h e r i t a n c e b [ n ]
where c h e c k I n h e r i t a n c e Nothing _ = return ( )
c h e c k I n h e r i t a n c e ( Just b ’ ) v i s i t e d =
do when ( b ’ ‘ elem ‘ v i s i t e d ) ( t h r o w E r r o r $ " C y c l i c i n h e r i t a n c e
i n v o l v i n g c l a s s " ++ n )
next <− g e t B a s e C l a s s b ’
c h e c k I n h e r i t a n c e next ( b ’ : v i s i t e d )

70
71
72
73
74
75

s e t M a i n C l a s s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t M a i n C l a s s ( GCDecl n _ _ ms ) = when ( " main " ‘ elem ‘ ms ’ ) ( g e t s m a i n C l a s s >>= s e t
)
where ms ’ = map ( \ ( GMDecl n ’ _ _) −> n ’ ) ms
s e t ( Just m) = t h r o w E r r o r $ "Method main a l r e a d y d e f i n e d i n c l a s s " ++
m ++ " but r e d e f i n e d i n c l a s s " ++ n
s e t Nothing = modify $ \ s −> s { m a i n C l a s s = Just n }

76
77
78
79
80
81
82
83
84
85

i n i t i a l S t a t e : : CAState
initialState =
CAState {
classes = [] ,
subClasses = [ ] ,
superClasses = [ ] ,
classSize = [] ,
classMethods = [ ] ,
m a i n C l a s s = Nothing }

86
87
88

s e t C l a s s e s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t C l a s s e s c@ ( GCDecl n _ _ _) = modify $ \ s −> s { c l a s s e s = ( n , c ) : c l a s s e s s }

89
90
91

s e t S u b C l a s s e s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t S u b C l a s s e s ( GCDecl n b _ _) = modify ( \ s −> s { s u b C l a s s e s = ( n ,
s u b C l a s s e s s } ) >> addSubClass n b

[])

:

92
93
94
95
96
97
98

addSubClass : : TypeName −> Maybe TypeName −> C l a s s A n a l y z e r ( )
addSubClass _ Nothing = return ( )
addSubClass n ( Just b ) = g e t s s u b C l a s s e s >>= \ s c −>
case lookup b s c of
Nothing −> modify $ \ s −> s { s u b C l a s s e s = ( b , [ n ] ) : s c }
( Just sc ’ ) −> modify $ \ s −> s { s u b C l a s s e s = ( b , n : sc ’ ) : delete ( b ,
sc ’ ) s c }

99
100
101
102

s e t S u p e r C l a s s e s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t S u p e r C l a s s e s ( GCDecl n _ _ _) = g e t s s u b C l a s s e s >>= \ s c −>
modify $ \ s −> s { s u p e r C l a s s e s = ( n , map f s t $ f i l t e r ( \ (_, sub ) −> n ‘ elem ‘
sub ) s c ) : s u p e r C l a s s e s s }

103
104
105
106

getClassSize
getClassSize
getClassSize
return $

: : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r S i z e
( GCDecl _ Nothing f s _) = return $ 1 + genericLength f s
( GCDecl _ ( Just b ) f s _) = g e t C l a s s b >>= g e t C l a s s S i z e >>= \ s z −>
s z + genericLength f s

107
108
109
110

s e t C l a s s S i z e : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t C l a s s S i z e c@ ( GCDecl n _ _ _) = g e t C l a s s S i z e c >>= \ s z −>
modify $ \ s −> s { c l a s s S i z e = ( n , s z ) : c l a s s S i z e s }

111
112
113
114
115

r e s o l v e C l a s s M e t h o d s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r [ M e t h o d D e c l a r a t i o n ]
r e s o l v e C l a s s M e t h o d s ( GCDecl _ Nothing _ ms ) = return ms
r e s o l v e C l a s s M e t h o d s ( GCDecl n ( Just b ) _ ms ) = g e t C l a s s b >>= r e s o l v e C l a s s M e t h o d s
>>= combine
where c h e c k S i g n a t u r e ( GMDecl m ps _, GMDecl m’ ps ’ _) = when (m == m’ && ps
/= ps ’ ) ( t h r o w E r r o r $ "Method " ++ m ++ " i n c l a s s " ++ n ++ " has

Appendix A Rooplc Source Code

82 of 111

116
117

i n v a l i d method s i g n a t u r e " )
compareName ( GMDecl m _ _) ( GMDecl m’ _ _) = m == m’
combine ms ’ = mapM_ c h e c k S i g n a t u r e ( ( , ) <$> ms <∗> ms ’ ) >> return (
unionBy compareName ms ms ’ )

118
119
120
121

s e t C l a s s M e t h o d s : : C l a s s D e c l a r a t i o n −> C l a s s A n a l y z e r ( )
s e t C l a s s M e t h o d s c@ ( GCDecl n _ _ _) = r e s o l v e C l a s s M e t h o d s c >>= \cm −>
modify $ \ s −> s { c l a s s M e t h o d s = ( n , cm) : c l a s s M e t h o d s s }

122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

caProgram : : Program −> C l a s s A n a l y z e r Program
caProgram ( GProg p ) =
do mapM_ s e t C l a s s e s p
mapM_ s e t S u b C l a s s e s p
mapM_ s e t S u p e r C l a s s e s p
mapM_ s e t C l a s s S i z e p
mapM_ s e t C l a s s M e t h o d s p
mapM_ c h e c k D u p l i c a t e C l a s s e s p
mapM_ c h e c k D u p l i c a t e F i e l d s p
mapM_ c h e c k D u p l i c a t e M e t h o d s p
mapM_ c h e c k B a s e C l a s s p
mapM_ c h e c k C y c l i c I n h e r i t a n c e p
mapM_ s e t M a i n C l a s s p
mc <− g e t s m a i n C l a s s
when ( isNothing mc) ( t h r o w E r r o r "No main method d e f i n e d " )
return $ GProg r o o t C l a s s e s
where r o o t C l a s s e s = f i l t e r noBase p
noBase ( GCDecl _ Nothing _ _) = True
noBase _ = False

142
143
144

c l a s s A n a l y s i s : : Program −> Except String ( Program , CAState )
c l a s s A n a l y s i s p = runStateT ( runCA $ caProgram p ) i n i t i a l S t a t e

Appendix A Rooplc Source Code

83 of 111

A.5
1

ScopeAnalyzer.hs

{−# LANGUAGE G e n e r a l i z e d N e w t y p e D e r i v i n g #−}

2
3

module S c o p e A n a l y z e r ( s c o p e A n a l y s i s , SAState ( . . ) ) where

4
5
6

import Data .Maybe
import Data . L i s t

7
8
9

import C o n t r o l .Monad. S t a t e
import C o n t r o l .Monad. Except

10
11
12

import AST
import C l a s s A n a l y z e r

13
14
15
16
17
18
19
20
21
22

data SAState =
SAState {
symbolIndex : : S I d e n t i f i e r ,
symbolTable : : SymbolTable ,
s c o p e S t a c k : : [ Scope ] ,
v i r t u a l T a b l e s : : [ ( TypeName , [ S I d e n t i f i e r ] ) ] ,
c a S t a t e : : CAState ,
mainMethod : : S I d e n t i f i e r
} deriving (Show, Eq)

23
24
25

newtype S c o p e A n a l y z e r a = S c o p e A n a l y z e r { runSA : : StateT SAState ( Except String )
a }
deriving ( Functor , A p p l i c a t i v e , Monad, MonadState SAState , MonadError String )

26
27
28

i n i t i a l S t a t e : : CAState −> SAState
i n i t i a l S t a t e s = SAState { symbolIndex = 0 , symbolTable = [ ] , s c o p e S t a c k = [ ] ,
v i r t u a l T a b l e s = [ ] , c a S t a t e = s , mainMethod = 0 }

29
30
31

enterScope : : ScopeAnalyzer ( )
e n t e r S c o p e = modify $ \ s −> s { s c o p e S t a c k = [ ]

: scopeStack s }

32
33
34

leaveScope : : ScopeAnalyzer ( )
l e a v e S c o p e = modify $ \ s −> s { s c o p e S t a c k = drop 1 $ s c o p e S t a c k s }

35
36
37
38
39
40

t o p S c o p e : : S c o p e A n a l y z e r Scope
t o p S c o p e = g e t s s c o p e S t a c k >>= \ s s −>
case s s of
( s :_) −> return s
[ ] −> t h r o w E r r o r "ICE : Empty s c o p e s t a c k "

41
42
43
44
45

addToScope : : ( I d e n t i f i e r , S I d e n t i f i e r ) −> S c o p e A n a l y z e r ( )
addToScope b =
do t s <− t o p S c o p e
modify $ \ s −> s { s c o p e S t a c k = ( b : t s ) : drop 1 ( s c o p e S t a c k s ) }

46
47
48
49
50
51
52
53
54

s a I n s e r t : : Symbol −> I d e n t i f i e r −> S c o p e A n a l y z e r S I d e n t i f i e r
s a I n s e r t sym n =
do t s <− t o p S c o p e
when ( i s J u s t $ lookup n t s ) ( t h r o w E r r o r $ " R e d e c l a r a t i o n o f symbol : " ++ n
)
i <− g e t s symbolIndex
modify $ \ s −> s { symbolTable = ( i , sym ) : symbolTable s , symbolIndex = 1
+ i }
addToScope ( n , i )
return i

55
56
57
58
59

saLookup : : I d e n t i f i e r −> S c o p e A n a l y z e r S I d e n t i f i e r
saLookup n = g e t s s c o p e S t a c k >>= \ s s −>
case listToMaybe $ mapMaybe ( lookup n ) s s of
Nothing −> t h r o w E r r o r $ " U n d e c l a r e d symbol : " ++ n

Appendix A Rooplc Source Code

84 of 111

60

Just i −> return i

61
62
63
64
65
66
67
68
69

s a E x p r e s s i o n : : E x p r e s s i o n −> S c o p e A n a l y z e r S E x p r e s s i o n
s a E x p r e s s i o n ( Constant v ) = pure $ Constant v
s a E x p r e s s i o n ( V a r i a b l e n ) = V a r i a b l e <$> saLookup n
s a E x p r e s s i o n N i l = pure N i l
s a E x p r e s s i o n ( Binary binop e1 e2 ) =
Binary binop
<$> s a E x p r e s s i o n e1
<∗> s a E x p r e s s i o n e2

70
71
72
73
74
75
76
77
78
79

s a S t a t e m e n t : : Statement −> S c o p e A n a l y z e r SStatement
saStatement s =
case s of
( A s s i g n n modop e ) −>
when ( elem n $ v a r e ) ( t h r o w E r r o r " I r r e v e r s i b l e v a r i a b l e a s s i g n m e n t " )
>> A s s i g n
<$> saLookup n
<∗> pure modop
<∗> s a E x p r e s s i o n e

80
81
82
83
84

( Swap n1 n2 ) −>
Swap
<$> saLookup n1
<∗> saLookup n2

85
86
87
88
89
90
91

( C o n d i t i o n a l e1 s 1 s 2 e2 ) −>
Conditional
<$> s a E x p r e s s i o n e1
<∗> mapM s a S t a t e m e n t s 1
<∗> mapM s a S t a t e m e n t s 2
<∗> s a E x p r e s s i o n e2

92
93
94
95
96
97
98

( Loop e1 s 1 s 2 e2 ) −>
Loop
<$> s a E x p r e s s i o n e1
<∗> mapM s a S t a t e m e n t s 1
<∗> mapM s a S t a t e m e n t s 2
<∗> s a E x p r e s s i o n e2

99
100
101
102
103
104
105

( O b j e c t B l o c k tp n stmt ) −>
do e n t e r S c o p e
n ’ <− s a I n s e r t ( L o c a l V a r i a b l e ( ObjectType tp ) n ) n
stmt ’ <− mapM s a S t a t e m e n t stmt
leaveScope
return $ O b j e c t B l o c k tp n ’ stmt ’

106
107
108
109
110
111
112
113
114

( L o c a l B l o c k n e1 stmt e2 ) −>
do e1 ’ <− s a E x p r e s s i o n e1
enterScope
n ’ <− s a I n s e r t ( L o c a l V a r i a b l e I n t e g e r T y p e n ) n
stmt ’ <− mapM s a S t a t e m e n t stmt
leaveScope
e2 ’ <− s a E x p r e s s i o n e2
return $ L o c a l B l o c k n ’ e1 ’ stmt ’ e2 ’

115
116
117
118
119

( L o c a l C a l l m a r g s ) −>
LocalCall
<$> saLookup m
<∗> l o c a l C a l l m a r g s

120
121
122
123
124

( L o c a l U n c a l l m a r g s ) −>
LocalUncall
<$> saLookup m
<∗> l o c a l C a l l m a r g s

125

Appendix A Rooplc Source Code

85 of 111

126
127
128
129
130
131

( ObjectCall o m args )
when ( a r g s /= nub
invocation of
>> O b j e c t C a l l
<$> saLookup o
<∗> pure m
<∗> mapM saLookup

−>
a r g s | | o ‘ elem ‘ a r g s ) ( t h r o w E r r o r $ " I r r e v e r s i b l e
method " ++ m)

args

132
133
134
135
136
137
138

( O b j e c t U n c a l l o m a r g s ) −>
when ( a r g s /= nub a r g s | | o ‘ elem ‘ a r g s ) ( t h r o w E r r o r $ " I r r e v e r s i b l e
i n v o c a t i o n o f method " ++ m)
>> O b j e c t U n c a l l
<$> saLookup o
<∗> pure m
<∗> mapM saLookup a r g s

139
140

S k i p −> pure S k i p

141
142
143
144

where v a r ( V a r i a b l e n ) = [ n ]
v a r ( Binary _ e1 e2 ) = v a r e1 ++ v a r e2
var _ = [ ]

145
146
147

isCF C l a s s F i e l d {} = True
isCF _ = False

148
149

r l o o k u p = f l i p lookup

150
151
152
153
154
155
156
157

l o c a l C a l l : : MethodName −> [ I d e n t i f i e r ] −> S c o p e A n a l y z e r [ S I d e n t i f i e r ]
l o c a l C a l l m args =
do when ( a r g s /= nub a r g s ) ( t h r o w E r r o r $ " I r r e v e r s i b l e i n v o c a t i o n o f
method " ++ m)
a r g s ’ <− mapM saLookup a r g s
s t <− g e t s symbolTable
when ( any isCF $ mapMaybe ( r l o o k u p s t ) a r g s ’ ) ( t h r o w E r r o r $ "
I r r e v e r s i b l e i n v o c a t i o n o f method " ++ m)
return a r g s ’

158
159
160

setMainMethod : : S I d e n t i f i e r −> S c o p e A n a l y z e r ( )
setMainMethod i = modify $ \ s −> s { mainMethod = i }

161
162
163
164
165
166
167
168
169
170
171

saMethod : : ( TypeName , M e t h o d D e c l a r a t i o n ) −> S c o p e A n a l y z e r ( TypeName ,
SMethodDeclaration )
saMethod ( t , GMDecl m ps body ) =
do m’ <− saLookup m
when (m == " main " ) ( setMainMethod m’ )
enterScope
ps ’ <− mapM i n s e r t M e t h o d P a r a m e t e r ps
body ’ <− mapM s a S t a t e m e n t body
leaveScope
return ( t , GMDecl m’ ps ’ body ’ )
where i n s e r t M e t h o d P a r a m e t e r ( GDecl tp n ) = GDecl tp <$> s a I n s e r t (
MethodParameter tp n ) n

172
173
174
175
176
177
178
179
180

g e t S u b C l a s s e s : : TypeName −> S c o p e A n a l y z e r [ C l a s s D e c l a r a t i o n ]
getSubClasses n =
do c s <− g e t s $ c l a s s e s . c a S t a t e
s c <− g e t s $ s u b C l a s s e s . c a S t a t e
case lookup n s c of
Nothing −> t h r o w E r r o r $ "ICE : Unknown c l a s s " ++ n
( Just sc ’ ) −> return $ mapMaybe ( r l o o k u p c s ) sc ’
where r l o o k u p = f l i p lookup

181
182
183
184
185

getMethodName : : S I d e n t i f i e r −> S c o p e A n a l y z e r ( S I d e n t i f i e r , MethodName )
getMethodName i = g e t s symbolTable >>= \ s t −>
case lookup i s t of
( Just ( Method _ m) ) −> return ( i , m)

Appendix A Rooplc Source Code

86 of 111

186

_ −> t h r o w E r r o r $ "ICE : I n v a l i d method i n d e x " ++ show i

187
188
189
190
191

p r e f i x V t a b l e : : [ ( S I d e n t i f i e r , MethodName ) ] −> ( S I d e n t i f i e r , MethodName ) −> [ (
S I d e n t i f i e r , MethodName ) ]
p r e f i x V t a b l e [ ] m’ = [m’ ]
p r e f i x V t a b l e (m: ms ) m’ = i f comp m m’ then m’ : ms e l s e m : p r e f i x V t a b l e ms m’
where comp (_, n ) (_, n ’ ) = n == n ’

192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209

s a C l a s s : : O f f s e t −> [ S I d e n t i f i e r ] −> C l a s s D e c l a r a t i o n −> S c o p e A n a l y z e r [ (
TypeName , S M e t h o d D e c l a r a t i o n ) ]
s a C l a s s o f f s e t p i d s ( GCDecl c _ f s ms ) =
do e n t e r S c o p e
mapM_ i n s e r t C l a s s F i e l d $ zip [ o f f s e t . . ] f s
m1 <− mapM getMethodName p i d s
m2 <− mapM i n s e r t M e t h o d ms
l e t m3 = map f s t $ f o l d l p r e f i x V t a b l e m1 m2
o f f s e t ’ = genericLength f s + o f f s e t
modify $ \ s −> s { v i r t u a l T a b l e s = ( c , m3) : v i r t u a l T a b l e s s }
s c <− g e t S u b C l a s s e s c
ms ’ <− concat <$> mapM ( s a C l a s s o f f s e t ’ m3) s c
ms ’ ’ <− mapM saMethod $ zip ( repeat c ) ms
leaveScope
return $ ms ’ ++ ms ’ ’
where i n s e r t C l a s s F i e l d ( o , GDecl tp n ) = s a I n s e r t ( C l a s s F i e l d tp n c o ) n
i n s e r t M e t h o d ( GMDecl n ps _) = s a I n s e r t ( Method (map getType ps ) n ) n
>>= getMethodName
getType ( GDecl tp _) = tp

210
211
212

saProgram : : Program −> S c o p e A n a l y z e r SProgram
saProgram ( GProg c s ) = concat <$> mapM ( s a C l a s s 1 [ ] ) c s

213
214
215

s c o p e A n a l y s i s : : ( Program , CAState ) −> Except String ( SProgram , SAState )
s c o p e A n a l y s i s ( p , s ) = runStateT ( runSA $ saProgram p ) $ i n i t i a l S t a t e s

Appendix A Rooplc Source Code

87 of 111

A.6
1

TypeChecker.hs

{−# LANGUAGE G e n e r a l i z e d N e w t y p e D e r i v i n g #−}

2
3

module TypeChecker ( typeCheck ) where

4
5

import Data . L i s t

6
7
8

import C o n t r o l .Monad. Reader
import C o n t r o l .Monad. Except

9
10
11
12

import AST
import C l a s s A n a l y z e r
import S c o p e A n a l y z e r

13
14
15

newtype TypeChecker a = TypeChecker { runTC : : ReaderT SAState ( Except String ) a
}
deriving ( Functor , A p p l i c a t i v e , Monad, MonadReader SAState , MonadError String
)

16
17
18
19
20
21
22
23

getType : : S I d e n t i f i e r −> TypeChecker DataType
getType i = a s k s symbolTable >>= \ s t −>
case lookup i s t of
( Just ( L o c a l V a r i a b l e t _) ) −> return t
( Just ( C l a s s F i e l d t _ _ _) ) −> return t
( Just ( MethodParameter t _) ) −> return t
_ −> t h r o w E r r o r $ "ICE : I n v a l i d i n d e x " ++ show i

24
25
26
27
28
29

getParameterTypes : : S I d e n t i f i e r −> TypeChecker [ DataType ]
getParameterTypes i = a s k s symbolTable >>= \ s t −>
case lookup i s t of
( Just ( Method ps _) ) −> return ps
_ −> t h r o w E r r o r $ "ICE : I n v a l i d i n d e x " ++ show i

30
31
32

expectType : : DataType −> DataType −> TypeChecker ( )
expectType t 1 t 2 = unless ( t 1 == t 2 ) ( t h r o w E r r o r $ " Expected t y p e : " ++ show t 1
++ " \ nActual t y p e : " ++ show t 2 )

33
34
35
36
37
38

g e t C l a s s M e t h o d s : : TypeName −> TypeChecker [ M e t h o d D e c l a r a t i o n ]
g e t C l a s s M e t h o d s n = a s k s ( c l a s s M e t h o d s . c a S t a t e ) >>= \cm −>
case lookup n cm of
Nothing −> t h r o w E r r o r $ "ICE : Unknown c l a s s " ++ n
( Just ms ) −> return ms

39
40
41
42
43
44

getDynamicParameterTypes : : TypeName −> MethodName −> TypeChecker [ DataType ]
getDynamicParameterTypes n m = g e t C l a s s M e t h o d s n >>= \ms −>
case find ( \ ( GMDecl m’ _ _) −> m == m’ ) ms of
Nothing −> t h r o w E r r o r $ " C l a s s " ++ n ++ " d o e s not s u p p o r t method " ++ m
( Just ( GMDecl _ ps _) ) −> return $ map ( \ ( GDecl tp _) −> tp ) ps

45
46
47
48
49
50

c h e c k C a l l : : [ S I d e n t i f i e r ] −> [ DataType ] −> TypeChecker ( )
c h e c k C a l l a r g s ps = when ( l a /= l p ) ( t h r o w E r r o r e r r ) >> mapM getType a r g s >>= \ a s
−> mapM_ checkArgument ( zip a s ps )
where l a = length a r g s
l p = length ps
e r r = " Passed " ++ show l a ++ " argument ( s ) t o method e x p e c t i n g " ++
show l p ++ " argument ( s ) "

51
52
53
54
55

checkArgument : : ( DataType , DataType ) −> TypeChecker ( )
checkArgument ( ObjectType ca , ObjectType cp ) = a s k s ( s u p e r C l a s s e s . c a S t a t e ) >>=
\ s c −>
unless ( ca == cp | | maybe False ( elem cp ) ( lookup ca s c ) ) ( t h r o w E r r o r $ "
C l a s s " ++ ca ++ " not a s u b t y p e o f c l a s s " ++ cp )
checkArgument ( ta , tp ) = expectType tp t a

56

Appendix A Rooplc Source Code

88 of 111

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

t c E x p r e s s i o n : : S E x p r e s s i o n −> TypeChecker DataType
t c E x p r e s s i o n ( Constant _) = pure I n t e g e r T y p e
t c E x p r e s s i o n ( V a r i a b l e n ) = getType n
t c E x p r e s s i o n N i l = pure NilType
t c E x p r e s s i o n ( Binary binop e1 e2 )
| binop == Eq | | binop == Neq =
do t 1 <− t c E x p r e s s i o n e1
t 2 <− t c E x p r e s s i o n e2
expectType t 1 t 2
pure I n t e g e r T y p e
| otherwise =
do t 1 <− t c E x p r e s s i o n e1
t 2 <− t c E x p r e s s i o n e2
expectType t 1 I n t e g e r T y p e
expectType t 2 I n t e g e r T y p e
pure I n t e g e r T y p e

73
74
75
76
77
78
79
80
81

t c S t a t e m e n t : : SStatement −> TypeChecker ( )
tcStatement s =
case s of
( A s s i g n n _ e ) −>
getType n
>>= expectType I n t e g e r T y p e
>> t c E x p r e s s i o n e
>>= expectType I n t e g e r T y p e

82
83
84
85
86

( Swap n1 n2 ) −>
do t 1 <− getType n1
t 2 <− getType n2
expectType t 1 t 2

87
88
89
90
91
92
93
94

( C o n d i t i o n a l e1 s 1 s 2 e2 ) −>
t c E x p r e s s i o n e1
>>= expectType I n t e g e r T y p e
>> mapM_ t c S t a t e m e n t s 1
>> mapM_ t c S t a t e m e n t s 2
>> t c E x p r e s s i o n e2
>>= expectType I n t e g e r T y p e

95
96
97
98
99
100
101
102

( Loop e1 s 1 s 2 e2 ) −>
t c E x p r e s s i o n e1
>>= expectType I n t e g e r T y p e
>> mapM_ t c S t a t e m e n t s 1
>> mapM_ t c S t a t e m e n t s 2
>> t c E x p r e s s i o n e2
>>= expectType I n t e g e r T y p e

103
104
105

( O b j e c t B l o c k _ _ stmt ) −>
mapM_ t c S t a t e m e n t stmt

106
107
108
109
110
111
112
113
114

( L o c a l B l o c k n e1 stmt e2 ) −>
getType n
>>= expectType I n t e g e r T y p e
>> t c E x p r e s s i o n e1
>>= expectType I n t e g e r T y p e
>> mapM_ t c S t a t e m e n t stmt
>> t c E x p r e s s i o n e2
>>= expectType I n t e g e r T y p e

115
116
117
118

( L o c a l C a l l m a r g s ) −>
getParameterTypes m
>>= c h e c k C a l l a r g s

119
120
121
122

( L o c a l U n c a l l m a r g s ) −>
getParameterTypes m
>>= c h e c k C a l l a r g s

Appendix A Rooplc Source Code

89 of 111

123
124
125
126
127
128

( O b j e c t C a l l o m a r g s ) −>
do t <− getType o
case t of
( ObjectType tn ) −> getDynamicParameterTypes tn m >>= c h e c k C a l l
args
_ −> t h r o w E r r o r $ "Non−o b j e c t t y p e " ++ show t ++ " d o e s not
s u p p o r t method i n v o c a t i o n "

129
130
131
132
133
134

( O b j e c t U n c a l l o m a r g s ) −>
do t <− getType o
case t of
( ObjectType tn ) −> getDynamicParameterTypes tn m >>= c h e c k C a l l
args
_ −> t h r o w E r r o r $ "Non−o b j e c t t y p e " ++ show t ++ " d o e s not
s u p p o r t method i n v o c a t i o n "

135
136

S k i p −> pure ( )

137
138
139
140
141
142

getMethodName : : S I d e n t i f i e r −> TypeChecker I d e n t i f i e r
getMethodName i = a s k s symbolTable >>= \ s t −>
case lookup i s t of
( Just ( Method _ n ) ) −> return n
_ −> t h r o w E r r o r $ "ICE : I n v a l i d i n d e x " ++ show i

143
144
145
146
147
148

tcMethod : : ( TypeName , S M e t h o d D e c l a r a t i o n ) −> TypeChecker ( )
tcMethod (_, GMDecl _ [ ] body ) = mapM_ t c S t a t e m e n t body
tcMethod (_, GMDecl i (_:_) body ) = getMethodName i >>= \n −>
when ( n == " main " ) ( t h r o w E r r o r "Method main has i n v a l i d s i g n a t u r e " )
>> mapM_ t c S t a t e m e n t body

149
150
151

tcProgram : : SProgram −> TypeChecker ( SProgram , SAState )
tcProgram p = ( , ) p <$> (mapM_ tcMethod p >> a s k )

152
153
154

typeCheck : : ( SProgram , SAState ) −> Except String ( SProgram , SAState )
typeCheck ( p , s ) = runReaderT ( runTC $ tcProgram p ) s

Appendix A Rooplc Source Code

90 of 111

A.7
1

CodeGenerator.hs

{−# LANGUAGE G e n e r a l i z e d N e w t y p e D e r i v i n g #−}

2
3

module CodeGenerator ( generatePISA ) where

4
5

import Data . L i s t

6
7
8
9

import C o n t r o l .Monad. S t a t e
import C o n t r o l .Monad. Except
import C o n t r o l . Arrow

10
11
12
13
14

import
import
import
import

AST
PISA
ClassAnalyzer
ScopeAnalyzer

15
16

{−# ANN module " HLint : i g n o r e Reduce d u p l i c a t i o n " #−}

17
18
19
20
21
22
23
24
25

data CGState =
CGState {
labelIndex : : SIdentifier ,
r e g i s t e r I n d e x : : Integer ,
l a b e l T a b l e : : [ ( S I d e n t i f i e r , Label ) ] ,
registerStack : : [ ( SIdentifier , Register ) ] ,
s a S t a t e : : SAState
} deriving (Show, Eq)

26
27
28

newtype CodeGenerator a = CodeGenerator { runCG : : StateT CGState ( Except String )
a }
deriving ( Functor , A p p l i c a t i v e , Monad, MonadState CGState , MonadError String )

29
30
31

i n i t i a l S t a t e : : SAState −> CGState
i n i t i a l S t a t e s = CGState { l a b e l I n d e x = 0 , r e g i s t e r I n d e x = 4 , l a b e l T a b l e = [ ] ,
registerStack = [ ] , saState = s }

32
33
34

registerZero : : Register
r e g i s t e r Z e r o = Reg 0

35
36
37

registerSP : : Register
r e g i s t e r S P = Reg 1

38
39
40

registerRO : : Register
r e g i s t e r R O = Reg 2

41
42
43

registerThis : : Register
r e g i s t e r T h i s = Reg 3

44
45
46
47
48
49

p u s h R e g i s t e r : : S I d e n t i f i e r −> CodeGenerator R e g i s t e r
pushRegister i =
do r i <− g e t s r e g i s t e r I n d e x
modify $ \ s −> s { r e g i s t e r I n d e x = 1 + r i , r e g i s t e r S t a c k = ( i , Reg r i ) :
registerStack s }
return $ Reg r i

50
51
52

p o p R e g i s t e r : : CodeGenerator ( )
p o p R e g i s t e r = modify $ \ s −> s { r e g i s t e r I n d e x = ( −1) + r e g i s t e r I n d e x s ,
r e g i s t e r S t a c k = drop 1 $ r e g i s t e r S t a c k s }

53
54
55
56
57
58

t e m p R e g i s t e r : : CodeGenerator R e g i s t e r
tempRegister =
do r i <− g e t s r e g i s t e r I n d e x
modify $ \ s −> s { r e g i s t e r I n d e x = 1 + r i }
return $ Reg r i

59

Appendix A Rooplc Source Code

91 of 111

60
61

popTempRegister : : CodeGenerator ( )
popTempRegister = modify $ \ s −> s { r e g i s t e r I n d e x = ( −1) + r e g i s t e r I n d e x s }

62
63
64
65
66
67

l o o k u p R e g i s t e r : : S I d e n t i f i e r −> CodeGenerator R e g i s t e r
l o o k u p R e g i s t e r i = g e t s r e g i s t e r S t a c k >>= \ r s −>
case lookup i r s of
Nothing −> t h r o w E r r o r $ "ICE : No r e g i s t e r r e s e r v e d f o r i n d e x " ++ show i
( Just r ) −> return r

68
69
70
71
72
73

getMethodName : : S I d e n t i f i e r −> CodeGenerator MethodName
getMethodName i = g e t s ( symbolTable . s a S t a t e ) >>= \ s t −>
case lookup i s t of
( Just ( Method _ n ) ) −> return n
_ −> t h r o w E r r o r $ "ICE : I n v a l i d method i n d e x " ++ show i

74
75
76
77
78
79

i n s e r t M e t h o d L a b e l : : S I d e n t i f i e r −> CodeGenerator ( )
insertMethodLabel m =
do n <− getMethodName m
i <− g e t s l a b e l I n d e x
modify $ \ s −> s { l a b e l I n d e x = 1 + i , l a b e l T a b l e = (m, " l_ " ++ n ++ "_"
++ show i ) : l a b e l T a b l e s }

80
81
82
83
84
85

getMethodLabel : : S I d e n t i f i e r −> CodeGenerator L a b e l
getMethodLabel m = g e t s l a b e l T a b l e >>= \ l t −>
case lookup m l t of
( Just l ) −> return l
Nothing −> i n s e r t M e t h o d L a b e l m >> getMethodLabel m

86
87
88
89
90
91

g e t U n i q u e L a b e l : : L a b e l −> CodeGenerator L a b e l
getUniqueLabel l =
do i <− g e t s l a b e l I n d e x
modify $ \ s −> s { l a b e l I n d e x = 1 + i }
return $ l ++ "_" ++ show i

92
93
94
95
96

97
98
99

l o a d V a r i a b l e A d d r e s s : : S I d e n t i f i e r −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
l o a d V a r i a b l e A d d r e s s n = g e t s ( symbolTable . s a S t a t e ) >>= \ s t −>
case lookup n s t of
( Just ( C l a s s F i e l d _ _ _ o ) ) −> t e m p R e g i s t e r >>= \ r −> return ( r , [ (
Nothing , ADD r r e g i s t e r T h i s ) , ( Nothing , ADDI r $ Immediate o ) ] ,
popTempRegister )
( Just ( L o c a l V a r i a b l e _ _) ) −> l o o k u p R e g i s t e r n >>= \ r −> return ( r , [ ] ,
return ( ) )
( Just ( MethodParameter _ _) ) −> l o o k u p R e g i s t e r n >>= \ r −> return ( r , [ ] ,
return ( ) )
_ −> t h r o w E r r o r $ "ICE : I n v a l i d v a r i a b l e i n d e x " ++ show n

100
101
102
103
104
105

l o a d V a r i a b l e V a l u e : : S I d e n t i f i e r −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
loadVariableValue n =
do ( ra , l a , ua ) <− l o a d V a r i a b l e A d d r e s s n
r v <− t e m p R e g i s t e r
return ( rv , l a ++ [ ( Nothing , EXCH r v r a ) ] , popTempRegister >> ua )

106
107
108
109
110
111
112

cgBinOp : : BinOp −> R e g i s t e r −> R e g i s t e r −> CodeGenerator ( R e g i s t e r , [ ( Maybe
Label , M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
cgBinOp Add r 1 r 2 = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , XOR r t r 1 ) , (
Nothing , ADD r t r 2 ) ] , popTempRegister )
cgBinOp Sub r 1 r 2 = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , XOR r t r 1 ) , (
Nothing , SUB r t r 2 ) ] , popTempRegister )
cgBinOp Xor r 1 r 2 = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , XOR r t r 1 ) , (
Nothing , XOR r t r 2 ) ] , popTempRegister )
cgBinOp BitAnd r 1 r 2 = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , ANDX r t r 1
r 2 ) ] , popTempRegister )
cgBinOp BitOr r 1 r 2 = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , ORX r t r 1 r 2
) ] , popTempRegister )

Appendix A Rooplc Source Code

92 of 111

113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

cgBinOp Lt r 1 r 2 =
do r t <− t e m p R e g i s t e r
r c <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Nothing , XOR r t r 1 ) ,
( Nothing , SUB r t r 2 ) ,
( Just l_top , BGEZ r t l_bot ) ,
( Nothing , XORI r c $ Immediate 1 ) ,
( Just l_bot , BGEZ r t l_top ) ]
return ( rc , cmp , popTempRegister >> popTempRegister )
cgBinOp Gt r 1 r 2 =
do r t <− t e m p R e g i s t e r
r c <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Nothing , XOR r t r 1 ) ,
( Nothing , SUB r t r 2 ) ,
( Just l_top , BLEZ r t l_bot ) ,
( Nothing , XORI r c $ Immediate 1 ) ,
( Just l_bot , BLEZ r t l_top ) ]
return ( rc , cmp , popTempRegister >> popTempRegister )
cgBinOp Eq r 1 r 2 =
do r t <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Just l_top , BNE r 1 r 2 l_bot ) ,
( Nothing , XORI r t $ Immediate 1 ) ,
( Just l_bot , BNE r 1 r 2 l_top ) ]
return ( r t , cmp , popTempRegister )
cgBinOp Neq r 1 r 2 =
do r t <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Just l_top , BEQ r 1 r 2 l_bot ) ,
( Nothing , XORI r t $ Immediate 1 ) ,
( Just l_bot , BEQ r 1 r 2 l_top ) ]
return ( r t , cmp , popTempRegister )
cgBinOp Lte r 1 r 2 =
do r t <− t e m p R e g i s t e r
r c <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Nothing , XOR r t r 1 ) ,
( Nothing , SUB r t r 2 ) ,
( Just l_top , BGTZ r t l_bot ) ,
( Nothing , XORI r c $ Immediate 1 ) ,
( Just l_bot , BGTZ r t l_top ) ]
return ( rc , cmp , popTempRegister >> popTempRegister )
cgBinOp Gte r 1 r 2 =
do r t <− t e m p R e g i s t e r
r c <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l "cmp_top"
l_bot <− g e t U n i q u e L a b e l "cmp_bot"
l e t cmp = [ ( Nothing , XOR r t r 1 ) ,
( Nothing , SUB r t r 2 ) ,
( Just l_top , BLTZ r t l_bot ) ,
( Nothing , XORI r c $ Immediate 1 ) ,
( Just l_bot , BLTZ r t l_top ) ]
return ( rc , cmp , popTempRegister >> popTempRegister )
cgBinOp _ _ _ = t h r o w E r r o r "ICE : Binary o p e r a t o r not implemented "

174
175
176
177

c g E x p r e s s i o n : : S E x p r e s s i o n −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
c g E x p r e s s i o n ( Constant 0 ) = return ( r e g i s t e r Z e r o , [ ] , return ( ) )
c g E x p r e s s i o n ( Constant n ) = t e m p R e g i s t e r >>= \ r t −> return ( r t , [ ( Nothing , XORI

Appendix A Rooplc Source Code

93 of 111

178
179
180
181
182
183
184

r t $ Immediate n ) ] , popTempRegister )
cgExpression ( Variable i ) = loadVariableValue i
c g E x p r e s s i o n N i l = return ( r e g i s t e r Z e r o , [ ] , return ( ) )
c g E x p r e s s i o n ( Binary op e1 e2 ) =
do ( r1 , l 1 , u1 ) <− c g E x p r e s s i o n e1
( r2 , l 2 , u2 ) <− c g E x p r e s s i o n e2
( ro , l o , uo ) <− cgBinOp op r 1 r 2
return ( ro , l 1 ++ l 2 ++ l o , uo >> u2 >> u1 )

185
186
187
188
189
190
191
192
193
194
195

c g B i n a r y E x p r e s s i o n : : S E x p r e s s i o n −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
cgBinaryExpression e =
do ( re , l e , ue ) <− c g E x p r e s s i o n e
r t <− t e m p R e g i s t e r
l_top <− g e t U n i q u e L a b e l " f_top "
l_bot <− g e t U n i q u e L a b e l " f_bot "
l e t f l a t t e n = [ ( Just l_top , BEQ r e r e g i s t e r Z e r o l_bot ) ,
( Nothing , XORI r t $ Immediate 1 ) ,
( Just l_bot , BEQ r e r e g i s t e r Z e r o l_top ) ]
return ( r t , l e ++ f l a t t e n , popTempRegister >> ue )

196
197
198
199
200
201
202
203
204
205

c g A s s i g n : : S I d e n t i f i e r −> ModOp −> S E x p r e s s i o n −> CodeGenerator [ ( Maybe Label ,
MInstruction ) ]
c g A s s i g n n modop e =
do ( r t , l t , ut ) <− l o a d V a r i a b l e V a l u e n
( re , l e , ue ) <− c g E x p r e s s i o n e
ue >> ut
return $ l t ++ l e ++ [ ( Nothing , cgModOp modop r t r e ) ] ++
i n v e r t I n s t r u c t i o n s ( l t ++ l e )
where cgModOp ModAdd = ADD
cgModOp ModSub = SUB
cgModOp ModXor = XOR

206
207
208
209
210
211
212
213
214
215

loadForSwap : : S I d e n t i f i e r −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
loadForSwap n = g e t s ( symbolTable . s a S t a t e ) >>= \ s t −>
case lookup n s t of
( Just C l a s s F i e l d { } ) −> l o a d V a r i a b l e V a l u e n
( Just ( L o c a l V a r i a b l e I n t e g e r T y p e _) ) −> l o a d V a r i a b l e V a l u e n
( Just ( L o c a l V a r i a b l e ( ObjectType _) _) ) −> l o a d V a r i a b l e A d d r e s s n
( Just ( MethodParameter I n t e g e r T y p e _) ) −> l o a d V a r i a b l e V a l u e n
( Just ( MethodParameter ( ObjectType _) _) ) −> l o a d V a r i a b l e A d d r e s s n
_ −> t h r o w E r r o r $ "ICE : I n v a l i d v a r i a b l e i n d e x " ++ show n

216
217
218
219
220
221
222
223

cgSwap : : S I d e n t i f i e r −> S I d e n t i f i e r −> CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n
)]
cgSwap n1 n2 = i f n1 == n2 then return [ ] e l s e
do ( r1 , l 1 , u1 ) <− loadForSwap n1
( r2 , l 2 , u2 ) <− loadForSwap n2
u2 >> u1
l e t swap = [ ( Nothing , XOR r 1 r 2 ) , ( Nothing , XOR r 2 r 1 ) , ( Nothing , XOR r 1
r2 ) ]
return $ l 1 ++ l 2 ++ swap ++ i n v e r t I n s t r u c t i o n s ( l 1 ++ l 2 )

224
225
226
227
228
229
230
231
232
233
234
235

c g C o n d i t i o n a l : : S E x p r e s s i o n −> [ SStatement ] −> [ SStatement ] −> S E x p r e s s i o n −>
CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
c g C o n d i t i o n a l e1 s 1 s 2 e2 =
do l _ t e s t <− g e t U n i q u e L a b e l " t e s t "
l _ a s s e r t _ t <− g e t U n i q u e L a b e l " a s s e r t _ t r u e "
l _ t e s t _ f <− g e t U n i q u e L a b e l " t e s t _ f a l s e "
l _ a s s e r t <− g e t U n i q u e L a b e l " a s s e r t "
r t <− t e m p R e g i s t e r
( re1 , l e 1 , ue1 ) <− c g B i n a r y E x p r e s s i o n e1
ue1
s1 ’ <− concat <$> mapM c g S t a t e m e n t s 1
s2 ’ <− concat <$> mapM c g S t a t e m e n t s 2

Appendix A Rooplc Source Code

94 of 111

236
237
238
239
240
241
242

( re2 , l e 2 , ue2 ) <− c g B i n a r y E x p r e s s i o n e2
ue2 >> popTempRegister −−r t
return $ l e 1 ++ [ ( Nothing , XOR r t r e 1 ) ] ++ i n v e r t I n s t r u c t i o n s l e 1 ++
[ ( Just l _ t e s t , BEQ r t r e g i s t e r Z e r o l _ t e s t _ f ) , ( Nothing , XORI r t $
Immediate 1 ) ] ++
s1 ’ ++ [ ( Nothing , XORI r t $ Immediate 1 ) , ( Just l _ a s s e r t _ t , BRA
l _ a s s e r t ) , ( Just l _ t e s t _ f , BRA l _ t e s t ) ] ++
s2 ’ ++ [ ( Just l _ a s s e r t , BNE r t r e g i s t e r Z e r o l _ a s s e r t _ t ) ] ++
l e 2 ++ [ ( Nothing , XOR r t r e 2 ) ] ++ i n v e r t I n s t r u c t i o n s l e 2

243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261

cgLoop : : S E x p r e s s i o n −> [ SStatement ] −> [ SStatement ] −> S E x p r e s s i o n −>
CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
cgLoop e1 s 1 s 2 e2 =
do l _ e n t r y <− g e t U n i q u e L a b e l " e n t r y "
l _ t e s t <− g e t U n i q u e L a b e l " t e s t "
l _ a s s e r t <− g e t U n i q u e L a b e l " a s s e r t "
l _ e x i t <− g e t U n i q u e L a b e l " e x i t "
r t <− t e m p R e g i s t e r
( re1 , l e 1 , ue1 ) <− c g B i n a r y E x p r e s s i o n e1
ue1
s1 ’ <− concat <$> mapM c g S t a t e m e n t s 1
s2 ’ <− concat <$> mapM c g S t a t e m e n t s 2
( re2 , l e 2 , ue2 ) <− c g B i n a r y E x p r e s s i o n e2
ue2 >> popTempRegister −−r t
return $ [ ( Nothing , XORI r t $ Immediate 1 ) , ( Just l_entry , BEQ r t
r e g i s t e r Z e r o l _ a s s e r t ) ] ++
l e 1 ++ [ ( Nothing , XOR r t r e 1 ) ] ++ i n v e r t I n s t r u c t i o n s l e 1 ++
s1 ’ ++ l e 2 ++ [ ( Nothing , XOR r t r e 2 ) ] ++ i n v e r t I n s t r u c t i o n s l e 2
++
[ ( Just l _ t e s t , BNE r t r e g i s t e r Z e r o l _ e x i t ) ] ++ s2 ’ ++
[ ( Just l _ a s s e r t , BRA l _ e n t r y ) , ( Just l _ e x i t , BRA l _ t e s t ) , (
Nothing , XORI r t $ Immediate 1 ) ]

262
263
264
265
266
267
268
269
270
271
272
273
274

c g O b j e c t B l o c k : : TypeName −> S I d e n t i f i e r −> [ SStatement ] −> CodeGenerator [ ( Maybe
Label , M I n s t r u c t i o n ) ]
c g O b j e c t B l o c k tp n stmt =
do rn <− p u s h R e g i s t e r n
r v <− t e m p R e g i s t e r
popTempRegister −−r v
stmt ’ <− concat <$> mapM c g S t a t e m e n t stmt
p o p R e g i s t e r −−rn
l e t c r e a t e = [ ( Nothing , XOR rn r e g i s t e r S P ) ,
( Nothing , XORI r v $ AddressMacro $ " l_ " ++ tp ++ "_vt" ) ,
( Nothing , EXCH r v r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ SizeMacro tp ) ]
return $ c r e a t e ++ stmt ’ ++ i n v e r t I n s t r u c t i o n s c r e a t e

275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292

c g L o c a l B l o c k : : S I d e n t i f i e r −> S E x p r e s s i o n −> [ SStatement ] −> S E x p r e s s i o n −>
CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
c g L o c a l B l o c k n e1 stmt e2 =
do rn <− p u s h R e g i s t e r n
( re1 , l e 1 , ue1 ) <− c g E x p r e s s i o n e1
r t 1 <− t e m p R e g i s t e r
popTempRegister >> ue1
stmt ’ <− concat <$> mapM c g S t a t e m e n t stmt
( re2 , l e 2 , ue2 ) <− c g E x p r e s s i o n e2
r t 2 <− t e m p R e g i s t e r
popTempRegister >> ue2
p o p R e g i s t e r −−rn
l e t c r e a t e r e r t = [ ( Nothing , XOR rn r e g i s t e r S P ) ,
( Nothing , XOR r t r e ) ,
( Nothing , EXCH r t r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ Immediate 1 ) ]
l o a d = l e 1 ++ c r e a t e r e 1 r t 1 ++ i n v e r t I n s t r u c t i o n s l e 1
c l e a r = l e 2 ++ i n v e r t I n s t r u c t i o n s ( c r e a t e r e 2 r t 2 ) ++
invertInstructions le2

Appendix A Rooplc Source Code

95 of 111

293

return $ l o a d ++ stmt ’ ++ c l e a r

294
295
296
297
298
299
300
301
302
303

c g C a l l : : [ S I d e n t i f i e r ] −> [ ( Maybe Label , M I n s t r u c t i o n ) ] −> R e g i s t e r −>
CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
c g C a l l a r g s jump t h i s =
do ( ra , l a , ua ) <− unzip3 <$> mapM l o a d V a r i a b l e A d d r e s s a r g s
sequence_ ua
r s <− g e t s r e g i s t e r S t a c k
l e t r r = ( r e g i s t e r T h i s : map snd r s ) \\ ( t h i s : r a )
s t o r e = concatMap push $ r r ++ r a ++ [ t h i s ]
return $ concat l a ++ s t o r e ++ jump ++ i n v e r t I n s t r u c t i o n s s t o r e ++
i n v e r t I n s t r u c t i o n s ( concat l a )
where push r = [ ( Nothing , EXCH r r e g i s t e r S P ) , ( Nothing , ADDI r e g i s t e r S P $
Immediate 1 ) ]

304
305
306

c g L o c a l C a l l : : S I d e n t i f i e r −> [ S I d e n t i f i e r ] −> CodeGenerator [ ( Maybe Label ,
MInstruction ) ]
c g L o c a l C a l l m a r g s = getMethodLabel m >>= \l_m −> c g C a l l a r g s [ ( Nothing , BRA l_m)
] registerThis

307
308
309

c g L o c a l U n c a l l : : S I d e n t i f i e r −> [ S I d e n t i f i e r ] −> CodeGenerator [ ( Maybe Label ,
MInstruction ) ]
c g L o c a l U n c a l l m a r g s = getMethodLabel m >>= \l_m −> c g C a l l a r g s [ ( Nothing , RBRA
l_m) ] r e g i s t e r T h i s

310
311
312
313
314
315
316
317

getType : : S I d e n t i f i e r −> CodeGenerator TypeName
getType i = g e t s ( symbolTable . s a S t a t e ) >>= \ s t −>
case lookup i s t of
( Just ( L o c a l V a r i a b l e ( ObjectType tp ) _) ) −> return tp
( Just ( C l a s s F i e l d ( ObjectType tp ) _ _ _) ) −> return tp
( Just ( MethodParameter ( ObjectType tp ) _) ) −> return tp
_ −> t h r o w E r r o r $ "ICE : I n v a l i d o b j e c t v a r i a b l e i n d e x " ++ show i

318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333

loadMethodAddress : : ( S I d e n t i f i e r , R e g i s t e r ) −> MethodName −> CodeGenerator (
R e g i s t e r , [ ( Maybe Label , M I n s t r u c t i o n ) ] )
loadMethodAddress ( o , r o ) m =
do r v <− t e m p R e g i s t e r
r t <− t e m p R e g i s t e r
r t g t <− t e m p R e g i s t e r
popTempRegister >> popTempRegister >> popTempRegister
o f f s e t M a c r o <− O f f s e t M a c r o <$> getType o <∗> pure m
l e t l o a d = [ ( Nothing , EXCH r v r o ) ,
( Nothing , ADDI r v o f f s e t M a c r o ) ,
( Nothing , EXCH r t r v ) ,
( Nothing , XOR r t g t r t ) ,
( Nothing , EXCH r t r v ) ,
( Nothing , SUBI r v o f f s e t M a c r o ) ,
( Nothing , EXCH r v r o ) ]
return ( r t g t , l o a d )

334
335
336
337
338
339
340

l o a d F o r C a l l : : S I d e n t i f i e r −> CodeGenerator ( R e g i s t e r , [ ( Maybe Label ,
M I n s t r u c t i o n ) ] , CodeGenerator ( ) )
l o a d F o r C a l l n = g e t s ( symbolTable . s a S t a t e ) >>= \ s t −>
case lookup n s t of
( Just C l a s s F i e l d { } ) −> l o a d V a r i a b l e V a l u e n
( Just _) −> l o a d V a r i a b l e A d d r e s s n
_ −> t h r o w E r r o r $ "ICE : I n v a l i d v a r i a b l e i n d e x " ++ show n

341
342
343
344
345
346
347
348

c g O b j e c t C a l l : : S I d e n t i f i e r −> MethodName −> [ S I d e n t i f i e r ] −> CodeGenerator [ (
Maybe Label , M I n s t r u c t i o n ) ]
cgObjectCall o m args =
do ( ro , l o , uo ) <− l o a d F o r C a l l o
r t <− t e m p R e g i s t e r
( r t g t , l o a d A d d r e s s ) <− loadMethodAddress ( o , r t ) m
l_jmp <− g e t U n i q u e L a b e l "l_jmp"
l e t j p = [ ( Nothing , SUBI r t g t $ AddressMacro l_jmp ) ,

Appendix A Rooplc Source Code

96 of 111

349
350
351
352
353
354
355

( Just l_jmp , SWAPBR r t g t ) ,
( Nothing , NEG r t g t ) ,
( Nothing , ADDI r t g t $ AddressMacro l_jmp ) ]
c a l l <− c g C a l l a r g s j p r t
popTempRegister >> uo
l e t l o a d = l o ++ [ ( Nothing , XOR r t r o ) ] ++ l o a d A d d r e s s ++
invertInstructions lo
return $ l o a d ++ c a l l ++ i n v e r t I n s t r u c t i o n s l o a d

356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374

c g O b j e c t U n c a l l : : S I d e n t i f i e r −> MethodName −> [ S I d e n t i f i e r ] −> CodeGenerator [ (
Maybe Label , M I n s t r u c t i o n ) ]
cgObjectUncall o m args =
do ( ro , l o , uo ) <− l o a d F o r C a l l o
r t <− t e m p R e g i s t e r
( r t g t , l o a d A d d r e s s ) <− loadMethodAddress ( o , r t ) m
l_jmp <− g e t U n i q u e L a b e l "l_jmp"
l_rjmp_top <− g e t U n i q u e L a b e l " l_rjmp_top "
l_rjmp_bot <− g e t U n i q u e L a b e l " l_rjmp_bot "
l e t j p = [ ( Nothing , SUBI r t g t $ AddressMacro l_jmp ) ,
( Just l_rjmp_top , RBRA l_rjmp_bot ) ,
( Just l_jmp , SWAPBR r t g t ) ,
( Nothing , NEG r t g t ) ,
( Just l_rjmp_bot , BRA l_rjmp_top ) ,
( Nothing , ADDI r t g t $ AddressMacro l_jmp ) ]
c a l l <− c g C a l l a r g s j p r t
popTempRegister >> uo
l e t l o a d = l o ++ [ ( Nothing , XOR r t r o ) ] ++ l o a d A d d r e s s ++
invertInstructions lo
return $ l o a d ++ c a l l ++ i n v e r t I n s t r u c t i o n s l o a d

375
376
377
378
379
380
381
382
383
384
385
386
387

cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement
cgStatement

: : SStatement −> CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
( A s s i g n n modop e ) = c g A s s i g n n modop e
( Swap n1 n2 ) = cgSwap n1 n2
( C o n d i t i o n a l e1 s 1 s 2 e2 ) = c g C o n d i t i o n a l e1 s 1 s 2 e2
( Loop e1 s 1 s 2 e2 ) = cgLoop e1 s 1 s 2 e2
( O b j e c t B l o c k tp n stmt ) = c g O b j e c t B l o c k tp n stmt
( L o c a l B l o c k n e1 stmt e2 ) = c g L o c a l B l o c k n e1 stmt e2
( LocalCall m args ) = cgLocalCall m args
( LocalUncall m args ) = cgLocalUncall m args
( ObjectCall o m args ) = cgObjectCall o m args
( ObjectUncall o m args ) = cgObjectUncall o m args
S k i p = return [ ]

388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410

cgMethod : : ( TypeName , S M e t h o d D e c l a r a t i o n ) −> CodeGenerator [ ( Maybe Label ,
MInstruction ) ]
cgMethod (_, GMDecl m ps body ) =
do l <− getMethodLabel m
r s <− addParameters
body ’ <− concat <$> mapM c g S t a t e m e n t body
clearParameters
l e t l t = l ++ "_top"
l b = l ++ "_bot"
mp = [ ( Just l t , BRA l b ) ,
( Nothing , SUBI r e g i s t e r S P $ Immediate 1 ) ,
( Nothing , EXCH r e g i s t e r R O r e g i s t e r S P ) ]
++ concatMap pushParameter r s ++
[ ( Nothing , EXCH r e g i s t e r T h i s r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ Immediate 1 ) ,
( Just l , SWAPBR r e g i s t e r R O ) ,
( Nothing , NEG r e g i s t e r R O ) ,
( Nothing , SUBI r e g i s t e r S P $ Immediate 1 ) ,
( Nothing , EXCH r e g i s t e r T h i s r e g i s t e r S P ) ]
++ i n v e r t I n s t r u c t i o n s (concatMap pushParameter r s ) ++
[ ( Nothing , EXCH r e g i s t e r R O r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ Immediate 1 ) ]
return $ mp ++ body ’ ++ [ ( Just lb , BRA l t ) ]

Appendix A Rooplc Source Code

97 of 111

411
412
413

where addParameters = mapM ( p u s h R e g i s t e r . ( \ ( GDecl _ p ) −> p ) ) ps
c l e a r P a r a m e t e r s = r e p l i c a t e M _ ( length ps ) p o p R e g i s t e r
pushParameter r = [ ( Nothing , EXCH r r e g i s t e r S P ) , ( Nothing , ADDI
r e g i s t e r S P $ Immediate 1 ) ]

414
415
416
417
418
419

c g V i r t u a l T a b l e s : : CodeGenerator [ ( Maybe Label , M I n s t r u c t i o n ) ]
c g V i r t u a l T a b l e s = concat <$> ( g e t s ( v i r t u a l T a b l e s . s a S t a t e ) >>= mapM
vtInstructions )
where v t I n s t r u c t i o n s ( n , ms ) = zip ( v t L a b e l n ) <$> mapM vtData ms
vtData m = DATA . AddressMacro <$> getMethodLabel m
v t L a b e l n = ( Just $ " l_ " ++ n ++ "_vt" ) : repeat Nothing

420
421
422

ge tMa inL abe l : : CodeGenerator L a b e l
ge tMa inL abe l = g e t s ( mainMethod . s a S t a t e ) >>= getMethodLabel

423
424
425
426
427
428

g e t M a i n C l a s s : : CodeGenerator TypeName
g e t M a i n C l a s s = g e t s ( m a i n C l a s s . c a S t a t e . s a S t a t e ) >>= \mc −>
case mc of
( Just tp ) −> return tp
Nothing −> t h r o w E r r o r "ICE : No main method d e f i n e d "

429
430
431
432
433
434
435

g e t F i e l d s : : TypeName −> CodeGenerator [ V a r i a b l e D e c l a r a t i o n ]
g e t F i e l d s tp =
do c s <− g e t s ( c l a s s e s . c a S t a t e . s a S t a t e )
case lookup tp c s of
( Just ( GCDecl _ _ f s _) ) −> return f s
Nothing −> t h r o w E r r o r $ "ICE : Unknown c l a s s " ++ tp

436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453

cgOutput : : TypeName −> CodeGenerator ( [ ( Maybe Label , M I n s t r u c t i o n ) ] , [ ( Maybe
Label , M I n s t r u c t i o n ) ] )
cgOutput tp =
do mfs <− g e t F i e l d s tp
co <− concat <$> mapM cgCopyOutput ( zip [ 1 . . ] $ reverse mfs )
return (map c g S t a t i c mfs , co )
where c g S t a t i c ( GDecl _ n ) = ( Just $ "l_r_" ++ n , DATA $ Immediate 0 )
cgCopyOutput ( o , GDecl _ n ) =
do r t <− t e m p R e g i s t e r
r a <− t e m p R e g i s t e r
popTempRegister >> popTempRegister
l e t copy = [ SUBI r e g i s t e r S P $ Immediate o ,
EXCH r t r e g i s t e r S P ,
XORI r a $ AddressMacro $ "l_r_" ++ n ,
EXCH r t ra ,
XORI r a $ AddressMacro $ "l_r_" ++ n ,
ADDI r e g i s t e r S P $ Immediate o ]
return $ zip ( repeat Nothing ) copy

454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473

cgProgram : : SProgram −> CodeGenerator PISA . MProgram
cgProgram p =
do v t <− c g V i r t u a l T a b l e s
r v <− t e m p R e g i s t e r
popTempRegister
ms <− concat <$> mapM cgMethod p
l_main <− ge tMa inL abe l
mtp <− g e t M a i n C l a s s
( out , co ) <− cgOutput mtp
l e t mvt = " l_ " ++ mtp ++ "_vt"
mn = [ ( Just " s t a r t " , BRA " top " ) ,
( Nothing , START) ,
( Nothing , ADDI r e g i s t e r S P ProgramSize ) ,
( Nothing , XOR r e g i s t e r T h i s r e g i s t e r S P ) ,
( Nothing , XORI r v $ AddressMacro mvt ) ,
( Nothing , EXCH r v r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ SizeMacro mtp ) ,
( Nothing , EXCH r e g i s t e r T h i s r e g i s t e r S P ) ,
( Nothing , ADDI r e g i s t e r S P $ Immediate 1 ) ,

Appendix A Rooplc Source Code

98 of 111

474
475
476
477
478
479
480
481
482
483
484

( Nothing , BRA l_main ) ,
( Nothing , SUBI r e g i s t e r S P $ Immediate 1 ) ,
( Nothing , EXCH r e g i s t e r T h i s r e g i s t e r S P ) ]
++ co ++
[ ( Nothing , SUBI r e g i s t e r S P $ SizeMacro mtp ) ,
( Nothing , EXCH r v r e g i s t e r S P ) ,
( Nothing , XORI r v $ AddressMacro mvt ) ,
( Nothing , XOR r e g i s t e r T h i s r e g i s t e r S P ) ,
( Nothing , SUBI r e g i s t e r S P ProgramSize ) ,
( Just " f i n i s h " , FINISH ) ]
return $ PISA . GProg $ [ ( Just " top " , BRA " s t a r t " ) ] ++ out ++ v t ++ ms ++ mn

485
486
487

generatePISA : : ( SProgram , SAState ) −> Except String ( PISA . MProgram , SAState )
generatePISA ( p , s ) = s e c o n d s a S t a t e <$> runStateT ( runCG $ cgProgram p ) (
initialState s)

Appendix A Rooplc Source Code

99 of 111

A.8
1

MacroExpander.hs

{−# LANGUAGE G e n e r a l i z e d N e w t y p e D e r i v i n g #−}

2
3

module MacroExpander ( expandMacros ) where

4
5
6

import Data .Maybe
import Data . L i s t

7
8
9
10

import C o n t r o l .Monad. Reader
import C o n t r o l .Monad. Except
import C o n t r o l . Arrow

11
12
13

import AST hiding ( Program , GProg , O f f s e t )
import PISA

14
15
16

import S c o p e A n a l y z e r
import C l a s s A n a l y z e r

17
18
19
20

type S i z e = Integer
type Address = Integer
type O f f s e t = Integer

21
22
23
24
25
26
27
28

data MEState =
MEState {
a d d r e s s T a b l e : : [ ( Label , Address ) ] ,
s i z e T a b l e : : [ ( TypeName , S i z e ) ] ,
o f f s e t T a b l e : : [ ( TypeName , [ ( MethodName , O f f s e t ) ] ) ] ,
programSize : : S i z e
} deriving (Show, Eq)

29
30
31

newtype MacroExpander a = MacroExpander { runME : : ReaderT MEState ( Except String
) a }
deriving ( Functor , A p p l i c a t i v e , Monad, MonadReader MEState , MonadError String
)

32
33
34
35
36
37
38

g e t O f f s e t T a b l e : : SAState −> [ ( TypeName , [ ( MethodName , O f f s e t ) ] ) ]
g e t O f f s e t T a b l e s = map ( s e c o n d (map t o O f f s e t ) ) indexedVT
where indexedVT = map ( s e c o n d $ zip [ 0 . . ] ) $ v i r t u a l T a b l e s s
t o O f f s e t ( i , m) = ( getName $ lookup m $ symbolTable s , i )
getName ( Just ( Method _ n ) ) = n
getName _ = error "ICE : I n v a l i d method i n d e x "

39
40
41
42
43
44
45
46
47
48

i n i t i a l S t a t e : : MProgram −> SAState −> MEState
i n i t i a l S t a t e ( GProg p ) s =
MEState {
a d d r e s s T a b l e = mapMaybe t o P a i r $ zip [ 0 . . ] p ,
sizeTable = ( c l a s s S i z e . caState ) s ,
offsetTable = getOffsetTable s ,
p r o g r a m S i z e = genericLength p }
where t o P a i r ( a , ( Just l , _) ) = Just ( l , a )
t o P a i r _ = Nothing

49
50
51
52
53
54

g e t A d d r e s s : : L a b e l −> MacroExpander Address
g e t A d d r e s s l = a s k s a d d r e s s T a b l e >>= \ a t −>
case lookup l a t of
( Just i ) −> return i
Nothing −> t h r o w E r r o r $ "ICE : Unknown l a b e l " ++ l

55
56
57
58
59
60

g e t S i z e : : TypeName −> MacroExpander S i z e
g e t S i z e tn = a s k s s i z e T a b l e >>= \ s t −>
case lookup tn s t of
( Just s ) −> return s
Nothing −> t h r o w E r r o r $ "ICE : Unknown t y p e " ++ tn

61

Appendix A Rooplc Source Code

100 of 111

62
63
64
65
66
67
68

g e t O f f s e t : : TypeName −> MethodName −> MacroExpander O f f s e t
g e t O f f s e t tn mn = a s k s o f f s e t T a b l e >>= \ o t −>
case lookup tn o t of
Nothing −> t h r o w E r r o r $ "ICE : Unknown t y p e " ++ tn
( Just mo) −> case lookup mn mo of
Nothing −> t h r o w E r r o r $ "ICE : Unknown method " ++ mn
( Just o ) −> return o

69
70
71
72
73
74
75

meMacro
meMacro
meMacro
meMacro
meMacro
meMacro

: : Macro −> MacroExpander Integer
( Immediate i ) = return i
( AddressMacro l ) = g e t A d d r e s s l
( SizeMacro tn ) = g e t S i z e tn
( O f f s e t M a c r o tn mn) = g e t O f f s e t tn mn
ProgramSize = a s k s p r o g r a m S i z e

76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction
meInstruction

: : M I n s t r u c t i o n −> MacroExpander I n s t r u c t i o n
(ADD r 1 r 2 ) = return $ ADD r 1 r 2
(ADDI r m) = ADDI r <$> meMacro m
(ANDX r 1 r 2 r 3 ) = return $ ANDX r 1 r 2 r 3
(ANDIX r 1 r 2 m) = ANDIX r 1 r 2 <$> meMacro m
(NORX r 1 r 2 r 3 ) = return $ NORX r 1 r 2 r 3
(NEG r ) = return $ NEG r
(ORX r 1 r 2 r 3 ) = return $ ORX r 1 r 2 r 3
(ORIX r 1 r 2 m) = ORIX r 1 r 2 <$> meMacro m
(RL r m) = RL r <$> meMacro m
(RLV r 1 r 2 ) = return $ RLV r 1 r 2
(RR r m) = RR r <$> meMacro m
(RRV r 1 r 2 ) = return $ RRV r 1 r 2
(SLLX r 1 r 2 m) = SLLX r 1 r 2 <$> meMacro m
(SLLVX r 1 r 2 r 3 ) = return $ SLLVX r 1 r 2 r 3
(SRAX r 1 r 2 m) = SRAX r 1 r 2 <$> meMacro m
(SRAVX r 1 r 2 r 3 ) = return $ SRAVX r 1 r 2 r 3
(SRLX r 1 r 2 m) = SRLX r 1 r 2 <$> meMacro m
(SRLVX r 1 r 2 r 3 ) = return $ SRLVX r 1 r 2 r 3
(SUB r 1 r 2 ) = return $ SUB r 1 r 2
(XOR r 1 r 2 ) = return $ XOR r 1 r 2
(XORI r m) = XORI r <$> meMacro m
(BEQ r 1 r 2 l ) = return $ BEQ r 1 r 2 l
(BGEZ r l ) = return $ BGEZ r l
(BGTZ r l ) = return $ BGTZ r l
(BLEZ r l ) = return $ BLEZ r l
(BLTZ r l ) = return $ BLTZ r l
(BNE r 1 r 2 l ) = return $ BNE r 1 r 2 l
(BRA l ) = return $ BRA l
(EXCH r 1 r 2 ) = return $ EXCH r 1 r 2
(SWAPBR r ) = return $ SWAPBR r
(RBRA l ) = return $ RBRA l
START = return START
FINISH = return FINISH
(DATA m) = DATA <$> meMacro m
( SUBI r m) = SUBI r <$> meMacro m

113
114
115
116

meProgram : : MProgram −> MacroExpander Program
meProgram ( GProg p ) = GProg <$> mapM expandPair p
where expandPair ( l , i ) = ( , ) l <$> m e I n s t r u c t i o n i

117
118
119

expandMacros : : ( MProgram , SAState ) −> Except String Program
expandMacros ( p , s ) = runReaderT (runME $ meProgram p ) $ i n i t i a l S t a t e p s

Appendix A Rooplc Source Code

101 of 111

A.9
1
2

ROOPLC.hs

import C o n t r o l .Monad. Except
import System . IO

3
4
5
6
7
8
9
10

import
import
import
import
import
import
import

Parser
PISA
ClassAnalyzer
ScopeAnalyzer
TypeChecker
CodeGenerator
MacroExpander

11
12

type E r r o r = String

13
14
15
16
17

main : : IO ( )
main =
do i n p u t <− getContents
e i t he r ( hPutStrLn stderr ) ( putStr . showProgram ) ( compileProgram i n p u t )

18
19
20
21
22
23
24
25
26
27

compileProgram : : String −> Either E r r o r Program
compileProgram s =
runExcept $
parseString s
>>= c l a s s A n a l y s i s
>>= s c o p e A n a l y s i s
>>= typeCheck
>>= generatePISA
>>= expandMacros

Appendix A Rooplc Source Code

102 of 111

APPENDIX

B

Example Output

B.1
1
2
3
4

LinkedList.rpl

class Program
int result
int n
Node foo

5
6
7
8
9
10
11
12
13
14
15
16
17

method BuildList(Node head)
if n = 0 then
call head::sum(result)
else
construct Node next
call next::constructor(n, head)
n -= 1
call BuildList(next)
n += 1
uncall next::constructor(n, head)
destruct next
fi n = 0

18
19
20
21
22
23
24
25

method main()
n += 7
construct Node tail
foo <=> tail
call BuildList(tail)
foo <=> tail
destruct tail

26
27
28
29

class Node
int data
Node next

30
31
32
33

method constructor(int d, Node n)
next <=> n
data ^= d

34
35
36
37
38
39
40
41

method sum(int s)
s += data
if next = nil then
skip
else
call next::sum(s)
fi next = nil

Appendix B Example Output

103 of 111

B.2
1
2
3
4
5
6

LinkedList.pal

;; pendulum pal file
top:
l_r_result:
l_r_n:
l_r_foo:
l_Node_vt:

7
8

l_Program_vt:

9
10

l_BuildList_2_top:

11
12
13
14
15
16
17

l_BuildList_2:

18
19
20
21
22
23
24
25
26
27
28

cmp_top_8:

29
30
31

cmp_bot_9:
f_top_10:

32
33

f_bot_11:

34
35

f_bot_11_i:

36
37
38

f_top_10_i:
cmp_bot_9_i:

39
40

cmp_top_8_i:

41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

test_4:

BRA
DATA
DATA
DATA
DATA
DATA
DATA
DATA
BRA
ADDI
EXCH
EXCH
ADDI
EXCH
ADDI
SWAPBR
NEG
ADDI
EXCH
ADDI
EXCH
EXCH
ADDI
ADD
ADDI
EXCH
BNE
XORI
BNE
BEQ
XORI
BEQ
XOR
BEQ
XORI
BEQ
BNE
XORI
BNE
EXCH
ADDI
SUB
BEQ
XORI
XOR
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI

Appendix B Example Output

start
0
0
0
302
338
15
242
l_BuildList_2_bot
$1 -1
$2 $1
$4 $1
$1 1
$3 $1
$1 1
$2
$2
$1 -1
$3 $1
$1 -1
$4 $1
$2 $1
$1 1
$6 $3
$6 2
$7 $6
$7 $0 cmp_bot_9
$8 1
$7 $0 cmp_top_8
$8 $0 f_bot_11
$9 1
$8 $0 f_top_10
$5 $9
$8 $0 f_top_10_i
$9 1
$8 $0 f_bot_11_i
$7 $0 cmp_top_8_i
$8 1
$7 $0 cmp_bot_9_i
$7 $6
$6 -2
$6 $3
$5 $0 test_false_6
$5 1
$6 $4
$7 $6
$7 1
$8 $7
$9 $8
$8 $7
$7 -1
$7 $6
$7 $3
$7 1
$3 $1
$1 1
$4 $1
$1 1
$7 $1
$1 1
$6 $1
$1 1

104 of 111

64
65

l_jmp_12:

66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

assert_true_5:
test_false_6:

89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

l_jmp_13:

ADDI
SWAPBR
NEG
ADDI
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
SUB
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
XOR
XORI
BRA
BRA
XOR
XORI
EXCH
ADDI
XOR
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
ADDI
SWAPBR
NEG
ADDI
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
SUB
EXCH

Appendix B Example Output

$9 -63
$9
$9
$9 63
$1 -1
$6 $1
$1 -1
$7 $1
$1 -1
$4 $1
$1 -1
$3 $1
$7 -1
$7 $3
$7 $6
$7 1
$8 $7
$9 $8
$8 $7
$7 -1
$7 $6
$6 $4
$5 1
assert_7
test_4
$6 $1
$7 4
$7 $1
$1 3
$7 $6
$8 $7
$8 0
$9 $8
$10 $9
$9 $8
$8 0
$8 $7
$8 $3
$8 2
$3 $1
$1 1
$6 $1
$1 1
$8 $1
$1 1
$4 $1
$1 1
$7 $1
$1 1
$10 -112
$10
$10
$10 112
$1 -1
$7 $1
$1 -1
$4 $1
$1 -1
$8 $1
$1 -1
$6 $1
$1 -1
$3 $1
$8 -2
$8 $3
$8 $7

105 of 111

130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190

l_rjmp_top_15:
l_jmp_14:

191
192
193
194
195

l_rjmp_bot_16:

ADDI
EXCH
XOR
EXCH
ADDI
EXCH
XOR
ADD
ADDI
EXCH
XORI
SUB
XORI
EXCH
ADDI
SUB
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
BRA
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
XORI
ADD
XORI
EXCH
ADDI
SUB
XOR
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
ADDI
RBRA
SWAPBR
NEG
BRA
ADDI
ADDI
EXCH

Appendix B Example Output

$8 0
$9 $8
$10 $9
$9 $8
$8 0
$8 $7
$7 $6
$7 $3
$7 2
$8 $7
$9 1
$8 $9
$9 1
$8 $7
$7 -2
$7 $3
$4 $1
$1 1
$6 $1
$1 1
$3 $1
$1 1
l_BuildList_2
$1 -1
$3 $1
$1 -1
$6 $1
$1 -1
$4 $1
$7 $3
$7 2
$8 $7
$9 1
$8 $9
$9 1
$8 $7
$7 -2
$7 $3
$7 $6
$8 $7
$8 0
$9 $8
$10 $9
$9 $8
$8 0
$8 $7
$8 $3
$8 2
$3 $1
$1 1
$6 $1
$1 1
$8 $1
$1 1
$4 $1
$1 1
$7 $1
$1 1
$10 -188
l_rjmp_bot_16
$10
$10
l_rjmp_top_15
$10 188
$1 -1
$7 $1

106 of 111

196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

assert_7:

219
220
221
222

cmp_top_17:

223
224
225

cmp_bot_18:
f_top_19:

226
227

f_bot_20:

228
229

f_bot_20_i:

230
231
232

f_top_19_i:
cmp_bot_18_i:

233
234

cmp_top_17_i:

235
236
237
238
239

l_BuildList_2_bot:
l_main_3_top:

240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261

l_main_3:

ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
SUB
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
XOR
ADDI
EXCH
XORI
XOR
BNE
ADD
ADDI
EXCH
BNE
XORI
BNE
BEQ
XORI
BEQ
XOR
BEQ
XORI
BEQ
BNE
XORI
BNE
EXCH
ADDI
SUB
BRA
BRA
ADDI
EXCH
EXCH
ADDI
SWAPBR
NEG
ADDI
EXCH
EXCH
ADDI
ADD
ADDI
EXCH
XORI
ADD
XORI
EXCH
ADDI
SUB
XOR
XORI
EXCH

Appendix B Example Output

$1 -1
$4 $1
$1 -1
$8 $1
$1 -1
$6 $1
$1 -1
$3 $1
$8 -2
$8 $3
$8 $7
$8 0
$9 $8
$10 $9
$9 $8
$8 0
$8 $7
$7 $6
$1 -3
$7 $1
$7 4
$6 $1
$5 $0 assert_true_5
$6 $3
$6 2
$7 $6
$7 $0 cmp_bot_18
$8 1
$7 $0 cmp_top_17
$8 $0 f_bot_20
$9 1
$8 $0 f_top_19
$5 $9
$8 $0 f_top_19_i
$9 1
$8 $0 f_bot_20_i
$7 $0 cmp_top_17_i
$8 1
$7 $0 cmp_bot_18_i
$7 $6
$6 -2
$6 $3
l_BuildList_2_top
l_main_3_bot
$1 -1
$2 $1
$3 $1
$1 1
$2
$2
$1 -1
$3 $1
$2 $1
$1 1
$4 $3
$4 2
$5 $4
$6 7
$5 $6
$6 7
$5 $4
$4 -2
$4 $3
$4 $1
$5 4
$5 $1

107 of 111

262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295

l_main_3_bot:
l_constructor_0_top:

296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

l_constructor_0:

ADDI
ADD
ADDI
EXCH
XOR
XOR
XOR
EXCH
ADDI
SUB
EXCH
ADDI
EXCH
ADDI
BRA
ADDI
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
XOR
XOR
XOR
EXCH
ADDI
SUB
ADDI
EXCH
XORI
XOR
BRA
BRA
ADDI
EXCH
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
SWAPBR
NEG
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
EXCH
ADDI
ADD
ADDI
EXCH
XOR
XOR
XOR
EXCH
ADDI
SUB
ADD
ADDI
EXCH
EXCH
XOR

Appendix B Example Output

$1 3
$5 $3
$5 3
$6 $5
$6 $4
$4 $6
$6 $4
$6 $5
$5 -3
$5 $3
$4 $1
$1 1
$3 $1
$1 1
l_BuildList_2
$1 -1
$3 $1
$1 -1
$4 $1
$5 $3
$5 3
$6 $5
$6 $4
$4 $6
$6 $4
$6 $5
$5 -3
$5 $3
$1 -3
$5 $1
$5 4
$4 $1
l_main_3_top
l_constructor_0_bot
$1 -1
$2 $1
$4 $1
$1 1
$5 $1
$1 1
$3 $1
$1 1
$2
$2
$1 -1
$3 $1
$1 -1
$5 $1
$1 -1
$4 $1
$2 $1
$1 1
$6 $3
$6 2
$7 $6
$7 $5
$5 $7
$7 $5
$7 $6
$6 -2
$6 $3
$6 $3
$6 1
$7 $6
$8 $4
$7 $8

108 of 111

328
329
330
331
332
333

l_constructor_0_bot:
l_sum_1_top:

334
335
336
337
338
339
340

l_sum_1:

341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360

cmp_top_25:

361
362
363

cmp_bot_26:
f_top_27:

364
365

f_bot_28:

366
367

f_bot_28_i:

368
369
370

f_top_27_i:
cmp_bot_26_i:

371
372

cmp_top_25_i:

373
374
375
376

test_21:

377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393

assert_true_22:
test_false_23:

EXCH
EXCH
ADDI
SUB
BRA
BRA
ADDI
EXCH
EXCH
ADDI
EXCH
ADDI
SWAPBR
NEG
ADDI
EXCH
ADDI
EXCH
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
ADD
EXCH
ADDI
SUB
EXCH
ADD
ADDI
EXCH
BNE
XORI
BNE
BEQ
XORI
BEQ
XOR
BEQ
XORI
BEQ
BNE
XORI
BNE
EXCH
ADDI
SUB
BEQ
XORI
XORI
BRA
BRA
ADD
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
EXCH
ADDI

Appendix B Example Output

$8 $4
$7 $6
$6 -1
$6 $3
l_constructor_0_top
l_sum_1_bot
$1 -1
$2 $1
$4 $1
$1 1
$3 $1
$1 1
$2
$2
$1 -1
$3 $1
$1 -1
$4 $1
$2 $1
$1 1
$5 $4
$6 $3
$6 1
$7 $6
$5 $7
$7 $6
$6 -1
$6 $3
$5 $4
$6 $3
$6 2
$7 $6
$7 $0 cmp_bot_26
$8 1
$7 $0 cmp_top_25
$8 $0 f_bot_28
$9 1
$8 $0 f_top_27
$5 $9
$8 $0 f_top_27_i
$9 1
$8 $0 f_bot_28_i
$7 $0 cmp_top_25_i
$8 1
$7 $0 cmp_bot_26_i
$7 $6
$6 -2
$6 $3
$5 $0 test_false_23
$5 1
$5 1
assert_24
test_21
$6 $3
$6 2
$7 $6
$8 $7
$9 $8
$9 1
$10 $9
$11 $10
$10 $9
$9 -1
$9 $8
$7 $6
$6 -2

109 of 111

394
395
396
397
398
399
400
401
402

l_jmp_29:

403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425

assert_24:

426
427
428
429

cmp_top_30:

430
431
432

cmp_bot_31:
f_top_32:

433
434

f_bot_33:

435
436

f_bot_33_i:

437
438
439

f_top_32_i:
cmp_bot_31_i:

440
441

cmp_top_30_i:

442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459

l_sum_1_bot:
start:

SUB
EXCH
ADDI
EXCH
ADDI
EXCH
ADDI
ADDI
SWAPBR
NEG
ADDI
ADDI
EXCH
ADDI
EXCH
ADDI
EXCH
ADD
ADDI
EXCH
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
EXCH
XOR
EXCH
ADDI
SUB
BNE
ADD
ADDI
EXCH
BNE
XORI
BNE
BEQ
XORI
BEQ
XOR
BEQ
XORI
BEQ
BNE
XORI
BNE
EXCH
ADDI
SUB
BRA
BRA
START
ADDI
XOR
XORI
EXCH
ADDI
EXCH
ADDI
BRA
ADDI
EXCH
ADDI
EXCH

Appendix B Example Output

$6 $3
$3 $1
$1 1
$4 $1
$1 1
$8 $1
$1 1
$11 -400
$11
$11
$11 400
$1 -1
$8 $1
$1 -1
$4 $1
$1 -1
$3 $1
$6 $3
$6 2
$7 $6
$9 $8
$9 1
$10 $9
$11 $10
$10 $9
$9 -1
$9 $8
$8 $7
$7 $6
$6 -2
$6 $3
$5 $0 assert_true_22
$6 $3
$6 2
$7 $6
$7 $0 cmp_bot_31
$8 1
$7 $0 cmp_top_30
$8 $0 f_bot_33
$9 1
$8 $0 f_top_32
$5 $9
$8 $0 f_top_32_i
$9 1
$8 $0 f_bot_33_i
$7 $0 cmp_top_30_i
$8 1
$7 $0 cmp_bot_31_i
$7 $6
$6 -2
$6 $3
l_sum_1_top
top
$1 480
$3 $1
$4 6
$4 $1
$1 4
$3 $1
$1 1
l_main_3
$1 -1
$3 $1
$1 -1
$4 $1

110 of 111

460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481

finish:

XORI
EXCH
XORI
ADDI
ADDI
EXCH
XORI
EXCH
XORI
ADDI
ADDI
EXCH
XORI
EXCH
XORI
ADDI
ADDI
EXCH
XORI
XOR
ADDI
FINISH

Appendix B Example Output

$5
$4
$5
$1
$1
$4
$5
$4
$5
$1
$1
$4
$5
$4
$5
$1
$1
$4
$4
$3
$1

3
$5
3
1
-2
$1
2
$5
2
2
-3
$1
1
$5
1
3
-4
$1
6
$1
-480

111 of 111

