First Advisor

Andrew Tolmach

Term of Graduation

Winter 1999

Date of Publication

2-12-1999

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Computer Science

Department

Computer Science

Language

English

Subjects

Programming languages (Electronic computers), Computer architecture, Functional programming (Computer science)

Physical Description

1 online resource (v, 67 pages)

Abstract

This study analyzes the use of a continuation-passing style (CPS) intermediate representation versus a direct style intermediate representation in the compilation of a higher-order applicative language. The translator used accepts a program written in an ML-like language as input, and outputs a C program acceptable to a standard C compiler. The effects of the translator's simplification and higher-order function removal transformations on the intermediate language are the primary focus of the analysis. The machine code programs generated from both representations are also analyzed.

Initially, the programs under the direct style representation performed better than those that underwent the CPS transformation. To rectify this, the simplification transformation was specialized to handle some situations unique to the CPS representation. With these modifications, along with using a stack allocation strategy for continuations, some of the CPS programs perform as well as their direct style counterparts. Additionally, an example is presented where the CPS machine code program uses continuations to gain an advantage over the direct style machine code program.

Although it is possible to make the CPS representation competitive with the direct style representation with respect to execution speed, the required modifications to the simplification stage are indicative of how complex a simplifier might need to be for a CPS representation, in particular for one which reflects the higher-order function removal transformation of this translator. Even without considering the complexity introduced by the higher-order function removal, it does not appear that a CPS representation offers any significant benefits over a direct style one with respect to optimizing the intermediate language. Unless further research can show how the explicit representation of function call contexts made possible by CPS can enable a significant set of optimizations, it is argued that a direct style representation would be satisfactory and in fact preferable when the presence of continuations would add an unnecessary level of complexity.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/

This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/44674

Download

Share

COinS