EXERCISE # 3

Extend the denotational semantic description of Tiny into Medium,
the language described below.  The description of Tiny is given
(mathematically) in the class notes; an implementation in RPAL is
also available in the class notes, and the corresponding code is
available on this site.  Extend Tiny's denotational implementation,
which is written in RPAL, to implement Medium.

Medium is, by and large, a superset of Tiny.  It has
declarations, most reasonable operators (not just "="), a "for" loop
like the one in the C programming language, a "do" loop, and
a case statement.   Below is Medium's concrete syntax, from which
you should infer the necessary extensions to Tiny's abstract syntax.

Medium     -> 'program' Name ':' Dclns Body Name '.' => 'program';
Dclns      -> 'var' (Dcln ';')*                      => 'dclns'
           ->                                        => 'dclns';
Dcln       -> Name list ',' ':' Type                 => 'dcln';
Type       -> 'integer'                              => 'integer'
           -> 'boolean'                              => 'boolean';
Body       -> 'begin' Statement list ';' 'end'       => 'block'
           -> Statement;
Statement  -> Name ':=' Expression                   => 'assign'
           -> 'output' '(' Expression list ',' ')'   => 'output'
           -> 'if' Expression 'then' Statement
                     ('else' Statement)?             => 'if'
           -> 'while' Expression 'do' Statement      => 'while'
           -> 'for' '(' Statement ';' Expression
                                  ';' Statement
                    ')' Body                         => 'for'
           -> 'do' Statement list ';' 'while'
	      Expression                             => 'do'
	   -> 'case' Expression 'of' C_clause+       => 'case'
           -> Body
           ->                                        => '<null>';

C_clause   -> '<integer>' ':' Statement              => 'c_clause';

Expression ->   ... as usual, with operators <=,>=,
                     <>,<,>,=,+,-,*,/,and,or,not,read.
                Atomic values are true,false, integer,
		       identifier, and eof (as in Pascal).

The following comments and suggestions might help:


The implementation closely mirrors the denotational semantics 
description given in the notes.  The AST is (inevitably) represented
as a tuple.  Comparing things in RPAL is a bit of a problem: "x eq y"
only works if x and y are of the same type.  Hence there is a generic
"EQ" function, that is used (with the "@" notation) in infix form.  
By the way, the "prefix to infix" transformer "@" is also used for
"COMP" (composition) and "PIPE" (=>).  Everything else should be
easily recognizable, IF you understand the class notes thoroughly.

You probably want to extend the "State" semantic domain, to incorporate
a declaration mechanism (an Id to Type mapping, where
Type = {Int,Bool}).  Alternatively, you could extend the "Memory"
semantic domain, to a mapping from Id's to (Val,Type) pairs.

Declarations should affect the declaration mechanism, and not memory.
Hence, when declared, an identifier has a type but not a value.

Don't forget to perform typechecking.

By definition (see the grammar), there is exactly
one "dclns" node.  Don't assume that there are at most two
"dcln" nodes under the "dclns" node.   The same goes for "block"
(a.k.a ";"), and "output" (a.k.a. "print").   You will need to traverse
the arbitrary number of kids of each of these, recursively.  It might
be useful to define a generic "recursive traverser" function.

Some test programs have been made available on this site.

A clarification on the semantics of the 'case' statement.
The control expression is intended to be evaluated only once,
at the beginning of the case statement.  Also, the intent is
to succesively compare the value of the control expression
against each constant, execute the corresponding statement
if there's a match, AND QUIT THE CASE STATEMENT.  Thus,
this case statement is modeled after the one in Pascal.