Using the Church numerals, we can define the succ function in the lambda calculus to take a Church numeral representing some number n and return the Church numeral representing n + 1.

succ = λa.λs.λz.a s (s z)

Give a lambda calculus definition of the addition function +, which takes two Church numerals representing two numbers m and n and returns a Church numeral representing their sum, m + n.

Suppose we want to define a way to represent pairs (or 2-tuples) in the lambda calculus. We can do this by defining the following function pair, which takes two arguments and generates a representation of a pair of those two values.

pair = λx.λy.λf.f x y For example, to represent the value (2,3), we would call pair  2 3, which would give us λf.f 2 3.

Give a lambda expression for the function first that takes a pair represented as above and extracts the first item of the pair. Using your definition, I should be able to write first (pair 2 3) and get 2.

Consider the following Java program.

class Test {
    static int a = 1;

    static int f() { return a; }

    public static void main(String[] args) {
        int a = 2;
        System.out.println(f());
    }
}

a. If Java used dynamic variable scoping, what would it output?

b. If Java used static variable scoping, what would it output?

c. Does Java use static or dynamic scoping?

Consider the Python program below.

def a():
    nonlocal x
    x = 3

def b():
    x = 4      # defines a new 'x' variable hiding the global 'x'
    a()
    print(x)

x = 2          # creates a global 'x' variable
b()
print(x)

a. If Python used statically scoped variables, what would this program print?

b. If it used dynamically scoped variables, what would it print?

c. Which does Python use?

Why would a language opt to use dynamic scoping (as Postscript and some old versions of Lisp do) rather than static scoping (as with nearly all other languages)?

Recall from class that FORTRAN uses static variable allocation, while most other languages (including Java and Python) use stack-dynamic variable allocation.

a. Name and explain an advantage of static variable allocation over stack-dynamic variable allocation.

b. Name and explain an advantage of stack-dynamic variable allocation over static allocation.

Give an example of a Python program where a local variable could not be allocated on the stack and so would need to be on the heap.

Name and explain a reason why generics (such as generics in Java and templates in C++) are a useful feature for a programming language to include.

Explain why generics make more sense as a feature in statically typed languages than in dynamically typed languages.

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.

What is the advantage of a tail-recursive function over other recursive functions?

Convert the following Haskell function into an equivalent tail-recursive Haskell function.

pow2 0 = 1
pow2 n = 2 * pow2 (n - 1)

Describe the translation process that a compiler can use to eliminate recursive calls from a tail-recursive function.

Prove the following using our axiomatic scheme. Give a written justification of each mathematical fact.

Prove the following using our axiomatic scheme. The notation fib_i is used to represent the ith Fibonacci number.

Provide a step-by-step partial correctness proof for the following. Justify each step with one of the three rules below, or “mathematical fact” if the conclusion is algebraically true and involves no assertions.

Prove the following using our axiomatic scheme.

Prove the following using our axiomatic scheme

Distinguish proofs of total correctness against proofs of partial correctness.

What loop invariant allows you to prove the postcondition for the following?

{ n = 2^k ∧ k ≥ 0 }
i = 0;
j = 1;
while (j != n) {
    j = j * 2;
    i = i + 1;
}
{ n = 2ⁱ }

What loop invariant allows you to prove the postcondition for the following?

{ n ≥ 0  }
a = 0;
c = n;
while (c > a + 1) {
    b = (a + c) / 2;
    if (b * b <= n) {
        a = b;
    } else {
        c = b;
    }
}
{ a ≤ √n < a + 1 }