# Assignment 1

Submission Instructions This assignment is due at 5pm on the date indicated in the class calendar. The starter code for the assignment can be found here. In order to submit your code, pack your BottomUpEnumerator.jl, Question2.jl, and question3.sk files into a tar file and submit through stellar (we will post a link as the deadline approaches).

Collaboration policy You are allowed to consult with at most one other student while working on the pset, but every student is responsible for writing their own code and submitting their own work. If you do consult with another student, you should explicitly acknowledge them in your submission (you can do that in a comment in BottomUpEnumerator.jl).

## Setup instructions

### Problem 1b

Your goal is now to implement a new the rest of the bottom up enumeration algorithm. Specifically, implement elim_equivalents, which takes a list of shapes and returns a list of shapes containing all the shapes in the input list, but with all equivalent shapes removed. Two shapes are equivalent if they have the same input/output behavior on the given points. The Dict feature in Julia will be useful for this task.

Then, implement synthesize, which takes a list of input/output pairs and returns a shape that matches the input/output pairs.

You can test your implementation by running the following command on your command line:

## Problem 3 (30 pts)

For this problem, you will be using Sketch to answer some of the questions about a new language. You should download the latest version of sketch from here . Note: do not follow the build instructions. Just unzip the file, and then run the binary located at sketch-frontend/sketch. You will find the sketch language reference useful.

We have defined a simple arithmetic language for the following expressions:

Node:= Num(int n).....................// numeric constant num:int | False()...........................// constant FALSE. | Var(string varname)...............// variable Var:int | Plus(Node left, Node right)......// arithmetic expressions plus and times | Times(Node left, Node right).....// Plus(int,int):int Times(int, int):int | Lt(Node left, Node right)........//less than operator Lt(int, int):bool | And(Node left, Node right).......// boolean operators And(bool,bool):bool | Not(Node left)...................// Not(bool):bool | Ite(Node cond, Node tcase, Node fcase)...// if-then-else; Ite(bool, int, int):int Starter code for this assignment is provided in question3.sk

### Problem 3.a

Encode the arithmetic grammar from above as a generator in Sketch.

### Problem 3.b

Use your generator to synthesize expressions for the following examples: x=5, y=5, out=15; x=8, y=3, out=14; x=1234, y=227, out=1688; And x=10, y=7, out=17 x=4, y=7, out=-7 x=10, y=3, out=13 x=1, y=-7, out=-6 x=1, y=8, out=-8

### Problem 3.c

Experiment with different flags to speed up the search. Your submitted code should use the pragma options directive to include the flags that give you the best performance.