CSc 262 Test 3 20 November 1998 >>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<< 1. (40 pts) In this question I ask you to provide the details of the activation records for the Pascal program below. Beside each statement in the program is the (hypothetical) decimal address for the start of the machine code for the statement. For example, the start of the code that includes instructions for leaving PROCEDURE ONE is 1290. Write a description of the stack of activation records with three columns. The first column should be labeled "memory address" and have the decimal address of the first byte of the given structure. The second column should be labeled "item" and name the item which is being stored in the memory location. The third column should be labeled "value" and have the numerical (or character) value stored in the memory location (provided it can be computed). Assume that CHARs take one byte of memory, INTEGERs two bytes, REALs four bytes, and addresses four bytes. Assume that the base (beginning) address of the stack is 4000. If the program below is executed it goes into infinite recursion. Write the details of the stack when the calling sequence main->two->three->one->two has occurred, and we are at the line marked with machine address 1070 (before the call THREE). Assume that static chains are used for implementing non-local references. In the next question, I ask you to do the exact same thing, except using displays for implementing non-local references, so leave space beside your three columns to add information to answer question 2. Indeed, read question 2, before answering this question. Some notes on the program below: (1) The FORWARD statement tells the compiler that the details of the procedure will appear later (akin to a prototype in C++). (2) Comments start with (* and end with *). (3) A formal parameter preceded by the keyword VAR is passed by reference; otherwise the parameter is passed by value. PROGRAM ZERO; VAR A:REAL; B:INTEGER; PROCEDURE TWO(VAR A:REAL; H:CHAR); FORWARD; PROCEDURE ONE(C:CHAR; VAR D:REAL); BEGIN C:='A'; (*1200*) D:=6; (*1240*) TWO(D,C); (*1260*) END(*PROCEDURE ONE*); (*1290*) PROCEDURE TWO(*VAR A:REAL; H:CHAR*); PROCEDURE THREE; VAR J:REAL; BEGIN J:=7.3; (*1100*) ONE('T',J); (*1120*) END(*PROCEDURE THREE*); (*1160*) BEGIN THREE; (*1070*) END(*PROCEDURE TWO*); (*1090*) BEGIN TWO(A,'Z'); (*1020*) END. (*1060*) Memory Address Item Value xxxxx xxxx xxxx 4084 H 'A' 4080 A (address) 4047 4076 Dynamic Link 4068 4072 Static Link 4000 [4051] (Question 2) 4068 Return Address 1290 (TWO)---------------- 4064 D (address) 4047 4063 C 'A' 4059 Dynamic Link 4051 4055 Static Link 4000 [4018] (Question 2) 4051 Return Address 1160 (ONE)--------------- 4047 J 6 (was 7.3) 4043 Dynamic Link 4035 4039 Static Link 4018 [????] (Question 2) 4035 Return Address 1090 (THREE)-------------- 4034 H 'Z' 4030 A (address) 4012 4026 Dynamic Link 4018 4022 Static Link 4000 [????] (Question 2) 4018 Return Address 1060 (TWO)---------------- 4016 B ???? 4012 A ???? 4008 Dynamic Link 4000 4004 Static Link ???? [????] (Question 2) 4000 Return Address ???? (MAIN)--------------------- 2. (10 pts) Repeat question 1, but using displays, rather than static chains. Diagram the display here. In the diagram above, you should have to change very little, except the information for maintaining the display, information which can be stored in the same place as the information for maintaining the static chain. So, instead of rewriting (almost) all the information from question 1, simply indicate in boxes beside the three columns above the numbers needed to maintain the display. Static Level Base Address 2 4035 1 4068 0 4000 3. (20 pts) Explain the mechanisms for hiding data and methods (functions) in a) Smalltalk All methods are public, and all data are private, except that one may inadvertently have access to private data through pointers which are used to give access to objects. b) C++ Data and functions are treated the same way. They may be public, in which case they are available to the user, they may be private, in which case they are only available to members of the class or friends of the class, or they may be protected, in which case they are not available to the user but are available to objects in the class, to friends of the class, and in subclasses of the class whose superclasses are public (and not private) sublcasses of the class. c) Simula 67 All methods and objects are public. It has no mechanisms for hiding data and methods. 4. (15 pts) Most modern languages have an abstract data type (ADT) for Boolean. Without reference to how it might be implemented in any specific language, describe the data abstraction (as opposed to the ADT) "Boolean." A Boolean has two values, say "true" and "false." It has unary operation, call it "other" such that other(true) is false and other(false) is true. One can test two Booleans for equality in the obvious way. There is a binary operation, call it U, such that U(true,true)=U(true,false)=U(false,true)=true and U(false,false)=false. There is a binary operation, call it W, such that W(true,true)=true and W(false,true)=W(true,false)=W(false,false)=false. 5. (15 pts) Let X be a Smalltalk block which creates global variables as necessary to serve as local variables (i.e., local to the block) and responds to the message X value:n value:delta by returning the sum of the numbers 1, 1+delta, 1+2*delta, 1+3*delta, ... for all such numbers less than or equal to n. For example, X value:10 value:1 returns 1+(1+1)+(1+2*1)+...+l0==1+2+3+...+10==55 X value:-6 value:2 returns 0 X value:12 value:4 returns 1+5+9==15 Write the code for the block. Two possible answers: X:=[:n :delta| S:=0. 1 to:n by:delta do:[:i| S:=S+i]. S] X:=[:n :delta| S:=0. T:=1. [T<=n] whileTrue:[S:=S+T. T:=T+delta]. S]