Lambda Calculus

Parser.

The functional language has a simple grammar and parsing it is quite easy; a parser is included in an appendix. The lexical symbols and syntactic types are used throughout the interpreter.

                                                           {lexical items}
symbol = (word, numeral, empty{ () }, nilsy, charliteral, truesy, falsesy,
          open, close, sqopen, sqclose, curlopen, curlclose,
          letsy, recsy, insy, comma, colon,
          ifsy, thensy, elsesy, lambdasy, dot,
          quote,
          conssy,
          orsy, andsy,
          eq, ne, lt, le, gt, ge,
          plus, minus, times, over,
          nullsy, hdsy, tlsy, notsy,
          eofsy
         );

{\fB Lexical Types. \fP}

The syntactic types define a parse tree. The interpreter walks this tree executing a program.

tree = ^ node;

SyntaxClass = ( ident, intcon, boolcon, charcon, emptycon, nilcon,
                lambdaexp, application, unexp, binexp, ifexp, block,
                declist, decln
              );

node = record case tag :SyntaxClass of
          ident       :( id :alfa );
          intcon      :( n:integer );
          boolcon     :( b:boolean );
          charcon     :( ch:char );
          emptycon, nilcon:();
          
          lambdaexp   :( fparam, body :tree );
          application :( fun, aparam :tree );
          unexp       :( unopr :symbol; unarg :tree );
          binexp      :( binopr:symbol; left, right :tree );
          ifexp       :( e1, e2, e3 :tree );
          block       :( decs, exp :tree );
          declist     :( recursive:boolean; hd, tl :tree );
          decln       :( name: alfa; val:tree )
end;

{\fB Syntactic Types. \fP}