o1-previewの力

lang-after.js

// Program class
class Program {
  constructor(defs, ...expressions) {
    this.defs = defs;
    this.expressions = expressions;
  }
}                                                                                                                                                                                                                                               // Function definition class
class FunDef {
  constructor(name, args, body) {
    this.name = name;
    this.args = args;
    this.body = body;
  }
}

// Base expression class
class Expression {}

// Assignment class
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
}

// Binary expression class
class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}

// Number class (supports integers and decimals)
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

// Variable reference class
class VarRef extends Expression {
  constructor(name) {
    super();
    this.name = name;
  }
}

// Function call class
class FunCall extends Expression {
  constructor(name, ...args) {
    super();
    this.name = name;
    this.args = args;
  }
}

// If expression class
class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

// While loop class
class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

// Sequence class
class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}

// Built-in function class
class BuiltinFun {
  constructor(name, func) {
    this.name = name;
    this.func = func;
  }
}

// List class
class List extends Expression {
  constructor(elements) {
    super();
    this.elements = elements;
  }
}

// String literal class
class StringLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

// Dictionary class
class Dict extends Expression {
  constructor(entries) {
    super();
    this.entries = entries;
  }
}

// Boolean literal class
class BooleanLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

function evalProgram(program) {
  const env = {};
  const funEnv = {};
  const builtinFunEnv = {
    'print': new BuiltinFun('print', (args) => {
      console.log(...args);
      return args[0];
    }),
    'input': new BuiltinFun('input', () => {
      return prompt('Enter input:');
    }),
    'add': new BuiltinFun('add', (args) => args.reduce((a, b) => a + b, 0)),
    'mul': new BuiltinFun('mul', (args) => args.reduce((a, b) => a * b, 1)),
    'len': new BuiltinFun('len', (args) => {
      if (args.length !== 1) throw new Error('len expects exactly one argument');
      const arg = args[0];
      if (typeof arg === 'string' || Array.isArray(arg)) {
        return arg.length;
      } else {
        throw new Error('len expects a string or array');
      }
    }),
    'get': new BuiltinFun('get', (args) => {
      if (args.length !== 2) throw new Error('get expects exactly two arguments');
      const [collection, key] = args;
      if (Array.isArray(collection)) {
        return collection[key];
      } else if (typeof collection === 'object' && collection !== null) {
        return collection[key];
      } else {
        throw new Error('get expects an array or object as the first argument');
      }
    }),
    'concat': new BuiltinFun('concat', (args) => {
      if (args.length !== 2) throw new Error('concat expects exactly two arguments');
      const [a, b] = args;
      if (typeof a === 'string' && typeof b === 'string') {
        return a + b;
      } else if (Array.isArray(a) && Array.isArray(b)) {
        return a.concat(b);
      } else {
        throw new Error('concat expects both arguments to be strings or arrays');
      }
    }),
    'append': new BuiltinFun('append', (args) => {
      if (args.length !== 2) throw new Error('append expects exactly two arguments');
      const [lst, elem] = args;
      if (Array.isArray(lst)) {
        return lst.concat([elem]);
      } else {
        throw new Error('append expects an array as the first argument');
      }
    }),
    'keys': new BuiltinFun('keys', (args) => {
      if (args.length !== 1) throw new Error('keys expects exactly one argument');
      const obj = args[0];
      if (typeof obj === 'object' && obj !== null && !Array.isArray(obj)) {
        return Object.keys(obj);
      } else {
        throw new Error('keys expects an object');
      }
    }),
    'values': new BuiltinFun('values', (args) => {
      if (args.length !== 1) throw new Error('values expects exactly one argument');
      const obj = args[0];
      if (typeof obj === 'object' && obj !== null && !Array.isArray(obj)) {
        return Object.values(obj);
      } else {
        throw new Error('values expects an object');
      }
    }),
  };
  let result = null;
  program.defs.forEach((d) => {
    funEnv[d.name] = d;
  });
  program.expressions.forEach((e) => {
    result = eval(e, env, funEnv, builtinFunEnv);
  });
  return result;
}

function eval(expr, env, funEnv, builtinFunEnv) {
  if (expr instanceof BinExpr) {
    const resultL = eval(expr.lhs, env, funEnv, builtinFunEnv);
    const resultR = eval(expr.rhs, env, funEnv, builtinFunEnv);
    switch (expr.operator) {
      case "+":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL + resultR;
        } else if (typeof resultL === 'string' || typeof resultR === 'string') {
          return String(resultL) + String(resultR);
        } else if (Array.isArray(resultL) && Array.isArray(resultR)) {
          return resultL.concat(resultR);
        } else {
          throw new Error(`Unsupported operand types for +: ${typeof resultL} and ${typeof resultR}`);
        }
      case "-":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL - resultR;
        } else {
          throw new Error(`Unsupported operand types for -: ${typeof resultL} and ${typeof resultR}`);
        }
      case "*":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL * resultR;
        } else {
          throw new Error(`Unsupported operand types for *: ${typeof resultL} and ${typeof resultR}`);
        }
      case "/":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL / resultR;
        } else {
          throw new Error(`Unsupported operand types for /: ${typeof resultL} and ${typeof resultR}`);
        }
      case "<":
        return resultL < resultR;
      case ">":
        return resultL > resultR;
      case "<=":
        return resultL <= resultR;
      case ">=":
        return resultL >= resultR;
      case "==":
        return resultL === resultR;
      case "!=":
        return resultL !== resultR;
      default:
        throw new Error(`Unsupported operator: ${expr.operator}`);
    }
  } else if (expr instanceof Num) {
    return expr.value;
  } else if (expr instanceof StringLit) {
    return expr.value;
  } else if (expr instanceof BooleanLit) {
    return expr.value;
  } else if (expr instanceof VarRef) {
    if (!(expr.name in env)) {
      throw new Error(`Variable ${expr.name} is not defined`);
    }
    return env[expr.name];
  } else if (expr instanceof Assignment) {
    const result = eval(expr.expr, env, funEnv, builtinFunEnv);
    env[expr.name] = result;
    return result;
  } else if (expr instanceof Seq) {
    let result = null;
    expr.bodies.forEach((e) => {
      result = eval(e, env, funEnv, builtinFunEnv);
    });
    return result;
  } else if (expr instanceof If) {
    if (eval(expr.cond, env, funEnv, builtinFunEnv)) {
      return eval(expr.thenExpr, env, funEnv, builtinFunEnv);
    } else {
      return eval(expr.elseExpr, env, funEnv, builtinFunEnv);
    }
  } else if (expr instanceof While) {
    while (eval(expr.cond, env, funEnv, builtinFunEnv)) {
      eval(expr.body, env, funEnv, builtinFunEnv);
    }
    return null;
  } else if (expr instanceof FunCall) {
    const def = funEnv[expr.name] || builtinFunEnv[expr.name];
    if (!def) throw new Error(`Function ${expr.name} is not defined`);

    const args = expr.args.map((a) => eval(a, env, funEnv, builtinFunEnv));

    if (def instanceof BuiltinFun) {
      return def.func(args);
    }

    const newEnv = {};
    for (let i = 0; i < def.args.length; i++) {
      newEnv[def.args[i]] = args[i];
    }
    return eval(def.body, newEnv, funEnv, builtinFunEnv);
  } else if (expr instanceof List) {
    return expr.elements.map((e) => eval(e, env, funEnv, builtinFunEnv));
  } else if (expr instanceof Dict) {
    const result = {};
    expr.entries.forEach(({ key, value }) => {
      const evalKey = eval(key, env, funEnv, builtinFunEnv);
      const evalValue = eval(value, env, funEnv, builtinFunEnv);
      result[evalKey] = evalValue;
    });
    return result;
  } else {
    throw new Error(`Unknown expression type: ${expr.constructor.name}`);
  }
}

const program = new Program(
  [
    new FunDef("main", [],
      new Seq(
        new Assignment("myList", new List([new Num(1), new Num(2), new Num(3)])),
        new Assignment("myString", new StringLit("Hello")),
        new Assignment("myDict", new Dict([
          { key: new StringLit("a"), value: new Num(1) },
          { key: new StringLit("b"), value: new Num(2) }
        ])),
        new FunCall("print", new FunCall("len", new VarRef("myList"))),
        new FunCall("print", new FunCall("concat", new VarRef("myString"), new StringLit(" World"))),
        new FunCall("print", new FunCall("get", new VarRef("myDict"), new StringLit("a"))),
        new FunCall("print", new BinExpr("==", new BooleanLit(true), new BooleanLit(false)))
      )
    )
  ],
  new FunCall("main")
);

