2 Homework 2
Released: Wednesday, January 18, 2023 at 6:00pm
Due: Wednesday, January 25, 2023 at 6:00pm
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW2 assignment on Gradescope. This page has additional information, and allows us to format things nicely.
2.1 Problem 1
Consider a binary tree, defined as follows:
(define-struct leaf [value])
(define-struct node [left right])
; A [Tree-of X] is one of:
; - (make-leaf X)
; - (make-node [Tree-of X] [Tree-of X])
Trees are often used for fast lookup of sorted data, as if it is sorted, at each node we can continue searching down only one half of the tree. But in order to be fast, they have to be balanced; a degenerate tree that only ever branches down one side will perform the same as a list.
A (height) balanced binary tree has a difference in height of the left and right subtrees of at most 1, where height is the longest path to a leaf. Importantly, this property (or invariant) must be mantained when inserting and removing elements from the tree. This may not be easy: if you have a tree:
(define T1 (make-node (make-node (make-leaf 2)
(make-leaf 3))
(make-leaf 4)))
And you want to add 1, while mantaining the fact that the tree is sorted (or else, you won’t be able to use it to quickly look up data), you would want to insert it before 2 in the tree. The easiest thing would be to replace the leaf 2 with a node with 1 and 2:
(define T2 (make-node (make-node (make-node (make-leaf 1)
(make-leaf 2))
(make-leaf 3))
(make-leaf 4)))
This is still sorted, but it is no longer balanced, as now the left side of the top-level node has height 3, but the right side has height 1, which is a difference of 2. Instead, you might have to "rotate" the 3 to the other side to rebalance and get the following tree:
(define T3 (make-node (make-node (make-leaf 1)
(make-leaf 2))
(make-node (make-leaf 3)
(make-leaf 4))))
There are many different ways of doing this, with different names (AVL trees, Red Black trees, etc), and our goal is not to implement insertion, rebalancing, deletion, etc. What we do want to do is capture the invariant of being balanced.
Your task: define balanced-prop as a predicate. You should test your property on several example trees using check-property.
2.2 Problem 2
A compiler is a program that translates expressions or programs written in one language into those written in another. We’ll come back to this idea later in the semester, but for this exercise, we are going to just consider simple arithmetic expressions (so simple, in fact, they only have addition!).
First, consider the following data definition:
(define-struct addexpr [left right])
; An AddExpression is one of:
; - Number
; - (make-addexpr Expression Expression)
(define A0 10)
(define A1 (make-addexpr 10 5))
(define A2 (make-addexpr (make-addexpr 3 4) 1))
This definition allows us to define arithmetic expressions with numbers and just + (so "Add Expressions"). We don’t have a direct way of writing "1 + 2 + 3", but we can write the two equivalent expressions "(1 + 2) + 3" and "1 + (2 + 3)":
(define A3 (make-addexpr (make-addexpr 1 2) 3))
(define A4 (make-addexpr 1 (make-addexpr 2 3)))
Now, consider this second data definition:
(define-struct push [num])
; An Instr is one of:
; - 'add
; - (make-push Number)
(define I0 (list (make-push 1)))
(define I1 (list (make-push 1) (make-push 1) 'add))
(define I2 (list (make-push 1) (make-push 1) 'add (make-push 2) 'add))
This second definition forms instructions for a stack-based calculator: each instruction operates on the stack of numbers, either pushing a new number or adding the top two (and pushing the result).
We can define an evaluator for a series of stack instructions as:
; eval : [List-of Number] [List-of Instr] -> [List-of Number]
; takes an initial stack and list of instructions and runs them, producing a final stack
; if the instructions are malformed, returns an empty stack; else result will be a stack
; with a single number
(define (eval stk instrs)
(local [; eval-instr : Instr [List-of Number] [List-of Instr] -> [List-of Number]
; evaluates a single instruction, given a stack and rest of instructions
(define (eval-instr i stk instrs)
(cond [(symbol? i)
(if (>= (length stk) 2)
(eval (cons (+ (first stk) (second stk))
(rest (rest stk)))
instrs)
(list))]
[(push? i) (eval (cons (push-num i) stk) instrs)]))]
(cond [(empty? instrs) stk]
[(cons? instrs) (eval-instr (first instrs) stk (rest instrs))])))
(check-expect (eval (list) I0) (list 1))
(check-expect (eval (list) I1) (list 2))
(check-expect (eval (list) I2) (list 4))
(check-expect (eval (list) (list (make-push 10) 'add)) (list))
Now, your task is to define a function compile with signature AddExpression -> [List-of Instr], and to give it a good specification, compile-prop. Be sure to test your property on several examples using check-property. You might want to define a helper function on AddExpressions to help you write compile-prop.