解釋器 - 閉包如何捕獲它的名字？

Question

在Haskell考慮以下代碼：

let factorial n = if n < 2 then 1 else n * factorial (n-1) in factorial 3 

我看到這個解釋在這樣的順序評估程序：

1. 這是一個結合。首先評估定義並評估「in」之後的部分。
2. 這是一個定義。評估身體，然後將身體與名稱關聯起來。
3. 這是一個lambda。捕捉環境，關閉並返回。
4. 定義的主體被評估，現在寫入名字。
5. 評估定義，評估表達式的正確部分。
6. 評估表達式，返回結果。

我看到這個模型的下列問題：在第3步，當閉包捕獲環境時，它不知道任何關於「階乘」綁定。

我正在爲JavaScript寫ML語言的解釋器，我偶然發現了這個問題。例如，以下語言爲我的語言：

fac = \x -> if (== x, 0) { 1 } else { fac (- x, 1) } in fac 3 

由於所描述的問題而不起作用。

其他語言的解釋器如何解決此問題？

下面是解釋器的代碼供參考。

"use strict"; 

const grammar = 
` 
Expression "expression" 
    = Condition 
/Application 
/Lambda 
/Binding 
/Integer 
/String 
/Identifier 
/'(' expr: Expression ')' { return expr; } 

_ "whitespace" 
    = [ \\t\\n\\r\\n]* 

Integer "integer" 
    = [0-9]+ { 
    return { type: 'literal', 
      literalType: 'Integer', 
      value: parseInt(text(), 10) 
      }; 
    } 

String "string" 
= '\"' value: ([^\"]* { return text(); }) '\"' { 
    return { type: 'literal', 
      literalType: 'String', 
      value: value 
      }; 
    } 

Letter 
    = [a-zA-Z] 

Identifier 
    = (Letter/'+'/'-'/'*'/'/'/'_'/'=='/'>'/'<')+ { 
    return { 
     type: 'identifier', 
     value: text() 
    } 
    } 

Application 
    = id: Identifier _ args: ActualArguments { 
    return { type: 'application', 
      fun: id, 
      args: args 
      } 
    } 
/lambda: ('(' l: Lambda ')' { return l; }) _ args: ActualArguments { 
    return { type: 'application', 
      fun: lambda, 
      args: args 
      } 
    } 

ActualArguments 
= expr: Expression rest: (',' _ e: Expression { return e })* { return [expr].concat(rest); } 

Lambda 
    = '\\\\' args: Arguments _ '->' _ body: Expression { 
    return { type: 'lambda', 
      args: args, 
      body: body 
      } 
    } 

Arguments 
    = head: Identifier rest: (',' _ i: Identifier { return i; })* { return [head].concat(rest); } 

Binding 
= name: Identifier _ '=' _ def: Expression _ 'in' _ expr: Expression { 
    return { 
    type: 'binding', 
    name: name, 
    def: def, 
    expr: expr 
    } 
} 

Condition 
= 'if' _ '(' _ cond: Expression _ ')' _ '{' _ expr1: Expression _ '}' expr2: (_ 'else' _ '{' _ e: Expression _ '}' { return e; })? { 
    return { 
    type: 'condition', 
    condition: cond, 
    expr1, 
    expr2 
    } 
} 
` 

const parser = peg.generate(grammar); 

const std = { 
    '+': (arg1, arg2) => arg1 + arg2, 
    '-': (arg1, arg2) => arg1 - arg2, 
    '*': (arg1, arg2) => arg1 * arg2, 
    '/': (arg1, arg2) => arg1/arg2, 
    'str': (arg1, arg2) => [arg1, arg2].join(""), 
    '>': (arg1, arg2) => arg1 > arg2, 
    '<': (arg1, arg2) => arg1 < arg2, 
    '==': (arg1, arg2) => arg1 === arg2, 
    'false': false, 
    'true': true, 
    'and': (arg1, arg2) => arg1 && arg2, 
    'or': (arg1, arg2) => arg1 || arg2 
} 

const makeLambda = (fun, parentEnv) => { 
    return (...args) => { 
     const env = Object.assign({}, parentEnv); 
     fun.args.forEach((el, i) => { 
     env[el.value] = args[i]; 
     }); 
     return _eval(fun.body, env); 
    } 
} 

const evalLiteral = (literal) => { 
    switch (literal.literalType) { 
    case 'Integer': 
     return parseInt(literal.value); 
    case 'String': 
     return String(literal.value); 
    default: 
     console.log('Literal type undefined'); 
     return literal.value; 
    } 
} 

const _eval = (expr, parentEnv = std) => { 
    const env = Object.assign({}, parentEnv); 
    switch (expr.type) { 
    case 'application': 
     const fun = _eval(expr.fun, env); 
     const args = expr.args.map(arg => _eval(arg, env)); 
     return fun.apply(null, args); 
     break; 
    case 'literal': 
     return evalLiteral(expr); 
    case 'identifier': 
     return env[expr.value]; 
    case 'lambda': 
     return makeLambda(expr, env); 
    case 'binding': 
     env[expr.name.value] = _eval(expr.def, env); 
     return _eval(expr.expr, env); 
    case 'condition': 
     if (_eval(expr.condition, env)) { 
     return _eval(expr.expr1, env); 
     } else { 
     return _eval(expr.expr2, env); 
     } 
    } 
} 

const parseAndEval = (str) => { 
    try { 
    const parsed = parser.parse(str); 
    console.log(parsed); 
    return _eval(parsed); 
    } catch (e) { 
    if (e.name == "SyntaxError") { 
    return e.toString() + 
     " start: " + JSON.stringify(e.location.start) + 
     " end: " + JSON.stringify(e.location.end); 
    } else { 
     return e.toString(); 
    } 
    } 
} 

Answer 1

UPDATE

我發現多了一個解決方案在這裏：http://lisperator.net/pltut/eval1/new-constructs

計算器是這種語言有所不同，雖然。 基本上，它歸結爲：

function make_lambda(env, exp) { 
    if (exp.name) {     // these 
     env = env.extend();   // lines 
     env.def(exp.name, lambda);  // are 
    }         // new 
    function lambda() { 
     var names = exp.vars; 
     var scope = env.extend(); 
     for (var i = 0; i < names.length; ++i) 
      scope.def(names[i], i < arguments.length ? arguments[i] : false); 
     return evaluate(exp.body, scope); 
    } 
    return lambda; 
} 

---

我發現在講課的解決方案上實現ML編譯： http://www.cs.cornell.edu/courses/cs312/2004fa/lectures/lecture24.htm

「的封閉由獨特的參數的名稱（見下面），定義函數體的表達式（即抽象語法樹），以及對創建閉包的環境的引用。我們使用對環境的引用有兩個原因：

• 首先，通過存儲引用而不是實際環境，我們節省了空間。

• 其次 - 更重要的是，引用的使用允許創建包含嵌入式引用指向環境本身的閉包的環境。這在定義遞歸或相互遞歸函數時很重要。「

所以，我所做的是通過環境對makeLamba()而不是複製的參考。因此，拉姆達股在創建時刻的環境中，但其身體的副本的評價環境是由（所以拉姆達裏的任何東西會發生變異父環境）。

// ... 
    case 'lambda': 
    return makeLambda(expr, parentEnv); // not a copy but a reference 
    // ... 

    const makeLambda = (fun, parentEnv) => { 
    return (...args) => { 
     const env = Object.assign({}, parentEnv); 
     fun.args.forEach((el, i) => { 
      env[el.value] = args[i]; 
     }); 
     return _eval(fun.body, env); 
    } 
    }