Exercises 1. (a) Expand the program in example (d) (b) What is the length of the program expanded from example (e) by this process?

(d) A program with two inputs that computes the function f(x1,x2)=x1+x2 is as follows: [B][A]YX1ZX2IFZ=0GOTOAGOTOEZZ1YY+1GOTOB Again, if challenged we would supply macro expansions for " YX1 " and " ZX2 "' as well as for the two unconditional branches. Note that Z is used to preserve the value of X2. (e) We now present a program that multiplies, i.e. that computes f(x1,x2)=x1x2. Since multiplication can be regarded as repeated addition, we are led to the "program" [B][A]Z2X2IFZ2=0GOTOAGOTOEZ2Z21Z1X1+YYZ1GOTOB Of course, the "instruction" Z1X1+Y is not permitted in the language S. What we have in mind is that since we already have an addition program, we can replace the macro Z1X1+Y by a program for computing it, which we will call its macro expansion. At first glance, one might wonder why the pair of instructions Z1X1+YYZ1 YX1+Y since we simply want to replace the current value of Y by the sum of its value and x1. The sum program in (d) computes Y=X1+X2. If we were to use that as a template, we would have to replace X2 in the program by Y. Now if we tried to use Y also as the variable being assigned, the macro expansion would be as follows: [B][A]YX1ZYIFZ=0GOTOAGOTOEZZ1YY+1GOTOB What does this program actually compute? It should not be difficult to see that instead of computing x1+y as desired, this program computes 2x1. Since X1 is to be added over and over again, it is important that X1 not be destroyed by the addition program. Here is the multiplication program, showing the macro expansion of Z1X1+Y : showing the macro expansion of Z1X1+Y : [B][A][B2][A2][E2]Z2X2IFZ2=0GOTOAGOTOEZ2Z21Z1X1Z3YIFZ3=0GOTOA2GOTOE2Z3Z31Z1Z1+1GOTOB2YZ1GOTOBZ1X1+Y Note the following: 1. The local variable Z1 in the addition program in (d) must be replaced by another local variable (we have used Z3 ) because Z1 (the other name for Z ) is also used as a local variable in the multiplication program. 2. The labels A,B,E are used in the multiplication program and hence cannot be used in the macro expansion. We have used A2,B2,E2 instead. 3. The instruction GOTO E2 terminates the addition. Hence, it is necessary that the instruction immediately following the macro expansion be labeled E2. In the future we will often omit such details in connection with macro expansions. All that is important is that our infinite supply of variables and