1.md

Part 1: parsing

The language we are making is an interpreted one. This means that we basically need to implement two things: a parser and an evaluator. In this first part, we implement the parser.

The job of the parser is to convert the program into something the evaluator understands. The evaluator evaluates whatever the parser produces, and returns the result. Here is a nice diagram to explain everything:

            +-----------+        +-------------+
    text    |           |  AST   |             |  result
  +-------->|  parser   |+------>|  evaluator  |+-------->
            |           |        |             |
            +-----------+        +-------------+

The format produced by the parser is called the abstract syntax tree (AST) of the program.

Our AST

So what does our AST look like? Lets have a sneak peek.

import static net.saga.diy.lisp.parser.Parser.parse;
import static java.util.Arrays.deepToString;
class DIY {
    public static void main (Strings args[]) {
        Object[] ast = (Object[])parse(" (define my-fn\n"
                    + ";; A meaningless, but recursive, function\n"
                    + "(lambda (x)\n"
                    + "(if (eq x 0)\n"
                    + "42\n"
                    + "(my-fn (- x 1)))))");
        System.out.println(deepToString(program));
    }
}

java DIY

[define, my-fn, [lambda, [x], [if, [eq, x, 0], 42, [my-fn, [-, x, 1]]]]]

The AST, then, is created as follows:

• Comments are removed.
• Symbols are represented as strings.
  • "foo" parses to "foo"
• The symbols #t and #f are represented by Java's true and false, respectively.
  • "#t" parses to frue
• Integers are represented as Java integers.
  • "42" parses to 42
• The Lisp list expressions are represented as Java Object arrays. "(foo #f 100)" parses to ["foo", False, 100]
• Nested expressions are parsed accordingly.
  • "((+ (- 1 2) (* (- 4 1) 42)))" parses to [['+', ['-', 1, 2], ['*', ['-', 4, 1], 42]]]

Your turn

The parsing is done in Parser.java. It is your job to implement the parse function here. A lot of the gritty work of counting parentheses and such has been done for you, but you must stitch everything together.

• Have a look at the provided functions in Parser.java before you start. These should prove useful.

• The following command runs the tests.

  mvn -Dtest=ParserTest test

• Run the tests and hack away until the tests are passing. Each test has a description, and you should probably read it if you get stuck.

What's next?

Go to part 2 where we evaluate some simple expressions.