evalProgram(program);

lang-after2.js

// Program class
class Program {
  constructor(defs, ...expressions) {
    this.defs = defs;
    this.expressions = expressions;
  }
}                                                                                                                       
// Function definition class
class FunDef {
  constructor(name, args, body) {
    this.name = name;
    this.args = args;
    this.body = body;
  }
}

// Base expression class
class Expression {}

// Assignment class
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
}

// Binary expression class
class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}

// Number class (supports integers and decimals)
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

// Variable reference class
class VarRef extends Expression {
  constructor(name) {
    super();
    this.name = name;
  }
}

// Function call class
class FunCall extends Expression {
  constructor(name, ...args) {
    super();
    this.name = name;
    this.args = args;
  }
}

// If expression class
class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

// While loop class
class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

// Sequence class
class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}

// Built-in function class
class BuiltinFun {
  constructor(name, func) {
    this.name = name;
    this.func = func;
  }
}

// List class
class List extends Expression {
  constructor(elements) {
    super();
    this.elements = elements;
  }
}

// String literal class
class StringLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

// Dictionary class
class Dict extends Expression {
  constructor(entries) {
    super();
    this.entries = entries;
  }
}

// Boolean literal class
class BooleanLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

function evalProgram(program) {
  const env = {};
  const funEnv = {};
  let result = null;

  program.defs.forEach((d) => {
    funEnv[d.name] = d;
  });

  program.expressions.forEach((e) => {
    result = eval(e, env, funEnv, builtinFunEnv);
  });

  return result;
}

function eval(expr, env, funEnv, builtinFunEnv) {
  if (expr instanceof BinExpr) {
    const resultL = eval(expr.lhs, env, funEnv, builtinFunEnv);
    const resultR = eval(expr.rhs, env, funEnv, builtinFunEnv);
    switch (expr.operator) {
      case "+":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL + resultR;
        } else if (typeof resultL === 'string' || typeof resultR === 'string') {
          return String(resultL) + String(resultR);
        } else if (Array.isArray(resultL) && Array.isArray(resultR)) {
          return resultL.concat(resultR);
        } else {
          throw new Error(`Unsupported operand types for +: ${typeof resultL} and ${typeof resultR}`);
        }
      case "-":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL - resultR;
        } else {
          throw new Error(`Unsupported operand types for -: ${typeof resultL} and ${typeof resultR}`);
        }
      case "*":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL * resultR;
        } else {
          throw new Error(`Unsupported operand types for *: ${typeof resultL} and ${typeof resultR}`);
        }
      case "/":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL / resultR;
        } else {
          throw new Error(`Unsupported operand types for /: ${typeof resultL} and ${typeof resultR}`);
        }
      case "%":
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL % resultR;
        } else {
          throw new Error(`Unsupported operand types for %: ${typeof resultL} and ${typeof resultR}`);
        }
      case "<":
        return resultL < resultR;
      case ">":
        return resultL > resultR;
      case "<=":
        return resultL <= resultR;
      case ">=":
        return resultL >= resultR;
      case "==":
        return resultL === resultR;
      case "!=":
        return resultL !== resultR;
      default:
        throw new Error(`Unsupported operator: ${expr.operator}`);
    }
  } else if (expr instanceof Num) {
    return expr.value;
  } else if (expr instanceof StringLit) {
    return expr.value;
  } else if (expr instanceof BooleanLit) {
    return expr.value;
  } else if (expr instanceof VarRef) {
    if (!(expr.name in env)) {
      throw new Error(`Variable ${expr.name} is not defined`);
    }
    return env[expr.name];
  } else if (expr instanceof Assignment) {
    const result = eval(expr.expr, env, funEnv, builtinFunEnv);
    env[expr.name] = result;
    return result;
  } else if (expr instanceof Seq) {
    let result = null;
    expr.bodies.forEach((e) => {
      result = eval(e, env, funEnv, builtinFunEnv);
    });
    return result;
  } else if (expr instanceof If) {
    if (eval(expr.cond, env, funEnv, builtinFunEnv)) {
      return eval(expr.thenExpr, env, funEnv, builtinFunEnv);
    } else {
      return eval(expr.elseExpr, env, funEnv, builtinFunEnv);
    }
  } else if (expr instanceof While) {
    while (eval(expr.cond, env, funEnv, builtinFunEnv)) {
      eval(expr.body, env, funEnv, builtinFunEnv);
    }
    return null;
  } else if (expr instanceof FunCall) {
    const def = funEnv[expr.name] || builtinFunEnv[expr.name];
    if (!def) throw new Error(`Function ${expr.name} is not defined`);

    const args = expr.args.map((a) => eval(a, env, funEnv, builtinFunEnv));

    if (def instanceof BuiltinFun) {
      return def.func(args, env, funEnv, builtinFunEnv);
    }

    const newEnv = {};
    for (let i = 0; i < def.args.length; i++) {
      newEnv[def.args[i]] = args[i];
    }
    return eval(def.body, newEnv, funEnv, builtinFunEnv);
  } else if (expr instanceof List) {
    return expr.elements.map((e) => eval(e, env, funEnv, builtinFunEnv));
  } else if (expr instanceof Dict) {
    const result = {};
    expr.entries.forEach(({ key, value }) => {
      const evalKey = eval(key, env, funEnv, builtinFunEnv);
      const evalValue = eval(value, env, funEnv, builtinFunEnv);
      result[evalKey] = evalValue;
    });
    return result;
  } else {
    throw new Error(`Unknown expression type: ${expr.constructor.name}`);
  }
}

