divs1210 · September 13, 2023 09:42 · divs1210 · Sep 9, 2023
diff --git a/stackless-eval-playground.html b/stackless-eval-playground.html
 <html>
  <head>
    <script type="text/javascript">
 // Trampoline
 // ==========
 class Thunk {
    constructor(f) {
        this.f = f;
    }
 }

 function trampoline(f, ...args) {
    let t = new Thunk(() => f(...args));

    while(t instanceof Thunk)
        t = t.f();

    return t;
 }


 // Environment
 // ===========
 // builtin functions
 let TopEnv = {
    '<': (x, y) => x < y,
    '*': (x, y) => x * y,
    '-': (x, y) => x - y,
 };

 // TCOd lookup function
 // returns value bound to identifier
 // in current scope, else in ancestor scopes
 // throws error if not found
 function lookup(env, identifier) {
    while(env) {
        if (env.hasOwnProperty(identifier))
            return env[identifier];
        else
            env = env.__parent__;
    }
    throw new Error(`${identifier} is not defined!`);
 }


 // Util
 // ====
 // stackless map
 // with_mapped is the callback
 // t_mapper is a stackless function:
 //     (with_fx, x) => thunk
 function t_map(with_mapped, t_mapper, arr) {
    if (arr.length == 0)
        return new Thunk(() => with_mapped([]));

    return new Thunk(() => {
        let [x, ...more] = arr;
        return t_mapper(
            (fx) => t_map(
                (mapped_more) => new Thunk(() =>
                    // immutable push
                    with_mapped([fx].concat(mapped_more))),
                t_mapper,
                more
            ),
            x
        );
    });
 }


 // Evaluator
 // =========
 // stackless eval
 // with_evaled is the callback
 function t_eval(with_evaled, expr, env) {
    // env defaults to TopEnv
    env = env || TopEnv;

    if (typeof expr === 'number') {
        // numbers are parsed as BigInt
        return new Thunk(() => with_evaled(BigInt(expr)));
    } else if (typeof expr === 'string') {
        // strings are treated as identifiers (variable names)
        return new Thunk(() => with_evaled(lookup(env, expr)));
    } else if (Array.isArray(expr)) {
        // arrays are treated as "forms"
        // with the first element as the operator
        // and the remaining elements as the operands
        let [op, ...args] = expr;
        
        if (op === 'fn') {
            // user defined function
            let [params, body] = args;
            return new Thunk(() =>
                with_evaled(
                    {type: 'function', params, body, env}));
        } else if (op === 'do') {
            // runs several expressions sequentially,
            // then gives the value of the last expression
            // to the callback
            function with_subexpr_vals(subexpr_vals) {
                return new Thunk(() =>
                    with_evaled(subexpr_vals.at(-1)));
            }

            function t_mapper(with_subexpr_val, subexpr) {
                return new Thunk(() =>
                    t_eval(with_subexpr_val, subexpr, env));
            }

            return new Thunk(() =>
                t_map(with_subexpr_vals, t_mapper, args));
        } else if (op === 'def') {
            // defines a variable in the current env
            // and sets it to the given value
            let [identifier, valExpr] = args;

            function with_val(val) {
                env[identifier] = val;
                return new Thunk(() => with_evaled());
            }
            
            return new Thunk(() => t_eval(with_val, valExpr, env));
        } else if (op === 'if') {
            // if / else
            let [condExpr, thenExpr, elseExpr] = args;

            function with_cond_val(condVal) {
                return new Thunk(() =>
                    t_eval(with_evaled,
                           condVal? thenExpr : elseExpr,
                           env));
            }

            return new Thunk(() =>
                t_eval(with_cond_val, condExpr, env));
        } else {
            // function call
            function with_f(f) {
                function with_arg_vals(arg_vals) {
                    return new Thunk(() =>
                        t_apply(with_evaled, f, arg_vals));
                }

                function t_mapper(with_arg_val, arg_expr) {
                    return new Thunk(() =>
                        t_eval(with_arg_val, arg_expr, env));
                }

                return new Thunk(() =>
                    t_map(with_arg_vals, t_mapper, args));
            }
            
            return new Thunk(() => t_eval(with_f, op, env));
        }
    } else throw new Error(`invalid expression: ${expr}`);
 }

 function t_apply(with_res, f, args) {
    if (typeof f === 'function')
        // builtin function
        return new Thunk(() => with_res(f(...args)));
    else if (f.type === 'function') {
        // user defined function
        let {params, body, env} = f;
        let newEnv = {__parent__: env};
    
        for(let i = 0; i < params.length; i++)
            newEnv[params[i]] = args[i];
    
        return new Thunk(() => t_eval(with_res, body, newEnv));
    } else 
        throw new Error(`${f} is not a function!`);
 }

 // trampolined stackless eval
 function eval(expr, env) {
    let id = (x) => x;
    return trampoline(t_eval, id, expr, env);
 }

 // Read, Eval, Print
 function REP() {
    result.value = "working...";
    setTimeout(() => {
      result.value = eval(JSON.parse(code.value));
    }, 5);
 }
    </script>
  </head>
  <body style="background-color:black; color:white;">
    <center>
    <div width="80%">
        <textarea id="code" cols="80" rows="20" style="width: 100%; background-color:black; color:white;">["do",

 ["def", "fact",
  ["fn", ["x"],
   ["if", ["<", "x", 2],
    1,
    ["*", "x", ["fact", ["-", "x", 1]]]]]],
 
 ["fact", 5]]</textarea>
    </div>
    <button onclick="REP()">RUN</button>
    <div width="80%">
        <textarea id="result" readonly cols="80", rows="20" style="width: 100%; background-color:black; color:white;">
        </textarea>
    </div>
    </center>
  </body>
 </html>
	<html>
	<head>
	<script type="text/javascript">
	// Trampoline
	// ==========
	class Thunk {
	constructor(f) {
	this.f = f;
	}
	}

	function trampoline(f, ...args) {
	let t = new Thunk(() => f(...args));

	while(t instanceof Thunk)
	t = t.f();

	return t;
	}


	// Environment
	// ===========
	// builtin functions
	let TopEnv = {
	'<': (x, y) => x < y,
	'': (x, y) => x y,
	'-': (x, y) => x - y,
	};

	// TCOd lookup function
	// returns value bound to identifier
	// in current scope, else in ancestor scopes
	// throws error if not found
	function lookup(env, identifier) {
	while(env) {
	if (env.hasOwnProperty(identifier))
	return env[identifier];
	else
	env = env.__parent__;
	}
	throw new Error(`${identifier} is not defined!`);
	}


	// Util
	// ====
	// stackless map
	// with_mapped is the callback
	// t_mapper is a stackless function:
	// (with_fx, x) => thunk
	function t_map(with_mapped, t_mapper, arr) {
	if (arr.length == 0)
	return new Thunk(() => with_mapped([]));

	return new Thunk(() => {
	let [x, ...more] = arr;
	return t_mapper(
	(fx) => t_map(
	(mapped_more) => new Thunk(() =>
	// immutable push
	with_mapped([fx].concat(mapped_more))),
	t_mapper,
	more
	),
	x
	);
	});
	}


	// Evaluator
	// =========
	// stackless eval
	// with_evaled is the callback
	function t_eval(with_evaled, expr, env) {
	// env defaults to TopEnv
	env = env \|\| TopEnv;

	if (typeof expr === 'number') {
	// numbers are parsed as BigInt
	return new Thunk(() => with_evaled(BigInt(expr)));
	} else if (typeof expr === 'string') {
	// strings are treated as identifiers (variable names)
	return new Thunk(() => with_evaled(lookup(env, expr)));
	} else if (Array.isArray(expr)) {
	// arrays are treated as "forms"
	// with the first element as the operator
	// and the remaining elements as the operands
	let [op, ...args] = expr;

	if (op === 'fn') {
	// user defined function
	let [params, body] = args;
	return new Thunk(() =>
	with_evaled(
	{type: 'function', params, body, env}));
	} else if (op === 'do') {
	// runs several expressions sequentially,
	// then gives the value of the last expression
	// to the callback
	function with_subexpr_vals(subexpr_vals) {
	return new Thunk(() =>
	with_evaled(subexpr_vals.at(-1)));
	}

	function t_mapper(with_subexpr_val, subexpr) {
	return new Thunk(() =>
	t_eval(with_subexpr_val, subexpr, env));
	}

	return new Thunk(() =>
	t_map(with_subexpr_vals, t_mapper, args));
	} else if (op === 'def') {
	// defines a variable in the current env
	// and sets it to the given value
	let [identifier, valExpr] = args;

	function with_val(val) {
	env[identifier] = val;
	return new Thunk(() => with_evaled());
	}

	return new Thunk(() => t_eval(with_val, valExpr, env));
	} else if (op === 'if') {
	// if / else
	let [condExpr, thenExpr, elseExpr] = args;

	function with_cond_val(condVal) {
	return new Thunk(() =>
	t_eval(with_evaled,
	condVal? thenExpr : elseExpr,
	env));
	}

	return new Thunk(() =>
	t_eval(with_cond_val, condExpr, env));
	} else {
	// function call
	function with_f(f) {
	function with_arg_vals(arg_vals) {
	return new Thunk(() =>
	t_apply(with_evaled, f, arg_vals));
	}

	function t_mapper(with_arg_val, arg_expr) {
	return new Thunk(() =>
	t_eval(with_arg_val, arg_expr, env));
	}

	return new Thunk(() =>
	t_map(with_arg_vals, t_mapper, args));
	}

	return new Thunk(() => t_eval(with_f, op, env));
	}
	} else throw new Error(`invalid expression: ${expr}`);
	}

	function t_apply(with_res, f, args) {
	if (typeof f === 'function')
	// builtin function
	return new Thunk(() => with_res(f(...args)));
	else if (f.type === 'function') {
	// user defined function
	let {params, body, env} = f;
	let newEnv = {__parent__: env};

	for(let i = 0; i < params.length; i++)
	newEnv[params[i]] = args[i];

	return new Thunk(() => t_eval(with_res, body, newEnv));
	} else
	throw new Error(`${f} is not a function!`);
	}

	// trampolined stackless eval
	function eval(expr, env) {
	let id = (x) => x;
	return trampoline(t_eval, id, expr, env);
	}

	// Read, Eval, Print
	function REP() {
	result.value = "working...";
	setTimeout(() => {
	result.value = eval(JSON.parse(code.value));
	}, 5);
	}
	</script>
	</head>
	<body style="background-color:black; color:white;">
	<center>
	<div width="80%">
	<textarea id="code" cols="80" rows="20" style="width: 100%; background-color:black; color:white;">["do",

	["def", "fact",
	["fn", ["x"],
	["if", ["<", "x", 2],
	1,
	["*", "x", ["fact", ["-", "x", 1]]]]]],

	["fact", 5]]</textarea>
	</div>
	<button onclick="REP()">RUN</button>
	<div width="80%">
	<textarea id="result" readonly cols="80", rows="20" style="width: 100%; background-color:black; color:white;">
	</textarea>
	</div>
	</center>
	</body>
	</html>