CSC 533: Programming Languages
Spring 2020

HW4: Implementing Subroutines

The SILLY interpreter you wrote for HW3 extends the original version to allow for local variables and nested scopes. For this final SILLY assignment, you are to extend the language further by implementing simple subroutines (without return values).

In order to implement simple subroutines, you will need to define two new classes, a subDeclaration class for declaring a subroutine and a subCall class for calling a subroutine. The grammar rules for these new statements are:

<subdecl> --> 'sub' <identifier> [ <identifier> { ',' <identifier> } ] ':' { <statement> } 'end' <subcall> --> 'call' <identifier> [ <expression> { ',' <expression> } ] ';'

Note that a subroutine declaration specifies the name of the subroutine, an arbitrary number of parameters (separated by commas), and the statements that make up that subroutine. A subroutine call specifies the subroutine name and the sequence of expressions (also separated by commas) that correspond to the parameters. If the number of expressions in a subroutine call does not match the number of parameters in its declaration, or if there is no declared subroutine with the specified name, the call should result in a runtime error. In addition, every subroutine declaration is assumed to be in the global scope, regardless of where that declaration occurs.

When a subroutine is called, it defines a new, independent scope. Parameters are treated as local variables in that scope, initialized based on the expressions provided in the subroutine call. In addition, local variables can be declared inside a subroutine using the var statement you wrote in HW3. Because a subroutine's scope is independent, statements within a subroutine cannot access variables outside that subroutine. As a result, it is legal to declare a subroutine parameter or local variable with whose name is already declared in an external scope.

For example:

SAMPLE CODE (output in red) 
  >>> sub foo :
          output "foo" ;
      end
  >>> call foo ;
  foo
  >>> sub bar x :
          var y = 9 ;
          var z = x + y ;
          output x , y , z ;
      end
  >>> call bar 1 ;
  1 9 10
  >>> call bar 3 + 2 ;
  5 9 14
  >>> sub biz a , b , c :
          var max = a ;
          if b > a then
              if b > c then
                  max = b ;
              else 
                  max = c ;
              end
          else
              if c > a then
                  max = c ;
              end
          end
          output "max" , "of" , a , b , c , "is" , max ;
      end
  >>> call biz 10 , 20 , 30 ;
  max of 10 20 30 is 30
  >>> var a = 7 ;
  >>> call biz a - 1 , a + 1 , a ;
  max of 6 8 7 is 8
  >>> var x = 1234 ;
  >>> sub baz x :
          var q = 88 ;
          output x , q ;
      end
  >>> var q = true ;
  >>> call baz 3 * 5 ;
  15 88
  >>> call baz "cs" ^ "dj" ;
  csdj 88
  >>> output x , q ;
  1234 true


  >>> sub fibonacci N :
          var previous = 0 ;
          var current = 1 ;
          while N > 0 do
              var temp = current ;
              current = previous + current ;
              previous = temp ;
              N = N - 1 ;
          end
          output current ;
      end
  >>> var f = 1 ;
  >>> while f <= 8 do
          call fibonacci f ;
          f = f + 1 ;
      end
  1
  2
  3
  5
  8
  13
  21
  34
  >>> sub recurse num :
          if num > 0 then
              call fibonacci num ;
              call recurse num - 1 ;
          end
      end
   >>> call recurse 8 ;
  34
  21
  13
  8
  5
  3
  2
  1
>>> var global = "danger" ;
>>> sub crashes :
    output global ;
end
>>> call crashes ;
  Exception in thread "main" java.lang.Exception: RUNTIME ERROR: variable global not declared

Note that executing a subroutine declaration does NOT result in its code being executed. Declaring a subroutine simply stores the code associated with that subroutine in memory so that it can be called later. You will need to add a third field to the MemorySpace class, corresponding to the code segment. When a subroutine declaration is executed, the parameters and code for that subroutine should be stored in the code segment. Subsequently, when a subroutine call is executed, the corresponding parameters and code must be accessed from the code segment so that it can be executed.