Recommendations for solving lab 2 with Java

Pattern matching with switch

The stub for lab 2 uses recent Java features (available since Java 17), which admits a more readable alternative to the visitor pattern suggested in the book.
The following example code shows how you can process an object exp of the type Exp generated by the parser defined in the stub.

switch(exp) {
    case EInt    e -> ... ;  
    case EDouble e -> ... ;  
    case EAnd    e -> ... ;  
    case EOr    e -> ... ;  
    ...  
    default -> throw new IllegalStateException("Case for " + e + " is not yet implemented.");  
}

On the right hand side of the -> you can extract further information from e, for example, in the case EAnd e, you can use the two operands e.exp_1 and e.exp_2.

switch, if used like above, produces a Java-expression, which means that you can use it in assignments:

var typedExpression = switch(exp) { ... }

Note that switch can also be used as a Java statement, like if.

Type-annotated syntax trees

The stub provides interface Annotated.java as a template for the type-annotated syntax. (It does not contain the type-annotations yet, to add them is your task.) Annotated.java uses recent Java features to encode abstract syntax in a more lightweight way compared to the class hierarchy produced by BNFC (which you can find in package cmm.Absyn).

In the following, we review these features per example.

Records and (sealed) interfaces

To define the neccessary datatypes, records are very useful. You can define a record like this:

record TypedAnd(TypedExpr e1, TypedExpr e2) {
}

Objects of this type can be constructed with new TypedAnd(e1,e2) where e1 and e2 are TypedExprs. For solving the lab, it is reasonable to define an interface TypedExpr with a method which returns the type of an expression:

interface TypedExpr {
  Type type();  
}

Where Type is a datatype for types that needs to be defined. With this interface, the TypedAnd from above can be turned into an implementation like this:

record TypedAnd(TypedExpr e1, TypedExpr e2) {
  Type type() {
    return new Type.Bool; // this is what it could look like if you implement basic types as an enum
  }
}

To keep a good overview, you can write implementations of an interface directly into the interface as "inner classes":

interface TypedExpr {
  Type type();  

  record And(TypedExpr e1, TypedExpr e2) implements TypedExpr {
    Type type() {
      return new Type.Bool;  
  }

  record Var(String name, Type type) implements TypedExpr { }
}

The second record Var shows a handy shortcut to overriding the method type: if the record has an attribute of the right Type and name ("type" in this case), it will automotically become the implementation.

You can work with a variable of type TypedExpr like in the example above, by using switch expressions. If you want to avoid the default case, you can use a sealed interface instead. To make that work, you have to declare all implementations inside the interface (or use permits):

sealed interface TypedExpr {
  Type type();  

  record And(TypedExpr e1, TypedExpr e2) implements TypedExpr {
    Type type() {
      return new Type.Bool;  
  }

  record Var(String name, Type type) implements TypedExpr { }
}

Method used in Annotated.java

The file Annotated.java defines a template of the abstract syntax in a single interface Annotated. It contains one type for each of the syntactic categories.
Categories that just have one form are represented as a record, e.g. Program, Def, and Arg.
Categories that have several constructors, such as Stm and Exp, are represented as sealed interface with each of their constructor represented as record.
Simple categories that just have atomic constructors are represented as enum, e.g. the operator categories IncDecOp, MulOp, AddOp and CmpOp.

Records and interfaces are accessed qualified, e.g., Annotated.Exp and Annotated.EAnd.
Constructors of enums are additionally qualified by their type, e.g. Annotated.IncDecOp.OInc.

Getting started on the type checker

This is just one way to start and the ideas given are not complete - be prepared to change everything along the way to a solution that passes all tests. To get started, here is a possible first try at an implementation of the typecheck function in the TypeChecker:

    public Annotated.Program typecheck(Program p) {
        var funDefs = ((PDefs) p).listdef_.stream()
                .map(def -> (DFun) def)
                .toList();  
        signatures = new HashMap<>();  
        extractSignatures(funDefs);  
        return new Annotated.Program(checkFunDefs(funDefs));  
    }

The first statement extracts a list of function definitions from (the parse-tree) p and stores it in funDefs. The var means that the type of funDefs is automatically infered. Then the signatures, which are stored in a field in the TypeChecker class, are initialized. To make the last line of this functions work, the type Annotated.Program was modified in the following way (the functions extractSignatures and checkFunDefs will be explained below):

interface Annotated {

