Statement Level Control Structures, Subprograms


Written on Monday, May 05, 2008 by Ennah, the comsci student

Chapter 7. Statement-Level Control Structures

1. What is pretest loop statement? a posttest loop statement?

Pretest loop statements are set of statements to be executed repeatedly in which the test for loop completion occurs before the loop body is executed

Posttest loop statements are set of statements to be executed repeatedly in which the test for loop completion occurs after the loop body is executed

2. What is the main reason user-located loop control statements were invented?

The main reason why user-located loop control statements were invented because in some situations, it is convenient for a programmer to choose a location for loop control other than top or bottom of the loop. As a result, some languages provide this capability, the user-located loop control mechanism.

3. What is a user-defined iteration control?

A user-defined iteration control is the one that issues a special call to the iterator, in which the iterator is called at the beginning of each iteration, and each time it is called, the iterator returns an element from a particular data structure in some specific order.

4. What are the design issues for

(a) selection structures

  1. What is the form and type of the expression that controls the section?
  2. Can a single statement, a sequence of statements, or a compound statement be selected?
  3. How should the meaning of nested selectors be specified?

(b) multiple selection statements

  1. What is the form and type of expression that controls the selection?
  2. May single statements, sequences of sentences, or compound sentences be selected?
  3. Is the entire construct encapsulated in a syntactic structure?
  4. Is execution flow through the structure restricted to include just a single selectable segment?
  5. How should unrepresented selector expression values be handled, if at all?

(c) counter-controlled loop statements

  1. What are the type and scope of the loop variable?
  2. What value does the loop variable have at the loop termination?
  3. Should it be legal for the loop variables or loop parameters to be changed in the loop, and if so, does the change affect the loop control?
  4. Should the loop parameters be evaluated only once, or once for every iteration?

(d) logically-controlled loop statements

  1. Should the control be pretest or posttest?
  2. Should the logically controlled loop be a special form of counting loop or a separate statement?

Sebesta. Chapter 8. Subprograms

5. Define

(a) static-chain

Static chain is a chain of static links that connect certain activation record instances in the stack.

(b) static depth

Static depth is an integer associated with a static scope that indicates how deeply it is nested in the outermost scope.

Ex: A main program has a static_depth of 0. If procedure A is the only procedure defined in a main program, its static_depth is 1. If procedure A contains the definition of a nested procedure B, the B's static_depth is 2.

(c) nesting depth

Nesting depth is interchangeable with chain offset

(d) chain offset

Chain_offset is the length of the static chain needed to reach the correct activation record instance for a nonlocal reference to a variable X is exactly the difference between the static_depth of the procedure containing the reference to X and the static_depth of the procedure containing the declaration for X. This difference is the chain_offset.

Ex: If the static_depths of A, B, and C are 0, 1, and 2, respectively. If procedure C references a variable declared in A, the chain_offset of the reference would be 2 (static depth of C minus the static_depth of A). If procedure C references a variable declared in B, the chain_offset of the reference would be 1. References to locals can be handled using the same mechanism, with a chain_offset of zero.

6. Explain the two methods of implementing blocks.

Blocks are treated as parameterless subprograms that are always called from the same place in the program. If blocks are implemented this way using the display method, one disadvantage is that as maximum nesting grows, required display size grows along with it. A display must be limited in size if it is to be stored in registers. So requiring display cells for blocks can cause the display to be stored in memory rather than in registers, causing considerable slowing of references to nonlocal variables.

Blocks can also be implemented in a different and somewhat simpler way. The maximum amount of storage required for block variables at any time during the execution of a program can be statically determined, because blocks are entered and exited in strictly textual order. This amount of space can be allocated after the local variables in the activation record. Offsets for all block variables can be statically computed, so block variables can be addressed exactly as if they were local variables.

7. Compare the deep access method and shallow access method of implementing dynamic scoping.

When a program that uses dynamic scoping refers to a nonlocal variable, the reference can be resolved by searching through the declarations in the other subprograms that are currently active, beginning with the one most recently activated. This concept is similar to that of accessing nonlocal variables in a static-scoped language, except that the dynamic-rather than static-chain is followed. The dynamic chain links together all subprogram activation record instances in the reverse of the order in which they were activated. Therefore, the dynamic chain is exactly what is needed to reference nonlocal variable in a dynamic-scoped language. This method is called deep access because access may require searches deep in the stack.

In the shallow access method, variables declared in subprograms are not stored in the activation records of those subprograms. Because with dynamic scoping there is at most one visible version of a variable of any specific name at a given time, a very different approach can be taken. One variation of shallow access is to have a separate stack for each variable name in a complete program. Every time a new variable with a particular name is created by a declaration at the beginning of a subprogram activation, the variable is given a cell on the stack for its name. Every reference to the name is to the variable on top of the stack associated with that name, because the top one is the most recently created.

The choice between shallow and deep access and nonlocal variables depends on the relative frequencies of subprogram calls and nonlocal references. The deep access method provides fast subprogram linkages, but references to nonlocals, especially references to distant nonlocals (in terms of the call chain), are costly. The shallow access method provides much faster references to nonlocals, especially distant nonlocals, but is more costly in terms of subprogram linkage.

If you enjoyed this post Subscribe to our feed

No Comment

Post a Comment