Register

4.1. Defining SLang 1¶

4.1.1. Syntax of SLang 1¶

So far we have examined how to program from a functional programming perspective and how the lambda calculus forms the theoretical foundation for that perspective. We will now shift our focus and consider how we could actually develop a small interpreter for a language based on the lambda calculus. We'll call that language SLang1, short for "Simple Language 1".

The development process for this interpeter will require our writing a JISON grammar to define the syntax of the language and transform programs in the language into an abstract syntax tree (AST).

How does abstract syntax differ from concrete syntax? In other words, how do parse trees differ from abstract syntax trees?

A parse tree has a leaf node for each token, and an interior node for each non-terminal. Parse trees are useful to represent the structure or syntax of the source program.

However, we are now interested in the meaning of the program, not just its superficial structure. Abstract syntax trees (or ASTs) are parse trees stripped of all nodes that are not essential for later processing (for us: the execution or interpretation process).

In an AST:

• Operators appear at interior nodes, not at leaf nodes and their operands become their children.
• Chains of unit productions (i.e., productions of the form <X> ::= <Y>) are collapsed.
• Lists are flattened.
• Syntactic details (semi-colons, parens, etc.) are omitted.

This is illustrated in the example below.

   Parse Tree       Abstract Syntax Tree
==========       ====================

exp                  *
|                  / \
term                3   +
/|\                   / \
term * factor            4   2
|      /|\
|     / | \
factor   ( exp )
|        /|\
3     exp + term
|      |
term   factor
|      |
factor   2
|
4


Additionally an AST often does not contain any nodes corresponding to non-terminals. Nonetheless, it contains all of the information that is needed for the interpreter to derive the correct meaning of the input program, that is, to evaluate the program and return its correct value.

     Input                                  Parse Tree
=====                                  ==========

{                                ____ methodBody _________
x = 0;                       /       /            \    \
while (x<10) {              {  declList        stmtList }
x = x+1;                       |           /        \
}                              epsilon   stmtList       stmt___
y = x*2;                                /      \       /  | \  \
}                                     stmtList   stmt    ID  = exp ;
/      \       \   (y)   / | \
AST                      stmtList      stmt     ...     exp * term
===                          |       / | |  \            |      |
epsilon   ID = exp ;         term   factor
methodBody                          (x)   |              |      |
/          \                            INTLITERAL     factor   INT
declList            stmtList                      (0)             |     (2)
/   |    \                                    ID
assign  while  assign                               (x)
/     \  ...   /     \
ID     INT     ID       *
(x)    (0)     (y)     / \
ID  INT
(x) (2)


The concrete syntax of Slang1 is defined by the following grammar:

<program>  ::= <exp>
<exp>      ::= <var_exp> | <fn_exp> | <app_exp> \red{| <papp_exp> | <int>}
<fn_exp>   ::= fn '(' (<var_exp> (',' <var_exp>)*)? ')' => <exp>
<app_exp>  ::= '(' <exp> <exp> ')'
<papp_exp> ::= <prim_op> '(' <args>? ')'
<args>     ::= <exp> (',' <exp>)*
<prim_op>  ::= + | * | add1


The SLang1 "program" (fn (a,b) => b y 3) would result in the following parse tree and AST.

                       parse tree                          AST
==========                          ===

program                          program
|                                |
exp                            app_exp
|                            /       \
_ app_exp ______            fn_exp         args
/   |   |    \   \           /    \        /    \
(  exp  exp   exp  )      [a,b]  var_exp var_exp int
_________/      \     \                   |      |      |
/              var_exp int                 b      y      3
______fn_exp___________     \     \
/ /    /  |    |  \  \  \     y     3               [ "Program",
/ /    /   |    |   \  \  \                            [ "AppExp",
fn ( var_exp , var_exp ) => exp                            [ "FnExp",
|         |          |                               ["a","b"],
a         b       var_exp                            ["VarExp","b"]],
|                             [ "args",
b                               ["VarExp","y"],
["IntExp",3]]]]


4.1.2. Concrete Syntax SLang1¶

This problem will help you master the concrete syntax of SLang 1. To earn credit for it, you must complete this randomized problem correctly three times in a row.

4.1.3. Abstract Syntax SLang1¶

This problem will help you master the abstract syntax of SLang 1.

4.1.4. Curry in SLang1¶

This problem will illustrate the semantics of SLang 1 while helping you review the definition of the curry function.

4.1.5. Semantics of SLang1¶

This problem focuses on the semantics of SLang 1.