CS 3304
Solutions to Homework Assignment 2
July 17, 1997

[8] 1.

Chapter 4, Problem 8.

a.

For static scoping, we need only look at the hierarchical structure of the program units within the program text. We see that procedures sub1 and sub3 are directly nested within program main. Procedure sub2 is nested within procedure sub1. There is a declaration of x in both main and in sub1. Hence, a reference to x in sub1 is to the declaration in sub1. A reference to x in sub2 is also to the declaration in sub1, since sub2 is nested within sub1. A reference to x in sub3 is to the declaration in main, since sub3 is nested within main, but not within sub1.

b.

For dynamic scoping, we need to examine the execution sequence

main calls sub1 calls sub2 calls sub3.

As with static scoping, a reference to x in sub1 is to the declaration in sub1. A reference to x in sub2 is also to the declaration in sub1, since the first declaration of x above sub2 in the execution sequence is in sub1. A reference to x in sub3 is also to the declaration in sub1, for the same reason.

[8] 2.

Chapter 4, Problem 13. Note that this problem assumes dynamic scoping.

a.

We summarize the visible variables in the following table:

b.

We summarize the visible variables in the following table:

c.

We summarize the visible variables in the following table:

d.

We summarize the visible variables in the following table:

e.

We summarize the visible variables in the following table:

f.

We summarize the visible variables in the following table:

[6] 3.

Chapter 5, Problem 13.

A reasonable solution is to provide syntax in the language that will allow the programmer to specify exactly which type of blue she is referring to. For example, the following syntax could distinguish these:

colors.blue
mood.blue

Whenever the implementation cannot determine the type of an overloaded value, an error is raised, forcing the programmer to clarify her intentions.

[8] 4.

Chapter 5, Problem 14.

Let

threeD : array (m..n,p..q,r..s) of t

declare a three dimensional array. Assume that a value of type t requires e bytes of storage. Let b be the base address of threeD (the l-value of threeD(m,p,q)).

To determine the l-value of

threeD(i,j,k)

in row-major order, first list the order elements are stored in RAM:

threeD(m,p,r)
threeD(m,p,r+1)
     ...
threeD(m,p,s)
threeD(m,p+1,r)
threeD(m,p+1,r+1)
     ...
threeD(m,p+1,s)
threeD(m,p+2,r)
     ...
threeD(m,q,s)
threeD(m+1,p,r)
threeD(m+1,p,r+1)
     ...
threeD(m+1,p,s)
threeD(m+1,p+1,r)
threeD(m+1,p+1,r+1)
     ...
threeD(m+1,p+1,s)
     ...
threeD(n,q,s)

Every time the first index is incremented, (q-p+1)(s-r+1) elements have been passed. Every time the second index is incremented, (s-r+1) elements have been passed. The resulting formula for the l-value is

To determine the l-value of

threeD(i,j,k)

in column-major order, first list the order elements are stored in RAM:

threeD(m,p,r)
threeD(m+1,p,r)
     ...
threeD(n,p,r)
threeD(m,p+1,r)
threeD(m+1,p+1,r)
     ...
threeD(n,p+1,r)
threeD(m,p+2,r)
     ...
threeD(m,q,s)
threeD(m,p,r+1)
threeD(m+1,p,r+1)
     ...
threeD(n,p,r+1)
threeD(m,p+1,r+1)
threeD(m+1,p+1,r+1)
     ...
threeD(n,p+1,r+1)
     ...
threeD(n,q,s)

Every time the last index is incremented, (n-m+1)(q-p+1) elements have been passed. Every time the second index is incremented, (n-m+1) elements have been passed. The resulting formula for the l-value is

[6] 5.

Refer to the type declarations on page 225. These types are to be implemented on a computer with a 32-bit word. Suppose that a value of enumerated type is represented in one byte. Suppose that an integer value is represented in a word and must be aligned on a word boundary. Suppose that a real value is represented in two words and must be aligned on a word boundary.

How many bytes should be allocated for a variable of type object? Explain.

The circle variant requires two words or eight bytes. The triangle variant requires four words or 16 bytes. The rectangle variant requires two words or eight bytes. Since this is a union (variant record), we need the maximum of these three requirements, that is, 16 bytes. The form discriminant needs a byte, so we need at least 17 bytes for variable figure. Because of the requirement to align integer and real values, we must be concerned about the l-value for figure. Typically, figure will be placed on a word boundary, that is, at an address that is divisible by 4. The layout of the three variants might then be:

The numbers are the offsets from the base l-value. The resulting representation requires 17 bytes, at a minimum. However, because the next data structure in memory is often also aligned, it is likely that 20 bytes is the effective amount of memory allocated to figure. If the layout is as in Figure 5.9, the allocated memory will always be 20 bytes.

[8] 6.

Chapter 6, Problem 10.

a.

Evaluation order is

b.

Evaluation order is

c.

Evaluation order is

d.

Evaluation order is

e.

Evaluation order is

f.

Evaluation order is

[8] 7.

Chapter 6, Problem 12.

We can modify the grammar that incorporated the unary minus from the previous homework to include all the operators listed:

The unary minus has a different precedence than it did in the previous homework. Also, note that is a unary operator.

[8] 8.

Chapter 6, Problem 21. Explain.

The first thing to notice about this problem is that fun does not return a value, so the value of x after the assignment is not well-defined. So we need to add a return to fun. One possibility is the following:

int fun (int *i) {
    *i += 5 ;
    return *i;
}

void main () {
    int x = 3;
    x = x + fun(&x);
}

a.

In the assignment

x = x + fun (&x);

the value of the left operand of the + is retrieved first and found to be 3. Then the l-value of x is retrieved by the &x construct. Next fun is called with that l-value passed to it. The function fun increments the value pointed to by its parameter, effectively assigning 8 to x. After fun returns the value 8, the addition is performed, with the result 11. Hence, x is assigned 11.

b.

With right to left evaluation, the principle difference with the previous answer is that the function fun is called before the left operand of the + is retrieved. Hence, both operands of the + are 8, with the result 16. Hence, x is assigned 16.

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -t CS 3304 Solutions to Homework Assignment 2 solvehw2.

The translation was initiated by cs3304sm class account on Thu Jul 17 09:15:23 EDT 1997