COMP 80 - Programming Languages
- Spring 2008

Sample Questions for Final Exam

- 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` - (1) Explain what garbage collection means in the context of computer
programming.
(2) List one advantage and one disadvantage of using garbage
collection.
- Briefly describe one method for implementing garbage collection.
(We discussed more than one such method in class. Pick one and explain
its details.)
- 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

- 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;

- 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

until the`triangle(X,Y,Z)`*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`. - 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];

- 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 getval a = [1,2,3,3,5,6] : int list val b = [1,3,9,10] : int list

- 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

- Explain what the following
-calculus function calculates:
- Explain what the following
-calculus function calculates:
- Evaluate the following -calculus
expression
by applying reductions until
no more reductions are applicable.
Explain the reduction steps you are using.
- What are
*static method binding*and*Dynamic method binding*? Which one is more costly in terms of run time? Why?

This document was generated using the
**LaTeX**2`HTML` translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.

Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.

The command line arguments were:

**latex2html** `-split 0 -no_navigation -no_images -dir TEMPHTML fsample.tex`

The translation was initiated by Roni Khardon on 2008-04-29

Roni Khardon 2008-04-29