Homework 8a

home work!

Programming Language #lang htdp/isl+



Due Date Tues at 9:00pm (Week 8)

Purpose Start on calculator project


In this assignment, you will start working on a project to create a small "calculator". Eventually, this will support not only arithmetic expressions, but input and "memory" operations (storing and recalling). In this assignment, you will build the first version, which is an evaluator for an arithmetic expression language. It will have placeholders for accepting input, but in this version, the expressions will not really accept input: we will just provide a single fixed "input" value.

Parsing Arithmetic Expressions

Consider the following definition of an arithmetic expression:

(: op? (Any -> Boolean))
; determines whether argument is the symbol of an arithmetic operator
(define (op? s)
  (member s '(+ - * /)))
(define Op (signature (predicate op?)))
(define-struct e-op [op left right])
(define-struct e-in [])
(define Exp (signature (mixed Number
                              (EOpOf Op Exp Exp)
(define E0 3)
(define E1 (make-e-op '+ (make-e-op '- 1 (make-e-op '+ 2 2))
                         (make-e-op '* 3 (make-e-op '/ 3 4))))
(define E2 (make-e-op '+ 1 (make-e-op '- 2 3)))
(define E3 (make-e-op '+ (make-e-in) 2))

Exercise 1 Your first task is to design (: parse (S-Exp -> Exp)) that takes an S-Expression and produces an Expression. This should allow you, using quote, to write (binary) arithmetic expressions just as you do in ISL+. You should have the S-Expression (list 'input) be how you represent input.

Recall the definition of S-Exp:

(define S-Exp (signature (mixed Number String Boolean Symbol (ListOf S-Exp))))

For example, the following three examples should parse to the examples given above:

(define S0 3)
(define S1 '(+ (- 1 (+ 2 2)) (* 3 (/ 3 4))))
(define S2 '(+ 1 (- 2 3)))
(define S3 '(+ (input) 2))

In case of an invalid S-Exp, you should raise an error. For example, the following (among others) tests should pass:

(check-error (parse #t))
(check-error (parse '(+ 1 hello)))

Evaluating Expressions

Exercise 2 Your next task is to evaluate expressions. Design (: eval (Number Exp -> Number)) that takes a fixed number for all input, an Exp and returns the number that it evaluates to. If you encounter a (make-e-in), it should be treated as the first argument to eval (this is not true input, but we’ll add support in a future assignment)


Algebraic Simplification

Even in arithmetic expressions that depend on input, certain expressions can be simplified before being run: e.g., (+ e 0) will always be the same as e, regardless of what e is.

Compiler optimizations are a fascinating and old topic. One of the most important people the field is Fran Allen (who won a Turing Award for the work), whose 1971 paper A Catalogue of Optimizing Transformations is still a great description of many transformations. This assignment is doing a version of "Constant Folding", p18 in that paper.

Such optimizations are very common, and are often done on programs through some form of compilation, as they can be done ahead of time, so that when the program is actually running, fewer operations need to be done. This is particularly useful if the computation in question would need to happen many times, or if it happens on a different, more hardware constrained platform than the program is built on.

Exercise 3 In this exercise, you will perform a few simple algebraic simplifications.

Design a function (: simplify (Exp -> Exp)) that returns an expression that has been simplified be replacing any occurrences of (+ e 0), (+ 0 e) or (- e 0) with e and (* e 1) or (* 1 e) or (/ e 1) with e. Note that you should simplify as much as you can, according to the rules described (but do not do arithmetic or reorder expressions).

In addition to simplifying trivial operations as you did in the previous exercise, it’s also not necessary to keep expressions when both operands are constants, as we can make equivalent expressions where the expression has been replaced with the result. e.g.,

(make-e-op '* 2 3) ; same as 6
(make-e-op '+ (make-e-op '+ 1 2) 0) ; same as 3

Exercise 4 Design a function (: compact (Exp -> Exp)) that, given a Exp, replaces all constant expressions with the number that they evaluate to. Note that you should do this as much as possible, but don’t need to re-order expressions in order to do this (i.e., (make-e-op '+ 2 (make-e-op '+ 3 (make-e-in))) need not be compacted, even thought the equivalent (make-e-op '+ (make-e-op '+ 2 3) (input)) would be).

Exercise 5 Compose your four functions together into a function (: run (Number S-Exp -> Number)) that parses, compacts, simplifies, and then evaluates.