Skip to content

Instantly share code, notes, and snippets.

@wchargin
Created Apr 9, 2021
Embed
What would you like to do?
two simple lambda calculi
/*::
type Expr =
| { type: "VAR", name: string }
| { type: "LAM", param: string, body: Expr }
| { type: "APP", fn: Expr, arg: Expr }
*/
function vr(name) {
return { type: "VAR", name };
}
function lam(param, body) {
return { type: "LAM", param, body };
}
function app(fn, arg) {
return { type: "APP", fn, arg };
}
function substitute(value, name, expr) {
// console.log(` [${print(value)}/${name}] ${print(expr)}`);
switch (expr.type) {
case "VAR":
if (expr.name === name) {
return value;
} else {
return expr;
}
case "LAM":
if (expr.param === name) {
return expr;
} else {
const newBody = substitute(value, name, expr.body);
return lam(expr.param, newBody);
}
case "APP": {
const newFn = substitute(value, name, expr.fn);
const newArg = substitute(value, name, expr.arg);
return app(newFn, newArg);
}
}
}
function print(expr) {
switch (expr.type) {
case "VAR":
return expr.name;
case "LAM":
return ${expr.param}. ${print(expr.body)}`;
case "APP":
return `(${print(expr.fn)}) (${print(expr.arg)})`;
}
}
function step(expr) {
switch (expr.type) {
case "VAR":
case "LAM":
return null;
case "APP": {
const { fn, arg } = expr;
const fnStep = step(expr.fn);
if (fnStep !== null) return app(fnStep, arg);
const argStep = step(expr.arg);
if (argStep !== null) return app(fn, argStep);
if (fn.type !== "LAM") {
throw new Error(`application of non-function: ${print(expr)}`);
}
const { param, body } = fn;
return substitute(arg, param, body);
}
}
}
function eval(expr, limit = 20) {
while (limit-- > 0) {
if (expr === null) return;
console.log(print(expr));
expr = step(expr);
}
console.log("[reached recursion limit]");
}
eval(
app(
app(lam("x", lam("y", vr("x"))), vr("k")),
app(lam("z", vr("z")), vr("m"))
)
);
const omega = lam("z", app(vr("z"), vr("z")));
eval(app(omega, omega));
type expr =
| Var of string
| Lam of string * expr
| App of expr * expr
let var name = Var name
let lam param body = Lam (param, body)
let app fn arg = App (fn, arg)
let rec show : expr -> string = function
| Var name -> name
| Lam (param, body) -> Printf.sprintf "λ%s. %s" param (show body)
| App (fn, arg) -> Printf.sprintf "(%s) (%s)" (show fn) (show arg)
let rec substitute (v : expr) (x : string) (e : expr) : expr =
match e with
| Var name -> if name = x then v else e
| Lam (param, body) ->
if param = x
then e
else Lam (param, substitute v x body)
| App (fn, arg) ->
App (substitute v x fn, substitute v x arg)
let rec step : expr -> expr option = function
| Var _ -> None
| Lam _ -> None
| App (fn, arg) ->
match step fn with Some fn -> Some (App (fn, arg)) | None ->
match step arg with Some arg -> Some (App (fn, arg)) | None ->
match fn with
| Lam (param, body) -> Some (substitute arg param body)
| _ -> failwith (Printf.sprintf
"stepped App of non-lambda: %s" (show (App (fn, arg))))
let rec eval ?(limit : int = 10) (e : expr) : unit =
if limit <= 0 then Printf.printf "[hit recursion limit]\n\n" else (
Printf.printf "%s\n" (show e);
match step e with
| None -> Printf.printf "[done]\n\n"
| Some e -> eval ~limit:(limit - 1) e
)
let () = eval (app (lam "x" (lam "y" (var "x"))) (var "k"))
let omega = lam "z" (app (var "z") (var "z"))
let () = eval (app omega omega)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment