const tokeniseInput = function(inputString) {
    const tokenise = function(tokens, currentToken, remaining) {
        if (remaining.length === 0) {
            return tokens;
        }

        const [currentChar, ...newRemaining] = remaining;

        // Only include the current token if it is not empty
        const tokensMaybeWithCurrent = function() {
            if (currentToken === '') {
                return tokens;
            } else {
                return [...tokens, currentToken];
            }
        }

        if (currentChar === ' ') {
            return tokenise(tokensMaybeWithCurrent(), '', newRemaining);
        } else if (currentChar === '(' || currentChar === ')') {
            return tokenise([...tokensMaybeWithCurrent(), currentChar], '', newRemaining);
        } else {
            return tokenise(tokens, currentToken + currentChar, newRemaining)
        }
    }
    return tokenise([], '', inputString);
}

const buildAST = function(tokens) {
    const parseToken = function(token) {
        const intVal = parseInt(token);
        if (!isNaN(intVal)) {
            return {type: 'literal', value: intVal};
        }
        const floatVal = parseFloat(token);
        if (!isNaN(floatVal)) {
            return {type: 'literal', value: intVal};
        }
        return {type: 'symbol', token};
    };

    const getOp = function(opToken) {
        if (opToken === 'begin') {
            return {type: 'begin'};
        } else if (opToken === 'if') {
            return {type: 'conditional'};
        } else if (opToken === 'define') {
            return {type: 'definition'};
        } else {
            return {type: 'call', value: parseToken(opToken)};
        }
    }

    const processUntilEndOfExpression = function(processed, inputTokens) {
        if (inputTokens.length === 0) {
            return processed;
        }

        const [token, ...remainingTokens] = inputTokens;

        if (token === '(') {
            const [newNode, newRemaining] = buildNode(remainingTokens);
            return processUntilEndOfExpression([...processed, newNode], newRemaining);
        } if (token === ')') {
            return [processed, remainingTokens];
        } else {
            return processUntilEndOfExpression([...processed, parseToken(token)], remainingTokens);
        }
    };

    const buildNode = function(tokens) {
        const [opToken, ...remainingTokens] = tokens;

        const [args, newRemaining] = processUntilEndOfExpression([], remainingTokens);
        return [{...getOp(opToken), args}, newRemaining];
    };

    return processUntilEndOfExpression([], tokens)[0];
}

const parse = function(inputString) {
    return buildAST(tokeniseInput(inputString));
}

const eval = function(expression) {
    const baseEnv = Object.freeze({
        '+': (x, y) => x + y,
        '-': (x, y) => x - y,
        '*': (x, y) => x * y,
        '/': (x, y) => x / y,
        '<': (x, y) => x < y,
        '>': (x, y) => x > y,
        'sqrt': Math.sqrt,
        '^': Math.pow,
        'pi': Math.PI,
    });

    const doEval = function(exp, env) {
        if (exp.type === 'symbol') {
            return {result: env[exp.token], env};
        } else if (exp.type === 'literal') {
            return {result: exp.value, env};
        } else if (exp.type === 'begin') {
            return exp.args.reduce(({env}, exp) => {
                return doEval(exp, env);
            }, {result: null, env});
        } else if (exp.type === 'definition') {
            const [symbol, valueExp] = exp.args;

            const newEnv = {
                ...env,
                [symbol.token]: doEval(valueExp, env).result
            };

            return {result: null, env: newEnv};
        } else if (exp.type === 'call') {
            const proc = doEval(exp.value, env).result;

            return {
                result: proc(...exp.args.map(exp => doEval(exp, env).result)),
                env
            };
        } else if (exp.type === 'conditional') {
            const [conditionExp, ifTrue, ifFalse] = exp.args;
            return doEval(conditionExp).result ? doEval(ifTrue).result : doEval(ifFalse).result;
        }
    }

    return doEval(expression, baseEnv).result;
}

const program = '(begin (define a 3) (define b 6) (sqrt (+ (^ a 2) (^ b 2))))';
const ast = parse(program);
console.log(eval(ast));