Call-by-push-value is an evaluation strategy that determines when arguments to functions are evaluated. Call-by-value is what every mainstream language does: arguments are evaluated before the function is called. Call-by-name substitutes arguments directly into a function, so they may be evaluated multiple times or not at all. For example, the following pseudocode:
function foo(n, m) {
sum = 0
for i in 1 to 4 {
sum = n + sum
}
if false {
print(m)
}
print(sum)
}
foo({print("1"); 2}, {print("3"); 4})
evaluated with Call-by-Value prints:
1
3
8
evaluated with Call-by-Name prints:
1
1
1
1
8
Call-by-push-value combines both by having two "kinds" of parameters: values which are evaluated immediately (call-by-value), and computations which are substituted (call-by-name). So the following code:
function foo(value n, computation m) {
sum = 0
for i in 1 to 4 {
sum = n + sum
}
if false {
print(m)
}
print(sum)
}
foo({print("1"); 2}, {print("3"); 4})
would print
1
8
The reason call-by-push-value may be useful is because both call-by-name and call-by-value have their advantages, especially with side-effects. Besides enabling programmers to write both traditional functions and custom loops/conditionals, CBPV is particularly useful for an IR to generate efficient code.
Currently, Scala has syntactic sugar for by-name parameters, and some languages like Kotlin and Swift make zero-argument closure syntax very simple (which does allow custom loops and conditionals, though it's debatable whether this is CBPV). Other languages like Rust and C have macros, which can emulate call-by-name, albeit not ideally (you have hygiene issues and duplicating syntax makes compilation slower). I don't know of any mainstream work on CBPV in the IR side.
Isn't
computationequivalent to passing a function by value?I believe the answer is yes, except that we’re talking about languages with currying, and those can’t represent a zero argument function without the “computation” kind (remember: all functions are
Arg -> Ret, and a multi-argument function is justArg1 -> (Arg2 -> Ret)). In the linked article, all functions are in fact “computations” (the two variants ofCompTypeareThunk ValTypeandFun ValType CompType). The author also describes computations as “a way to add side-effects to values”, and the equivalent in an imperative language to “a value which produces side-effects when read” is either a zero-argument function (getXYZ()), or a “getter” which is just syntax sugar for a zero-argument function.The other reason may be that it’s easier in an IR to represent computations as intrinsic types vs. zero-argument closures. Except if all functions are computations, then your “computation” type is already your closure type. So the difference is again only if you’re writing an IR for a language with currying: without CBPV you could just represent closures as things that take one argument, but CBPV permits zero-argument closures.
Thank you so much! For years I was carrying around the thought: Why do we have to decide between eager and lazy evaluation? Your explanations are so clear and motivate me to finally dig deeper into that topic. So approachable. Thanks!