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 都可以有更深入的了解和體會。

// 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;
}