// The built-in functions (as defined earlier)
const builtinFunEnv = {
  // Existing functions
  'print': new BuiltinFun('print', (args) => {
    console.log(...args);
    return args[0];
  }),
  'input': new BuiltinFun('input', () => {
    return prompt('Enter input:');
  }),
  'add': new BuiltinFun('add', (args) => args.reduce((a, b) => a + b, 0)),
  'mul': new BuiltinFun('mul', (args) => args.reduce((a, b) => a * b, 1)),

  // Functions for Lists
  'len': new BuiltinFun('len', (args) => {
    if (args.length !== 1) throw new Error('len expects exactly one argument');
    const arg = args[0];
    if (typeof arg === 'string' || Array.isArray(arg)) {
      return arg.length;
    } else {
      throw new Error('len expects a string or array');
    }
  }),
  'get': new BuiltinFun('get', (args) => {
    if (args.length !== 2) throw new Error('get expects exactly two arguments');
    const [collection, key] = args;
    if (Array.isArray(collection)) {
      return collection[key];
    } else if (typeof collection === 'object' && collection !== null) {
      return collection[key];
    } else {
      throw new Error('get expects an array or object as the first argument');
    }
  }),
  'slice': new BuiltinFun('slice', (args) => {
    if (args.length < 2 || args.length > 3) throw new Error('slice expects 2 or 3 arguments');
    const [collection, start, end] = args;
    if (Array.isArray(collection) || typeof collection === 'string') {
      return collection.slice(start, end);
    } else {
      throw new Error('slice expects a string or array as the first argument');
    }
  }),
  'append': new BuiltinFun('append', (args) => {
    if (args.length !== 2) throw new Error('append expects exactly two arguments');
    const [lst, elem] = args;
    if (Array.isArray(lst)) {
      return lst.concat([elem]);
    } else {
      throw new Error('append expects an array as the first argument');
    }
  }),
  'map': new BuiltinFun('map', (args, env, funEnv, builtinFunEnv) => {
    if (args.length !== 2) throw new Error('map expects exactly two arguments');
    const [lst, funcName] = args;
    if (!Array.isArray(lst)) throw new Error('map expects an array as the first argument');
    const func = funEnv[funcName] || builtinFunEnv[funcName];
    if (!func) throw new Error(`Function ${funcName} is not defined`);
    return lst.map((elem) => {
      if (func instanceof BuiltinFun) {
        return func.func([elem]);
      } else {
        const newEnv = { [func.args[0]]: elem };
        return eval(func.body, newEnv, funEnv, builtinFunEnv);
      }
    });
  }),
  'filter': new BuiltinFun('filter', (args, env, funEnv, builtinFunEnv) => {
    if (args.length !== 2) throw new Error('filter expects exactly two arguments');
    const [lst, funcName] = args;
    if (!Array.isArray(lst)) throw new Error('filter expects an array as the first argument');
    const func = funEnv[funcName] || builtinFunEnv[funcName];
    if (!func) throw new Error(`Function ${funcName} is not defined`);
    return lst.filter((elem) => {
      if (func instanceof BuiltinFun) {
        return func.func([elem]);
      } else {
        const newEnv = { [func.args[0]]: elem };
        return eval(func.body, newEnv, funEnv, builtinFunEnv);
      }
    });
  }),
  'reduce': new BuiltinFun('reduce', (args, env, funEnv, builtinFunEnv) => {
    if (args.length !== 3) throw new Error('reduce expects exactly three arguments');
    const [lst, funcName, initial] = args;
    if (!Array.isArray(lst)) throw new Error('reduce expects an array as the first argument');
    const func = funEnv[funcName] || builtinFunEnv[funcName];
    if (!func) throw new Error(`Function ${funcName} is not defined`);
    return lst.reduce((acc, elem) => {
      if (func instanceof BuiltinFun) {
        return func.func([acc, elem]);
      } else {
        const newEnv = { [func.args[0]]: acc, [func.args[1]]: elem };
        return eval(func.body, newEnv, funEnv, builtinFunEnv);
      }
    }, initial);
  }),
  'indexOf': new BuiltinFun('indexOf', (args) => {
    if (args.length !== 2) throw new Error('indexOf expects exactly two arguments');
    const [lst, elem] = args;
    if (Array.isArray(lst) || typeof lst === 'string') {
      return lst.indexOf(elem);
    } else {
      throw new Error('indexOf expects a string or array as the first argument');
    }
  }),
  'join': new BuiltinFun('join', (args) => {
    if (args.length !== 2) throw new Error('join expects exactly two arguments');
    const [lst, separator] = args;
    if (Array.isArray(lst)) {
      return lst.join(separator);
    } else {
      throw new Error('join expects an array as the first argument');
    }
  }),

  // Functions for Strings
  'substring': new BuiltinFun('substring', (args) => {
    if (args.length < 2 || args.length > 3) throw new Error('substring expects 2 or 3 arguments');
    const [str, start, end] = args;
    if (typeof str === 'string') {
      return str.substring(start, end);
    } else {
      throw new Error('substring expects a string as the first argument');
    }
  }),
  'toUpperCase': new BuiltinFun('toUpperCase', (args) => {
    if (args.length !== 1) throw new Error('toUpperCase expects exactly one argument');
    const [str] = args;
    if (typeof str === 'string') {
      return str.toUpperCase();
    } else {
      throw new Error('toUpperCase expects a string');
    }
  }),
  'toLowerCase': new BuiltinFun('toLowerCase', (args) => {
    if (args.length !== 1) throw new Error('toLowerCase expects exactly one argument');
    const [str] = args;
    if (typeof str === 'string') {
      return str.toLowerCase();
    } else {
      throw new Error('toLowerCase expects a string');
    }
  }),
  'split': new BuiltinFun('split', (args) => {
    if (args.length !== 2) throw new Error('split expects exactly two arguments');
    const [str, separator] = args;
    if (typeof str === 'string') {
      return str.split(separator);
    } else {
      throw new Error('split expects a string as the first argument');
    }
  }),
  'replace': new BuiltinFun('replace', (args) => {
    if (args.length !== 3) throw new Error('replace expects exactly three arguments');
    const [str, searchValue, replaceValue] = args;
    if (typeof str === 'string') {
      return str.replace(new RegExp(searchValue, 'g'), replaceValue);
    } else {
      throw new Error('replace expects a string as the first argument');
    }
  }),

  // Functions for Dictionaries
  'keys': new BuiltinFun('keys', (args) => {
    if (args.length !== 1) throw new Error('keys expects exactly one argument');
    const obj = args[0];
    if (typeof obj === 'object' && obj !== null && !Array.isArray(obj)) {
      return Object.keys(obj);
    } else {
      throw new Error('keys expects a dictionary');
    }
  }),
  'values': new BuiltinFun('values', (args) => {
    if (args.length !== 1) throw new Error('values expects exactly one argument');
    const obj = args[0];
    if (typeof obj === 'object' && obj !== null && !Array.isArray(obj)) {
      return Object.values(obj);
    } else {
      throw new Error('values expects a dictionary');
    }
  }),
  'hasKey': new BuiltinFun('hasKey', (args) => {
    if (args.length !== 2) throw new Error('hasKey expects exactly two arguments');
    const [obj, key] = args;
    if (typeof obj === 'object' && obj !== null && !Array.isArray(obj)) {
      return obj.hasOwnProperty(key);
    } else {
      throw new Error('hasKey expects a dictionary as the first argument');
    }
  }),
  'merge': new BuiltinFun('merge', (args) => {
    if (args.length !== 2) throw new Error('merge expects exactly two arguments');
    const [obj1, obj2] = args;
    if (typeof obj1 === 'object' && typeof obj2 === 'object' && !Array.isArray(obj1) && !Array.isArray(obj2)) {
      return { ...obj1, ...obj2 };
    } else {
      throw new Error('merge expects dictionaries as arguments');
    }
  }),

  // Functions for Booleans
  'and': new BuiltinFun('and', (args) => {
    if (args.length !== 2) throw new Error('and expects exactly two arguments');
    const [a, b] = args;
    return Boolean(a && b);
  }),
  'or': new BuiltinFun('or', (args) => {
    if (args.length !== 2) throw new Error('or expects exactly two arguments');
    const [a, b] = args;
    return Boolean(a || b);
  }),
  'not': new BuiltinFun('not', (args) => {
    if (args.length !== 1) throw new Error('not expects exactly one argument');
    const [a] = args;
    return !a;
  }),
};


// The example program (as defined earlier)
const program = new Program(
  [
    // Define a function to double a number
    new FunDef("double", ["x"],
      new BinExpr("*", new VarRef("x"), new Num(2))
    ),
    // Define a function to check if a number is even
    new FunDef("isEven", ["x"],
      new BinExpr("==", new BinExpr("%", new VarRef("x"), new Num(2)), new Num(0))
    ),
    // Define a reducer function to sum numbers
    new FunDef("sum", ["a", "b"],
      new BinExpr("+", new VarRef("a"), new VarRef("b"))
    )
  ],
  new Seq(
    // Working with Lists
    new Assignment("numbers", new List([new Num(1), new Num(2), new Num(3), new Num(4)])),
    new Assignment("doubledNumbers", new FunCall("map", new VarRef("numbers"), new StringLit("double"))),
    new FunCall("print", new VarRef("doubledNumbers")), // Output: [2, 4, 6, 8]
    new Assignment("evenNumbers", new FunCall("filter", new VarRef("numbers"), new StringLit("isEven"))),
    new FunCall("print", new VarRef("evenNumbers")), // Output: [2, 4]
    new Assignment("total", new FunCall("reduce", new VarRef("numbers"), new StringLit("sum"), new Num(0))),
    new FunCall("print", new VarRef("total")), // Output: 10

    // Working with Strings
    new Assignment("greeting", new StringLit("Hello, World!")),
    new Assignment("uppercaseGreeting", new FunCall("toUpperCase", new VarRef("greeting"))),
    new FunCall("print", new VarRef("uppercaseGreeting")), // Output: "HELLO, WORLD!"
    new Assignment("words", new FunCall("split", new VarRef("greeting"), new StringLit(", "))),
    new FunCall("print", new VarRef("words")), // Output: ["Hello", "World!"]
    new Assignment("joinedWords", new FunCall("join", new VarRef("words"), new StringLit(" - "))),
    new FunCall("print", new VarRef("joinedWords")), // Output: "Hello - World!"

    // Working with Dictionaries
    new Assignment("person", new Dict([
      { key: new StringLit("name"), value: new StringLit("Alice") },
      { key: new StringLit("age"), value: new Num(30) }
    ])),
    new FunCall("print", new FunCall("keys", new VarRef("person"))), // Output: ["name", "age"]
    new FunCall("print", new FunCall("values", new VarRef("person"))), // Output: ["Alice", 30]
    new FunCall("print", new FunCall("get", new VarRef("person"), new StringLit("name"))), // Output: "Alice"
    new FunCall("print", new FunCall("hasKey", new VarRef("person"), new StringLit("email"))), // Output: false
    new Assignment("additionalInfo", new Dict([
      { key: new StringLit("email"), value: new StringLit("[email protected]") }
    ])),
    new Assignment("updatedPerson", new FunCall("merge", new VarRef("person"), new VarRef("additionalInfo"))),
    new FunCall("print", new VarRef("updatedPerson")),
    // Output: { name: "Alice", age: 30, email: "[email protected]" }

    // Working with Booleans
    new Assignment("bool1", new BooleanLit(true)),
    new Assignment("bool2", new BooleanLit(false)),
    new FunCall("print", new FunCall("and", new VarRef("bool1"), new VarRef("bool2"))), // Output: false
    new FunCall("print", new FunCall("or", new VarRef("bool1"), new VarRef("bool2"))), // Output: true
    new FunCall("print", new FunCall("not", new VarRef("bool2"))) // Output: true
  )
);

