Makevisitors: What it does and how it works

Translating Haskell code to Java code

To demonstrate how to translate Haskell code to Java code, we will use a running example throughout this assignment: arithmetic expressions.

Here is our (by now, familiar) Haskell AST for expressions:

  data Op = Plus | Minus | Times | Divide

  data Expr = Value Integer
            | BinOp Op Expr Expr

Important Aside: Haskell records

Until now, we have not given names to our associated values in Haskell. For example, in our Expr data type above, when we declare the BinOp tag, we describe only the types of its three associated values:

  BinOp Op Expr Expr

However, Haskell supports records, which allows us to give names for the associated values, like so:

  BinOp {operator :: Op, leftOperand :: Expr, rightOperand :: Expr}

For this assignment, makevisitors will translate a Haskell declaration only if:

  • None of the data type’s tags have associated values (as with Op in the example above), or
  • All of the tags that have associated values use records.

The reason for this restriction is that it is much easier to generate Java code (which requires fields to have names) if we use record syntax.

Given this restriction, our Expr data type now looks like this:

  data Op = Plus | Minus | Times | Divide

  data Expr = Value {value :: Integer}
            | BinOp {operator :: Op, leftOperand :: Expr, rightOperand :: Expr}

The key thing to remember is that all associated values must be named, using record syntax.

From Haskell to Java

First, a couple of definitions:

  • a simple data type is one where none of its tags have associated values.
  • a complex data type is one where at least one of its tags has an associated value. In our Expr example, Op is simple, and Expr is complex.

The following picture shows how our Haskell example translates to Java. More details follow the image.

translating Haskell to Java

To create Java code from Haskell, we need to do the following:

  • Translate each simple type to a Java enum. The name of the enum matches the name of the Haskell data type. The enum values will be capitalized versions of the Haskell tags.
  • Translate each complex type T in the following way:
    • Create a visitor interface for the data type. The name of the visitor is TVisitor, where T is the name of the data type. For each tag the visitor declares a public method visitTag, where Tag matches the name of the tag. The method takes an argument of type Tag and returns void.
    • Create an abstract base class for the data type. The name of the abstract class matches the name of the Haskell data type. The abstract class should declare a public abstract accept method that takes a TVistor and returns void.
    • For each tag, create a concrete class. The name of the class matches the name of the tag. The concrete class extends the abstract class. For each associated value, the concrete class declares a field. (The name of the field is field_, where field is the name of the associated value in Haskell. The type of the field matches the Java equivalent of the Haskell type.) The concrete class declares a constructor that initializes the field values. The concrete class implements the accept method, as required by the visitor pattern.

Additionally, we need to create a Java package and import some Java libraries to be able to support Maybes and tuple types. Here is all the generated code for the Expr example.

Automatically translating from Haskell code to Java code

As you might have guessed, it is somewhat tedious to translate even a relatively simple Haskell data type to its Java equivalent.

This is a perfect scenario for metaprogramming! Rather than write new Java code by hand for each different Haskell file, we write one program (makevisitors) that generates Java code for any and all Haskell files. We call this “meta”programming because we are writing a program whose output is another program.

makevisitors

As a reminder, the makevisitors program automatically translates Haskell data types to equivalent Java classes. Furthermore, the Java code supports the visitor pattern, so that people can add new operations, without modifying the generated Java code.

To do its work, makevisitors performs the following steps:

  1. Read the Haskell data type specification from a text file (already implemented!);

  2. Parse the Haskell into our Haskell AST (already implemented!);

  3. Using the Haskell AST, generate the equivalent Java AST, making multiple passes over the data type representation if necessary (this is the part you will implement);

  4. Render the Java-code representation to a Doc, a library type for pretty-printed text (already implemented!);

  5. Write out the text of the Doc (already implemented!).

The straightforward not-so-interesting code has already been written. Your job is to finish the fun part (step 3). Whereas the example at the top of this page showed how to translate Haskell concrete syntax to Java concrete syntax, the code you write will translate from Haskell abstract syntax to Java abstract syntax.

Automatically translating from Haskell AST to Java AST

The interesting work for this assignment is to write a translator from Haskell AST to Java AST. The makevisitors program breaks this task down by performing multiple traversals (also called “passes”) over the Haskell AST. Each pass generates a particular kind of Java AST:

  • Pass 1: For each simple Haskell data type, generate a Java enum.
  • Pass 2: For each complex Haskell data type, generate a Java visitor interface.
  • Pass 3: For each complex Haskell data type, generate an abstract class.
  • Pass 4: For each case of a complex data type, generate a concrete class.