-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathnotes.txt
176 lines (129 loc) · 5.86 KB
/
notes.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
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
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
174
175
--------------------------------------------------------------------------------
Integers, expressions, and variables (int_exp.rkt) [249 lines]
Language S_0:
e ::= n | x | (+ e e) | (- e) | (read) | (let ([x e]) e)
* uniquify
* flatten to C0
atomic a ::= n | x
expr e ::= a | (prim op a ...)
stmt s ::= (assign x e) | (return a)
program p ::= (program (x ...) (s ...))
* instruction selection to x86
--------------------------------------------------------------------------------
Parsing? Racket has "Parser Tools: lex and yacc-style Parsing"
and there's an example of doing S_0 by Dan King
https://gist.github.com/danking/1068185
--------------------------------------------------------------------------------
Register Allocation (register_allocator.rkt) [210 lines]
reserve rax for spill code
-> can use same code as prior to register allocation!
perform a single-pass of register allocation
--------------------------------------------------------------------------------
Conditional control flow, Booleans, and type checking (conditionals.rkt)
[311 lines]
S_1
T ::= Integer | Boolean
e ::= ...
| #t | #f | (if e e e) | (eq? e e) | (and e e) | (or e e) | (not e)
Γ ⊢ e0 : T Γ ⊢ e1 : T
--------------------------
Γ ⊢ (eq? e0 e1) : Bool
--------------------------------------------------------------------------------
Tuples (Racket Vectors) and heap allocation (vectors.rkt) [136 lines]
(too easy?)
(needed to represent closures)
(do we need mutation here, or can that be delayed?)
T ::= Integer | (Vector T_1 ... T_n) | Void
e ::= ...
| (vector e_1 ... e_n) | (vector-ref e e)
| (vector-set! e e e)
Type System
Γ ⊢ e0 : Integer Γ ⊢ e1 : T
-------------------------------------
Γ ⊢ (vector e_1 ... e_n) : (Vector T1 ... Tn)
Γ ⊢ e : (Vector T_1 ... T_n)
---------------------------
Γ ⊢ (vector-ref e i) : T_i
Γ ⊢ e_1 : (Vector T_1 ... T_n) Γ ⊢ e_2 : T_i
--------------------------------------------
Γ ⊢ (vector-set! e_1 i e_2) : Void
--------------------------------------------------------------------------------
S3: Functions (functions.rkt) (top-level functions) [411 lines]
T ::= Integer | Boolean | (Vectorof T) | (T1 ... Tn -> T)
p ::= (program d ... e)
d ::= (define (f [x : T] ...) : T e)
e ::= ...
| (e0 e1 ... en)
Γ,x1 : T1, ..., xn : Tn ⊢ e : T
------------------------------------------------------------------
Γ ⊢ (define (f [x1 : T1] ... [xn : Tn]) : T e) : (T1 ... Tn -> T)
where Γ is the top-level environment obtained by collecting
all of the types for the defines.
Γ ⊢ e0 : (T1 ... Tn -> T) for i ∈ 1..n, Γ ⊢ ei : Ti
---------------------------------------------------------
Γ ⊢ (e0 e1 ... en) : T
--------------------------------------------------------------------------------
Garbage Collection (Copying Collector)
idea:
* Put pointers (GC roots) on a separate stack to differentiate from
non-pointers. At this stage in the compiler, the only heap-allocated
things are vectors. So we're putting vectors (which are pointers) onto
the separate stack.
* We still need to have type information about the objects on the heap
to facilitate recursively exploring them during collection.
Here's a couple options:
1. Create a table for type information, with a unique natural number for
each type, assigned during compilation.
Allocate the table during initialization of the program.
2. Add a bitmask at the front of each vector that indicates
which elements are pointers to the heap and which ones are not.
--------------------------------------------------------------------------------
First-Class Functions (lambda.rkt) [182 lines]
e ::= ...
| (lambda: ([x1 : T1] ... [xn : Tn]) : T e)
| (e e ...)
Γ, x1 : T1, ..., xn : Tn ⊢ e : T
----------------------------------------------------------------
Γ ⊢ (lambda: ([x1 : T1] ... [xn : Tn]) : T e) : (T1 ... Tn -> T)
--------------------------------------------------------------------------------
Type dynamic
T ::= Integer | Boolean | (Vectorof T) | (-> T T ...) | Dyn
G ::= Integer | Boolean | (Vectorof Dyn) | (-> Dyn ... Dyn)
e ::= ...
| (inject e G) | (project e G) | (isa? G e)
Γ ⊢ e : G
----------------------
Γ ⊢ (inject e G) : Dyn
Γ ⊢ e : Dyn
----------------------
Γ ⊢ (project e G) : G
Γ ⊢ e : Dyn
----------------------
Γ ⊢ (is? G e) : Boolean
--------------------------------------------------------------------------------
Dynamic typing
(side project)
e ::= n | x | (+ e e) | (- e) | (let ([x e] ...) e)
| (vector-immutable e ...) | (vector-length e) | (vector-ref e e)
| #t | #f | (if e e e) | (equal? e e) | (and e e) | (or e e) | (not e)
| (lambda (x ...) e) | (e e ...)
--------------------------------------------------------------------------------
Gradual typing
T ::= Integer | Boolean | (Vectorof T) | (-> T T ...) | Dyn
e ::= n | x | (+ e e) | (- e) | (let: ([x : T e] ...) e)
| (vector-immutable e ...) | (vector-length e) | (vector-ref e e)
| #t | #f | (if e e e) | (equal? e e) | (and e e) | (or e e) | (not e)
| (lambda: ([x : T] ...) e) | (e e ...)
| (lambda (x ...) e) | (let ([x e] ...) e)
| (ann e T) | (static e) | (dynamic e)
--------------------------------------------------------------------------------
Lists and mutation
T ::= Integer | Boolean | (Vectorof T) | (-> T T ...) | Dyn | (Listof T)
e ::= ...
| (eq? e e)
| null | (mcons e e) | (mcar e) | (mcdr e) | (set-mcar! e e) |
(set-mcdr! e e)
--------------------------------------------------------------------------------
Parametric Polymorphism (strech goal)
--------------------------------------------------------------------------------
Optimization (Function inlining, constant folding, etc.)