I don't think we should make this change. To explain why, I'll use an example message written using the proposed syntax:

Example 1:

set $v1 = {foo :func}
set $v2 = {$v1}
set $v3 = {$v1}
set $v1 = {42}
{{$v2}}

I'm assuming, based on #299, that the formatting spec will eventually specify some form of lazy evaluation for local variables.

There are two varieties of lazy evaluation: call-by-name and call-by-need.

If we choose call-by-name, then the result of evaluating this message is the result of sequentially replacing each declaration's LHS with its RHS. So under call-by-name semantics, Example 1 is equivalent to Example 2:

Example 2:

set $v1 = {foo :func}
set $v2 = {foo :func}
set $v3 = {foo :func}
set $v1 = {42}
{{$v2}}

The result is the result of calling func on the literal foo.

Under call-by-need, for each declaration let $v = {e}, each LHS $v would be bound to a mutable slot that contains a closure. The closure contains the code representing e, and an environment, which gives meanings to any free variables in e.

The steps in evaluating the message would be:

1. Bind $v1 to a mutable slot containing a closure that computes {foo :func}, with an empty environment (empty because {foo :func} has no free variables).
2. Bind $v2 to a mutable slot containing a closure that computes {$v1} and an environment mapping the name $v1 onto the mutable slot created in step 1.
3. Bind $v3 to a separate mutable slot containing a closure that computes {$v1} and an environment mapping the name $v1 onto the mutable slot created in step 1.
4. Overwrite the contents of $v1 with a closure that computes {42} with an empty environment.
5. Evaluate the body by invoking the closure created in step 2.

The result is the literal 42, because the closure for $v2 contains a reference to $v1 -- not the initial value of $v1 -- and during step 5, $v1 denotes a slot that (effectively) contains the literal 42.

So we see that whether we choose call-by-need or call-by-name changes the meaning of the message. This is why call-by-need is not typically used in languages with mutable data. We could commit to using call-by-name semantics, which would mean this message would resolve to what the user probably expects it to resolve to (which is to say, whatever func(foo) returns). However, that commitment potentially means repeating a lot of computation. The question is whether the benefits of allowing mutation are worth it.

You might ask: "Don't we have the same problem with the existing let-construct? After all, the only difference is whether the keyword is let or set."

Yes and no. If we also specify that the sequential lets in a message are syntactic sugar for nested lets -- which is to say, for example:

Example 3:

let $v1 = {e1}
let $v2 = {e2}
let $v3 = {e3}
{{$v1} {$v2}}

is equivalent to:

Example 4:

let $v1 = {e1} in
  let $v2 = {e2} in
    let $v3 = {e3} in
       {{$v1} {$v2}}

then we solve the problem. Example 4 isn't a valid message; the point is just to show what it means to treat the lets as conceptually nested.

This solves the problem because if we consider examples 3 and 4 to be equivalent in meaning, then we can also specify that:

Example 5:

let $v1 = {e1}
let $v2 = {$v1}
let $v1 = {e3}
{{$v1} {$v2}}

is equivalent to:

Example 6:

let $v1 = {e1}
let $v2 = {$v1}
let $v3 = {e3}
{{$v3} {$v2}}

Example 6 is the result of uniquely renaming each variable. If we know that all variables are unique, then we can explain variable resolution by repeated substitution (for spec purposes; it doesn't have to be implemented as substitution):

{{$v3} {$v2}}   # after unique renaming
{e3 {$v1}}       # after substituting `$v3`⟼`e3` and `$v2`⟼`{$v1}`
{e3 e1}           # after substituting `$v1`⟼`e1`

In other words: with the existing let syntax, it's unsurprising to say that alpha-renaming (giving each distinct declaration a unique name and performing substitutions so as to preserve the message's meaning) is a meaning-preserving transformation.

On the other hand, if we moved towards set and treating declarations like assignments, it would be counterintuitive to treat examples 5 and 6 as equivalent. Going back to example 2, if you think the $v1 assigned on line 1 and the $v1 assigned on line 4 are the same mutable variable, you will be surprised. And the syntax encourages you to think that. With call-by-need, this difference is observable.

(Edited for clarity, 2023-07-05)

