miniml.ts

// ============================================================
// MiniML — Core Interpreter
// ============================================================

import * as fs from "fs";
import * as readline from "readline";

// ============================================================
// Section 1: Problem-Set Type Definitions
// ============================================================

// Problem 3 — Peano naturals
class Succ{
    readonly n: Succ | undefined;
    constructor(n: Succ | undefined){
        this.n = n;
    }
}

type Nat = Succ | undefined;
const Zero: Nat = undefined;

// Tree types (Problem 10)
class Tleaf {};
class TNode{
    left: Tree;
    right: Tree;
    constructor(left: Tree, right: Tree){
        this.left = left;
        this.right = right;
    }
}

type Tree = Tleaf | TNode | undefined;

// ============================================================
// Section 2: MiniML AST Node Definitions
// ============================================================
// Base expression class (Problem 6a)
class Expr{};

// Leaf nodes
class Literal extends Expr{
    readonly value: number;
    constructor(value: number){
        super(); 
        this.value = value;
    }
}

class Var extends Expr{
    readonly name: string;
    constructor(name: string){
        super();
        this.name = name;
    }
}

// Arithmatic operators
class Plus extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

class Minus extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

class Mul extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

// Comparison operators
class LessThan extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

class GreaterThan extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

class Equals extends Expr{
    readonly left: Expr;
    readonly right: Expr;
    constructor(left: Expr, right: Expr){
        super();
        this.left = left;
        this.right = right;
    }
}

// Control flow
class If extends Expr{
    readonly cond: Expr;
    readonly then: Expr;
    readonly els: Expr;
    constructor(cond: Expr, then: Expr, els: Expr){
        super();
        this.cond = cond;
        this.then = then;
        this.els = els;
    }
}

class Let extends Expr{
    readonly name: string;
    readonly binding: Expr;
    readonly body: Expr;
    constructor(name: string, binding: Expr, body: Expr){
        super();
        this.name = name;
        this.binding = binding;
        this.body = body;
    }
}

// Functions (Phase 2)
// Lambda: (lambda (param) body) -- a single-parameter function definition.
// At eval time, produces a closure capturing the current environment.
class Lambda extends Expr{
    readonly param: string;
    readonly body: Expr;
    constructor(param: string, body: Expr){
        super();
        this.param = param;
        this.body = body;
    }
}

// Application: (fn arg) -- apply a function to an argument.
// The parser left-associates multiple args: (f a b) becomes App(App(f, a), b).
class App extends Expr{
    readonly fn: Expr;
    readonly arg: Expr;
    constructor(fn: Expr, arg: Expr){
        super();
        this.fn = fn;
        this.arg = arg;
    }
}

// Define: (define name expr) -- top-level binding for REPL and files.
// Unlike Let, has no body -- permanently extends the environment.
class Define extends Expr{
    readonly name: string;
    readonly binding: Expr
    constructor(name: string, binding: Expr){
        super();
        this.name = name;
        this.binding = binding;
    }
}

// ============================================================
// Section 3: MiniML Value and Environment Types
// ============================================================

// Tagged union for all runtime values.
// Phase 1: num, bool. Phase 2 adds: closure, builtin, list.
type Value =
    | {tag: "num"; value: number}              // integer result
    | {tag: "bool"; value: boolean}            // comparison result or if condition
    | { tag: "closure"; param: string; body: Expr; env: Env }  // lambda + captured environment
    | { tag: "builtin"; name: string; arity: number; args: Value[]; fn: (args: Value[]) => Value }  // TypeScript function with auto-currying
    | { tag: "list"; items: Value[] };         // list produced by builtins (range, map, etc.)

type Env = [string, Value][];

// ============================================================
// Section 4: Problem-Set Helper Functions
// ============================================================

// Computes running totals (prefix sums) of the input array.
// Each output[i] = sum of l[0..i]. Used as the "cumsum" built-in.
// Example: [12, 27, 13] → [12, 39, 52]
function cumulative_sum(lst: number[]): number[]{
    const result: number[] = [];
    let acc = 0;
    for(const x of lst){
        acc += x;
        result.push(acc);
    }

    return result;
}

// Linear search: returns the index of the first occurrence of n, or undefined.
// Same scan-from-front algorithm used by environment lookup in evalExpr.
// Example: search([1, 3, 5, 3, 1], 3) → 1
function search(lst: number[], n: number): number | undefined{
    for(let i = 0; i < lst.length; i++){
        if(lst[i] === n){
            return i;
        }
    }
    return undefined;
}

