CSC 533: Programming Languages
Spring 2022

HW3: Implementing Scopes

In the HW2 version of the SILLY interpreter, all of the variables in a SILLY program were treated as being in the same, global memory space. The first time a variable was assigned a value, an entry was stored for that variable and any subsequent reference to that variable would access that same entry. While this simple model works fine for regular variables, it causes problems once constants are introduced. Recall that a constant declaration creates a variable that cannot be reassigned once it is initialized. Consider what happens when a constant declaration is placed inside a loop:

repeat 3
    const x = 10
    output ( x )
end

During the first pass through the loop, the constant x is declared, initialized, and displayed. However, the second pass produces a runtime error, since the variable x already exists when the constant declaration is executed again. In most languages, control structures such as repeat, while and if define new scopes. Variables (including constants) that are declared within the structure are considered local to that scope. The lifetime of such a variable begins when its declaration is reached and ends when the enclosing scope ends. Using scopes, the above example would execute without error, since each pass through the loop would define a new scope and so no conflicts would occur.

For this assignment, you are to extend the SILLY intepreter so that each control structure (if, while, repeat) defines a new scope. In addition you will define a new statement type for local variable declarations. Any variable that is explicitly declared inside a control structure, using either a const or local declaration, belongs to the scope defined by that structure. That means it exists only while executing that scope and it disappears after the scope is finished. For example, consider the following code segment: 

x = 100
if ( x > 0 )
    const x = 200
    if ( x > 100 )
        local x = 300
        output ( x )
    end
    output ( x )
end
output ( x )

This code segment defines three nested scopes. The global scope encompasses everything and includes any variables that are not explicitly declared (using const or local). As such, the first assignment statement assigns a value to x in the global scope. The if statement defines a scope that contains the constant x. Within that scope, a nested if statement defines an additional scope, in which local variable x is declared. When evaluating expressions in SILLY, static scoping is used. Thus, if a variable is declared within the current scope, the corresponding value should be accessed. If it is not declared in the current scope, the enclosing scope should be checked next, then the scope that encloses that scope, etc.

To implement nested scopes, you will need to modify the MemorySpace class so that a stack of scopes (variable/binding maps) is maintained (as opposed to a single, global scope/map). New methods should be added to the MemorySpace class for beginning a new scope (i.e., pushing it on the stack) and ending the current scope (i.e., popping it off the stack). When the statements in a control structure are executed, a new scope should begin so that any local variables or constants declared within are stored within that scope. When execution ends, that scope should end, removing any local variables/constants. Note that variables that are assigned a value without being declared are assumed to belong to the global scope (as before), and so persist once they are assigned. The methods for declaring, storing, and looking up variables in the memory space will also need to be modified so that they access and modify the appropriate scope in the runtime stack.

SAMPLE CODE (output in red) 
  >>> x = 100
  >>> repeat 3
          const x = 10
          output ( x )
      end
  10
  10
  10 
  >>> output ( x )
  100 
  >>> repeat 3
          local x = 10
          x = ( x * 2 )
          output ( x )
      end
  20
  20
  20 
  >>> output ( x )
  100 
  >>> if ( x > 0 )
          const x = 200
          if ( x > 100 )
              local x = 300
              output ( x )
          end
          output ( x )
      end
  300
  200 
  >>> output ( x )
  100 
  >>> if true
          const vbl = "foo"
          output ( vbl ( vbl + vbl ) )
      end
  foo foofoo 
  >>> vbl = 99
  >>> output ( vbl ( vbl + vbl ) )
  99 198 

  >>> i = 1 
  >>> while ( i <= 8 )
          local sum = 0
          local j = 1
          while ( j <= i )
              sum = ( sum + j )
              j = ( j + 1 )
          end
          output ( i  sum )
          i = ( i + 1 )
      end
  1 1
  2 3
  3 6
  4 10
  5 15
  6 21
  7 28
  8 36    
  >>> global1 = 100
      repeat 2
          const localConst = 200
          local localVar = 300
          global2 = 400
          if ( localConst > 0 ) 
              local localVar = 500
              global1 = ( global1 + 1 )
              global2 = ( global2 + 1 )
              if ( global2 > global1 ) 
                  global3 = ( global1 + global2 )
              end
              output ( localConst localVar global1 global2 global3 )
          end
          output ( localConst localVar )
      end
output ( global1 global2 global3 )
  200 500 101 401 502 
  200 300 
  200 500 102 401 503 
  200 300  
  >>> output ( g1 g2 g3 )
  102 401 503