Tsonnet #22 - Fixing a "lazy" bug

Fixing Tsonnet's lazy evaluation inconsistency in objects

Welcome to the Tsonnet series!

If you haven't been following the series so far, you can check out how it all started in the first post of the series.

In the previous post, I implemented local variables scoped to objects:

Tsonnet #21 - Making object definitions more dynamic

While writing, I realized that Tsonnet wasn't interpreting local variables within objects in a lazy-evaluated manner. This is inconsistent with the properties of the language, so let's fix it!

Photo by Luis Villasmil on Unsplash

The inconsistency

Let's add a slightly smaller version of the Jsonnet tutorial file introduced in the previous post:

This is perfectly parsed and interpreted, both by Jsonnet and Tsonnet:

Now let's move the pour local variable declaration after its usage:

This currently fails in Tsonnet:

I wrote earlier in Tsonnet 16 - Late binding and Jsonnet inconsistency about how Jsonnet evaluates local variables top to bottom. Funnily enough, Jsonnet has no problem whatsoever in interpreting this file:

I was definitely not expecting this, but I'll take it -- this is what we would expect in an object-oriented language anyway.

Let's update the variables.t cram tests to capture this with the expected results:

Now to the implementation.

Interpreting late binding within objects

We must first interpret the ObjectExpr entries. These hold the Local expressions that will add the variables to the environment. The ObjectField entries will be added to the environment for later interpretation:

Adding local variables to the environment with names that were previously added overrides the outer scope -- a concept called shadowing in programming language design. With the current Env implementation and its purely functional semantics, it never destroys or updates the environment, it always generates a new one within the local scope, while the outer scope remains untouched.

For object fields, however, we must be careful not to override locally scoped variables when adding fields to the environment. Here's where the obj_id comes into play. Local bindings are only identified by their names in the local scope, but we can have object fields that have the same name of local variables, but they shouldn't override local bindings when added to the environment. To mitigate this, we must have a unique identifier for every single object, and their attributes will be scoped to that ID.

Only after adding local bindings and fields to the environment can we interpret all ObjectField entries in the object:

This strategy is similar to the type-checking method I used for checking invalid cyclical references, where we fill the environment with references and then dig in until we reach the bottom of the evaluation chain. The translation of objects by the type checker does exactly that too. It has been extracted to the function translate_object:

After type-checking, we reset the environment, so the interpreter gets a clean slate to work with:

Now to the lib/env.ml file changes. Starting with the new env_id type Id module:

1. We don't want to confuse regular ints with unique IDs generated by the environment, so we type our newly generated IDs as EnvId.

2. The new Id module encapsulates the ID generation and reset through the ref counter.

3. It will fail if it hits the maximum integer ceiling. This can be worked around in multiple ways, but I want to keep it as simple as possible for now. It's unlikely to max out 64-bit integers (2^62 - 1), to say the least.

And the helper functions:

1. add_local is just a helper function providing more semantic meaning than the previous Env.Map.add. This makes it clear that we are dealing with local variables only.

2. add_obj_field makes use of another helper function, uniq_field_ident, that will get the obj_id and merge with the field name, and then we use it to add to the environment.

3. get_obj_field reuses find_var to retrieve the value for the ObjectField given its obj_id.

Invalid local binding cycles

We should expect invalid local binding cycles within objects to be treated as usual "invalid binding cycles":

The cram test captures it:

Conclusion

With this implementation, Tsonnet now properly handles lazy evaluation of local variables within objects, bringing it in line with Jsonnet's behavior. This fix ensures that local variables can be referenced before they're declared within an object, making Tsonnet's evaluation model truly consistent with its lazy evaluation principles.

The entire diff can be seen here.

---