Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 4301/6371 Advanced Programming Languages
Sample
Spring 2024 Midterm Exam
Sample Spring 2024 Midterm Exam
Write your name at the top of this exam paper and turn it in as the front page of your submission. You may take a single, two-sided sheet of notes with you into the exam. All other books or notes must remain closed throughout the exam. You will have the duration of the class period to complete the exam; all papers must be turned in by 2:15pm. Good luck!
(1) A number can be encoded as a list of digits. For example, the list [1;0;2;4] encodes the number 1024 in base-10, and the list [15;15] encodes 0xFF=255 in base-16. In this problem you will implement OCaml functions that convert between integers and digit lists. Do not use any List library functions in your solutions except that you may use List.fold left if you wish. In case you need them, the OCaml integer-division and integer-modulo operators are (x/y) and (x mod y), respectively.
(a) (7 pts) Implement a tail-recursive OCaml function (digitize b n) that converts an integer n into a base-b digit list. You may assume that b ≥ 2 and n ≥ 0.
(b) (6 pts) Implement a tail-recursive OCaml function (undigitize b dl) that converts a base-b digit list dl to an integer. You may assume that b ≥ 2 and that no elements of dl are less than 0 or greater than b − 1.
(2) (14 pts) Recall following definition of map from class: let rec map f = function [] -> [] | h::t -> (f h)::(map f t);;
Unfortunately this definition is not tail-recursive. Explain why. What is the impact in terms of time and space? Fix this problem by finding a new implementation of map that uses only fold left for recursion.
(3) Consider the following extension to SIMPL, which defines the syntax and large-step semantics of a new arithmetic expression called calc:
a ::= · · · | calc(v, a1, a2) ha1, σi ⇓ n1 ha2, σi ⇓ n2 n1 ≤ n2 hcalc(v, a1, a2), σi ⇓ σ(v) (C1) ha1, σi ⇓ n1 ha2, σi ⇓ n2 n1 > n2 hcalc(v, a1, a2), σ[v 7→ σ(v) + 1]i ⇓ n hcalc(v, a1, a2), σi ⇓ n (C2)
(a) (8 pts) Define σ = {(x, 1)}. Derive hcalc(x, x + 1, x * x), σi ⇓ n for any integer n.
(b) (5 pts) Write a “plain English” description of calc(v, a1, a2) for a programmer’s reference manual. Your description should not refer to inference rules, stores, or derivations since most programmers aren’t familiar with such concepts. Is it possible for calc to ever loop infinitely? Your description should either explain under what conditions it can, or why it cannot. What is the final value of v after the expression finishes evaluating?
(c) (10 pts) Write small-step operational semantic rules for calc that are equivalent to the large-step rules given above. (You need not prove semantic equivalence.)
(4) Consider the following recursive definition of function f:
f(x) = x= 100 → 0 | x>100 → f(x − 1) + 1 | x<100 → f(x + 1) + 1)
(a) (1 pt) Define a non-recursive functional F whose least fixed point is f.
(b) (4 pts) Give a closed-form function definition h such that h = f.
(c) (15 pts) Prove by fixed point induction that h = fix (F)