Lang in JS

statically-typed-lang.js

const readline = require('readline');
const fs = require('fs');
const readLineSync = require('readline-sync');
const { type } = require('os');
function input(prompt) {
  return readLineSync.question(prompt);
}

function arrayEquals(arr1, arr2) {
  return (
      Array.isArray(arr1) &&
      Array.isArray(arr2) &&
      arr1.length === arr2.length &&
      arr1.every((value, index) => value === arr2[index])
  );
}

//プログラム全体
class Program {
  constructor(defs, ...expressions){
    this.defs = defs;
    this.expressions = expressions;
  }
}
//関数定義を表すクラス
class FunDef {
  constructor(name, args, returnType, body) {
    this.name = name;
    this.args = args;
    this.returnType = returnType;
    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;
  }
}
// 単項演算子（not）のためのクラス
class UnaryExpr extends Expression {
  constructor(operator, expr) {
    super();
    this.operator = operator;
    this.expr = expr;
  }
}
// 整数値のためのクラス
class Num extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 真偽値のためのクラス
class Bool extends Expression {
  constructor(value) {
    super();
    this.value = value;
  }
}
// 文字列のためのクラス
class Str 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;
  }
}

class Type {
  constructor(name) {
    this.name = name;
  }
  equals(other) {
    return this.name === other.name;
  }
  toString() {
    return `Type(${this.name})`;
  }
}
class FunctionType {
  constructor(argTypes, returnType) {
    this.argTypes = argTypes;
    this.returnType = returnType;
  }
  equals(other) {
    return arrayEquals(this.argTypes, other.argTypes) && this.returnType.equals(other.returnType);
  } 
  toString() {
    return `FunctionType(${this.argTypes} -> ${this.returnType})`;
  }
}

const INT_TYPE = new Type("int");
const BOOLEAN_TYPE = new Type("boolean");
const STRING_TYPE = new Type("string");
function typeFromName(name) {
  switch(name) {
    case "int":
      return INT_TYPE;
    case "boolean":
      return BOOLEAN_TYPE;
    case "string":
      return STRING_TYPE;
  }
}

