PLS Lab

Call-by-name

Call-by-name (CBN) refers to a style of evaluation of the λ-calculus in which identifiers refer to arbitrary terms

The usual \beta-reduction for a function applied to an argument is given by

	(\lambda x. M)N \longrightarrow M[N/x]

Thus, the bound identifier x in M stands for an arbitrary term N.

CBN reduction is closely related to normal order reduction, though they are not the same.

Relationship to CBV

A classic paper by Gordon Plotkin Plotkin 1975 that compares CBN and CBV by establishing simulations of one into the other, using continuations.

Please expand: call-by-push-value.

History

The term call-by-name seems to have first appeared in the report defining ALGOL 60 Backus et al 1960.
Here is the exact quote:

4.7.3.2. Name replacement (call by name)

Any formal parameter not quoted in the value list is replaced, throughout the procedure body, by the corresponding actual parameter, after enclosing this latter in parentheses wherever syntactically possible. Possible conflicts between identifiers inserted through this process and other identifiers already present within the procedure body will be avoided by suitable systematic changes of the formal or local identifiers involved.

See also

References

Backus, J. W., F. L. Bauer, J. Green, C. Katz, J. McCarthy, A. J. Perlis, H. Rutishauser, et al. 1960. ‘Report on the Algorithmic Language ALGOL 60’. Edited by Peter Naur. Communications of the ACM 3 (5): 299–314. https://doi.org/10.1145/367236.367262. pdf 
@article{backus_1960,
	title = {Report on the algorithmic language {ALGOL} 60},
	volume = {3},
	doi = {10.1145/367236.367262},
	number = {5},
	journal = {Communications of the ACM},
	author = {Backus, J. W. and Bauer, F. L. and Green, J. and Katz, C. and McCarthy, J. and Perlis, A. J. and Rutishauser, H. and Samelson, K. and Vauquois, B. and Wegstein, J. H. and van Wijngaarden, A. and Woodger, M.},
	editor = {Naur, Peter},
	year = {1960},
	pages = {299--314},
}
Plotkin, G.D. 1975. ‘Call-by-Name, Call-by-Value and the λ-Calculus’. Theoretical Computer Science 1 (2): 125–59. https://doi.org/10.1016/0304-3975(75)90017-1. pdf 
@article{plotkin_1975,
	title = {Call-by-name, call-by-value and the λ-calculus},
	volume = {1},
	doi = {10.1016/0304-3975(75)90017-1},
	number = {2},
	journal = {Theoretical Computer Science},
	author = {Plotkin, G.D.},
	year = {1975},
	pages = {125--159}
}