Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage

Details Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage

2004-05-22

arxiv.org/abs/cs/0405075v1

Computer Science

Programming Languages

This is a modified version of the master's thesis of Xiaochu Qi

Scientific paper

Higher-order representations of objects such as programs, proofs, formulas and types have become important to many symbolic computation tasks. Systems that support such representations usually depend on the implementation of an intensional view of the terms of some variant of the typed lambda-calculus. Various notations have been proposed for lambda-terms to explicitly treat substitutions as basis for realizing such implementations. There are, however, several choices in the actual reduction strategies. The most common strategy utilizes such notations only implicitly via an incremental use of environments. This approach does not allow the smaller substitution steps to be intermingled with other operations of interest on lambda-terms. However, a naive strategy explicitly using such notations can also be costly: each use of the substitution propagation rules causes the creation of a new structure on the heap that is often discarded in the immediately following step. There is thus a tradeoff between these two approaches. This thesis describes the actual realization of the two approaches, discusses their tradeoffs based on this and, finally, offers an amalgamated approach that utilizes recursion in rewrite rule application but also suspends substitution operations where necessary.

Affiliated with

Also associated with

No associations

Rating

Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage 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 Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-261427