    record Program(Map<String, Def> defs) { }
    ...  
}

A Type from the parser syntax (in cmm.Absyn) can then be translated to a Annotated.Type like this (where this function definition could for example be put into TypeChecker):

    Annotated.Type typeFrom(Type type) {
    return switch(type) {
        case Type_int p -> Annotated.Type.Type_int;  
        // TODO: other cases
        default -> throw new IllegalStateException("Unexpected value: " + type);  
    };  
    }

Now, we'll get back to the functions we left unexplained above, extractSignatures and checkFunDefs. As the name suggests, extractSignatures should pass through all function definitions and extract their signatures, which we will need to check the actual function defintions. This is a possible implementaion:

    void extractSignatures(List<DFun> funDefs) {
        for(var def : funDefs) {
            List<Annotated.Type> argTypes = def.listarg_.stream()
                    .map(arg -> typeFrom(((ADecl) arg).type_))
                    .toList();  
            Signature signature = new Signature(typeFrom(def.type_), argTypes);  
            if(signatures.put(def.id_, signature) != null) {
                throw new TypeException("Signature already defined for " + def.id_);  
            };  
        }
    }

One thing that could be added here (or somewhere else) is, that there should be exactly one function called "main" which returns int and has no arguments. We will only give a sketch of an implementation of checkFunDefs. One thing to take care of is dealing with contexts in the right way, which needs some data structure like a stack or list. This is not explained in detail here:

    HashMap<String, Annotated.Def> checkFunDefs(List<DFun> funDefs) {
        var checkedFunDefs = new HashMap<String, Annotated.Def>();  
        for(var funDef : funDefs) {
        // TODO: produce 'args' which should be a list of argument names with their types
        // TODO: produce 'contexts' which should be some datastructure storing types of declared variables
            Annotated.Def checkedFunDef =
              new Annotated.Def(typeFrom(funDef.type_),  
                                args,  
                                checkStms(funDef.liststm_, contexts));  
            if(checkedFunDefs.put(funDef.id_, checkedFunDef) != null) {
                throw new TypeException("Function " + funDef.id_ + " already defined!");  
            }
        }
        return checkedFunDefs;  
    }

Getting started on the interpreter

Now we will give an oversimplified sketch of the interpreter. All the functions below should still be changed to solve lab 2. We will also give a start for an implementation of Value as an interface below and we will assume the Interpreter has a field env which stores the environment(s).

    void interpret(Annotated.Program p) {
        defs = p.defs();  
        if (!defs.containsKey("main")) {
            throw new RuntimeException("Main function not found");  
        }
        runFunction(defs.get("main")); // TODO: deal with arguments...  
    }

    // TODO: Extends to functions with arguments
    Value runFunction(Annotated.Def f) {
        // TODO: 'env', used in the following should be a field of the Interpreter,  
        // which should open a new block at this point, with the arguments from the function call
        for (var s : f.liststm_()) {
            run(s, env);  
        }
        // TODO: proper return value
        return new Value.Void();  
    }

    void run(Annotated.Stm s) {
        switch (s) {
            case Annotated.Stm.SInit decl -> {
                env.addVar(decl.id_(), new Value.Void());  
                env.updateVar(decl.id_, evalExpr(decl.exp_()));  
            }
            case Annotated.Stm.SExp expr -> {
                var v = evalExpr(expr.exp_());  
            }
        }
    }

Expressions can be evaluated like this:

    Value evalExpr(Annotated.Exp expr) {
        return switch(expr) {
            case Annotated.EInt anInt  -> new Value.Int(anInt.integer_());  
            case Annotated.EId  var    -> env.getVar(var.id_());  
            case Annotated.EAss assign -> // TODO: evaluate assingment, update environment;  
            case Annotated.EApp app    -> // TODO: run a function;  
        };  
    }

Here is a start for the value datatypes:

sealed interface Value {
    record Int(Integer i) implements Value {}
    record Void() implements Value {}
}