Skip to content

README.md

Latest commit

 

History

History
219 lines (157 loc) · 10.7 KB

README.md

File metadata and controls

219 lines (157 loc) · 10.7 KB

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

Both phases are implemented. Phase 1 provides the core interpreter (arithmetic, comparisons, conditionals, let). Phase 2 adds first-class functions, a standard library, and an interactive REPL with file loading.

What works today

  • ✅ Tokenizer -- breaks source strings into tokens, handles whitespace, comments, negative literals
  • ✅ Recursive-descent parser -- builds an AST from all supported forms
  • ✅ Tree-walking evaluator -- integer literals, arithmetic (+, -, *), comparisons (<, =, >), if conditionals, let bindings with lexical scoping
  • ✅ Environment-based variable resolution with proper shadowing
  • ✅ lambda expressions and lexical closures
  • ✅ Function application (App node) with automatic partial application for built-ins
  • ✅ define for top-level bindings
  • ✅ closure, builtin, and list value types
  • ✅ Standard library built-ins (sum, cumsum, range, filtermap, map, filter, find, length, depth, nat+, nat->int, int->nat)
  • ✅ Pretty printing of closures, built-ins, and lists
  • ✅ Interactive REPL with :load and :quit commands
  • ✅ .mml file loading from the command line or from the REPL
  • ✅ Example programs in examples/

Running it

npm install
npx tsc
node dist/miniml.js                       # start the REPL
node dist/miniml.js examples/closures.mml # load a file then drop into the REPL

In the REPL:

miniml> (+ 1 (* 2 3))
7
miniml> (define add (lambda (x) (lambda (y) (+ x y))))
defined add
miniml> ((add 3) 4)
7
miniml> (sum (range 1 1 100))
5050
miniml> :load examples/closures.mml
miniml> :quit

Language Features

MiniML supports:

  • 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

; 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

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

; Built-in over a range
(sum (range 1 1 100))  ; => 5050

; Higher-order functions on lists
(filtermap (lambda (x) (< x 5))
           (lambda (x) (* x x))
           (range 1 1 10))  ; => (1 4 9 16)

; Partial application of a built-in
(define myrange (range 1))
(myrange 1 10)         ; => (1 2 3 4 5 6 7 8 9 10)

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

  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), control flow (If, Let), and functions (Lambda, App, Define).

  3. Value and Environment Types - Value is a tagged union with num, bool, closure, builtin, and list 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 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, lambda, define) are recognized by keyword; any other head position is treated as function application.

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

  8. Apply helper - Dispatches closures vs. built-ins. Built-ins collect arguments one at a time and invoke when arity is satisfied (automatic partial application).

  9. Pretty printer - Prints values: numbers, booleans (#t/#f), <closure>, <builtin:name[k/n]>, and parenthesized list notation.

  10. Standard library - Wraps the helper functions as callable MiniML built-ins and seeds them into the initial environment.

  11. REPL and file loader - Interactive prompt with :load <file> and :quit commands. Files passed on the command line are loaded in order, then the REPL starts with those definitions in scope.

Key Design Decisions

S-expressions keep the tokenizer under 80 lines and the parser under 150. 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.

Automatic partial application for built-ins lets (range 1) return a new built-in still expecting two arguments, matching the currying model used by user-defined lambdas.

Getting Started

Prerequisites

  • Node.js (v14 or later)
  • npm

Setup

npm install
npx tsc
node dist/miniml.js

Standard Library Reference

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 (spacing, 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. When loading a file, a failing expression is reported but subsequent expressions still run.

Known Limitations

  • 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. Top-level define does not self-reference at definition time, so recursive functions require a fixpoint combinator.
  • 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.
  • Lists are produced only by built-ins. There is no literal list syntax in MiniML source; lists come from range, cumsum, map, filter, and filtermap.