recursion works

ae_scheme.js

(()=>{
    const STATES = {
        FAILURE: -1,
        ROOT: 0,
        LIST: 1,
        NUMBER: 2,
        SYMBOL: 3,
        LITERAL: 4
    };
    
    const Node = (Type) => {
        return  {
            type: Type,
            quote: false,
            content: undefined,
            children: [],
            parent: undefined,
            attach: function (child) {
                child.parent = this;
                this.children.push(child);
            }
        };
    };
    
    const is_node = (el) => el.hasOwnProperty('type') && el.hasOwnProperty('attach');
    
    const Parser = (string) => {
        const num_accept = '1234567890.';
    
        let state = STATES.ROOT;
        let current_parse = '';
        let quote = false;
        
        // readhead
        let pos = 0;
        
        let current_node = Node(STATES.ROOT);
    
        const parse_literal = () => {
            state = STATES.LITERAL;		
            const reject = '(.\'`';
            if (reject.includes(string[pos])) {
                state = STATES.FAILURE;
                return;
            }		
            switch (string[pos]) {
                case ' ':
                case '\n':
                    {
                    let new_node = Node(STATES.LITERAL);
                    new_node.content = current_parse;
                    current_parse = '';
                    current_node.attach(new_node);
                    state = current_node.type;
                    quote = current_node.quote;
                    break;
                    }
                case ')':
                    {
                    let new_node = Node(STATES.LITERAL);
                    new_node.content = current_parse;
                    current_parse = '';
                    current_node.attach(new_node);
                    state = current_node.parent.type;
                    current_node = current_node.parent;
                    quote = current_node.quote;
                    break;
                    }
                default:
                    current_parse += string[pos];
            }
        };
    
        const parse_number = () => {
            if (quote) {
                parse_literal();
                return;
            }
    
            state = STATES.NUMBER;
            if (num_accept.includes(string[pos])) {
                if (string[pos] === '.' && current_parse.includes('.'))
                    state = STATES.FAILURE;
                else
                    current_parse += string[pos];
                return;
            }
        
            switch (string[pos]) {
                case ' ': 
                case '\n':
                    {
                    let new_node = Node(STATES.NUMBER);
                    new_node.content = current_parse;
                    current_parse = '';
                    current_node.attach(new_node);
                    state = current_node.type;
                    break;
                    }
                case ')':
                    {
                    let new_node = Node(STATES.NUMBER);
                    new_node.content = current_parse;
                    current_parse = '';				
                    current_node.attach(new_node);
                    state = current_node.parent.type;
                    current_node = current_node.parent;
                    break;
                    }
                default:
                    state = STATES.FAILURE;
                    return;
            }
        };
    
        const parse_symbol = () => {
            if (quote) {
                parse_literal();
                return;
            }
            state = STATES.SYMBOL;
            const reject = '(.\'`';
            if (reject.includes(string[pos])) {
                state = STATES.FAILURE;
                return;
            }
            switch (string[pos]) {
                case ' ':
                case '\n':
                    {
                    if (current_parse === 'quote') {
                        quote = true;
                    } else {
                        let new_node = Node(STATES.SYMBOL);
                        new_node.content = current_parse;
                        current_node.attach(new_node);
                    }
                        current_parse = '';
                        state = current_node.type;
                    break;
                    }
                case ')':
                    {
                    let new_node = Node(STATES.SYMBOL);
                    new_node.content = current_parse;
                    current_parse = '';	
                    current_node.attach(new_node);
                    state = current_node.parent.type;
                    current_node = current_node.parent;
                    break;
                    }
                default:
                    current_parse += string[pos];
            }
        };
    
        const parse_list = () => {
            switch (string[pos]) {
            case '(':
                let new_node = Node(STATES.LIST);
                current_node.attach(new_node);
                current_node = new_node;
                state = STATES.LIST;
                if (quote) {
                    current_node.quote = true;
                }
                break;
            case ')':
                state = current_node.parent.type;
                if (!current_node.parent.quote)
                    quote = false;
                current_node = current_node.parent;
                break;
            case '\'':
                quote = true;
                break;
            case ' ':
            case '\n':
                break;
            default:
                if (current_node.quote)
                    parse_literal();
                else {
                    if (num_accept.includes(string[pos]))
                        parse_number();
                    else
                    parse_symbol();
                }
            }
        };
    
        while (pos < string.length) {
            switch (state) {
            case STATES.ROOT:
            case STATES.LIST:
                parse_list();
                break;
            case STATES.NUMBER:
                parse_number();
                break;
            case STATES.SYMBOL:
                parse_symbol();
                break;		
            case STATES.LITERAL:
                parse_literal();
                break;
            case STATES.FAILURE:
                return "mmsus!!!";
            }
            pos++;
        };
    
        return current_node;
    };
    
    const Evaluator = (AST) => {
        let env = {};
    
        const Func = (fn, arg) => {
            if (arg === 0)
                return fn;
    
            return {
                func: fn,
                arity: arg // -1 means variadic, pass all args in array, extract when this is 0
            };
        };
    
        const SpecialForm = (fn, arg, inliner = undefined) => {
            let r = Func(fn, arg);
            r.special = true;
            r.inliner = inliner; // doing this instead of eval(inlining whatever) for Func because that has its own issues (scope mostly)
            return r;
        };
    
        // special rules for eval order, explicitly call Eval, expect nodes as inputs, return nodes
        env['car'] = SpecialForm(list => {
            if (!Eval(list.children[0]).hasOwnProperty('func'))
                return list.children[0];
            else
                return Eval(list)[0];
        }, 1);				// do not eval anything
        env['cdr'] = SpecialForm(list => {
            let list_node = Node(STATES.LIST);
            if (!Eval(list.children[0]).hasOwnProperty('func')) {
                list.children.slice(1).forEach(e => list_node.attach(e));
            }
            else {
                Eval(list).slice(1).forEach(e => list_node.attach(e));
            }
            return list_node;
        }, 1);			// do not eval anything
        env['cons'] = SpecialForm((i, list) => {
            let list_node = Node(STATES.LIST);
            list_node.attach(i);
            if (!Eval(list.children[0]).hasOwnProperty('func')) {
                list.children.forEach(e => list_node.attach(e));
            }
            else {
                Eval(list).forEach(e => list_node.attach(e));
            }
            return list_node;
        }, 2);	// do not eval anything
        env['quote'] = undefined; // reject, already handled in parsing, something must have gone wrong
    
        const lambda_toString = (body) => {
            let body_args = `${[...body.children.slice(1).map((el) => ((el.children.length > 1 ? lambda_toString(el) : el.content)))]}`;
            if (typeof Eval(body.children[0]) === 'string' || Eval(body.children[0]) instanceof String)
                return `(${Eval(body.children[0])})(${body_args})`;
            else 
            {
                if (Eval(body.children[0]).arity === -1) // variadic
                    body_args = `[${body_args}]`;
                if (Eval(body.children[0]).inliner){
                    return `(${Eval(body.children[0]).inliner.apply(null, body.children.slice(1).map((el) => ((el.children.length > 1 ? lambda_toString(el) : el.content))))})`;
                }
                return `(${Eval(body.children[0]).func.toString()})(${body_args})`;
            }
        };
    
        env['__myself__'] = '__myself__'; // shit...
        
        env['lambda'] = SpecialForm(
            (args, body) => Func(new Function(...args.children.map(e => e.content), `return ${lambda_toString(body)}`), args.children.length)
        , 2); // this is has free symbols
        
        const why = fn => (maker => (...args) => fn(maker(maker), ...args))(maker => (...args) => fn(maker(maker), ...args));
        const construct_recursive_lambda = (args, body) => {
            return Func(why(
                new Function(
                    ...args.children.map(e => e.content), 
                    `return ${lambda_toString(body)};`
                )
            ), args.children.length - 1);
        };
    
        env['define'] = SpecialForm((a, b) => {
            if (a.children.length > 1) {
                let is_recursive = false;
                let args_node = Node(STATES.LIST);
                let body_node = Node(STATES.LIST);
    
                b.children.forEach(function check_recursion (e, i ,arr) {
                    if (e.type === STATES.LIST)
                        e.children.forEach(check_recursion);
                    else if (e.type === STATES.SYMBOL && e.content === a.children[0].content) {
                        is_recursive = true;
                        arr[i].content = '__myself__';
                    }
                });
    
                b.children.forEach(e => body_node.attach(e));
    
                if (is_recursive) {
                    let recur_arg = Node(STATES.SYMBOL);
                    recur_arg.content = '__myself__';			
                    args_node.attach(recur_arg);			
                    a.children.slice(1).forEach(e => args_node.attach(e));
                    env['define'].func(a.children[0], construct_recursive_lambda(args_node, body_node)); // free symbols, do not eval
                    
                }
                else {
                    a.children.slice(1).forEach(e => args_node.attach(e));
                    env['define'].func(a.children[0], env['lambda'].func(args_node, body_node)); // free symbols, do not eval
                }
            }
            else if (a.children.length === 1)
                env[a.children[0].content] = Eval(b);
            else
                env[a.content] = Eval(b);
        }, 2);
        env['list'] = Func(args => args, -1); 	// eval
        env['else'] = true;
        env['cond'] = SpecialForm((clauses) => {
            for (let i = 0; i < clauses.children.length; i++) {
                if (Eval(clauses[i].children[0]))
                    return clauses[i].children[1];
            }
        }, -1,
        (clauses) => `(() => {
            for (let i = 0; i < ${clauses}.children.length; i++) {
                if (Eval(${clauses}[i].children[0]))
                    return ${clauses}[i].children[1];
            })()`
        );
        env['if'] = SpecialForm((condition, a, b) => (Eval(condition) ? Eval(a) : Eval(b)), 3,
            (condition, a, b) => `Eval(${condition}) ? Eval(${a}) : Eval(${b})`
        );
        env['and'] = SpecialForm((args) => args.every(i => Eval(i)), -1,
            (args) => `${args}.every(i => Eval(i))`
        );
        env['or'] = SpecialForm((args) => args.some(i => Eval(i)), -1,
            (args) => `${args}.some(i => Eval(i))`
        );
        env['not'] = Func((c) => !c, 1);
        env['eq?'] = Func((a, b) => a === b, 2);
        env['#t'] = true;
        env['#f'] = false;
        env['apply'] = SpecialForm((args) =>  Eval(args[0])(...args.slice(1).map(Eval)), -1,
            (args) => `Eval(${args}[0])(...${args}.slice(1).map(Eval))`
        );
    
        // stdlib, expecting everything to already be eval'd, return eval'd primitive
        env['+'] = Func(args => (args.reduce((a, b) => a + b, 0)), -1);
        env['-'] = Func((a, b) => (a - b), 2);
        env['*'] = Func(args => (args.reduce((a, b) => a * b, 1)), -1);
        env['/'] = Func((a, b) => (a / b), 2);
        env['%'] = Func((a, b) => (a % b), 2);
        env['sin'] = Func(Math.sin, 1);
        env['cos'] = Func(Math.cos, 1);
        env['tan'] = Func(Math.tan, 1);
        env['arcsin'] = Func(Math.asin, 1);
        env['arccos'] = Func(Math.acos, 1);
        env['arctan'] = Func(Math.atan, 1);
        env['atan2'] = Func(Math.atan2, 2);
        env['PI'] = Math.PI;
        env['E'] = Math.E;
        env['exp'] = Func(Math.exp, 1);
        env['log'] = Func(Math.log10, 1);
        env['ln'] = Func(Math.log, 1);
        env['sqrt'] = (Math.sqrt, 1);
        env['pow'] = Func(Math.pow, 2);
        env['round'] = Func(Math.round, 1);
        env['ceil'] = Func(Math.ceil, 1);
        env['floor'] = Func(Math.floor, 1);
        env['sign'] = Func(Math.sign, 1);
        env['abs'] = Func(Math.abs, 1);
    
        env['lerp'] = Func(linear, 5);
        env['clamp'] = Func(clamp, 3);
    
        env['min'] = Func(args => (Math.min(...args)), -1);
        env['max'] = Func(args => (Math.max(...args)), -1);
        env['map'] = Func((f, list) => (list.map(f)), 2);
        env['filter'] = Func((f, list) => (list.filter(f)), 1);
        env['fold-left'] = Func((f, i, list) => (list.reduce(f, i)), 3);
        env['fold-right'] = Func((f, i, list) => (list.reduceRight(f, i)), 3);
    
        // AE lib expecting everything to already be evaled, return eval'd primitive
        env['time'] = time;
        env['time-to-frames'] = Func(timeToFrames, 1);
        env['frames-to-time'] = Func(framesToTime, 1);
        env['posterize-time'] = Func(posterizeTime, 1);
        env['this-project'] = thisProject;
        env['this-layer'] = thisLayer;
        env['this-comp'] = thisComp;
        env['comp'] = Func(comp, 1);
        env['effect'] = Func(effect, 1);
        env['rgba-to-hsla'] = Func((r, g, b, a) => (rgbToHsl([r, g, b, a])), 4);
        env['hsla-to-rgba'] = Func((h, s, l, a) => (hslToRgb([h, s, l, a])), 4);
        env['deg-to-rad'] = Func(degreesToRadians, 1);
        env['rad-to-deg'] = Func(radiansToDegrees, 1);
        env['random'] = Func(random, 1);
        env['random-seed'] = Func(seedRandom, 2);
        env['wiggle'] = Func(wiggle, 2);
    
        let state = STATES.ROOT;
    
        const SpecialForm_SymbolExtract = (node) => {
            switch (node.type) {
                case STATES.LIST:
                {
                    for (let i = 0; i < node.children.length; i++) // these nodes should only be used here and nowhere else, so okay if we mutate
                        node.children[i] = SpecialForm_SymbolExtract(node.children[i]);
                    return node;
                }
                case STATES.SYMBOL:
                    if (thisProperty.hasOwnProperty(node.content))
                        return Func(thisProperty[node.content], thisProperty[node.content].length);
                    else if (env.hasOwnProperty(node.content))
                    // if (env.hasOwnProperty(node.content))
                        return env[node.content];
                    else
                        return node;
                default:
                    return node;
            }
        };
    
        Eval = (node) => {  // declaring it global because new Function funcs only have access to globals
            // return thing if it is not an AST node
            if (!is_node(node)) // this is stupid, i do not know the right way to do this in js
                return node;
            if (state !== STATES.FAILURE)
                switch (node.type) {
                case STATES.LIST:
                {
                    if (!Eval(node.children[0]).hasOwnProperty('func')) {
                        console.log("first element of list is not Func: ");
                        console.log(node.children[0]);
                        state = STATES.FAILURE;
                        return;
                    }
                    if (Eval(node.children[0]).hasOwnProperty('special')) {
                        // special forms cannot be partially applied
                        // leave evaling args to the funcs
                        let list = node.children;
                        
                        if (list.length - 1 === Eval(list[0]).arity)
                                return Eval(list[0]).func.apply(null, list.slice(1).map(SpecialForm_SymbolExtract));
                        else if (Eval(list[0]).arity === -1) 
                                return Eval(list[0]).func.apply(null, [list.slice(1).map(SpecialForm_SymbolExtract)]);
                        else {
                            console.log("fail to pair special form args: ");
                            console.log(list);
                            state = STATES.FAILURE;
                            return;
                        }
                    }
                    else {
                        let list = node.children.map(Eval);
                        if (list[0].arity === -1)
                            return list[0].func.apply(null, [list.slice(1)]); // variadic funcs cannot be partially applied
                        else if (list.length - 1 <= list[0].arity)
                            return Func(list[0].func.apply(null, list.slice(1)), list[0].arity - (list.length - 1));
                        else {
                            console.log("fail to pair function args: ");
                            console.log(list);
                            state = STATES.FAILURE;
                            return;
                        }
                    }
                }
                case STATES.NUMBER:
                    return Number(node.content);
                case STATES.SYMBOL:
                    if (thisProperty.hasOwnProperty(node.content))
                         return Func(thisProperty[node.content], thisProperty[node.content].length);
                    else if (env.hasOwnProperty(node.content))
                    // if (env.hasOwnProperty(node.content))
                        return env[node.content];
                    else {
                        console.log("fail to resolve symbol: ");
                        console.log(node.content);
                        state = STATES.FAILURE;
                        return;
                    }
                case STATES.LITERAL:
                    return node.content;
                default:
                    return "mmsus!!!";
                }
            else
                return "FAILED";
        }
    
        const root_S_exps = AST.children.map(a => (Eval(a, true)));
        return root_S_exps[root_S_exps.length - 1];
    };
    
    return (src) => Evaluator(Parser(src));
})()