So in my opinion, if everybody agrees that local variable declarations should be evaluated lazily, we should keep the let syntax and give it a semantics in which unique renaming doesn't change the meaning of the message. The combination of mutation and call-by-need is confusing and I'm not aware of any significant programming languages that have it.

Moreover, I don't know how to precisely specify the meaning of name shadowing without specifying how the sequential let construct desugars to nested lets: in other words, why lets are lexically scoped. Or, alternately, specifying how alpha-renaming works. Either of those seems very challenging to do at the level of formality of the current spec. That's why I also believe that name shadowing should be disallowed, but that's a separate question.

@catamorphism Would it be possible for you to replace the expressions like {e1} and patterns like {p} in the above with valid syntax? I'm getting rather lost in trying to figure out what each might mean, end e.g. can't tell what the difference is between examples 5 and 6.

So in my opinion, if everybody agrees that local variable declarations should be evaluated lazily, [...]

This is not necessarily a valid premise, and I don't think we've explicitly established any explicit preference or requirement for laziness or eagerness in the spec at least so far. In fact, we've gone out of way to ensure that either approach is valid.

In that spirit, the recent formatting PR added this to the Error Handling section:

This is intended to allow for either eager or lazy behaviour in an implementation. So if it made the explanation simpler, with that language being included we could specify something like this in the spec and still support both:

Each declaration is processed in source order.
A declaration modifies the formatting context variable mapping of string identifiers to values
by assigning the resolved value of its expression as the value for its variable name.
If a declaration expression includes variables,
their values are resolved using the variable mapping values as they were before the current declaration.

This kind of formulation would simplify our scopes to just one, which should be easier to understand.

With that as a starting point, the declarations of your first example

set $v1 = {foo :func}
set $v2 = {$v1}
set $v3 = {$v1}
set $v1 = {42}
{{$v2}}

would modify the formatting context variable mapping as follows:

0. Start with an empty set {}
1. After set $v1 = {foo :func} we have { v1: func('foo') }
2. After set $v2 = {$v1} we have { v1: func('foo'), v2: func('foo') }
3. After set $v3 = {$v1} we have { v1: func('foo'), v2: func('foo'), v3: func('foo') }
4. After set $v1 = {42} we have { v1: '42', v2: func('foo'), v3: func('foo') }

And so during the pattern formatting, {$v2} would get its value for func('foo').

If we disallow mutating variables, we also avoid the issue completely.

@catamorphism Would it be possible for you to replace the expressions like {e1} and patterns like {p} in the above with valid syntax? I'm getting rather lost in trying to figure out what each might mean, end e.g. can't tell what the difference is between examples 5 and 6.

Sure, I edited it -- let me know if it makes sense now.

This is not necessarily a valid premise, and I don't think we've explicitly established any explicit preference or requirement for laziness or eagerness in the spec at least so far. In fact, we've gone out of way to ensure that either approach is valid.

I'm assuming, perhaps wrongly, that if the difference between laziness and eagerness is observable, then the spec has to require either laziness or eagerness (there are really (at least) three options: call-by-value (eager), call-by-name (lazy with substitution), and call-by-need (lazy with memoization). That is: when the difference between laziness and eagerness is observable, the spec dictates which behavior the implementation has to produce. (Of course an implementation could simulate laziness with eagerness, or vice versa, if it wanted to, as long as the observable result is the same.)

There are two ways the difference could be observable:
a. The same message formats to a different string (without loss of generality I'm assuming "formatting to a string" rather than "formatting to parts" for the sake of this discussion) depending on the evaluation strategy.
b. For the same message, the formatter processes it with no errors under one evaluation strategy, but emits errors under a different evaluation strategy.

I'm assuming the spec has to be precise enough to rule out both (1) and (2).

Example 1 falls into category (a): with either call-by-value or call-by-name, the result is func('foo'); with call-by-need, the result is 42.

An example that falls into category (b) is:

Example 7:

let $v1 = {$oops}
{foo}

Assuming no externally defined variables: under call-by-value, an "Unresolved Variable" error is emitted because $oops is not defined. Under either call-by-name or call-by-need, no errors are emitted because $v1 is never referenced.

So if it's a requirement to avoid category (a) ambiguities, then the spec does have to require observably call-by-value, call-by-name, or call-by-need semantics. If the single-assignment property is enforced (either requiring all let-defined names to be unique, or not allowing multiple set-assignments to the same variable, depending on the chosen syntax), then that makes the difference between call-by-name and call-by-need unobservable for category (a) ambiguities.

Even with the single-assignment property, call-by-name and call-by-need are still distinguishable for messages in category (b) -- for example:

Example 8:

let $v1 = {$oops}
{{$v1} {$v1}}

In an implementation that emits all errors, call-by-name means this emits two "Unresolved Variable" errors since the body is equivalent to {{$oops} {$oops}}. Call-by-need means it only emits one error, since {$oops} is evaluated exactly once.

Maybe category (b) isn't important since the spec implies that implementations aren't required to report more than one error in a given message.

I'm assuming category (a) is important, since if two different implementations can format the same message with the same arguments and function registry (with observationally equivalent implementations of all the functions) to different strings and both be spec-compliant, that seems undesirable to me. But maybe that assumption isn't shared.

With that as a starting point, the declarations of your first example

set $v1 = {foo :func}
set $v2 = {$v1}
set $v3 = {$v1}
set $v1 = {42}
{{$v2}}

would modify the formatting context variable mapping as follows:

0. Start with an empty set {}
1. After set $v1 = {foo :func} we have { v1: func('foo') }
2. After set $v2 = {$v1} we have { v1: func('foo'), v2: func('foo') }
3. After set $v3 = {$v1} we have { v1: func('foo'), v2: func('foo'), v3: func('foo') }
4. After set $v1 = {42} we have { v1: '42', v2: func('foo'), v3: func('foo') }

And so during the pattern formatting, {$v2} would get its value for func('foo').

Not necessarily. In a call-by-need implementation, the "resolved values" are thunks (closures paired with environments), and as I outlined in the first comment, the result is 42, not func('foo'). The thunk created when evaluating $v2 contains a reference to the contents of $v1 -- {foo :func} can't be fully evaluated before creating this thunk. If it was, then the implementation would be using call-by-value semantics (eager evaluation). The reference to $v1 means whatever the name $v1 means when the thunk is invoked, not when it's created. In the absence of mutation, the meaning of $v1 never changes and so there's no difference. This is why call-by-need doesn't interact well with mutation: it sneaks dynamic scope in through the back door.

If the observable difference between call-by-need and call-by-name implementations is undesirable, then the spec has to either specify what the "resolved values" are, concretely; or be more detailed about requiring either call-by-value or call-by-name (but not call-by-need) semantics.

There are two ways the difference could be observable:
a. The same message formats to a different string (without loss of generality I'm assuming "formatting to a string" rather than "formatting to parts" for the sake of this discussion) depending on the evaluation strategy.
b. For the same message, the formatter processes it with no errors under one evaluation strategy, but emits errors under a different evaluation strategy.

I'm assuming the spec has to be precise enough to rule out both (a) and (b).

The assumption about (b) is currently false, given the paragraph in Error Handling that I referenced in my previous comment.

Even with the single-assignment property, call-by-name and call-by-need are still distinguishable for messages in category (b) -- for example:

Example 8:

let $v1 = {$oops}
{{$v1} {$v1}}

In an implementation that emits all errors, call-by-name means this emits two "Unresolved Variable" errors since the body is equivalent to {{$oops} {$oops}}. Call-by-need means it only emits one error, since {$oops} is evaluated exactly once.

Maybe category (b) isn't important since the spec implies that implementations aren't required to report more than one error in a given message.

That's correct. For messages that include multiple errors, we do not specify which of them would be emitted, or really any errors beyond the first.

I'm assuming category (a) is important, since if two different implementations can format the same message with the same arguments and function registry (with observationally equivalent implementations of all the functions) to different strings and both be spec-compliant, that seems undesirable to me. But maybe that assumption isn't shared.

This I agree with, and that's why I've been trying to resolve our current ambiguity by clarifying the spec text as in #381 or my previous comment to make it clear how variable resolution works.

[...] The thunk created when evaluating $v2 contains a reference to the contents of $v1 -- {foo :func} can't be fully evaluated before creating this thunk. If it was, then the implementation would be using call-by-value semantics (eager evaluation).

My intent with our current spec language has been to enforce what I understand you refer to as "call-by-value", but this is admittedly unfortunately vague with respect to variable resolution. Specifically, regarding a declaration let $v2 = {$v1}, we have:

This is intended to mean that the variable $v1 is resolved to whatever value it holds without consideration of the current declaration or any later declaration, and that value is then assigned to $v2. After this declaration, the value of $v2 is no longer influenced by any potential changes in $v1, as the variable lookup has already taken place.

If the observable difference between call-by-need and call-by-name implementations is undesirable, then the spec has to either specify what the "resolved values" are, concretely; or be more detailed about requiring either call-by-value or call-by-name (but not call-by-need) semantics.

I think the simplest choice that does not prohibit mutability is to define the spec in terms of an eager call-by-value approach, while ensuring that a compliant implementation may choose to internally follow lazy call-by-name semantics instead. This is why the Error Handling includes the MAY statement about ignoring errors in unused variables.

Is anyone advocating that we should follow call-by-need semantics?

Thanks, @catamorphism, for the in-depth analysis.

I'm assuming, based on #299, that the formatting spec will eventually specify some form of lazy evaluation for local variables.

Perhaps we were too quick to dismiss eager evaluation. I just commented about this in #299 (comment).

I think the simplest choice that does not prohibit mutability is to define the spec in terms of an eager call-by-value approach, while ensuring that a compliant implementation may choose to internally follow lazy call-by-name semantics instead.

This sound reasonable to me.

(Sorry about the delayed reply, was on vacation)

This is intended to mean that the variable $v1 is resolved to whatever value it holds without consideration of the current declaration or any later declaration, and that value is then assigned to $v2. After this declaration, the value of $v2 is no longer influenced by any potential changes in $v1, as the variable lookup has already taken place.

I see what you mean now. In effect (according to the current spec), variable references must be resolved eagerly, but the implementation is free to choose whether function calls are evaluated lazily or eagerly. I wasn't considering that possibility when I was writing my previous comments, because I was assuming that either both are eager, or both are lazy.

I think the simplest choice that does not prohibit mutability is to define the spec in terms of an eager call-by-value approach, while ensuring that a compliant implementation may choose to internally follow lazy call-by-name semantics instead. This is why the Error Handling includes the MAY statement about ignoring errors in unused variables.

I agree that "define the spec in terms of an eager call-by-value approach" seems like the simplest choice. As far as allowing the implementation to internally follow lazy call-by-name semantics, it seems a little challenging for the implementation to actually do so. Maybe part of why it seems challenging to me has to do with the definition of "resolved value".

The "Function Resolution" section of the spec reads:

and:

This implies that the set of possible "resolved values" that defines what variable resolution may produce is the same as the set of possible values that can be passed to a function. For a lazy implementation -- that is, an implementation designed to take advantage of the "Resolution and Formatting errors in expressions that are not used in pattern selection or formatting MAY be ignored" clause -- this causes problems. To avoid making the comment thread too hard to read, I'll post subsequent comments with some code examples that show why.

Is anyone advocating that we should follow call-by-need semantics?

See #299 (comment) , although that comment hadn't been posted yet when you wrote your comment :)

Even without anyone advocating for call-by-need explicitly, my reasoning is that "Resolution and Formatting errors in expressions that are not used in pattern selection or formatting MAY be ignored" means some implementors may wish to ignore these errors. If you do wish to ignore those errors, you can either do dynamic analysis (which amounts to lazy evaluation) or static analysis. Static analysis seems quite challenging, since functions are opaque. That leaves lazy evaluation. In practice, lazy evaluation is implemented in a call-by-need way, since the cost of repeating the same computation multiple times usually exceeds the benefit of not computing values that aren't used. It's possible MessageFormat could be an exception to that if it's unusual for variables to be referred to more than once.

In this comment I want to address how "Resolution and Formatting errors in expressions that are not used in pattern selection or formatting MAY be ignored" could be realized in an implementation. Suppose I'm an implementor who wants to ignore all errors relating to unused expressions. Static analysis could address some, but not all of those errors: as long as no function calls are involved, I can detect unused variables with static analysis. But in an example like:

Example 9:

let $v1 = {:foo}
let $v2 = {$v1 :bar}
match {:quux}
when x {{$v1}}
when * {{$v2}}

I can't tell if $v2 is used without calling quux, so if both foo and bar can potentially error, that's out of the question.

So I'm left with lazy evaluation. Next I have to decide how much computation I want to do when processing a let-declaration. This is equivalent to the question of what the "resolved value" of a variable is, i.e. what "variable resolution" returns. The two options I can see are to (Option 1) delay the evaluation of the entire right-hand side until the left-hand side is referenced; or to (Option 2), as @eemeli suggested in #413 (comment), immediately evaluate variable references while delaying the evaluation of function calls. (Perhaps there are others.)

(Option 1 is compatible with either call-by-name or call-by-need, supposing immutability; Option 2 forces call-by-name, since it effectively means variables are substituted away, and I think it works with or without mutability, though I haven't thought that through.)

To be concrete, I'll step through evaluation for example 9 using both options; assume that all functions are defined to be constant functions that return their own names.

Option 1:

1. Bind v1 to a closure that (in effect) contains the code {:foo}.
2. Bind v2 to a closure that contains the code {$v1: bar} and an environment mapping the name v1 to either the closure created in step 1 (call-by-name) or a mutable slot containing that closure (call-by-need). (The environment is necessary if we allow name shadowing.)
3. Call quux, which by assumption returns "quux".
4. Resolve {{$v2}}, since the * variant matches the result:
   1. Resolve the value of the operand, here $v1. In option 1, resolved values are closures. A closure is an internal implementation-specific structure and it can't be passed to the function bar as-is. So the implementation here has to depart from the "Function Resolution" spec as written: while the resolved value of $v1 is the closure created in step 1 (call-by-name) or a mutable reference to that closure (call-by-need), the "resolved value" that needs to be passed to bar is the result of evaluating that closure.
   2. Supposing there are two different meanings of "resolved value" (one that's the output of variable resolution, and another that's the input to functions), evaluate {:foo} by following the "Function Resolution" section of the spec. By assumption, it returns "foo".
   3. Evaluate the call to bar with "foo" as the resolved value of the operand, also by following "Function Resolution".

Option 2:

1. Bind v1 to a closure that (in effect) contains the code {:foo}. (as in Option 1)
2. Resolve the reference to v1 in {$v1: bar}. The resolved value is the closure created in step 1.
3. Bind v2 to a closure that (in effect) contains the code {{:foo} :bar} This is not valid MessageFormat syntax, so the implementation needs to have its own internal language to represent "partially evaluated" messages.
4. Call quux, which by assumption returns "quux". (unchanged)
5. Resolve {{$v2}}, since the * variant matches the result: (unchanged):
   1. The name v2 resolves to the closure created in step 3, representing {{:foo} :bar}. As in step 4.1 in option 1, this "resolved value" can't be passed to the function bar, so it the closure has to be evaluated. Here, we can't evaluate it by following the spec, since {{:foo} :bar} is not a valid message. Whatever is done to relate {{:foo} :bar} to a resolved value is implementation-specific.
   2. At least in this example, it's fairly obvious what to do: resolve the operand by calling foo, which returns "foo" (by assumption).
   3. Evaluate the call to bar with "foo" as the resolved value of the operand, by following "Function Resolution".

Stepping back:

1. In "Function Resolution", is the "resolved value" of an operand the same as the "resolved value" that can be passed to a function?
   1. If yes, this means that both options 1 and 2 can't be implemented in a spec-compliant way, since both of these require resolving an operand to something that is not a "resolved value" per the spec.
   2. If no, then I think the spec needs to make it clear what "resolved value" means in each context where that term is used.
2. How does the implementation internally represent the meaning of a variable?
   1. In eager evaluation (not shown here), it's simple: a variable is bound to its "resolved value" as per "Variable Resolution" in the spec.
   2. In lazy evaluation with option 1, a variable is bound to a closure. The code "inside" the closure is conceptually just a MessageFormat expression.
   3. In lazy evaluation with option 2, a variable is also bound to a closure, but the code "inside" the closure is not a MessageFormat expression.

I understand why the spec leaves the term "resolved value" abstract, but I think it's hard to reason about whether a lazy implementation complies with the spec if such an implementation can't plug in the same definition of "resolved value" everywhere that phrase is used in the spec.

Also, an implementation that follows option 2 (eager variable resolution, lazy function resolution) has to pick a representation for "partially evaluated" expressions, which is neither the "resolved value" as currently used in the spec, nor a structure containing a valid MessageFormat expression and possibly an environment providing values for any of its free variables. I suppose this could be done, but it also seems like this would make reasoning about spec compliance difficult.

So my two closing questions are:

• Should the clause "Resolution and Formatting errors in expressions that are not used in pattern selection or formatting MAY be ignored, as they do not affect the output of the formatter" just be removed from the spec? How helpful is it to say that implementations may do this if it's impractical to realize?
• Should the spec be changed to be more concrete about what the meaning of "resolved value" is? This likely requires a commitment to eager evaluation, which influences the answer to the first question.

I also have a separate question about how to handle resolution errors in a lazy implementation that uses what I called "option 2" in my previous comment (eager variable resolution / lazy function resolution).

Example 10:

let $v1 = {$oops :bar}
let $v2 = {$oops1}
let $v3 = {:foo}
match {$v3}
when foo {{$v1}}
when * {{$v2}}

Stepping through evaluation again (suppose foo is a function that always returns "foo", as in my previous comment):

1. Evaluate {$oops: bar} by first evaluating $oops, which is undefined, so bind v1 to the "fallback value" as per step 1 of "Function Resolution".
2. Bind v2 to a fallback value as well, since $oops1 is also undefined.
3. Bind v3 to a closure, as before.
4. Evaluate {$v3}, forcing the closure and resulting in "foo"
5. Select the first variant and (omitting some details) call the function bar on the value of v1, which is the fallback value.

The question is how to ensure the resolution error for oops is reported, but not the resolution error for oops1. If we use the same definition of "resolved value" everywhere, then the implementation needs some way of tracking when fallback values are actually used. I can imagine ways to do that, but it seems simpler to me if the resolved value of an expression is a set that includes a distinguished "error" symbol, which the implementation can check for in order to emit the error before calling the function. This symbol should be internal to the implementation and not be in the set of resolved values that can be passed to a function, since the spec already requires the fallback value to be passed into the function.

This problem doesn't arise either with fully lazy evaluation (option 1), since variables are only resolved when they're used and the error can be emitted immediately.

I agree that "define the spec in terms of an eager call-by-value approach" seems like the simplest choice. As far as allowing the implementation to internally follow lazy call-by-name semantics, it seems a little challenging for the implementation to actually do so. Maybe part of why it seems challenging to me has to do with the definition of "resolved value".

To make sure for myself that it's not too challenging, I went ahead and updated my polyfill implementation to resolve variables as follows:

During a formatting call, a scope: Record<string, unknown> is constructed from the message parameters, and the declarations. During construction, each declaration is wrapped up as an UnresolvedExpression that retains its source expression and the current scope. If a name is re-used, then we create a new scope for later declarations and the message body.

Later during the call, when we are resolving a variable, we check if our scope value for it is an UnresolvedExpression. If so, we resolve it using its own scope and update the value for it in our scope.

I also added a small bunch of test cases for the above.

So I'm left with lazy evaluation. Next I have to decide how much computation I want to do when processing a let-declaration. This is equivalent to the question of what the "resolved value" of a variable is, i.e. what "variable resolution" returns. The two options I can see are to (Option 1) delay the evaluation of the entire right-hand side until the left-hand side is referenced; or to (Option 2), as @eemeli suggested in #413 (comment), immediately evaluate variable references while delaying the evaluation of function calls. (Perhaps there are others.)

Option 2 is not quite what I had in mind: We don't need to resolve the variables immediately, if we can later resolve them with the values they ought to have in their position. Hence the scope that I include in the UnresolvedExpression.

Should the clause "Resolution and Formatting errors in expressions that are not used in pattern selection or formatting MAY be ignored, as they do not affect the output of the formatter" just be removed from the spec? How helpful is it to say that implementations may do this if it's impractical to realize?

Removing that would force implementations to always eagerly resolve all expressions and to complain about any errors in them. As I hope my code demonstrated, I don't think it's impractical.

Should the spec be changed to be more concrete about what the meaning of "resolved value" is? This likely requires a commitment to eager evaluation, which influences the answer to the first question.

I don't think that's necessarily relevant here. A key part of what I'm seeking to achieve here is a spec that can be reasoned about as if the execution was eager, but still provides space for an implementation to process lazily. A key part of that (and the overall topic here) is that the shape of a declaration is unobservable except when a selector or pattern expression includes a variable reference for it. When we need to resolve that expression, then we need a "resolved value" representation of the variable's value.

That unobservable space is where I get to introduce my UnresolvedExpression, which I then resolve when it's required, but no earlier.

The above dialog is a deep dive in the assessing the feasibility of mutability--more of a "How would we do", rather than a "should we do it".

Are there practical, compelling use cases for mutable variables? By compelling, I propose a subjective (& surely not to be agreed by all) threshold to be:

• authoring a class of MF2 messages is not achievable without mutability
• authoring a class of MF2 messages without mutability creates an arduous burden on the author in greater than 1 in 1000 message creation cases, where arduous may loosely be defined as doubling the mental burden or labor duration in furnishing the message

I know this is 🎨 , but I personally do not find the hypotheticals in #310 compelling, nor do I posit that they'd satisfy my self-authored self-declared thresholds.

My vote is for immutability at current time.

To make sure for myself that it's not too challenging, I went ahead and updated my polyfill implementation to resolve variables as follows:

[snip]

I think I understand what your code is doing (basically, the dynamic equivalent of the desugaring + unique renaming I outlined in #413 (comment) -- if I follow it correctly, https://github.com/messageformat/messageformat/blob/6656c95d66414da29a332a6f5bbb225371f2b9a3/packages/mf2-messageformat/src/messageformat.ts#L85 effectively introduces a new name on the fly anytime a variable is redefined). As I said initially, that transformation is semantics-preserving as long as we avoid call-by-need (in other words, as long as we don't memoize.) It looks like your code does memoize results for variables directly referenced in the message body, just not for variables referenced on the right-hand side of a let-declaration, which should work fine since lexical and dynamic scope are always the same within the message body.

In fact, your code would probably be able to memoize all results if you did the unique renaming as a separate pass rather than interleaved with evaluating the declarations. This is what I said in an earlier comment (call-by-need works with no surprises as long as the single-assignment property holds.)

Option 2 is not quite what I had in mind: We don't need to resolve the variables immediately, if we can later resolve them with the values they ought to have in their position. Hence the scope that I include in the UnresolvedExpression.

Equivalently, according to lexical scope. What you call a scope in the code would usually be called an "environment", but it's clear enough.

Removing that would force implementations to always eagerly resolve all expressions and to complain about any errors in them. As I hope my code demonstrated, I don't think it's impractical.

The reason I thought it was impractical was that I was assuming that the environment (what your code calls a scope) maps variables onto resolved values. As your code shows, the values that the environment maps variables onto are not necessarily the same as what the spec calls a "resolved value". So that assumption on my part was wrong, and Option 1 is straightforward to implement as long as variables are immutable and are either eagerly evaluated, or not memoized (i.e. we use call-by-value or call-by-name). Option 2 is irrelevant -- I thought you were suggesting doing that in order to achieve mutability. But it looks like by "mutability" you mean syntactic sugar for immutability with name shadowing. (If I'm misunderstanding there, let me know.)

I say that it's syntactic sugar because your environment maps variables onto immutable values, not onto mutable slots containing values. So, I'm not sure that this issue is actually asking a different question from "should name shadowing be allowed?"

I wouldn't think of my approach as dynamic renaming, but it's mostly equivalent. The way I think of it, a rename is creating a "scope boundary" (Sorry, no idea what a proper-er name might be), with the memoization always being limited to one side of the boundary. So if we have a message like

let $x = {13}
let $y = {$x}
let $x = {$y}
let $z = {$y}
{{$x}{$z}{$y}}

then we end up with two scope objects existing during the runtime:

const a = {
  x: Unresolved(Literal('13'), a),
  y: Unresolved(Variable('x'), a)
}
const b = {
  x: Unresolved(Variable('y'), a),
  y: Unresolved(Variable('x'), a),
  z: Unresolved(Variable('y'), b)
}

of which we use b for formatting the pattern. Taking that step by step, after resolving {$x} we have:

a = { x: '13', y: '13' }
b = {
  x: '13',
  y: Unresolved(Variable('x'), a),
  z: Unresolved(Variable('y'), b)
}

where y is memoized only in scope a.

Then, after also resolving {$z} everything is memoized:

a = { x: '13', y: '13' }
b = { x: '13', y: '13', z: '13' }

So the let RHS expressions do mostly get memoized as well, just not necessarily all in the same scope as what we're using for pattern or selector resolution.

I did also consider dynamic renaming so everything could end up in the same scope and e.g. y would not need to get resolved twice as above, but I couldn't think of a way to do it that wasn't significantly heavier than this approach, where most messages do end up with just one scope.

@eemeli In your comment above, you've described an implementation of immutable variables with name shadowing and memoization (lazy call-by-need semantics). The issue is about mutability, so I think if we agree that we want immutability, and the issue at hand is whether to allow name shadowing, we can close this issue and continue discussing name shadowing on #310.

To be clear about what I mean by that, I drew a diagram:

Above the green line, the diagram shows the runtime state when processing the following declarations, in the hypothetical syntax:

set $x = {13}
set $y = {$x}
set $x = {$y}

Below the green line, the diagram shows the runtime state when processing the following declarations, in the existing syntax:

let $x = {13}
let $y = {$x}
let $x = {$y}

Both diagrams assume a standard kind of evaluator based on an environment and a store. An environment maps variable names onto locations. A store (sometimes called a "heap") maps locations onto runtime values. A runtime value can either be a thunk (what you call an Unresolved above) or a value. This is not that different from your approach; what you're calling a "scope" is more traditionally called an environment. Your implementation doesn't need a separate store since it doesn't handle mutable variables.

Starting above the green line (mutability):

1. set $x = {13}: In the store, create a mapping from a fresh location L to a thunk (the purple box containing the text "13"). Extend the global environment with a mapping from x to L. In the picture I've linked x's mapping in the environment to the thunk with an arrow; the arrow symbolizes L.
2. set $y = {$x}: In the store, create a mapping from a fresh location L1 to a thunk (the purple box containing the text "$x"). Extend the global environment with a mapping from y to L1.
3. set $x = {$y}: In the store, overwrite location L with a new thunk (the purple box containing the text "$y"). The environment does not need to be extended because the name x is already mapped to a location.

Note the state of the store after the third line of code: the thunks for $x and $y form a cyclical structure, so if either $x or $y is referenced in the body of the message, evaluating it will not terminate. This happens because the third set construct mutates location L.

Below the green line (name shadowing):

In the presence of name shadowing, each thunk is actually a pair of a pointer to code (equivalently, to an AST node) and a pointer to an environment. With mutability, there was no need for the environment pointers. We could just use one global environment, since there was no name shadowing. Here, each thunk points to its own local environment.

This should look familiar to you since it's almost exactly what your implementation is doing. You implemented an additional optimization that basically re-uses the global environment instead of creating a new environment for each thunk, except when a name is shadowed. For simplicity, I'm not showing that optimization (or others, like immediately evaluating 13 instead of allocating a thunk for it), but otherwise it's the same approach with a few different terms.

1. let $x = {13}: In the store, create a mapping from a fresh location L to a thunk. The thunk has code 13 and an empty environment, since it has no free variables. Extend the global environment with a mapping from x to L.
2. let $y = {$x}: In the store, create a mapping from a fresh location L1 to a thunk. The thunk has code $x and a local environment that maps the variable x to the location L. Extend the global environment with a mapping from y to L1.
3. let $x = {$y}: In the store, create a mapping from a fresh location L2 to a thunk. The thunk has code $y and a local environment that maps the variable y to the location L1. Extend the global environment with a mapping from x to L2. This overwrites the previous mapping in the environment for x, but the only change to the store is the new mapping for L2.

Note the different state of the store at the end: the thunk for $x points to the thunk for $y, which points to the thunk that was allocated for the outer use of $x. There are no cycles and if either $x or $y was evaluated in the message body, its value would be 13. Unlike in the mutable model, where the third declaration changed the contents of L, here, no location is ever overwritten with a thunk that has different code.

I hope this shows the difference between mutability and name shadowing, and the reason to reject mutability if memoization is desirable. I've assumed throughout that when we're talking about mutability, we don't just mean whether the keyword is spelled let or set, but about different semantics.

(The model I'm using is loosely based on on section 4.2.2 of The Structure and Interpretation of Computer Programs (second edition), but the underlying interpreter they use has a lot of complications that don't apply to a language without nested lets.)

With mutability defined as above (yes, the diagram does help), I'd be happy to also conclude that we don't want it, and that this issue may be closed.

On name shadowing we can continue in #310.