How to parse pure functions

Question

Let's say you have the following function

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);

Is it possible to have a function that takes a reference to the function action and outputs say the LISP format (lambda (c) (plus (plus 42 (multiply 4 2)) c))

We're allowed to put some restrictions on what action can be.

• the body should only be a single expression
• it should be a pure function
• any free variables are constants

The main question is given a function you can invoke with a range of inputs and it's source code can you discover the correct value to substitute the free variables with?

For the above example you know that a and b are constant and you could intellectually plot the output for a few values and see the pattern and then just know what the constants are.

Question:

How would you write a function that takes a function reference and it's source code and produces some form of AST for the function with any free variables substituted for their run-time values.

An example of an AST format would be the LISP equivalent of the code.

I basically want to serialize and deserialize the function and have it behave the same

It should be noted that the problem becomes trivial if you pass { a: a, b: b } to the analysis function. That would be cheating.

Use-case:

I want to generate a language agnostic form of a pure JavaScript function so I can effectively pass it to C++ without requiring the user of my library to use a DSL to create this function

Let's imagine you had a database driver

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

You want to determine at run-time what the function is and convert it into an AST format so that you can use your efficient query builder to convert it into SQL or whatever query engine your database has.

This means you don't have to write:

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

Which is a function the DB library can execute with a query object and have you build the query object transformation without verbose methods.

Answer 1

Here is a full solution (using catalog of variables which is accessible by the parse function):

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));

I just wrote it so there might be some problems in the style but I think that the idea is clear.

You can get the function body by using the .toString method. After that you can use regular expression to match the return statement

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

Note that here you must use semicolons for successful match! In the next step all variables are transformed to number values using the CONSTANTS object (I see that you have some parameters left so you may need little modifications here). After that the string is being tokenized, for easier parsing. In next step the infix expression is transformed into a prefix one. At the last step I build a string which will make the output looks like what you need (+ - plus, - - minus and so on).