Lua language context/scope implementation

Question

I am implementing a Lua interpreter in C# and I've stumbled across a performance issue, which I assume it is caused by incorrect design: in my implementation, scopes are arranged in a hierarchical manner, that is, each scope has a parent scope which may or may not be null; each time a variable is being set or requested the scope checks whether the specified variable is contained in it. If not, asks its parent to do the same or, if there is no parent, it creates it / returns nil. The problem is that scopes use Dictionary<string, LuaObject> underneath, and Get / Set functions are recursive. Is there a better way to do it? I've been thinking about different approaches, and I've found this one, which is not very elegant nor sounds efficient (inspired by both V8 and C# closures):

Use types and fields as variables.

• Everytime you request a variable which was not previously declared, create a new type using Reflection that inherits the previous one.
• If a function is declared, check whether it uses a variable declared in a outer scope. If so, re-create a field in that type and make the outer variable point to the new one. (I know this point is explained really awfully, but it is nothing but the standard way C# closures are implemented. You can go and read that if you didn't understand)

Are there simpler / more elegant solutions? How is Lua internally implemented?

Answer 1

The way it's done in the reference implementation, and in many other implementations of similar languages: At compile time,

• Figure out at compile time which name refers to which scope.
• For each scope (except global), enumerate the variables and assign an index to each.
• Instead of mentioning the variable names in the bytecode, use the indices from the previous step.

Then during execution,

• Store the values of the locals in an array (per activation record). Read and write opcodes carry the necessary index.
• Implement globals like a Lua table (and get nil for missing variables for free).

This is much simpler, easier, and portable than mucking around with dynamically created types. It may even be faster, but certainly won't be much slower.

Closure support is mostly orthogonal. So-called upvalues refer to (a slot in) the locals array while it's still alive, and adopt the closed-over value when the locals array dies. You could do something similar with your original design. For correctness, you must take care to only create one upvalue per closed-over variable and to flatten closures. As an example, g in the below code must also close over x so that it still exists by the time the h closure is created:

function f()
  local x = 1
  function g()
    function h()
      return x
    end
    return h
  end
  return g
end

print(f()()())