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 nonempty 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 lefttoright order
and a righttoleft order in evaluating parameters when they are passed to
a method?
 In ML, is there a difference between a lefttoright order
and a righttoleft 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 (ifthenelse). 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.