Solution to midterm 2

1. (20 points) Lackwit implements a polymorphic type inference algorithm. Give an example that illustrates the power of polymorphic type inference (as opposed to monomorphic type inference). Explain in your own words how the example illustrates polymorphic type inference.
Answer: fun id x = x
if we do polymorphic type inference of this, we would get the type 'a->'a. So if we call id with an int, we get back the same type (int). The power of this is that callers of id get accurate type information.

2. (20 points) The following two statements have sometimes been made by opponents and proponents of safe typing: "Programs written in safely typed languages are slower than those written in languages such as C" and "Programs written in safely typed languages can be faster than those written in languages such as C". In other words, in some situations, safe typing has a cost while in other situations, safe typing can allow optimizations that would be perhaps very hard to do for languages such as C. GIve one example in support of each argument.
Answer: opponent of safe typing:

-some operations require run time checks at runtime which slows down program: e.g.

array bounds checking
 
Proponent of static type checking:
-Can do type based analysis and optimization
e.g. S1<:T, S2<:T, lets say T has a field f which is inherited by S1 and S2.
var s1:S1; s2:S2;
s1->f = 10
s2->f = 20

one knows in a statically/safely typed language that s1 & s2 cannot possibly point
to same objects & thus the two statements can be reordered if needed by optimizations.

3. (20 points) Assume that you have a language for which you can correctly find all the pointers in the stack and in the heap. For such a language, give the advantages and disadvantages of each of the three basic collection schemes we looked aat in class: reference counting, copying, and mark and sweep. Base your argument on the following criteria: (i)number of instructins to do allocation, (ii)number of instructions to do garbage collection, (iii)accuracy of collection (i.e., which scheme collects more objects). Note that you don't actually need to list the number of instructions for each of the collection schemes in part (i) and (ii); you just need to argue which scheme will use fewer instructions.
Answer:
(i)Mark and sweep and reference counting are both expensive at allocation since we need to search "free lists". Copying is fast since free space is compacted.
(ii)Mark and sweep and reference counting cost depends on all the allocated objects. Coping cost depends only on live objects. If most objects are dead, copying may be faster, otherwise mark and sweep and reference counting will be faster.
(iii)Accuracy: Reference counting will not collect cycles. The other two algorithms will collect cycles.