// Peano addition: moves Succ layers from x onto y one at a time.
// Base case: 0 + y = y. Recursive case: Succ(x') + y = Succ(x' + y).
// Example: add(Succ(Succ(undefined)), Succ(undefined)) → Succ(Succ(Succ(undefined))) (2+1=3)
function add(x: Nat, y: Nat): Nat{
    if(x === undefined){
        return y;
    }
    return new Succ(add(x.n, y));
}

// Converts a Peano natural to a JS integer by counting Succ layers.
// Iterative unwrapping: Succ(Succ(Succ(undefined))) → 3
function  to_int(x: Nat): number{
    let count = 0;
    while(x !== undefined){
        count++;
        x = x.n;
    }

    return count;
}

// Converts a JS integer to a Peano natural by wrapping x layers of Succ.
// Builds inside-out: from_int(3) → Succ(Succ(Succ(undefined)))
function from_int(x: number): Nat{
    let nat: Nat = undefined;
    for(let i = 0; i < x; i++){
        nat = new Succ(nat);
    }

    return nat;
}


// Generates an arithmetic progression: start at l, step by s, stop when > h.
// Exposed as the "range" built-in. Example: sequence(2, 1, 10) → [1, 3, 5, 7, 9]
function sequence(low: number, high: number, step: number): number[]{
    const result: number[] = [];
    let current = low;
    while(current <= high){
        result.push(current);
        current += step;
    }

    return result;
}

// Single-pass filter+map: keeps elements where filterf returns true, transforms them with mapf.
// Generic <T, U> allows different input and output types — essential for Phase 2 where T=U=Value.
// Example: filtermap(x => x > 2, x => x * x, [1,2,3,4]) → [9, 16]
function filtermap<T, U>(filterf: (v:T) => boolean, mapf: (v:T) => U, lst: T[]): U[]{
    const result: U[] = [];
    for(const x of lst){
        if(filterf(x)){
            result.push(mapf(x));
        }
    }

    return result;
}

// Computes the maximum depth of a binary tree by recurring into both children.
// Three cases: undefined (empty) → 0, TLeaf (terminal) → 1, TNode → 1 + max of children.
// Example: TNode(TLeaf, TNode(TLeaf, undefined)) → 3
function maxdepth(t: Tree): number{
    if(t === undefined){
        return 0;
    }else if(t instanceof Tleaf){
        return 1;
    }else if(t instanceof TNode){
        return 1 + Math.max(maxdepth(t.left), maxdepth(t.right));
    }
    return 0;
}

// ============================================================
// Section 5: Tokenizer
// ============================================================
type Token =
  | { type: "lparen" }
  | { type: "rparen" }
  | { type: "number"; value: number }
  | { type: "symbol"; value: string };

// Breaks a raw source string into an array of tokens.
// Walks the string character-by-character, classifying each span as one of:
//   lparen, rparen, number (including negative literals), or symbol.
// Strips whitespace and comments (;) so the parser never sees them.
// Example: "(+ 1 (* 2 3))" → [lparen, symbol(+), number(1), lparen, symbol(*), number(2), number(3), rparen, rparen]
function tokenize(source: string): Token[]{
    const tokens: Token[] = [];
    let pos = 0;

    while(pos < source.length){
        const ch = source[pos];

        // Skip whitespace
        if(ch === " " || ch === "\t" || ch === "\n" || ch === "\r"){
            pos++;
            continue;
        }

        // Skip comments
        if(ch === ";"){
            while(pos < source.length && source[pos] !== "\n"){
                pos++;
            }
            continue;
        }

        if(ch === "("){
            tokens.push({type: "lparen"});
            pos++;
            continue;
        }

        if(ch === ")"){
            tokens.push({type: "rparen"});
            pos++;
            continue;
        }
        
        // Numbers (including negative literals like -3)
        // A minus is part of a number only when immediately followed by a digit.
        // This avoids confusing the minus operator (- 3 5) with a negative literal (-3).
        if(
            (ch >= "0" && ch <= "9") ||
            (ch === "-" && pos + 1 < source.length && source[pos+1] >= "0" && source[pos+1] <="9")
        ){
            let start = pos;
            if(ch === "-"){
                pos++;
            }
            while(pos < source.length && source[pos] >= "0" && source[pos] <= "9"){
                pos++;
            }
            tokens.push({type: "number", value: parseInt(source.slice(start, pos), 10)});
            continue;
        }

        // Symbols — identifiers (+, -, *, <, =, >, if, let, x, myVar, etc.)
        // A symbol is any run of non-whitespace, non-paren, non-semicolon characters.
        if(ch !== "(" && ch !== ")"){
            let start = pos;
            while(
                pos < source.length &&
                source[pos] !== " " &&
                source[pos] !== "\t" &&
                source[pos] !== "\n" &&
                source[pos] !== "\r" &&
                source[pos] !== "(" &&
                source[pos] !== ")" &&
                source[pos] !== ";"
            ){
                pos++;
            }
            tokens.push({type: "symbol", value: source.slice(start, pos)});
            continue;
        }

        pos++;
    }

    return tokens;
}


