6 Control🔗

6.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.

6.1.1 reverse🔗

(reverse : ((Listof Number) -> (Listof Number)))

(define (reverse l)

(type-case (Listof Number) l

[empty empty]

[(cons hd tl)

(append (reverse tl) (list hd))]))

6.1.2 sum-tree🔗

(sum-tree : (Tree -> Number))

(define (sum-tree t)

(type-case Tree t

[(leaf v) v]

[(node l r) (+ (sum-tree l) (sum-tree r))]))

6.2 Named Exceptions [40 Points]🔗

Many programming languages like Java have named exceptions that let you raise and handle specific exceptions. For example, the following Java program snippet shows how to catch an ArithmeticException when a division by zero occurrs:

Your task in this problem is to implement a definitional interpreter for a small language with named exceptions. Here is the abstract syntax of the language:

> (define-type Exn     (numE [n : Number])     (addE [e1 : Exn] [e2 : Exn])     (identE [id : Symbol])     (appE [e1 : Exn] [e2 : Exn])     (lamE [arg : Symbol] [body : Exn])     (tryE [body : Exn] [code : Symbol] [handler : Exn])     (raiseE [code : Symbol]))

The numE, addE, identE, appE, and lamE expressions behave as normal for the lambda calculus extended with numbers. For this problem evaluation order is critical: for (addE e1 e2), e1 is evaluated first and then e2; for appE e1 e2, e2 is evaluated first and then e1.

The (raiseE code) expression raises an exception with a particular code. If that code is not handled by any exception handler, then an ’unhandled-exception error should be raised.

The (tryE body code handler) runs body and jumps to the the inner-most handler expression if an exception with type code is raised.

Example:

> (interp-exn (tryE (raiseE 'catchme)

'catchme

(numE 10)))

(numV 10)

> (interp-exn

(tryE

(tryE (addE (raiseE 'catchme1) (raiseE 'catchme2))

'catchme2 (numE 10))

'catchme1 (numE 20)))

(numV 20)

6.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:

> (define-type Amb     (ifA [guard : Amb] [thn : Amb] [els : Amb])     (andA [e1 : Amb] [e2 : Amb])     (notA [e : Amb])     (boolA [b : Boolean])     (identA [id : Symbol])     (chooseA [id : Symbol] [body : Amb])     (failA))

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

• (failA) denotes failure: it means that this run of the program is invalid and should be rejected.

• (chooseA id body) tries to find a non-failing assignment to id. First, it runs body with id assigned to #t; if this fails, then it tries to run body with id assigned to #f; if this also fails, then the (chooseA id body) itself fails.

If all paths in an Amb program fails, then your interpreter should raise a 'no-valid-assignment error.

Your task is to implement a definitional interpreter for Amb programs called interp-amb. Here are some examples of running Amb programs:

> (interp-amb (chooseA 'x (ifA (identA 'x) (failA) (boolA #t))))

#t

> (interp-amb (chooseA 'x (ifA (identA 'x) (failA) (failA))))

no-valid-assignment: no assignment found

> (interp-amb (chooseA 'x

(chooseA 'y

(ifA (identA 'x) (failA) (identA 'x)))))

#f

Your solution should make use of continuations to implement backtracking. You will need to use a helper function for your implementation that keeps track of the necessary continuations.