کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436342 689993 2008 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The weak lambda calculus as a reasonable machine
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The weak lambda calculus as a reasonable machine
چکیده انگلیسی

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 the 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).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 398, Issues 1–3, 28 May 2008, Pages 32-50