COMP 80 - Programming Languages - Spring 2008

Sample Questions for Final Exam

1. The alphabet for the following regular expressions includes exactly the letters a, b, c. The parentheses indicate grouping, * indicates Kleene's star. Consider the regular languages generated by the expressions
L1 = a*b* (a|c) (a*b)*
L2 = (a|b)* c (a|b)*

Give a string in the language of L1 but not in the language of L2

Give a string in the language of L2 but not in the language of L1

2. (1) Explain what garbage collection means in the context of computer programming. (2) List one advantage and one disadvantage of using garbage collection.

3. Briefly describe one method for implementing garbage collection. (We discussed more than one such method in class. Pick one and explain its details.)

4. Recall that in C++ we can choose between row-major'' and row-pointers'' memory allocations for (two dimensional) array.

Briefly explain the difference between the two

Give a code fragment that declares, allocates, and initializes a two dimensional array using row-major allocation

Give a code fragment that declares, allocates, and initializes a two dimensional array using row-pointers allocation

5. Study the following ML code and (1) give the values of a1, b1, a2, b2, a3, b3, (2) explain your answer (do the values change? why?)
val x = 5;
fun f1 y = x+y;
fun f2 z = z * f1 2;

val a1 = f1 5;
val b1 = f2 5;

val x = 10;

val a2 = f1 5;
val b2 = f2 5;

fun f1 y = x-y;

val a3 = f1 5;
val b3 = f2 5;


6. Consult the following Prolog code:
e(1,2).
e(3,1).
e(2,1).
e(1,1).
e(2,3).
e(1,3).

triangle(A,B,C) :- e(A,B),e(B,C),e(C,A).


(1) Draw the search tree (as we did in class) for running the query triangle(X,Y,Z) until the third output is produced. Make sure to annotate the tree with binding for variables. In addition, mark potential backtracking points in the tree.

(2) To clarify your answer from above, list the first 3 answers produced by the system on the query triangle(X,Y,Z). For each answer give the binding for X, Y, Z.

7. Study the following code and (1) give the type of the function f (2) briefly explain how you inferred the type (3) give the value of a and explain how you computed it. (The function foldl is included for your convenience - it is identical to the one covered in class).
fun foldl f e [] = e
|  foldl f e (h::t) =
foldl f (f(h,e)) t;

fun f L = foldl (fn(x,y) => 10*y+x) 0 L;

val a = f [1,2,3];


8. Write a function in ML that takes two sorted integer lists as input and produces a sorted merged list as illustrated by the following examples. The type of the function is:
val merge = fn : int list * int list -> int list

and when running the function with:
val a = merge([1,3,5],[2,3,6]);
val b = merge([10],[1,3,9]);

we get
val a = [1,2,3,3,5,6] : int list
val b = [1,3,9,10] : int list


9. Write a Prolog procedure length2sub(L,Out) whose input L is a list and whose output Out is a subset of L with exactly two elements. Backtracking using ; should produce all such subsets as illustrated by the following examples.

You may not assume or use any list library functions. If you need such a function you should give the code for it as well.

?- length2sub([a,b,c,a],Out).
Out = [a, b] ;
Out = [a, c] ;
Out = [a, a] ;
Out = [b, c] ;
Out = [b, a] ;
Out = [c, a] ;
No

?- length2sub([1,2],Out).
Out = [1, 2] ;
No

?- length2sub([1],Out).
No


10. Explain what the following -calculus function calculates:

11. Explain what the following -calculus function calculates:

12. Evaluate the following -calculus expression by applying reductions until no more reductions are applicable. Explain the reduction steps you are using.

13. What are static method binding and Dynamic method binding? Which one is more costly in terms of run time? Why?