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!
@tatterdemalion @armchair_progamer
No.
Elaborate?Kinda, except if you pass a function pointer the compiler automatically inserts parentheses to call the function after pasting it in every required place. But the compiler does not do that when you pass an expression, non-function-pointer variable or literal.
I must say, your examples/explanation was much better than the link IMO.
I’d like to better understand the algebraic stuff the article was talking about. But clearly it requires brushing up on the Haskell kind system and I dont think I’m up for that today.
