کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4950676 1364298 2017 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On the value of variables
ترجمه فارسی عنوان
در ارزش متغیرها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Call-by-value and call-by-need λ-calculi are defined using the distinguished syntactic category of values. In theoretical studies, values are variables and abstractions. In more practical works, values are usually defined simply as abstractions. This paper shows that practical values lead to a more efficient process of substitution-for both call-by-value and call-by-need-once the usual hypotheses for implementations hold (terms are closed, reduction does not go under abstraction, and substitution is done in micro steps, replacing one variable occurrence at a time). Namely, the number of substitution steps becomes linear in the number of β-redexes, while theoretical values only provide a quadratic bound. We complete the picture by showing that the same quadratic / linear bounds also hold for theoretical / practical versions of call-by-name.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 255, Part 2, August 2017, Pages 224-242
نویسندگان
, ,