From 80e885a9847c9bce1be8cccafc85ea39cbc120e2 Mon Sep 17 00:00:00 2001 From: Teddy Date: Fri, 9 Aug 2013 23:50:42 +0800 Subject: numerical overflow detection --- Makefile | 2 +- builtin.cpp | 68 ++++++++++++++++++++++++++++++++++++++++++++++++++++++------- builtin.h | 4 ++++ consts.cpp | 3 ++- consts.h | 3 ++- eval.cpp | 4 ++++ main.cpp | 2 +- 7 files changed, 75 insertions(+), 11 deletions(-) diff --git a/Makefile b/Makefile index eddc4b8..ad43056 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 -g -pg -DGMP_SUPPORT -Wall -Wextra -Wconversion + g++ $< -c -g -pg -DGMP_SUPPORT -Wall -Wextra clean: rm -f *.o diff --git a/builtin.cpp b/builtin.cpp index 115377c..fbcbd84 100644 --- a/builtin.cpp +++ b/builtin.cpp @@ -15,6 +15,8 @@ static const int NUM_LVL_COMP = 0; static const int NUM_LVL_REAL = 1; static const int NUM_LVL_RAT = 2; static const int NUM_LVL_INT = 3; +const double EPS = 1e-16; +const int PREC = 16; #define ARGS_EXACTLY_TWO \ if (args == empty_list || \ @@ -35,7 +37,7 @@ static const int NUM_LVL_INT = 3; string double_to_str(double val, bool force_sign = false) { stringstream ss; if (force_sign) ss << std::showpos; - ss << std::setprecision(16); + ss << std::setprecision(PREC); ss << val; return ss.str(); } @@ -79,6 +81,9 @@ int gcd(int a, int b) { return abs(a); } +bool is_zero(double x) { + return -EPS < x && x < EPS; +} InexactNumObj::InexactNumObj(NumLvl level) : NumObj(level, false) {} @@ -200,7 +205,10 @@ NumObj *CompNumObj::mul(NumObj *_r) { NumObj *CompNumObj::div(NumObj *_r) { CompNumObj *r = static_cast(_r); - double f = 1.0 / (C * C + D * D); + double f = C * C + D * D; + if (f == 0) + throw NormalError(RUN_ERR_NUMERIC_OVERFLOW); + f = 1 / f; return new CompNumObj((A * C + B * D) * f, (B * C - A * D) * f); } @@ -300,6 +308,8 @@ ExactNumObj::ExactNumObj(NumLvl level) : NumObj(level, true) {} #ifndef GMP_SUPPORT RatNumObj::RatNumObj(int _a, int _b) : ExactNumObj(NUM_LVL_RAT), a(_a), b(_b) { + if (b == 0) + throw NormalError(RUN_ERR_NUMERIC_OVERFLOW); int g = gcd(a, b); a /= g; b /= g; @@ -329,6 +339,8 @@ RatNumObj *RatNumObj::from_string(string repr) { try { mpq_class ret(repr, 10); + if (ret.get_den() == 0) + throw NormalError(RUN_ERR_NUMERIC_OVERFLOW); ret.canonicalize(); return new RatNumObj(ret); } @@ -505,8 +517,9 @@ NumObj *IntNumObj::div(NumObj *_r) { #ifndef GMP_SUPPORT return new RatNumObj(val, static_cast(_r)->val); #else - return new RatNumObj(mpq_class(val, - static_cast(_r)->val)); + mpz_class d(static_cast(_r)->val); + if (d == 0) throw NormalError(RUN_ERR_NUMERIC_OVERFLOW); + return new RatNumObj(mpq_class(val, d)); #endif } @@ -940,7 +953,7 @@ BUILTIN_PROC_DEF(make_list) { } BUILTIN_PROC_DEF(num_add) { - ARGS_AT_LEAST_ONE; +// ARGS_AT_LEAST_ONE; NumObj *res = new IntNumObj(0), *opr; // the most accurate type for (;args != empty_list; args = TO_PAIR(args->cdr)) { @@ -964,6 +977,12 @@ BUILTIN_PROC_DEF(num_sub) { NumObj *res = static_cast(args->car), *opr; args = TO_PAIR(args->cdr); + if (args == empty_list) + { + IntNumObj _zero(0); + NumObj *zero = res->convert(&_zero); + return zero->sub(res); + } for (; args != empty_list; args = TO_PAIR(args->cdr)) { if (!args->car->is_num_obj()) // not a number @@ -982,7 +1001,7 @@ BUILTIN_PROC_DEF(num_sub) { BUILTIN_PROC_DEF(num_mul) { - ARGS_AT_LEAST_ONE; +// ARGS_AT_LEAST_ONE; NumObj *res = new IntNumObj(1), *opr; // the most accurate type for (;args != empty_list; args = TO_PAIR(args->cdr)) { @@ -1003,9 +1022,14 @@ BUILTIN_PROC_DEF(num_div) { ARGS_AT_LEAST_ONE; if (!args->car->is_num_obj()) throw TokenError("a number", RUN_ERR_WRONG_TYPE); - NumObj *res = static_cast(args->car), *opr; args = TO_PAIR(args->cdr); + if (args == empty_list) + { + IntNumObj _one(1); + NumObj *one = res->convert(&_one); + return one->div(res); + } for (; args != empty_list; args = TO_PAIR(args->cdr)) { if (!args->car->is_num_obj()) // not a number @@ -1428,6 +1452,36 @@ BUILTIN_PROC_DEF(is_number) { return new BoolObj(args->car->is_num_obj()); } +BUILTIN_PROC_DEF(is_complex) { + ARGS_EXACTLY_ONE; + return new BoolObj(args->car->is_num_obj()); + // any numbers are complex +} + + +BUILTIN_PROC_DEF(is_real) { + ARGS_EXACTLY_ONE; + if (!args->car->is_num_obj()) + return new BoolObj(false); + NumObj *obj = static_cast(args->car); + if (obj->level >= NUM_LVL_REAL) + return new BoolObj(true); + return new BoolObj(is_zero(static_cast(obj)->imag)); +} + +BUILTIN_PROC_DEF(is_rational) { + ARGS_EXACTLY_ONE; + return new BoolObj(args->car->is_num_obj() && + static_cast(args->car)->level >= NUM_LVL_RAT); +} + +BUILTIN_PROC_DEF(is_integer) { + ARGS_EXACTLY_ONE; + return new BoolObj(args->car->is_num_obj() && + static_cast(args->car)->level >= NUM_LVL_INT); +} + + BUILTIN_PROC_DEF(display) { ARGS_EXACTLY_ONE; printf("%s\n", args->car->ext_repr().c_str()); diff --git a/builtin.h b/builtin.h index 7b2c6d1..d7721a8 100644 --- a/builtin.h +++ b/builtin.h @@ -263,6 +263,10 @@ BUILTIN_PROC_DEF(num_eq); BUILTIN_PROC_DEF(num_is_exact); BUILTIN_PROC_DEF(num_is_inexact); BUILTIN_PROC_DEF(is_number); +BUILTIN_PROC_DEF(is_complex); +BUILTIN_PROC_DEF(is_real); +BUILTIN_PROC_DEF(is_rational); +BUILTIN_PROC_DEF(is_integer); BUILTIN_PROC_DEF(bool_not); BUILTIN_PROC_DEF(is_boolean); diff --git a/consts.cpp b/consts.cpp index d0c767c..04705ed 100644 --- a/consts.cpp +++ b/consts.cpp @@ -17,5 +17,6 @@ const char *ERR_MSG[] = { "Improper vector structure", "Bad formal %s in expression", "Queue overflowed: the expected expansion is too long!", - "%s stack overflowed!" + "%s stack overflowed!", + "Numeric overflow!" }; diff --git a/consts.h b/consts.h index 4a7c900..7e5de8d 100644 --- a/consts.h +++ b/consts.h @@ -18,7 +18,8 @@ enum ErrCode { PAR_ERR_IMPROPER_VECT, SYN_ERR_BAD_FORMAL, RUN_ERR_QUEUE_OVERFLOW, - RUN_ERR_STACK_OVERFLOW + RUN_ERR_STACK_OVERFLOW, + RUN_ERR_NUMERIC_OVERFLOW }; extern const char *ERR_MSG[]; diff --git a/eval.cpp b/eval.cpp index 323c4c9..369a150 100644 --- a/eval.cpp +++ b/eval.cpp @@ -35,6 +35,10 @@ void Evaluator::add_builtin_routines() { ADD_BUILTIN_PROC("exact?", num_is_exact); ADD_BUILTIN_PROC("inexact?", num_is_inexact); ADD_BUILTIN_PROC("number?", is_number); + ADD_BUILTIN_PROC("complex?", is_complex); + ADD_BUILTIN_PROC("real?", is_real); + ADD_BUILTIN_PROC("rational?", is_rational); + ADD_BUILTIN_PROC("integer?", is_integer); ADD_BUILTIN_PROC("not", bool_not); ADD_BUILTIN_PROC("boolean?", is_boolean); diff --git a/main.cpp b/main.cpp index f9c09ae..221941d 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(); -- cgit v1.2.3-70-g09d2