Evaluation order, Oh My!

[kyouko-taiga]

An interesting question has come up recently about the evaluation order of function calls.

TL;DR; what's the evaluation order of &x.f(x.g()) and what consequences it has on the well-typedness of this expression?

In Val, like in most call-by-value languages, the evaluation order is generally thought to be leftmost-innermost. That means given an expression e, the next sub-expression to evaluation is the innermost one found by scanning e from left to right. Note that this evaluation order only really matters in a world where side-effects can occur. For example:

fun combine<T: Sinkable>(_ x: sink T, _ y: sink T) -> (T, T) { (x, y) }

public fun main() {
  _ = combine(combine(print("a"), print("b")), print("c"))
}

According to a leftmost-innermost strategy, this program should print "a", "b" and "c" in that specific order. I speculate that it corresponds to most people's intuition.

We could leave things there in a world where functions aren't first-class. But if they are, then comes the question of the moment when the callee is evaluated relative to the arguments in a function call. For example, what should be the trace of this program:

fun make_fun() -> (_: String) -> Void {
  print("make_fun")
  return fun(_ s: String) { print(s) }
}

fun make_arg() -> String {
  print("make_arg")
  return "foo"
}

public fun main() {
  make_fun()(make_arg())
}

Here, if we look at the AST, we would conclude that make_fun() is at the same depth as make_arg(). So because make_fun() is left of make_arf(), the former should be evaluated first. That might be a little more surprising, but I still think most people would get on board at this point. The next example may be more divisive:

type A {
  fun f(_ i: Int) inout {}
  fun g() -> Int { 0 }
}

public fun main() {
  var x = A()
  &x.f(x.g()) // what happens here?
}

Should this program compile? Well, I think the answer is tricky.

An important thing to consider the meaning of &x.f. A reasonable way to understand a method is to see it as sugar for a free function that accepts its receiver as a hidden parameter. That's how Val actually operates under the cover: the signature of A.f equivalent to (inout A, Int) -> Void. If we curry this function, we get something of the form [inout A](Int) -> Void (that is, a function (Int) -> Void that captures a mutable projection of A). Following this observation, one way to re-write main would be as follow:

public fun main() {
  var x = A()
  var f = fun[inout self = &x](_ i: Int) { A.f(&self, i) }
  let g = fun[let self = x]() { A.g(self) } // type error
  &f(g())
}

This program is ill-typed because it tries to bind x to initialize g after it's been bound inout to initialize f.

Another and perhaps more straightforward way to use the free form of the method is to just call it directly without using currying. So the call &x.f(x.g()) should be equivalent to A.f(&x, A.g(x)). Under that interpretation, the program should still not compile because A.g(x) attempts to use x after it's been bound inout to form the first argument. Further, we should note that this interpretation suggests &x.f in &x.f(x.g())) doesn't actually evaluate to a function of type (Int) -> Void, meaning these expressions do not have the same semantics:

• &x.f(x.g())
• (&x.f,).0(x.g())

Alternatively, we could say that self should come last in the parameter list, so that we evaluate x.g() first. However, that would go against a direct application of the leftmost-innermost strategy on the original expression, i.e., &x.f(x.g()).

What do you think should be the best strategy? What did I miss?

Personally, I think we should go with the last approach.

[dabrahams]

the next sub-expression to evaluation is the innermost one found by scanning e from left to right

I could interpret that statement two ways that are both consistent with your example. I suspect you mean #1:

1. Find the leftmost unevaluated immediate sub-expression of the whole expression, and find its leftmost unevaluated immediate sub-expression, and so on, until you reach an sub-expression E with no un-evaluated sub-expressions. E is the next sub-expression to evaluate.
2. Rate un-evaluated sub-expressions by their nesting levels, and then choose the leftmost sub-expression having the highest rating.