evalProgram(program);

lang-before.js

//プログラム全体
class Program {
  constructor(defs, ...expressions){
    this.defs = defs;
    this.expressions = expressions;
  }
}
//関数定義を表すクラス
class FunDef {
  constructor(name, args, body) {
    this.name = name;
    this.args = args;
    this.body = body;
  }
}
// 式を表すクラス
class Expression {}
// 代入を表すクラス
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
} // 二項演算子（+、-、*、/）のためのクラス
class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}
// 整数値のためのクラス
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 変数参照のためのクラス
class VarRef extends Expression {
  constructor(name){
    super();
    this.name = name;
  }
}

// 関数呼び出しのためのクラス
class FunCall extends Expression {
  constructor(name, ...args) {
    super();
    this.name = name;
    this.args = args;
  }
}

// 条件分岐のためのクラス
class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

// 繰り返しのためのクラス
class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

// 連接のためのクラス
class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}
// 組み込み関数のためのクラス
class BuiltinFun {
  constructor(name, func) {
    this.name = name;
    this.func = func;
  }
}

function evalProgram(program) {
  const env = {};
  const funEnv = {};
  const builtinFunEnv = {
    'print': new BuiltinFun('print', (args) => {
      console.log(...args);
      return args[0];
    }),
    'input': new BuiltinFun('input', () => {
      return prompt('Enter input:');
    }),
    'add': new BuiltinFun('add', (args) => args.reduce((a, b) => a + b, 0)),
    'mul': new BuiltinFun('mul', (args) => args.reduce((a, b) => a * b, 1)),
  };
  let result = null;
  program.defs.forEach((d) => {
    funEnv[d.name] = d;
  });
  program.expressions.forEach((e) => {
    result = eval(e, env, funEnv, builtinFunEnv);
  });
  return result;
}

