1. Homepage
2. Programming
3. CMPT 489 Compiler Technology - SIMD Parallel Processing - Final Project: Program Synthesis

# CMPT 489 Compiler Technology - SIMD Parallel Processing - Final Project: Program Synthesis

SFUCMPT489Compiler TechnologySIMD Parallel ProcessingProgram SynthesisJava

CMPT 489 / 980 Program Synthesis

Final Project

Phase I is due by 11:59pm PT on Wednesday Nov 8, 2023. Phase II is due by 11:59pm PT on Tuesday Dec 5, 2023. Please submit them to Canvas on time. No late submission is accepted.

Requirements:

This project must be your own work. No collaboration is permitted.

The programming language of this project is Java 11.

You can learn the code on slides and start from it.

You can use third-party libraries but not existing synthesizers. However, you can implement the algorithms in existing synthesizers by yourself.

1 Problem Description

Consider the following context-free grammar G
E
::= Ite(B,E,E)|Add(E,E)|Multiply(E,E)|x|y|z|1|2|3

B ::= Lt(E, E) | Eq(E, E) | And(B, B) | Or(B, B) | Not(B) x, y, z Variables 1, 2, 3 Constants

Here, E is the start symbol. E and B are non-terminals; all other symbols are terminals. The meaning of terminal symbols are self-explanatory. Specifically, Ite is the if-then-else operator. Add is the addition (+) operator. Multiply is the multiplication () operator. x,y,z are integer variables. 1,2,3 are integer constants. Lt is the less-than (<) operator. Eq is the equals (==) operator. And is the logical conjunction (&&). Or is the logical disjunction (||). Not is the logical negation (!).

In this project, you need to write an example-based program synthesizer in Java. Specifically, the synthesizer takes as input a list of input-output examples and the context-free grammar G and produces as output an implementation of f(x,y,z) in the language of G such that f(x,y,z) is consistent with the provided examples. You can assume f only uses three variables x, y, z, and all their types are Int. The return type of f is also Int. If the synthesis succeeds, your program should print the program, e.g., Add(Add(y, z), x), to the console. Otherwise, if the synthesis fails, the program should print null.

2 Codebase

A codebase is provided as the starting point. It contains the basic framework for the synthesizer. Details are explained as follows.

Package synth.cfg

This package defines the data structure for the context-free grammar (CFG). It has the following classes Symbol. An abstract class for symbols in the CFG.
Terminal. A subclass of Symbol that corresponds to terminals in the CFG.
NonTerminal. A subclass of Symbol that corresponds to non-terminals in the CFG.

1

• Production. A class for productions in the CFG. A production is of the form ReturnSymbol ::= Operator(ArgSymbol, ..., ArgSymbol)

• CFG. A class for representing the CFG. The most important method is getProductions, which takes as input a non-terminal symbol N and returns as output a list of all productions with N being the left-hand-side of the production.

Package synth.core

This package contains the classes for synthesizers, examples, programs, and interpreters.

• ASTNode. A class for general Abstract Syntax Tree (AST) nodes. The symbol fields corresponds to

the symbol in the CFG. The children field corresponds to the children nodes.

• Program. A class for representing a program. It only has one field root, which is the root node of the

corresponding AST.

• Example. A class that defines the data structure of an example. The input field is a map from variable

names to their values. The output field is the output value.

• Interpreter. A class that defines an interpreter of the language of G. The most important method is the static method evaluate, which takes as input a program and an environment and returns as output the evaluation result. The environment is essentially a map from variable names to their values, just like the input field of Example. Concrete examples on how to use Interpreter.evaluate are provided in the test class synth.core.InterpreterTests.

• ISynthesizer. An interface that defines the input and output of a synthesizer. The inputs are a CFG and a list of examples. The output is a program.

• TopDownEnumSynthesizer. A top-down enumerative synthesizer that implements the ISynthesizer interface. You need to implement this class.

Package synth.util

This package contains the utility classes and methods.

• FileUtils. A class for file operations. The readLinesFromFile static method reads a file into a list of strings, where each line of the file is a string.

