Due 19 November at 11:59pm EST (Late: 20 November at 11:59pm)
P/SP/S: 50/50/0
In this project, you will implement an interpreter for SmallC, a tiny C-like language. The language supports variables, int and bool types, equality and comparison operations, math and boolean operations, control flow, and printing, all while maintaining static type-safety and being Turing complete.
The language consists of expressions from the expr type and statements from the stmt type. These algebraic types can be used to represent the full space of well-formed SmallC programs. Their definitions are found in the smallCTypes.ml file. This file should be a constant reference to the data types involved in successfully working with SmallC.
You must use the lexer and parser you implemented in p4a. If yours isn't working, come to virtual office hours and we'll do our best to help you. So you should begin by copying in your parser and lexer implementation from the previous portion of the project.
In your code, you may use any non-imperative standard library functions (with the exception of printing), but the ones that will be useful to you will be found in the Stdlib module and the List module.
You still may not use any imperative structures of OCaml such as references or the Hashtbl module.
You can run the SmallC interpreter directly on a SmallC program by running dune exec bin/interface.bc -- <filename>. This driver reads in a program from a file and evaluates the code, outputing the results of any print statements present in the source file. Think of this command a lot like the ruby command, but instead of running the Ruby interpreter, it runs the SmallC interpreter that you wrote.
If you would like more detailed information about what your code produced, running dune exec bin/interface.bc -- <filename> -R provides a report on the final variable bindings as reported by your evaluator. If you would like to see the data structure that is being generated by the parser and fed into your interpreter, run dune exec bin/interface.bc -- <filename> -U and our Utils module will translate the data structure into a string and print it out for you. Use the interface executable to your advantage when testing; that's why we're providing it!
You will submit this project to Gradescope. Make sure to submit parser.ml and lexer.ml and eval.ml each time, even if you only modified one of them (this will be done automatically if you use the gradescope-submit command.)
The evaluator must be implemented in eval.ml in accordance with the signatures for eval_expr and eval_stmt found in eval.mli. eval.ml is the only file you will write code in. The functions should be left in the order they are provided, as your implementation of eval_stmt will rely on eval_expr.
The heart of SmallC is your evaluator. We have already implemented Lexer and Parser modules that deal with constructing tokens and creating the AST out of a program. Where your code picks up is with a representation of SmallC programs as OCaml datatypes, which you are then responsible for evaluating according the rules below. A program is made up of a series of statements and expressions:
- Statements represent the structure of a program - declarations, assignments, control flow, and prints in the case of SmallC. - Expressions represent operations on data - variable lookups, mathematical and boolean operations, and comparison. Expressions can't affect the environment, and as a result only return a
valuecontaining the value of the expression.
You are responsible for implementing two functions, eval_expr and eval_stmt in that order. Each of these takes as an argument an environment (given in smallCTypes.ml) that is an association list. An association list is a list of pairs (2-tuples) where the key is the first element of the pair and the value is the second element. Elements earlier in the list override elements later in the list. In our case the association list is of type (string * value) list where the string is the id name and the value is the current value of that id. The List module has many useful functions for working with association lists. Statements may change the values of variables, so eval_stmt returns a possibly updated environment.
A formal operational semantics of SmallC can be found in semantics.pdf. We highly recommend you read this document as you work to clear up any possible ambiguity introduced by the English explanations below. The formal semantics do not, however, define error cases such as addition between a boolean and an integer and therefore represent a stuck reduction. The expected behavior for these irreducable error cases are defined only in this document and can be boiled down to the following rules:
- Any expression containing division by zero should raise a
DivByZeroerror when evaluated. - Any expression or statement that is applied to the wrong types should raise a
TypeErrorexception when evaluated, for example, the expression1 + truewould result inTypeError. - An expression or statement that redefines an already defined variable, assigns to an undefined variable, or reads from an undefined variable should raise a
DeclareErrorwhen evaluated.
We do not enforce what messages you use when raising the TypeError or DeclareError exceptions; that's up to you. Evaluation of subexpressions should be done from left to right, as specified by the semantics, in order to ensure that lines with multiple possible errors match up with our expected errors.
- Type:
environment -> expr -> value - Description: Takes an environment
envand an expressioneand produces the result of evaluatinge, which is something of typevalue(Int_ValorBool_Val).
Integer literals evaluate to a Int_Val of the same value.
Boolean literals evaluate to a Bool_Val of the same value.
An identifier evaluates to whatever value it is mapped to by the environment. Should raise a DeclareError if the identifier has no binding.
These rules are jointly classified as BinOp-Int in the formal semantics.
These mathematical operations operate only on integers and produce a Int_Val containing the result of the operation. All operators must work for all possible integer values, positive or negative, except for division, which will raise a DivByZeroError exception on an attempt to divide by zero. If either argument to one of these operators evaluates to a non-integer, a TypeError should be raised. For exponentiation, if the operation would give you back a non-integer, you should floor it.
These rules are jointly classified as BinOp-Bool in the formal semantics.
These logical operations operate only on booleans and produce a Bool_Val containing the result of the operation. If either argument to one of these operators evaluates to a non-boolean, a TypeError should be raised.
The unary not operator operates only on booleans and produces a Bool_Val containing the negated value of the contained expression. If the expression in the Not is not a boolean (and does not evaluate to a boolean), a TypeError should be raised.
These rules are jointly classified as BinOp-Int in the formal semantics
These relational operators operate only on integers and produce a Bool_Val containing the result of the operation. If either argument to one of these operators evaluates to a non-integer, a TypeError should be raised.
These equality operators operate both on integers and booleans, but both subexpressions must be of the same type. The operators produce a Bool_Val containing the result of the operation. If the two arguments to these operators do not evaluate to the same type (i.e. one boolean and one integer), a TypeError should be raised.
- Type:
environment -> stmt -> environment - Description: Takes an environment
envand a statementsand produces an updatedenvironment(defined in smallCTypes.ml) as a result. This environment is represented asain the formal semantics, but will be referred to as the environment in this document.
NoOp is short for "no operation" and should do just that - nothing at all. It is used to terminate a chain of sequence statements, and is much like the empty list in OCaml in that way. The environment should be returned unchanged when evaluating a NoOp.
The sequencing statement is used to compose whole programs as a series of statements. When evaluating Seq, evaluate the first substatement under the environment env to create an updated environment env'. Then, evaluate the second substatement under env', returning the resulting environment.
The declaration statement is used to create new variables in the environment. If a variable of the same name has already been declared, a DeclareError should be raised. Otherwise, if the type being declared is Int_Type, a new binding to the value Int_Val(0) should be made in the environment. If the type being declared is Bool_Type, a new binding to the value Bool_Val(false) should be made in the environment. The updated environment should be returned.
The assignment statement assigns new values to already-declared variables. If the variable hasn't been declared before assignment, a DeclareError should be raised. If the variable has been declared to a different type than the one being assigned into it, a TypeError should be raised. Otherwise, the environment should be updated to reflect the new value of the given variable, and an updated environment should be returned.
The if statement consists of three components - a guard expression, an if-body statement and an else-body statement. The guard expression must evaluate to a boolean - if it does not, a TypeError should be raised. If it evaluates to true, the if-body should be evaluated. Otherwise, the else-body should be evaluated instead. The environment resulting from evaluating the correct body should be returned.
The while statement consists of two components - a guard expression and a body statement. The guard expression must evaluate to a boolean - if it does not, a TypeError should be raised. If it evaluates to true, the body should be evaluated to produce a new environment and the entire loop should then be evaluated again under this new environment, returning the environment produced by the reevaluation. If the guard evaluates to false, the current environment should simply be returned.
The formal semantics rule for while loops is particularly helpful!
The for statement will contain four components: an ID, a starting expression, an ending expression, and a body statement. The starting and ending expressions should both evaluate to an integer value that will be used as the start value for your ID, and the ending point of the loop respectively (inclusive). If either of the expressions do not evaluate to an integer, then you should raise a TypeError.
On each iteration of the for loop you should evaluate the body statement. This evaluation will result in a new environment, under which the following iteration of the loop will be evaluated. Note that the for loop for our language is self-incrementing, meaning that the ID will be incremented by one at the end of the loop (with any other changes made to the ID or other variables from within the body being respected). The current environment will be returned in the case that the value is not within the range as defined by the starting and ending expressions.
The print statement is your project's access to standard output. First, the expression to print should be evaluated. Print supports both integers and booleans. Integers should print in their natural forms (i.e. printing Int_Val(10) should print "10". Booleans should print in plaintext (i.e. printing Bool_Val(true) should print "true" and likewise for "false"). Whatever is printed should always be followed by a newline.
VERY IMPORTANT NOTE ON PRINTING: If you attempt to print with print_string, print_int, etc... you will fail any test that checks your output. This is because we do not directly intercept your output, but rather have implemented some wrapper functions in the Utils for program printing (do not remove open Utils from the top of eval.ml!). As a result, your code may have any amount of print_string statements and it WILL NOT be seen the tests. Only printing performed through the following wrapper functions will be evaluated by the test system, and as a result should be used exclusively with Print. The supplied print wrappers which you must use in place of the built-in print functions for any and all output resulting from Print statements and for nothing else are as follows:
print_output_string : string -> unitprint_output_int : int -> unitprint_output_bool : bool -> unitprint_output_newline : unit -> unit
This means that you may use the standard print functions (e.g. print_string) for debugging purposes without messing up the tests.
Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus, which you should review before starting.