// ============================================================
// Section 6: Parser
// ============================================================

// Top-level entry point: tokenizes the source and parses exactly one expression.
// Verifies all tokens were consumed — trailing tokens indicate malformed input.
function parse(source: string): Expr {
  const tokens = tokenize(source);
  if (tokens.length === 0) {
    throw new Error("Parse error: empty input");
  }
  const [expr, pos] = parseExpr(tokens, 0);
  if (pos !== tokens.length) {
    throw new Error(`Parse error: unexpected token at position ${pos}`);
  }
  return expr;
}

// Parses a source string that may contain multiple top-level expressions.
// Used by the file loader, where a .mml file has several defines followed by expressions.
// Calls parseExpr repeatedly until all tokens are consumed.
function parseMultiple(source: string): Expr[] {
  const tokens = tokenize(source);
  const exprs: Expr[] = [];
  let pos = 0;
  while (pos < tokens.length) {
    const [expr, nextPos] = parseExpr(tokens, pos);
    exprs.push(expr);
    pos = nextPos;
  }
  return exprs;
}

// Recursive-descent parser: consumes tokens starting at pos, returns [AST node, next position].
// The returned position tells the caller where to continue parsing.
// Dispatches on the current token type to decide which AST node to build.
function parseExpr(tokens: Token[], pos: number): [Expr, number]{
    if(pos >= tokens.length){
        throw new Error("Parse error: unexpected end of input");
    }

    const token = tokens[pos];

    // Atom: a bare number becomes a literal node
    if(token.type === "number"){
        return [new Literal(token.value), pos + 1];
    }

    // Atom: a bare symbol becomes a Var node
    if(token.type === "symbol"){
        return[new Var(token.value), pos +1];
    }

    // Compound expression starts with '(' look at the head symbol to decide the form
    if(token.type === "lparen"){
        pos++;

        if(pos >= tokens.length){
            throw new Error("Parse error: unexpected end of input after '('");
        }

        const head = tokens[pos];

        // Arithmatic operators: (+ e1 e2), (- e1 e2), (* e1,e2)
        // Parse exactly two sub-expressions, then expect closing ')'
        if(head.type === "symbol" && (head.value === "+" || head.value === "-" || head.value === "*")){
            const op = head.value;
            pos++;
            const [left, pos2] = parseExpr(tokens, pos);
            const [right, pos3] = parseExpr(tokens, pos2);
            if(pos3 >= tokens.length || tokens[pos3].type !== "rparen"){
                throw new Error(`Parse error: expected ')' at position ${pos3}`);
            }

            // Map the operator string to the corresponding AST node class
            const node = 
                op === "+" ? new Plus(left, right):
                op === "-" ? new Minus(left, right):
                new Mul(left, right);

            return [node, pos3 + 1];
        }

        // Comparison operators: (< e1 e2), (= e1 e2), (> e1 e2)
        // Same structure as arithmetic — two sub-expressions, but produces a boolean at eval time
        if (head.type === "symbol" && (head.value === "<" || head.value === "=" || head.value === ">")) {
            const op = head.value;
            pos++; // consume operator symbol
            const [left, pos2] = parseExpr(tokens, pos);
            const [right, pos3] = parseExpr(tokens, pos2);
            if (pos3 >= tokens.length || tokens[pos3].type !== "rparen") {
              throw new Error(`Parse error: expected ')' at position ${pos3}`);
            }
            const node =
              op === "<" ? new LessThan(left, right) :
              op === "=" ? new Equals(left, right) :
              new GreaterThan(left, right);
            return [node, pos3 + 1];
        }

        // Conditional: (if cond then else)
        // Parse three sub-expressions: condition, then-branch, else-branch
        if (head.type === "symbol" && head.value === "if") {
            pos++; // consume 'if'
            const [cond, pos2] = parseExpr(tokens, pos);   // parse condition
            const [then, pos3] = parseExpr(tokens, pos2);   // parse then-branch
            const [els, pos4] = parseExpr(tokens, pos3);    // parse else-branch
            if (pos4 >= tokens.length || tokens[pos4].type !== "rparen") {
              throw new Error(`Parse error: expected ')' at position ${pos4}`);
            }
            return [new If(cond, then, els), pos4 + 1];
        }

        // Let binding: (let name binding body)
        // Read a symbol (variable name), then parse two sub-expressions (value + body)
        if (head.type === "symbol" && head.value === "let") {
            pos++; // consume 'let'
            if (pos >= tokens.length || tokens[pos].type !== "symbol") {
              throw new Error(`Parse error: expected variable name after 'let' at position ${pos}`);
            }
            const name = (tokens[pos] as { type: "symbol"; value: string }).value;
            pos++; // consume variable name
            const [binding, pos2] = parseExpr(tokens, pos);  // parse the value to bind
            const [body, pos3] = parseExpr(tokens, pos2);     // parse the body where the binding is visible
            if (pos3 >= tokens.length || tokens[pos3].type !== "rparen") {
              throw new Error(`Parse error: expected ')' at position ${pos3}`);
            }
            return [new Let(name, binding, body), pos3 + 1];
        }

        // Lambda: (lambda (param) body)
        // Parses a single-parameter function definition.
        // The parameter is wrapped in parens: (lambda (x) ...) not (lambda x ...).
        // Multi-argument functions use nesting: (lambda (x) (lambda (y) ...))
        if(head.type === "symbol" && head.value === "lambda"){
            pos++; // consume 'lambda'
            if(pos >= tokens.length || tokens[pos].type !== "lparen"){
                throw new Error(`Parse error: expected '(' after 'lambda' at position ${pos}`);
            }
            pos++; // consume '(' before parameter name
            if(pos >= tokens.length || tokens[pos].type !== "symbol"){
                throw new Error(`Parse error: expected paramater name at position ${pos}`);
            }
            const param = (tokens[pos] as {type: "symbol"; value: string}).value;
            pos++; // consume parameter name (any valid symbol, not just single chars)
            if(pos >= tokens.length || tokens[pos].type !== "rparen"){
                throw new Error(`Parse error: expected ')' after parameter at position ${pos}`);
            }
            pos++; // consume ')' after parameter name
            const [body, pos2] = parseExpr(tokens, pos); // parse the function body
            if (pos2 >= tokens.length || tokens[pos2].type !== "rparen") {
              throw new Error(`Parse error: expected ')' at position ${pos2}`);
            }
            return [new Lambda(param, body), pos2 + 1]; // +1 consumes outer ')'
        }

        // Define: (define name expr)
        // Top-level binding for use in files and the REPL.
        // Unlike let, define has no body -- it modifies the environment permanently.
        // The REPL and file loader handle define specially via evalDefine.
        if (head.type === "symbol" && head.value === "define") {
          pos++; // consume 'define'
          if (pos >= tokens.length || tokens[pos].type !== "symbol") {
            throw new Error(`Parse error: expected variable name after 'define' at position ${pos}`);
          }
          const name = (tokens[pos] as { type: "symbol"; value: string }).value;
          pos++; // consume variable name
          const [binding, pos2] = parseExpr(tokens, pos); // parse the value expression
          if (pos2 >= tokens.length || tokens[pos2].type !== "rparen") {
            throw new Error(`Parse error: expected ')' at position ${pos2}`);
          }
          return [new Define(name, binding), pos2 + 1];
        }

        // Function application: (fn arg1 arg2 ...)
        // Fallback -- must come AFTER all special-form checks.
        // Any parenthesized form whose head is not a recognized keyword lands here.
        // Left-associates multiple arguments for currying: (f a b) becomes App(App(f, a), b).
        {
            const [fn, pos2] = parseExpr(tokens, pos); // parse the function expression
            let currentFn = fn;
            let currentPos = pos2;

            // Parse arguments one at a time, wrapping each in an App node
            while (currentPos < tokens.length && tokens[currentPos].type !== "rparen") {
                const [arg, nextPos] = parseExpr(tokens, currentPos);
                currentFn = new App(currentFn, arg); // left-associate: previous result becomes the function
                currentPos = nextPos;
            }

            if (currentPos >= tokens.length || tokens[currentPos].type !== "rparen") {
                throw new Error(`Parse error: expected ')' at position ${currentPos}`);
            }
            return [currentFn, currentPos + 1];
        }


    }

    throw new Error(`Parse error: unexpected token '${token.type}' at position ${pos}`);

}

// ============================================================
// Section 7: Evaluator
// ============================================================

// The heart of the interpreter: recursively walks the AST and produces a Value.
// Generalizes evaluate_env (Problem 7b) to return Value instead of number|undefined,
// and extends it with comparisons, If, and Let.
// The env parameter threads bindings through the recursion — each Let extends it.
function evaluateExpr(expr: Expr, env: Env): Value{

    // Integer literal is leaf node, no recurssion is needed
    // Wraps the raw number in a tagged value so the type system can destinguish it.
    if(expr instanceof Literal){
        return {tag: "num", value: expr.value};
    }

    // Variable reference — linear scan of the environment (same algorithm as search, Problem 2).
    // Scans front-to-back, so newer bindings (prepended by Let) shadow older ones.
    // Unlike evaluate_env, throws on unbound variables instead of returning undefined.
    if (expr instanceof Var) {
      for (const [name, val] of env) {
        if (name === expr.name) return val;   // found — return the bound value
      }
      throw new Error(`Runtime error: unbound variable '${expr.name}'`);
    }

    // Arithmetic: +, -, *
    // Recursively evaluate both operands, check they're both numbers, compute the result.
    // Dynamic type check: (+ (< 1 2) 3) would fail here because (< 1 2) produces a bool.
    if (expr instanceof Plus || expr instanceof Minus || expr instanceof Mul) {
      const left = evaluateExpr(expr.left, env);
      const right = evaluateExpr(expr.right, env);
      if (left.tag !== "num" || right.tag !== "num") {
        throw new Error("Runtime error: arithmetic on non-numbers");
      }
      const result =
        expr instanceof Plus ? left.value + right.value :
        expr instanceof Minus ? left.value - right.value :
        left.value * right.value;
      return { tag: "num", value: result };
    }

    // Comparisons: <, =, >
    // Same pattern as arithmetic but produces a bool Value instead of a num Value.
    if (expr instanceof LessThan || expr instanceof Equals || expr instanceof GreaterThan) {
      const left = evaluateExpr(expr.left, env);
      const right = evaluateExpr(expr.right, env);
      if (left.tag !== "num" || right.tag !== "num") {
        throw new Error("Runtime error: comparison on non-numbers");
      }
      const result =
        expr instanceof LessThan ? left.value < right.value :
        expr instanceof Equals ? left.value === right.value :
        left.value > right.value;
      return { tag: "bool", value: result };
    }

    // Conditional: if evaluates only the chosen branch
    if(expr instanceof If){
        const cond = evaluateExpr(expr.cond, env);
        if(cond.tag !== "bool"){
            throw new Error("Runtime error: if condition must be a boolean");
        }

        return cond.value ? evaluateExpr(expr.then, env) : evaluateExpr(expr.els, env);
    }

    // Let binding is the environment-threading step:
    // 1. Evaluate binding in current env
    // 2. Prepend [name, value] to env (shadows any prior binding of that name)
    // 3. Evaluate body in extended env
    if (expr instanceof Let) {
      const val = evaluateExpr(expr.binding, env);            // step 1
      const newEnv: Env = [[expr.name, val], ...env];     // step 2: prepend
      return evaluateExpr(expr.body, newEnv);                 // step 3: body sees the new binding
    }

    // Lambda -- does NOT evaluate the body. Packages the parameter name,
    // unevaluated body, and CURRENT environment into a closure value.
    // When applied later, the body runs in the captured env, not the caller's.
    if (expr instanceof Lambda) {
      return { tag: "closure", param: expr.param, body: expr.body, env: env };
    }

    // Application -- evaluate both sides (eager evaluation), then delegate to apply.
    // apply handles both closures (extend captured env) and builtins (collect args).
    if (expr instanceof App) {
      const fn = evaluateExpr(expr.fn, env);   // evaluate the function expression
      const arg = evaluateExpr(expr.arg, env); // evaluate the argument expression
      return apply(fn, arg);                   // dispatch to closure or builtin logic
    }

    throw new Error("Runtime error: unknown expression type");
}   


// Evaluates a define form and returns the extended environment.
// Unlike let (which scopes to a body), define permanently adds the binding.
// Called by the REPL and file loader, not by evaluateExpr directly.
function evalDefine(expr: Define, env: Env): Env {
  const val = evaluateExpr(expr.binding, env); // evaluate the value
  return [[expr.name, val], ...env];           // prepend the new binding
}

// ============================================================
// Section 8: Apply Helper
// ============================================================

// Central dispatch for all function calls in MiniML.
// Handles two kinds of callable values: closures and builtins.
function apply(fn: Value, arg: Value): Value {
  // Closure: extend the CAPTURED environment (not the caller's) with the argument,
  // then evaluate the body. This is lexical scoping in three lines.
  // Uses fn.env (from definition time), not the current env (from call time).
  if (fn.tag === "closure") {
    const newEnv: Env = [[fn.param, arg], ...fn.env];
    return evaluateExpr(fn.body, newEnv);
  }
  // Builtin: collect the argument into a new args array (never mutate the original).
  // If we have enough arguments, call the TypeScript function.
  // If not, return a new builtin with the argument accumulated (partial application).
  if (fn.tag === "builtin") {
    const newArgs = [...fn.args, arg];        // new array, not mutation
    if (newArgs.length === fn.arity) {
      return fn.fn(newArgs);                  // arity met -- call the underlying function
    }
    // Partial application: return a new builtin that remembers this argument
    return { tag: "builtin", name: fn.name, arity: fn.arity, args: newArgs, fn: fn.fn };
  }
  throw new Error(`Runtime error: cannot apply value of type '${fn.tag}'`);
}

