A type inference algorithm and transition semantics for polymorphic C
By:  Mustafa Ozgen
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1996
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 113
Description: In an attempt to bring the ML-style type inference to the C programming language, Smith and Volpano developed a type system for a dialect of C, called PolyC SmV96a SmV95b. PolyC extends C with ML-style polymorphism and a limited form of higher-order function. Smith and Volpano proved a type soundness theorem that basically says that evaluation of a well-typed PolyC program cannot fail due to a type mismatch. The type soundness proof is based on an operational characterization of a special kind of semantic formulation called a natural semantics. This thesis presents an alternative semantic formulation, called a transition semantics, that could be used in place of the natural semantics to prove type soundness. The primary advantage of the transition semantics is that it eliminates the extra operational level, but the disadvantage is that it consists of many more evaluation rules than the natural semantics. Thus it is unclear whether it is a suitable alternative to the two-level approach of Smith and Volpano. Further, the thesis gives the first full type inference algorithm for the type system of PolyC. Despite implicit variable dereferencing found in PolyC, the algorithm turns out to be a rather straight-forward extension of Damas and Milner's algorithm W DaM82. The algorithm has been implemented as an attribute grammar in Grammatech's SSL and a complete source code listing is given in the Appendix.
Notes: Thesis advisor(s): Dennis Volpano.

"September 1996."

Thesis (M.S. in Computer Science) Naval Postgraduate School, September 1996.

Includes bibliographical references (p. 111-112).

Approved for public release; distribution unlimited.

Also available online.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Turkish Navy author.

dk/dk cc:9996 01/16/97