Static and Dynamic Scoping

The scope concept
Static and dynamic scoping
Implementing static scoping
Lab: A language with dynamic scoping
Lab: Modifying SL1 for dynamic scoping

Scope

Scope of named entity = region where name references the entity
Scopes can overlap

class Example // Java
{
  private int foo;
  public void fun(double foo)
  {
    System.out.println(foo); // Which foo? 
  }
  public void fun()
  {
    System.out.println(foo); // Which foo? 
  }
}

Particularly common in languages with nested functions

def fun(x : Int) { // Scala
  def helper() { var x : Int; ... }
  ...
}

Static vs. Dynamic Scoping

Static scope: Depends on program source only
Dynamic scope: Depends on execution history

Example

val x = 1;
def f(y) = x + y;
def g() { val x = 2; f(x) };
g()

Static scoping: Result is 1 + 2
Dynamic scoping: Result is 2 + 2
Dynamic scoping is common in interpreted languages (see lab)
Disadvantage: Meaning of program harder to understand

Implementation of Dynamic Scoping

Global symbol table
Push definition when it is encountered, pop at end of scope

Example:

val x = 1;
def f(y) = x + y;
def g() { val x = 2; f(x) };
g()

x -> 1 // first def. of x
x -> 2, x -> 1 // def. of x inside g
y -> 2, x -> 2, x -> 1 // def. of parameter y

Implementation of Static Scoping

Each function has its own symbol table
Records the meanings of symbols when the function was defined
Function body is evaluated with that table (augmented by parameter bindings)

Example:

val x = 1;
def f(y) = x + y; // x -> 1
def g() { val x = 2; f(0) }; // f -> ...

Table only needs to store free variables in function body

When f is executed:
```
y -> 2, x -> 1
```

Implementing Recursive Functions

Can't use val:

val fac = x => if (x == 0) 1 else x * fac(x - 1)

RHS is an anonymous function with free variable fac
```
x => if (x == 0) 1 else x * fac(x - 1)
```
Then a new variable fac is defined

def simultaneously adds fac and RHS to symbol table

case class Closure(params : List[String], body : Block, var env : List[(String, Any)])
 ...
def evalDef(symbols : List[(String, Any)], defn : Definition) =
  defn match {
    case Defdef(name, Function(params, body)) => {
      val cl = Closure(params, body, symbols)
      val syms = (name, cl) :: symbols
      cl.env = syms // mutation
      syms
    }
    ...
  }

Here, for the first time, we use a var in the interpreter.
Pure functional solution is possible but intricate. (Take CS252)

Lab

Check into eCampus in the usual way
Scribe puts in report
Buddy puts in comment with scribe's name
Whoever got a lower exam grade is the coder, the other the scribe

Step 1: Bash

Launch your bash shell. (What, no bash shell? Install Cygwin.)
Next, some background information. The bash command shell has a rudimentary programming language. Here are some of its features.
1. You declare global variables with the syntax
```
varname=initialValue
```
2. You declare functions with the syntax
```
function funname {
   . . .
}
```
  Function parameters are not named. Instead, you refer to them as $1, $2, $3...
3. You call functions with the syntax
```
funname arg1 arg2 arg3 . . .
```
4. You declare local variables (inside functions) with the syntax
```
local varname=initialValue
```
5. You get the value of a variable with the syntax
```
$varname
```
  For example, the command
```
echo $a
```
  prints the value of a

Step 1: Bash (Continued)

Make a file test1.bash with the contents

x="2"

function f {
   echo $x
}

function main {
   local x="3" ; 
   f ;
}

main

Start the bash shell (i.e. Cygwin). Run the program: source test1.bash. What does it print?
What does that tell you about variable scoping in the bash language?

Step 2: More Bash (If you have time)

Make a file test2.bash with the contents.

x="2"

function f {
   echo $x
}

function g {
   local x="3" ; 
   f ;
}

function main {
   local x="4" ;
   f ;
   g ;
   f ;
}

f ;
main

What do you expect this program to print?

Start the bash shell (i.e. Cygwin). Run the program: source test2.bash. What does it print?
Explain the behavior by drawing diagrams of the environment.

Step 3: Understanding Closures in SL1

Consider the SL1 program

val a = 3;
val f = { x => x * a };
val g = { a => a * f(a)};
g(1)

What result output do you expect?

Start the SL1 interpreter and run the program. What output did you get?
Place a breakpoint in the line
```
case Valdef(name, Function(params, body)) => { (name, Closure(params, body, symbols)) :: symbols }
```
Run the debugger with the same program as input. When the breakpoint is hit, inspect symbols. What do you get for symbols when the definitions of f and g are evaluated?
Change the code for
```
case Funcall(fun, args) => eval(fun, symbols) match
```
to
```
case Funcall(fun, args) => val funval = eval(fun, symbols); funval match
```
Debug the program again, this time with a breakpoint in the line
```
evalBlock(body, params.zip(args.map(eval(_, symbols))) ::: syms)
```
The breakpoint will be triggered when g and f are executed/ What are the values of symbols and the syms in the closure object when g is executed?
With what environment is the body of f executed?

Step 4 (If you have more time)

I had to work a bit to make SL1 use static scoping. Undo this to make an interpreter that uses dynamic scoping.

Remove the case class Closure

Remove the line

case Valdef(name, Function(params, body)) => { (name, Closure(params, body, symbols)) :: symbols }

so that the line below will simply add the Function object to the table

Remove the line
```
 case Function(params, body) => Closure(params, body, symbols)
```
so that the line below will simply cause a Function to evaluate to itself
Remove the Defdef case of evalDef for now. (It mutates the env field of the closure. This would need to be solved by mutating the symbol table entry, as in homework 3, but in this lab step, we just won't use def.)

Change

case Closure(params, body, syms) =>
  evalBlock(body, params.zip(args.map(eval(_, symbols))) ::: syms)

case Function(params, body) =>
  evalBlock(body, params.zip(args.map(eval(_, symbols))) ::: symbols)

Translate test1.bash into SL1dyn. What is your test case? What is the result?