TIE-20306 Principles of Programming Languages, autumn 2019

Last change 27.11.2019 17:19.

This page change history:
2019-11-22: First public version
2019-11-27: Added description of provided helper code. Changed requirements of interpretation levels 1 and 3 a little.

Project work, phase 4

Semantic checks and/or running the program

Using the syntax tree it is now time for semantic checks and running the program. For full credits you DO NOT have to implement everything listed here. One can easily think about dozens of different checks and implementing them all would be too much work for this project.

So select the items you are interested in and concentrate creating a clearly documented, easy to read implementation of them. You might concentrate on hunting semantic errors or running the program.

A fully functional example on how to do semantic checks and a simple interpreter using our syntax tree can be found here.

Semantics of the language

This section describes the intended semantics (= meaning) of the language constructs. Please note that this is just a description, you don't have to implement all of these! The following sections describe what semantic checks and functionality to implement.

These are just quidelines. You decide the exact semantics yourself (and document them in your submission).

Datatypes

Variables

Functions

Pipes

Built-ins

Semantic checks

In this assigment, semantic checks are performed on the syntax tree (i.e., before running the program, even if you implement the interpreter part). In many programming languages ALL the checks are run and results printed out. However, it's easier to stop at the first semantic error (since recovering from the error and continuing is often quite complicated), so that's what we'll do in this assignment.

In the Semantics of the language section above, ideas for possible semantic checks are marked with "This is a possible semantic check.". However, there are more possible semantic checks that could be performed, so it's ok to also include your own, if you wish. The list below lists the mentioned semantic checks in the estimated order of easiness (the easiness of course depends somewhat on your design choices):

  1. Variables, functions, and parameters have to be defined before being used, no double definitions allowed.
  2. Parameters are only allowed to appear in the function in which they have been defined.
  3. The number of actual parameters in a function call has to match the number for formal parameters in the function definition.
  4. If a function returns a single value (with =), it can only be used in a place where a single value is ok. If a function returns a tuple (with !=), it can only be used in a place where a tuple is ok.
  5. When piping a tuple to a function or "each:", the size of the tuple has to agree with the number of parameters. Similarly, in "select:" the element number has to be within the tuple size. This semantic check is a little more challenging that most others, since it requires you to track the sizes of tuples in the syntax tree.

Implementing semantic checks

Probably easiest way to implement semantic checking of the syntax tree is to use the provided visitor pattern based function visit_tree(), as well as provided simple data structure SemData. The visitor can be used to perform checking passes over the tree, selecting which types of node to act on. The SemData class can be used to store the symbol table as well as other information needed for semantic checking, as well as passing that information along when performing the checks. For more hints on how to implement phase 4, please watch the 26.11. lecture recording, and read the description of the provided helpers at the end of this page.

Semantic errors are reported by returning an error message string instead of None from the functions provided to the visitor implementation. The provided visitor then prints out this error message and stops the program. If syntax tree nodes contain an attribute called "lineno", the line number is included in the error message.

Running the program

After running semantic checks, you now should have a syntax tree (program) which can be executed. We suggest that you write an interpreter which interprets (= runs) the syntax tree. (Alternatively you can generate code from the tree, i.e. write a compiler, but that's probably more complicated than interpretation. If you choose this option, contact the course staff first).

While running the program you don't have to implement any run-time semantic checks, if you don't want to. I.e. you can assume the program is semantically correct, even if you don't write all semantic checks, and you can assume there are no run-time errors which would require error handling in the interpreter.

Interpreting

One way to implement an interpreter is to have an "eval()" method that recursively evaluates the nodes in the syntax tree. You call the topmost eval() and it goes through the tree executing the node statements in the correct order. E.g. before running a plus(+) operation the left and right parts are evaluated first (the value of the evaluated expression can be the return value of eval()). The example Unicode calculator can be used as the basis for your interpreter (or you are welcome to design your own).

Levels of implementation

Below are different levels of implementing execution. Since levels depend on each other, it's advisable to implement them in order. Also, it's ok if some level is only implemented partially (of course that will be taken into account in grading).

  1. Evaluation of expressions consisting of arithmetic expressions and integer literals. The interpret should print out the value returned from the top-level return statement "=".
  2. Additionally, using integer variables works (i.e., definition and reading the value).
  3. Evaluation tuple variables and tuple expressions (including "select:" but not including pipes).
  4. In addition to above, function definitions, function calls and parameter passing works.
  5. Evaluation of pipe operations.
  6. Implementing recursion and proper local variables and parameters.

Grading in this phase

From this phase you can raise your preliminary grade from phase 3 by at most 3 grades:

Minimal functionality

Your program must start when executed in python by: python3 main.py in your submission directory. You can assume that this python interpreter has PLY installed.

Your program must understand the following command line arguments:

usage: main.py [-h] [--who | -f FILE]
  -h, --help            show this help message and exit
  --who                 print out student IDs and NAMEs of authors
  -f FILE, --file FILE  filename to process
(See the course snippet on how to implement this using python standard library.)

Errors

Your code should be built on top the previous phase (syntax), so the same errors messages from there should be used here also. As mentioned before, you don't have to implement run-time error checking, if writing the interpreter.

Required text document

In addition to the code, the group submits a text document in either plain text (.txt), markdown (.md) or pdf (.pdf) format. It should document each semantic check / implementation level you've done, explaining how it works. If you implemented any things of your own, explain them also in the document. Also tell what you thought about this assignment? What was difficult? What was easy? Did you learn anything useful?

Extras

If you have an idea, feel free to implement it (AND remember to document it)

Tools provided by the course

The file semantics_common.py contains a helper function visit_tree() and classes SemData and SymbolData to help with semantic checks (the classes may be useful also during interpretation).

Questions with answers

Nothing at the moment.

General practical questions about the course should be sent to popl@lists.tuni.fi.