Homework # 4
due 2004/10/28

Using Attribute Extensions

In lecture we have seen (or will see) several attribute grammar extensions, including:

These extensions make it easier and more high-level to define semantic analyzers for real programming languages.

Use these new features to rewrite your semantic analyzer for Cool. You should also ensure that your semantic analyzer handles all of Cool. (Undergraduates need not check for any additional errors; graduate students should find all the errors that coolc finds.)

Not all of the extensions are available with the static scheduler, and thus you will need to use the dynamic scheduler (omit the -S option to apscpp). The dynamic scheduler will not warn you about undefined attributes at compile-time; the problem will not be discovered until run-time. You will need to use the -G option to apscpp to generate tracing information, and the -s option to the driver to turn on the trace.

As before we have provided a partial attribute grammar to get you started. You cannot start this homework until you are done working on Homework #3, since the part we provide you is for the cases you handled in the previous homework. We also provide a driver and a Makefile.

APS has other features (such as procedures, polymorphic attributes, for-loops, and pattern matching) but the apscpp compiler does not currently implement them, so they cannot be used. Adding more features to apscpp or making more things available for static scheduling is a good master's project or thesis possibility.

The Table ADT

For this assignment, we encourage you to use the TABLE module. This module provides rapid lookup but has some extra requirements to ensure declarativeness. The TABLE module takes two parameters: the key type (which must be ordered) and the value type (which must be combinable). The value type is usually a bag or set type.

All the values assigned for a key in the table are combined together without regard to the order in which they were entered. Assuming we have a collection (or occurrence of a collection attribute) $t$ of type $T$, then if you write

$t$ :> $T$$table_entry($k$,$v$);
then an entry for key $k$ and value $v$ is added to $t$. In order to find something in the table, you need to select out the part of the table dealing with the particular key and then pattern match on the result:
case \(T\)$select(\(t\),\(k\)) begin
  match \(T\)$table_entry(?,?v) begin
    - use v
  end;
end;
The result of select will always be of this form: if the key has never been entered in the table, the initial value of the combinable value type (for instance {}) is the result.

As usually in APS, the value of the table cannot be used until the table is complete. In particular, it is useless to write:

if not in_table(\(t,k\)) then   - Don't do this!
  \(t\) :> \(T\)$table_entry(...);
endif;
The current implementation of TABLE is somewhat fragile. Don't call the combination function yourself: only use a table type as the type of a collection (or collection attribute).

Files and Deliverables

Make a directory for your assignment, go into it and then copy over the APS files:


grid.cs: make -f /afs/cs.uwm.edu/users/classes/cs754/src/homework4/Makefile
This will get several files including
README
Some questions to answer.
Makefile
A Makefile to make the executable (with dynamic scheduling).
table.aps
The table abstraction in APS.
cool-dynamic-semant-driver.cpp
The driver (to use the global collection messages).
cool-dynamic-semant.aps
The semantic analyzer attribute grammar (incomplete!)
Only the README and the last file should be edited. The others should not be.

You will get a link error when you first start because the functions type_lub, type_leq and find_class have empty bodies, and the current APS compiler assumes they are ``native'' functions (with bodies written in C++). You should start the assignment by writing (first drafts of) these functions.

When you are finished with the homework, please answer the questions in the README.


John Tang Boyland
2004-10-11