1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
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();
|
