TIOJ::1821.基本語(NPSC 古可魚語)

http://tioj.ck.tp.edu.tw/problems/1821

這題是很經典的題目(?)
題目很簡單,就是給你一些語法,要你實作一個直譯器。

題目應該很好找,是NPSC的老題目,這是TIOJ的題目連結:http://web2.ck.tp.edu.tw/~step5/img/problem/0153/pH.pdf

這題題目簡單,實作起來卻很複雜。
我是在看了一本書講Python實作概論,才忽然興起決定來寫這題。

首先就是有數種語法,基本上不難寫。
只有一種型別,就是數字。
最困難的大概就是lambda這個語法了。

實作起來第一個難關就是Parser,不過基本上語法很好解析,就是用小括號括起來的就是一句話,話裡面也可以遞迴的有話,基本上每句話就是一個函數,都有一個回傳值。唯一例外是數字和代表數字的變數可能直接出現沒有括號。

所以基本上可以把所有的語句都當作函數去實作,不過我是把幾個語句 begin, if 等等的直接當作語句去實作了,畢竟函數呼叫很耗資源。
display 是一定要當作函數實作的,因為他可以被當作函數傳入函數中呼叫(callback),不過題目有另外保證不會用define語句去定義display的別名(不過其實要定義也沒差就是了)。

我實作的方式就是參考 Python 的實作方式的精簡版,先宣告一個基本的物件 OF_Obj,之後所有的物件都包含這個物件,這樣指標就可以互相轉型,基本的介面就全部用 OF_Obj 來溝通。
其中 OF_Obj 中有實作引用計數,不過這題是你直接複製也不會爆記憶體的,所以也可以不要實作引用計數或乾脆不要回收記憶體,當然現實中這樣是很不好的。

然後我定義了一些 bin code ,並在Parse函數中把語句轉成編譯好的 bin code,也就是轉成一個數字組成的 vector ,並把常數存到另外一個 vector 裡(常數都是 OF_Obj ),變數名字存進一個 string 的 vector中,這樣的結構組成一個 OF_Code 物件。

之後我就可以把這個物件傳入 exec 函數中執行,基本概念就是有一個 Stack 和一個 dict(用 unordered_map 實作), 每個數字對應一個指令,利用指令操作 Stack 來達到我們想要的操作。
像是 define 就是先把後面的值壓入 Stack 中,然後執行指令 STORE_NAME ,找出對應的名字並把名字和 Stack 的 Top 存進 dict 裡面,之後變數就從這個 dict 裡面讀取。

至於 lambda 比較複雜,我們必須要編譯出另外一個 OF_Code 物件,並把他指定給一個 OF_Fun 物件。
參數傳遞就直接當作 define 語句就可以了。
重點是環境(那個存了變數的 dict ),也就是變數的連結。
按照題目敘述,優先參考的是函數參數,接著是定義的時候的環境,再來還有一個就是執行的時候的環境。於是我們可以發現古可魚語是可以實作閉包的(範測就可以看的到)。
我的作法很簡單,把函數定義時的環境直接複製一遍並存起來。之後呼叫的時候再把環境複製一變,並把函數定義時的環境覆蓋過去,最後才把參數定義出來,這樣就可以完成閉包了。
因為都是指標,所以複製是很廉價的,再加上有引用計數所以可以不用擔心變數的存活問題。

總結一下,運行的順序就是,吃一句話,編譯,執行,吃下一句話。

最後推薦一下我跟朋友借來看的書,「Python 源码剖析」。
這本書是中國人寫的,內容是分析 CPython 的原始碼,並透過重新編譯 Python 讓我們驗證我們的假設。分析的很仔細又不會太冗長,對 Python 和 C 都可以有更深入的了解和體會。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
// Bin Code
#define PRINT 0
#define POP_TOP 1
// #define SWP_TOP 2
#define NUM_ADD 3
#define NUM_SUB 4
#define NUM_CMP 5
#define LOAD_NUM 90
#define STORE_NAME 91
#define LOAD_NAME 92
#define JUMP_IF_FALSE 93
// #define JUMP_IF_TRUE 94
#define JUMP_FORWARD 95
#define MAKE_FUN 96
#define CALL_FUN 97
#include <bits/stdc++.h>
#define dict unordered_map
using namespace std;
#define OF_HEAD(x) char c=x; int ref=1
struct OF_Obj{
OF_HEAD('O');
};
#define INC(ob) ((ob)->ref++)
void delete_obj(OF_Obj*);
#define DEC(ob) if(--(ob)->ref == 0)delete_obj((OF_Obj*)(ob))
struct OF_Int{
OF_HEAD('I');
int val;
OF_Int(int w): val(w){ }
}OF_True(1), OF_False(0);
struct OF_Code{
OF_HEAD('C');
vector<int> code;
vector<OF_Obj*> num;
vector<string> name;
~OF_Code(){
for(auto p:num)DEC(p);
}
};
struct OF_Fun{
OF_HEAD('F');
OF_Code *co;
dict<string, OF_Obj*> env;
OF_Fun():co(NULL){ }
~OF_Fun(){
if(co)DEC(co);
for(auto p:env)DEC(p.second);
}
};
void delete_obj(OF_Obj *ob){
if(ob->c=='O')delete ob;
if(ob->c=='I')delete (OF_Int*)ob;
if(ob->c=='C')delete (OF_Code*)ob;
if(ob->c=='F')delete (OF_Fun*)ob;
}
string getString(){
string s;
char c;
if(!(cin>>c)) return s;
s += c;
if(c=='(' || c==')' || c==';') return s;
while(c = cin.peek()){
if(c==' ' || c=='\n' || c=='(' || c==')') return s;
s += c;
cin.ignore(1);
}
}
bool isNumber(const string &s){
for(char c:s) if(!isdigit(c)) return false;
return true;
}
void OF_assert(bool ok){
if(ok)return;
throw 1;
}
void parse_sen(OF_Code *co, dict<OF_Obj*, int> *num, dict<string, int> *name, string s, bool is_fun=false){
if(s == "("){
s = getString();
parse_sen(co, num, name, s, true);
if(is_fun){
int an = 0;
while(s = getString(), s != ")"){
parse_sen(co, num, name, s);
an++;
}
co -> code.push_back(CALL_FUN);
co -> code.push_back(1);
co -> code.push_back(an);
}
}else if(s == ")"){
OF_assert(false);
}else if(is_fun && s == "begin"){
while(1){
s = getString();
if(s != ")"){
parse_sen(co, num, name, s);
co -> code.push_back(POP_TOP);
}else{
co -> code.pop_back();
break;
}
}
}else if(is_fun && s == "if"){
parse_sen(co, num, name, getString());
co -> code.push_back(JUMP_IF_FALSE);
co -> code.push_back(1);
co -> code.push_back(-1);
int p1 = co -> code.size()-1;
co -> code.push_back(POP_TOP);
parse_sen(co, num, name, getString());
co -> code.push_back(JUMP_FORWARD);
co -> code.push_back(1);
co -> code.push_back(-1);
int p2 = co -> code.size()-1;
co -> code.push_back(POP_TOP);
parse_sen(co, num, name, getString());
int p3 = co -> code.size()-1;
s = getString();
OF_assert(s == ")");
co -> code[p1] = p2-p1;
co -> code[p2] = p3-p2;
}else if(is_fun && s=="+" || s=="-" || s=="<"){
parse_sen(co, num, name, getString());
parse_sen(co, num, name, getString());
if(s=="+")co -> code.push_back(NUM_ADD);
if(s=="-")co -> code.push_back(NUM_SUB);
if(s=="<")co -> code.push_back(NUM_CMP);
s = getString();
OF_assert(s == ")");
}else if(is_fun && s=="define"){
s = getString();
OF_assert(s!="display");
parse_sen(co, num, name, getString());
if(name->find(s) == name->end()){
(*name)[s] = co -> name.size();
co -> name.push_back(s);
}
co -> code.push_back(STORE_NAME);
co -> code.push_back(1);
co -> code.push_back((*name)[s]);
s = getString();
OF_assert(s == ")");
}else if(is_fun && s=="lambda"){
OF_Code *nc = new OF_Code();
dict<OF_Obj*, int> *nnum = new dict<OF_Obj*, int>();
dict<string, int> *nname = new dict<string, int>();
s = getString(); OF_assert(s=="(");
for(s = getString(); s!=")"; s = getString()){
if(nname->find(s) == nname->end()){
(*nname)[s] = nc -> name.size();
nc -> name.push_back(s);
}
nc -> code.push_back(STORE_NAME);
nc -> code.push_back(1);
nc -> code.push_back((*nname)[s]);
nc -> code.push_back(POP_TOP);
}
parse_sen(nc, nnum, nname, getString());
delete nnum;
delete nname;
s = getString();
OF_assert(s == ")");
(*num)[(OF_Obj*)nc] = co-> num.size();
co -> num.push_back((OF_Obj*)nc);
co -> code.push_back(MAKE_FUN);
co -> code.push_back(1);
co -> code.push_back((*num)[(OF_Obj*)nc]);
}else if(isNumber(s)){
int w = atoi(s.c_str());
OF_Obj *i = (OF_Obj*)new OF_Int(w);
if(num->find(i) == num->end()){
(*num)[i] = co -> num.size();
co -> num.push_back(i);
}
co -> code.push_back(LOAD_NUM);
co -> code.push_back(1);
co -> code.push_back((*num)[i]);
}else{
if(name->find(s) == name->end()){
(*name)[s] = co -> name.size();
co -> name.push_back(s);
}
co -> code.push_back(LOAD_NAME);
co -> code.push_back(1);
co -> code.push_back((*name)[s]);
if(is_fun){
int an = 0;
while(s = getString(), s != ")"){
parse_sen(co, num, name, s);
an++;
}
co -> code.push_back(CALL_FUN);
co -> code.push_back(1);
co -> code.push_back(an);
}
}
}
OF_Code* parse(){
OF_Code *co = new OF_Code();
dict<OF_Obj*, int> num;
dict<string, int> name;
string s;
while(1){
s = getString();
if(s == "")return NULL;
if(s == ";"){
getline(cin, s);
cout<<";"<<s<<endl;
continue;
}
OF_assert(s == "(");
parse_sen(co, &num, &name, getString(), true);
co -> code.push_back(POP_TOP);
return co;
}
}
vector<int> load_arg(vector<int>::iterator &p){
vector<int> arg;
int len = *(p++);
while(len--)arg.push_back(*(p++));
return arg;
}
void exec(OF_Code *co, dict<string, OF_Obj*> *env, stack<OF_Obj*> *st){
auto p = co->code.begin();
int now, i;
OF_Obj *w, *v, *u;
OF_Fun *fun;
stack<OF_Obj*> *nst;
dict<string, OF_Obj*> *nenv;
string s;
vector<int> arg;
while(p != co->code.end()){
now = *(p++);
if(now >= 90)arg = load_arg(p);
switch(now){
case PRINT:
w = st -> top(); st -> pop();
v = (OF_Obj*)&OF_False;
cout<<((OF_Int*)w)->val<<'\n';
st -> push(v);
INC(v);
DEC(w);
break;
case POP_TOP:
w = st -> top(); st -> pop();
DEC(w);
break;
case NUM_ADD:
w = st -> top(); st -> pop();
v = st -> top(); st -> pop();
u = (OF_Obj*)new OF_Int(((OF_Int*)v)->val + ((OF_Int*)w)->val);
st->push(u);
DEC(w);
DEC(v);
break;
case NUM_SUB:
w = st -> top(); st -> pop();
v = st -> top(); st -> pop();
u = (OF_Obj*)new OF_Int(((OF_Int*)v)->val - ((OF_Int*)w)->val);
st->push(u);
DEC(w);
DEC(v);
break;
case NUM_CMP:
w = st -> top(); st -> pop();
v = st -> top(); st -> pop();
u = (OF_Obj*)((((OF_Int*)v)->val < ((OF_Int*)w)->val) ? &OF_True : &OF_False);
st -> push(u);
INC(u);
DEC(w);
DEC(v);
break;
// ---- arg ----
case LOAD_NUM:
w = co->num[arg[0]];
st -> push(w);
INC(w);
break;
case STORE_NAME:
s = co->name[arg[0]];
w = st -> top();
(*env)[s] = w;
INC(w);
break;
case LOAD_NAME:
s = co->name[arg[0]];
w = (*env)[s];
OF_assert(st != NULL);
st -> push(w);
INC(w);
break;
case JUMP_IF_FALSE:
w = st -> top();
if(!(((OF_Int*)w)->val))p += arg[0];
break;
case JUMP_FORWARD:
p += arg[0];
break;
case MAKE_FUN:
fun = new OF_Fun();
w = co -> num[arg[0]];
fun -> co = (OF_Code*)w;
fun -> env = dict<string, OF_Obj*>(*env);
for(auto p:fun->env)INC(p.second);
st -> push((OF_Obj*)fun);
INC(w);
break;
case CALL_FUN:
nst = new stack<OF_Obj*>();
i = arg[0];
OF_assert(st->size()>=i+1);
while(i--)nst->push(st->top()), st->pop();
fun = (OF_Fun*)st -> top(); st -> pop();
nenv = new dict<string, OF_Obj*>(*env);
for(auto p: *nenv)INC(p.second);
for(auto p: fun->env){
auto q = nenv->find(p.first);
if(q != nenv -> end()){
DEC(q->second);
q->second = p.second;
}else{
nenv -> insert(make_pair(p.first, p.second));
}
INC(p.second);
}
exec(fun->co, nenv, nst);
OF_assert(nst->size()>0);
st->push(nst->top()); nst->pop();
for(auto p: *nenv)DEC(p.second);
delete nenv;
OF_assert(nst->size()==0);
delete nst;
DEC(fun);
break;
}
}
}
main(){
dict<string, OF_Obj*> env;
stack<OF_Obj*> st;
OF_Fun* disp = new OF_Fun();
disp -> co = new OF_Code();
disp -> co -> code.push_back(PRINT);
env[string("display")] = (OF_Obj*)disp;
while(1){
OF_Code *co;
try{
co = parse();
}catch(int e){
cout<<"Syntax Error!"<<endl;
continue;
}
if(co == NULL)break;
// for(int i: co->code){
// cout<<" --- # "<<i<<endl;
// }
// cout<<" --- # Start Code..."<<endl;
try{
exec(co, &env, &st);
}catch(int e){
cout<<"Runtime Error!"<<endl;
}
// cout<<"END: "<<st.size()<<endl;
// cout<<" --- # END Code..."<<endl;
DEC(co);
}
for(auto p:env)DEC(p.second);
// cout<<" --- # END All...."<<endl;
}