<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
handle: 11585/610072 , 11585/519735
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 hypothesis 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.
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], call-by-value, values, explicit substitutions, complexity, cost model, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Cost models; Explicit substitutions; Implementations of functional programming languages; lambda-Calculus; Theoretical Computer Science; Computational Theory and Mathematics
[INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], call-by-value, values, explicit substitutions, complexity, cost model, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Cost models; Explicit substitutions; Implementations of functional programming languages; lambda-Calculus; Theoretical Computer Science; Computational Theory and Mathematics
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 23 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |