gistfile1.js

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] === 'await') {
			var t = newt();
			return normalize(form[1], function(n){
				return [n, [':LAMBDA', [t], ctx(t)]]
			})
		} 
		else return normalizeName$(form, ctx)
	} else {
		return ctx([':GETV', form])
	}
}
function normalizeName(form, ctx){
	return normalize(form, function(n){
		var t = newt();
		return [':LET', t, n, ctx(t)]
	})
}
function normalizeName$(form, ctx){
	if(!form.length){
		return ctx(null)
	} else {
		return normalizeName(form[0], function(t){
			return normalizeName$(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((normalizeTerm(['f', ['g', 'a', 'b', 'c'], ['await', 'b'], 'c']))))
console.log(shrink((normalizeTerm(['f', ['g', 'a', ['b'], 'c'], ['await', 'b'], 'c']))))
console.log(shrink((normalizeTerm(['f', ['g', 'a', ['await', 'b'], 'c'], ['await', 'b'], 'c']))))
console.log(shrink(redex(normalizeTerm(['f', ['g', 'a', 'b', 'c'], ['await', 'b'], 'c'])).value))
console.log(shrink(redex(normalizeTerm(['f', ['g', 'a', ['b'], 'c'], ['await', 'b'], 'c'])).value))
console.log(shrink(redex(normalizeTerm(['f', ['g', 'a', ['await', 'b'], 'c'], ['await', 'b'], 'c'])).value))