// ============================================================
// Section 9: Pretty Printer
// ============================================================

// Converts any Value to a human-readable string for REPL output.
// Each tag has its own representation:
//   num     -> digits (e.g. "42")
//   bool    -> #t or #f (Scheme convention)
//   closure -> <closure> (internals not shown)
//   builtin -> <builtin:name> or <builtin:name[collected/total]> if partially applied
//   list    -> parenthesized elements (e.g. "(1 2 3)")
function printValue(v: Value): string {
  switch (v.tag) {
    case "num":
      return String(v.value);
    case "bool":
      return v.value ? "#t" : "#f";
    case "closure":
      return "<closure>";
    case "builtin":
      // Show partial application progress: <builtin:range[1/3]> means 1 of 3 args collected
      if (v.args.length > 0) {
        return `<builtin:${v.name}[${v.args.length}/${v.arity}]>`;
      }
      return `<builtin:${v.name}>`;
    case "list":
      // Recursively print each element, join with spaces, wrap in parens
      return "(" + v.items.map(printValue).join(" ") + ")";
  }
}

// ============================================================
// Section 10: Standard Library (Built-ins)
// ============================================================

// Creates a builtin Value with an empty args array.
// The apply helper handles currying: each application adds one arg until arity is met.
function makeBuiltin(name: string, arity: number, fn: (args: Value[]) => Value): Value {
  return { tag: "builtin", name, arity, args: [], fn };
}


