CSE 341, Final Exam, Spring 1997

Final Exam, June 12, 1997

Closed Book, Closed Notes
One hour, fifty minutes
Answer the problems on the exam paper.
If you need extra space use the back of a page
Problems are not of equal difficulty, if you get stuck on a problem, move on.
Be concise on short answer questions - but provide clear explanations.

Problem 1 (14 points) Give functional programs for the following problems. Your answers will not be graded on syntax - but try to make your programs look as much like ML as possible:

Find the maximum value in a non-empty list of integers.
Given integers x and n, build a list consisting of the first n Notkin numbers which are greater than or equal to x. Use the built in predicate isNotkin which returns true if its argument is a Notkin number, and false otherwise.

Problem 2 (6 points)

Consider the function maplist

fun maplist f nil = nil
|   maplist f (L as x::xs) = (f L) :: maplist f xs;

What is the result of the following call to maplist:
```
maplist (fn(x) => x) [1, 2, 3];
```
How does maplist differ from the built in ML function map and the LISP function MAPCAR?

Problem 3 (10 points)

In Java, is there a difference between a left-to-right order and a right-to-left order in evaluating parameters when they are passed to a method?
In ML, is there a difference between a left-to-right order and a right-to-left order in evaluating parameters when they are passed to a function? (Just consider the subset of ML that we used in class - no refs or arrays).

Problem 4 (8 points)

List four significant differences between Java and C++.

Problem 5 (6 points)

Suppose you have the Prolog rules:

a(X) :- b(X), c(X).
a(X) :- c(X), d(X).
a(X) :- b(X), d(X).

When is a(X) true?

Problem 6 (12 points)

Consider the following Prolog program.

a([],[]).
a([1],[1]).
a([0],[0]).
a([0, 0 | L1], L2) :- a([0 | L1], L2).
a([0, 1 | L1], [0 | L2]) :- a([1 | L1], L2).
a([1, 0 | L1], [1 | L2]) :- a([0 | L1], L2).
a([1, 1 | L1], L2) :- a([1 | L1], L2).

What are the results of the following queries:

| ?- a([1,1], [1]).

| ?- a([1,0], [0]).

| ?- a([1,1,1], X).

| ?- a([1,1,0,0,1,1,1], X).

| ?- a(X,[0]).

Give a one or two sentence description of the relation a?

Problem 7 (12 points)

How does pattern matching differ between Prolog and ML?
How does ML determine the type of a variable?
How does C determine the type of a variable?
How does LISP determine the type of a variable?

Problem 8 (10 Points)

Provide the response that Common Lisp will give to each of the input expressions.

USER(1): (cond ((and (= 1 2) (= 3 4)) 5) (t 6))

USER(2): (car (cdr (cdr '(car cdr cdr car))))

USER(3): (append '(1 2 3) '(4 5 6))

USER(4): (mapcar #'(lambda (x) (* x x)) '(1 3 5 7))

USER(5): (defun ssq (L)
            (cond ((null L) 0)
                  (t (+ (* (car L) (car L)) (ssq (cdr L))))))

;; No need to give an answer for USER(5),  Common Lisp just responds SSQ.

USER(6): (ssq '(1 5 10))

Problem 9 (12 points)

Here is a Java implementation of an Animal class:


class Animal {
  boolean canFly () {
    return false;
  }

  boolean canSwim () {
    return false;
  }
}

Suppose you wished to include classes Mammal, Bird, Fish, Whale, Kangaroo, Bat, Ostrich, Penguin, Eagle, Flying Fish, and Gold Fish. Give a diagram of the resulting class hierarchy.
Give the implementations of the classes Bird, Ostrich, Penguin and Eagle, including the canFly() and canSwim() methods as necessary.

Problem 10 (10 points)

Briefly describe the meaning of the following Java terms/keywords/classes.

this
interface
catch
Integer
Vector
unicode
protected
InputStream
Component
static

Problem 11 (20 points)

Which language is more powerful: Logo or the Lambda Calculus?
The language ABD (Almost Brain Dead, I just made it up) allows programmers to use only a single goto, and no loops or function calls in their programs. The language does provide variables, expressions, and conditionals (if-then-else). How powerful is the ABD language?
What is dynamic scoping?
What is aliasing?
What does it mean for one variable to hide another?
Could a version of LISP allow overloaded functions? Why or why not.
Can a language which gives users access to pointers be type safe?
C allows the user to define macros which look a lot like functions, e.g., swap can be implemented as a macro. How do these macros differ from functions in terms of scope and parameter passing?
How does a reference counting garbage collector differ from a copying garbage collector?
Suppose you are asked to implement a garbage collector for a language which relies exclusively on static allocation. What do you do?

Problem 12 (10 points)

(0 points) What is your favorite programming language?
(10 points) Why? Give three reasons why it is a good language.