Exercise 3.

We extend the grammar of Exercise 2 in order to handle unary functions with a single returned value. Here's a program showing these new features.

f: integer -> integer;
f(n: integer): integer == { 
  if n = 0 then {1} else {n * f(n-1)}; 
}

To do so, we add productions for generating the type of a function, the definition of a function, and a call to a function. Here's the enhanced grammar.

P $\longmapsto$ D; S

D $\longmapsto$ D; D

D $\longmapsto$ $\bf id$ :  T

T $\longmapsto$ A

A $\longmapsto$ $\bf boolean$

A $\longmapsto$ $\bf integer$

T $\longmapsto$ A₁$\bf\rightarrow$A₂

E $\longmapsto$ $\bf literal$

E $\longmapsto$ $\bf num$

E $\longmapsto$ $\bf id$

E $\longmapsto$ E₁ $\bf +$ E₂

E $\longmapsto$ E₁ $\bf =$ E₂

E $\longmapsto$ $\bf id$$\bf ($E₁$\bf )$

S $\longmapsto$ S₁; S₂

S $\longmapsto$ E

S $\longmapsto$ $\bf id$ := S₁

S $\longmapsto$ $\bf if$ E $\bf then$ $\bf\{$S₁$\bf\}$$\bf else$ $\bf\{$S₂$\bf\}$

S $\longmapsto$ $\bf while$ E $\bf repeat$ $\bf\{$S₁$\bf\}$

S $\longmapsto$ $\bf id$ $\bf ($$\bf id$ :  A₁$\bf )$$\bf :$A₂ = = $\bf\{$S₁$\bf\}$

To keep things simple, observe that we impose the following constraints.

(C₁)

The input type and the output type of a function can only be primitive types, that is boolean or integer. This appears in the above grammar.

(C₂)

In our language, there is only one scope for variables and functions. In other words, every variable or function is global.

(C₃)

In addition, each formal parameter of a function is viewed as a variable.

These constraints imply that only one symbol table is needed, as in the previous exercise. To denote the type of a function you can use a record of the form [in : T₁, out : T₂]. So, coming back to the above example

• parsing the first line would create an entry like in the symbol table,
• parsing the function definition would create an entry like .

Finally, since in this language every statement has a value (see the previous exercise), a function definition must have a value too. This value is simply the defined function. So, coming back again to the above example, the type of the statement corresponding to the function definition is just [in :  integer, out :  integer].

Question. Complete the type checker for the following rules. You can use any pseudo-code style that you like or even write sentences like if there exists an entry e with type T then T.

Answer 3