From e782bbeb805fffaaa4a118fb88be96894ac68c28 Mon Sep 17 00:00:00 2001 From: Teddy Date: Fri, 9 Aug 2013 09:16:48 +0800 Subject: deal with circular reference --- Makefile | 2 +- builtin.cpp | 1 - main.cpp | 2 +- model.cpp | 68 +++++++++++++++++++++++++++++++++++++++---------------------- model.h | 16 ++++++++++----- 5 files changed, 57 insertions(+), 32 deletions(-) diff --git a/Makefile b/Makefile index 790d71e..07feba0 100644 --- a/Makefile +++ b/Makefile @@ -2,7 +2,7 @@ main: main.o parser.o builtin.o model.o eval.o exc.o consts.o g++ -o main $^ -pg -lgmp .cpp.o: - g++ $< -c -O2 -g -pg -DGMP_SUPPORT + g++ $< -c -g -pg -DGMP_SUPPORT clean: rm -f *.o diff --git a/builtin.cpp b/builtin.cpp index 56ed81c..cec007e 100644 --- a/builtin.cpp +++ b/builtin.cpp @@ -1,4 +1,3 @@ -#include "exc.h" #include "consts.h" #include "builtin.h" #include "model.h" diff --git a/main.cpp b/main.cpp index ba47a6a..8f7683f 100644 --- a/main.cpp +++ b/main.cpp @@ -6,7 +6,7 @@ #include int main() { -// freopen("in.scm", "r", stdin); + //freopen("in.scm", "r", stdin); Tokenizor *tk = new Tokenizor(); ASTGenerator *ast = new ASTGenerator(); Evaluator *eval = new Evaluator(); diff --git a/model.cpp b/model.cpp index 87e6b69..8599bd0 100644 --- a/model.cpp +++ b/model.cpp @@ -4,6 +4,7 @@ #include "consts.h" static ReprCons *repr_stack[REPR_STACK_SIZE]; +EvalObjAddrHash hash; FrameObj::FrameObj(ClassType _ftype) : ftype(_ftype) {} @@ -59,30 +60,40 @@ bool EvalObj::is_true() { } string EvalObj::ext_repr() { + hash.clear(); + // TODO: Performance improvement + // (from possibly O(n^2logn) to strictly O(nlogn)) ReprCons **top_ptr = repr_stack; *top_ptr++ = this->get_repr_cons(); - //printf("%s\n", (this->get_repr_cons())->repr.c_str()); EvalObj *obj; + hash.insert(this); while (!(*repr_stack)->done) { if ((*(top_ptr - 1))->done) { - top_ptr--; - obj = (*(top_ptr - 1))->next((*top_ptr)->repr + " "); + hash.erase((*--top_ptr)->ori); + obj = (*(top_ptr - 1))->next((*top_ptr)->repr); if (obj) + { *top_ptr++ = obj->get_repr_cons(); + if (hash.count((*(top_ptr - 1))->ori)) + *(top_ptr - 1) = new ReprStr("#cyc#"); + } else - { *(top_ptr - 1) = new ReprStr((*(top_ptr - 1))->repr); - } } else { obj = (*(top_ptr - 1))->next(""); *top_ptr++ = obj->get_repr_cons(); + if (hash.count((*(top_ptr - 1))->ori)) + *(top_ptr - 1) = new ReprStr("#cyc#"); } } - return (*repr_stack)->repr; + string &res = (*repr_stack)->repr; + if (this->is_pair_obj()) + res = "(" + res + ")"; + return res; } Pair::Pair(EvalObj *_car, EvalObj *_cdr) : @@ -90,7 +101,7 @@ Pair::Pair(EvalObj *_car, EvalObj *_cdr) : next(NULL) {} ReprCons *Pair::get_repr_cons() { - return new ListReprCons(this); + return new PairReprCons(this, this); } RetAddr::RetAddr(Pair *_addr) : FrameObj(CLS_RET_ADDR), addr(_addr) {} @@ -224,7 +235,7 @@ void VecObj::push_back(EvalObj *new_elem) { } ReprCons *VecObj::get_repr_cons() { - return new VectReprCons(this); + return new VectReprCons(this, this); } StrObj *StrObj::from_string(string repr) { @@ -278,38 +289,47 @@ Continuation::Continuation(Environment *_envt, Pair *_pc, envt(_envt), pc(_pc), prev_cont(_prev_cont), proc_body(_proc_body) {} -ReprCons::ReprCons(bool _done) : done(_done) {} +ReprCons::ReprCons(bool _done, EvalObj *_ori) : done(_done), ori(_ori) {} ReprStr::ReprStr(string _repr) : ReprCons(true) { repr = _repr; } EvalObj *ReprStr::next(const string &prev) { throw NormalError(INT_ERR); } -ListReprCons::ListReprCons(Pair *_ptr) : - ReprCons(false), ptr(_ptr) { repr = "("; } +PairReprCons::PairReprCons(Pair *_ptr, EvalObj *_ori) : + ReprCons(false, _ori), ptr(_ptr), state(0) {} -EvalObj *ListReprCons::next(const string &prev) { +EvalObj *PairReprCons::next(const string &prev) { repr += prev; EvalObj *res; - if (ptr->is_simple_obj()) + if (state == 0) { - repr += ". "; - res = ptr; - ptr = empty_list; + state = 1; + res = TO_PAIR(ptr)->car; + if (res->is_pair_obj()) + repr += "("; return res; } - if (ptr == empty_list) + else if (state == 1) + { + state = 2; + if (TO_PAIR(ptr)->car->is_pair_obj()) + repr += ")"; + ptr = TO_PAIR(ptr)->cdr; + repr += " "; + if (ptr->is_simple_obj()) + repr += ". "; + if (ptr == empty_list) + return NULL; + return ptr; + } + else { - *repr.rbegin() = ')'; return NULL; } - - res = TO_PAIR(ptr)->car; - ptr = TO_PAIR(ptr)->cdr; - return res; } -VectReprCons::VectReprCons(VecObj *_ptr) : - ReprCons(false), ptr(_ptr), idx(0) { repr = "#("; } +VectReprCons::VectReprCons(VecObj *_ptr, EvalObj *_ori) : + ReprCons(false, _ori), ptr(_ptr), idx(0) { repr = "#("; } EvalObj *VectReprCons::next(const string &prev) { repr += prev; diff --git a/model.h b/model.h index dfbca59..7a53c8e 100644 --- a/model.h +++ b/model.h @@ -5,11 +5,13 @@ #include #include #include +#include using std::list; using std::string; using std::map; using std::vector; +using std::set; // the range of unsigned char is enough for these types typedef unsigned char ClassType; @@ -113,7 +115,9 @@ class EvalObj : public FrameObj { virtual ReprCons *get_repr_cons() = 0; }; -class ListReprCons; +typedef set EvalObjAddrHash; + +class PairReprCons; /** @class Pair * Pair construct, which can be used to represent a list, or further * more, a syntax tree @@ -152,9 +156,10 @@ class RetAddr : public FrameObj { class ReprCons { public: + EvalObj *ori; bool done; string repr; - ReprCons(bool done); + ReprCons(bool done, EvalObj *ori = NULL); virtual EvalObj *next(const string &prev) = 0; }; @@ -164,11 +169,12 @@ class ReprStr : public ReprCons { EvalObj *next(const string &prev); }; -class ListReprCons : public ReprCons { +class PairReprCons : public ReprCons { private: + int state; EvalObj *ptr; public: - ListReprCons(Pair *ptr); + PairReprCons(Pair *ptr, EvalObj *ori); EvalObj *next(const string &prev); }; @@ -178,7 +184,7 @@ class VectReprCons : public ReprCons { VecObj *ptr; int idx; public: - VectReprCons(VecObj *ptr); + VectReprCons(VecObj *ptr, EvalObj *ori); EvalObj *next(const string &prev); }; -- cgit v1.2.3