Test 2 Solutions: Questions
[8 pts] What is the most general possible type for the following Haskell function? Describe the type using Haskell syntax.
threshold f z x = if f x < z then f x else z
[12 pts] Consider the Python program below.
def a():
nonlocal x
x = 9
def b():
x = 8 # creates a new 'x' variable hiding the global 'x'
a()
print(x)
x = 7 # creates a global 'x' variable
b()
print(x)
a. If Python used dynamically scoped variables, what would this program display?
b. Why do all modern languages use lexical scoping (static scoping) rather than dynamic scoping?
[8 pts]
Explain why the variable arr in the below Python program
cannot be stored on the stack.
def sequenceComputer(a, b):
arr = [a, b]
def sequenceComp(n):
while len(arr) <= n:
arr.append(arr[-2] + arr[-1])
return arr[n]
return sequenceComp
fib = sequenceComputer(0, 1)
print(fib(20))
[8 pts] Both C++ and Java allow a programmer to use a class name as a parameter to a generic class. Neglecting syntax and other usage rules, distinguish how the language have a different underlying implementation of such generics.
[8 pts] Convert the following Haskell function into an equivalent tail-recursive function.
hailstone n | n == 1 = 1
| odd n = 1 + hailstone (3 * n + 1)
| even n = 1 + hailstone (n `div` 2)
[10 pts] Prove the following using our axiomatic scheme, including the Rules of Preconditions, Assignment, and Sequence.
{ x ≥ 1 }y = x * x;{ y ≥ 1 }
[6 pts] What loop invariant allows you to prove the postcondition for the following?
{ n ≥ 1 }k = a[n];
i = n - 1;
while (i >= 1) {
k = k + a[i];
i = i - 1;
}
{ k = ∑j = 1n aj }
[6 pts]
Convert the following Haskell expression using do
notation to the equivalent non-do form using the Monad
operators >> and >>=.
do putStr "Name: "
name <- getLine
putStrLn ("Hello " ++ name)
[8 pts]
Distinguish the >> and >>= operators for monads in
Haskell.
[8 pts]
Write a function main with type IO () which reads two
lines from the user and displays them in sorted order. You should
not use any functions except for getLine, putStrLn,
string comparison operators, and the monad sequencing operators
(perhaps used implicitly through do notation).
[8 pts]
Based on the BNF grammar below, draw a syntax tree for the sentence
x x y x y x.
| S | → | T y T |
| T | → | x | x S |
[10 pts] Using BNF syntax, write a context-free grammar for the language of binary numbers: i.e., every sentence begins with a 1 followed by any sequence of 0's and 1's, except that 0 alone is also a sentence. Examples include 0, 1, 100, and 1111, but not 00 or 0101.
Test 2 Solutions: Solutions
Ord a => (b -> a) -> a -> b -> a
a. 9 then 7
b. Dynamic scoping easily leads to unexpected
program behavior. Taking the above program as an example, a
programmer writing a may well be unaware of which functions
use a, but still need to reference a variable in an outer scope.
And in writing b, a programmer could accidentally
define a variable with that same name.
While the variable arr is a variable local to the
sequenceComputer function, its value persists beyond
the end of the function call since the returned function
sequenceComp (later named to fib)
will need its value when it's called. Since its
value must be kept beyond the end of the function call where
it is created, space for the variable must be allocated on the heap.
In C++, a generic (“template”) is used to generate a new class definition for each usage of it with a different type, and each of these definitions is compiled separately. In Java, there is only one instance of the generic compiled, and it is compiled to deal with Object as the generic parameter. The type information with the generic is used only for type-checking by the compiler.
hailstone n = sub n 1
where sub n k | n == 1 = k
| odd n = sub (3 * n + 1) (k + 1)
| even n = sub (n `div` 2) (k + 1)
| 1. | x ≥ 1 ⇒ x ⋅ x ≥ 1 | Mathematical fact |
| 2. |
{ x ⋅ x ≥ 1 }y = x * x;{ y ≥ 1 } | Assignment |
| 3. |
{ x ≥ 1 }y = x * x;{ y ≥ 1 } | Preconditions: 1, 2 |
putStr "Name: " >> (getLine >>= (\name -> putStrLn ("Hello " ++ name)))
The >> operator expects a monad on both sides;
it sequences the first monad with the second, with the overall
result being the second monad's result (and the first
monad's result discarded). While >>= also expects a monad
on the left side, the right side should be a function that
takes the result from the left-side monad to produce a
second monad; the overall result is the second monad's result.
main =
do a <- getLine
b <- getLine
if a < b then
do putStrLn a
putStrLn b
else
do putStrLn b
putStrLn a
| S | → | 0 | 1 T |
| T | → | 0 T | 1 T |