---
# System prepended metadata

title: 'Lab 35: A Provably-Correct Optimizer'

---

# Lab 35: A Provably-Correct Optimizer

## Problem 1

**Claim:** For any expression e, eval(e) = eval(optimize(e)) 

_Proof._ We will proceed by induction on $e$.

Case 1: $e$ is a number:

left side:
eval(e) -> e

right side:
eval(optimize(e)) -> eval(e) -> e

## Problem 2
Case 2: $e$ is an addition:

