8.3

Homework 8

home work!

Programming Language ISL+

Due Date Tuesday 11/2 at 9:00pm (Week 8)

Purpose To practice designing functions over trees, mutually recursive data, and two complex inputs.

Finger Exercises

Exercise 1 From HTDP, 311 312 313 318 319 323 324

Graded Exercises

Tree Maps

We could have named this [TreeMap X Y], analogous to how we write [List-of X], and it would mean exactly the same thing as [TreeMap K I]. But given that one type describes the key fields, and one type describes the info fields, it’s helpful to pick names that are slightly more mnemonic.

Exercise 2 Develop a data definition, including examples and a template, of a [TreeMap K I]. It should contain a [Comparison K] as well as a binary search tree that contains a K value and an I value (referred to as a key and an info, respectively) at each node.

For this assignment, a [Comparison X] is a [X X -> Real], where a negative output indicates the first parameter comes before the second, a positive output indicates the first parameter comes after the second, and 0 indicates they are the same. (Note: a particular Comparison might indicate two values are “the same”, even if they’re not “equal”. For instance, we might have a case-insensitive string comparison that ignores capitalization to check whether two strings are “the same”, even though they clearly are not string=?.)

Note than an empty TreeMap (i.e. containing no keys) is possible.

As you develop TreeMap examples for testing the functions below, be sure you consider all the ways TreeMaps can vary: you should have at least two examples that use different types of data, and you should have at least two trees which operate over the same types of keys but different comparisons, so that they demonstrate how binary search tree behaviors can differ when given different comparison functions. As a warning reminder, recall that you cannot check-expect functions themselves, which will make writing check-expects over TreeMaps impossible—so you’ll have to be slightly cleverer about how you write your test cases.

Exercise 3 Design a function insert, which given a key and an info (with types K and I, respectively) inserts the pair into a TreeMap. If the key is already present, the old value should be overwritten. Be sure to uphold the invariants of a binary search tree.

Exercise 4 Design a function find, which given a key finds the associated info in the tree. Don’t search any more of the tree than necessary, and error if no such key is found.

Exercise 5 Design a function submap, which given two keys, lo and hi, and a TreeMap, outputs a TreeMap where the binary search tree is a subtree of the original, containing no keys lower than lo or higher than hi (as indicated by the comparison function). Note: when lo or hi are not actually present in the TreeMap, your result may not precisely be a subtree of the original tree. Make sure you test examples of this scenario! Drawing sketches of the trees on paper will help.

S-Expressions

For this homework, we will consider simplified s-expressions containing only symbols:
; An SExpr is one of:
; - Symbol
; - [List-of SExpr]

While you do not have to provide examples or a template for s-expressions, you may find them helpful.

Exercise 6 Design the function topsy-turvy, which inverts the order of an s-expression. An inverted s-expression should not only have the orders of its list reversed, but each individual element of the list should also be inverted. Note the symbols themselves should be left as-is.

Exercise 7 Design the function find-path, which given an s-expression and a symbol outputs the path to the leftmost occurence of that symbol in the s-expression. If that symbol is not present, the function should output #false. As an example, the path to 'wish in 'wish would be '(), and in '(though (i might (wish))) would be '(1 2 0).

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.

; A Bool is a [X X -> X]

Exercise 8 Define the two shortest functions that have this signature. The functions are restricted to only use λ expressions and variables. These will be our Bools.

Exercise 9 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).

As a technical side-note: your design for these functions do not need to match the short-circuiting behavior of and and or.

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

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

Exercise 12 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 7 Lambda, check it out!

Algebraic Simplification

We can define algebraic expressions like 1 + (2 * x) + 3 with the following data definition (we could also include division and subtraction, but we don’t need them 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 3 (make-add 1 0)) ; same as just 3

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

Exercise 13 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 14 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).

Note: this could easily get tricky, where simplifying expressions might lead to expressions that you can compact, but compacting them leads to more expressions you can simplify, which leads to more expressions that you could compact... For example, (make-add 42 (make-mul (make-add -2 2) 'x)) could simplify the inner addtion to 0, which could simplify the multiplcation to 0, which could simplify the outer addition to 42. You do not have to handle situations like these; simplify and compact are separate functions.