CS 5010: Problem Set 10

Problem Specification

You will write an interpreter for a simple functional programming language with this concrete syntax:

    <pgm>     ::=  <defn> ;
              ::=  <defn> ; <pgm>
    <defn>    ::=  <id> = <const>
              ::=  <id> (<formals>) <expr>
    <const>   ::=  true 
              ::=  false
              ::=  <int>
    <lambda>  ::=  (λ ( <formals> ) <expr>)
    <expr>    ::=  <const>
              ::=  <id>
              ::=  <lambda>
              ::=  <arith>
              ::=  <call>
              ::=  <if>
              ::=  ( <expr> )
    <arith>   ::=  <expr> <op> <expr>
    <call>    ::=  <expr> (<exprs>)
    <if>      ::=  if <expr> then <expr> else <expr> fi
    
    <op>      ::=  < | = | > | + | - | *
    
    <formals>  ::=  <id>
               ::=  <id> , <formals>
    <exprs>    ::=  <expr>
               ::=  <expr> , <exprs>
    
    <int> and <id> are described by regular expressions:
    
        digit digit*
    
        letter (letter | digit)*
  

That concrete syntax may be easy for humans to read, but it is not a convenient representation for compilers or interpreters. Compilers and interpreters generally use a more convenient internal representation known as abstract syntax trees. (Abstract syntax trees are closely related to the list representation of programs used in Lisp/Scheme/Racket/Clojure, and to the XML notation used to represent more general kinds of data.)

For the programming language above, we need abstract syntax trees for programs, definitions, and expressions. There are six different kinds of expressions, so we need six different kinds of abstract syntax trees for expressions. That gives us the following conceptual hierarchy:

    Ast
        Pgm
        Def
        Exp
            ConstantExp
            IdentifierExp
            LambdaExp
            ArithmeticExp
            CallExp
            IfExp
  

We will represent the abstract syntax tree for a program as a List<Def>. All of the other categories within that hierarchy will be represented by the Java interfaces shown below. To save you from having to copy and paste those interfaces, we are giving you the Java source files as a gzip'ed tar file, set10.tgz. When you unpack that file, it will expand into a set10 directory that already contains the following Java source files.

Abstract Syntax Trees

The Ast.java file:

    // An Ast is an object of any class that implements the Ast interface.
    //
    // Interpretation: An Ast represents the abstract syntax tree
    // for some part of a source program.
    //
    // This abstract data type simplies the parser,
    // but should not be used by the type checker or interpreter.
    
    import java.util.List;
    
    interface Ast {
    
        // Returns true iff this Ast is for a program, definition,
        // or expression, respectively
    
        boolean isPgm();
        boolean isDef();
        boolean isExp();
    
        // Precondition: this Ast is for a program.
        // Returns a representation of that program.
    
        List<Def> asPgm();
    
        // Precondition: this Ast is for a definition.
        // Returns a representation of that definition.
    
        Def asDef();
    
        // Precondition: this Ast is for an expression.
        // Returns a representation of that expression.
    
        Exp asExp();
    }
  

Definitions

The Def.java file:

    // A Def is an object of any class that implements the Def interface.
    //
    // Interpretation: A Def represents one definition of the source program.
    
    interface Def extends Ast {
    
        // Returns the left hand side of this definition,
        // which will be an identifier represented as a String.
    
        String lhs();
    
        // Returns the right hand side of this definition,
        // which will be a ConstantExp or a LambdaExp.
    
        Exp rhs();
    }
  

Expressions

The Exp.java file:

    // An Exp is an object of any class that implements the Exp interface.
    //
    // Interpretation: An Exp represents an expression of a source program.
    
    import java.util.Map;
    
    interface Exp extends Ast {
    
        // Returns true iff this Exp is a constant, identifier,
        // lambda, arithmetic, call, or if expression (respectively).
    
        boolean isConstant();
        boolean isIdentifier();
        boolean isLambda();
        boolean isArithmetic();
        boolean isCall();
        boolean isIf();
    
        // Precondition: the corresponding predicate above is true.
        // Returns this.
        // (These methods amount should eliminate most casts.)
    
        ConstantExp   asConstant();
        IdentifierExp asIdentifier();
        LambdaExp     asLambda();
        ArithmeticExp asArithmetic();
        CallExp       asCall();
        IfExp         asIf();
    
        // Returns the value of this expression when its free variables
        //     have the values associated with them in the given Map.
        // May run forever if this expression has no value.
        // May throw a RuntimeException if some free variable of this
        //     expression is not a key of the given Map or if a type
        //     error is encountered during computation of the value.
    
        ExpVal value (Map<String,ExpVal> env);
    }
  

