JS 筆記#12 - 創造一個程式語言 Egg

{
  type: "apply",
  operator: { type: "word", name: ">" },
  args: [
    { type: "word", name: "x" },
    { type: "value", value: 5 }
  ]
}

// (program: string) => {expr: ExpressionNode, rest: string}
// ExpressionNode = 
//   | {type: "value", value: string | number}
//   | {type: "word", name: string}
//   | {type: "apply", operator: ExpressionNode, args: ExpressionNode[]}
function parseExpression(program) {
  program = skipSpace(program);
  let match, expr;

  // 解析字串
  if (match = /^"([^"]*)"/.exec(program)) {
    expr = {type: "value", value: match[1]};
  }
  // 解析數字
  else if (match = /^\d+\b/.exec(program)) {
    expr = {type: "value", value: Number(match[0])};
  }
  // 解析變數名稱
  else if (match = /^[^\s(),#"]+/.exec(program)) {
    expr = {type: "word", name: match[0]};
  }
  // 語法錯誤
  else {
    throw new SyntaxError("Unexpected syntax: " + program);
  }
  // 檢查表達式後是否有 apply（函數調用）
  return parseApply(expr, program.slice(match[0].length));
}

// 移除字串開頭的所有空白字元
// (string: string) => string
function skipSpace(string) {
  let first = string.search(/\S/);
  if (first == -1) return "";
  return string.slice(first);
}

// (expr: ExpressionNode, program: string) => {expr: ExpressionNode, rest: string}
// ExpressionNode = 
//   | {type: "value", value: string | number}
//   | {type: "word", name: string}
//   | {type: "apply", operator: ExpressionNode, args: ExpressionNode[]}
function parseApply(expr, program) {
  program = skipSpace(program);
  // 如果下一個字元不是左括號，則不是 apply
  if (program[0] != "(") {
    return {expr: expr, rest: program};
  }
  // 解析 apply 表達式
  program = skipSpace(program.slice(1));
  expr = {type: "apply", operator: expr, args: []};
  // 解析參數列表
  while (program[0] != ")") {
    let arg = parseExpression(program);
    expr.args.push(arg.expr);
    program = skipSpace(arg.rest);
    // 處理參數分隔字元
    if (program[0] == ",") {
      program = skipSpace(program.slice(1));
    } else if (program[0] != ")") {
      throw new SyntaxError("Expected ',' or ')'");
    }
  }
  // 檢查是否有連續的 apply，如 f(x)(y)
  return parseApply(expr, program.slice(1));
}

// (program: string) => ExpressionNode
function parse(program) {
  let {expr, rest} = parseExpression(program);
  if (skipSpace(rest).length > 0) {
    throw new SyntaxError("Unexpected text after program");
  }
  return expr;
}

console.log(parse("+(a, 10)"));
// → {type: "apply",
// operator: {type: "word", name: "+"},
// args: [{type: "word", name: "a"},
// {type: "value", value: 10}]}

// 儲存特殊形式（如 if、while 等語言結構）的對象
// specialForms: Object
const specialForms = Object.create(null);

// 對給定的表達式進行求值，根據不同的表達式類型執行不同的操作
// (expr: ExpressionNode, scope: Object) => any
// ExpressionNode = 
//   | {type: "value", value: any}
//   | {type: "word", name: string}
//   | {type: "apply", operator: ExpressionNode, args: ExpressionNode[]}
function evaluate(expr, scope) {
  // 如果表達式是 value 表達式，直接返回其值
  if (expr.type == "value") {
    return expr.value;
  }
  // 如果表達式是 word 表達式，從作用域中查找對應的綁定，如果存在則返回其值，否則拋出錯誤
  else if (expr.type == "word") {
    if (expr.name in scope) {
      return scope[expr.name];
    } else {
      throw new ReferenceError(
        `Undefined binding: ${expr.name}`);
    }
  }
  // 如果表達式是 apply 表達式，根據不同的情況執行不同的操作
  // 如果是特殊形式（如 if、while 等），使用對應的特殊形式處理函數
  // 如果是普通函數調用，先評估運算子，確認它是函數，然後用評估後的參數調用它
  // 如果運算子不是函數，拋出錯誤
  else if (expr.type == "apply") {
    let {operator, args} = expr;
    if (operator.type == "word" &&
        operator.name in specialForms) {
      return specialForms[operator.name](expr.args, scope);
    } else {
      let op = evaluate(operator, scope);
      if (typeof op == "function") {
        // 對每個參數調用 evaluate 函數，將結果作為參數傳遞給 op 函數
        return op(...args.map(arg => evaluate(arg, scope)));
      } else {
        throw new TypeError("Applying a non-function.");
      }
    }
  }
}

