Accession Number : ADA258635


Title :   Explicit Polymorphism and CPS Conversion,


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE


Personal Author(s) : Harper, Robert ; Lillibridge, Mark


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a258635.pdf


Report Date : Oct 1992


Pagination or Media Count : 26


Abstract : We study the typing properties of CPS conversion for an extension of F omega, with control operators. Two classes of evaluation strategies are considered, each with call-by-name and call-by-value variants. Under the 'standard' strategies, constructor abstractions are values, and constructor applications can lead to non-trivial control effects. In contrast, the 'ML-like' strategies evaluate beneath constructor abstractions, reflecting the usual interpretation of programs in languages based on implicit polymorphism. Three continuation passing style sub-languages are considered, one on which the standard strategies coincide, one on which the ML-like strategies coincide, and one on which all the strategies coincide. Compositional, type-preserving CPS transformation algorithms are given for the standard strategies, resulting in terms on which all evaluation strategies coincide. This has as a corollary the soundness and termination of well-typed programs under the standard evaluation strategies. A similar result is obtained for the ML-like call-by-name strategy. In contrast, such results are obtained for the call-by value ML-like strategy only for a restricted sub-language in which constructor abstractions are limited to values.


Descriptors :   *CONVERSION , *PROGRAMMING LANGUAGES , *POLYMORPHISM , ALGORITHMS , CONTROL , CONTRAST , LANGUAGE , TRANSFORMATIONS , CALCULUS , STANDARDS , STRATEGY , THEORY , COMPUTER PROGRAMMING


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE