CS314, Fall 2007
Homework 6: Midterm redo and practice with Scheme

1. REDO the scoping problem from the midterm exam. Draw the run-time stack
to show local variable storage (and their values as they change during
execution). Hand simulate this program and show the output from
the 6 print statements in the order they occur.

What are the contents of the run-time stack when execution reaches
the program point /****/?


main()
{ integer a, b, c := 0;    // all initially 0
  procedure p()
  {  integer a := 1;
     print "#1", a, b, c;
	a++; b++; 
	if (b mod 2 = 0) then  Q();
	else  p();
     print "#2", a, b, c;
  }--end p;

  procedure Q()
  {   integer b := 0;
	 a++; b++; c++;
      print "#3", a, b, c;/****/
       }--end Q;

  p();
  print "#4", a, b, c;
}--end main

2. REDO the Prolog problem (a) from the midterm.

Given the program Given the following Prolog clauses defining
predicate f(), answer the questions below.  The built-in predicate
integer() returns true when its argument is an integer or a variable
bound to an integer value, else fails.  The built-in predicate var()
returns true when its argument is an unbound variable, else
fails. 

f([ ],0).
f([_|Y],L) :- integer(L), L > 0, M is L-1,f(Y,M), L is M+1.
f([_|Y],L) :- var(L), f(Y,M), L is M+1.

Write the answer which is returned by the following queries (notice we are
looking for the first answer only). Run this program with trace on to obtain
these answers.

i.  ?- f([1,2,3],X)._______________

ii. ?- f([1,2,3],4). _______________

iii. ?- f(X,3).  _______________

iv. ?- f(X,Y). ________________

Draw the first 2 levels of the Prolog search tree for query iv, counting
the root as level 0.. 

3. Getting Dr. Scheme experience. Try coding the following simple
Scheme functions:

i. last, a function that returns the last element in a list. Do not use
a reverse function which reverses the elements of a list.

ii. stem, a function that returns the list obtained by removing the last
element from the argument list. Again, do not use reverse.

iii. and2, a function that will take the logical ``and'' of its two
arguments. Do not use the built-in function and.

iv. or2, a function that will take the logical ``or'' of its two
arguments. Do not use the built-in function or.

Print out your functions to turn them in.