CS5314: Concepts of Programming Languages
Assignment I: Static Type Checking in Prolog
2/22/16 New Due Dates and Assignment Specification:
Stage 1 due: Feb 26, 2016 at 11:59pm
Final due date for entire project: Stages 1+ 2 due: March 2, 2016 at 11:59pm
Stage 3 can be turned in for extra credit
Note: Stay tuned as to whether or not final project contains string type
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.
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
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
- 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.
- 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.
- Write code for a Warren-style Prolog parser and type checker for programs
written in our assignment language described by the grammar above.
- 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.
- 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
- 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.
- 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.
- 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