Recommendations for solving lab 2 with Java

The stub for lab 2 uses Java 21, 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) { ... }

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 implentations 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 { }
}

How to start

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 AnnotatedProgram typecheck(Program p) {
        var funDefs = ((PDefs) p).listdef_.stream()
                .map(def -> (DFun) def)
                .toList();  
        signatures = new HashMap<>();  
        extractSignatures(funDefs);  
        return new AnnotatedProgram(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 AnnotatedProgram) was modified to an inner record of the TypeChecker in the following way (the functions extractSignatures and checkFunDefs will be explained below):

    record AnnotatedProgram(Map<String, TypedFunDef> defs) { }

The type TypedFunDef is also defined as an inner record of TypeChecker:

    record TypedFunDef(CType returns, List<TypedArg> args, List<Statement> stms) { }
    record TypedArg(String name, CType type) { }

... and Statement and CType are defined in separate files:

sealed interface Statement {
  record Decl(String varName, CType type) implements Statement {}
  // TODO: add more records for all the statements we need in the typed syntax
}
enum CType {
    Int, Double, Bool, Void
}

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

    CType typeFrom(Type type) {
    return switch(type) {
        case Type_int ignored -> CType.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<CType> 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, TypedFunDef> checkFunDefs(List<DFun> funDefs) {
        var checkedFunDefs = new HashMap<String, TypedFunDef>();  
        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
            TypedFunDef checkedFunDef = new TypedFunDef(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;

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(TypeChecker.AnnotatedProgram 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(TypeChecker.TypedFunDef 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.stms()) {
            run(s, env);  
        }
        return new Value.Void();  
    }

    void run(Statement s) {
        switch (s) {
            case Statement.Decl decl -> env.addVar(decl.name(), decl.type());  
            case Statement.Expr expr -> evalExpr(expr.typedExpr());  
        };  
    }

Depending on how return statements are implemented, it might be reasonable to return more information here than just Values. For the following evaluation function for expressions, it should however be enough to return only a Value:

    Value evalExpr(TypedExpr expr) {
        return switch(expr) {
            case TypedExpr.Int anInt -> new Value.Int(anInt.i());  
            case TypedExpr.Var var -> env.getVar(var.id());  
            case TypedExpr.Assign assign -> // TODO: update environment;  
            case TypedExpr.App 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 {}
}