Assignment 6: Programming with Continuations

Instructions:

  • Due date: Fri. Nov 15, 11:59PM EST
  • Upload your solutions to gradescope as problem-1.rkt, problem-2.rkt, and problem-3.rkt.
  • Ask questions on Piazza or during office hours.
  • Perform all the work for this project by yourself. You may discuss with your classmates, but you must write your own code and solve your own exercises.
  • Starter code:

Problem 1: Tail Form [20 Points]

In class, you saw how you can convert a recursive function into a tail-recursive one. Convert the following Racket functions into their tail-recursive form. You can do either the continuation approach or the custom accumulator one. Do not change the signature of the function (you can write helper functions). Don’t forget that only recursive functions needs to be converted into tail form.

  1. ;;; reverse-list : List A -> List A
;;; Returns a new list of the same length with the order of elements reversed.
(define/contract (reverse-list xs)
  (parametric->/c [A] (-> (listof A) (listof A)))
  (match xs
['() '()]
[(cons x rest) (append (reverse-list rest) (list x))]))

  2. ;;; fold-right : (A -> B -> B) -> B -> List A -> B
;;; Combines the elements of the list into a single result of type B.
;;; Evaluated right to left (f x[0] (f x[1] ... (f x[n] init)))
(define/contract (fold-right f init xs)
  (parametric->/c [A B] (-> (-> A B B) B (listof A) B))
  (match xs
['() init]
[(cons x rest) (f x (fold-right f init rest))]))

3.

;;; type tree =
;;;   | Leaf
;;;   | Node of tree * Int * tree
(define-struct leaf ()
  #:transparent)
(define-struct node (left val right)
  #:transparent)

;;; tree-sum : tree -> Int
;;; Sums up all the values in the tree
(define/contract (tree-sum tree)
  (-> (or/c leaf? node?) integer?)
  (match tree
    [(leaf) 0]
    [(node left val right) (+ (tree-sum left) val (tree-sum right))]))

Problem 2: Named Exceptions [40 Points]

Many programming languages, like Racket, allow programmers to catch and handle different variants of exceptions separately:

(struct exn:fail:odd-number exn:fail ())

(define (raise-odd-number-error)
  (raise (exn:fail:odd-number "odd number" (current-continuation-marks))))

(define (raise-divide-by-zero-error)
  (raise (exn:fail:contract:divide-by-zero "divide by zero" (current-continuation-marks))))

(define (is-even n)
  (with-handlers ([exn:fail:user? (λ _ #t)])
    (with-handlers ([exn:fail:odd-number? (λ _ #f)])
      (with-handlers ([exn:fail:contract:divide-by-zero? (λ _ #t)])
        (cond
          [(= n 0) (raise (raise-user-error "zero is even!"))]
          [(= (modulo n 2) 0) (raise-divide-by-zero-error)]
          [else (raise-odd-number-error)])))))

Notice, because exn:fail:odd-number is not handled by the third (inner-most) with-handlers block, it bubbles up and is caught by the second with-handlers block. Likewise, any raised exn:fail:user exxception bubbles up past the second and third with-handlers blocks before being caught by the first (outer-most) with-handlers block. Hence, this function works as intended:

> (is-even 2)
#t
> (is-even 7)
#f

In this problem, we will extend the try-catch language from lecture to include an arbitrary number of exception handlers, following the semantics of the Racket code presented above.

Consider the following $\lambda$ calculus with try-catch:

(struct enum (n)
  #:guard (struct-guard/c integer?))
(struct eadd (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c)))
(struct eident (id)
  #:guard (struct-guard/c string?))
(struct elam (param body)
  #:guard (struct-guard/c string? (recursive-contract expr/c)))
(struct eapp (e1 e2)
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c)))
(struct etry (body code handler)
  #:guard (struct-guard/c (recursive-contract expr/c) integer? (recursive-contract expr/c)))
(struct eraise (code)
  #:guard (struct-guard/c integer?))

(define expr/c (or/c enum? eadd? eident? elam? eapp? etry? eraise?))
(define value/c (or/c enum? elam?))

Your primary task is to implement the interpreter interp, a continuation-passing style interpreter that interprets expressions from the exception language, using interp/helper and subst as helper functions. The interpreter should satisfy the following criteria:

  1. enum, eadd, eident, elam, and eapp correspond to numbers, addition, variables, $\lambda$ terms, and function application in the $\lambda$-calculus, respectively.
  2. eraise follows the syntax (eraise exception-code), where exception-code is an integer representing the variant of exception that is raised.
  3. etry follows the syntax (etry try-expr exception-code catch-expr). etry will attempt to interpret try-expr and catch any raised exceptions with code exception-code by interpreting catch-expr. If an exception with a different code than exception-code is raised, then it “bubbles up” (as illustrated in the example above).
  4. If the interpreter encounters an uncaught exception, it raises an “uncaught exception” exception by using (raise-uncaught-exn-error).
  5. If the interpreter encounters an unbound identifier, it raises a runtime exception by using (raise-runtime-error).

Note: In order to receive full credit for your solution, your interpreter must utilize continuations and be in tail form.

Problem 3: Non-determinism [40 Points]

Many problems in computer science involve backtracking searching through a space of possible solutions. In this problem, we will make a small programming language for solving problems that involve backtracking search by introducing non-determinism and failure.

Here is the abstract syntax of the Amb language, introduced by John McCarthy in 1963:

(struct eif (guard thn els)
  #:transparent
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c) (recursive-contract expr/c)))
(struct eand (e1 e2)
  #:transparent
  #:guard (struct-guard/c (recursive-contract expr/c) (recursive-contract expr/c)))
(struct enot (e1) #:transparent
  #:guard (struct-guard/c (recursive-contract expr/c)))
(struct ebool (v) #:transparent
  #:guard (struct-guard/c boolean?))
(struct eident (id)
  #:transparent
  #:guard (struct-guard/c string?))
(struct echoose (id body)
  #:transparent
  #:guard (struct-guard/c string? (recursive-contract expr/c)))
(struct efail () #:transparent)
(define expr/c (or/c eif? echoose? eand? enot? efail? ebool? eident?))

The language has some familiar constructs (conditionals, and, not, Booleans, and identifiers), and two new constructs: echoose and efail. Their semantics are:

  1. (echoose id body) is similar to let: it non-deterministically picks a Boolean value and assigns it to id. Then, it runs body.
  2. (efail) denotes failure: it means that this run of the program is invalid and should be rejected, and another assignment to the non-deterministic choices should be tried instead.

An Amb program is valid if there is an assignment to non-deterministic choices that does not evaluate (efail), and invalid if all assignments to non-deterministic choices evaluate (efail). For example, the following Amb programs are valid:

(ebool #t)
(echoose "x" (eident "x"))                          ; valid assignments: x = t or x = f
(echoose "x" (eif (eident "x") (efail) (ebool #t))) ; valid assignment: x = f

The following Amb programs are invalid:

(efail)
(echoose "x" (eif (eident "x") (efail) (efail)))

Your task is to implement the interp function that returns #t if an Amb program is valid and #f if it is invalid. Your solution must involve continuations to receive full credit.