// (args: ExpressionNode[], scope: Object) => any
specialForms.if = (args, scope) => {
  if (args.length != 3) {
    throw new SyntaxError("Wrong number of args to if");
  } else if (evaluate(args[0], scope) !== false) {
    return evaluate(args[1], scope);
  } else {
    return evaluate(args[2], scope);
  }
};

// (args: ExpressionNode[], scope: Object) => false
specialForms.while = (args, scope) => {
  if (args.length != 2) {
    throw new SyntaxError("Wrong number of args to while");
  }
  while (evaluate(args[0], scope) !== false) {
    evaluate(args[1], scope);
  }

  // 因為 Egg 中沒有 undefined，我們返回 false,
  return false;
};

// (args: ExpressionNode[], scope: Object) => any || false
specialForms.do = (args, scope) => {
  let value = false;
  for (let arg of args) {
    value = evaluate(arg, scope);
  }
  return value;
};

// (args: ExpressionNode[], scope: Object) => any
specialForms.define = (args, scope) => {
  if (args.length != 2 || args[0].type != "word") {
    throw new SyntaxError("Incorrect use of define");
  }
  let value = evaluate(args[1], scope);
  scope[args[0].name] = value;
  return value;
};

// (args: ExpressionNode[], scope: Object) => Function
specialForms.fun = (args, scope) => {
  // 檢查是否提供了函數體
  if (!args.length) {
    throw new SyntaxError("Functions need a body");
  }
  
  // 提取函數體（最後一個參數）
  let body = args[args.length - 1];
  
  // 提取並驗證參數名（除最後一個參數外的所有參數）
  let params = args.slice(0, args.length - 1).map(expr => {
    // 確保參數名是 word 類型
    if (expr.type != "word") {
      throw new SyntaxError("Parameter names must be words");
    }
    return expr.name;
  });
  
  // 返回一個函數，該函數在調用時會創建新的作用域並執行函數體
  return function(...args) {
    // 檢查參數數量是否匹配
    if (args.length != params.length) {
      throw new TypeError("Wrong number of arguments");
    }
    
    // 創建一個新的本地作用域，原型鏈接到定義函數時的作用域
    let localScope = Object.create(scope);
    
    // 將參數綁定到本地作用域
    for (let i = 0; i < args.length; i++) {
      localScope[params[i]] = args[i];
    }
    
    // 在本地作用域中評估函數體並返回結果
    return evaluate(body, localScope);
  };
};

run(`
do(define(plusOne, fun(a, +(a, 1))),
   print(plusOne(10)))
`);
// → 11

// 創建一個沒有原型的全局作用域對象
// 使用 Object.create(null) 確保沒有繼承任何屬性
const topScope = Object.create(null);

// 在全局作用域中定義 Boolean 值
// 由於 Boolean 只有兩個，我們不需要為它們創建特殊語法，直接將它們綁定到名稱上即可
topScope.true = true;
topScope.false = false;

// 為全局作用域添加基本算術和比較運算子
// 使用 Function 構造函數動態創建運算符函數
for (let op of ["+", "-", "*", "/", "==", "<", ">"]) {
  // 為每個運算子創建一個接受兩個參數的函數
  // 例如：對於 "+"，創建的函數等同於 (a, b) => a + b
  topScope[op] = Function("a, b", `return a ${op} b;`);
}

// 添加輸出函數，將 console.log 包裝成 Egg 語言的 print 函數
// 該函數輸出值並返回該值，以便在表達式中使用
topScope.print = value => {
  console.log(value);
  return value;
};

// 提供一個方便的方式來解析和執行 Egg 程序
// (program: string) => any
function run(program) {
  // 1. parse 解析程式文本為表達式樹
  // 2. 創建一個新的作用域，並將原型鏈接到全局作用域
  // 3. 在新作用域中評估表達式樹
  return evaluate(parse(program), Object.create(topScope));
}

run(`
do(define(total, 0),
   define(count, 1),
   while(<(count, 11),
         do(define(total, +(total, count)),
            define(count, +(count, 1)))),
   print(total))
`);
// → 55