Download No-Longer-Foreign - Microsoft Research
Transcript
place. The encoding of the C type system is provided as a CM library, and ml-nlffigen can be hooked up with CM in such a way that it gets invoked automatically whenever necessary. The resulting system has the following characteristics: • • • • The human programmer sees ML code only. (Some of this ML code will act much like C code, and it is remarkable that ML can be made to do that.) No knowledge of ML’s or C’s low-level representations is required. The types in an ML interface faithfully reflect the types in the original C interface represented by it. If the C interface changes, then these changes will be propagated automatically to the ML side. Any resulting inconsistencies show up as ordinary ML type errors and can be fixed as such. ML aspires to being a “safe” language where, for example, no integer can be mistaken for a pointer. C is not a safe language, so using our interface (which embeds C into ML) makes ML unsafe as well. But since the very act of linking with C code already compromises ML’s safety guarantees, this should not be seen as a problem. In practice, we believe that using our system will be more robust than many of the alternatives because it at least respects and enforces the types of the original C code within its ML clients. 3 Encoding the C type system The encoding of C types in the ML type system is mostly based on the following “folklore” trick: Invariants for values of a given type T are enforced by making this type the representation type of a new abstract n-ary type constructor C (where n > 0) and adding cleverly chosen type constraints on its instantiations. The type arguments of C are called phantom types. 3.1 Array dimensions As an example, let us consider static array dimensions. This is not a toy example but part of the larger picture because we will later need precise size information for all C types to be able to perform pointer arithmetic or array subscript correctly. ML’s built-in array type constructor does not express array size. In contrast, a C compiler will statically distinguish between types (int[3]) and (int[4]). Still, it is not impossible to get the same effect in ML. We define a new type constructor (τ , δ) arr that also includes a dimension component δ, and arrays of different size must instantiate δ differently. Of course, δ must be a type, not a number. Thus, we need a new type for every new dimension value. We should also make sure that no more than one type is used for any dimension value, so we set up an infinite family of types 4