• Parser. A class for parsing the examples. The parseAnExample static method parses text of the form “x=a, y=b, z=c -> d” to an object of class Example. The parseAllExamples static method parses a list of examples from a list of strings, where each string corresponds to an example. It ignores empty strings.

Class synth.Main

The main class of the framework. It has two methods.

• main. It is the entry of the program. It takes one command-line argument args[0] for the path to the examples file.

• buildCFG. It builds the CFG G in Section 1. Tests

JUnit tests are provided in the src/test directory. You are welcome to add more!
synth.core.InterpreterTests. It contains several unit tests for the interpreter, which is also helpful

for understanding the usage of the interpreter.
2

Other Files

pom.xml. The configuration file for Maven. examples.txt. A sample examples file.

3 Compilation and Execution

Compilation. This codebase uses the Maven build system. Suppose you enter the Synth directory, the project can be easily compiled with one command

\$ mvn package
Then you should be able to see the message “BUILD SUCCESS”. A directory called target will be created

and a jar file called synth-1.0.jar will be generated inside the target.
Execution. In the Synth directory, you can execute the program using the following command (use ;

instead of : in Windows)

```\$ java -cp lib:target/synth-1.0.jar synth.Main <path-to-examples-file>
```

where <path-to-examples-file> is the path to the examples file. For example, you can run

```\$ java -cp lib:target/synth-1.0.jar synth.Main examples.txt
```

You will see a runtime exception with message “To be implemented”, because the synthesizer is not imple- mented yet. After you finish implementing the synthesizer, you should see something like (not unique)

```Add(Add(y, z), x)
```

4 Phase I

In Phase I, you need to implement a top-down enumerative synthesizer in synth.core.TopDownEnumSynthesizer. Deliverable

5

A zip file called Phase1 Firstname Lastname.zip that contains at least the followings:

The entire Synth directory. You can change existing code if you want, but please make sure the project can be compiled and executed as explained in Section 3.

A short report (1-2 pages) called Phase1 Firstname Lastname.pdf that explains the design choices, features, tests, issues (if any), and anything else that you want to explain about your program.

Phase II

In Phase II, you can implement any synthesis algorithm that improves the performance of the synthesizer on the same problem. You also need to create a small benchmark set and evaluate your algorithm over the benchmarks.

A zip file called Phase2 Firstname Lastname.zip that contains at least the followings:

• The entire Synth directory. You can change existing code if you want, but please make sure the project

can be compiled and executed as explained in Section 3.

• A long report (5-6 pages) called Phase2 Firstname Lastname.pdf that explains the algorithms, benchmarks, evaluation results, design choices, features, tests, issues (if any), and anything else that you want to explain about your program.

## Get in Touch with Our Experts

QQ
WeChat
Whatsapp
SFU代写,CMPT489代写,Compiler Technology代写,SIMD Parallel Processing代写,Program Synthesis代写,Java代写,SFU代编,CMPT489代编,Compiler Technology代编,SIMD Parallel Processing代编,Program Synthesis代编,Java代编,SFU代考,CMPT489代考,Compiler Technology代考,SIMD Parallel Processing代考,Program Synthesis代考,Java代考,SFUhelp,CMPT489help,Compiler Technologyhelp,SIMD Parallel Processinghelp,Program Synthesishelp,Javahelp,SFU作业代写,CMPT489作业代写,Compiler Technology作业代写,SIMD Parallel Processing作业代写,Program Synthesis作业代写,Java作业代写,SFU编程代写,CMPT489编程代写,Compiler Technology编程代写,SIMD Parallel Processing编程代写,Program Synthesis编程代写,Java编程代写,SFUprogramming help,CMPT489programming help,Compiler Technologyprogramming help,SIMD Parallel Processingprogramming help,Program Synthesisprogramming help,Javaprogramming help,SFUassignment help,CMPT489assignment help,Compiler Technologyassignment help,SIMD Parallel Processingassignment help,Program Synthesisassignment help,Javaassignment help,SFUsolution,CMPT489solution,Compiler Technologysolution,SIMD Parallel Processingsolution,Program Synthesissolution,Javasolution,