javascript - 如何在 JavaScript 中实现 lambda/匿名函数

Question

所以我正在尝试使用 JavaScript 实现 LISP 的一个子集。我被困在与 lambda 相关的两件事上。

如何实现创建 lambda 并同时向其提供参数并立即对其求值的能力？例如:

((lambda(x)(* x 2)) 3)

现在我在我的 eval-loop 中硬编码了这个功能，如下所示:

else if (isArray(expr)){
      if (expr[0][0] === 'lambda' || expr[0][0] === 'string') { 
         console.log("This is a special lambda");
         var lambdaFunc = evaluate(expr[0], env)
         var lambdaArgs = [];
         for(var i = 1; i < expr.length; i++){
            lambdaArgs.push(expr[i]);
         }         
         return lambdaFunc.apply(this, lambdaArgs);
      }

现在这行得通了，如果我用参数编写上面的 lambda，它将评估为 6，但是，我想知道是否有任何更聪明的方法来实现它？

如果 lambda 被绑定(bind)到一个符号，例如:

(define fib (lambda(n)
    (if (< n 2) 1 
    (+ (fib (- n 1))(fib (- n 2)))
    )))

在这种情况下，(define fib) 部分将首先由 eval 循环求值，就好像 fib 只是被分配了一个数字一样:

else if (expr[0] === 'define') { // (define var value)
        console.log(expr + " is a define statement");
        var newVar = expr[1];
        var newVal = evaluate(expr[2], env);
        env.add(newVar, newVal);
        return env;
    }

lambda 函数是这样创建的:

else if (expr[0] === 'lambda') { // (lambda args body)
        console.log(expr + " is a lambda statement");
        var args = expr[1];
        var body = expr[2];
        return createLambda(args, body, env);
    }

创建 lambda 的单独函数:

function createLambda(args, body, env){ // lambda args body
   function runLambda(){
         var lambdaEnvironment = new environment(env, "lambda environment");
         for (var i = 0; i < arguments.length; i++){
            lambdaEnvironment.add(args[i], evaluate(arguments[i], env));
         }
         return evaluate(body, lambdaEnvironment);
   }  
   return runLambda;
}

这适用于 lambda，例如:

(define range (lambda (a b) 
    (if (= a b) (quote ()) 
    (cons a (range (+ a 1) b)))))

(define fact (lambda (n) 
    (if (<= n 1) 1 
    (* n (fact (- n 1))))))

例如，(range 0 10) 返回一个从 0 到 10 的列表。

但是如果我在一个 lambda 中尝试一个 lambda，它是行不通的。例如:

(define twice (lambda (x) (* 2 x)))  
(define repeat (lambda (f) (lambda (x) (f (f x)))))

我期望以下返回 40:

((repeat twice) 10)

但相反，它返回一个如下所示的列表:

function runLambda(){ var lambdaEnvironment = new environment(env, "lambda 
environment"); for (var i = 0; i < arguments.length; i++){ 
lambdaEnvironment.add(args[i], evaluate(arguments[i], env)); } return 
evaluate(body, lambdaEnvironment); },10

有什么想法这里可能遗漏了什么吗？

完整的 JavaScript；

//functions for parsing invoice String

function parse(exp) {
    return readFromTokes(tokenize(exp));//code
}


function isNumeric(arg){
    return !isNaN(arg);
}

function isArray(obj){
    return !!obj && obj.constructor === Array;
}

function readFromTokes(exp){
   //Create abstract syntax tree
   if (exp.length == 0) {
   }
   var token = exp.shift();
   if (token == '('){
      var L = [];
      while (exp[0] != ')') {
         L.push(readFromTokes(exp));
         }         
        exp.shift(); //remove end paranthesis
        return L;
   } else {
         if (token == ')') {
            console.log("Unexpected )");
         } else {
            return atom(token);
         }
   }
}

function tokenize(exp){
   //Convert a program in form of a string into an array (list)
   var re = /\(/g;
   var re2 = /\)/g;
   exp = exp.replace(re, " ( ");
   exp = exp.replace(re2, " ) ");
   exp = exp.replace(/\s+/g, ' ');
   exp = exp.trim().split(" ");
   return exp;
}

function atom(exp){
   if (isNumeric(exp)) {
   return parseInt(exp); //A number is a number
   } else {
      return exp; //Everything else is a symbol
   }
}

function environment(parentEnvironment, name){
    var bindings = [];
    var parent = parentEnvironment;
    var name = name;

    function add(variable, value){
        console.log("variable: " + variable + " value: " + value);
        bindings.push([variable, value]);
    }

    function printName(){
      console.log(name);
    }

    function print() {
        console.log("printing environment: ")
        for (var i = 0; i < bindings.length; i++){
            console.log(bindings[i][0] + " " + bindings[i][1]);
        }
    }

    function get(variable){
        for (var i = 0; i < bindings.length; i++){
            if (variable == bindings[i][0]){
                return bindings[i][1];
            }
        }
        if (parent != null){
            return parent.get(variable);
        } else {
        console.log("No such variable");
            return false;
        }
    }

    function getParent(){
        return parent;
    }

    this.add = add;
    this.get = get;
    this.getParent = getParent;
    this.print = print;
    this.printName = printName;
    return this;
}

function addPrimitives(env){
   env.add("+", function() {var s = 0; for (var i = 0; i<arguments.length;i++){ s += arguments[i];} return s});
   env.add("-", function() {var s = arguments[0]; for (var i = 1; i<arguments.length;i++){ s -= arguments[i];} return s});
   env.add("*", function() {var s = 1; for (var i = 0; i<arguments.length;i++){ s *= arguments[i];} return s});
   env.add("/", function(x, y) { return x / y });
   env.add("false", false);
   env.add("true", true);
   env.add(">", function(x, y){ return (x > y) });
   env.add("<", function(x, y){ return (x < y) }); 
   env.add("=", function(x, y){ return (x === y)});
   env.add(">=", function(x, y){ if (x >= y){return true;} else {return false;}}); 
   env.add("<=", function(x, y){ if (x <= y){return true;} else {return false;}});
   env.add("eq?", function() {var s = arguments[0]; var t = true; for(var i = 1; i<arguments.length; i++){ if (arguments[i] != s) {t = false }} return t;});
   env.add("cons", function(x, y) { var temp = [x]; return temp.concat(y); });
   env.add("car", function(x) { return x[0]; });
   env.add("cdr", function(x) { return x.slice(1); });
   env.add("list", function () { return Array.prototype.slice.call(arguments); });
   env.add("list?", function(x) {return isArray(x); });
   env.add("null", null);
   env.add("null?", function (x) { return (!x || x.length === 0); });
}


function createLambda(args, body, env){ // lambda args body
   function runLambda(){
     var lambdaEnvironment = new environment(env, "lambda environment");
         for (var i = 0; i < arguments.length; i++){
            lambdaEnvironment.add(args[i], evaluate(arguments[i], env));
         }
         return evaluate(body, lambdaEnvironment);
   }  
   return runLambda;
}

function evaluate(expr, env) {
    console.log(expr + " has entered evaluate loop");
    if (typeof expr === 'string') {
        console.log(expr + " is a symbol");
        return env.get(expr);
    } else if (typeof expr === 'number') {
        console.log(expr + " is a number");
        return expr;
    } else if (expr[0] === 'define') { // (define var value)
        console.log(expr + " is a define statement");
        var newVar = expr[1];
        var newVal = evaluate(expr[2], env);
        env.add(newVar, newVal);
        return env;
    } else if (expr[0] === 'lambda') { // (lambda args body)
        console.log(expr + " is a lambda statement");
        var args = expr[1];
        var body = expr[2];
        return createLambda(args, body, env);
    } else if (expr[0] === 'quote') {
        return expr[1];
    } else if (expr[0] === 'cond'){
        console.log(expr + " is a conditional");
        for (var i = 1; i < expr.length; i++){
            var temp = expr[i];
            if (evaluate(temp[0], env)) {
                console.log(temp[0] + " is evaluated as true");
                return evaluate(temp[1], env);
            }
        }
        console.log("no case was evaluated as true");
        return;
    } else if (expr[0] === 'if') {
        console.log(expr + "is an if case");
        return function(test, caseyes, caseno, env){
            if (test) {
                return evaluate(caseyes, env);
            } else {
                return evaluate(caseno, env);
            }
        }(evaluate(expr[1], env), expr[2], expr[3], env); 
    } else if (typeof expr[0] === 'string'){
        console.log(expr + " is a function call");
        var lispFunc = env.get(expr[0]);
        var lispFuncArgs = [];        
        for(var i = 1; i < expr.length; i++){
        lispFuncArgs.push(evaluate(expr[i], env));
       }
       return lispFunc.apply(this, lispFuncArgs);
    } else if (isArray(expr)){
        if (expr[0][0] === 'lambda' || expr[0][0] === 'string') { 
            console.log("This is a special lambda");
            var lambdaFunc = evaluate(expr[0], env)
            var lambdaArgs= [];
            for(var i = 1; i < expr.length; i++){
                lambdaArgs.push(expr[i]);
            }         
            return lambdaFunc.apply(this, lambdaArgs);
        } else { 
             console.log(expr + " is a list");
             var evaluatedList = [];
             for(var i = 0; i < expr.length; i++){
                 evaluatedList.push(evaluate(expr[i], env));
             }
             return evaluatedList;
        }
    } else {
        console.log(expr + " cannot be interpreted");
    }
}


var globalEnvironment = new environment(null, "Global");

addPrimitives(globalEnvironment);

function start(string) {
    return evaluate(parse(string), globalEnvironment);
}

var output = function (string) {
    try {
        document.getElementById('debugdiv').innerHTML = start(string);
    } catch (e) {
        document.getElementById('debugdiv').innerHTML = e.name + ': ' + e.message;
    }
};

完整的 HTML；

<html>
    <head>
        <meta content="text/html; charset=UTF-8" http-equiv="Content-Script-Type" content="text/javascript">
        <title>LISP in JavaScript</title>
        <script type="text/javascript" src="lisp.js"></script>
    </head>
    <body>
        <form id="repl" name="repl" action="parse(prompt.value)">
        lisp==&gt;
            <input id="prompt" size="200" value="" name="prompt" maxlength="512">
            <br>
            <input type=button style="width:60px;height:30px" name="btnEval" value="eval" onclick="output(prompt.value)">
            <br>
            </form>
        <div id="debugdiv" style="background-color:orange;width=100px;height=20px">
        </div>        
    </body>
</html>

当然也欢迎进一步的想法、建议和评论。谢谢!

Answer 1

您不会检查操作数的结构以查看它是否是lambda 您eval 操作数。 eval 的标准方法是检查它是否是原始类型，然后检查特殊形式和宏，然后在应用之前评估运算符和操作数。

只需删除 expr[0][0] === 'lambda' || 的部分expr[0][0] === 'string' 为真，而不是仅仅返回您需要应用操作数的形式的评估:

else if (isArray(expr)){
  const fn = evaluate(expr[0], env);
  const evaluatedList = [];
  for(var i = 1; i < expr.length; i++){
    evaluatedList.push(evaluate(expr[i], env));
  }
  return fn(...evaluatedList);
}

createLambda 是错误的，因为您在错误的环境中计算参数。这是正确的，因为参数已经被评估:

function createLambda(args, body, env){ // lambda args body
   function runLambda(){
     const lambdaEnvironment = new environment(env, "lambda environment");
     for (let i = 0; i < arguments.length; i++){
       lambdaEnvironment.add(args[i], arguments[i]);
     }
     return evaluate(body, lambdaEnvironment);
   }  
   return runLambda;
}