// Constructs the initial environment with all built-in functions.
// Each builtin unwraps Value objects, calls the underlying TypeScript helper,
// and wraps the result back in a Value. This is the bridge between MiniML and TypeScript.
function buildStdlib(): Env{
    const stdlib: Env = []
    
    // cumsum -- Problem 1
    // (cumsum list) -> list
    // Wraps cumulative_sum. Takes a list of numbers, returns a list of partial sums.
    const cumsumFn = (args: Value[]): Value => {
        if (args[0].tag !== "list") throw new Error("cumsum: expected a list");

        const nums = args[0].items.map(v => {
          if (v.tag !== "num") throw new Error("cumsum: list must contain numbers");
          return v.value;
        });

        const result = cumulative_sum(nums);
        return { tag: "list", items: result.map(n => ({ tag: "num" as const, value: n })) };
    };
    stdlib.push(["cumsum", makeBuiltin("cumsum", 1, cumsumFn)]);
  
    // sum — derived from Problem 1
    // (sum list) -> num
    // Returns the last element of cumulative_sum, which is the total sum.
    const sumFn = (args: Value[]): Value => {
        if (args[0].tag !== "list") throw new Error("sum: expected a list");

        const nums = args[0].items.map(v => {
          if (v.tag !== "num") throw new Error("sum: list must contain numbers");
          return v.value;
        });

        const sums = cumulative_sum(nums);
        if (sums.length === 0) return { tag: "num", value: 0 };
        return { tag: "num", value: sums[sums.length - 1] };
    };
    stdlib.push(["sum", makeBuiltin("sum", 1, sumFn)]);

    // find — Problem 2
    // (find list n) -> num | -1
    // Wraps search. Returns the index of n in the list, or -1 if not found.
    const findFn = (args: Value[]): Value => {
        if (args[0].tag !== "list") throw new Error("find: expected a list as first argument");
        if (args[1].tag !== "num") throw new Error("find: expected a number as second argument");
  
        const nums = args[0].items.map(v => {
          if (v.tag !== "num") throw new Error("find: list must contain numbers");
          return v.value;
        });
  
        const result = search(nums, args[1].value);
        return { tag: "num", value: result === undefined ? -1 : result };
    };
    stdlib.push(["find", makeBuiltin("find", 2, findFn)]);

    // range — Problem 4
    // (range spacing low high) -> list
    // Wraps sequence. Generates an arithmetic progression.
    const rangeFn = (args: Value[]): Value => {
        if (args[0].tag !== "num" || args[1].tag !== "num" || args[2].tag !== "num") {
          throw new Error("range: expected three numbers");
        }

        const result = sequence(args[1].value, args[2].value, args[0].value);
        return { tag: "list", items: result.map(n => ({ tag: "num" as const, value: n })) };
    };
    stdlib.push(["range", makeBuiltin("range", 3, rangeFn)]);

    // filtermap — Problem 8
    // (filtermap pred mapfn list) -> list
    // Takes two MiniML closures and a list. For each element, if pred returns true,
    // apply mapfn and include the result. This is where the host-language filtermap<T,U>
    // is exercised with T = U = Value.
    const filtermapFn = (args: Value[]): Value =>{
        const pred = args[0];
        const mapfn = args[1];

        if(args[2].tag !== "list") throw new Error("filtermap: expected a list as third argument");
        const items = args[2].items;

        const predFn = (v: Value): boolean => {
            const r = apply(pred, v);
            if (r.tag !== "bool") throw new Error("filtermap: predicate must return a boolean");
            return r.value;
        };

        const mapFn = (v: Value): Value => apply(mapfn, v);

        const result = filtermap(predFn, mapFn, items);
        return {tag: "list", items: result};
    };
    stdlib.push(["filtermap", makeBuiltin("filtermap", 3, filtermapFn)]);


    // nat->int — Problem 3
    // (nat->int nat) -> num
    const natToIntFn = (args: Value[]): Value => {
        if (args[0].tag !== "num") throw new Error("nat->int: expected a number (Peano representation)");
        
        const nat = from_int(args[0].value);
        return { tag: "num", value: to_int(nat) };
    };
    stdlib.push(["nat->int", makeBuiltin("nat->int", 1, natToIntFn)]);

    // int->nat — Problem 3
    // (int->nat num) -> num
    // Since MiniML has no native Nat type, this round-trips through Peano and back.
    // The pedagogical point is that the conversion functions exist and work.
    const intToNatFn = (args: Value[]): Value => {
        if (args[0].tag !== "num") throw new Error("int->nat: expected a number");

        const nat = from_int(args[0].value);
        return { tag: "num", value: to_int(nat) };
    };
    stdlib.push(["int->nat", makeBuiltin("int->nat", 1, intToNatFn)]);

    // nat+ — Problem 3
    // (nat+ a b) -> num
    // Adds two numbers using Peano addition: converts both to Nat, adds, converts back.
    const natPlusFn = (args: Value[]): Value => {
        if (args[0].tag !== "num" || args[1].tag !== "num") {
          throw new Error("nat+: expected two numbers");
        }

        const a = from_int(args[0].value);
        const b = from_int(args[1].value);
        return { tag: "num", value: to_int(add(a, b)) };
    };
    stdlib.push(["nat+", makeBuiltin("nat+", 2, natPlusFn)]);

    // depth — Problem 10
    // (depth expr-as-value) -> num
    // Since MiniML values are not AST nodes, this builtin takes a list
    // (as a binary-tree-like structure) and computes its nesting depth.
    const depthFn = (args: Value[]): Value => {
        // Convert a nested list structure to a Tree and compute depth
        function valueToTree(v: Value): Tree {
            if (v.tag === "list" && v.items.length === 2) {
                return new TNode(valueToTree(v.items[0]), valueToTree(v.items[1]));
            } else if (v.tag === "list" && v.items.length === 0) {
                return undefined;
            } else {
                return new Tleaf();
            }
        }

        return { tag: "num", value: maxdepth(valueToTree(args[0])) };
    };
    stdlib.push(["depth", makeBuiltin("depth", 1, depthFn)]);

    // map — convenience built-in (uses filtermap with always-true filter)
    // (map fn list) -> list
    const mapFn = (args: Value[]): Value => {
        const mapfn = args[0];
        if (args[1].tag !== "list") throw new Error("map: expected a list as second argument");
        const items = args[1].items;

        const alwaysTrue = (_: Value): boolean => true;
        const applyMap = (v: Value): Value => apply(mapfn, v);

        const result = filtermap(alwaysTrue, applyMap, items);
        return { tag: "list", items: result };
    };
    stdlib.push(["map", makeBuiltin("map", 2, mapFn)]);

    // filter — convenience built-in (uses filtermap with identity map)
    // (filter pred list) -> list
    const filterFn = (args: Value[]): Value => {
        const pred = args[0];
        if (args[1].tag !== "list") throw new Error("filter: expected a list as second argument");
        const items = args[1].items;

        const predFn = (v: Value): boolean => {
            const r = apply(pred, v);
            if (r.tag !== "bool") throw new Error("filter: predicate must return a boolean");
            return r.value;
        };

        const identity = (v: Value): Value => v;

        const result = filtermap(predFn, identity, items);
        return { tag: "list", items: result };
    };
    stdlib.push(["filter", makeBuiltin("filter", 2, filterFn)]);

    // length — returns the length of a list
    // (length list) -> num
    const lengthFn = (args: Value[]): Value => {
        if (args[0].tag !== "list") throw new Error("length: expected a list");
        return { tag: "num", value: args[0].items.length };
    };
    stdlib.push(["length", makeBuiltin("length", 1, lengthFn)]);

    // true and false constants
    stdlib.push(["true", { tag: "bool", value: true }]);
    stdlib.push(["false", { tag: "bool", value: false }]);

    return stdlib;

}

