MiniML

A tiny functional programming language implemented in TypeScript. MiniML uses S-expression syntax, a tree-walking interpreter, and lexical closures. It is built in two phases: a core interpreter that handles arithmetic, comparisons, conditionals, and let bindings, followed by first-class functions, a standard library, and an interactive REPL.

Motivation

This project grew out of a set of standalone TypeScript problems covering cumulative sums, linear search, Peano naturals, sequence generation, expression trees, environment-based evaluation, higher-order functions, and tree traversal. The problems were part of a set for a programming languages class. Each problem teaches an isolated concept, but real software rarely uses concepts in isolation.

A language interpreter is one of the few projects where all of these ideas have a natural home:

Problem	Concept	Role in MiniML
1 - Cumulative Sum	Array accumulation	cumsum and sum built-ins
2 - Linear Search	Indexed scan	Environment lookup algorithm
3 - Peano Naturals	Recursive data, base/recursive cases	nat+, nat->int, int->nat built-ins
4 - Sequence Generator	Loop-based generation	range built-in
6a - Expression Types	Class hierarchies, instanceof	The AST node classes
7a - Variable Expressions	Extending a type hierarchy	Var node for variable references
8 - Filter Map	Higher-order functions, generics	filtermap, map, filter built-ins
10 - Max Tree Depth	Recursive tree traversal	depth built-in

Problems 5 (string append map), 6b (expression evaluator), 7b (environment evaluator), and 9 (closures/makesay) informed the design but are not included as standalone functions. Their concepts are demonstrated directly by the interpreter itself: the evaluator generalizes Problems 6b and 7b, and lambda evaluation generalizes the closure pattern from Problem 9.

Current Status

The project is built in two phases. Phase 1 (the core interpreter) is implemented and working. Phase 2 (functions, standard library, REPL) is not yet started.

What works today

• ✅ Tokenizer -- breaks source strings into tokens, handles whitespace, comments, negative literals
• ✅ Recursive-descent parser -- builds an AST from tokens for all Phase 1 forms
• ✅ Tree-walking evaluator -- integer literals, arithmetic (+, -, *), comparisons (<, =, >), if conditionals, let bindings with lexical scoping
• ✅ Environment-based variable resolution with proper shadowing
• ✅ Helper functions for the future standard library (cumulative_sum, search, add/to_int/from_int, sequence, filtermap, maxdepth)
• ✅ Test harness that runs verification expressions and prints results

What does not work yet

• ✗ lambda expressions and closures
• ✗ Function application (App node)
• ✗ define for top-level bindings
• ✗ closure, builtin, and list value types
• ✗ The apply helper and partial application
• ✗ Standard library built-ins (sum, range, filtermap, etc.)
• ✗ Pretty printing of closures and lists
• ✗ REPL and file loading
• ✗ Example .mml program files

Running the current build

npm install
npx tsc
node dist/miniml.js

This runs the Phase 1 test harness and prints:

42  =>  42
(+ 1 2)  =>  3
(+ 1 (* 2 3))  =>  7
(- 10 3)  =>  7
(< 3 5)  =>  #t
(> 3 5)  =>  #f
(= 3 3)  =>  #t
(if (< 3 5) 1 0)  =>  1
(let x 10 (+ x 5))  =>  15
(let x 10 (if (< x 5) 1 2))  =>  2
(let a 3 (let b 4 (+ a b)))  =>  7

Language Features

When complete, MiniML will support:

• Integer literals and arithmetic (+, -, *)
• Comparisons (<, =, >) producing booleans
• if conditionals with then/else branches
• let bindings with lexical scoping and shadowing
• lambda expressions with single parameters (multi-argument via currying)
• Function application with automatic currying for built-ins
• define for top-level bindings in the REPL and files
• Comments starting with ;

Example Programs

Expressions that work now:

; Basic arithmetic
(+ 1 (* 2 3))          ; => 7

; Let bindings with variable shadowing
(let x 10
  (let y (+ x 3)
    (if (< y 15) (* y 2) 0)))  ; => 26

; Nested lets with all bindings in scope
(let a 3 (let b 4 (+ a b)))    ; => 7

Expressions that will work after Phase 2:

; Curried addition
(define add (lambda (x) (lambda (y) (+ x y))))
((add 3) 4)            ; => 7

; Higher-order functions on lists
(sum (range 1 1 100))  ; => 5050

(filtermap (lambda (x) (< x 5))
           (lambda (x) (* x x))
           (range 1 1 10))  ; => (1 4 9 16)

Architecture

The entire interpreter lives in a single file, miniml.ts, organized into sections that depend only on sections above them.

Data Flow

Source string --> tokenize() --> Token[] --> parse() --> Expr --> evaluateExpr() --> Value --> printValue() --> string

Sections (current)

1. Type Definitions - Peano naturals (Succ, Nat) and binary trees (TLeaf, TNode, Tree) used by helper functions and built-ins.

