- Statically typed languages associate a fixed type with every variable at compile time. The compiler makes sure that your code does not try to assign a value of a different type to this variable and produces an error when you do. Dynamically typed languages on the other hand allow values of arbitrary types to be assigned to any variable. The type of the value stored in a variable may even change over the course of your program’s execution. Select all correct statements in the following list (and only the correctones).
A.Dynamic typing is more flexible.
B.Dynamic typing is safer. The program is less likely to crash because a wider range of operations are allowed and thus won’t lead to runtime errors.
C.Dynamic typing is more efficient because it eliminates type checking.
D.Static typing is safer because assigning an integer to a string variable, for example, is usually an error in the logic of your program and the compiler will catch such errors.
E.Static typing is more efficient because the size and type of the data stored in a variable is known at compile time, so the compiler can generate efficient code to manipulate these data.
- Consider the following statements and select all those that are true, and only
A.Exception handling allows us to associate exception handlers with different parts of our code. The exception handlers active in any part of the code can be managed without runtime overhead (compared to not supporting exception handling); a cost is incurred only when an exception is raised.
B.Call by sharing is the result of using call by value with a reference model of variables.
C.If f() is a function with a long list of optional arguments, calling it without these optional arguments can be much faster than providing these arguments.
D.Call by sharing was invented as a parameter passing mode that provides a mechanism for the callee to pass information back to the caller in a controlled fashion, without giving the callee the ability to overwrite the caller’s actual parameter with arbitrary values.
- Haskell supports polymorphic functions. These are functions that can be applied to arguments of any type, possibly subject to the constraint that the type must be an instance of a set of type classes. Java supports generic functions.Again, these are functions that can be applied to arguments of any type, possibly subject to the constraint that the type
must implement a set of interfaces. In Haskell, the language itself does not constrain what types can be arguments to such a function; only the programmer imposes such constraints in the form of type classes. At this point, Java allows only class types, not primitive types such as int, bool or char to be used as arguments to generic functions.
Now let us call a type a value type if the language uses a value model for variables that store values of this type; if the language uses a reference model for variables that store values of a given type, then the type is a reference type. In Haskell, all types are reference types. In Java, primitive types are value types and classes are reference types.
One thing that Haskell and Java have in common is that the compiler translates a polymorphic/generic function into one function in machine code or JVM byte code that can be applied to any argument type. The machine code does not contain a specialized version of the function for each type to which we apply the function.
Now consider the approaches to generics taken by C++ and Rust. From the programmer’s perspective, Rust generics and C++ templates are fairly similar to Java generics. However, both C++ and Rust allow generics/templates to be applied to any type even though all types in C++ and Rust are value types. When it comes to compilation, both the C++ compiler and the Rust compiler do produce specialized machine code versions of a generic function or template, one version per data type to which we apply the function.
Here’s the summary of this situation:
| Language | Variable model | Types that can be used with generics | Implementation of generics |
| Haskell | Reference model for all
types |
Any type | One compiled function
applicable to any type |
|
Java |
Value model for primitive types
Reference model for class types |
Only class types |
One compiled function applicable to any (class type |
|
C++/Rust |
Value model for all types |
Any type |
Many compiled version
of the function, one per type it is applied to |
Question:
A.Explain why Haskell and Java support polymorphism/generics only for reference types. Specifically, discuss why supporting generics using a single compiled function, as Haskell/Java do, is much easier for reference types than when supporting generics also for
value types.
B.Is the C++/Rust approach of generating many specialized compiled versions of the function the only possible solution when allowing generics also for value types or is there a way for the compiler to generate a single compiled function that can support both value and reference types? Discuss.
- Inclass, we discussed different parameter passing Consider the following code:
-
proceduremain()
-
Obj x =newObj()
-
setLabel("Foo") -
bar(x)
-
print(x.label())
-
end 7
-
procedurebar(x)
-
Obj y =newObj()
-
setLabel("Bar1") -
setLabel("Bar2") -
x = y
-
end
Now assume we call main() and that label() returns the label of an object set using setLabel(). For each of the following parameter passing modes, select the output printed by the print(x) statement in line 5.
Call by value
Call by value/return Call by sharing Call by reference
1.Foo 2.Bar1 3.Bar2
- This question is about Prolog’ssolution Consider the following database: a(X,Y) :- b(X,Y).
a(1,2). b(X,Y) :- c(X), d(Y). b(3,4). c(5). c(6). d(7). d(8).
The output you see when you ask the query a(X, Y) is:
?- a(X,Y). X = 5, Y = 7 ; X = 5, Y = 8 ; X = 6, Y = 7 ; X = 6, Y = 8 ; X = 3, Y = 4 ; X = 1, Y = 2.
Explain how Prolog finds this set of answers. I am not looking for the general answer that Prolog uses unification and backtracking but for a concrete answer that explains how Prolog’s search procedure leads to this specific answer.
- Thisis a continuation of the previous question about Prolog’s solution We have now added a cut to the first rule for b(X, Y):
a(X,Y) :- b(X,Y). a(1,2). b(X,Y) :- c(X), !, d(Y). b(3,4). c(5). c(6). c(7). c(8).
The output you see when you ask the query a(X, Y) is:
?- a(X,Y). X = 5, Y = 7 ; X = 5, Y = 8 ; X = 1, Y = 2.
Explain how the cut leads to this reduced set of answers. Again, I am not looking for the general answer that the cut eliminates some choices but a concrete explanation of why the answers
X = 6, Y = 7 ; X = 6, Y = 8 ; X = 3, Y = 4 ;
are not found.
- Consider a language L of strings over the alphabet {a, b} defined by the following grammar:
S -> AM M -> S | ε A -> aE | bAA E -> aB | bA | ε B -> bE | aBB
Describe in plain English the language defined by this grammar.
8.
Here is the grammar from the previous question again, this time split into individual productions:
S -> AM M -> S M -> ε A -> aE A -> bAA E -> aB E -> bA E -> ε B -> bE B -> aBB
For each production, choose the correct predictor set.
- Different types of objects are stored in different memory regions during runtime. The three primary regions we are concerned about are the program’s static address space, the stack, and the heap. For each of the following objects, select the memory region that is most appropriate for storing
- Consider the following code example in pseudo-Pascal. Every function definition is of the form procedure name … begin … end. Local definitions of each procedure (local variables, nested procedures) occur between procedure and begin. The statements that are executed when calling the procedure occur between begin and
-
procedureA()
-
varx
-
procedureB()
-
procedureC()
-
begin
6 x = 5
-
end
-
procedureD()
-
begin
10 C()
-
end
-
begin 13 D()
-
end
-
procedureE()
-
procedureF()
-
varx
-
begin
19 ...
-
end
-
procedureG()
-
begin
23 B()
-
end
-
begin 26 F()
27 G()
-
end
-
begin 30 E()
31 end
Assume A() is the first function we call and consider the state of the call stack at the time we reach line 6.
Question 1: List the sequence of stack frames on the call stack at the time we reach line 6 from bottom to top. List the function names without spaces. For example, if the bottommost stack frame belongs to procedure A(), the next stack frame on top of it belongs to B(), the next stack frame on top of that belongs to C(), and the topmost stack frame belongs to another invocation of A(), your answer should be “ABCA”.
Question 2: Assume our language uses static scoping. How many static links need to be followed at runtime to locate the variable x accessed in line 6. Provide a numerical answer (e.g., 4).
Question 3: Now assume the language uses dynamic scoping. How many dynamic links need to be followed at runtime to locate the variable x accessed in line 6. Provide a numerical answer (e.g., 3).
- Consider the following codesnippet:
*p = 5; x = 3; *q = *p + x;
As a reminder, this means that p and q are pointers and *p and *q access the memory locations referenced by p and q. p, q, and x are defined somewhere before you reach these three assignments. From the following list of options, select all possible combinations of values of *p, *q, and x after executing these three assignments. The result depends on where p and q point.
Question options:
*p = 5, *q = 8, x = 3 *p = 8, *q = 8, x = 3 *p = 5, *q = 8, x = 8 *p = 5, *q = 10, x = 10 *p = 3, *q = 6, x = 3 *p = 3, *q = 8, x = 3 *p = 3, *q = 6, x = 6 *p = 6, *q = 6, x = 6
- Select all of the statements in the following list that describe problems that can ariseif a language uses normal order evaluation of function arguments and cannot arise if the language uses applicative order evaluation of function
A.Side effects of the argument evaluation can happen more than once.
B.The function execution may be less efficient because some function arguments may be evaluated even when the callee does not need to know their value.
C.Recursion becomes difficult to implement because normal order evaluation amounts to textual replacement of the argument expression into every expression where the callee refers to the argument.
D.If the callee accesses the value of an argument more than once, each access may yield a different value.
E.The function execution may be less efficient because function arguments may be evaluated more than once.
