Skip to content

Instantly share code, notes, and snippets.

@lachrymaLF
Created November 19, 2021 05:04
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save lachrymaLF/02e7fa7362dee336ca4086ad8eaf174f to your computer and use it in GitHub Desktop.
recursion works
(()=>{
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));
})()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment