107 lines
2.2 KiB
TypeScript
107 lines
2.2 KiB
TypeScript
const peggy = require("./parser.js");
|
|
|
|
const isVariable = (ast: any) => typeof ast === "string";
|
|
const isApplication = (ast: any) =>
|
|
typeof ast === "object" && "application" in ast;
|
|
const isAbstraction = (ast: any) =>
|
|
typeof ast === "object" && "abstraction" in ast;
|
|
|
|
const emitCode = (ast: any) => {
|
|
if (isVariable(ast)) {
|
|
return ast;
|
|
}
|
|
|
|
if (isApplication(ast)) {
|
|
const { application } = ast;
|
|
const { left, right } = application;
|
|
return `( ${emitCode(left)} ${emitCode(right)} )`;
|
|
}
|
|
|
|
const { abstraction } = ast;
|
|
const { param, body } = abstraction;
|
|
|
|
return `(λ ${emitCode(param)} . ${emitCode(body)})`;
|
|
};
|
|
|
|
const substitute = (param: string, term: any, result: any) => {
|
|
if (isVariable(term)) {
|
|
if (term === param) {
|
|
return result;
|
|
}
|
|
return term;
|
|
}
|
|
|
|
if (isApplication(term)) {
|
|
const { application } = term;
|
|
const { left, right } = application;
|
|
|
|
return {
|
|
application: {
|
|
left: substitute(param, left, result),
|
|
right: substitute(param, right, result),
|
|
},
|
|
};
|
|
}
|
|
|
|
const { abstraction } = term;
|
|
const { body } = abstraction;
|
|
return {
|
|
abstraction: {
|
|
param: abstraction.param,
|
|
body: substitute(param, body, result),
|
|
},
|
|
};
|
|
};
|
|
|
|
const betaReduce = (ast: any) => {
|
|
if (isVariable(ast)) {
|
|
return ast;
|
|
}
|
|
|
|
if (isApplication(ast)) {
|
|
const { application } = ast;
|
|
const { left, right } = application;
|
|
|
|
if (isAbstraction(left)) {
|
|
const { abstraction } = left;
|
|
const { param } = abstraction;
|
|
|
|
return substitute(param, right);
|
|
}
|
|
|
|
return {
|
|
application: {
|
|
left: betaReduce(left),
|
|
right: betaReduce(right),
|
|
},
|
|
};
|
|
}
|
|
|
|
// it's an abstraction
|
|
const { abstraction } = ast;
|
|
const { param, body } = abstraction;
|
|
return { param: betaReduce(param), body: betaReduce(body) };
|
|
};
|
|
|
|
const evaluate = (lambdaTerm: string) => {
|
|
const ast = peggy.parse(lambdaTerm);
|
|
|
|
const fullBetaReduction = betaReduce(ast);
|
|
return emitCode(fullBetaReduction);
|
|
};
|
|
|
|
const doRepl = async () => {
|
|
const prompt = ">>> ";
|
|
process.stdout.write(prompt);
|
|
|
|
for await (const line of console) {
|
|
const result = evaluate(line);
|
|
console.log(result);
|
|
break;
|
|
}
|
|
|
|
await doRepl();
|
|
};
|
|
|
|
await doRepl();
|