2. AST Node Definitions - A class hierarchy rooted at Expr. Leaf nodes (Literal, Var), binary operators (Plus, Minus, Mul, LessThan, Equals, GreaterThan), and control flow (If, Let).

3. Value and Environment Types - Value is a tagged union with num and bool variants. Env is an association list ([string, Value][]) where lookup scans front-to-back so newer bindings shadow older ones.

4. Helper Functions - Problem-set functions that will back the standard library: cumulative_sum, search, add/to_int/from_int, sequence, filtermap, maxdepth.

5. Tokenizer - Converts a source string into a flat array of tokens (lparen, rparen, number, symbol). Strips whitespace and comments.

6. Parser - Recursive-descent parser that converts tokens into an AST. Special forms (+, -, *, <, =, >, if, let) are recognized by keyword.

7. Evaluator - Tree-walking evaluator (evaluateExpr) that recurses over the AST, threading an environment through let bindings.

8. Main Harness - Test driver that runs verification expressions through the full pipeline and prints results.

Sections (planned for Phase 2)

Phase 2 will add the following to the existing file:

• AST nodes for Lambda, App, and Define
• Value variants for closure, builtin, and list
• Parser branches for lambda, define, and function application (the fallback case)
• Evaluator branches for Lambda (creates closures) and App (calls apply)
• Apply helper that dispatches closures vs. built-ins with automatic partial application
• Pretty printer extended for closures, built-ins, and list notation
• Standard library wrapping the helper functions as callable MiniML built-ins
• REPL and file loader with :load and :quit commands
• The main harness will be replaced by the REPL entry point

Key Design Decisions

S-expressions keep the tokenizer under 50 lines and the parser under 100. An infix parser with operator precedence would be several times larger for identical semantics.

Tagged unions for values make the evaluator's type checks explicit. Each branch of the instanceof chain handles one case, mirroring pattern matching in functional languages.

Association-list environments are the simplest scoping representation. Prepend to shadow, scan to look up. This makes the scoping model transparent and easy to debug.

Single-argument lambdas avoid multi-argument parsing complexity. The tradeoff is verbosity, but it makes closure semantics maximally clear: each application extends the environment by exactly one binding.

Getting Started

Prerequisites

• Node.js (v14 or later)
• npm

Setup

npm install
npx tsc
node dist/miniml.js

See Current Status for what to expect from the output.

Standard Library Reference (Phase 2)

Built-in	Arity	Description
sum	1	Sum of a number list
cumsum	1	Running totals of a number list
find	2	Index of first occurrence, or -1
range	3	Arithmetic progression (step, low, high)
filtermap	3	Filter then map in one pass
map	2	Apply function to each element
filter	2	Keep elements passing a predicate
length	1	Number of elements in a list
nat+	2	Addition via Peano naturals
nat->int	1	Peano natural to integer
int->nat	1	Integer to Peano natural
depth	1	Max depth of a nested list as a tree
true	-	Boolean constant
false	-	Boolean constant

All multi-argument built-ins support partial application. (range 1) returns a function that still needs two arguments.

Project Structure

Project4/
  miniml.ts        -- single-file implementation
  tsconfig.json    -- TypeScript compiler configuration
  package.json     -- project metadata and dependencies
  examples/        -- example .mml programs

Error Handling

MiniML reports errors at two levels:

• Parse errors identify the token position where parsing failed (missing parentheses, unexpected tokens, malformed special forms).
• Runtime errors identify the specific type violation (arithmetic on non-numbers, unbound variables, applying a non-function, if condition not a boolean).

Errors in the REPL are caught and printed without terminating the session.

Known Limitations

These are constraints of the current implementation or deliberate design tradeoffs.

Not yet implemented (Phase 2)

• No functions. lambda, function application, and closures are not yet supported. You cannot define or call functions.
• No REPL. The program runs a fixed set of test expressions and exits. There is no interactive prompt.
• No file loading. The :load command and .mml file support do not exist yet.
• No standard library. Built-in functions like sum, range, and filtermap are not wired in. The underlying helper functions exist in TypeScript but are not yet exposed to MiniML programs.
• No lists. The list value type and parenthesized list notation are not implemented.
• No define. Top-level bindings require nested let expressions.
• No partial application. Multi-argument built-ins cannot be partially applied.

By design

• Single-argument lambdas only. Multi-argument functions must be written as nested lambdas (currying). This is a deliberate simplification that keeps closure semantics explicit.
• No strings. MiniML has integers and booleans. There is no string type or string operations.
• No mutation. All bindings are immutable. There are no assignment operators or mutable references.
• No recursion without workarounds. There is no letrec or named recursion. Recursive functions require a fixpoint combinator, which is possible but verbose.
• No tail-call optimization. Deeply recursive programs will overflow the JavaScript call stack.
• No static type checking. Type errors (such as (+ true 3)) are caught at runtime, not at parse time. The AST accepts any Expr in any position.
• Linear environment lookup. Variable resolution scans the association list front-to-back. This is O(n) per lookup, which is fine for small programs but would not scale to thousands of bindings.