javascript - 如何解析纯函数

Question

假设您有以下功能

var action = (function () {

  var a = 42;
  var b = 2;

  function action(c) {
    return a + 4 * b + c;
  }

  return action;
}());

// how would you parse action into it's serialized LISP / AST format?
var parsed = parse(action);

是否可以有一个函数引用函数 action 并输出 LISP 格式 (lambda (c) (plus (plus 42 (multiply 4 2)) c))

我们可以对action 的内容进行一些限制。

• 正文只能是一个表达式
• 它应该是一个纯函数
• 任何自由变量都是常量

主要问题是给定一个函数，您可以使用一系列输入调用它的源代码，您能否找到正确的值来替换自由变量？

对于上面的示例，您知道 a 和 b 是常量，您可以智能地绘制一些值的输出并查看模式，然后只知道常量是什么。

问题:

您将如何编写一个函数，该函数采用函数引用及其源代码并为该函数生成某种形式的 AST，并用任何自由变量替换其运行时值。

AST 格式的一个示例是代码的 LISP 等价物。

我基本上想序列化和反序列化该函数并使其表现相同

应该注意的是，如果将 { a: a, b: b } 传递给分析函数，问题就会变得微不足道。那将是作弊。

用例:

我想生成一种与语言无关的纯 JavaScript 函数形式，这样我就可以有效地将它传递给 C++，而无需我的库的用户使用 DSL 来创建此函数

假设您有一个数据库驱动程序

var cursor = db.table("my-table").map(function (row) {
  return ["foo", row.foo]
})

您想在运行时确定函数是什么并将其转换为 AST 格式，以便您可以使用高效的查询构建器将其转换为 SQL 或您的数据库具有的任何查询引擎。

这意味着你不必写:

var cursor = db.table("my-table").map(function (rowQueryObject) {
    return db.createArray(db.StringConstant("foo"), rowQueryObject.getProperty("foo"))
})

这是一个 DB 库可以使用查询对象执行的函数，让您无需冗长的方法即可构建查询对象转换。

Answer 1

这是一个完整的解决方案(使用解析函数可访问的变量目录):

var CONSTANTS = { 
   a: 42,
   b: 2,
   c: 4
};

function test() {
    return a + 4 * b + c;
}

function getReturnStatement(func) {
    var funcStr = func.toString();
    return (/return\s+(.*?);/g).exec(funcStr)[1];
}

function replaceVariables(expr) {
    var current = '';
    for (var i = 0; i < expr.length; i += 1) {
        while (/[a-zA-Z_$]/.test(expr[i]) && i < expr.length) {
            current += expr[i];
            i += 1;
        }
        if (isNumber(CONSTANTS[current])) {
            expr = expr.replace(current, CONSTANTS[current]);
        }
        current = '';
    }
    return expr;
}

function isNumber(arg) {
    return !isNaN(parseInt(arg, 10));
}      

function tokenize(expr) {
    var tokens = [];
    for (var i = 0; i < expr.length; i += 1) {
        if (isWhitespace(expr[i])) {
            continue;
        } else if (isOperator(expr[i])) {
            tokens.push({
                type: 'operator',
                value: expr[i]
            });
        } else if (isParentheses(expr[i])) {
            tokens.push({
                type: 'parant',
                value: expr[i]
            });
        } else {
            var num = '';
            while (isNumber(expr[i]) && i < expr.length) {
                num += expr[i];
                i += 1;
            }
            i -= 1;
            tokens.push({
                type: 'number',
                value: parseInt(num, 10)
            });
        }
    }
    return tokens;
}

function toPrefix(tokens) {
    var operandStack = [],
        operatorStack = [],
        current,
        top = function (stack) {
            if (stack) {
                return stack[stack.length - 1];
            }
            return undefined;
        };

    while (tokens.length) {
        current = tokens.pop();
        if (current.type === 'number') {
            operandStack.push(current);
        } else if (current.value === '(' || 
                !operatorStack.length || 
                (getPrecendence(current.value) >
                 getPrecendence(top(operatorStack).value))) {

            operatorStack.push(current);
        } else if (current.value === ')') {
            while (top(operatorStack).value !== '(') {
                var tempOperator = operatorStack.pop(),
                    right = operandStack.pop(),
                    left = operandStack.pop();
                operandStack.push(tempOperator, left, right);
            }
            operatorStack.pop();
        } else if (getPrecendence(current.value) <= 
                getPrecendence(top(operatorStack).value)) {
            while (operatorStack.length &&
                    getPrecendence(current.value) <=
                    getPrecendence(top(operatorStack).value)) {

                tempOperator = operatorStack.pop();
                right = operandStack.pop();
                left = operandStack.pop();
                operandStack.push(tempOperator, left, right);
            }
        }

    }

    while (operatorStack.length) {
        tempOperator = operatorStack.pop();
        right = operandStack.pop();
        left = operandStack.pop();
        operandStack.push(tempOperator, left, right);
    }

    return operandStack;
}

function isWhitespace(arg) {
    return (/^\s$/).test(arg);
}

function isOperator(arg) {
    return (/^[*+\/-]$/).test(arg);
}

function isParentheses(arg) {
    return (/^[)(]$/).test(arg);
}

function getPrecendence(operator) {
    console.log(operator);
    switch (operator) {
        case '*':
            return 4;
        case '/':
            return 4;
        case '+':
            return 2;
        case '-':
            return 2;
        default:
            return undefined;
    }
}

function getLispString(tokens) {
    var result = '';
    tokens.forEach(function (e) {
        if (e)
            switch (e.type) {
            case 'number':
            result += e.value;
            break;
            case 'parant':
            result += e.value;
            break;
            case 'operator':
            result += getOperator(e.value);
            break;
            default:
            break;
        }
        result += ' ';
    });
    return result;
}

function getOperator(operator) {
    switch (operator) {
        case '+':
            return 'plus';
        case '*':
            return 'multiplicate';
        case '-':
            return 'minus';
        case '\\':
            return 'divide';
        default:
            return undefined;
    }
}

var res = getReturnStatement(test);
console.log(res);
res = replaceVariables(res);
console.log(res);
var tokens = tokenize(res);
console.log(tokens);
var prefix = toPrefix(tokens);
console.log(prefix);
console.log(getLispString(prefix));

我只是写的，所以风格可能有一些问题，但我认为思路很清楚。

您可以使用.toString 方法获取函数体。之后就可以使用正则表达式来匹配返回语句了

(/return\s+(.*?);/g).exec(funcStr)[1];

注意这里必须使用分号才能匹配成功!在下一步中，使用 CONSTANTS 对象将所有变量转换为数字值(我看到您还剩下一些参数，因此您可能需要在此处进行少量修改)。之后，字符串被标记化，以便于解析。在下一步中，中缀表达式被转换为前缀表达式。在最后一步，我构建了一个字符串，使输出看起来像您需要的那样(+ - plus, - - minus 等等)。