[SOLVED] Your Name:

Your Name:
Analysis of Programming Languages Final Examination Sample Answers, Spring 2022
The test consists of 7 problems worth a total of 100 points.
1. (10%) Java classes ultimately evolved from C struct types. In what important ways are classes and structs (also known as records) different ? (Please confine yourself to semantics; if you do mention syntax, it should only be in order to explain semantics.)

Copyright By Assignmentchef assignmentchef

Answer: Here are four important ways. In addition to data members, which C structs have, Java classes also contain class methods, including one or more constructors that are used when objects of the class are created; this can be used to ensure that the object is in a consistent and well-defined state. Members of a Java class can be declared private making them off-limits to code outside the class. Java classes can inherit from other classes using extends. Java does not allow class objects to exist directly as values; Java class objects can only be manipulated via references (that is, all class variables and parameters in Java are references).
2. (25%) The next three questions concern the the figure below, which represents an S- expression. Here, each cell has a car pointer on the left and a cdr pointer on the right. Symbols are just written as words without any cell.
(a) (10%) Write down the s-expression represented by the figure. Answer: (car (cons (quote (a b)) (quote (c))))
(b) (5%) Write down the s-expression that results from its evaluation Answer: (a b)
(c) (10%) Write a diagram of the cons-cell structure representing the resulting value.

3. (20%) Write a Scheme function named setify which removes all repetitions in a list (thus making it a set). Thus (setify (a b a c d a d c)) should return (a b c d) (it doesnt matter if your function returns them in a different order). Then use this function to define a union function which takes two lists and returns the set of elements in their union. Thus (union (a b c) (c b f)) returns (a b c f).
(HINTS: You may use the built-in member function. Note if the first element of a list is contained in the rest of the list, you do not want to include it in the result; otherwise you do. Once setify is written, union is a one-liner using another built-in Scheme function.)
(define (settify L)
((null?L) ())
((member (car L) (cdr L)) (settify (cdr L)))
(#t (cons (car L) (settify (cdr L))))))
(define (union L1 L2)
(settify (append L1 L2)))
4. (10%) Each of the C functions below has a bug. Identify the bug and explain why its a bug. Suggest a fix that preserves the idea of the function.
char* triple(char* s) { char x[100];
strcpy(x, s);
strcat(x, s); // This function concatenates s onto the end of x
strcat(x, s);
Answer: triple() is returning a pointer to a local variable. The location at that address is on the call stack and will likely be overwritten by later calls. This is a dangling pointer bug. A reasonable fix would be to allocate x dynamically by replacing
char x[100];
// Allocate enough space for 3 copies and a null terminator
char *x = (char*) malloc(strlen(s)*3+1);

void longing() { char* l = long;
strcpy(l, longer);
Answer: longing() is copying to an address in the programs global section, which is where all string constants are. The global section of programs is read-only. The compiler allows this, but the program probably crashes at runtime. A reasonable fix is again to allocate l dynamically.
5. (15%) Draw the stack of activation records for the following C program after the second call to the function B. Also, what happens to the stack after that point?
void B(int);
void C(int);
int gval = 0; // global
void main() { gval = 1;
void B(int val) { if(val < 4) {void C(int val) { gval = val + 1;(NOTE: A more complete drawing here might also show the control links and return addresses in each activation record. But a key point is that gval is not part of any activation record.Answer: The stack will continue growing as B() and C() call each other recursively until C() increments gval to 4 and calls B(), which will then return without calling C() and the stack will unwind back to main().6. (10%) Explain why a left-recursive grammar like the one shown below cant be parsed with a recursive-descent parser. Write a version of this rule in EBNF and explain how recursive-descent parsing works in that case.expr expr + term | termAnswer: The problem is that the recursive descent function for expr() will immedi-ately call itself, leading to an infinite recursion. The EBNF version is: expr term {+term}This can be handled by writing the expr() function so that it calls term() and then loops while the current token is the +, calling getToken() and then term().7. (10%) Consider the following Scheme function, r. Assume that the argument passed to l is always an association list.(define (r e l)(cond ((null? l) ‘())((equal?e (car (car l))) (cons (car (cdr (car l))) (r e (cdr l))))(#t (r e (cdr l)))))(a) (5%) Compute the value of (r ‘a ‘((a b) (q v) (a e))). Show how the re-cursive calls work to compute the answer.Answer: The function returns the value (b e). The recursive calls to the function are:(r ‘a ‘((a b) (q v) (a e))),(r ‘a ‘((q v) (a e))),(r ‘a ‘((a e))), (r ‘a ‘()),The fourth (last) call returns (), the third call returns (e) because (equal? a (a e)) is true. The second call also returns (e), and the first call returns (b e).(b) (5%) What does this function do in general (again, assuming l is an association list)?Answer: By using tail recursion, the function generates the list of all values in the association list l which match the key e. Only the values are returned, not the pairs. CS: assignmentchef QQ: 1823890830 Email: [email protected]