Generating Type-Safe Application-Specific Foreign Interfaces

A foreign interface mechanism is an important feature in most high-level language implementations. Such foreign interface mechanisms provide a Foreign Function Interface (FFI) for the high-level language to call C functions and data marshaling and unmarshaling mechanisms to support conversion between the high-level and C data representations. Often, systems provide tools to automate the generation of foreign interfaces, but these tools typically lock the user into a specific model of interoperability. It is our belief that the policy used to craft the mapping between a high-level language and C should be distinct from the underlying mechanism used to implement the mapping. Furthermore, we believe that the lack of flexibility in specifying the foreign interface policy is a serious weakness in existing foreign interface generation tools. Foreign interfaces should balance the goals of aesthetics and performance. Thus, the foreign interface implementation should be tailored to a particular API. This motivates us to propose a novel approach to the problem of interoperability called application-specific foreign interface generation. We have built a foreign interface generation tool, called FIG (Foreign Interface Generator), that embodies this idea and enables high-level functional languages to interface with C. FIG takes two inputs: raw C header files and a declarative script that allows the user to tailor the resulting foreign interface to his or her application. The C header files are processed into abstract structures by a front-end CKIT tool, and the script sets the policy for the translation. The FIG engine then uses a combination of user-supplied policies from the script and default policies in the FIG basic library to generate glue code for the given C-language header file. This dissertation describes the theoretical basis and the structure of FIG, with a focus on the application-specific approach, the typemap system we propose to address the correctness and safety of the generated interface, and many related topics. We first describe the term rewriting techniques which the FIG engine is based on. Internally, FIG works by rewriting a term representation of a C-language header file to an interface, the mapping policies of which we call typemaps. Then, we introduce a typemap system featuring a cross-language type inference system, the concept of conversions as an intermediate model of foreign interface, and the concept of typemaps. We will discuss the concept of typemaps in detail, looking specifically at their well-formedness---a property on which the generated foreign interface's safety is based. A typemap is a term representation of two types (e.g., a C type and a high-level type) and the marshaling and unmarshaling functions that map between the types. Internally, FIG uses typemap operators to combine simple typemaps into more complicated ones and, thus, synthesize the glue code for the foreign interface. As a final step, typemaps are realized as executable code. Unfortunately, there is a significant possibility that the generated glue code may not correctly map between the C API and the generated high-level language API. In this dissertation, we define a type system for the internals of FIG and prove that it guarantees that generated glue code will not introduce type errors. Specifically, we show that well-formed typemaps produce well-typed code and that the type rules for typemap operators ensure that the well-typedness of typemaps is preserved. The typemap system also raises several special issues that we discuss, such as representations for the memory layouts of low-level types and how to model the object-oriented features...