Part 1 of 2 – Part 1 – Multiple Choice
39.0 Points
Question 1 of 23
3.0 Points
Consider the following Scheme program:
(define mystery
(lambda (l)
(if (null? l)
nil
(append (mystery (cdr l)) (list (car l))))))
Is this program tail-recursive?
• A.
Yes, tail recursive because “car” is the last step of the function.
• B. No, not tail recursive because “mystery” does not occur last.
• C.
Yes, tail recursive, because “mystery” occurs last.
• D.
No, not tail recursive because “car” is the last step of the function.
Answer Key:B
Feedback:The subprogram is not tail-recursive because append is the last step of the subprogram. In order for it to be tail-recursive, mystery would need to be the last step.
Question 2 of 23
3.0 Points
Ada and newer versions of C++ support strongly typed enumerations. What does this mean?
• A.
Enumerated values are not treated as integers.
• B.
Type checking is performed to ensure that a value of one enumerated type cannot be assigned to a variable of a different enumerated type.
• C.
Both of the above.
• D.
None of the above.
Answer Key:C
Feedback:
Strongly typed enumerated values are human-readable names that have no numeric value. Hence, mathematical operations and comparisons cannot be performed. Also, type checking is performed to ensure that a value of one enumerated type cannot be assigned to a variable of a different enumerated type.
Question 3 of 23
3.0 Points
The runtime performance of a non-local variable lookup using a display is:
• A. Logarithmic in the number of nested subprograms
• B. Constant, but at the cost of overhead in each subprogram’s prologue and epilogue
• C. Linear in the number of activation records on the stack
• D. Linear in the number of nested subprograms
Answer Key:B
Feedback:The display provides constant time access to the top-most activation record of any active scope within the program. However, the contents of the display must be updated every time a subprogram is called or returns.
Question 4 of 23
3.0 Points
Switching back and forth between applicative and normal order evaluation while reducing a Lambda expression…
• A. is not permitted.
• B. eliminates any need for alpha conversions.
• C. may result in a different normal form than if only one type of evaluation were used.
• D. will evaluate to the same normal form as applicative order alone or normal order alone, provided one exists.
Answer Key:D
Feedback:Reducing in either normal order, applicative order, or both will yield the same normal form, provided one exists. If a normal form exists, normal order reduction is guaranteed to produce it.
Question 5 of 23
3.0 Points
Which of the following is responsible for pushing actual parameters onto an activation record?
• A. The body of the subprogram being called.
• B. The prologue of the subprogram being called.
• C. The epilogue of the calling subprogram.
• D. The body of the calling subprogram.
Answer Key:D
Feedback:The body of the calling subprogram is responsible for initially setting up the activation record, then passing control to the subprogram being called, where the prologue of the subprogram being called completes the setup of the activation record in accordance with the calling convention in use.
Question 6 of 23
3.0 Points
What is the size of a Variant in Ada?
• A. Determined by the discriminant
• B. The size of the largest field
• C. 16 bytes
• D. The sum of the sizes of all of fields, regardless of discriminant
Answer Key:A
Feedback:Correct! The size of a variant is determined solely by the discriminant, which must be passed in at the time of declaration.
Question 7 of 23
3.0 Points. Point(s) deducted for incorrect answer: 2.0
There are some similarities and differences regarding Ada variants as compared to variants in C/C++ using a free union. All references to C/C++ below assume the approach shown on slide 35 of the Types lecture.
Please check off all of the answers which are true.
A.
In both languages, the discriminant cannot be changed after the variable is declared.
B.
Both the Ada and C/C++ variants have a fixed size regardless of the discriminant.
C.
Both may serve as an alternative to using classes, and are especially useful for distributed computing.
D.
Variants make sense for Ada and C/C++ because these are both statically typed languages. Dynamically typed languages do not require any notion of a variant due to their nature.
Answer Key:C, D
Question 8 of 23
3.0 Points
Does the following expression require an alpha conversion before the next Beta reduction can be performed?
(λyx.(xyz)) (λyz.(xy))
• A.
No, because there is no free variable in the right expression.
• B.
Yes, because x is free in the right expression, but bound in the left.
• C.
No, because z is bound in both the left and right expression.
• D.
Yes, because z is bound in the right expression, but free in the left.
Answer Key:B
Feedback:Correct! The alpha conversion rule says that a variable that is free in the argument but bound in the function must be alpha-converted. In this case, x is free in the argument on the right, but bound in the function on the left.
Question 9 of 23
3.0 Points
Consider the expression: a = b = c == d;
Assume that ‘=’ is the assignment operator and ‘==’ is the equality operator. The intent of the code above is to compare c to d, and then assign the true or false result to b and then a. For this to happen according to the stated intent, what do we need?
• A.
Precedence: == higher than =, and right associativity for =
• B.
Precedence: = higher than ==, and left associativity for =
• C.
Precedence: == higher than =, and left associativity for =
• D.
Precedence: = higher than ==, and right associativity for =
Answer Key:A
Feedback:
Correct! Operator == requires higher precedence than = so that the expression (c==d) is grouped together. Now with a=b=(c==d), we additionally need right-associativity for = so that we have a=(b=(c==d)), which is the proper interpretation according to the question.
Question 10 of 23
3.0 Points
What is the main language design concern with locally declared objects whose size is determined at runtime?
• A. There is not enough room to store the objects on the runtime stack.
• B. The location of the objects on the stack frame may not be a fixed offset from the frame pointer.
• C. Dynamically sized objects must be stored in the static region
• D. Determining the types of the objects is not possible.
Answer Key:B
Question 11 of 23
3.0 Points
For most major languages, which of the following is considered the most authoritative source of information concerning the definition and usage of the language?
• A. The ISO web site.
• B. The language standard.
• C. Know-it-all types who post in the StackOverflow forums.
• D. Books written by the person or group who first invented the language.
Answer Key:B
Feedback:Correct! The language standard serves as the authoritative source of information concerning most major languages. Compilers cannot be relied upon to enforce correctness because, for example, undefined behavior may not generate any warning or error. Although books written by notable authors are useful, they are mostly intended for education purposes and may not cover the full details of the language definition. Internet-based sources such as Wikipedia and StackOverflow are not authoritative and should be used with caution.
Question 12 of 23
3.0 Points
How shall the following expression be interpreted?
λy . x λy . y λx . z
• A.
λy . (x (λy . y) (λx . z) )
• B.
(λy . x) (λy . y) (λx . z)
• C.
(λy . x λy . y) (λx . z)
• D.
λy . (x λy . (y λx . (z)))
Answer Key:D
Feedback:Application has precedence over abstraction. This means that, unless otherwise parenthesized, the body of a function should be interpreted as extending as far to the right as possible.
Question 13 of 23
3.0 Points
Which of the following parameter passing conventions will utilize the most stack space, assuming no special optimizations are in place?
• A. Passing a primitive/value type by reference
• B. Passing a large object by value
• C. Passing a large object by reference
• D. Passing a primitive/value type by value
Answer Key:B
Feedback:Passing anything by reference amounts to the stack frame holding a memory address. When passed by value, however, the object itself goes onto the stack frame. Thus, passing a large object by value will consume the most space. Special compiler optimizations may cause this to not be the case, however.
Part 2 of 2 – Part 2 – Non-Multiple Choice
40.0 Points
Question 14 of 23
4.0 Points
Write a grammar to accept the language anb2n for n >= 1. That is, “strings consisting of one or more a’s followed by b’s, where there are exactly twice as many b’s than a’s.”
Examples of strings belonging to the language: abb, aabbbb, aaabbbbbb. You may use BNF notation if you wish. You may also use epsilon transitions in your grammar, but are not obligated to.
S -> aTbb
T -> aTbb | epsilon
Model Short Answer:A ==> aAbb | eps
Comment:A bit of unnecessary duplication between the 2 productions.
Question 15 of 23
4.0 Points
Which of the following is true about statically scoped languages? Check all that apply.
A. The closest nested scope rule applies.
B. They all support nested subprograms.
C. References to non-locals require searching each frame on the runtime stack one by one, starting from the topmost stack frame downward.
D. May use displays, if subprograms are nested.
E. The location of variable declarations can be determined at compile time.
Answer Key:A, D, E
Feedback:With statically scoped languages, the location of variable declarations can be identified by looking at the program text. If the subprograms are nested, these languages may also use displays and static linkages to locate non-local variables.
Question 16 of 23
4.0 Points
What follows is a fill in the blank question with 3 blanks.
program main;
var a: real;
var b: int;
procedure sub1;
var b, c : real;
procedure sub2;
var c, a : integer;
begin [sub2]
b = …..
end; [sub2]
begin [sub1]
…
end; [sub1]
begin [main]
…
end [main]
With respect to the assignment to variable b inside of sub2, the type of b is real and it is declared inside subprogram sub1 , according to static scoping rules?
Name one language runtime data structure we’ve studied that may be used by the programming language runtime to assist in resolving the non-local reference to b? C++
Type your answers above carefully as they are automatically graded.
Answer Key:real, sub1, display|static link*|static chain
Feedback:Static linkages and displays are both used to resolve non-local references in languages that support nested subprograms.
Comment:C++ is not a data structure
Question 17 of 23
4.0 Points
What follows is a fill in the blank question with 10 blanks.
Consider the following C++ code. You can assume the code compiles:
The unqualified foo function called from main will print 2 followed by 3 , followed by 3 .
For the call to bp->foo(), is static or dynamic binding used? dynamic
For the call to dp->foo(), is static or dynamic binding used? dynamic
For the call to emd.foo(), is static or dynamic binding used? static
Is the object pointed to by bp stack or heap allocated? stack
Is the object pointed to by dp stack or heap allocated? stack
Is the object emd stack or heap allocated? heap
This code has an issue. What is it? .
Answer Key:2, 3, 3, d*, d*, s*, h*, h*, s*, memory leak
Feedback:
Note that there are 2 bindings for foo in this example: the foo belonging to one of the classes and the unqualified foo.
For the first two calls to foo in the unqualified function foo, dynamic binding is used and the version corresponding to the object pointed to is called. This is due to 2 requirements being met: foo is declared virtual and the method is being called through a polymorphic variable (i.e., pointer). The third call to foo is through a local variable. Static binding applies in this case.
The new operator is indicative of heap-based allocation. The code has a memory leak because allocated memory in unqualified foo is never freed and becomes inaccessible when unqualified foo returns.
Question 18 of 23
4.0 Points
What follows is a fill in the blank question with 2 blanks.
Coercion, pointers, and the printf function in C are all features of a static type programming language.
Answer Key:weak*, typ*
Feedback:Coercion, pointers, and C’s implementation of variable-argument functions like printf are markers of a weakly typed language because these features require the type system to be circumvented. Note that variable-argument functions in general are not necessarily weakly typed (e.g. Java).
Question 19 of 23
4.0 Points
What follows is a fill in the blank question with 2 blanks.
Consider the following regular expression:
Consider also the following input string:
X7!gB4AA
Write the portion of this string that would be matched by a greedy regex engine? X7!gB4AA
And by a lazy regex engine? X
Answer Key:X7!gB, X7!
Feedback:The ^ character means “beginning of the line”. This is followed by exactly 3 occurrences of any character, which captures the substring “X7!”. Under greedy rules, the [a-zA-Z]* will match as many alpha characters as possible and would capture “gB”, but not 4 or anything else that follows. Under lazy rules, it would capture nothing, since the Kleene star operator means “zero or more” and zero is a legal match.
Question 20 of 23
4.0 Points
What follows is a fill in the blank question with 4 blanks.
Consider the following Scheme code. Fill in the blanks below:
(let ((x 1) (y 2))
(let ((x (+ y 1)) ; value of this x is 3
(y (* x 2)) ; value of this y is 2
(s (lambda (z) (* x y z))))
(+ x y (s 3)))) ; value of (s 3) is 6
The final answer is 11 .
Answer Key:3, 2, 6, 11
Feedback:
Correct! Remember that inside a let clause, the expressions corresponding to the names x, y, and s cannot reference earlier bindings in the same let clause. Rather, they can only access the bindings in the outer let clause.
Question 21 of 23
4.0 Points
What follows is a fill in the blank question with 3 blanks.
Consider the pseudocode below:
a=5;
b=3;
foo (x, y, z)
[
y = 4;
x = z+x;
print x, y, z;
]
foo (a,b,a+b);
Under call-by-value parameter passing semantics, this program will print 13 , 4 , 8 .
Answer Key:13, 4, 8
Feedback:Correct. Under call by value, the arguments are evaluated first and applied to the function body. Upon entering the function body, the arguments (if they were printed) would print 5, 3, and 8. The assignment of y changes the value from 3 to 4, but affects the local copy only. The expression “z+x” adds 8+5.
Question 22 of 23
4.0 Points
Below is a Scheme implementation of the Make_Incr routine we studied in Ada:
(define (Make_Incr X) (lambda (Base) (+ Base X)))
(define Add_Five (Make_Incr 5))
(Add_Five 10)
Running this through the DrRacket interpreter for R5RS, one can readily verify that the program works as expected. On the other hand, the Ada version does not work due to the limits of stack-based allocation. Why do stack-based languages like Ada have so much trouble with subprograms like this? Why can functional languages handle it so smoothly? Explain as clearly and concisely as you can.
Stack-based languages like Ada has problems with fixed-size stack frame to deal with subprograms that might overload. Functional languages will not run out of memory stack frame due to its size is determined on numbers of subprograms.
Model Short Answer:The difficulty for stack-based languages arises where Make_Incr returns a closure because the non-local referencing environment containing X will no longer exist by the time Add_Five is invoked.
Comment:The problem has nothing to do with the size of the stack frame or number of subprograms. Please review.
Question 23 of 23
4.0 Points
Refer to slide 17 of the Subprograms lecture. Explain why the printf family of functions in C (printf, sprintf, fprintf, etc.) requires actual parameters to be pushed in reverse (right-to-left) order? What is the problem with pushing the actuals in the normal left-to-right order?
Be clear, concise, and use correct terminology in your answer.
It is pushed in reverse order because the called function has to deal with extra passed arguments in stack. If we push in the normal left to right order, we can’t access the first element that we tend to access and will access the last one instead.
Model Short Answer:
When the parameters are pushed in usual order, the compiler is unable to compute how far the format string is from the frame pointer, since the number and size of parameters is unknown until runtime.
Pushing the actual parameters in reverse order places the format string closest to the frame pointer at a known offset.
Comment:You are right that we cannot access the first element, but you are lacking the proper reasoning as to why.