How is the lexical definition implemented?

Question

A few years ago, I started writing an interpreter for a small domain-specific language that included user-defined functions.

First, I implemented a variable scope using a simple stack of character tables. But now I want to move on to the correct lexical scope (with the possibility of closure). Can someone explain or point me to a good explanation of the data structure and the lexical sphere algorithm?

Answer 1

To get the correct lexical reach and closures in the interpreter, all you have to do is follow these rules:

• In your interpreter, variables are always scanned in the environment table passed by the caller / saved as a variable, and not some global env-stack. That is, eval(expression, env) => value .
• When the interpreted code calls the function, the environment is NOT passed to this function. apply(function, arguments) => value .
• When an interpreted function is called, the environment in which its body is evaluated is the environment in which the definition of the function was defined, and has nothing to do with the caller. Therefore, if you have a local function, then this is a closure, that is, a data structure containing the {function definition, env-at-definition-time} fields.

To extend this last bit in the Python-ish syntax:

 x = 1 return lambda y: x + y 

performed as if he

 x = 1 return makeClosure(<AST for "lambda y: x + y">, {"x": x}) 

where the second dict argument can only be current-env, not the data structure built at this time. (On the other hand, saving all env, not just private variables, may cause a memory leak.)

Answer 2

There are many ways to implement lexical reach. Here are some of my favorites:

• If you don't need ultra-fast performance, use a purely functional data structure to implement your symbol tables and imagine a nested function as a pair containing a pointer to a code and a pointer to a symbol table.

• If you need speed with your own code, my favorite technique is described in Creating Fast Curry by Simon Marlow and Simon Peyton Jones.

• If you need native code speeds, but cardinal functions are not that important, consider closing closure style .

Answer 3

Read For example, to implement Lua 5.0 .

Answer 4

There is no single right way to do this. It is important to clearly articulate the semantics that you want to provide, and then the subsequent data structures and algorithms.

Answer 5

Stroustrup implemented this in the first C ++ compiler with just one symbol table for each scope and a chaining rule that follows the areas until a definition is found. How it works exactly depends on your exact semantics. Make sure you nail them down.

Knuth in the Art of Computer Programming, Volume 1, provides an algorithm for the Cobol character table, in which the scope is determined by reference.