Final Project Proposal: Part 4

Prompt: Decide on the implementation.

•frontend:

We will parse the language in the same way we parse the 164 language: we will be using the same AST generated from the symantic actions in project 3 to create the DAG.

•the core language: We will reuse the 164 language from project 3. The least that is required for creating the DAG is just a list of statements. After this, we will extend this to lists of statements within lists of statements when we incorporate lambdas.

•internal representation:

There are two ways we can interpret the dag created from the AST. One way is to execute the statements while traversing the dag. The other way is to compile the dag into bytecode and send that to the bytecode interpreter to run it in parallel. We are leaning towards the bytecode interpreter since we would only have to modify it and it gives us the freedom to parallelize coroutines (if we figure out a way how of course).

•interpreter/compiler:

The parser will generate the AST for the 164 language as before. Instead of compiling the AST into bytecode, the compiler will traverse the AST and record what variables are written and/or read at each statement. Then based on this the compiler will create a DAG where each node represents a statement and the edges represent the flow of the program. This means that before node N is executed, all of its parent nodes must be executed.

The bytecode interpreter will start at the top of the dag and run each independent source in parallel. Every child statement will have a counter to count how many parent statements have finished executing. When a statement is done executing, it will increment the counter of its child and check to see if the counter value is equal to the number of parents of the child. If it is equal, it will execute that statement. This continues until the DAG is traversed.

•debugging: We will debug our implementation by using GraphViz to visualize the DAG.