the expression combine(print("a"), identity(print("b"))) would be evaluated differently according to these two criteria (#1 prints "a" then "b"; #2 prints the opposite order).

[kyouko-taiga]

Excellent observation. I meant the first one indeed.

[kyouko-taiga]

Small observation: maybe another way to understand my definition of leftmost-innermost is to think of a postorder traversal of the AST.

This is still an awkward definition in practice, though, because there isn't a 1-to-1 correspondance between the concrete and abstract syntax of Val. For example, !x and x! are both represented by (roughly) FunctionCall(Name(domain: Name("x"), n), arguments: []) where n is Name("prefix!") and Name("postfix!"), respectively.

[dabrahams]

type A {
  fun f(_ i: Int) inout {}
  fun g() -> Int { 0 }
}

public fun main() {
  var x = A()
  &x.f(x.g()) // what happens here?
}

Should this program compile? Well, I think the answer is tricky.

I don't think the answer to that question is tricky at all. The code has an obvious meaning and should obviously compile! The interesting question from my point of view is: what is the evaluation order algorithm that allows us to interpret that code (and all other code we think is obvious) in the obvious way? It is of course possible that we can't agree on obviousness or that no such algorithm exists, but we should start by trying.

Aside:

If we curry this function…

Applying currying is only valid if &x.f is a subexpression of &x.f(x.g()). That doesn't match my mental model, and it clashes with the view that a method call is "sugar for a free function that accepts its receiver as a hidden parameter". If you rewrite that call as a free function, you get A.f(&x, A.g(x)), and the curried form is never computed.
(end aside)

I believe that part of the key a satisfactory algorithm is viewing the evaluation of an inout argument as computing an identity rather than a value. That is still imprecise, though, so let's dig into it with an example that's complex enough to nail down the details: &y[i].f(y[j].g()), where y: Array<A>.

We can begin by rewriting it as A.f(&y[i], A.g(y[j])).

First question: is this legal code? If &x.f(x.g())/A.f(&x, A.g(x)) is going to be legal (which I claim it "obviously" is), I can see no rational justification for making the more complex example illegal.

Second question: what should the avaluation order be? I'll try to answer that in a follow-up.

[kyouko-taiga]

What's the semantics of CompoundExpression.evaluate(subexpression_values:,in:)?

I don't understand why i gets evaluated after the call to A.g here but I'm surely missing something. The way I understood your algorithm, the first partition creates [&y[i], A.g(y[j])], suggesting i will always come first when we recursively call evaluate(in:) on &y[i].

[kyouko-taiga]

If we want i to be evaluated first, a more complex algorithm is needed.

We might need that more complex algorithm. I would expect i to be evaluated first and would be very surprised otherwise since I suspect it would be the case when in the absence of mutation (e.g., f(g(i), h(j))).

I'm worried that such an algorithm would leave us with a rather intricate evaluation order, though. What happens herefoo(&x[&x.pop_last()!], x.copy()) where x is an array on Ints? I guess we're forced to say the call to pop_last comes after the copy, hence introducing yet another difference compared to the non-mutating case (and assuming the use of the more complex algorithm).

Here are a all the use cases I think we must consider:

1. f01(x[x.first()!].copy(), x[x.last()!].copy())
2. f02(x[x.first()!].copy(), x[&x.pop_last()!].copy())
3. f03(x[x.first()!].copy(), &x[x.last()!])
4. f04(x[x.first()!].copy(), &x[&x.pop_last()!])
5. f05(x[&x.pop_first()!].copy(), x[x.last()!].copy())
6. f06(x[&x.pop_first()!].copy(), x[&x.pop_last()!].copy())
7. f07(x[&x.pop_first()!].copy(), &x[x.last()!])
8. f08(x[&x.pop_first()!].copy(), &x[&x.pop_last()!])
9. f09(&x[x.first()!], x[x.last()!].copy())
10. f10(&x[x.first()!], x[&x.pop_last()!].copy())
11. f11(&x[x.first()!], &x[x.last()!])
12. f12(&x[x.first()!], &x[&x.pop_last()!])
13. f13(&x[&x.pop_first()!], x[x.last()!].copy())
14. f14(&x[&x.pop_first()!], x[&x.pop_last()!].copy())
15. f15(&x[&x.pop_first()!], &x[x.last()!])
16. f16(&x[&x.pop_first()!], &x[&x.pop_last()!])

IIUC your mental correctly, the following should be illegal: 11, 12, 15, and 16.
According to mine, (9 ... 16) are.

[dabrahams]

What's the semantics of CompoundExpression.evaluate(subexpression_values:,in:)?

Given the values of all the evaluated subexpressions, it evaluates the compound expression in the environment. In other words, if the compound expression is a * b + c * d, the subexpression values are the two results of evaluating a * b and c * d, and the result of the evaluate call is the sum of the subexpression values.

I don't understand why i gets evaluated after the call to A.g here but I'm surely missing something. The way I understood your algorithm, the first partition creates [&y[i], A.g(y[j])], suggesting i will always come first when we recursively call evaluate(in:) on &y[i].

The argument to stable_partition tells you whether an element belongs in the 2nd partition, so it creates the opposite ordering.

I realized last night that the criterion I want may not be "does it start with an ampersand?" but actually something like, "is it a projection of an lvalue?"

[dabrahams]

I'm worried that such an algorithm would leave us with a rather intricate evaluation order, though. What happens herefoo(&x[&x.pop_last()!], x.copy()) where x is an array on Ints? I guess we're forced to say the call to pop_last comes after the copy

I suppose so. I don't have a problem with that answer because when I look at that code, I don't think the semantics are obvious. As long as this example follows a set of rules consistent with the examples I do find obvious, I'm fine with that.

hence introducing yet another difference compared to the non-mutating case (and assuming the use of the more complex algorithm).

Yeah, though as mentioned earlier, I think I may not have got the criterion quite right. It may be based more on what-is-a-projection than what-is-mutating. We need to look at some more examples, and I think your list is a great start. I'll rewrite them here into equivalent free-function form (and yes, I believe the equivalence is important).

1. f01(A.copy(x[A.first(x)!]), A.copy(x[A.last(x)]))
2. f02(A.copy(x[A.first(x)!]), A.copy(x[&x.pop_last()!]))
3. f03(A.copy(x[A.first(x)!]), &x[A.last(x)!])
4. f04(A.copy(x[A.first(x)!]), &x[&x.pop_last()!])
5. f05(A.copy(x[&x.pop_first()!]), A.copy(x[A.last(x)!]))
6. f06(A.copy(x[&x.pop_first()!]), A.copy(x[&x.pop_last()!]))
7. f07(A.copy(x[&x.pop_first()!]), &x[A.last(x)!])
8. f08(A.copy(x[&x.pop_first()!]), &x[&x.pop_last()!])
9. f09(&x[A.first(x)!], A.copy(x[A.last(x)!]))
10. f10(&x[A.first(x)!], A.copy(x[&x.pop_last()!]))
11. f11(&x[A.first(x)!], &x[A.last(x)!])
12. f12(&x[A.first(x)!], &x[&x.pop_last()!])
13. f13(&x[&x.pop_first()!], A.copy(x[A.last(x)!]))
14. f14(&x[&x.pop_first()!], A.copy(x[&x.pop_last()!]))
15. f15(&x[&x.pop_first()!], &x[A.last(x)!])
16. f16(&x[&x.pop_first()!], &x[&x.pop_last()!])

Whether first and last should be methods or projections (properties) is an interesting question that would change how I view many of these.

[dabrahams]

I guess I need your answers to these questions before we know if this rewritten list is even relevant.

[dabrahams]

I can get behind this interpretation and that's how I've been implementing the language so far. I just want the record to show that there's a valid interpretation of e1(e2) that evaluates e1 as a lambda regardless of the expression that contains it, if any.

Yeah, I was thinking that since currying neither mutates nor has any side-effects, maybe it's a perfectly fine transformation to make.

The distinction is important if we consider the ability use bound methods as first-class values (e.g.: x.filter(y.contains(_:)) where both x and y are collections).

What distinction? I think you're describing a unification, or non-distinction. Anyway, just I want the record to show that we can distinguish bound methods from method calls syntactically, and they could be interpreted differently if necessary. But it's probably not necessary.

I'll have to come back to your <aside id=2> later; it's an interesting question…

I think A.f(&y[i], A.g(y[j])) is "obviously" illegal because my mental model sees the passing of arguments as the formation of bindings. So I understand that expression to be equivalent to inout a1 = &y[i]; let a2 = A.g(y[j]); <code of A.f>; <end of projections>.

In that case I believe you contradict your own previous agreement with me, because A.f(&x, A.g(x)) is equivalent toinout a1 = &x; let a2 = A.g(x); <code of A.f>; <end of projections>, which makes it illegal. Remember, you can't make a special rule that syntactically distinguishes an expression like x from one like y[i] because x could be a computed property.

[kyouko-taiga]

Doesn't this cause problems for the equivalence of self.some_method() and some_method()?

Sorry, I should have said "when the callee is a name bound to a function declaration". Whether that name is qualified or not is in fact irrelevant.

I've always hated the fact that in C++ qualified and unqualified name lookup were so different, so based on the words alone (and not yet understanding fully what they mean) I find that worrisome.

I don't think I've introduced any significant difference in the lookup mechanisms. The only difference I can think of is that unqualified lookup must climb the scope hierarchy whereas qualified lookup doesn't. That is orthogonal to the question at hand.

Because of overloading?

No, because foo() is an expression that requires evaluation to produce a function.

When the callee is a name bound to a function declaration, we're usually interested in how to dispatch the call. We typically answer this question by looking at the declaration candidates and we can do that using unqualified/qualified lookup. Typically, this process has no observable semantics because it is just a matter of selecting the right function. Even late binding typically doesn't involve any observable computation steps.

Maybe one way to connect this point to what you've said here is to say that a name bound to a function declaration denotes an identity rather than a value.

When the callee is any other expression (including a name bound to a variable/property with a function type), dispatch gets out of the picture because now we've got an expression to evaluate. It's only by computing the value of that expression that we can get the identity of the function to call. Such a computation will typically involve observable computation steps.

fun foo() -> () -> Int { fun() { 42 } }
fun foo(_ x: Int) -> () -> Int { fun[sink let y = x.copy()]() { y.copy() } }

public fun main() {
  _ = (foo())()
}

When we look at (foo())(), the only way to get the identity of the function being called is to evaluate foo(). When we look at that call, though, we can "resolve" the identity of foo by looking at its declarations.

If you can compute the identity of the callee without computing its value, then you can evaluate the arguments first and the environment second. Otherwise, the environment will have to be captured before the call can occur unless the callee is evaluated after the arguments., in which case the distinction gets erased.

Answers to your other points are in the pipeline.

[dabrahams]

When the callee is a name bound to a function declaration, we're usually interested in how to dispatch the call.

I'm afraid I don't understand why we'd be “interested” in how to dispatch the call in that case. When it's a name bound to a (which means, ”one single”) function declaration, we dispatch to the definition of the function to whose declaration the name is bound, neh? Seems like a straightforward answer. In the case of overloaded functions it's more interesting, but I don't think that's what you're talking about; at least if that's what you meant I'd expect you to use the term "overload resolution". I clearly don't understand what you mean by "dispatch."

When the callee is any other expression (including a name bound to a variable/property with a function type), dispatch gets out of the picture because now we've got an expression to evaluate

Even then, overloading can come into play because you may select the meaning of that expression based on what it takes to make the whole expression typecheck… but now I'm confused again because the example you show clearly does depend on overload resolution.

[kyouko-taiga]

Let's try another way. Imagine we're teaching programming to someone and we are looking at this piece of code:

fun foo() -> Int { 42 }

public fun main() {
  foo(10) // (1)
}

The person asks: "what happens at (1)". I would answer: "we're calling foo". Should foo be overloaded, I would say: "we're calling this particular definition of foo because ..."

Now let's imagine we're looking at this piece of code:

fun bar() -> () -> Int { fun() { 42 } }

public fun main() {
  _ = bar()() // (1)
}

The person asks: "what happens at (1)". I would answer: "we're calling the results of foo()'s application".

Notice that in the first case I did not say "we're calling the result of foo's evaluation" and I claim most people would not either. That's because when the callee is a name, the way we're thinking about code is to perform name lookup by ourselves. Name lookup typically never causes side effects and so my claim is that the way most people think about a name is different than the way they think about the evaluation of an arbitrary expression.

I also claim that it is how most people think about bound members:

type A {
  fun foo() {}
  fun bar() {
    foo() // (1)
  }
}

If I have to explain what (1) does I will say: "we're calling foo". I won't say: "we're calling the result of self.foo's evaluation".

Qualification doesn't change the way we think about names, neither does overloading or late binding. These features just make lookup more sophisticated. Overload resolution and dynamic dispatch are "pure" algorithm that most people don't consider an evaluation. They are black-box procedures connecting a name to a definition.

We only need to think of callees as results of evaluations when functions are first-class values. So I claim that in Pascal no one would every say "we're calling the result of evaluating foo".

[kyouko-taiga]

Connecting things back to my previous post, "dispatch" is the name I use to denote the procedure that connects a name to a function identity. When I look at the code, I don't need to think about possible side effects this procedure may have, because in my experience in never has any.

The point is:

Qualification doesn't change the way we think about names, neither does overloading or late binding. These features just make lookup more sophisticated. Overload resolution and dynamic dispatch are "pure" algorithms that most people don't consider an evaluation.

Evaluating an expression requires a different mindset because arbitrary expressions can have side effects. So the procedure that gets from an expression to a function identity becomes a different beast. We can't just perform name lookup in our head and look at function definitions. Instead, we must figure out how a function gets created at runtime.

[dabrahams]

The person asks: "what happens at (1)". I would answer: "we're calling the results of foo()'s application".

bar's.

Notice that in the first case I did not say "we're calling the result of foo's evaluation" and I claim most people would not either.

Of course not. Most people have no idea what you mean by “application” and “evaluation,” so they also wouldn't describe it the way you did, either. They'd say we're “calling bar, and then calling the result of that call” or “calling the result of calling bar.”

That's because when the callee is a name, the way we're thinking about code is to perform name lookup by ourselves. Name lookup typically never causes side effects

Looking up the name never causes side-effects at runtime because it's a compile-time operation! Beginning/ending the projection of an identifier-expression happens at runtime, can have side-effects, and significantly in Val, has huge implications for LoE.

But regardless of whether any of what you wrote before is valid, we can deal with your conclusion on its own:

my claim is that the way most people think about a name is different than the way they think about the evaluation of an arbitrary expression.

I'm happy to posit that people think about "a name" differently from “expression evaluation.” One is just a piece of syntax, while the other is a process, so to me they are obviously in different categories.

If I have to explain what (1) does I will say: "we're calling foo". I won't say: "we're calling the result of self.foo's evaluation".

I would say we're calling foo on self. You don't get to just ”call foo” without some receiver. I think the plain English version of "we're calling the result of self.foo's evaluation" is "we're evaluating the expression self.foo and then calling that". Regardless of whether you would say that, I would be deeply surprised by any language where any of the following lines had different meanings inside of A.bar

1. foo()
2. self.foo()
3. (self.foo)()
4. identity(self.foo)() if it were legal. In Val it might need to be identity[self.foo]().

So to me it makes no difference which way you explain what's happening. And to me, none of this has obvious relevance to our choice of evaluation order.

Overload resolution and dynamic dispatch are "pure" algorithm that most people don't consider an evaluation.

Nor do I consider them evaluations. I don't know what that has to do with how we understand expression evaluation order. If all you're trying to say is that overload resolution isn't involved in determining the semantics of some calls like g() in fun f(_ g: ()->()) { g() }, well I don't need to be convinced of that, but I also don't see the relevance to the topic of this discussion.

[dabrahams]

I believe @kyouko-taiga and I have resolved how evaluation order works:

The callee of a function call syntax is evaluated after all the other arguments, which is equivalent to a rewrite rule that lifts a binding to each argument value out of the call and into a prior statement, in left-to-right order, and then making the call on those bindings.

So return x.f(x.g(), x.h()) is equivalent to

let %0 = x.g
let %1 = %0()
let %2 = x.h
let %3 = %2()
let %4 = x.f
return %4(%1, %3)

where %n denotes a synthesized temporary binding. For method calls, you could say self is implicitly the last argument, but the rewrite rule also affects the meaning of non-method expressions like foo()(bar()) (bar is called before foo).

This rule entirely syntactic and applies no matter what kind of expression the callee is. In the case of an expression like x.f(y), the callee is x.f, and that applies whether f is a method of x's type or a property of x having function type.

The rule for evaluating operator expressions is similarly syntactically driven: x + y evaluates x first, but x.infix+(y) evaluates y first.

Dimi, did I miss anything?

[kyouko-taiga]

I guess there's a typo in your example. You probably meant return %4(%1, %3).

Aside from that, you didn't miss anything AFAICT. Great summary, thanks!

[dabrahams]

Thanks; fixing