Appendice C : inferW stile funzionale
(Realizzato da M.Bellia)
/**
*** Algoritmo W di Hindely-Milner [...] adattato a Sigma_x ed espresso nel *** linguaggio funzionale tipo OCAML utilizato in Benjamin Pierce [...] ***
*** To formally introduce the algorithm we give first the structures of the main *** ingredients of the type checker: (a) the abstract syntax of the language
*** terms, (b) atomic types, type constructors and type schemes, (c) environments *** for typing term identifiers, and (d) the substitutions for refining type
*** schemes. ***
*** (a) Abstract syntax. The language terms are constructed according to the *** following algebraic data type definition (Hakell-Caml like):
***
*** data Term = Bool Information Bool_value *** | String Information String_value
*** | ... and so on for the other language primitive values
*** | Var Information Var_name
*** | Update Information Term Sel_name Term *** | Select Information Term Sel_name Actuals *** | Object Information Type_name SelMetPairs *** | Abstract Information Term Term Actuals
*** | Extract Information Term Term Sel_name Actuals *** | Method Information Formals Term
*** | Obj Information SelMetPairs ***
*** with the type expressions below *** type Actuals = [Term]
*** type SelMetPairs = [D(Sel_name,Term)] *** type Formals = [P(Var_name,TypeA)]
*** where Sel_name, Var_name, Type_name are OCAML types for identifiers of selections, *** variables and parameters, and object types, respectively.
***
*** (b) Atomic types and type constructors are defined by the data type TypeA below: ***
*** data TypeA = Void
*** | TyBool
*** | TyString
*** | ... and so on for the other atomic types
*** | TyObject [(Sel_name,Type)]
*** | TyArrow [Type] Type
***
*** The Atomic types include the unknown void.
*** The use of Type scheme extends (and replaces) the definition above with the *** type variables and the overdefined Top as it follows:
***
*** | ... and so on for the other atomic types
*** | TyObject [O(Sel_name,Type)]
*** | TyArrow [Type] Type
*** | Ty Type_var
*** | Top
***
*** (c) Environments are bindings from language identifiers to type schemes. *** As far as the type checking of the program proceeds, the type scheme, *** associated to each identifier, is refined by instantiating the variables *** occurring in it, to the inferred type.
***
*** type Environment = [(Identifier,TypeB)] ***
*** (d) Substitutions are bindings from type variables to type schemes. They make *** identical two (or more) distinct type schemes. Hence, substitutions are *** introduced according to the following definition:
***
*** type Substitution = [(Type_var,TypeB)] ***
*** **/
inferW:: Environment x Term --> Substitution x Type inferW ctx t = match t with (1) Bool(fi,v) --> ([], TyBool) | String(fi,s) --> ([], TyString) ... (2) | Var(fi,i) --> ([], getTypeFromCxt fi ctx i) | Update(fi,a,l,m) -->
let (Sa,Ta) = inferW cxt a in (3) let (Sm,Tm) = inferW Sa(cxt) m in (4) if (isTyArrow Tm)
then let A = Class Tm in
(5) if (A == Sm(Ta)) and (isTyObject A) then let Tm' = getTypeFromObj fi A l in
if (Tm == Tm') then (Sa.Sm, A) // just same type (6) else error fi "error selection clashes"
else error fi "update in non object term" else error fi "update with no method"
| Select(fi,a,l,pl) -->
let (Sa,Ta) = inferW cxt a in if (isTyObject Ta)
then let Tm = getTypeFromObj fi Ta l in // method type (7) let(Spl,Tpl) = unzip (map (\p.inferW Sa(cxt) p) pl) in // propagation on "pl" of the constraints on "a". let Sn = fold (\sub s. (sub.s)) Sa Spl // substitutions composition (8) let newX = newTypeVar() in // unconstrained new variable let T' = TyArr(Ta:Tpl,newX) in // for the method range,
(9) let Sf = Sn.mgu(Tm,Sn(T')) in // collect constraints on parameters
(Sf, Sf(newX))
else error fi "selection in non object term" | Object(fi,A,ls) -->
let parTypes = \(l m).(match m with
Method(fi,fl,by) --> (l,(normalize fi fl))
| _ --> top // ready for other extentions let (lY,list) = unzip (map partypes ls) in
let S = fold (\r ts. r.mgu(A,(Class ts)) [] list // unicity of the self type. if (S = top) then error fi "type mismatch in class self"
else
let objT = zip lY S(list) in let lstype = TyObject(objT) in let ctx' = addBinding cxt A lstype in
let cxt" = fold (\cxt O(l,ltype).addBinding cxt l ltype) cxt' objT in
let byType = // context is extended to complete analysis
\sub D(l,E(fi,fl,by)).
let Ts = getTypeFromCxt fi ctx" l in
let (Mpl,Tpl) = unzip fl in
let fl* = zip Mpl (Dom Ts) in
let cxt* = fold (\cxt P(x,type).addBinding cxt x type) sub(cxt") fl* in
let (S,T) = inferW cxt* by in
sub.S.mgu((Range Ts),T) in // substitutions composition let Sf = fold byType S ls in
(Sf,Sf(lstype)) | Abstract(fi,a,m,pl) -->
let (Sb,Tr) = inferW cxt m in let (Sa,Ta) = inferW cxt Sb(a) in
let (Sub,bool) = lessThan(Sb.Sa(cxt),Ta,Sa(Class tr))
// it uses subtype relation in checking types that satisfy the structure if (not bool) then error fi "method cannot apply in abstraction" else
let (Spl,Tpl) = unzip (map (\p.inferW Sb.Sa(cxt) p) pl) // propaga vincoli sul tipo di "a" ai tipi di "pl".
let Sn = fold (\sub s. (sub.s)) Sb.Sa Spl // substitutions composition let newX = newTypeVar() in
let T' = TyArr(Ta:Tpl,newX) in // new variable for inferring the range type let Sf = mgu(Sn(Tr),T') in // it collects constraints on parameters (Sf,Sf(newX))
| Extract(fi,a,o,l,pl) -->
let (So,To) = inferW cxt o in let (Sa,Ta) = inferW So(cxt) a in
if (not(isTypeObject To)) or (not(isTypeObject Ta)) then error fi "non object in selection"
else
let (Sub,bool) = lessThan(So.Sa(cxt),Ta,Sa(To)) in // subsumption if (not bool) then error fi "method cannot apply in abstraction" else let Tr = getTypeFromObj fi To l in // method type let (Spl,Tpl) = unzip (map (\p.inferW Sb.Sa(cxt) p) pl)
let newX = newTypeVar() in let T' = TyArr(Sa(To):Tpl,newX) in
let Sf = mgu(Sn(Tr),T') in // it collects constraints on types (Sf,Sf(newX))
| method(fi,fl,by) -->
let (Tv->A) = normalize fl in // complete signature of the method let parList = zip tv ((2.unzip) fl) // list of (name,type)_parameters. // 2 select second component in pairs
let cxt* = fold (\cxt P(x,type).addBinding cxt x type) cxt parList in let (Sb,T) = inferW cxt* by in
let S = Sb.mgu(A,T) in
// usefull with polymorhic types: A may be also a non variable type (S,S(Tv->A))
| Object(fi,ls) -->
let A = newIdeType in inferW cxt Object(fi,A,ls) | _ ? error fi "term expected"
Note:
(1) [ ]: utilizzato, secondo i casi, come lista vuota o sostituzione identità. (2) getTypeFromObj:: Information x TyObject x Sel_name --> TypeB Ad esempio, (getTypeFromObj fi A l) è il tipo del metodo associato ad l in A, if any. In caso contrario, vale top (segnala error fi "selection not found"). Similmente,
getTypeFromCxt:: Information x Environment x Identifier --> TypeB addBinding:: Environment Identifier TypeB --> Environment
(3) Sa(cxt), Sn(pl): applicazione della sostituzione Sa a tutti i tipi (schemi di tipo) legati agli identificatori tipati in cxt. Similmente per una lista pl. p.q: composizione di sostituzioni nel modo usuale.
Tm==tm': impone che valore (i.e. metodo) associato ad un selettore di un oggetto mantenga il tipo attribuito al selettore quando l'oggetto è stato definito (introdotto). (4) isTyObject A: predicato vero se A è un tipo object_type.
isTyArrow m: predicato vero se m è un tipo metodo. Range TyArr(pl,T) = T tipo del rango
Dom TyArr(pl,T) = pl lista tipi
Class TyArr((P(x,A)|L),T) = A tipo del self del metodo.
(5) sui tipi è definita una relazione == come usuale uguaglianza strutturale con caso particolare: (top == top) è false.
(6) error:: Information x MessageString --> TypeB It throws an exception and return type Top.
: :: a x [a] --> [a] usuale cons. ++ :: [a] x [a] --> [a] usuale append
fold:: (a -> b -> a) -> a -> [b] -> a è il left-folding: fold f r [] = r
fold f r [x:xs] = fold f (f r x) xs map:: (a -> b) -> [a] -> [b] la solita map unzip:: [(a,b)] -> ([a],[b]) la solita unzip
(8) newTypeVar(): introduce una nuova variabile di tipo, ovvero Ty Type_var. (9) mgu: most general unifier
normalize: Information -> [(Var-name,TypeA)] -> TypeB
normalizza segnature nelle quali parte (o la totalit ) dei formali non hanno tipo esplicito.
Un'implementazione è la seguente: normalize fi fl =
let tv = normalizeArg fi fl in
let newX = newTypeVar in // una variabile di tipo per il range TyArr(tv,newX) // tipo dell'astratto
where normalizeArg fi FL =
match fl with
[(_,Void):Rt] --> let t = newTypeVar in // variabile di tipo let Lt = normalizeArg Rt in
t:Lt
| [(_,type):Rt] --> let t = type // tipo
let Lt = normalizeArg Rt in
t:Lt | [] --> []
