Skip to main content

Abstract

rascal-0.40.17

Synopsis​

A version of the "Exp" language based on abstract syntax.

Description​

The abstract syntax for a language is a data type that is used to represent programs in the language in an abstract form. Abstract syntax has the following properties:

  • It is "abstract" in the sense that it does not literally contain textual details such as parentheses, layout, and the like.
  • While a language typically has one grammar (also known as, concrete syntax) it may have several abstract syntaxes for different purposes: type analysis, code generation, etc.
  • Abstract syntax trees are sometimes also used as symbolic values for abstract computation and interpretation.

Examples​

The abstract syntax for Exp looks like this:

data Exp 
    = con(int n)               ❶  
    | mul(Exp e1, Exp e2)      ❷  
    | add(Exp e1, Exp e2)      ❸  
    ;
  • Line 4 defines integer constants, e.g., con(123).
  • Line 5 defines multiplication, e.g., mul(con(2),con(3)).
  • Line 6 defines addition, e.g., add(con(2),con(3)).

Given the abstract syntax for Exp, we can define an interpreter that evaluates expressions. An interpreter, in this case, is a function that takes Exp as input and produces int as output:

int eval(con(int n)) = n;                                 ❶  
int eval(mul(Exp e1, Exp e2)) = eval(e1) * eval(e2);      ❷  
int eval(add(Exp e1, Exp e2)) = eval(e1) + eval(e2);      ❸  

test bool tstEval1() = eval(con(7)) == 7;
test bool tstEval2() = eval(mul(con(7), con(3))) == 21;
test bool tstEval3() = eval(add(con(7), con(3))) == 10;
test bool tstEval4() = eval(add(con(3), mul(con(4), con(5)))) == 23;

Here we see Rascal's pattern-directed invocation in action (see Function Declaration). The essence is this: In other languages the formal parameters in a function declaration are just that: Formal parameters, i.e., single names that can be used inside the function and that are bound when the function is called. In Rascal, however, the formal parameters are actually a pattern and functions can have arbitrarily complex patterns as (single) formal parameter. These patterns may bind variables and thus introduce variables that can be used in the function body.

The big advantage of pattern-directed invocation is modularity and extensibility:

  • The treatment of the cases in the abstract syntax is decoupled.
  • If the abstract is extended later on with new cases, the functions for the old cases can be reused.

In this example we use this mechanism to define separate functions for each case in the abstract syntax.

  • ❶ Defines the case for evaluating integer constants: They evaluate to themselves.
  • ❷ Defines the case for evaluating multiplication: First evaluate the arguments e1 and e2 and return the multiplication of their values.
  • ❸ Defines the case for evaluating addition: first evaluate the arguments e1 and e2 and return the addition of their values.
rascal>eval(mul(con(7), con(3)));
int: 21
rascal>eval(add(con(3), mul(con(4), con(5))));
int: 23

Entering expressions in abstract syntax form is no fun, and this is where concrete syntax comes to the rescue.