The other *Exp.java files:

    // A ConstantExp is an object of any class that implements ConstantExp.
    //
    // Interpretation: A ConstantExp represents an identifier (or variable) integer or boolean constant.
    
    interface ConstantExp extends Exp {
    
        // Returns the value of this constant expression.
    
        ExpVal value();
    }
  

    // An IdentifierExp is an object of any class that implements IdentifierExp.
    //
    // Interpretation: A IdentifierExp represents an identifier (or variable).
    
    interface IdentifierExp extends Exp {
    
        // Returns the name of this identifier.
    
        String name();
    }
  

    // A LambdaExp is an object of any class that implements LambdaExp.
    //
    // Interpretation: A LambdaExp represents a lambda expression.
    
    import java.util.List;
    
    interface LambdaExp extends Exp {
    
        // Returns the formal parameters of this lambda expression.
    
        List<String> formals();
    
        // Returns the body of this lambda expression.
    
        Exp body();
    }
  

    // An ArithmeticExp is an object of any class that implements ArithmeticExp.
    //
    // Interpretation: An ArithmeticExp represents an expression of the form
    //
    //       
    
    interface ArithmeticExp extends Exp {
    
        // Returns the appropriate subexpression.
    
        Exp leftOperand();
        Exp rightOperand();
    
        // Returns the binary operation as one of the strings
        //     "LT"
        //     "EQ"
        //     "GT"
        //     "PLUS"
        //     "MINUS"
        //     "TIMES"
    
        String operation();
    }
  

    // A CallExp is an object of any class that implements CallExp.
    //
    // Interpretation: A CallExp represents a function call.
    
    import java.util.List;
    
    interface CallExp extends Exp {
    
        // Returns the expression for the function part of the call.
    
        Exp operator();
    
        // Returns the list of argument expressions.
    
        List<Exp> arguments();
    }
  

    // An IfExp is an object of any class that implements IfExp.
    //
    // Interpretation: An IfExp represents an if expression.
    
    interface IfExp extends Exp {
    
        // Returns the appropriate part of this if expression.
    
        Exp testPart();
        Exp thenPart();
        Exp elsePart();
    }
  

Expression Values

The value of an expression in this language will always be a boolean, integer, or function.

    // An ExpVal is an object of any class that implements the ExpVal interface.
    //
    // Interpretation: An ExpVal represents the value of an expression.
    
    interface ExpVal {
    
        // Returns true iff this ExpVal is a boolean, integer, or
        // function (respectively).
    
        boolean isBoolean();
        boolean isInteger();
        boolean isFunction();
    
        // Precondition: the corresponding predicate above is true.
        // Returns this.
        // (These methods amount should eliminate most casts.)
    
        boolean asBoolean();
        long asInteger();
        FunVal asFunction();
    }
  

    // A FunVal is an object of any class that implements the FunVal interface.
    //
    // Interpretation: A FunVal represents the value of a lambda expression.
    
    import java.util.Map;
    
    interface FunVal extends ExpVal {
    
        // Returns the lambda expression from which this function was created.
    
        LambdaExp code();
    
        // Returns the environment that maps the free variables of that
        // lambda expression to their values.
    
        Map<String,ExpVal> environment();
    }
  

---

We have divided that problem into two parts. In the first part, you will implement the abstract data types for definitions, expressions, and expression values, and define a public class that defines public static factory methods for those types. In the second part, you will define a public class that defines a public static method for running any given program of the language on any given inputs.

1. Download and unpack the set10.tgz file we are giving you.

   Inside that set10 directory, define another file named Asts.java that defines a class named Asts that defines the following public static methods:

           // Static factory methods for Def
           
           // Returns a Def with the given left and right hand sides.
           
           public static Def def (String id1, Exp rhs) { ... }
           
           // Static factory methods for Exp
           
           // Returns an ArithmeticExp representing e1 op e2.
           
           public static ArithmeticExp arithmeticExp (Exp e1, String op, Exp e2) { ... }
           
           // Returns a CallExp with the given operator and operand expressions.
           
           public static CallExp callExp (Exp operator, List<Exp> operands) { ... }
           
           // Returns a ConstantExp with the given value.
           
           public static ConstantExp constantExp (ExpVal value) { ... }
           
           // Returns an IdentifierExp with the given identifier name.
           
           public static IdentifierExp identifierExp (String id) { ... }
           
           // Returns an IfExp with the given components.
           
           public static IfExp ifExp (Exp testPart, Exp thenPart, Exp elsePart) { ... }
           
           // Returns a LambdaExp with the given formals and body.
           
           public static LambdaExp lambdaExp (List<String> formals, Exp body) { ... }
           
           // Static factory methods for ExpVal
           
           // Returns a value encapsulating the given boolean.
           
           public static ExpVal expVal (boolean b) { ... }
           
           // Returns a value encapsulating the given (long) integer.
           
           public static ExpVal expVal (long n) { ... }
           
           // Returns a value encapsulating the given lambda expression
           // and environment.
           
           public static FunVal expVal (LambdaExp exp, Map<String,ExpVal> env) { ... }
           
           // Static methods for creating short lists
           
           public static <X> List<X> list (X x1) { ... }
           
           public static <X> List<X> list (X x1, X x2) { ... }
           
           public static <X> List<X> list (X x1, X x2, X x3) { ... }
           
           public static <X> List<X> list (X x1, X x2, X x3, X x4) { ... }
         

2. Inside your set10 directory, include another file named Programs.java that defines a Programs class that defines the following public static method:

           public static ExpVal run (List<Def> pgm, List<ExpVal> inputs) {
               ...
           }
         

   Here is an example, which should print 120:

           // fact (n) if n = 0 then 1 else n * fact (n - 1) fi
           
           Exp exp1
               = Asts.arithmeticExp (Asts.identifierExp ("n"),
                                     "MINUS",
                                     Asts.constantExp (Asts.expVal (1)));
           Exp call1
               = Asts.callExp (Asts.identifierExp ("fact"),
                               Asts.list (exp1));
           Exp testPart
               = Asts.arithmeticExp (Asts.identifierExp ("n"),
                                     "EQ",
                                     Asts.constantExp (Asts.expVal (0)));
           Exp thenPart
               = Asts.constantExp (Asts.expVal (1));
           Exp elsePart
               = Asts.arithmeticExp (Asts.identifierExp ("n"),
                                     "TIMES",
                                     call1);
           Def def1
               = Asts.def ("fact",
                           Asts.lambdaExp (Asts.list ("n"),
                                           Asts.ifExp (testPart,
                                                       thenPart,
                                                       elsePart)));
           ExpVal result = Programs.run (Asts.list (def1),
                                         Asts.list (Asts.expVal (5)));
           System.out.println (result.asInteger());