-
Notifications
You must be signed in to change notification settings - Fork 81
/
ast.lem
243 lines (217 loc) · 5.28 KB
/
ast.lem
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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
open import Pervasives
open import Lib
(* Literal constants *)
type lit =
| IntLit of integer
| Char of char
| StrLit of string
| Word8 of word8
| Word64 of word64
(* Built-in binary operations *)
type opn = Plus | Minus | Times | Divide | Modulo
type opb = Lt | Gt | Leq | Geq
type opw = Andw | Orw | Xor | Add | Sub
type shift = Lsl | Lsr | Asr
(* Module names *)
type modN = string
(* Identifiers *)
type id 'a =
| Short of 'a
| Long of modN * 'a
(* Variable names *)
type varN = string
(* Constructor names (from datatype definitions) *)
type conN = string
(* Type names *)
type typeN = string
(* Type variable names *)
type tvarN = string
val mk_id : forall 'a. maybe modN -> 'a -> id 'a
let mk_id mn_opt n =
match mn_opt with
| Nothing -> Short n
| Just mn -> Long mn n
end
val id_to_n : forall 'a. id 'a -> 'a
let id_to_n id =
match id with
| Short n -> n
| Long _ n -> n
end
type word_size = W8 | W64
type op =
(* Operations on integers *)
| Opn of opn
| Opb of opb
(* Operations on words *)
| Opw of word_size * opw
| Shift of word_size * shift * nat
| Equality
(* Function application *)
| Opapp
(* Reference operations *)
| Opassign
| Opref
| Opderef
(* Word8Array operations *)
| Aw8alloc
| Aw8sub
| Aw8length
| Aw8update
(* Word/integer conversions *)
| WordFromInt of word_size
| WordToInt of word_size
(* Char operations *)
| Ord
| Chr
| Chopb of opb
(* String operations *)
| Implode
| Strsub
| Strlen
(* Vector operations *)
| VfromList
| Vsub
| Vlength
(* Array operations *)
| Aalloc
| Asub
| Alength
| Aupdate
(* Call a given foreign function *)
| FFI of string
(* Logical operations *)
type lop =
| And
| Or
(* Type constructors.
* 0-ary type applications represent unparameterised types (e.g., num or string)
*)
type tctor =
(* User defined types *)
| TC_name of id typeN
(* Built-in types *)
| TC_int
| TC_char
| TC_string
| TC_ref
| TC_word8
| TC_word64
| TC_word8array
| TC_fn
| TC_tup
| TC_exn
| TC_vector
| TC_array
(* Types *)
type t =
(* Type variables that the user writes down ('a, 'b, etc.) *)
| Tvar of tvarN
(* deBruijn indexed type variables.
The type system uses these internally. *)
| Tvar_db of nat
| Tapp of list t * tctor
(* Some abbreviations *)
let Tint = Tapp [] TC_int
let Tchar = Tapp [] TC_char
let Tstring = Tapp [] TC_string
let Tref t = Tapp [t] TC_ref
let rec TC_word W8 = TC_word8
and TC_word W64 = TC_word64
let Tword wz = Tapp [] (TC_word wz)
let Tword8 = Tword W8
let Tword64 = Tword W64
let Tword8array = Tapp [] TC_word8array
let Tfn t1 t2 = Tapp [t1;t2] TC_fn
let Texn = Tapp [] TC_exn
(* Patterns *)
type pat =
| Pvar of varN
| Plit of lit
(* Constructor applications.
A Nothing constructor indicates a tuple pattern. *)
| Pcon of maybe (id conN) * list pat
| Pref of pat
| Ptannot of pat * t
(* Expressions *)
type exp =
| Raise of exp
| Handle of exp * list (pat * exp)
| Lit of lit
(* Constructor application.
A Nothing constructor indicates a tuple pattern. *)
| Con of maybe (id conN) * list exp
| Var of id varN
| Fun of varN * exp
(* Application of a primitive operator to arguments.
Includes function application. *)
| App of op * list exp
(* Logical operations (and, or) *)
| Log of lop * exp * exp
| If of exp * exp * exp
(* Pattern matching *)
| Mat of exp * list (pat * exp)
(* A let expression
A Nothing value for the binding indicates that this is a
sequencing expression, that is: (e1; e2). *)
| Let of maybe varN * exp * exp
(* Local definition of (potentially) mutually recursive
functions.
The first varN is the function's name, and the second varN
is its parameter. *)
| Letrec of list (varN * varN * exp) * exp
| Tannot of exp * t
type type_def = list (list tvarN * typeN * list (conN * list t))
(* Declarations *)
type dec =
(* Top-level bindings
* The pattern allows several names to be bound at once *)
| Dlet of pat * exp
(* Mutually recursive function definition *)
| Dletrec of list (varN * varN * exp)
(* Type definition
Defines several data types, each of which has several
named variants, which can in turn have several arguments.
*)
| Dtype of type_def
(* Type abbreviations *)
| Dtabbrev of list tvarN * typeN * t
(* New exceptions *)
| Dexn of conN * list t
type decs = list dec
(* Specifications
For giving the signature of a module *)
type spec =
| Sval of varN * t
| Stype of type_def
| Stabbrev of list tvarN * typeN * t
| Stype_opq of list tvarN * typeN
| Sexn of conN * list t
type specs = list spec
type top =
| Tmod of modN * maybe specs * decs
| Tdec of dec
type prog = list top
(* Accumulates the bindings of a pattern *)
val pat_bindings : pat -> list varN -> list varN
let rec
pat_bindings (Pvar n) already_bound =
n::already_bound
and
pat_bindings (Plit l) already_bound =
already_bound
and
pat_bindings (Pcon _ ps) already_bound =
pats_bindings ps already_bound
and
pat_bindings (Pref p) already_bound =
pat_bindings p already_bound
and
pat_bindings (Ptannot p _) already_bound =
pat_bindings p already_bound
and
pats_bindings [] already_bound =
already_bound
and
pats_bindings (p::ps) already_bound =
pats_bindings ps (pat_bindings p already_bound)