README.md

DIFF

A tiny interpreter in Elm that adds recursive difference expressions.

DIFF builds on CONST, where we established the basic source text → AST → value structure. Allowing an expression to contain other expressions introduces recursion across the grammar, AST, parser, and evaluator.

Read DIFF: Adding Recursive Expressions to a Tiny Interpreter in Elm for a guided explanation of how it works.

flowchart TD
    A["-(2, -(4, 3))"] -->|parse| B["Program (Diff (Const 2) (Diff (Const 4) (Const 3)))"]
    B -->|evaluate| C["VNumber 1"]

Loading

Usage

You’ll need Nix with flakes enabled.

Enter the development environment and start the Elm REPL:

nix develop
elm repl

Import the interpreter and run a program:

import DIFF.Interpreter as I

I.run "-(456, 123)"
-- Ok (VNumber 333)

Language

DIFF supports non-negative integer constants:

123

and difference expressions:

-(456, 123)

A difference expression evaluates both of its operands and subtracts the value of the second from the value of the first.

Because each operand is itself an expression, difference expressions can be nested:

-(2, -(4, 3))

Recursive expressions

The grammar describes both operands of a difference expression as expressions:

Diff ::= '-' '(' Expr ',' Expr ')'

That recursive structure appears in the abstract syntax tree (AST):

Diff Expr Expr

The parser uses P.lazy to obtain the recursive expr parser when parsing reaches an operand, and the evaluator recursively evaluates both operands before applying subtraction.

The same recursive shape therefore appears in the grammar, AST, parser, and evaluator.

Tiny Interpreters

DIFF is part of Tiny Interpreters, where we learn how programming languages work by building tiny interpreters.