function eval(expr, env, funEnv, builtinFunEnv) {
  if(expr instanceof BinExpr) {
    const resultL = eval(expr.lhs, env, funEnv, builtinFunEnv);
    const resultR = eval(expr.rhs, env, funEnv, builtinFunEnv);
    switch(expr.operator) {
      case "+":
        return resultL + resultR;
      case "-":
        return resultL - resultR;
      case "*":
        return resultL * resultR;
      case "/":
        return resultL / resultR;
      case "<":
        return resultL < resultR ? 1 : 0;
      case ">":
        return resultL > resultR ? 1 : 0;
      case "<=":
        return resultL <= resultR ? 1 : 0;
      case ">=":
        return resultL >= resultR ? 1 : 0;
      case "==":
        return resultL === resultR ? 1 : 0;
      case "!=":
        return resultL !== resultR ? 1 : 0;
    }
  } else if(expr instanceof Num) {
     return expr.value;
  } else if(expr instanceof VarRef) {
     if (!(expr.name in env)) {
       throw new Error(`variable ${expr.name} is not defined`);
     }
     return env[expr.name];

     return env[expr.name];
  } else if(expr instanceof Assignment) {
     const result = eval(expr.expr, env, funEnv, builtinFunEnv);
     env[expr.name] = result;
     return result;
  } else if(expr instanceof Seq) {
     let result = null;
     expr.bodies.forEach((e) => {
        result = eval(e, env, funEnv, builtinFunEnv);
     });
     return result;
  } else if(expr instanceof If) {
     if(eval(expr.cond, env, funEnv, builtinFunEnv) !== 0) {
       return eval(expr.thenExpr, env, funEnv, builtinFunEnv);
     }else {
       return eval(expr.elseExpr, env, funEnv, builtinFunEnv);
     }
  } else if(expr instanceof While) {
     while(eval(expr.cond, env, funEnv, builtinFunEnv) !== 0) {
       eval(expr.body, env, funEnv, builtinFunEnv);
     }
     return 0;
  } else if(expr instanceof FunCall) {
     const def = funEnv[expr.name] || builtinFunEnv[expr.name];
     if(!def) throw `function ${expr.name} is not defined`;

     const args = expr.args.map((a) => eval(a, env, funEnv, builtinFunEnv));

     if (def instanceof BuiltinFun) {
       return def.func(args);
     }

     const newEnv = {}
     for(let i = 0; i < def.args.length; i++) {
       newEnv[def.args[i]] = args[i];
     }
     return eval(def.body, newEnv, funEnv, builtinFunEnv);
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

const program = new Program(
  [
    new FunDef("print_add", ["x", "y"],
      new FunCall("print", 
        new FunCall("add", 
          new FunCall("mul", new VarRef("x"), new VarRef("y")),
          new Num(3)
        )
      )
    )
  ],
  new FunCall("print_add", new Num(5), new Num(3))
);

evalProgram(program);

statically-typed.js

// Base Type class
class Type {}

// Primitive types (Number, String, Boolean)
class PrimitiveType extends Type {
  constructor(name) {
    super();
    this.name = name;
  }
}

// Function types
class FunctionType extends Type {
  constructor(paramTypes, returnType) {
    super();
    this.paramTypes = paramTypes; // Array of Type
    this.returnType = returnType; // Type
  }
}

// List type
class ListType extends Type {
  constructor(elementType) {
    super();
    this.elementType = elementType; // Type
  }
}

// Dictionary type
class DictType extends Type {
  constructor(keyType, valueType) {
    super();
    this.keyType = keyType; // Type
    this.valueType = valueType; // Type
  }
}

// Type variable for parametric polymorphism
class TypeVariable extends Type {
  constructor(name) {
    super();
    this.name = name;
  }
}

// Helper functions for type variables
let typeVarCounter = 0;
function freshTypeVariable(prefix = 'T') {
  return new TypeVariable(`${prefix}${typeVarCounter++}`);
}

// Function to reset type variable counter (useful for tests)
function resetTypeVarCounter() {
  typeVarCounter = 0;
}

// Modify FunDef to include parameter types and return type
class FunDef {
  constructor(name, params, returnType, body, typeParams = []) {
    this.name = name;
    this.params = params; // Array of { name: string, type: Type }
    this.returnType = returnType; // Type
    this.body = body;
    this.typeParams = typeParams; // Array of TypeVariable
  }
}

// Base expression class
class Expression {}

// Various Expression Classes
class Assignment extends Expression {
  constructor(name, expr) {
    super();
    this.name = name;
    this.expr = expr;
  }
}

class BinExpr extends Expression {
  constructor(operator, lhs, rhs) {
    super();
    this.operator = operator;
    this.lhs = lhs;
    this.rhs = rhs;
  }
}

class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

class VarRef extends Expression {
  constructor(name) {
    super();
    this.name = name;
  }
}

class FunCall extends Expression {
  constructor(name, ...args) {
    super();
    this.name = name;
    this.args = args;
  }
}

class If extends Expression {
  constructor(cond, thenExpr, elseExpr) {
    super();
    this.cond = cond;
    this.thenExpr = thenExpr;
    this.elseExpr = elseExpr;
  }
}

class While extends Expression {
  constructor(cond, body) {
    super();
    this.cond = cond;
    this.body = body;
  }
}

class Seq extends Expression {
  constructor(...bodies) {
    super();
    this.bodies = bodies;
  }
}

class ListExpr extends Expression { // Renamed to avoid conflict with built-in List
  constructor(elements) {
    super();
    this.elements = elements;
  }
}

class StringLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

class Dict extends Expression {
  constructor(entries) {
    super();
    this.entries = entries;
  }
}

class BooleanLit extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}

// Built-in function class (modified to include types)
class BuiltinFun {
  constructor(name, func, type, typeParams = []) {
    this.name = name;
    this.func = func;
    this.type = type; // FunctionType
    this.typeParams = typeParams; // Array of TypeVariable
  }
}

// Environment Class to Unify Variables and Functions
class Environment {
  constructor() {
    this.entries = new Map(); // name -> { kind: 'variable' | 'function', type: Type | FunctionType, value | func: any }

    // Initialize Built-in Functions
    this.initializeBuiltins();
  }

  // Method to add variables
  addVariable(name, type, value = null) {
    this.entries.set(name, { kind: 'variable', type, value });
  }

  // Method to get variables
  getVariable(name) {
    const entry = this.entries.get(name);
    if (entry && entry.kind === 'variable') {
      return entry.value;
    }
    throw new Error(`Variable ${name} is not defined`);
  }

  // Method to set variable values
  setVariable(name, value) {
    const entry = this.entries.get(name);
    if (entry && entry.kind === 'variable') {
      entry.value = value;
    } else {
      throw new Error(`Variable ${name} is not defined`);
    }
  }

  // Method to add user-defined functions
  addFunction(funDef) {
    const paramTypes = funDef.params.map(param => param.type);
    const funcType = new FunctionType(paramTypes, funDef.returnType);
    this.entries.set(funDef.name, {
      kind: 'function',
      func: funDef,
      type: funcType,
      typeParams: funDef.typeParams
    });
  }

  // Method to add built-in functions
  addBuiltin(builtinFun) {
    this.entries.set(builtinFun.name, {
      kind: 'function',
      func: builtinFun,
      type: builtinFun.type,
      typeParams: builtinFun.typeParams
    });
  }

  // Method to get function information
  getFunction(name) {
    const entry = this.entries.get(name);
    if (entry && entry.kind === 'function') {
      return entry;
    }
    throw new Error(`Function ${name} is not defined`);
  }

  // Initialize built-in functions
  initializeBuiltins() {
    // Reset the type variable counter
    resetTypeVarCounter();

    // Define built-in functions
    this.addBuiltin(new BuiltinFun(
      'print',
      (args) => {
        console.log(...args);
        return args[0];
      },
      new FunctionType([freshTypeVariable('T')], freshTypeVariable('T')),
      [freshTypeVariable('T')]
    ));

    // 'len' :: forall T. (List<T> | String) -> Number
    this.addBuiltin(new BuiltinFun(
      'len',
      (args) => {
        if (args.length !== 1) throw new Error('len expects exactly one argument');
        const arg = args[0];
        if (typeof arg === 'string' || Array.isArray(arg)) {
          return arg.length;
        } else {
          throw new Error('len expects a string or array');
        }
      },
      new FunctionType([freshTypeVariable('T')], new PrimitiveType('Number')),
      [freshTypeVariable('T')]
    ));

    // 'map' :: forall T, U. (List<T>, (T) -> U) -> List<U>
    this.addBuiltin(new BuiltinFun(
      'map',
      (args, env) => {
        if (args.length !== 2)
          throw new Error('map expects exactly two arguments');
        const [lst, func] = args;
        if (!Array.isArray(lst))
          throw new Error('map expects an array as the first argument');
        return lst.map(elem => {
          return evaluateFunction(func, [elem], env, this);
        });
      },
      new FunctionType(
        [
          new ListType(freshTypeVariable('T')),
          new FunctionType([freshTypeVariable('T')], freshTypeVariable('U')),
        ],
        new ListType(freshTypeVariable('U'))
      ),
      [freshTypeVariable('T'), freshTypeVariable('U')]
    ));

    // 'filter' :: forall T. (List<T>, (T) -> Boolean) -> List<T>
    this.addBuiltin(new BuiltinFun(
      'filter',
      (args, env) => {
        if (args.length !== 2)
          throw new Error('filter expects exactly two arguments');
        const [lst, func] = args;
        if (!Array.isArray(lst))
          throw new Error('filter expects an array as the first argument');
        return lst.filter(elem => {
          return evaluateFunction(func, [elem], env, this);
        });
      },
      new FunctionType(
        [
          new ListType(freshTypeVariable('T')),
          new FunctionType([freshTypeVariable('T')], new PrimitiveType('Boolean')),
        ],
        new ListType(freshTypeVariable('T'))
      ),
      [freshTypeVariable('T')]
    ));

    // 'reduce' :: forall T, U. (List<T>, (U, T) -> U, U) -> U
    this.addBuiltin(new BuiltinFun(
      'reduce',
      (args, env) => {
        if (args.length !== 3)
          throw new Error('reduce expects exactly three arguments');
        const [lst, func, initial] = args;
        if (!Array.isArray(lst))
          throw new Error('reduce expects an array as the first argument');
        return lst.reduce((acc, elem) => {
          return evaluateFunction(func, [acc, elem], env, this);
        }, initial);
      },
      new FunctionType(
        [
          new ListType(freshTypeVariable('T')),
          new FunctionType(
            [freshTypeVariable('U'), freshTypeVariable('T')],
            freshTypeVariable('U')
          ),
          freshTypeVariable('U'),
        ],
        freshTypeVariable('U')
      ),
      [freshTypeVariable('T'), freshTypeVariable('U')]
    ));

    // 'toUpperCase' :: (String) -> String
    this.addBuiltin(new BuiltinFun(
      'toUpperCase',
      (args) => {
        if (args.length !== 1)
          throw new Error('toUpperCase expects exactly one argument');
        const str = args[0];
        if (typeof str !== 'string')
          throw new Error('toUpperCase expects a string');
        return str.toUpperCase();
      },
      new FunctionType([new PrimitiveType('String')], new PrimitiveType('String'))
    ));

    // 'split' :: (String, String) -> List<String>
    this.addBuiltin(new BuiltinFun(
      'split',
      (args) => {
        if (args.length !== 2)
          throw new Error('split expects exactly two arguments');
        const [str, separator] = args;
        if (typeof str !== 'string' || typeof separator !== 'string')
          throw new Error('split expects strings as arguments');
        return str.split(separator);
      },
      new FunctionType(
        [new PrimitiveType('String'), new PrimitiveType('String')],
        new ListType(new PrimitiveType('String'))
      )
    ));

    // 'join' :: (List<String>, String) -> String
    this.addBuiltin(new BuiltinFun(
      'join',
      (args) => {
        if (args.length !== 2)
          throw new Error('join expects exactly two arguments');
        const [lst, separator] = args;
        if (!Array.isArray(lst) || typeof separator !== 'string')
          throw new Error('join expects an array and a string');
        return lst.join(separator);
      },
      new FunctionType(
        [new ListType(new PrimitiveType('String')), new PrimitiveType('String')],
        new PrimitiveType('String')
      )
    ));

    // 'keys' :: forall V. (Dict<K, V>) -> List<K>
    this.addBuiltin(new BuiltinFun(
      'keys',
      (args) => {
        if (args.length !== 1)
          throw new Error('keys expects exactly one argument');
        const obj = args[0];
        if (typeof obj !== 'object' || obj === null || Array.isArray(obj))
          throw new Error('keys expects a dictionary');
        return Object.keys(obj);
      },
      new FunctionType(
        [new DictType(freshTypeVariable('K'), freshTypeVariable('V'))],
        new ListType(freshTypeVariable('K'))
      ),
      [freshTypeVariable('K'), freshTypeVariable('V')]
    ));

    // 'values' :: forall K, V. (Dict<K, V>) -> List<V>
    this.addBuiltin(new BuiltinFun(
      'values',
      (args) => {
        if (args.length !== 1)
          throw new Error('values expects exactly one argument');
        const obj = args[0];
        if (typeof obj !== 'object' || obj === null || Array.isArray(obj))
          throw new Error('values expects a dictionary');
        return Object.values(obj);
      },
      new FunctionType(
        [new DictType(freshTypeVariable('K'), freshTypeVariable('V'))],
        new ListType(freshTypeVariable('V'))
      ),
      [freshTypeVariable('K'), freshTypeVariable('V')]
    ));

    // 'get' :: forall K, V. (Dict<K, V>, K) -> V
    this.addBuiltin(new BuiltinFun(
      'get',
      (args) => {
        if (args.length !== 2)
          throw new Error('get expects exactly two arguments');
        const [obj, key] = args;
        if (typeof obj !== 'object' || obj === null)
          throw new Error('get expects a dictionary as the first argument');
        return obj[key];
      },
      new FunctionType(
        [new DictType(freshTypeVariable('K'), freshTypeVariable('V')), freshTypeVariable('K')],
        freshTypeVariable('V')
      ),
      [freshTypeVariable('K'), freshTypeVariable('V')]
    ));

    // 'hasKey' :: forall K, V. (Dict<K, V>, K) -> Boolean
    this.addBuiltin(new BuiltinFun(
      'hasKey',
      (args) => {
        if (args.length !== 2)
          throw new Error('hasKey expects exactly two arguments');
        const [obj, key] = args;
        if (typeof obj !== 'object' || obj === null)
          throw new Error('hasKey expects a dictionary as the first argument');
        return Object.prototype.hasOwnProperty.call(obj, key);
      },
      new FunctionType(
        [new DictType(freshTypeVariable('K'), freshTypeVariable('V')), freshTypeVariable('K')],
        new PrimitiveType('Boolean')
      ),
      [freshTypeVariable('K'), freshTypeVariable('V')]
    ));

    // 'merge' :: forall K, V. (Dict<K, V>, Dict<K, V>) -> Dict<K, V>
    this.addBuiltin(new BuiltinFun(
      'merge',
      (args) => {
        if (args.length !== 2)
          throw new Error('merge expects exactly two arguments');
        const [obj1, obj2] = args;
        if (
          typeof obj1 !== 'object' ||
          obj1 === null ||
          typeof obj2 !== 'object' ||
          obj2 === null
        )
          throw new Error('merge expects dictionaries');
        return { ...obj1, ...obj2 };
      },
      new FunctionType(
        [
          new DictType(freshTypeVariable('K'), freshTypeVariable('V')),
          new DictType(freshTypeVariable('K'), freshTypeVariable('V')),
        ],
        new DictType(freshTypeVariable('K'), freshTypeVariable('V'))
      ),
      [freshTypeVariable('K'), freshTypeVariable('V')]
    ));

    // 'and' :: (Boolean, Boolean) -> Boolean
    this.addBuiltin(new BuiltinFun(
      'and',
      (args) => {
        if (args.length !== 2)
          throw new Error('and expects exactly two arguments');
        const [a, b] = args;
        if (typeof a !== 'boolean' || typeof b !== 'boolean')
          throw new Error('and expects booleans');
        return a && b;
      },
      new FunctionType(
        [new PrimitiveType('Boolean'), new PrimitiveType('Boolean')],
        new PrimitiveType('Boolean')
      )
    ));

    // 'or' :: (Boolean, Boolean) -> Boolean
    this.addBuiltin(new BuiltinFun(
      'or',
      (args) => {
        if (args.length !== 2)
          throw new Error('or expects exactly two arguments');
        const [a, b] = args;
        if (typeof a !== 'boolean' || typeof b !== 'boolean')
          throw new Error('or expects booleans');
        return a || b;
      },
      new FunctionType(
        [new PrimitiveType('Boolean'), new PrimitiveType('Boolean')],
        new PrimitiveType('Boolean')
      )
    ));

    // 'not' :: (Boolean) -> Boolean
    this.addBuiltin(new BuiltinFun(
      'not',
      (args) => {
        if (args.length !== 1)
          throw new Error('not expects exactly one argument');
        const [a] = args;
        if (typeof a !== 'boolean')
          throw new Error('not expects a boolean');
        return !a;
      },
      new FunctionType([new PrimitiveType('Boolean')], new PrimitiveType('Boolean'))
    ));
  }

  // Check if a name exists in the environment
  has(name) {
    return this.entries.has(name);
  }
}

// Helper function to evaluate functions (user-defined or built-in)
function evaluateFunction(funcInfo, args, env, globalEnv) {
  if (funcInfo.kind === 'function') {
    if (funcInfo.func instanceof BuiltinFun) {
      return funcInfo.func.func(args, env);
    } else if (funcInfo.func instanceof FunDef) {
      const newEnv = new Map(); // New environment for function execution
      funcInfo.func.params.forEach((param, index) => {
        newEnv.set(param.name, args[index]);
      });
      return evalExpr(funcInfo.func.body, newEnv, globalEnv);
    } else {
      throw new Error('Unknown function type');
    }
  } else if (funcInfo instanceof FunDef) {
    const newEnv = new Map(); // New environment for function execution
    funcInfo.params.forEach((param, index) => {
      newEnv.set(param.name, args[index]);
    });
    return evalExpr(funcInfo.body, newEnv, globalEnv);
  } else {
    throw new Error('Attempted to call a non-function');
  }
}

// Type checking functions
function isTypeEqual(t1, t2) {
  if (t1 instanceof PrimitiveType && t2 instanceof PrimitiveType) {
    return t1.name === t2.name;
  } else if (t1 instanceof TypeVariable && t2 instanceof TypeVariable) {
    return t1.name === t2.name;
  } else if (t1 instanceof ListType && t2 instanceof ListType) {
    return isTypeEqual(t1.elementType, t2.elementType);
  } else if (t1 instanceof DictType && t2 instanceof DictType) {
    return (
      isTypeEqual(t1.keyType, t2.keyType) &&
      isTypeEqual(t1.valueType, t2.valueType)
    );
  } else if (t1 instanceof FunctionType && t2 instanceof FunctionType) {
    if (t1.paramTypes.length !== t2.paramTypes.length) {
      return false;
    }
    for (let i = 0; i < t1.paramTypes.length; i++) {
      if (!isTypeEqual(t1.paramTypes[i], t2.paramTypes[i])) {
        return false;
      }
    }
    return isTypeEqual(t1.returnType, t2.returnType);
  } else {
    return false;
  }
}

function matchTypes(t1, t2, typeSubstitution) {
  if (t1 instanceof TypeVariable) {
    const tvarName = t1.name;
    if (tvarName in typeSubstitution) {
      return matchTypes(typeSubstitution[tvarName], t2, typeSubstitution);
    } else {
      typeSubstitution[tvarName] = t2;
      return true;
    }
  } else if (t2 instanceof TypeVariable) {
    return matchTypes(t2, t1, typeSubstitution);
  } else if (t1 instanceof PrimitiveType && t2 instanceof PrimitiveType) {
    return t1.name === t2.name;
  } else if (t1 instanceof ListType && t2 instanceof ListType) {
    return matchTypes(t1.elementType, t2.elementType, typeSubstitution);
  } else if (t1 instanceof DictType && t2 instanceof DictType) {
    return (
      matchTypes(t1.keyType, t2.keyType, typeSubstitution) &&
      matchTypes(t1.valueType, t2.valueType, typeSubstitution)
    );
  } else if (t1 instanceof FunctionType && t2 instanceof FunctionType) {
    if (t1.paramTypes.length !== t2.paramTypes.length) {
      return false;
    }
    for (let i = 0; i < t1.paramTypes.length; i++) {
      if (!matchTypes(t1.paramTypes[i], t2.paramTypes[i], typeSubstitution)) {
        return false;
      }
    }
    return matchTypes(t1.returnType, t2.returnType, typeSubstitution);
  } else {
    return false;
  }
}

function substituteTypeVariables(type, typeSubstitution) {
  if (type instanceof TypeVariable) {
    const tvarName = type.name;
    if (tvarName in typeSubstitution) {
      return substituteTypeVariables(
        typeSubstitution[tvarName],
        typeSubstitution
      );
    } else {
      return type;
    }
  } else if (type instanceof ListType) {
    const elemType = substituteTypeVariables(
      type.elementType,
      typeSubstitution
    );
    return new ListType(elemType);
  } else if (type instanceof DictType) {
    const keyType = substituteTypeVariables(type.keyType, typeSubstitution);
    const valueType = substituteTypeVariables(type.valueType, typeSubstitution);
    return new DictType(keyType, valueType);
  } else if (type instanceof FunctionType) {
    const paramTypes = type.paramTypes.map(t =>
      substituteTypeVariables(t, typeSubstitution)
    );
    const returnType = substituteTypeVariables(
      type.returnType,
      typeSubstitution
    );
    return new FunctionType(paramTypes, returnType);
  } else {
    return type;
  }
}

function instantiateFunctionType(funcType, typeParams) {
  const typeSubstitution = {};
  typeParams.forEach(tp => {
    typeSubstitution[tp.name] = freshTypeVariable(tp.name);
  });
  const instantiatedType = substituteTypeVariables(funcType, typeSubstitution);
  return instantiatedType;
}

function matchFunctionTypes(funcType, argTypes, typeSubstitution) {
  if (funcType.paramTypes.length !== argTypes.length) {
    return false;
  }
  for (let i = 0; i < argTypes.length; i++) {
    if (!matchTypes(funcType.paramTypes[i], argTypes[i], typeSubstitution)) {
      return false;
    }
  }
  return true;
}

function typeCheck(expr, typeEnv, env) {
  if (expr instanceof BinExpr) {
    const leftType = typeCheck(expr.lhs, typeEnv, env);
    const rightType = typeCheck(expr.rhs, typeEnv, env);
    const operator = expr.operator;

    // Type checking for binary expressions
    if (['+', '-', '*', '/', '%'].includes(operator)) {
      if (
        isTypeEqual(leftType, new PrimitiveType('Number')) &&
        isTypeEqual(rightType, new PrimitiveType('Number'))
      ) {
        return new PrimitiveType('Number');
      } else if (
        operator === '+' &&
        isTypeEqual(leftType, new PrimitiveType('String')) &&
        isTypeEqual(rightType, new PrimitiveType('String'))
      ) {
        return new PrimitiveType('String');
      } else if (
        operator === '+' &&
        leftType instanceof ListType &&
        rightType instanceof ListType &&
        isTypeEqual(leftType.elementType, rightType.elementType)
      ) {
        return new ListType(leftType.elementType);
      } else {
        throw new Error(
          `Unsupported operand types for ${operator}: ${leftType.name} and ${rightType.name}`
        );
      }
    } else if (['<', '>', '<=', '>=', '==', '!='].includes(operator)) {
      return new PrimitiveType('Boolean');
    } else {
      throw new Error(`Unsupported operator: ${operator}`);
    }
  } else if (expr instanceof Num) {
    return new PrimitiveType('Number');
  } else if (expr instanceof StringLit) {
    return new PrimitiveType('String');
  } else if (expr instanceof BooleanLit) {
    return new PrimitiveType('Boolean');
  } else if (expr instanceof VarRef) {
    if (typeEnv.has(expr.name)) {
      return typeEnv.get(expr.name);
    }
    try {
      const funcInfo = env.getFunction(expr.name);
      if (funcInfo.type) {
        return funcInfo.type;
      }
    } catch (e) {
      // Not a function
    }
    throw new Error(`Variable or function ${expr.name} is not defined`);
  } else if (expr instanceof Assignment) {
    const exprType = typeCheck(expr.expr, typeEnv, env);
    typeEnv.set(expr.name, exprType);
    env.addVariable(expr.name, exprType);
    return exprType;
  } else if (expr instanceof Seq) {
    let resultType = null;
    for (let e of expr.bodies) {
      resultType = typeCheck(e, typeEnv, env);
    }
    return resultType;
  } else if (expr instanceof If) {
    const condType = typeCheck(expr.cond, typeEnv, env);
    if (!isTypeEqual(condType, new PrimitiveType('Boolean'))) {
      throw new Error('Condition expression must be Boolean');
    }
    const thenType = typeCheck(expr.thenExpr, typeEnv, env);
    const elseType = typeCheck(expr.elseExpr, typeEnv, env);
    if (!isTypeEqual(thenType, elseType)) {
      throw new Error('Types of then and else branches must be the same');
    }
    return thenType;
  } else if (expr instanceof While) {
    const condType = typeCheck(expr.cond, typeEnv, env);
    if (!isTypeEqual(condType, new PrimitiveType('Boolean'))) {
      throw new Error('Condition expression must be Boolean');
    }
    typeCheck(expr.body, typeEnv, env);
    return null;
  } else if (expr instanceof FunCall) {
    const funcInfo = env.getFunction(expr.name);
    let funcType = funcInfo.type;
    if (funcInfo.typeParams && funcInfo.typeParams.length > 0) {
      funcType = instantiateFunctionType(funcType, funcInfo.typeParams);
    }
    const argTypes = expr.args.map(arg => typeCheck(arg, typeEnv, env));
    const typeSubstitution = {};
    if (!matchFunctionTypes(funcType, argTypes, typeSubstitution)) {
      throw new Error(`Argument types do not match for function ${expr.name}`);
    }
    const returnType = substituteTypeVariables(
      funcType.returnType,
      typeSubstitution
    );
    return returnType;
  } else if (expr instanceof ListExpr) {
    if (expr.elements.length === 0) {
      throw new Error('Cannot infer type of empty list');
    }
    const elemTypes = expr.elements.map(elem => typeCheck(elem, typeEnv, env));
    const firstElemType = elemTypes[0];
    for (let t of elemTypes) {
      if (!isTypeEqual(t, firstElemType)) {
        throw new Error('All elements of the list must have the same type');
      }
    }
    return new ListType(firstElemType);
  } else if (expr instanceof Dict) {
    if (expr.entries.length === 0) {
      throw new Error('Cannot infer type of empty dictionary');
    }
    const keyTypes = [];
    const valueTypes = [];
    for (let entry of expr.entries) {
      const keyType = typeCheck(entry.key, typeEnv, env);
      const valueType = typeCheck(entry.value, typeEnv, env);
      keyTypes.push(keyType);
      valueTypes.push(valueType);
    }
    const firstKeyType = keyTypes[0];
    const firstValueType = valueTypes[0];
    for (let t of keyTypes) {
      if (!isTypeEqual(t, firstKeyType)) {
        throw new Error('All keys of the dictionary must have the same type');
      }
    }
    for (let t of valueTypes) {
      if (!isTypeEqual(t, firstValueType)) {
        throw new Error('All values of the dictionary must have the same type');
      }
    }
    return new DictType(firstKeyType, firstValueType);
  } else {
    throw new Error(`Unknown expression type: ${expr.constructor.name}`);
  }
}

function typeCheckFunction(def, env) {
  const typeEnv = new Map();
  def.params.forEach(param => {
    typeEnv.set(param.name, param.type);
  });
  const bodyType = typeCheck(def.body, typeEnv, env);
  if (!isTypeEqual(bodyType, def.returnType)) {
    throw new Error(`Return type mismatch in function ${def.name}`);
  }
}

function typeCheckProgram(program, env) {
  // Process function definitions
  for (let def of program.defs) {
    env.addFunction(def);
  }

  // Type check function bodies
  for (let def of program.defs) {
    typeCheckFunction(def, env);
  }

  // Type check expressions
  const typeEnv = new Map();
  for (let expr of program.expressions) {
    typeCheck(expr, typeEnv, env);
  }
}

// The Program class
class Program {
  constructor(defs, ...expressions) {
    this.defs = defs;
    this.expressions = expressions;
  }
}

// Evaluate the program
function evalProgram(program, env) {
  const evaluationEnv = new Map(); // Variable environment
  for(let def of program.defs) {
    evaluationEnv.set(def.name, def);
  }

  let result = null;
  for (let expr of program.expressions) {
    result = evalExpr(expr, evaluationEnv, env);
  }

  return result;
}

function evalExpr(expr, env, globalEnv) {
  if (expr instanceof BinExpr) {
    const resultL = evalExpr(expr.lhs, env, globalEnv);
    const resultR = evalExpr(expr.rhs, env, globalEnv);
    switch (expr.operator) {
      case '+':
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL + resultR;
        } else if (typeof resultL === 'string' || typeof resultR === 'string') {
          return String(resultL) + String(resultR);
        } else if (Array.isArray(resultL) && Array.isArray(resultR)) {
          return resultL.concat(resultR);
        } else {
          throw new Error(
            `Unsupported operand types for +: ${typeof resultL} and ${typeof resultR}`
          );
        }
      case '-':
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL - resultR;
        } else {
          throw new Error(
            `Unsupported operand types for -: ${typeof resultL} and ${typeof resultR}`
          );
        }
      case '*':
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL * resultR;
        } else {
          throw new Error(
            `Unsupported operand types for *: ${typeof resultL} and ${typeof resultR}`
          );
        }
      case '/':
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL / resultR;
        } else {
          throw new Error(
            `Unsupported operand types for /: ${typeof resultL} and ${typeof resultR}`
          );
        }
      case '%':
        if (typeof resultL === 'number' && typeof resultR === 'number') {
          return resultL % resultR;
        } else {
          throw new Error(
            `Unsupported operand types for %: ${typeof resultL} and ${typeof resultR}`
          );
        }
      case '<':
        return resultL < resultR;
      case '>':
        return resultL > resultR;
      case '<=':
        return resultL <= resultR;
      case '>=':
        return resultL >= resultR;
      case '==':
        return resultL === resultR;
      case '!=':
        return resultL !== resultR;
      default:
        throw new Error(`Unsupported operator: ${expr.operator}`);
    }
  } else if (expr instanceof Num) {
    return expr.value;
  } else if (expr instanceof StringLit) {
    return expr.value;
  } else if (expr instanceof BooleanLit) {
    return expr.value;
  } else if (expr instanceof VarRef) {
    if (env.has(expr.name)) {
      return env.get(expr.name);
    }
    try {
      const funcInfo = globalEnv.getFunction(expr.name);
      if (funcInfo.kind === 'function' && funcInfo.func instanceof BuiltinFun) {
        return funcInfo;
      } else {
        throw new Error(`Function ${expr.name} cannot be used as a variable`);
      }
    } catch (e) {
      throw new Error(`Variable or function ${expr.name} is not defined`);
    }
  } else if (expr instanceof Assignment) {
    const result = evalExpr(expr.expr, env, globalEnv);
    env.set(expr.name, result);
    globalEnv.setVariable(expr.name, result);
    return result;
  } else if (expr instanceof Seq) {
    let result = null;
    for (let e of expr.bodies) {
      result = evalExpr(e, env, globalEnv);
    }
    return result;
  } else if (expr instanceof If) {
    if (evalExpr(expr.cond, env, globalEnv)) {
      return evalExpr(expr.thenExpr, env, globalEnv);
    } else {
      return evalExpr(expr.elseExpr, env, globalEnv);
    }
  } else if (expr instanceof While) {
    while (evalExpr(expr.cond, env, globalEnv)) {
      evalExpr(expr.body, env, globalEnv);
    }
    return null;
  } else if (expr instanceof FunCall) {
    const funcInfo = globalEnv.getFunction(expr.name);
    const args = expr.args.map(a => evalExpr(a, env, globalEnv));
    return evaluateFunction(funcInfo, args, env, globalEnv);
  } else if (expr instanceof ListExpr) {
    return expr.elements.map(e => evalExpr(e, env, globalEnv));
  } else if (expr instanceof Dict) {
    const result = {};
    for (let entry of expr.entries) {
      const evalKey = evalExpr(entry.key, env, globalEnv);
      const evalValue = evalExpr(entry.value, env, globalEnv);
      result[evalKey] = evalValue;
    }
    return result;
  } else {
    throw new Error(`Unknown expression type: ${expr.constructor.name}`);
  }
}

