Homework 9a
MUST BE DONE WITH YOUR PARTNER
Due Date Wed at 9:00pm (Week 9)
Exercises
In this assignment, you will continue with the in-class exercise to create a small “calculator”. In class, we worked directly with s-expressions; in this assignment, you will take the other approach, and convert s-expressions to structs first, before manipulating them further.
We’re also going to simulate user-input in a calculator: if part of the s-expression is '(input), we will want to treat that as if a user were typing in a numeric value. In this assignment, we won’t fully implement that ability, just prepare for it to work at some future point.
Parsing Arithmetic Expressions
Consider the following definition of an arithmetic expression:
; An Op is a symbol of an arithmetic operator ; op? : Any -> Boolean ; determines whether argument is in fact an Op (define (op? s) (member s '(+ - * /))) (define-struct e-op [op left right]) (define-struct e-in []) ; An Exp is one of ; - Number ; - (make-e-op Op Exp Exp) ; - (make-e-in) ; and represents an expression that a calculator might process: either a ; single number, an operator applied to subexpressions, or user input. (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 of signature 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 full definition of S-Exp from class:
; An S-Exp is one of ; - Atom ; - LoSExp ; An Atom is one of ; - Number ; - String ; - Boolean ; - Symbol ; An LoSExp is a [List-of 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 In class we developed a function evaluate that worked directly with s-expression based arithmetic expressions. Do the same here for Exps, but with the beginning of support for user input. Specifically, design a function eval with signature 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 evaluate to the first argument given to eval (this is not true input, obviously, but it will suffice for now)
Algebraic Simplification
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.
Exercise 3 In this exercise, you will perform a few simple algebraic simplifications.
It’s tempting to try to perform more algebraic manipulations all at once in a single function. Don’t be tempted – it’s more useful to have lots of small optimizations that each do one simplification and are obviously correct, and compose them together, than it is to have one fancy but complicated optimization function. This is just our standard design recipe for functions: each function should just do one thing at a time.
Design a function simplify, with signature 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 these six rules described (but do not do any other arithmetic or try to 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 that, given a Exp, produces a new Exp that 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) (make-e-in)) should be).
Exercise 5 Compose your four functions together into a function run with signature Number S-Exp -> Number that parses, compacts, simplifies, and then evaluates.