UNB/ CS/ David Bremner/ teaching/ cs4613/ tutorials/ CS4613 Tutorial 08: More practice for midterm


This tutorial consists of a simulated test, with two questions based on lecture and previous tutorial material. You are given a single skeleton file for both questions, and you should hand the single modified file to the handin server before 11:30 on 2024-03-20. Unlike assignments, there is no requirement for test coverage, but the handin server will still limit you to 120 characters on a line.

Simulating Union Types

In Tutorial 6, you used union types to build an object-oriented binary tree structure. In order to satisfy the typing rules for plait, we can replace the use of union types with a new algebraic data type NodeOrNum. Node is then defined in terms of NodeOrNum. The provided skeleton contains the following code:

(define-type NodeOrNum
  [aNode .... ]
  [aNum (num : Number)])

(define-type-alias Node ....)

(define (msg-num [obj : Node] [selector : Symbol])

(define (node [v : Number] [l : Node] [r : Node]) : Node
  (lambda (m)
    (case m
      [(value) (aNum v)]
      [(left)  (aNode l)]
      [(right) (aNode r)]
      [(sum) (aNum (+ v (+ (msg-num l 'sum) (msg-num r 'sum))))]
      [else (error 'node (symbol->string m))])))

(define (mt)
  (lambda ([m : Symbol])
    (case m
      [(sum) (aNum 0)]
      [else (error 'mt (symbol->string m))])))

Complete the type definitions

Complete the given type definitions so that the modified versions of node and mt typecheck. If you choose to work on the other question first, you will need to comment out or remove the part of the skeleton for this question.

Update msg-num

In Tutorial 6 we wrote a function msg-num that helped make our dynamically dispatched code statically typecheck. Update msg-num for the new type definitions, so that the following tests pass

(module+ test
  (test (msg-num (mt) 'sum) 0)
  (test/exn (msg-num (node 3 (mt) (mt)) 'left)) "cannot convert"))

Update msg-node

Update the function msg-node (the idea is very similar msg-num) so that the following tests pass.

(module+ test
  (define tree1 (node 1 (mt) (mt)))
  (test (msg-num tree1 'sum) 1)
  (test (msg-num tree1 'value) 1)
  (define tree2 (node 1 (node 2 (mt) (mt)) (mt)))
  (test (msg-num tree2 'value) 1)
  (test (msg-num (msg-node tree2 'left) 'value) 2)
  (test (msg-num (msg-node tree2 'right) 'sum) 0)
  (test/exn (msg-node tree2 'value) "cannot convert"))

Tagged references

The provided skeleton contains a skeleton of a simple tagged reference language with plus and if expressions. Compared to the example from the Lecture 11 , there are boolean expressions instead of strings.

Complete the functions read-bool, store-bool and calc so that the following tests pass.

(module+ test
  (test (read-num (calc (plusE (numE 1) (numE 2)))) 3)
  (test (read-num
         (calc (plusE (numE 1) (plusE (numE 2) (numE 3))))) 6)
  (test (read-bool (calc (boolE #t))) #t)
  (test (read-bool (calc (boolE #f))) #f)
  (test (read-num (calc (ifE (boolE #t) (numE 3) (plusE (numE 42) (boolE #f))))) 3)
  (test/exn (calc (ifE (boolE #f) (numE 3) (plusE (numE 42) (boolE #f)))) "number"))

For reference, here are the parts of the skeleton to update

(define (store-bool b) ....)

(define (read-bool a) ....)
(calc : (Exp -> Value))
(define (calc e)
  (type-case Exp e
    [(numE n) (numV n)]
    [(boolE b) (boolV b)]
    [(plusE l r) (num+ (calc l) (calc r))]
    [(ifE c t e) ....]))