One of the first things I do when I define the syntax for a new language is implement a formatter — code to produce a textual representation of expressions in the language. Humans are intensely visual, so having a way to look at the structures you are constructing in code is a great way of aiding understanding. Further, since this a programming language we’re creating, the ability to print expressions is necessary for the interpreter. If you haven’t read yesterday’s post and are unfamiliar with the lambda calculus, I recommend reading it before proceeding.

Formatting

The interface our formatter needs to implement is as follows: given an OutputStream, output a string representation of the given ASTNode.

/**
 * Format the given {@code ASTNode}, outputting to the given {@code OutputStream}. All character
 * data is formatted to {@code out} using the {@link Charset} this object was constructed with.
 * @param out  The {@code OutputStream} to format {@code root} to.
 * @param root The {@code ASTNode} to format.
 * @throws IOException if {@code out} had an issue being written to.
 */
public abstract void format(final OutputStream out, final ASTNode root) throws IOException;

/src/alonzo/ast/fmt/Formatter.java

Formatting Var

Remember that the definition of a variable (Var) is a sequence of characters, not including the punctuation used for other expression types:

<var> ::= [^()λ. ]+

The test for our formatter is likewise simple. When we have a variable containing a name, the string representation should just be the name. For now, ignore that we’re testing 2 different formatters here, this post only concerns the recursive formatter.

@Test
public void fmtVar() {
    final Var v = new Var("testVariableName");

    assertEquals("testVariableName", iterFmt.format(v));
    assertEquals("testVariableName", recFmt.format(v));
}

/tst/alonzo/ast/fmt/FormatterTest.java

Given the quite simple definition of Var, formatting it is a one-liner:

if (root instanceof Var) {
    out.write(bytes(((Var) root).name()));
}

/src/alonzo/ast/fmt/RecursiveFormatter.java

Formatting Fun

Formatting functions is a bit more tricky than formatting variables. Notice the recursive definition of a function as being an expression that contains another expression:

<function-definition> ::= '(λ' <var> '.' <expr> ')'

But first, the test. Straightforward, as usual:

@Test
public void fmtFun() {
    final Fun f = new Fun(new Var("var"), new Var("body"));

    assertEquals("(λvar.body)", iterFmt.format(f));
    assertEquals("(λvar.body)", recFmt.format(f));
}

/tst/alonzo/ast/fmt/FormatterTest.java

The recursive definition of Fun makes defining the formatter in a recursive manner a really natural and intuitive choice. So, to format a function, we output the punctuation of the function, then recursively call format on the substructures: the parameter and the body of the function:

private void formatFun(final OutputStream out, final Fun fun) throws IOException {
    out.write(bytes("(λ"));
    format(out, fun.parameter());
    out.write(bytes("."));
    format(out, fun.body());
    out.write(bytes(")"));
}

/src/alonzo/ast/fmt/RecursiveFormatter.java

Formatting App

Function application (App) is formatted in much the same way function was. Again, App is recursively defined as being composed of other expressions:

<function-application> ::= '(' <expr> ' ' <expr> ')'

The test for formatting App makes use of all the other ASTNodes, asking the formatter to format an application of the identity function to a free variable y.

@Test
public void fmtApp() {
    final App a = new App(new Fun(new Var("x"), new Var("x")), new Var("y"));

    assertEquals("((λx.x) y)", iterFmt.format(a));
    assertEquals("((λx.x) y)", recFmt.format(a));
}

/tst/alonzo/ast/fmt/FormatterTest.java

The implementation is very similar to Fun, outputting the relevant punctuation, then recursively calling format on the function and argument substructures.

private void formatApp(final OutputStream out, final App app) throws IOException {
    out.write(bytes("("));
    format(out, app.function());
    out.write(bytes(" "));
    format(out, app.argument());
    out.write(bytes(")"));
}

/src/alonzo/ast/fmt/RecursiveFormatter.java

Putting It All Together

With all the pieces of RecursiveFormatter together, we can format arbitrarily complicated lambda calculus expressions. I’ve added a “complicated” test to the suite showing that our formatter can format the Y-combinator:

@Test
public void fmtComplicated() {
    final Fun sub = new Fun(new Var("x"), new App(new Var("f"), new App(new Var("x"), new Var("x"))));
    final Fun ycombinator = new Fun(new Var("f"), new App(sub, sub));

    assertEquals("(λf.((λx.(f (x x))) (λx.(f (x x)))))", iterFmt.format(ycombinator));
    assertEquals("(λf.((λx.(f (x x))) (λx.(f (x x)))))", recFmt.format(ycombinator));
}

/tst/alonzo/ast/fmt/FormatterTest.java

Next time on Alonzo: they taught you not to use recursion in Java; what to do when your stack gets blown?
Stay tuned to find out.