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

Engage in a Conversation
SFUCMPT489Compiler TechnologySIMD Parallel ProcessingProgram SynthesisJava

CMPT 489 / 980 Program Synthesis CourseNana.COM

Final Project CourseNana.COM

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. CourseNana.COM

Requirements: CourseNana.COM

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

The programming language of this project is Java 11. CourseNana.COM

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

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

1 Problem Description CourseNana.COM

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

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

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 (!). CourseNana.COM

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. CourseNana.COM

2 Codebase CourseNana.COM

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

Package synth.cfg CourseNana.COM

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. CourseNana.COM

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

  • 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. CourseNana.COM

    Package synth.core CourseNana.COM

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

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

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

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

    corresponding AST. CourseNana.COM

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

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

  • 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. CourseNana.COM

  • 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. CourseNana.COM

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

    Package synth.util CourseNana.COM

    This package contains the utility classes and methods. CourseNana.COM

    • 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. CourseNana.COM

    • 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. CourseNana.COM

      Class synth.Main CourseNana.COM

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

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

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

        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 CourseNana.COM

        for understanding the usage of the interpreter.
        2
        CourseNana.COM

CourseNana.COM

Other Files CourseNana.COM

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

3 Compilation and Execution CourseNana.COM

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

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

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 ; CourseNana.COM

instead of : in Windows) CourseNana.COM

$ 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 CourseNana.COM

$ 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) CourseNana.COM

Add(Add(y, z), x)

4 Phase I CourseNana.COM

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

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

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. CourseNana.COM

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. CourseNana.COM

Phase II CourseNana.COM

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. CourseNana.COM

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

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

    can be compiled and executed as explained in Section 3. CourseNana.COM

  • 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.  CourseNana.COM

Get in Touch with Our Experts

QQ QQ
Wechat WeChat
Whatsapp 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,