Week 9 Set a

Due Date Monday 10/28 at 9:00pm (Week 9)

Purpose To get

Finger Exercises

Exercise 1 From HTDP, 311 312 313 318

Graded Exercises

Take Me To Church

Alonzo Church is one of the founders of computer science: he came up with the λ calculus, which we know and love so dearly. In fact, he famously argued that λ, much like love, is all you need! Let’s see whether or not he was right by investigating one of our favorite atomic data types, booleans.

Exercise 3 Design a bool->boolean function, which will allow us to test the functions we define below by converting to normal ISL #true / #false.

For the following three functions, besides define and λ, your function definitions should not use any ISL-provided functions or keywords (and certainly not bool->boolean, #true or #false).

Exercise 4 Design and/bool, which functions analogusly to and, but takes in two Bools and outputs a Bool.

Exercise 5 Design or/bool, which functions analogusly to or, but takes in two Bools and outputs a Bool.

Exercise 6 Design not/bool, which functions analogusly to not, but takes in one Bool and outputs a Bool.

For those of you who enjoyed this brain teaser but didn’t yet get the chance to finish the second half of lab 7, check it out!

Algebraic Simplification

We can define algebraic expressions like 1 + (2 * x) + 3 with the following data definition (we could add division and subtraction, but aren’t for these exercises):

; An Expression is one of:

; - Number

; - Symbol

(define-struct add [left right])

; - (make-add Expression Expression)

(define-struct mul [left right])

; - (make-mul Expression Expression

We can translate expressions in the form you are used to from math class into ISL+ as follows:

; x

'x

; 1 + 2

(make-add 1 2)

; x * (x + 2) * z

(make-mul 'x (make-mul (make-add 'x 2) 'z))

; x + 2 * 3

(make-add 'x (make-mul 2 3))

Now that we have these expressions, we notice that it’s easy to write silly expressions:

(make-add 0 'x) ; same as just 'x

(make-add (make-add 1 2) 0) ; same as just (make-add 1 2)

(make-mul 1 'y) ; same as just 'y

(make-mul (make-add 1 0) 3) ; same as just 3

In particular, we notice that adding 0 to anything and multiplying 1 to anything results in the same as the input.

Exercise 7 Design a function simplify that, given an Expression, returns an expression that has been simplified according to the strategy described above. Note that you should simplify as much as you can, according to the rules described (without doing arithmetic or reordering expressions).

In addition to adding 0 and multiplying by 1, it’s also not necessary to have add and mul when both operands are constants, as we can make equivalent expressions where the expression has been replaced with the result. e.g.,

(make-mul 2 3) ; same as 6

(make-add (make-add 1 2) 0) ; same 3

Exercise 8 Design a function compact that, given a Expression, replaces all constant add and mul 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-add 2 (make-add 3 'x)) need not be compacted, even thought the equivalent (make-add (make-add 2 3) 'x) would be).