function translateExpr(jsonObject) {
  if(Array.isArray(jsonObject)) {
    const operator = jsonObject[0];
    switch(operator) {
      case "+":
        return new BinExpr("+", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "-":
        return new BinExpr("-", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "*":
        return new BinExpr("*", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "/":
        return new BinExpr("/", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "%":
        return new BinExpr("%", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<":
        return new BinExpr("<", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case ">":
        return new BinExpr(">", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<=":
        return new BinExpr("<=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case ">=":
        return new BinExpr(">=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "==":
        return new BinExpr("==", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "!=":
        return new BinExpr("!=", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "and":
        return new BinExpr("and", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "or":
        return new BinExpr("or", translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "not":
        return new UnaryExpr("not", translateExpr(jsonObject[1]));
      case "seq":
        return new Seq(...jsonObject.slice(1).map(translateExpr));
      case "if":
        return new If(translateExpr(jsonObject[1]), translateExpr(jsonObject[2]), translateExpr(jsonObject[3]));
      case "while":
        return new While(translateExpr(jsonObject[1]), translateExpr(jsonObject[2]));
      case "<-":
        return new Assignment(jsonObject[1], translateExpr(jsonObject[2]));
      case "ref":
        return new VarRef(jsonObject[1]);
      case "call":
        return new FunCall(jsonObject[1], ...jsonObject.slice(2).map(translateExpr));
    }
  }
  switch (typeof jsonObject) {
    case "number":
      return new Num(jsonObject);
    case "string":
      return new Str(jsonObject);
    case "boolean":
      return new Bool(jsonObject);
  }
  throw "Not implemented for: " + JSON.stringify(jsonObject);
}

/* 
 * {"functions": [
 *    ["factorial", [["n": "int"], "int",
 *      ["if", ["==", "n", 0], 
 *         1, 
 *         ["*", "n", ["call", "factorial", ["-", "n", 1]]]]]],
 *     ...
 *  ], 
 *  "body": ["call", "factorial", 5]
 * }
 */
function translateProgram(jsonProgram) {
  const defs = jsonProgram['functions'].map(f => 
    new FunDef(f[0], f[1], f[2], translateExpr(f[3]))
  );
  const body = translateExpr(jsonProgram['body']);
  return new Program(defs, body);
}

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

function evalJsonProgram(jsonString) {
    const jsonProgram = JSON.parse(jsonString);
    const program = translateProgram(jsonProgram);
    typeCheckProgram(program);
    return evalProgram(program);
}

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;
      case "<":
        return resultL < resultR;
      case ">":
        return resultL > resultR;
      case "<=":
        return resultL <= resultR;
      case ">=":
        return resultL >= resultR;
      case "==":
        return resultL === resultR;
      case "!=":
        return resultL !== resultR;
      case "and":
        return resultL && resultR;
      case "or":
        return resultL || resultR;
    }
  } else if(expr instanceof UnaryExpr) {
    const result = eval(expr.expr, env, funEnv, builtinFunEnv);
    switch(expr.operator) {
      case "not":
        return !result;
    }
  } else if(expr instanceof Num) {
     return expr.value;
  } else if(expr instanceof Bool) {
     return expr.value;
  } else if(expr instanceof Str) {
     return expr.value;
  } else if(expr instanceof VarRef) {
     if (!(expr.name in env)) {
       throw `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 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][0]] = args[i];
     }
     return eval(def.body, newEnv, funEnv, builtinFunEnv);
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

function typeCheck(expr, typeEnv) {
  if(expr instanceof BinExpr) {
    const typeL = typeCheck(expr.lhs, typeEnv);
    const typeR = typeCheck(expr.rhs, typeEnv);
    switch(expr.operator) {
      case "+":
      case "-":
      case "*":
      case "/":
      case "%":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Type error. Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE} actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return INT_TYPE;
      case "<":
      case ">":
      case "<=":
      case ">=":
        if(!typeL.equals(INT_TYPE) || !typeR.equals(INT_TYPE)) {
          throw `Type error. Required: ${INT_TYPE} ${expr.operator} ${INT_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
      case "==":
      case "!=":
        if(!typeL.equals(typeR)) {
          throw `Type error. Left and right must be equal. actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE
      case "and":
      case "or":
        if(!typeL.equals(BOOLEAN_TYPE) || !typeR.equals(BOOLEAN_TYPE)) {
          throw `Type error. Required: ${BOOLEAN_TYPE} ${expr.operator} ${BOOLEAN_TYPE}, actual: ${typeL} ${expr.operator} ${typeR}`;
        }
        return BOOLEAN_TYPE;
    }
  } else if(expr instanceof UnaryExpr) {
    const typeL = typeCheck(expr.expr, typeEnv);
    switch(expr.operator) {
      case "not":
        if(!typeL.equals(BOOLEAN_TYPE)) {
          throw `Type error. Required: not ${BOOLEAN_TYPE}, actual: not ${typeL}`;
        }
        return BOOLEAN_TYPE;
    }
  } else if(expr instanceof Num) {
    return INT_TYPE;
  } else if(expr instanceof Bool) {
    return BOOLEAN_TYPE;
  } else if(expr instanceof Str) {
    return STRING_TYPE;
  } else if(expr instanceof VarRef) {
     if (!(expr.name in typeEnv)) {
       throw `variable ${expr.name} is not defined`;
     }
     return typeEnv[expr.name];
  } else if(expr instanceof Assignment) {
     const valueType = typeCheck(expr.expr, typeEnv);
     const name = expr.name;
     if(!(name in typeEnv)) {
       typeEnv[name] = valueType;
       return valueType;
     }
     if(!typeEnv[name].equals(valueType)) {
         throw `Type error in re-assignment. Since the variable ${name} is declared as ${typeEnv[name]}, ${valueType} cannot be assigned`;
     }
     return valueType;
  } else if(expr instanceof Seq) {
     let resultType;
     expr.bodies.forEach((e) => {
        resultType = typeCheck(e, typeEnv);
     });
     return resultType;
  } else if(expr instanceof If) {
      const condType = typeCheck(expr.cond, typeEnv);
      if(!condType.equals(BOOLEAN_TYPE)) {
          throw `Type error. Required: ${BOOLEAN_TYPE}, actual: ${condType}`;
      }
      const thenType = typeCheck(expr.thenExpr, typeEnv);
      const elseType = typeCheck(expr.elseExpr, typeEnv);
      if(!thenType.equals(elseType)) {
         throw `Type error. Then and else must be equal. Actual: ${thenType} != ${elseType}`;
      }
      return thenType;
  } else if(expr instanceof While) {
      const condType = typeCheck(expr.cond, typeEnv);
      if(!condType.equals(BOOLEAN_TYPE)) {
          throw `Type error.  Required: ${BOOLEAN_TYPE}, actual: ${condType}`;
      }
      const bodyType = typeCheck(expr.body, typeEnv);
      return INT_TYPE;
  } else if(expr instanceof FunCall) {
    const targetType = typeEnv[expr.name]
    if(!(targetType instanceof FunctionType)) {
      throw `Type error. Type ${expr.name} is required to function.  Actual: ${targetType}`;
    }
    const argTypes = expr.args.map((a) => typeCheck(a, typeEnv));
    if(targetType.argTypes.length !== argTypes.length) {
      throw `Type error. Required: ${targetType.argTypes.length} arguments, actual: ${argTypes.length} arguments`;
    }
    for(let i = 0; i < targetType.argTypes.length; i++) {
      if(!targetType.argTypes[i].equals(argTypes[i])) {
        throw `Type error. Required: ${targetType.argTypes[i]}, actual: ${argTypes[i]}`;
      }
    }
    return targetType.returnType;
  } else {
     console.assert(false, `should not reach here ${expr}`);
  }
}

function typeCheckProgram(program) {
  const typeEnv = {
    'print': new FunctionType([STRING_TYPE], STRING_TYPE),
    'input': new FunctionType([STRING_TYPE], STRING_TYPE),
    'concat': new FunctionType([STRING_TYPE, STRING_TYPE], STRING_TYPE),
    'parseInt': new FunctionType([STRING_TYPE], INT_TYPE),
    'add': new FunctionType([INT_TYPE, INT_TYPE], INT_TYPE),
    'mul': new FunctionType([INT_TYPE, INT_TYPE], INT_TYPE),
    'length': new FunctionType([STRING_TYPE], INT_TYPE),
    'charAt': new FunctionType([STRING_TYPE, INT_TYPE], STRING_TYPE),
    'slice': new FunctionType([STRING_TYPE, INT_TYPE, INT_TYPE], STRING_TYPE),
    'intToString': new FunctionType([INT_TYPE], STRING_TYPE),
  };

  program.defs.forEach((def) => {
    typeEnv[def.name] = new FunctionType(
      def.args.map((arg) => typeFromName(arg[1])),
      typeFromName(def.returnType)
    );
  });

  program.defs.forEach((def) => {
    const localEnv = { ...typeEnv };
    def.args.forEach((arg) => {
      localEnv[arg[0]] = typeFromName(arg[1]);
    });

    const bodyType = typeCheck(def.body, localEnv);
    const expectedType = typeFromName(def.returnType);

    if (!bodyType.equals(expectedType)) {
      throw `Function ${def.name} expected return type ${expectedType}, but got ${bodyType}`;
    }
  });

  let result = null;
  program.expressions.forEach((e) => {
    result = typeCheck(e, typeEnv);
  });
  return result;
}

try {
  const program = fs.readFileSync(process.argv[2], 'utf8');
  evalJsonProgram(program);
} catch (err) {
  console.error('Error reading the file:', err);
}