First version of interpreter

[jeshecdom]

Towards #512 and #455.

It supports expressions and statements. Specifically:

• Calls to module-level functions without attributes (including recursive calls). Unsupported attributes: native, inline, extends, mutates
• Reference to module-level constant declarations and declared local variables.
• All expressions supported by the constant evaluator. In fact, I refactored the constant evaluator and moved all its code into the interpreter, since the constant evaluator is basically an expression interpreter (otherwise I was producing a lot of code duplication, and moving the code to the interpreter I have more control, instead of having the code in two separate files.).
• All the following statements: simple and augmented assignments (but only for identifiers as path expressions), let, conditions, repeat, do-until, while, return. Unsupported: simple and augmened assignments for more complex path expressions, try/catch, foreach.

The interpreter assumes that before calling the interpreter, the user has executed the typechecker. The interpreter relies on CompilerContext to extract declarations.

• [ ] I have updated CHANGELOG.md
• [ ] I have documented my contribution in Tact Docs: https://github.com/tact-lang/tact-docs/pull/PR-NUMBER
• [X] I have added tests to demonstrate the contribution is correctly implemented: this usually includes both positive and negative tests, showing the happy path(s) and featuring intentionally broken cases
• [X] I have run all the tests locally and no test failure was reported
• [X] I have run the linter, formatter and spellchecker
• [X] I did not do unrelated and/or undiscussed refactorings

[anton-trunov]

Let's also have a negative test for the case when a let-binding shadows a let-binding:

let x = 42;
let x = 43;

[anton-trunov]

To perform that test you might need to turn off the typechecker.

[jeshecdom]

Let's also have a negative test for the case when a let-binding shadows a let-binding:

let x = 42;
let x = 43;

Currently, the interpreter will simply overwrite the variable in the runtime environment because it was relying on the typechecker. And actually, I rely on runtime shadowing of local variables for certain uses cases, for example, for modelling recursion in a simple manner. Suppose the following recursive function:

fun foo(v: Int) {
   if (v == 0) {
      return;
   }
   foo(v - 1);
}

And suppose foo(4) is called.

The environment stack will look as follows just before foo finishes execution (the arrows point to their parent environment in the stack):

v = 4   <------  v = 3  <-------- v = 2  <-------- v = 1  <------ v = 0

As you can see, local v is being shadowed by the children environments. If I add local variable shadowing checks when a variable is declared, I would need to add special cases for recursion in order to allow the above behavior, and for this, I would need to add state in the environment stack to know if I am currently in a recursive call (probably I will need to add some map telling me the names of all currently called functions in the stack: if I am going to add debugging features in the future, probably I will need to add this anyway, since the debugger needs to show a calling stack).

But regarding the shadowing checks, I am starting to get worried that the interpreter will do code duplication for certain checks done by the typechecker. Do you think the interpreter should call the typechecker before the interpreter executes each command? Probably this is a case of turning on and off the typechecker monad in the collecting semantics? I am not sure how to proceed here.

[anton-trunov]

The case of modeling recursion looks more than reasonable, let's rely on the typechecker for this. Also, let's document your reasoning somewhere as a design decision comment, this is really useful.

Btw, we have scoping test files prefixed with var-scope-, it would be nice if you checked we are not missing some corner cases there, given that you are relying on those static checks.

[jeshecdom]

The case of modeling recursion looks more than reasonable, let's rely on the typechecker for this. Also, let's document your reasoning somewhere as a design decision comment, this is really useful.

Would it be ok if I document this recursion behavior in the code itself? I will also add comments in the Interpreter class itself, saying that you should call the typechecker before calling the interpreter and pass to the interpreter the CompilerContext that the typechecker manipulated.

[jeshecdom]

.... you should call the typechecker before calling the interpreter and pass to the interpreter the CompilerContext that the typechecker manipulated.

The reason for passing the CompilerContext of the typechecker to the interpreter is that the interpreter should also work on code that the interpreter did not execute itself (this is the use case for the partial evaluator). For example, in this code (I marked inside square brackets [ ] the places where the interpreter gets called to simplify expressions):

const C: Int = [1];

contract TestContract {

   get fun test(): Int {
      return [C + 1];
   }
}

When the interpreter gets called in the brackets, it does not know what other code is surrounding those brackets, because the interpreter did not execute the code outside the brackets. Hence, it relies on the typechecker to receive the CompilerContext that includes the declarations in the code (the constant C for example).

Another use case is when the interpreter gets called in a REPL. In this case, it knows the entire code, but I think it just should call the typechecker on the given code and then attempt the interpretation.

[anton-trunov]

Got it, thanks for clarifying it. Documenting it would be highly appreciated!