// The example program with types
const program = new Program(
  [
    // Define a function to double a number
    new FunDef(
      'double',
      [{ name: 'x', type: new PrimitiveType('Number') }],
      new PrimitiveType('Number'),
      new BinExpr('*', new VarRef('x'), new Num(2))
    ),
    // Define a function to check if a number is even
    new FunDef(
      'isEven',
      [{ name: 'x', type: new PrimitiveType('Number') }],
      new PrimitiveType('Boolean'),
      new BinExpr(
        '==',
        new BinExpr('%', new VarRef('x'), new Num(2)),
        new Num(0)
      )
    ),
    // Define a reducer function to sum numbers
    new FunDef(
      'sum',
      [
        { name: 'a', type: new PrimitiveType('Number') },
        { name: 'b', type: new PrimitiveType('Number') },
      ],
      new PrimitiveType('Number'),
      new BinExpr('+', new VarRef('a'), new VarRef('b'))
    ),
  ],
  new Seq(
    // Working with Lists
    new Assignment(
      'numbers',
      new ListExpr([new Num(1), new Num(2), new Num(3), new Num(4)])
    ),
    new Assignment(
      'doubledNumbers',
      new FunCall('map', new VarRef('numbers'), new VarRef('double'))
    ),
    new FunCall('print', new VarRef('doubledNumbers')), // Output: [2, 4, 6, 8]
    new Assignment(
      'evenNumbers',
      new FunCall('filter', new VarRef('numbers'), new VarRef('isEven'))
    ),
    new FunCall('print', new VarRef('evenNumbers')), // Output: [2, 4]
    new Assignment(
      'total',
      new FunCall('reduce', new VarRef('numbers'), new VarRef('sum'), new Num(0))
    ),
    new FunCall('print', new VarRef('total')), // Output: 10

    // Working with Strings
    new Assignment('greeting', new StringLit('Hello, World!')),
    new Assignment(
      'uppercaseGreeting',
      new FunCall('toUpperCase', new VarRef('greeting'))
    ),
    new FunCall('print', new VarRef('uppercaseGreeting')), // Output: "HELLO, WORLD!"
    new Assignment(
      'words',
      new FunCall('split', new VarRef('greeting'), new StringLit(', '))
    ),
    new FunCall('print', new VarRef('words')), // Output: ["Hello", "World!"]
    new Assignment(
      'joinedWords',
      new FunCall('join', new VarRef('words'), new StringLit(' - '))
    ),
    new FunCall('print', new VarRef('joinedWords')), // Output: "Hello - World!"

    // Working with Dictionaries
    new Assignment(
      'person',
      new Dict([
        { key: new StringLit('name'), value: new StringLit('Alice') },
        { key: new StringLit('age'), value: new StringLit('30') }, // Changed from StringLit to Num for consistency
      ])
    ),
    new FunCall('print', new FunCall('keys', new VarRef('person'))), // Output: ["name", "age"]
    new FunCall('print', new FunCall('values', new VarRef('person'))), // Output: ["Alice", 30]
    new FunCall(
      'print',
      new FunCall('get', new VarRef('person'), new StringLit('name'))
    ), // Output: "Alice"
    new FunCall(
      'print',
      new FunCall('hasKey', new VarRef('person'), new StringLit('email'))
    ), // Output: false
    new Assignment(
      'additionalInfo',
      new Dict([
        { key: new StringLit('email'), value: new StringLit('[email protected]') },
      ])
    ),
    new Assignment(
      'updatedPerson',
      new FunCall('merge', new VarRef('person'), new VarRef('additionalInfo'))
    ),
    new FunCall('print', new VarRef('updatedPerson')),
    // Output: { name: "Alice", age: 30, email: "[email protected]" }

    // Working with Booleans
    new Assignment('bool1', new BooleanLit(true)),
    new Assignment('bool2', new BooleanLit(false)),
    new FunCall(
      'print',
      new FunCall('and', new VarRef('bool1'), new VarRef('bool2'))
    ), // Output: false
    new FunCall(
      'print',
      new FunCall('or', new VarRef('bool1'), new VarRef('bool2'))
    ), // Output: true
    new FunCall('print', new FunCall('not', new VarRef('bool2'))) // Output: true
  )
);


// Create a new Environment instance
const globalEnv = new Environment();

// Type Check the program
typeCheckProgram(program, globalEnv);

// Evaluate the program
evalProgram(program, globalEnv);