CSc 262 Final Examination Saturday, 12 December 1998 4-7 PM Page 1 Suggested answers will be posted on CSCKAY shortly after 7. Name_____________________________________________________________________ 1. (25 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 executing A[H]:=B[H]+1 is located at 1120. 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 value stored in the memory location (provided it can be computed). Assume that INTEGERs take two byte of memory, REALs three bytes, and addresses four bytes. Assume that the base (beginning) address of the stack is 4000. Write the details of the stack when the line marked with the comment (*POINT 1*) has been reached. Assume that static chains are used for implementing non-local references. Some notes on the program below: (1) Comments start with (* and end with *). (2) A formal parameter preceded by the keyword VAR is passed by reference; otherwise the parameter is passed by value. (3) In the declaration of PROCEDURE TWO, when I write A:RAY I am declaring the parameter A to be an ARRAY[3..5] OF REAL. PROGRAM ZERO; TYPE RAY=ARRAY[3..5] OF REAL; VAR I:INTEGER; X:RAY; PROCEDURE TWO(VAR A:RAY; B:RAY; H:INTEGER); VAR J:INTEGER; BEGIN A[H]:=B[H]+1; (*1120*) J:=H+4; (*1150*) (*POINT 1*) END(*PROCEDURE TWO*); (*1160*) BEGIN FOR I:=3 TO 5 DO (*1000*) X[I]:=I; TWO(X,X,4); (*1020*) WRITELN(OUTPUT,X[4]); (*1040*) END. (*1060*) Memory Address Item Value 4050 J 8 4048 H 4 4045 B[5] 5 4042 B[4] 4 4039 B[3] 3 4035 Addr A 4014 4031 Dynamic Pointer 4023 4027 Static Pointer 4000 4023 Return Address 1040 <^^^^^^^THREE^^^^^^^^^> 4020 X[5] 5 4017 X[4] 5 4014 X[3] 3 4012 I 5 or 6 (????) 4008 Dynamic Pointer 4000 4004 Static Pointer ???? 4000 Return Address ???? 2. (25 pts) In the table below I have labeled the rows with the names of five languages, and I have labeled the columns with five properties a given language may or may not have. Fill in the 25 cells of the table by placing a Y in the cell if the language in the cell's row has the property in the cell's column and an N otherwise. Strong Late User-defined Interpreted Supports Typing Binding Overloading Concurrency FORTRAN-77 Y N N N N Standard Pascal Y N N N N Lisp N Y N Y N Java Y N Y Y Y Smalltalk N Y Y Y Y 3. (25 pts) Explain the difference between pass by reference and pass by value-result. Give some sample code where executing the code would lead to different outcomes, depending on whether parameters are passed by reference or by value-result. With pass by reference, the formal parameter of the subprogram is an alias for its corresponding actual parameter. Thus, any operations on the formal parameter in the subprogram are performed on the actual parameter. With pass by value-result, at the beginning of the call to the subprogram the contents of the actual parameter are copied into memory location(s) set aside for the formal parameter. At the end of the call, the contents of the formal parameter are copied into the actual parameter. Given the procedure PROCEDURE ONE(VAR A,B,C:INTEGER); BEGIN A:=A+1; B:=B+1; C:=B; END; given the declarations VAR X,Y:INTEGER and given the code X:=1; ONE(X,X,Y) then after the call to ONE, if the parameters are passed by reference, Y will have the value 3, but if the parameters are passed by value-result, Y will have the value 2. 4. (25 pts) Write a Lisp function FIRSTLAST which takes one argument. If the argument is a list with at least two element, FIRSTLAST returns a list consisting of the first and last elements of the list, otherwise it returns nil. HINT: The Lisp function REVERSE is useful here. (defun FIRSTLAST (lis) (cond ((atom lis) nil) ((null (cdr lis)) nil) (T (list (car lis) (car (reverse lis)))))) 5. (25 pts) Describe the data abstraction (NOT the implementation as an ADT) for Semaphor. Explain how Semaphors can be used for cooperation synchronization and competition synchronization. A Semaphor stores a counter and a queue whose entries consist of enough information about a process so that it can resume processing at some point where it has been (temporarily) stopped. A Semaphor can be "Initialized" so that its queue is empty and its counter is zero. It can be told to "wait" in which case the counter is decremented, and if it is < 0 the process telling the Semaphor "wait" is suspended and put in the Semaphor's queue. A Semaphor can be told "signal" in which case the counter is incremented, and if it is <= 0, the process telling the Semaphor wait is suspended and a process is removed from the queue and starts processing. (The above description could be done without reference to the counter, but would be more contorted). Cooperation Synchronization: Assume process Donor provides data for process Charity. Create two Semaphors, one called haveData, the other wantData. Start by signalling wantData. When Charity wants data, she "waits" haveData, gets the data, and then "signals" wantData. When Donor wants to provide data, she "waits" wantData, stores the data, and then signals "haveData." Competition Synchronization: Assume various processes want to access some data. Create a Sempahor called access and start by signalling access. Any process wanting access to the data "waits" access, accesses the data, and "signals" access. In this case a Semphor must be able to run without interruption. 6. (25 pts) In designing a language, explain the design issues one confronts when deciding the behavior of (1) arithmetic expressions and (2) boolean expressions. (1) One has to decide which operators to implement. Clearly one should implement addition, subtraction, multiplication, and division. Should one also have exponentiation. Should there be a "mode" operator for integers? One must also decide how the language will handle expressions that mix types, e.g., reals and integers. Will reals "coerce" integers in mixed expressions? Should division for integers be different from division for reals? One must decide upon the precedence of the operations. Should there be a precedence? If so, should it be exponentiation, then division and multiplication, and then additions and subtraction? What is the associativity of each operator? That is do we interpret the expression a op b op c as (a op (b op c)), which is right associative, or do we interpret a op b op c as ( (a op b) op c), which is left associative? Finally, when evaluating an expression involving functions of the form f(x) op g(x), which function should be evaluated first before performing the operation? (2) Many of the design issues for boolean expressions are the same as above. We should implement "and", "or", and "not." What about "xor?" Then we must worry about precedence and associativity of the operators. We also have to deal with how to evaluate f(x) op g(x). In addition, we have the question of whether to implement short-circuit evaluation. When evaluating the expression f(x) and g(y) we do not have to evaluate g(y) if f(x) is false, because the expression must be false, irrespective of the value of f(x). Similarly, the expression f(x) or g(y) must be true if f(x) is. If we implement short circuit evalution we do not evaluate the second expression when we do no have to. 7. (25 pts) Explain the differences between Standard Pascal and FORTRAN 77 in terms of (1) why one languague uses a stack of activation records and the other does not, and (2) the way in which arrays are stored. (1) Standard Pascal needs to use a stack of activation records, because it supports recursion. The activation records are used to preserve the local environment when a subprogram call is made. Without the stack, a recursive call would erase the local environment for the previous call of the subprogram. Since FORTRAN 77 does not implement recursion it can statically allocate space for subprograms. (2) Given an n-dimension array X, FORTRAN stores the array in memory in the order X(1,1,1,1,..,1), X(2,1,...1), ..., X(n,1,1,...,1), X(1,2,1,1...1), X(2,2,...,1), ...., X(n,2,1,....,1).....X(n,j,k,...,t) That is, it cycles through all its indices, starting from the leftmost index and proceeding through all its indices. Pascal works from the right to the left: X(1,1,1....,1), X(1,1,1....2), X(1,1,1,...t), X(1,1,...,2,1), X(1,1,....2,2), ... X(1,....,2,t),..., X(n,j,k,....,t) 8. (25 pts) In designing a language, what iteration structure(s) would you include and why? There are many correct answers to this question, none of them right. I give a correct answer. I want my iteration structures to be simple and flexible, so that the programmer does not have much to remember but has little work to do in constructing loops. I borrow my ideas from Smalltalk. I would have two counter-controlled loops and one logically controlled loop. I will use BNF notation for the Pascal-like syntax of the structures and then explain the semantics. => | | => for := to do => for := to by do => loop ; whileTrue is the usual for statement of Pascal and c2-loop allows increments other than 1. The readily produces a while loop e.g., loop ; whileTrue, and readily produces a negative version of a repeat statement, e.g., loop ; whiletrue; The structure further allows one exit from any part of the body of the loop by apportioning the statements of the loop between the first and second . The exit from the middle would be highly readable, because one would likely adopt a formatting convention like loop ... ... ... whileTrue begin ... ... ... end