UMBC CMSC 331 Fall'00: Principles of Programming Languages

[an error occurred while processing this directive]

Review for CMSC 331 Final

Here is a list of topics that you should be familiar with. You should:

Be able to explain the difference between high level and low level languages
Be able to name four benefits provided by high level languages
Be able to explain the difference between a compiler and an interpreter
Understand the basic difference between semantics and syntax
Understand the difference between prefix, postfix and infix notation
Understand operator precedence and associatively
Be able to write a simple BNF grammar for a language described in English.
Be able to show a parse tree given a grammar and a string in that language
Be able to prove that a BNF grammar is ambiguous and to show how to change it to remove the ambiguity.
Be able to explain what an invariant is and be able to identify them in an algorithm
Know the difference between a data object and data representation
Understand the difference row-major and column-major layouts for multidimensional arrays
Be able to explain the differences between records and arrays
Understand unions and why they are not type safe
Understand pointers: why they are used and the problems they bring
Understand type checking and type equivalence
Be able to illustrate the difference between lexical and dynamic scope
Be able to explain different kinds of polymorphism and give an example of each
Be able to explain several benefits of inheritance
Be able to explain the idea of exceptions and how they work in Java
Be able to explain the idea of garbage collection and why it's useful
Be able to explain interfaces in Java and the idea of interfaces as "adjectives" (e.g. class Foo implements Sortable) and why coding "to an interface" increases code reusability
Be able to compared and contrast procedural (e.g. C) programming with object oriented programming
Be able to compare and contrast functional and imperative programming languages
Understand that functional programming is expression-oriented programming and that programs are expressions that evaluate to values
Be able to understand simple programs written in java, Lisp and ML (section 0101) or Prolog (section 0201)
Be able to define basic data structures using Lisp lists and to write simple recursive list processing functions.
Be able to write simple programs written in Java, Lisp and ML (section 0101) or Prolog (section 0201)
Understand that programming languages are simply tools that we use to do our job of solving problems!

General

You are developing a program and must choose between two imperative languages, one of which is interpreted and the other of which is compiled. Under what conditions should you use one instead of the other? Under what conditions does your choice not matter? Cover the following (mutually exclusive) conditions:
1. You're in a hurry to make the program work.
2. The program must execute efficiently and with maximal speed.
3. The program must occupy very little memory.
4. The program needs a lot of dynamic memory.
5. The program is huge.
6. The program is small.
7. The program must be ported to a lot of machines.
True or False: In any object-oriented programming language, if object a is an instance of class A, and object b is an instance of class B, and B is a subclass of A, then the amount of data in b is less than or equal to the amount of data in a. Why is this true or false?
For each of C++, Java, and Lisp and Prolog, give: (1) An application that is well-suited to this language (e.g., Device Drivers to C++) (No, you can't use that example), (2) What needs of the application make it well-suited to the language (e.g., need for low-level, fast code), (3) What characteristics of the language match the needs of the application (e.g., C++ lets you manipulate memory efficiently).
Consider the following BNF grammar:

<face> ::= <eyes><mouth> | <mouth><eyes>
<eyes> ::= ":" | ";" 
<mouth> ::= "(" | ")" | "<" | ">"

List all possible faces according to this grammar.
Is the language of faces context-free? Why?
Let's write a new grammar which includes all faces, for example `{-:#', `]=:', `[^:', `(v:'and similar ones.
```
<hair> ::= "#" | "
<brow> ::= "<" | ">" | "/" | "\" | "|"
<eyes> ::= ":" | ";" | "!" 
<nose> ::= "-" | "~" | "=" | "+" | "v" | "^"
<mouth> ::= "(" | ")" | "<" | ">" 
          | "[" | "]" | "{" | "}"
          | "O" | "C" | "D" | "Q"
```
Write a revised set of grammar rules for so that
1. A face can be drawn either left-to-right or right-to-left.
2. Eyes and mouth constitute a face.
3. Nose is optional but must appear between eyes and mouth (no cubism).
4. Brows are optional but must appear above eyes.
5. Hair is optional and must appear above either eyes or optional brows.
(extra credit) Describe the semantics of the following faces:
1. :+Q
2. D-;|

Java

What is the "sandbox" model of execution? Where and why is it employed in Java?
Java programs fall into one of two categories: applications and applets. Explain the major differences between the two. Give an example class definition (i.e., the line that includes the word "class") for each.
Java's event model is used heavily in providing GUI (Graphical User Interface) support. Explain the principles of the event model. Illustrate your explanation by describing how a program could respond to a Button that a user might press.
What is "the AWT"? SWING? How do they differ?
Explain why, as a general principle, the attributes of a class should be declared private or protected.
An array containing the first 5 prime numbers is required as part of a class. Write a single line of code that declares and initialises the array together with ensuring its values can't be changed subsequently.
Write a method getValidAge() that reads a valid age for a human being from the user (keyboard). The method should have the following signature: public static int getValidAge() A valid age is one considered to be between 0 and 125 inclusive.
What's a design pattern? What's it good for?
Why would anyone ever want to use Model-View-Controller pattern? Why would anyone ever not want to use Model-View-Controller pattern?

Lisp

What does (weird 1) return given this definition:

(defun weird (i) 
  (let ((i (* i 2))) 
    (let ((i (* i 3))) 
      i)))

Given the Lisp functions

(defun w1 (i) (setq i 1) i)
(defun w2 (i) (setf (car i) 2) 'i)
(defun w3 () (let ((i 3) (j '(4 5))) (w1 i) (w2 j) (list i j)))

what are the values of (w1 3), (w2 '(4 5)), and (w3)?

The builtin Lisp function mapcar applies a function to each element of a list and returns a list of all results. Implement it in Lisp recursively without using any other mapping function or global variables. You may not use `map', `mapc', `mapcan', etc. You will at least need `if', `null', `cons', `car', `cdr', and `apply'. Examples:
```
(defun add (lst) (+ (car lst) (cadr lst)))
(mapcar #'add '()) => ()
(mapcar #'add '((1 2) (3 4))) => (3 7)
(mapcar #'(lambda (i) (+ i 1)) '(1 2 3 4)) => (2 3 4 5)
```
Write mapcar for 2 arguments only -- don't worry the extra cases described in books.
Write iota as a LISP function that takes a positive integer as an argument and returns a list of the numbers between 1 and that integer.
```
clisp> (iota 5)
(1 2 3 4 5)
clisp> (iota 0)
nil
clisp> (iota -2)
nil
```
Consider the following Lisp function definition:

(defun mystery (lis a) (cond ((null lis) a) (t (mystery (cdr lis) (cons (car lis) a))) ))

Give the values of the following expressions, explaining your reasoning.

(mystery '() '(1 2 3 4 5))

(mystery '(1 2 3 4 5) '())

What does y evaluate to in the following and why does this not mean that LISP is call-by-reference?
```
Clisp> (defun foo (x) (setf (car x) 1))
Clisp> (setf y '(a b c))
Clisp> (foo y)
Clisp> y
```

Prolog

Below are three prolog definitions of member/2. For each version, simulate repeated attempts to satisfy the goal member(X,[a,b,c,d]) and give the sequence of instantiations of X which are produced from these attempts.
1. ```
member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y).
```
2. ```
member(X,[X|_]) :- !.
member(X,[_|Y]) :- member(X,Y).
```
3. ```
member(X,[X|_]).
member(X,[_|Y]) :- member(X,Y),!.
```

Consider the Prolog program:

male(paul):-!. 
male(harry).
female(sue). 
likes(paul,X):-female(X).
likes(X,jody):-male(X).
likes(paul,jody):-!. 
likes(X,jody):-female(X).

Give the sequence of all satisfactions of ?- likes(X,Y). in order.

Describe the bindings which occur when the following Prolog goals are executed:
1. ?- fun(X,[A|B])=fun(a,[B,c,d]).
2. ?- [A,b,[C,d]]=[[b,C],C|T].
3. ?- [a,b]=[A].
Mre prolog
1. Simplify the following Prolog program so that it has as few variables in each clause as possible (by exploiting list matching).
```
interlace([],[],[]). 
interlace(A,X,B):-A=[C|T],B=[D|U],C=D,interlace(T,X,U).
interlace(X,A,B):-A=[C|T],B=[D|U],C=D,interlace(X,T,U).
```
2. Then give the sequence of all instantiations of X for the query
```
?- interlace([a,b],[c,d],X).
```
Given the Prolog database:
```
foo(a,100). 
foo(b,200).
foo(c,150).
foo(c,200):-!.
foo(c,250).
foo(X,Y):-foo(X,_),!,foo(_,Y).
```
Give all instantiations of variables (in order) for repeated satisfaction attempts of the goals:
- ?- [a,b,c]=[H,I|T].
- ?- [X,a,Y]=[[c,d]|[a,X]].
- ?- foo(X,Y).
- ?- foo(b,Y).
- ?- foo(X,150).
Write a Prolog goal iota that takes a single argument that is a positive integer, and returns a list of the integers between 1 and that argument(iota is handy when you want to write a `for' loop in prolog. iota(X,Y),member(Z,Y) is the same as `for Z from 1 to X'.).

?- iota(5,X). 
X=[1,2,3,4,5];
no
?- iota(0,X).
no
?- iota(-10,X).
no

Review for CMSC 331 Final

General

Java

Lisp

Prolog

ML