CSE 428: Home Assignments

Spring 99, CSE 428: Assignment 3

Distributed: Feb 5.
Due: Feb 11 in class.
Total maximum score: 100 points.

The purpose of this assignment is to provide experience with parameter-passing methods, static and dynamic scope, and recursion.

[Points 30] Consider the following (incomplete) procedure declaration:
```
   procedure p(...);
      begin 
      x := x+1;
      y := y+2
      end;
```
where x is the parameter of p and y is a global variable of type integer. Say what will be the output of the following portion of code:
```
      y := 0;
      p(y);
      print(y);
```
under each of the following assumptions:
1. Call by value: the head is written as procedure p(x:integer)
2. Call by reference: the head is written as procedure p(var x:integer)
3. Call by value-result: the head is written as procedure p(value-result x:integer)

[Points 20] Consider the following procedure declaration (p), containing two internal procedure declarations (q and r):

procedure p(var x:integer);
   procedure q; /* declaration of a procedure q local to p */
      begin     /* begin body of q */
      x := x+1;
      end;      /* end body of q */
   procedure r; /* declaration of a procedure r local to p */ 
      var x:integer; /* declaration of a variable x local to r */
      begin          /* begin body of r */
      x := 0;      
      q;
      end;           /* end body of r */
   begin   /* begin body of p */
   r;
   end;    /* end body of p */

The symbols /* and */ in the above code are delimiters of comments. Say what is the output of the following portion of code:

   y := 1;
   p(y);
   print(y);

under each of the following assumptions:

Static scope
Dynamic scope

Note: as far as the scoping rules are concerned, the parameter x of p is "seen" by q as if it were a variable declared at the top-level in p.

[Points 50] Condider the procedure "search_exit" searching for the exit from a maze represented as a bidimentional array of characters, explained in last Thursday's lecture (see also the LN of that lecture).
Modify the procedure so that the array will contain, at the end, a "trace" representing the path from the initial position to the exit, if it exists. You don't need to care about other modifications possibly done by the procedure on the array (like filling the array with more "*"). You also don't need to care about the possibility of multiple paths or multiple exits (it is sufficient to find one of them).
For example, assume that the original maze is
```
   **** ****
   ***  *  *
   *** ** **
   *    x **
   *********
```
where "*" represents a brick, " " (blank) represents a place we can walk by, and "x" is the initial position.
Then the following answer is ok, where the "o"'s represent the path:
```
   ****o****
   ***oo****
   ***o*****
   *  ooo***
   *********
```
Note: the exercise is less difficult than it looks: It is sufficient to add just one instruction to the procedure on the LN. You can use the C version of the procedure if you prefer.