There is an interesting article by David Warren on compiling with Prolog (i.e., David H.D. Warren, Logic Programming and Compiler Writing, Software Practice and Experience, vol 10, pp 97-125, available online from class lecture page through a VT Web connection) that shows examples of compiling arithmetic expressions by parsing them into syntax trees (represented as Prolog terms) and then translating those trees into a pseudo-assembly code. A word of caution: the published Warren article has many typos, despite the fact that it is an important paper, showing the flexibility of Prolog in protoyping. Please consult this errata sheet as you read the paper to avoid confusion.

This assignment involves parsing and type checking programs in a small, simple expression language with explicitly declared types. Your parser will build an abstract syntax tree for the input, and will type check all the program's expressions in that tree. For this purpose, an assignment statement will be considered a binary expression and an if statement will be well typed if each of its constituent statements are well-typed and its logical expression is well-typed. Because we are emphasizing type checking in this assignment, our language only contains assignments and if statements. The assignment will be staged to require type checking of increasingly larger subsets of the simple language that is defined by this grammar, revised on 2/17/2016.

All operations involving variables (e.g., assignment, addition, subtraction, concatenation) are only legal if the types are compliant and consistent with the types expected by the operation. The language does allow some type coercion; that is, one can assign an integer constant to a variable declared of type double with the appropriate type conversion happening automatically.

Stage 1 of the assignment will involve both assignment and if statements restricted only to involve scalar variables and constants. Stage 2 will involve scalar variables, constants and structs containing only scalar variables. There will be some new assignments possible such as A = B, where A and B are structs. The semantics of this copy statement are that if A and B are structs of the same type (i.e., with same named fields in same order), then the value of each field f of B is copied into the f field of A, assuming that the type of field f of B is type compatible with the type of field f of A. Stage 3 will further expand the assignment by the addition of arrays and array elements.

To sum up, you will be doing the following in each stage (over different kinds of variables in the expressions):

• building a predictive parser in Prolog, patterned after the one in the Warren paper, for a simple programming language involving assignments and if statements, and simple expressions built from scalar variables and constants (in Stage 1), and then including aggregate variables, namely, structs (in Stage 2) and arrays (in Stage 3).
• type checking programs in this simple statically typed language and issuing a message that declares a program to be well-typed or, if the program is not well-typed, issuing error messages that delineate those program statements (or expressions) that cause type errors.

Assignment Specifics

1. Your required documentation will be comments in the Prolog rules in your typechecker about which grammar rule they are parsing OR which grammar construct they are type checking. These comments should come at the top of the set of related Prolog clauses. Please consult Dr. Edwards' notes on commenting in Prolog for hints on good usage.
2. Write code for a Warren-style Prolog parser and type checker for programs written in our assignment language described by the grammar above.
3. The first step in the assignment will be to follow these instructions as to how to change the tokenizing programs given to you to recognize the terminals and statements in our assignment language. Use the parser in the Warran paper as a guide.
4. To write your typechecker so that it can be graded (in part) by WEB-CAT, we need to have all students use the same standard top-level Prolog predicate and the same output format. Please consult these instructions to make your Prolog program conformant and WEB-CAT checkable.
5. There are many ways to decompose this assignment into separate tasks each with a set of Prolog rules. Think about the overall organization of the type checking algorithm you will use BEFORE starting to code the Prolog and feel free to reuse parts of the Warren parser which will be provided.
   
   WARNING: you can spend lots of time on fancy type error checking -- DON'T. Get the main functionality of the assignment working with simple error checking before getting 'fancy'. Do not worry about your compiler being invertible! You can use Hint the simplest way to do the assignment is to build the program parse tree and then traverse it checking the types.
6. The provided Prolog files (i.e., tokenizing, symbol table lookup, copy of the Warren parser) will be posted on piazza by Hasan soon as will initial test data.
7. Grading Points will be earned by your code and its documentation, with emphasis on code functionality. All submissions at each stage will be tested on a set of common test data given to you, as well as additional test data added for grading. The correctness of your parse tree and your type checking will count for the final grade on the project. Partial credit can be earned by a correct solution for each stage of the of the assignment.

Last edited at 9:23pm by BGR on February 22, 2016