assignment2.md

Assignment 2

interpreter.py

How does --trace work?

The structure resembles a tree where each node has properties: name, execution_time and children

Two global variables are important: current_frame and trace_root

• trace_root marks the entry point into the tree is in the beginning always set to: {"name": "main", "execution_time": None, "children": []} ⇒ making main the frame at depth 0 and marking all successive calls as children of main
• current_frame points to the children array of the current frame

If the global flag TRACING_ENABLED is set, do_call and do call set_frames , passing the name of the called function

• In the case of do (non-user-defined functions), it is checked whether the function is whitelisted or not (only print is whitelisted)

set_frames constructs a new node for the tree (only explicitly setting name because time is not yet known and new node does not (yet) have children)

• It appends the new node to current_frame
• It stores current_frame and overrides it with the (empty) children property of the new node ⇒ Allows for nested calls
• It returns the new node plus the copy of the overwritten current_frame

do and do_call calculate and set the execution time of the new node

After the call has finished, reset_frames is called with the “last” current_frame, resetting the global current_frame to that pointer

Explain this code snippet

def parse_args(argv=None):
  p = argparse.ArgumentParser()
  p.add_argument(
    "--trace",
    action="store_true",
    help="Print a function-call trace with timings",
  )
  p.add_argument("--log_envs", action="store_true", help="Print envs at end of program")
  p.add_argument("filename", help="Program file to run (.lgl)")
  return p.parse_args(argv)

• argsparse.ArgumentParser() builds an object that knows how to read and validate CLI arguments. It automatically provides h/--help output.

• Three arguments are defined

  • --trace and --log_envs both of which are optional
    • The action=store_true sets args.trace and args.log_envs to True or False depending whether or not the flags were provided
  • Positional argument filename which is not optional (no action=store_true provided)

    • Positional arguments are provided without leading dashes

    • They are identified by their position in the program call whereby non positional arguments do not count towards their position:

      python interpreter.py --trace hello.lgl

      python interpreter.py hello.lgl --trace

      are equivalent

• Finally, the return value of p.parse_args(argv) is used to set global flags TRACING_ENABLED and LOG_ENVS

How is scoping handled in the interpreter?

Structure: Environment variables are tracked via a stack of dicts called envs

Scoping is done dynamically: envs_get finds the most recent definition of a variable in the stack ⇒ this means that functions can access variables which lexically are outside their scope. You could say that every defined variable (outside the call of a user-defined function) is global and lives forever. For example: everything defined inside a seq or a while will add to the global envs dict and live there forever while in lexical scoping, variables defined inside these blocks would be lost after they have finished

• BUT there is a scoping mechanism built in: when calling user defined functions, a new frame is added to envs which only is available during the function call (popped afterwards). This means that labels and their values inside the body of user defined functions are only visible during their execution
  • But as long as the function is running, the variables are visible, so nested functions can see the parameters of their parent functions

⇒ globals persist for the whole run; locals (defined inside user-defined functions) persist only for the duration of a call; and name lookup is dynamic across the call stack (= simply finding most recent implementation)

Explain this line: op = ALIASES.get(program[0], program[0])

• This is a fallback ⇒ If program[0] is present in ALIASES, the respective value for they key is assigned to op
• If the key program[0] is not present in ALIASES, op = program[0]

Explain this block at the top of do:

try:
  return env_get(program, envs)
except AssertionError:
  pass

It allows for evaluating strings as variable names:

# This works (if x was previously defined)
["add", "x", 1]

# Makes this redundant:
["add", ["get", "x"], 1]

• Important: Only bare strings are evaluated! One could think that because the block is at the top of do, whole expressions like ["add", "x", 1] could be looked up in envs (which would be really bad), this is not true because envs_get asserts that program is a bare string

• But our implementation does have a problem: envs_get returns an assertion error in two cases:

  1. The passed in parameter is not a string
  2. The string was not found in envs, meaning that the variable was not defined

• But our implementation catches and suppresses both assertion errors, so there is no distinction between variable not found (breaking, program should stop) and looking up a non string literal (expected)

  • This means that if we do something like this:

  # Hello not wrapped inside quote
  ["print", "hello"]

  • The program looks up “hello” in envs and does not find it → we suppress the raised error by envs_get and search program[0] in the OPS dict (we have a missing assert(program, list) guard there) ⇒ Program will error with “Unknown operation ‘h’” because program[0] == "h"
  • This is unexpected behaviour. What we should’ve done is:

  # Only evaluate string literals
  if isinstance(program, str):
    return env_get(program, envs)   
    
  # No catch: not found variables should raise!

Explain the need for quote in the code

Quote allows strings to be treated as data rather than variable names. For example: because we look up all string literals in do at the beginning, "hello" is evaluated as a variable name in ["print", "hello"]

• With quote, we can do: ["print", ["quote", "hello"]] and treat “hello” as a normal string