An Invariant Cost Model for the Lambda Calculus

Details An Invariant Cost Model for the Lambda Calculus An Invariant Cost Model for the Lambda Calculus

2005-11-12

arxiv.org/abs/cs/0511045v1

Computer Science

Logic in Computer Science

19 pages

Scientific paper

We define a new cost model for the call-by-value lambda-calculus satisfying the invariance thesis. That is, under the proposed cost model, Turing machines and the call-by-value lambda-calculus can simulate each other within a polynomial time overhead. The model only relies on combinatorial properties of usual beta-reduction, without any reference to a specific machine or evaluator. In particular, the cost of a single beta reduction is proportional to the difference between the size of the redex and the size of the reduct. In this way, the total cost of normalizing a lambda term will take into account the size of all intermediate results (as well as the number of steps to normal form).

Affiliated with

Also associated with

No associations

Rating

An Invariant Cost Model for the Lambda Calculus 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 An Invariant Cost Model for the Lambda Calculus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Invariant Cost Model for the Lambda Calculus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-408060