two simple lambda calculi

lc.js

/*::
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));

lc.ml

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)