Skip to content

Instantly share code, notes, and snippets.

@be5invis

be5invis/jsbin.dakin.html

Last active August 29, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save be5invis/630c7c075432430682ba to your computer and use it in GitHub Desktop.
Save be5invis/630c7c075432430682ba to your computer and use it in GitHub Desktop.
Download ZIP
Raw
jsbin.dakin.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JS Bin</title>
</head>
<body>
</body>
</html>
Raw
jsbin.dakin.js
// CPS-style Deorthogonalification, based on Danvy and Filinski's work
function isStatement(form){
return form instanceof Array && (form[0] === '.if' || form[0] === '.begin' || form[0] === '.return' || form[0] === '.while')
}
var newt = function(){
var n = 0;
return function(){
return '_t' + (++n);
};
}();
// Optimization: Find out all expression-only subtrees.
// [.lambda]'s are regularized in this procedure
function plain(form){
if(form instanceof Array){
if(form[0] === '.lambda'){
return ['.plain', ['.lambda', form[1], rs(plain(form[2]), id)]]
} else if(form[0] === '.quote') {
return ['.plain', form]
} else if(isStatement(form)){
return [form[0]].concat(form.slice(1).map(plain))
} else {
var j0 = (typeof form[0] === 'string' && !(/\w/.test(form[0]))) ? 1 : 0;
var a = form.slice(0, j0).concat(form.slice(j0).map(plain));
console.log(a);
for(var j = j0; j < a.length; j++){
if(!(a[j] && (a[j][0] === '.plain'))){
return a
}
};
return ['.plain', a.slice(0, j0).concat(a.slice(j0).map(function(x){ return x[1] }))];
}
} else if(typeof form === 'string') {
if(/^\w/.test(form)) return ['.plain', form]
else return form
} else {
return form
}
}
function id(x){ return x }
// RS: regularize in statement environment, with return value dropped
function rs(form, ctx){
if(form instanceof Array){
if(form[0] === '.return'){
return re(form[1], function(x){
return ['.return', x]
})
} else if(form[0] === '.if'){
return re(form[1], function(c){
if(form[3]){
return ctx(['.if', c, rs(form[2], id), rs(form[3], id)])
} else {
return ctx(['.if', c, rs(form[2], id)])
}
})
} else if(form[0] === '.while'){
if(form[1] instanceof Array && form[1][0] === '.plain'){
return ctx(['.while', form[1][1], rs(form[2], id)])
} else {
return ra(form[1], function(t){
return ctx(['.while', t, rs(form[2], function(x){
return ['.begin', x, re(form[1], function(x){ return ['=', t, x]})]
})])
})
}
} else if(form[0] === '.begin'){
if(form.length > 2) {
return rs(form[1], function(e){
return ['.begin', e, rs(['.begin'].concat(form.slice(2)), ctx)]
})
} else if(form.length === 2) {
return rs(form[1], ctx)
} else {
return ctx(['.unit'])
}
} else {
return re(form, ctx)
}
} else {
return re(form, ctx)
}
}
// RE: regularize in expression environment, keep return value
function re(form, ctx){
if(!form) {
return ctx(['.unit'])
} else if(form instanceof Array){
if(form[0] === '.lambda' || form[0] === '.quote' || form[0] === '.unit') {
// Lambdas are regularized, just pass it into ctx
return ctx(form)
} else if(form[0] === '.if'){
return re(form[1], function(c){
var t = newt();
return ['.begin',
['.if', c,
re(form[2], function(x){ return ['=', t, x]}),
re(form[3], function(x){ return ['=', t, x]})],
ctx(t)
]
})
} else if(form[0] === '.while'){
return ra(form[1], function(c){
var t = newt();
return ['.begin', ['.while', t, re(form[2], function(x){
return ['.begin', ['=', t, x], re(form[1], function(x){ return ['=', c, x] })]
})], ctx(t)]
});
} else if(form[0] === '.return'){
return re(form[1], function(x){
return ['.begin', ['.return', x]]
})
} else if(form[0] === '=') {
return rAssign(form, ctx)
} else if(form[0] === '.begin') {
return re$b(form.slice(1), ctx)
} else if(form[0] === '.plain') {
return ctx(form[1])
} else {
return recall(form, ctx)
}
} else {
return ctx(form)
}
}
function ra(form, ctx){
return re(form, function(x){
if(typeof x === 'string' && x[0] === '_'){
return ctx(x)
} else {
var t = newt();
return ['.begin', ['=', t, x], ctx(t)]
}
})
}
function re$(form, ctx){
if(!form.length) return ctx(null)
return ra(form[0], function(x0){
return re$(form.slice(1), function(x$){
if(x$) return ctx([x0].concat(x$))
else return ctx([x0])
})
})
}
function re$b(form, ctx){
if(!form.length) return ctx(null)
else if(form.length === 1) return ra(form[0], ctx)
return rs(form[0], function(x0){
return ['.begin', x0, re$b(form.slice(1), function(x$){
if(x$) return ctx(x$)
else return ctx(x0)
})]
})
}
function recall(form, ctx){
if(form[0] instanceof Array && form[0][0] === '.'){
return ra(form[0][1], function(xl){
return ra(form[0][2], function(xr){
return re$(form.slice(1), function(x$){
if(x$) return ctx([['.', xl, xr]].concat(x$))
else return ctx([['.', xl, xr]])
})
})
})
} else {
return re$(form, ctx)
}
}
function rAssign(form, ctx){
if(form[1] instanceof Array && form[1][0] === '.'){
return ra(form[1][1], function(xl){
return ra(form[1][2], function(xr){
return ra(form[2], function(r){
return ctx(['=', ['.', xl, xr], r])
})
})
})
} else {
var left = form[1];
while(left instanceof Array && left[0] === '.plain') left = left[1];
return ra(form[2], function(r){
return ctx(['=', left, r])
})
}
}
function mb(form){
if(form instanceof Array && form[0] === '.begin'){
var a = form.slice(1).map(mb);
var res = [];
for(var j = 0; j < a.length; j++){
if(a[j] instanceof Array && a[j][0] === '.begin'){
res = res.concat(a[j].slice(1))
} else {
res.push(a[j])
}
};
return ['.begin'].concat(res);
} else if(form instanceof Array){
return form.map(mb)
} else {
return form
}
}
var form = plain(['f', ['.lambda', ['x'], ['.return', ['phi', ['.begin', 'a', ['.return', 'b'], 'c']]]]]);
console.log(form);
console.log(mb(rs(form, id)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment