Midterm Exam 1

CSE 428
Fall 2000

Midterm #1
Test Form A

27 September 2000

The next five questions refer to the following grammar:

        E ::=  E ``*'' F | F 
        F ::=  F ``+'' G | G 
        G ::=  ``--'' H | H 
        H ::=  N | Id | ``('' E ``)''

This grammar:
- (A) is ambiguous
- (B) has more than one parse tree for some string
- (C) does not define a language
- (D) recognizes only ambiguous strings
- (E) is unambiguous
The operator precedences enforced by this grammar are:
- (A) None
- (B) ``*'' lower than ``+''; and ``+'' lower than ``-''
- (C) ``*'' higher than ``+''; and ``+'' higher than ``-''
- (D) ``*'' lower than ``+''; and ``-'' lower than ``*''
- (E) arbitrary
The operators ``*'' and ``+'' are:
- (A) both left associative
- (B) both right associative
- (C) neither left nor right associative
- (D) both left and right associative
- (E) unknown associativity
Which of the following strings cannot be generated by this grammar:
- (A) ``3+4*5''
- (B) ``- 5''
- (C) ``((--(2+2)))''
- (D) ``-(-5 + 6)''
- (E) ``(2 + - 5)''
If we change the second line of the grammar to be
```
        F & ::= & F ``+'' G | F ``--'' G | G
```
then
- (A) The new grammar is ambiguous
- (B) The new grammar is unambiguous
- (C) The binary operator ``--'' has lower precedence than ``+''
- (D) The binary operator ``--'' has higher precedence than ``+''
- (E) The new grammar recognizes exactly the same strings as the original grammar
The formal specification of a programming language consists of
- (A) A definition of the set of legal programs in the language
- (B) An implementation of the language
- (C) A context-free grammar and typing rules
- (D) A large sample of legal programs
- (E) Its syntax and semantics
Static typing
- (A) is not used by modern languages
- (B) requires programs to be type-checked at run time
- (C) allows programs to be type-checked at compile time
- (D) cannot be used by languages that are implemented by a compiler
- (E) slows down the execution of programs
Static scoping
- (A) is not used by modern languages
- (B) binds all uses of identifiers to declarations at compile time
- (B) binds all uses of identifiers to declarations at run time
- (D) cannot be used by languages that are implemented by a compiler
- (E) makes programs more difficult to understand
An advantage of interpreting over compiling is
- (A) faster execution speed
- (B) better use of machine-specific instructions
- (C) more optimizations possible
- (D) better debugging tools
- (E) no need for run-time type checking
An advantage of compiling over interpreting is
- (A) easier to construct
- (B) better debugging tools
- (C) more optimizations possible
- (D) better error handling
- (E) portability
For the next five items, specify the most general type of the given function definition.
fun f (x,y) = if x>0 then x+y else x-y
- (A) int
- (B) int -> int -> int
- (C) (int * int ) -> int
- (D) (int * 'a) -> int
- (E) int ->int
fun s(x,y) = (y,x)
- (A) ('a * 'b) -> ('b * 'a)
- (B) (int * int ) -> (int *int )
- (C) ('a * 'a) -> ('a * 'a)
- (D) ('a * 'b)
- (E) 'a -> 'a
```
fun g (0,h,y) = y
   |g (n,h,y) = h(g(n-1,h,y)) + 1.0
```
- (A) int
- (B) (int *int * real) -> real
- (C) (int *(real-> int )* real) -> real
- (D) (int *(int -> real)* real) -> real
- (E) (int *(real-> real)* real) -> real
```
fun nfold(f,0,x) = x
   |nfold(f,n,x) = f(nfold(f,n-1,x))
```
- (A) int
- (B) ('a * int * 'a) -> 'a
- (C) (('a -> 'b) * int * 'a) -> 'b
- (D) ((int -> int ) * int * int ) -> int
- (E) (('a -> 'a) * int * 'a) -> 'a
fun qz x = (fn y => x+y)
- (A) int -> int -> int
- (B) (int -> int ) -> int
- (C) int * int -> int
- (D) int -> int
- (E) int
For the next five items, specify the value of the given expression, assuming the following definitions
```
fun s n = n+1;
fun compose(f,g) = fn x => f(g(x));
fun twice(f,y) = f(f(y));
fun ctwice f y = f(f(y));
fun sum(g,0) = g(0)
   |sum(g,n) = g(n) + sum(g,n-1);
```
(fn f => (fn x=>f(f(f x)))) s 1
- (A) 1
- (B) 2
- (C) 3
- (D) 4
- (E) 5
twice(compose(s,s),0)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
sum(fn x=>x*x-2,3)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
compose(fn x=>x+1,fn y=>y-1)(4)
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
twice(ctwice,s) 2
- (A) 0
- (B) 2
- (C) 4
- (D) 6
- (E) 8
Which of the following is an inductive definition of natural numbers:
- (A) 0,1,2,3,...
- (B) 0 is a natural number; if n is a natural number then n+1 is a natural number, for all n> 0
- (C) all integers greater than or equal to 0
- (D) n is a natural number, for all n> 0
- (E) {n | n> 0}

Consider two definitions of factorial:

fun fact 0 = 1                 local
   |fact n = n * fact(n-1);      fun tfact(0,k) = k
                                    |tfact(n,k) = tfact(n-1,n*k)
                               in
                                 fun fastfact n = tfact(n,1)
                               end;

We can prove fact(n) = fastfact(n) by applying mathematical induction (over n) to what property:

(A) fact(n) = tfact(n,1)
(B) k*fact(n) = tfact(n,k)
(C) fact(n) = fastfact(n)
(D) fact(n) = tfact(n,k)
(E) fact(n*k) = tfact(n,k)

Consider the following Standard ML function:
```
  fun petruchio(nil,nil) = true
     |petruchio(x::xs,y::ys) = petruchio(xs,ys)
     |petruchio(xs,ys) = false
```
What does this function do:
- (A) test whether two lists are identical
- (B) test whether two lists are of the same type
- (C) test whether two lists are the same length
- (D) test whether two lists contain the same elements
- (E) test whether it is given two lists as arguments
The language Standard ML is higher order because
- (A) it is an upper-class language
- (B) it does not contain assignment
- (C) it is purely functional
- (D) it has a well-defined semantics
- (E) functions can be passed as values and returned as results
The Penn State women's volleyball team
- (A) was national champions last year
- (B) is fun to watch
- (C) has the longest home winning streak
- (D) plays in Rec Hall
- (E) all of the above