On this page:
6.1 Tail Form [20 Points]
6.1.1 reverse
6.1.2 sum-tree
6.2 Named Exceptions [40 Points]
6.3 Non-determinism [40 Points]
8.15

6 Control🔗

Instructions:
  • Due date: Wednesday, March 19 at 11:59PM

  • Upload your solutions to GradeScope here. You should upload a single file called code.rkt. Be sure to check that your uploaded solution is valid; you will receive 0 points if your solution does not run.

  • Your programs will be evaluated on the fraction of tests that they pass. We will show you some tests, but not all tests. You should test your code thoroughly. After the submission deadline, we will reveal the hidden tests.

  • Starter code: here.

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:

public static void main(String[] args) {

    int n = 10;

    int m = 0;

    try {

       // Code that may throw an exception

       int ans = n / m;

       System.out.println("Answer: " + ans);

    }

    catch (ArithmeticException e) {

       // Handling the exception

       System.out.println("Error: Division by zero is not allowed!");

    } finally {

       System.out.println( "Program continues after handling the exception.");

    }

}

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:

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.