// ============================================================
// Section 11: REPL and File Loader 
// ============================================================
// Reads a .mml file, parses all expressions, and evaluates them in order.
// Define forms extend the environment; other expressions are evaluated and printed.
// Returns the updated environment so later code can see the definitions.
// Errors in individual expressions are caught and printed without aborting the file.
function loadFile(path: string, env: Env): Env {
    let source: string;
    try {
        source = fs.readFileSync(path, "utf-8");
    } catch (e: any) {
        console.log(`Error: could not read file '${path}': ${e.message}`);
        return env; // file unreadable -- return env unchanged
    }

    const exprs = parseMultiple(source); // parse all top-level expressions
    let currentEnv = env;

    for (const expr of exprs) {
      try {
        if (expr instanceof Define) {
            currentEnv = evalDefine(expr, currentEnv); // extend env with the new binding
            console.log(`defined ${expr.name}`);
        } else {
            const result = evaluateExpr(expr, currentEnv); // evaluate and print
            console.log(printValue(result));
        }
      } catch (e: any) {
            console.log(`Error: ${e.message}`); // catch per-expression, keep going
      }
    }

    return currentEnv; // return env with all successful defines accumulated
}

// Interactive REPL. Reads one expression per line, evaluates it, prints the result.
// The environment persists across lines via the mutable currentEnv variable,
// so (define x 5) on one line makes x available on the next.
// Supports two commands:
//   :load <file> -- load and execute a .mml file, adding its defines to the env
//   :quit        -- exit the REPL (empty input also exits)
function startRepl(env: Env): void {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout,
    });

    let currentEnv = env; // mutable -- accumulates define bindings across lines

    console.log("MiniML REPL -- type :quit to exit, :load <file> to load a file");

    const prompt = () => {
        rl.question("miniml> ", (line: string) => {
            const trimmed = line.trim();

            // Exit on empty input or :quit
            if (trimmed === "" || trimmed === ":quit") {
                rl.close();
                return;
            }

            // :load command -- load a file, update the env, then re-prompt
            if (trimmed.startsWith(":load ")) {
                const path = trimmed.slice(6).trim();
                currentEnv = loadFile(path, currentEnv);
                prompt();
                return;
            }

            // Normal expression -- parse, evaluate, print
            try {
                const expr = parse(trimmed);
                if (expr instanceof Define) {
                    currentEnv = evalDefine(expr, currentEnv); // define updates the persistent env
                    console.log(`defined ${(expr as Define).name}`);
                } else {
                    const result = evaluateExpr(expr, currentEnv);
                    console.log(printValue(result));
                }
            } catch (e: any) {
                console.log(`Error: ${e.message}`); // errors don't kill the REPL
            }

            prompt(); // loop back for the next line
      });
    };

    prompt();
}


// ============================================================
// Section 12: Entry Point --- TODO phase2
// ============================================================

// Entry point: build the standard library, optionally load files from the command line,
// then start the REPL. Files are loaded in order, and their defines are available
// in subsequent files and in the REPL session.
function main(): void {
    const env = buildStdlib();            // start with all builtins in the env
    const args = process.argv.slice(2);   // command-line args after "node miniml.js"

    if (args.length > 0) {
        // Load each file in order, threading the environment through
        let currentEnv = env;
        for (const file of args) {
            currentEnv = loadFile(file, currentEnv);
        }
        startRepl(currentEnv); // REPL starts with all file definitions available
    } else {
        startRepl(env);        // no files -- REPL starts with just the stdlib
    }
}

main();