Computer Science – Logic in Computer Science
Scientific paper
2007-02-26
Computer Science
Logic in Computer Science
38 pages
Scientific paper
This paper concerns the explicit treatment of substitutions in the lambda calculus. One of its contributions is the simplification and rationalization of the suspension calculus that embodies such a treatment. The earlier version of this calculus provides a cumbersome encoding of substitution composition, an operation that is important to the efficient realization of reduction. This encoding is simplified here, resulting in a treatment that is easy to use directly in applications. The rationalization consists of the elimination of a practically inconsequential flexibility in the unravelling of substitutions that has the inadvertent side effect of losing contextual information in terms; the modified calculus now has a structure that naturally supports logical analyses, such as ones related to the assignment of types, over lambda terms. The overall calculus is shown to have pleasing theoretical properties such as a strongly terminating sub-calculus for substitution and confluence even in the presence of term meta variables that are accorded a grafting interpretation. Another contribution of the paper is the identification of a broad set of properties that are desirable for explicit substitution calculi to support and a classification of a variety of proposed systems based on these. The suspension calculus is used as a tool in this study. In particular, mappings are described between it and the other calculi towards understanding the characteristics of the latter.
Gacek Andrew
Nadathur Gopalan
No associations
LandOfFree
A Simplified Suspension Calculus and its Relationship to Other Explicit Substitution Calculi does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Simplified Suspension Calculus and its Relationship to Other Explicit Substitution Calculi, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Simplified Suspension Calculus and its Relationship to Other Explicit Substitution Calculi will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-131452