17.2 Subtyping

< Free Open Study >

The pseudocode presentation of the algorithmic subtype relation on page 212 can be translated directly into OCaml as follows.

   let rec subtype tyS tyT =      (=) tyS tyT ||      match (tyS,tyT) with        (TyRecord(fS), TyRecord(fT)) →          List.for_all            (fun (li,tyTi) →               try let tySi = List.assoc li fS in                   subtype tySi tyTi               with Not_found → false)            fT      | (_,TyTop) →          true      | (TyArr(tyS1,tyS2),TyArr(tyT1,tyT2)) →          (subtype tyT1 tyS1) && (subtype tyS2 tyT2)      | (_,_) →          false

We have made one slight change to the algorithm from the pseudocode presentation, adding a reflexivity check at the beginning. (The (=) operator is ordinary equality; it is written in prefix position here because, in some of the other subtyping implementations, it is replaced by a call to a different comparison function. The || operator is a short-circuiting boolean or: if the first branch yields true, the second is never evaluated.) Strictly speaking, this check is not needed. However, it is actually an important optimization in real compilers. In the majority of real-world programs, subtyping is used quite rarely—that is, most times when the subtype checker is called, the two types being compared are actually equal. Moreover, if types are represented so that structurally isomorphic types are guaranteed to have physically identical representations—for example, using hash consing (Goto, 1974; Appel and Gonçalves, 1993) when constructing types—then this check is just one instruction.

The subtyping rule for records naturally involves a certain amount of fussing around with lists. List.for_all applies a predicate (its first argument) to every member of a list and returns true iff all these applications return true. List.assoc li fS looks up the label li in the list of fields fS and returns the associated field type tySi; if li is not among the labels in fS, it raises Not_found, which we catch and convert into a false response.

< Free Open Study >