Homework 3 Sample Solution

1. 

Static scoping:

1
1
2
2

Because of static scoping, all function calls refer to the x 
visible when the functions are defined, which is in this case the 
global x. Therefore, control flow will have no effect. 

Dynamic scoping:


1
1
2
1

When second() is called, a local varialbe x is defined. Before second() is returned,
set_x(2) is called, and due to dynamic scoping, set_x(2) will lookup x tracing 
the dynamic link starting from its caller's frame, where it finds the local x. 
So set_x(2) will update the local x as 2. The call to print_x within second() will
refer to the updated local x for the same reason. Therefore 2 is printed.
After the call to second() is returned, its local x along with the frame is poped off
the stack. Therefore another call to print_x this time will refer to the global x, 
which is 1 as the result of the previous call to first(). 



2. 

Version of tail-recursion

fun isord ([] : int list) = true
  | isord [_] = true
  | isord (t1::t2::ts) = if t1 <= t2 then isord (t2::ts)
                         else false

Version of non tail-recursion

fun isord ([] : int list) = true
  | isord [_] = true
  | isord (t1::t2::ts) = (t1 <= t2) andalso isord (t2::ts)

3. 

   ^  -----------------  ^
   |  |     main      |  |
   |--|access  control|--|
 .>   |      x=1      |
 | .> ----------------- <.
 | |                     |
 | |  -----------------  |
 | |  |       H       |  |
 | |--|access  control|--|
 |    |      b=1      |
 |    ----------------- <.
 |                       |
 |    -----------------  |
 |    |       F       |  |
 |----|access  control|--|
 |    |      a=1      |
 | .> ----------------- <.
 | |                     |
 | |  -----------------  |
 | |  |       G       |  |
 | |--|access  control|--|
 |    |      i=1      |
 |    ----------------- <.
 |                       |
 |    -----------------  |
 |    |       F       |  |
 |----|access  control|--|
      |      a=0      |
   .> ----------------- <.
   |                     |
   |  -----------------  |
   |  |       G       |  |
   |--|access  control|--|
      |      i=0      |
      -----------------