To keep sharing, every instance of a node will be kept in a table, and the
mark of the old node will be equal (modulo a translation) to the index of
the corresponding node in the table. Since we do not know at the beginning
the size of the table. we write a library of extensible arrays.
| | |
| module Iarray =
struct
type 'a t = { mutable t : 'a array; v : 'a }
let create k v = { t = Array.create (max k 3) v; v = v }
let get a i =
if Array.length a.t > i then a.t.(i) else a.v
let set a i v =
let n = Array.length a.t in
if n > i then a.t.(i) <- v else
begin
let t = Array.create (2 * n) a.v in
Array.blit a.t 0 t 0 n;
a.t <- t;
t.(i) <- v;
end
end;; |
|
Now, we can define the instance function. The polymorphic variables are
created first. Then, when we meet variables that have not been created, we
know that they should be shared rather than duplicated.
| | |
| let type_instance (q, t) =
let table = Iarray.create 7 (tvar()) in
let poly = marker() in
let copy_var t =
let t' = tvar() in let p = marker() in
t.mark <- p; Iarray.set table (p - poly) t'; t' in
let q' = List.map copy_var q in
let rec visit t =
let t = repr t in
if t.mark > poly then Iarray.get table (t.mark -poly)
else
begin match desc t with
| Tvar _ | Tcon (_, []) -> t
| Tcon (g, l) ->
let t' = copy_var t in
t'.texp <- Desc (Tcon (g, List.map visit l)); t'
end in
visit t;; |
|