Com Sci 221 --- Programming Languages Assignment #4 --- Winter 1995 Due Monday, 30 January

Last modified: Fri Jan 27 14:53:41 1995

Other versions:

We saw in class that, although the stack implementation of expression evaluation is designed primarily for left-to-right innermost evaluation, it allows certain types of outermost evaluation (called ``selective evaluation'' in the text), such as that required to produce the usual behavior of conditionals under the set of rules
```
if T then  <alpha> else <beta>  =>  <alpha>

if F then  <alpha> else <beta>  =>  <beta>
```
and the slightly unusual, but extremely useful, behavior of and and or under the set of rules
```
F and  <beta>  =>  F

T and  <beta>  =>  <beta>

T or <beta>  =>  T

F or <beta>  =>  <beta>
```
Comment on the problems involved in trying to do outermost evaluation on a stack with sets of rules such as
1. ```
<alpha> or T   =>  T

<alpha> or F   =>  <alpha>
```
2. ```
<alpha> or T   =>  T
	 
T or <beta>  =>  T
	 
F or F   =>  F
```
3. ```
if <alpha> then <beta> else <beta>  =>  <beta>

if T then <alpha> else <beta>  =>  <alpha>

if F then <alpha> else <beta>  =>  <beta>
```
  This is a deliberately open-ended question. You will get more credit the more insight you can generate about why each set of rules is not only problematic, but more problematic than the ones before. Long answers, however, are not recommended. It is possible in each case to get the essential points in a few sentences.
You are given two arrays, A and B, each indexed from 0 to 20. A contains integers, and B contains characters. You are searching for a contiguous sequence of two entries in A, numbered i and i + 1, such that B[A[i]] = B[A[20 - i]], B[A[i + 1]] = B[A[20 - i - 1]]. There is no guarantee that entries in A are in the range 0 to 20. The basic structure of your procedure will be:
```
     i := 0;
     While i<=20 but i does not satisfy the desired
        condition do
             i := i+1
     end while
```
When the loop completes, either i satisfies the desired condition, or there is no way to satisfy it, and i = 21. Realize the structure above as well as you can in Pascal and C. This is not necessarily the best program structure for the given task, but use it anyway. You should come closer in C that in Pascal, by using the conditional forms of and and/or or (written ``&&'' and ``||''). Demonstrate your programs on a set of inputs that demonstrates the interesting qualities of the programs.

Comments