CSc 262 Final Examination Thursday 11 December 1997 8 AM >>>>>>>>>>>>>SUGGESTED ANSWERS<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<, 1. (20 pts) Write a recursive LISP function entryn such that evaluating the expression (entryn n alist) returns the nth entry in the list alist, if it has at least n entries, or nil if it has fewer than n entries. Your function can assume that n is an integer. >>>>>>>>>>>>>>>>>>>>>> (defun entryn (n alist) (cond ( (null alist) nil) ( (lessp n 2) (car alist)) (t (entryn (difference n 1) (cdr alist) ) ) ) >>>>>>>>>>>>>>>>>>>>>> 2. (10 pts) Explain the notion of garbage collection. Explain how the notion of garbage collection applies to LISP and Smalltalk. >>>>>>>>>>>>>>>>>>>>> Garbage collection refers to the freeing up of dynamically allocated memory. In LISP, all lists are represented with linked lists. When they are no longer bound to a variable they are available for garbage collection, which occurs when the system runs out of memory. In Smalltalk, all objects are represented by pointers. When objects are not pointed to they are available for garbage collection, which occurs sporadically. >>>>>>>>>>>>>>>>>>>>>>>> 3. (25 pts) Explain the details of how lists are represented in LISP. Explain how car and cdr are implemented in terms of this representation. Suggest a scheme for implementing "last" and "butlast" in terms of this representation. >>>>>>>>>>>>>>>>>>>>>>>>Lists are implemented with linked lists of nodes, where the "key" of each node is a pointer to the given entry in the list, either an atom or another list, and the "node-pointer" points to the next entry in the linked list. Car is the "key" and Cdr is the "node-pointer" (which points to the rest of the list or NULL if there is no more list). To implement last, return nil for an empty list. Otherwise traverse the list until pointing to the last entry and return its key. To implement butlast return nil if the list is nil or only has one entry. Otherwise, traverse the list to the second last entry, making a copy of the list while traversing. Then set the next node of the second last entry to nil. >>>>>>>>>>>>>>>>>>>>>>>> 4. (25 pts) In Smalltalk I created a class Box, which is a subclass of class Object. Box adds no class variables nor any class methods. Instances of Box have two instance variables, 'corner' and 'extent', which are meant to represent the upper left hand corner of a rectangle (corner) and the dimensions of the rectangle in the x and y directions (extent). Both variables are meant to store points of the form x@y. Instances of Box have two methods, "corner: extent:" and "area". The code for these two methods follows: corner:aC extent:anE corner:=aC. extent:=anE. area |temp| temp:= extent x * extent y. ^temp Consider the following sequence of expressions: X:=Box new. X corner:2@3 extent:4@5. X area Assuming some activation record for the environment of the above three expressions, draw the activation record for the evaluation of the expression "X area" as it awaits the return from the call "extent y". Note that points respond to the messages "x" and "y" by returning their x and y components, respectively. Wherever possible indicate the actual values stored. Include in your diagram the representation of the instance of Box and the representation of the class Box. AR for "X area" ------ IP | |------------------------------------------------------\ method ------ class Box | offset | | ------- | ------ size| 7 | | temp | --- | ------- ----- | ------ name| |-->|"Box"| | SL | |--\ ------- ----- ------------ | ------ | super| |----------->|Class Object| | DL | | | class ------- ------------ | / ------ | class| |--------\ ----------- | | | ------- -->|Class Class| | | | inst | 4 | ----------- | V | size ------- --------------- | caller | inst | |------>|"corner extent"| | | ------- --------------- | ------/ inst | |-- | | meth ------- | | | -----/ | | V | | | | v | X | aMethodDict | ----- | ------ | size| 4 | | | |------------------ | ----- | ------ | | class | |--------- | |- | | desc ----- ------ | | | corner| |----------\ | | | -----| | | | | extent| |--\ | ------ | | ----- | | | | | | | V | | ----/ v aMethod | | | aPoint ----- ---------------- | | | ----- | |->|"corner:extent:"|| | V | |-->2 ----- ---------------- | | aPoint ----- | |\ --------------- | | ------ | |-->3 ----- -|"corner:aC.... | | | | |--> 4 ----- | | | extent:=anE"| | | ------ -----\ --------------- | | | |--> 5 \ ---------- | | ------ |byte codes| | | ---------- | | | | -------------------------------- | | | v | aMethod ------ | ------- |"area"| | | |-/ ------ | ------- ----------------------------- | | |-->|"area |temp| temp:=... ^temp"| | ------- ----------------------------- | -->| | ---------- | | ------- \-|byte codes| | | ---------- | \---------------------------------------------- 5. (30 pts) This semester we have used a list of principles to guide our discussion of seven languages: pseudo-code, FORTRAN, Algol, Pascal, Ada, Smalltalk, and LISP. For each of the principles listed below, choose two languages and explain in what way(s) the first language better exemplifies the principle than the second language. A language may be used in only one statement, so that at the end of the this question you will have referred to six languages. a. Security >>>>>>>>>>>>>>>Pascal arrays are more secure than FORTRAN arrays, because you cannot exceed the array bounds in Pascal>>>>>>>>>>>>>>>>>> b. Abstraction >>>>>>>>>>>>>>>Algol provides better abstraction than pseudo-code, because pseudo-code abstracts practically nothing, while Algol abstracts loops, if-then statements, modularity, etc. >>>>>>>>>>>>>>>>>>>>>>>> c. Information Hiding >>>>>>>>>>>>>>> Smalltalk hides information better than LISP. Smalltalk's instance variables cannot be accessed by any outsider, while LISP's lists are all available to anyone.>>>>>>>>>>>>>>>>>>>>>>>>>>>> 6. (30 pts) We have discussed (at least) four ways to pass parameters to modules: by value, by reference, by name, by value-result. Explain the differences among these four methods and give an example or some examples, which illustrate how they all differ. >>>>>>>>>>>>>>>>Pass by value makes a copy of the actual parameter in the module. The actual parameter is unaffected by the manipulations of the copy. Pass by reference binds the formal parameter to the actual parameter so that all changes to the formal parameter are changes to the actual parameter. Call by name binds the name of the actual parameter to the formal parameter so that each time the formal parameter is referenced, the actual parameter is evaluated. Call by value result copies the value of the actual parameter into the formal parameter at the call and then copies the value of the formal parameter back into the actual parameter when exiting the module. I write the example below in Pascalish code, but consider how the code behaves as a function of the way the parameter is passed to the procedure x. program one; var t:array[1..3] of integer; j:integer; procedure x(y:integer); begin j:=2; y:=y+2; y:=y+t[1]; end; begin j:=1; t[1]:=0; t[2]:=0; x(t[j]); end. After the call to x, if t[j] is (a) passed by value, t[1]=t[2]=0 (b) passed by reference, t[1]=4, t[2]=0 (c) passed by name, t[1]=0, t[2]=2, and (d) passed by value-result, t[1]=2, t[2]=0 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 7. (10 pts)For the Pascal program below, find the static distance between the declaration of x and its use at lines 7, 10, 11, 15 and 18. 1: program one; 2: var x:integer; 3: procedure one; 4: procedure two; 5: procedure three(var x:integer); 6: begin 7: x:=4; >>>>>>>>> 0 8: end; 9: begin 10: three(x); >>>>>>>>> 2 11: x:=x+4; >>>>>>>>> 2 12: end; 13: begin 14: two; 15: x:=x-4; >>>>>>>>> 1 16: end; 17: begin 18: x:=5; >>>>>>>>> 0 19: one; 20: end. 8. (15 pts) Discuss the differences between arrays in FORTRAN and in Pascal. >>>>>>>>>>>>FORTRAN arrays are indexed only by integers and must start at 1, while Pascal arrays can be indexed by chars, integers, booleans, or an enumerated type. The bounds can start and stop anywhere. The components of FORTRAN arrays must be real or integer, while the components of a Pascal array can be practically any type. FORTRAN allows multi-dimensional arrays, whereas all Pascal arrays are of one dimension. Finally, the index to a FORTRAN array is peculiarly restricted, while Pascal arrays can have any legitimate expression as an index. >>>>>>>>>>>>>>>>>>>>>>>>>>>> 9. (25 pts) Rank the seven languages (pseudo-code, FORTRAN, Algol, Pascal, Ada, Smalltalk, and LISP) according to how well they exemplify the principle of simplicity, and explain the reasons for your ranking. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> LISP first, because there are only atoms and lists, and lists are either evaluated or left intact psuedo-code second, because there are only (at most) 20 instructions Smalltalk third, because its syntax is so simple, there are only three kinds of messages, and because evaluation of message expressions always return a single object Pascal fourth, because its arithmetic syntax is more complicated than Smalltalk's, because passing of parameters is more complicated, because there are both functions and procedures with somewhat different syntax, and because it has many more data structures Algol because it is a more complicated version of Pascal, especially in its having blocks and in its scoping of variables. FORTRAN because its rules have so many peculiar exceptions, e.g., the indexing of arrays. Ada because it is such a huge language, with so many different structures and corresponding rules. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 10. (10 pts) Explain the advantages of Pascal's strong typing of variables. Explain the advantages of Smalltalk's weak (indeed, lack of) typing of variables. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Pascal's strong typing of variables offers a strong defense against errors. Parameters cannot be passed unless there is type agreement, and expressions cannot be formed unless there is type agreement. This catches many errors at compile time, saving the programmer time and grief. Smalltalk's lack of typing makes its code very easy to use in a variety of applications. At compile time, the very simple Smalltalk syntax only need be satisfied, without regard to the type of the variables. Then, at run time, the only question that need be satisfied is whether the object understands the message, again without regard to type. >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>