typer.ml 12.5 KB
Newer Older
1
2
(* I. Transform the abstract syntax of types and patterns into
      the internal form *)
3
4
5
6

open Location
open Ast

7
8
9
10
11
exception Pattern of string
exception NonExhaustive of Types.descr
exception Constraint of Types.descr * Types.descr * string

let raise_loc loc exn = raise (Location (loc,exn))
12
13
14
15

(* Internal representation as a graph (desugar recursive types and regexp),
   to compute freevars, etc... *)

16
type ti = {
17
18
19
20
21
22
23
24
  id : int; 
  mutable loc' : loc;
  mutable fv : string SortedList.t option; 
  mutable descr': descr;
  mutable type_node: Types.node option;
  mutable pat_node: Patterns.node option
} 
and descr =
25
   [ `Alias of string * ti
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
   | `Type of Types.descr
   | `Or of ti * ti
   | `And of ti * ti
   | `Diff of ti * ti
   | `Times of ti * ti
   | `Arrow of ti * ti
   | `Record of Types.label * bool * ti
   | `Capture of Patterns.capture
   | `Constant of Patterns.capture * Types.const
   ]
    


module S = struct type t = string let compare = compare end
module StringMap = Map.Make(S)
module StringSet = Set.Make(S)

let mk' =
  let counter = ref 0 in
  fun () ->
    incr counter;
47
48
49
50
51
52
53
54
    let rec x = { 
      id = !counter; 
      loc' = noloc; 
      fv = None; 
      descr' = `Alias ("__dummy__", x);  
      type_node = None; 
      pat_node = None 
    } in
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
    x

let cons loc d =
  let x = mk' () in
  x.loc' <- loc;
  x.descr' <- d;
  x
    
(* Note:
   Compilation of Regexp is implemented as a ``rewriting'' of
   the parsed syntax, in order to be able to print its result
   (for debugging for instance)
   
   It would be possible (and a little more efficient) to produce
   directly ti nodes.
*)
    
module Regexp = struct
  let memo = Hashtbl.create 51
  let defs = ref []
  let name =
    let c = ref 0 in
    fun () ->
      incr c;
      "#" ^ (string_of_int !c)

  let rec seq_vars accu = function
    | Epsilon | Elem _ -> accu
    | Seq (r1,r2) | Alt (r1,r2) -> seq_vars (seq_vars accu r1) r2
    | Star r | WeakStar r -> seq_vars accu r
    | SeqCapture (v,r) -> seq_vars (StringSet.add v accu) r

  let rec propagate vars = function
    | Epsilon -> `Epsilon
    | Elem x -> `Elem (vars,x)
    | Seq (r1,r2) -> `Seq (propagate vars r1,propagate vars r2)
    | Alt (r1,r2) -> `Alt (propagate vars r1, propagate vars r2)
    | Star r -> `Star (propagate vars r)
    | WeakStar r -> `WeakStar (propagate vars r)
    | SeqCapture (v,x) -> propagate (StringSet.add v vars) x

  let cup r1 r2 = 
    match (r1,r2) with
      | (_, `Empty) -> r1
      | (`Empty, _) -> r2
      | (`Res t1, `Res t2) -> `Res (mk noloc (Or (t1,t2)))

  let rec compile fin e seq : [`Res of Ast.ppat | `Empty] = 
    if List.mem seq e then `Empty
    else 
      let e = seq :: e in
      match seq with
	| [] ->
	    `Res fin
	| `Epsilon :: rest -> 
	    compile fin e rest
	| `Elem (vars,x) :: rest -> 
	    let capt = StringSet.fold
			 (fun v t -> mk noloc (And (t, (mk noloc (Capture v)))))
			 vars x in
	    `Res (mk noloc (Prod (capt, guard_compile fin rest)))
	| `Seq (r1,r2) :: rest -> 
	    compile fin e (r1 :: r2 :: rest)
	| `Alt (r1,r2) :: rest -> 
	    cup (compile fin e (r1::rest)) (compile fin e (r2::rest))
	| `Star r :: rest -> cup (compile fin e (r::seq)) (compile fin e rest) 
	| `WeakStar r :: rest -> cup (compile fin e rest) (compile fin e (r::seq))

  and guard_compile fin seq =
    try Hashtbl.find memo seq 
    with
	Not_found ->
          let n = name () in
	  let v = mk noloc (PatVar n) in
          Hashtbl.add memo seq v;
	  let d = compile fin [] seq in
	  (match d with
	     | `Empty -> assert false
	     | `Res d -> defs := (n,d) :: !defs);
	  v


  let atom_nil = Types.mk_atom "nil"
  let constant_nil v t = 
    mk noloc (And (t, (mk noloc (Constant (v, Types.Atom atom_nil)))))

  let compile regexp queue : ppat =
    let vars = seq_vars StringSet.empty regexp in
    let fin = StringSet.fold constant_nil vars queue in
    let n = guard_compile fin [propagate StringSet.empty regexp] in
    Hashtbl.clear memo;
    let d = !defs in
    defs := [];
    mk noloc (Recurs (n,d))
