Assignment 3: Calc and cond

Objectives:

  • Become comfortable with the basic calc, ite interpreters and be able to extend them.

Resources:

  • The Plait tutorial and documentation page: https://docs.racket-lang.org/plait/
  • PLAI pages 17 – 47

Parameters:

  • Due date: Friday Feb. 2 at 11:59PM
  • Upload your solution on Gradescope.
  • 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.
  • Note: this assignment is slightly longer and more difficult than the others. Start early!
  • Grading: each problem is worth a certain number of points. The points given for each problem is the fraction of tests passed for that problem (i.e., if 50% of the tests are passed for a 20 point problem, 10 points are given).

Exercise 1: To infinity and beyond [45 Points]

Recall the tiny calculator from class:

(define-type Exp
    [num (n : Number)]
    [plus (left : Exp) (right : Exp)])

(define (parse s)
  (cond
    [(s-exp-number? s)
     (num (s-exp->number s))]
    [(s-exp-list? s)
     (let ([l (s-exp->list s)])
       (cond
         [(empty? l) (error 'parse "empty list")]
         [(symbol=? '+
                     (s-exp->symbol (first l)))
           (plus (parse (second l))
                 (parse (third l)))]
         [else (error 'parse "unrecognized symbol")]))]))

(define (calc e)
  (type-case Exp e
    [(num n) n]
    [(plus l r) (+ (calc l) (calc r))]))

In this exercise you will extend this calculator to handle infinite values. Infinity is used in real programming languages such as JavaScript and Elm to allow programmers to not run into divide-by-zero errors. In fact, infinity is represented in the IEEE Floating Point standard used in almost all programming languages!

Use the symbol 'infty to denote positive infinity. For instance, the following s-expression denotes an addition that involves infinity:

> `(+ infty 1)
- S-Exp
`(+ infty 1)

The desired semantics of an infinite value is that anything added with infinite is infinite, including itself. To capture this, use the following new value type that is either infinity or a number:

(define-type ExtendedNumValue
  [v-num (n : Number)]
  [v-infty]
  )

Your task: Extend Exp, parse, and calc to parse and evaluate expressions that involve infinity. Your function calc should have type (Exp -> ExtendedNumValue). We will not test for parse errors.

Example behavior:

(calc (parse `(+ infty 1)))
- ExtendedNumValue
(v-infty)

Exercise 2: cond [55 Points]

Recall the ite language from class (where here we have provided you with a parser):

(define-type Value
  [numV (n : Number)]
  [boolV (b : Boolean)])

(define-type IteExp
  [numE (n : Number)]
  [boolE (b : Boolean)]
  [plusE (left : IteExp) (right : IteExp)]
  [cndE (test : IteExp) (then : IteExp) (else : IteExp)])

(define (boolean-decision v)
  (type-case Value v
             [(boolV b) b]
             [else (error 'if "expects conditional to evaluate to a boolean")]))

(define (add v1 v2)
  (type-case Value v1
             [(numV n1)
              (type-case Value v2
                         [(numV n2) (numV (+ n1 n2))]
                         [else (error '+ "expects RHS to be a number")])]
             [else (error '+ "expects LHS to be a number")]))

(define (ite-parse s)
  (cond
    [(s-exp-number? s)
     (numE (s-exp->number s))]
    [(s-exp-boolean? s)
     (boolE (s-exp->boolean s))]
    [(s-exp-list? s)
     (let ([l (s-exp->list s)])
       (cond
         [(empty? l) (error 'parse "empty list")]
         [(symbol=? '+ (s-exp->symbol (first l)))
          (plusE (ite-parse (second l)) (ite-parse (third l)))]
         [(symbol=? 'if (s-exp->symbol (first l)))
          (cndE (ite-parse (second l)) (ite-parse (third l)) (ite-parse (fourth l)))]
         [else (error 'parse "urecognized symbol")]
         ))]
    [else (error 'parse "unrecognized symbol")]))


(define (ite-calc e)
  (type-case IteExp e
             [(numE n) (numV n)]
             [(boolE b) (boolV b)]
             [(plusE l r) (add (ite-calc l) (ite-calc r))]
             [(cndE c t e) (if (boolean-decision (ite-calc c))
                               (ite-calc t)
                               (ite-calc e))]))

In this exercise you will develop a new language that replaces if with cond. You will use the following abstract syntax:

(define-type IteExp
  [numE (n : Number)]
  [boolE (b : Boolean)]
  [plusE (left : IteExp) (right : IteExp)]
  [condE (arms : (Listof (IteExp * IteExp)))])

The syntax of our language is given by the following grammar:

<e> ::= #t | #f | num | (cond ((<e> <e>)+)) | (+ <e> <e>)

The notation ((<e> <e>)+) means “a non-empty list of pairs of expressions”; this syntax is the familiar syntax for cond in Plait. The condE form takes a list of pairs of expressions as its argument; each pair of expressions is called an arm. Pairs are constructed and deconstructed in Plait as follows:

> (pair 20 10)
- (Number * Number)
(values 20 10)

> (fst (pair 20 10))
- Number
20

> (snd (pair 20 10))
- Number
10

The semantics of condE is given as follows:

  • Each arm should be evaluated in the order it appears in the list.
  • An arm is a pair (guard, body):
    • If guard evaluates to #t then body should be evaluated and returned. The remaining arms need not be evaluated–this is what is called a short-circuiting operation.
    • If guard evaluates to #f, then the next arm should be evaluated. If there is no next arm, a 'cond error should be raised.
  • If guard evaluates to something that is not a Boolean, then a 'cond error should be raised.
  • If the list of arms is empty, then a 'cond error should be raised.

Your task: Extend ite-parse and ite-calc to handle this new cond form. We will not test for parse errors; we will only test your program on syntactically valid inputs (so, you can ignore the case when cond is given an empty list as an argument for example).

Example usage and demonstration of syntax:

> (calc (parse `(cond (#t 10) (#f 20))))
- Value
(numV 10)

> (calc (parse `(cond (10 10) (#f 20))))
- Value
cond: expects conditional to evaluate to a boolean

> (calc (parse `(cond (#t (cond (#f 0) (#t 25))) (#f 20) (#t 0))))
- Value
(numV 25)