Computing Reviews

CPS transformation of beta-redexes
Danvy O., Nielsen L. Information Processing Letters94(5):217-224,2005.Type:Article
Date Reviewed: 02/07/06

A continuous passing style (CPS) is a lambda encoding of lambda terms. CPS transformations are used to generate compilers. This paper presents a CPS transformation that is relatively more compact than others.

The first section introduces the CPS, and provides a brief survey with a list of references. The second section begins by presenting a CPS with context-insensitive administrative reductions. This is followed by a detailed discussion of a three-pass CPS transformation proposed by Sabry and Felleisen [1]. The transformation has context-sensitive administrative reductions. Section 3 contains an observation that a term in a particular type of normal form does not give rise to any extra context-sensitive administration reductions. The major contribution of the paper is described in section 4: a one-pass CPS transformation with context-insensitive administration reductions. Section 5 concludes the paper.

A strong background in lambda calculus is required to understand and appreciate the work. With respect to practical applications, the paper hints in one place that the presented reductions can be programmed in the Scheme language. Readers new to lambda calculus will find the list of references helpful.


1)

Sabry, A.; Felleisen, M. Reasoning about programs in continuation-passing style. LISP and Symbolic Computation 6, 3-4(1993), 289–360.

Reviewer:  Maulik A. Dave Review #: CR132402 (0609-0947)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy