Created
May 9, 2014 20:48
-
-
Save be5invis/72e74acb2a377d3a42ec to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset="utf-8"> | |
| <title>JS Bin</title> | |
| </head> | |
| <body> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| var Ref = function(s){ this.ref = s } | |
| var newt = function(n){ | |
| return function(){ | |
| return new Ref("_" + (n++)) | |
| } | |
| }(0); | |
| function id(x){ return x } | |
| function normalizeTerm(form){ return normalize(form, id) } | |
| function normalize(form, ctx){ | |
| if(form instanceof Array){ | |
| if(form[0] === '.lambda') return ctx([':LAMBDA', form[1], normalizeTerm(form[2])]) | |
| else if(form[0] === '.yield') { | |
| var t = newt(); | |
| return normalize(form[1], function(n){ | |
| return [n, [':LAMBDA', [t], ctx(t)]] | |
| }) | |
| } else if(form[0] === '=') { | |
| return normalizeAssign(form, ctx) | |
| } else return normalizeCall(form, ctx) | |
| } else if(typeof form === 'string') { | |
| return ctx([':GETV', form]) | |
| } | |
| } | |
| function normalizeArg(form, ctx){ | |
| return normalize(form, function(n){ | |
| var t = newt(); | |
| return [':LET', t, n, ctx(t)] | |
| }) | |
| } | |
| function normalizeAssign(form, ctx){ | |
| if(form[1] && form[1][0] === '.'){ | |
| return normalize(form[1][1], function(tl){ | |
| return normalize(form[1][2], function(tr){ | |
| return normalize(form[2], function(n){ | |
| return normalize(form[2], function(n){ | |
| var t = newt(); | |
| return [':LET', t, ['=', ['.', tl, tr], n], ctx(t)] | |
| }) | |
| }) | |
| }) | |
| }) | |
| } else { | |
| return normalize(form[2], function(n){ | |
| var t = newt(); | |
| return [':LET', t, ['=', form[1], n], ctx(t)] | |
| }) | |
| } | |
| } | |
| function normalizeCall(form, ctx){ | |
| if(form[0] && form[0][0] === '.'){ | |
| return normalizeArg(form[0][1], function(tl){ | |
| return normalizeArg(form[0][2], function(tr){ | |
| return normalizeList(form.slice(1), function(t$){ | |
| if(t$) return ctx([['.', tl, tr].concat(t$)]) | |
| else return ctx([['.', tl, tr]]) | |
| }) | |
| }) | |
| }) | |
| } else { | |
| return normalizeList(form, ctx); | |
| } | |
| } | |
| function normalizeList(form, ctx){ | |
| if(!form.length){ | |
| return ctx(null) | |
| } else { | |
| return normalizeArg(form[0], function(t){ | |
| return normalizeList(form.slice(1), function(t$){ | |
| if(t$) return ctx([t].concat(t$)); | |
| else return ctx([t]) | |
| }) | |
| }) | |
| } | |
| }; | |
| function redex(form){ | |
| if(form instanceof Ref){ | |
| var r = {}; | |
| r[form.ref] = true; | |
| return {value: form, refes: r} | |
| } else if(form instanceof Array){ | |
| if(form[0] === ':LET'){ // Let bind | |
| var body = redex(form[3]); | |
| var bound = redex(form[2]); | |
| if(body.refes[form[1].ref]) { | |
| form[1].ref = bound.value; | |
| for(var each in bound.refes) body.refes[each] = true; | |
| return body | |
| } else { | |
| var r = {}; | |
| for(var each in bound.refes) r[each] = true; | |
| for(var each in body.refes) r[each] = true; | |
| return {value: ['!LET', form[1], bound.value, body.value], refes: r} | |
| } | |
| } else if(form[0] === ':LAMBDA'){ | |
| return {value: ['!LAMBDA', form[1], redex(form[2]).value], refes: {}} | |
| } else if(form[0] === ':GETV'){ | |
| return {value: ['!GETV', form[1]], refes: {}} | |
| } else { | |
| var a = [], r = {}; | |
| for(var j = 0; j < form.length; j++){ | |
| var term = redex(form[j]); | |
| a[j] = term.value; | |
| for(var each in term.refes) r[each] = true; | |
| }; | |
| return {value: a, refes: r} | |
| } | |
| } else { | |
| return {value: form, refes: {}} | |
| } | |
| } | |
| function shrink(form){ | |
| if(form instanceof Ref){ | |
| return shrink(form.ref) | |
| } else if(form instanceof Array){ | |
| return form.map(shrink) | |
| } else { | |
| return form | |
| } | |
| } | |
| console.log(shrink(redex(normalizeTerm(['begin', ['=', ['.', ['.yield', 'o'], 'm'], 'x']])).value)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment