# 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

First, you should install julia using the instructions here. Then, install the packages you will need for this assignment by running the following commands in the julia REPL:## Problem 1 (40 pts)

The goal of this assignment is for you to experiment with some of the bottom up inductive synthesis algorithm discussed in class. The code defining the language and interpreter is in the `src` directory, under `Combinata.jl` and `Interpreter.jl`. You should only modify the `BottomUpEnumerator.jl` file; you will submit only this file for Question 1. We have defined a simple language for the following expressions:`make_coord`

, `make_rect`

, `make_triangle`

, and `make_circle`

rather than calling the constructors directly. These functions will check that the coordinates are valid and throw an error if they are not.
To see examples of how to render shapes for debugging, you can look at the `Render.jl`

file, specifically the
function `render_examples`

.
### Problem 1a

As a starter task, implement the function`grow`

in `BottomUpEnumerator.jl`

. This function
takes a list of shapes and returns a list of shapes containing
- all the shapes in the input list
- all the shapes that can be obtained by applying one of the constructors to two shapes in the input list
You can test your implementation by running the following command on your command line:
### 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:

Many of these tests might take several seconds, but not much longer. The entire question-1b suite takes 90 seconds on Kavi's laptop. If your tests are taking much longer than this (> 5 minutes), you should consider revising your implementation.

Hint for the test `flipped_triangle`

: make sure that the Context independent equivalence property holds for your implementation.

## Problem 2 (30 pts)

Consider the following grammar for a problem:`last2Digits(x + 3) ++ last3Digits(x + 537) ++ last4Digits(x + 82) ++ last5Digits(x + 87)`

applied to 9928 should return 31465001010015 (31 ++ 465 ++ 0010 ++ 100015)
The question marks ?? indicate unknown constants.
You should assume the function operates only over the integers.
Even though the space of potential expression is very large, the search space has a lot of
structure. Our goal for this problem is to come up with a representation of the search
space and a search strategy that exploits this structure and allows us to efficiently solve for a program in
this space given a set of input/output pairs. In particular, the goal is to find a way
to factor the search so it is possible to solve for the unknowns without having
to search the exponentially large space.
So your goal is to implement a function with the interface below.
`inputoutputs`

is a list of input output pairs (each input/output pair
represented as a tuple of Int64, String). The function should return an AST for the synthesized
program using the same format as `example_lkd`

.
The key requirement is that your function
should execute in **linear time** with respect to the size of this input list.
Your code should be well commented to clearly explain why your algorithm is linear
time and complete (guaranteed to find a solution if one exists).
Hints:

- If the last 3 digits of (x + y) are z, then the last 3 digits of (z - x) are the last 3 digits of y.
- For a given program, the locations at which the output breaks into terms are fixed.
- A solution that has to iterate through the input list a large number of times is still linear time as long as the number of passes is bounded by a constant.

## 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**. You will find the sketch language reference useful.

*not*follow the build instructions. Just unzip the file, and then run the binary located at sketch-frontend/sketchWe have defined a simple arithmetic language for the following expressions:

### 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:### Problem 3.c

We add the constraints- Multiplications can only occur between variables and constants or between two variables
- Comparisons cannot include any arithmetic, only variables and constants

### Problem 3.d

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.