end

let compile_regexp = Regexp.compile


let rec compile env { loc = loc; descr = d } : ti = 
  match (d : Ast.ppat') with
  | PatVar s -> 
      (try StringMap.find s env
158
159
       with Not_found -> 
	 raise_loc loc (Pattern ("Undefined type variable " ^ s))
160
161
162
163
164
      )
  | Recurs (t, b) ->
      let b = List.map (fun (v,t) -> (v,t,mk' ())) b in
      let env = 
	List.fold_left (fun env (v,t,x) -> StringMap.add v x env) env b in
165
166
167
      List.iter 
	(fun (v,t,x) -> x.loc' <- t.loc; x.descr' <- `Alias (v, compile env t)) 
	b;
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
      compile env t
  | Regexp (r,q) -> compile env (Regexp.compile r q)
  | Internal t -> cons loc (`Type t)
  | Or (t1,t2) -> cons loc (`Or (compile env t1, compile env t2))
  | And (t1,t2) -> cons loc (`And (compile env t1, compile env t2))
  | Diff (t1,t2) -> cons loc (`Diff (compile env t1, compile env t2))
  | Prod (t1,t2) -> cons loc (`Times (compile env t1, compile env t2))
  | Arrow (t1,t2) -> cons loc (`Arrow (compile env t1, compile env t2))
  | Record (l,o,t) -> cons loc (`Record (l,o,compile env t))
  | Constant (x,v) -> cons loc (`Constant (x,v))
  | Capture x -> cons loc (`Capture x)

let rec comp_fv seen s =
  match s.fv with
    | Some l -> l
    | None ->
	let l = 
	  match s.descr' with
186
	    | `Alias (_,x) -> if List.memq s seen then [] else comp_fv (s :: seen) x
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
	    | `Or (s1,s2) 
	    | `And (s1,s2)
	    | `Diff (s1,s2)
	    | `Times (s1,s2)
	    | `Arrow (s1,s2) -> SortedList.cup (comp_fv seen s1) (comp_fv seen s2)
	    | `Record (l,opt,s) -> comp_fv seen s
	    | `Type _ -> []
	    | `Capture x
	    | `Constant (x,_) -> [x]
	in
	if seen = [] then s.fv <- Some l;
	l


let fv = comp_fv []

let rec typ seen s : Types.descr =
  match s.descr' with
205
206
207
208
209
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this type"))
210
211
212
213
214
215
216
217
	else typ (s :: seen) x
    | `Type t -> t
    | `Or (s1,s2) -> Types.cup (typ seen s1) (typ seen s2)
    | `And (s1,s2) ->  Types.cap (typ seen s1) (typ seen s2)
    | `Diff (s1,s2) -> Types.diff (typ seen s1) (typ seen s2)
    | `Times (s1,s2) ->	Types.times (typ_node s1) (typ_node s2)
    | `Arrow (s1,s2) ->	Types.arrow (typ_node s1) (typ_node s2)
    | `Record (l,o,s) -> Types.record l o (typ_node s)
218
    | `Capture _ | `Constant _ -> assert false
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234

and typ_node s : Types.node =
  match s.type_node with
    | Some x -> x
    | None ->
	let x = Types.make () in
	s.type_node <- Some x;
	let t = typ [] s in
	Types.define x t;
	x

let type_node s = Types.internalize (typ_node s)

let rec pat seen s : Patterns.descr =
  if fv s = [] then Patterns.constr (type_node s) else
  match s.descr' with
235
236
237
238
239
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this pattern"))
240
241
242
243
244
245
	else pat (s :: seen) x
    | `Or (s1,s2) -> Patterns.cup (pat seen s1) (pat seen s2)
    | `And (s1,s2) -> Patterns.cap (pat seen s1) (pat seen s2)
    | `Diff (s1,s2) when fv s2 = [] ->
	let s2 = Types.cons (Types.neg (Types.descr (type_node s2)))in
	Patterns.cap (pat seen s1) (Patterns.constr s2)
246
247
    | `Diff _ ->
	raise_loc s.loc' (Pattern "Difference not allowed in patterns")
248
249
    | `Times (s1,s2) -> Patterns.times (pat_node s1) (pat_node s2)
    | `Record (l,false,s) -> Patterns.record l (pat_node s)
250
251
252
    | `Record _ ->
	raise_loc s.loc' 
	  (Pattern "Optional field not allowed in record patterns")
253
254
    | `Capture x ->  Patterns.capture x
    | `Constant (x,c) -> Patterns.constant x c
255
256
257
    | `Arrow _ ->
	raise_loc s.loc' (Pattern "Arrow not allowed in patterns")
    | `Type _ -> assert false
258
259
260
261
262
263
264
265
266
267
268
269
270

and pat_node s : Patterns.node =
  match s.pat_node with
    | Some x -> x
    | None ->
	let x = Patterns.make (fv s) in
	s.pat_node <- Some x;
	let t = pat [] s in
	Patterns.define x t;
	x

let typ e =
  let e = compile StringMap.empty e in
271
272
273
  if fv e = [] then type_node e 
  else (raise_loc e.loc' 
	  (Pattern "Capture variables are not allowed in types"))
274
275
276
277
278
279
280

let pat e =
  let e = compile StringMap.empty e in
  pat_node e



281
282
(* II. Build skeleton *)

283
284
module Fv = StringSet

285
let rec expr { loc = loc; descr = d } = 
286
  let (fv,td) = 
287
    match d with
288
289
290
291
      | Var s -> (Fv.singleton s, Typed.Var s)
      | Apply (e1,e2) -> 
	  let (fv1,e1) = expr e1 and (fv2,e2) = expr e2 in
	  (Fv.union fv1 fv2, Typed.Apply (e1,e2))
292
      | Abstraction a ->
293
294
295
296
	  let iface = List.map (fun (t1,t2) -> (typ t1, typ t2)) a.fun_iface in
	  let t = List.fold_left 
		    (fun accu (t1,t2) -> Types.cap accu (Types.arrow t1 t2)) 
		    Types.any iface in
297
298
299
	  let iface = List.map 
			(fun (t1,t2) -> (Types.descr t1, Types.descr t2)) 
			iface in
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
328
329
330
331
332
333
334
335
336
	  let (fv0,body) = branches a.fun_body in
	  let fv = match a.fun_name with
	    | None -> fv0
	    | Some f -> Fv.remove f fv0 in
	  (fv,
	   Typed.Abstraction 
	     { Typed.fun_name = a.fun_name;
	       Typed.fun_iface = iface;
	       Typed.fun_body = body;
	       Typed.fun_typ = t;
	       Typed.fun_fv = Fv.elements fv0
	     }
	  )
      | Cst c -> (Fv.empty, Typed.Cst c)
      | Pair (e1,e2) ->
	  let (fv1,e1) = expr e1 and (fv2,e2) = expr e2 in
	  (Fv.union fv1 fv2, Typed.Pair (e1,e2))
      | RecordLitt r -> 
	  (* XXX TODO: check that no label appears twice *)
	  let fv = ref Fv.empty in
	  let r = List.map 
		    (fun (l,e) -> 
		       let (fv2,e) = expr e in
		       fv := Fv.union !fv fv2;
		       (l,e)
		    ) r in
	  (!fv, Typed.RecordLitt r)
      | Op (o,e) -> 
	  let (fv,e) = expr e in (fv, Typed.Op (o,e))
      | Match (e,b) -> 
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Match (e, b))
      | Map (e,b) ->
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Map (e, b))
337
  in
338
339
  fv,
  { Typed.exp_loc = loc;
340
341
342
343
    Typed.exp_typ = Types.empty;
    Typed.exp_descr = td;
  }
	      
344
345
346
347
348
349
350
351
352
353
  and branches b = 
    let fv = ref Fv.empty in
    let b = List.map 
	      (fun (p,e) ->
		 let (fv2,e) = expr e in
		 fv := Fv.union !fv fv2;
		 { Typed.br_used = false;
		   Typed.br_pat = pat p;
		   Typed.br_body = e }
	      ) b in
354
    (!fv, { Typed.br_typ = Types.empty; Typed.br_branches = b } )
355
356
357
358
359
360
361
362
363
364
365
366
367
368

module Env = StringMap

open Typed

let rec compute_type env e = 
  let d = compute_type' e.exp_loc env e.exp_descr in
  e.exp_typ <- Types.cup e.exp_typ d;
  d

and compute_type' loc env = function
  | Var s -> Env.find s env
  | Apply (e1,e2) ->
      let t1 = compute_type env e1 and t2 = compute_type env e2 in
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
      if Types.is_empty t2 
      then Types.empty
      else 
	if Types.subtype t1 Types.Arrow.any 
	then
	  let t1 = Types.Arrow.get t1 in
	  let dom = Types.Arrow.domain t1 in
	  if Types.subtype t2 dom
	  then Types.Arrow.apply t1 t2
	  else
	    raise_loc loc 
	      (Constraint 
		 (t2,dom,"The argument is not in the domain of the function"))
	else
	  raise_loc loc
	    (Constraint
	       (t1,Types.Arrow.any,"The expression in function position is not necessarily a function"))
386
387
388
389
390
  | Abstraction a ->
      let env = match a.fun_name with
	| None -> env
	| Some f -> Env.add f a.fun_typ env in
      List.iter (fun (t1,t2) ->
391
392
393
		   let t = type_branches loc env t1 a.fun_body in
		   if not (Types.subtype t t2) then
		     raise_loc loc (Constraint (t,t2,"Constraint not satisfied in interface"))
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
		) a.fun_iface;
      a.fun_typ
  | Cst c -> Types.constant c
  | Pair (e1,e2) -> 
      let t1 = compute_type env e1 and t2 = compute_type env e2 in
      let t1 = Types.cons t1 and t2 = Types.cons t2 in
      Types.times t1 t2
  | RecordLitt r ->
      List.fold_left 
	(fun accu (l,e) ->
	   let t = compute_type env e in
	   let t = Types.record l false (Types.cons t) in
	   Types.cap accu t
	) Types.Record.any r
  | Op (op,e) -> assert false
  | Match (e,b) ->
      let t = compute_type env e in
411
      type_branches loc env t b
412
413
  | Map (e,b) -> assert false

414
and type_branches loc env targ brs =
415
  if Types.is_empty targ then Types.empty 
416
417
418
419
  else (
    brs.br_typ <- Types.cup brs.br_typ targ;
    branches_aux loc env targ Types.empty brs.br_branches
  )
420
    
421
422
and branches_aux loc env targ tres = function
  | [] -> raise_loc loc (NonExhaustive targ)
423
424
425
426
427
428
  | b :: rem ->
      let p = b.br_pat in
      let acc = Types.descr (Patterns.accept p) in

      let targ' = Types.cap targ acc in
      if Types.is_empty targ' 
429
      then branches_aux loc env targ tres rem
430
431
432
433
434
435
436
      else 
	( b.br_used <- true;
	  let res = Patterns.filter targ' p in
	  let env' = List.fold_left 
		       (fun env (x,t) -> Env.add x (Types.descr t) env) 
		       env res in
	  let t = compute_type env' b.br_body in
437
438
439
440
441
442
	  let tres = Types.cup t tres in
	  let targ'' = Types.diff targ acc in
	  if (Types.non_empty targ'') then 
	    branches_aux loc env targ'' (Types.cup t tres) rem 
	  else
	    tres
443
	)