Commits

O01eg committed ff9193c

GP: Add type optimization.

Comments (0)

Files changed (9)

    - Add scripting for individual testing and comparsion.
    - Support for galapagos (https://github.com/brunoro/galapagos) visualisation tool.
 
+Now
+ * GP
+  - Add type optimization.
+
 Version 0.0.5 2012-09-05
  - Support for C++0x (GCC 4.5.3)
  - Add optimization of programs.
 {
 	m_Funcs.push_back(std::make_pair(m_Env.GetIF(), 3));
 	m_Funcs.push_back(std::make_pair(m_Env.GetEVAL(), 1));
-	VM::Environment::Func* array = func_array;
+	FuncData* array = func_array;
 	while(array->func)
 	{
 		size_t index = m_Env.LoadFunction(array->name, array->number_param, array->func);
-		m_Funcs.push_back(std::make_pair(VM::Object(m_Env, VM::FUNC, index), array->number_param));
+		VM::Object f = VM::Object(m_Env, VM::FUNC, index);
+		m_Funcs.push_back(std::make_pair(f, array->number_param));
+		// load optimize rules
+		m_OptimizeRules.mode.insert({f, array->mode});
+		m_OptimizeRules.returnERRORat.insert({f, array->returnERRORat});
+		if(array->return0atBOOL)
+		{
+			m_OptimizeRules.return0atBOOL.insert(f);
+		}
+
 		++ array;
 	}
 
 
 Individual GA::GenerateRand() const
 {
-	VM::Program prog = GP::GenerateProg(m_Env, m_Funcs);
+	VM::Program prog = GP::GenerateProg(m_Env, m_Funcs, m_OptimizeRules);
 	return Individual(prog, {});
 }
 
 Individual GA::Mutation(const Individual& ind) const
 {
-	return Individual(GP::MutateProg(ind.GetProgram(), m_Funcs), ind.GetParents());
+	return Individual(GP::MutateProg(ind.GetProgram(), m_Funcs, m_OptimizeRules), ind.GetParents());
 }
 
 Individual GA::Crossover(const Individual& ind1, const Individual& ind2) const
 {
-	return Individual(GP::CrossoverProg(ind1.GetProgram(), ind2.GetProgram()), {ind1, ind2});
+	return Individual(GP::CrossoverProg(ind1.GetProgram(), ind2.GetProgram(), m_OptimizeRules), {ind1, ind2});
 }
 
 bool GA::Load(const char* filename, Individual *ind) const
 		VM::Program prog(obj);
 		for(int adf_index = MAX_FUNCTIONS; adf_index >= 0; -- adf_index)
 		{
-			prog.SetADF(adf_index, GP::Optimize(prog.GetADF(adf_index), prog));
+			prog.SetADF(adf_index, GP::Optimize(prog.GetADF(adf_index), prog, m_OptimizeRules));
 		}
 		prog.Minimize();
 		(*ind) = Individual(std::move(prog), {});
 #include <algorithm>
 #include <memory>
 #include "individual.h"
+#include "ga_utils.h"
 
 /// \class GA
 /// \brief Genetic Algoritms.
 	size_t m_PopulationSize; ///< Size of population.
 	Population m_Population; ///< Auto pointer to population.
 	std::vector<std::pair<VM::Object, size_t> > m_Funcs; ///< Functions for GA.
+	GP::OptimizeRules m_OptimizeRules;
 };
 
 #endif
 #include "ga_utils.h"
 #include "vm/program.h"
 #include "conf.h"
+//#include "vm/ioobject.h"
 
 const size_t MAX_DEPTH = Config::Instance().GetSLong("max-object-depth", 8);
 const size_t MAX_OPT_LOOPS = Config::Instance().GetSLong("max-opt-loops", 512);
 	return res;
 }
 
-VM::Object GP::Optimize(const VM::Object& obj, VM::Program& prog)
+VM::Object GP::Optimize(const VM::Object& obj, VM::Program& prog, const OptimizeRules& rules, const OptimizeMode mode)
 {
 	VM::Environment &env = obj.GetEnv();
 	VM::Object res(env);
 				std::stack<VM::Object> stack;
 				while((! t.IsNIL()) && (t.GetType() == VM::LIST))
 				{
-					VM::Object opt = GP::Optimize(t.GetHead(), prog);
+					VM::Object opt(env);
+					if(check_no_if)
+					{
+						std::unordered_map<VM::Object, OptimizeMode>::const_iterator it = rules.returnERRORat.find(head);
+						if((it != rules.returnERRORat.end()) && (mode != OPT_BOOL) && (mode & it->second))
+						{
+							//std::cerr << "Error mode=" << mode << " head=" << head << std::endl;
+							return env.GetERROR();
+						}
+						if((mode == OPT_BOOL) && rules.return0atBOOL.count(head))
+						{
+							return VM::Object(env, VM::INTEGER, 0);
+						}
+
+						// get mode for arguments
+						OptimizeMode mode_arg = OPT_NONE;
+						it = rules.mode.find(head);
+						if(it != rules.mode.end())
+						{
+							mode_arg = it->second;
+						}
+
+						opt = GP::Optimize(t.GetHead(), prog, rules, mode_arg);
+					}
+					else // get IF
+					{
+						if(check_1st)
+						{
+							opt = GP::Optimize(t.GetHead(), prog, rules, OPT_BOOL);
+						}
+						else
+						{
+							// other args must support current mode.
+							opt = GP::Optimize(t.GetHead(), prog, rules, mode);
+						}
+					}
+
 					if(check_no_if || check_1st)
 					{
 						check_1st = false;
 						if((! opt.IsNIL()) && (opt.GetType() == VM::ERROR))
 						{
+							//std::cerr << "Error mode=" << mode << " opt=" << opt << std::endl;
 							return opt;
 						}
 					}
 					t = VM::Object(stack.top(), t);
 					stack.pop();
 				}
+				if(! GP::IsContainParam(t))
+				{
+					return GP::Optimize(VM::Object(head, t), prog, rules, mode);
+				}
 				return VM::Object(head, t);
 			}
 		}
 	}
 	else //if(GP::IsContainParam(obj))
 	{
-		if(obj.IsNIL() || (obj.GetType() != VM::LIST))
-		{
-			// don't optimize atoms.
-			return obj;
-		}
 		size_t circle_count = MAX_OPT_LOOPS;
 		res = env.Eval(obj, &circle_count);
 		if((! res.IsNIL()) && (res.GetType() == VM::ERROR))
 		{
+			//std::cerr << "Error mode=" << mode << " obj=" << obj << std::endl;
 			return res; // return ERROR for wrong code.
 		}
-		else
+		else // get value.
 		{
-			if(res.IsNIL() || (res.GetType() == VM::INTEGER))
+			if(res.IsNIL())
 			{
+				// not allow at OPT_REQ_INT and OPT_REQ_LIST
+				if((mode == GP::OPT_REQ_INT) || (mode == GP::OPT_REQ_LIST))
+				{
+					//std::cerr << "Error mode=" << mode << " obj=" << obj << " res=NIL" << std::endl;
+					return env.GetERROR();
+				}
 				return res;
 			}
-			else
+			else // no-NIL
 			{
-				return VM::Object(env.GetQUOTE(), VM::Object(res, VM::Object(env)));
+				if(mode == GP::OPT_BOOL)
+				{
+					return VM::Object(env, VM::INTEGER, 0);
+				}
+				if((mode == GP::OPT_REQ_LIST) && (res.GetType() != VM::LIST))
+				{
+					//std::cerr << "Error mode=" << mode << " obj=" << obj << " res=" << res << std::endl;
+					return env.GetERROR();
+				}
+				if((mode == GP::OPT_REQ_INT) && (res.GetType() != VM::INTEGER))
+				{
+					//std::cerr << "Error mode=" << mode << " obj=" << obj << " res=" << res << std::endl;
+					return env.GetERROR();
+				}
+
+				if(res.GetType() == VM::INTEGER)
+				{
+					return res;
+				}
+				else
+				{
+					return VM::Object(env.GetQUOTE(), VM::Object(res, VM::Object(env)));
+				}
 			}
 		}
 	}// if(GP::IsContainParam(obj))
 	return res;
 }
 
-VM::Program GP::GenerateProg(VM::Environment &env, const std::vector<std::pair<VM::Object, size_t> >& funcs)
+VM::Program GP::GenerateProg(VM::Environment &env, const std::vector<std::pair<VM::Object, size_t> >& funcs, const OptimizeRules& rules)
 {
 	VM::Program res(env);
 	for(int adf_index = MAX_FUNCTIONS; adf_index >= 0; -- adf_index)
 		}
 		while(! GP::CheckForParam(adf));
 		res.SetADF(adf_index, adf);
-		res.SetADF(adf_index, GP::Optimize(adf, res));
+		res.SetADF(adf_index, GP::Optimize(adf, res, rules));
 	}
 	res.Minimize();
 	return res;
 }
 
-VM::Program GP::MutateProg(const VM::Program &prog, const std::vector<std::pair<VM::Object, size_t> >& funcs)
+VM::Program GP::MutateProg(const VM::Program &prog, const std::vector<std::pair<VM::Object, size_t> >& funcs, const OptimizeRules& rules)
 {
 	VM::Environment& env = prog.GetEnv();
 	VM::Program res(env);
 			adf = new_adf;
 		}
 		res.SetADF(adf_index, adf);
-		res.SetADF(adf_index, GP::Optimize(adf, res));
+		res.SetADF(adf_index, GP::Optimize(adf, res, rules));
 	}
 	res.Minimize();
 	return res;
 }
 
-VM::Program GP::CrossoverProg(const VM::Program &prog1, const VM::Program &prog2)
+VM::Program GP::CrossoverProg(const VM::Program &prog1, const VM::Program &prog2, const OptimizeRules& rules)
 {
 	VM::Environment &env = prog1.GetEnv();
 	if(&env != &prog2.GetEnv())
 			}
 		}
 		res.SetADF(adf_index, adf);
-		res.SetADF(adf_index, GP::Optimize(adf, res));
+		res.SetADF(adf_index, GP::Optimize(adf, res, rules));
 	}
 	res.Minimize();
 	return res;
 #ifndef _GA_UTILS_H_
 #define _GA_UTILS_H_
 
+#include <unordered_set>
+#include <unordered_map>
 #include "vm/object.h"
 
 /// \brief GP-related stuff.
 namespace GP
 {
+	enum OptimizeMode
+	{
+		OPT_NONE = 0,
+		OPT_REQ_LIST = 1,
+		OPT_REQ_INT = 2,
+		OPT_BOOL = 3
+	};
+
+	struct OptimizeRules
+	{
+	public:
+		std::unordered_map<VM::Object, OptimizeMode> mode;
+		std::unordered_map<VM::Object, OptimizeMode> returnERRORat;
+		std::unordered_set<VM::Object> return0atBOOL;
+	};
+
 	/// \brief Count IFs in object exclude quoted.
 	/// \param obj Object.
 	/// \return Count of IFs.
 	/// \brief Reduce all constant parts.
 	/// \param obj Object to reduction.
 	/// \param prog Context of evalation.
+	/// \param[in] mode Mode of optimization.
 	/// \return Optimized object.
-	VM::Object Optimize(const VM::Object& obj, VM::Program& prog);
+	VM::Object Optimize(const VM::Object& obj, VM::Program& prog, const OptimizeRules& rules, const OptimizeMode mode = OPT_NONE);
 
 	/// \brief Generate any object.
 	/// \param env Environment.
 	/// \param env Environment.
 	/// \param funcs Functions for GA.
 	/// \return Generated program.
-	VM::Program GenerateProg(VM::Environment &env, const std::vector<std::pair<VM::Object, size_t> >& funcs);
+	VM::Program GenerateProg(VM::Environment &env, const std::vector<std::pair<VM::Object, size_t> >& funcs, const OptimizeRules& rules);
 
 	/// \brief Mutate program.
 	/// \param prog Program.
 	/// \param funcs Functions for GA.
 	/// \return Generated program.
-	VM::Program MutateProg(const VM::Program &prog, const std::vector<std::pair<VM::Object, size_t> >& funcs);
+	VM::Program MutateProg(const VM::Program &prog, const std::vector<std::pair<VM::Object, size_t> >& funcs, const OptimizeRules& rules);
 
 	/// \brief Crossover programs.
 	/// \param prog1 First program.
 	/// \param prog2 Second program.
 	/// \return Generated program.
-	VM::Program CrossoverProg(const VM::Program &prog1, const VM::Program &prog2);
+	VM::Program CrossoverProg(const VM::Program &prog1, const VM::Program &prog2, const OptimizeRules& rules);
 }
 
 #endif
 	}
 	{
 		VM::Environment env;
-		VM::Environment::Func* array = func_array;
+		FuncData* array = func_array;
 		while(array->func)
 		{
 			env.LoadFunction(array->name, array->number_param, array->func);

src/gpoptimize.cpp

 			return -1;
 		}
 		VM::Environment env;
-		VM::Environment::Func* array = func_array;
+		FuncData* array = func_array;
+		GP::OptimizeRules rules;
 		while(array->func)
 		{
-			env.LoadFunction(array->name, array->number_param, array->func);
+			size_t index = env.LoadFunction(array->name, array->number_param, array->func);
+			VM::Object f = VM::Object(env, VM::FUNC, index);
+			//load optimize rules
+			rules.mode.insert({f, array->mode});
+			rules.returnERRORat.insert({f, array->returnERRORat});
+			if(array->return0atBOOL)
+			{
+				rules.return0atBOOL.insert(f);
+			}
+
 			++ array;
 		}
 
 		for(size_t i = 0; i < prog.GetSize(); ++ i)
 		{
 			VM::Object adf = prog.GetADF(i);
-			VM::Object new_adf = GP::Optimize(adf, prog);
+			VM::Object new_adf = GP::Optimize(adf, prog, rules);
 			prog.SetADF(i, new_adf);
 			std::cout << "Opt %" << i << ": " << adf << " -> " << new_adf << std::endl;
 		}

src/libfunctions/functions.cpp

 
 /// \file functions.cpp
 
-Environment::Func func_array[] =
+FuncData func_array[] =
 {
-	Environment::Func(func_01_cons, "CONS", 2),
-	Environment::Func(func_02_car, "CAR", 1),
-	Environment::Func(func_03_cdr, "CDR", 1),
-	Environment::Func(func_04_is_nil, "NULL?", 1),
-	Environment::Func(func_05_is_int, "INT?", 1),
-	Environment::Func(func_06_is_func, "FUNC?", 1),
-	Environment::Func(func_07_is_adf, "ADF?", 1),
-	Environment::Func(func_08_is_param, "PARAM?", 1),
-	Environment::Func(func_09_is_quote, "QUOTE?", 1),
-	Environment::Func(func_10_is_list, "LIST?", 1),
-	Environment::Func(func_11_int_plus, "+", 2),
-	Environment::Func(func_12_int_minus, "-", 2),
-	Environment::Func(func_13_int_mult, "*", 2),
-	Environment::Func(func_14_int_div, "DIV", 2),
-	Environment::Func(func_15_int_mod, "MOD", 2),
-	Environment::Func(func_16_equal, "EQ", 2),
-	Environment::Func(func_17_and, "AND", 2),
-	Environment::Func(func_18_or, "OR", 2),
-	Environment::Func(func_19_int_less, "<", 2),
-	Environment::Func(func_20_int_greater, ">", 2),
-	Environment::Func(func_21_int_equal, "==", 2),
-	Environment::Func()
+	FuncData(func_01_cons, "CONS", 2, GP::OPT_NONE, GP::OPT_REQ_INT, true),
+	FuncData(func_02_car, "CAR", 1, GP::OPT_REQ_LIST, GP::OPT_NONE, false),
+	FuncData(func_03_cdr, "CDR", 1, GP::OPT_REQ_LIST, GP::OPT_NONE, false),
+	FuncData(func_04_is_nil, "NULL?", 1, GP::OPT_BOOL, GP::OPT_BOOL, false),
+	FuncData(func_05_is_int, "INT?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_06_is_func, "FUNC?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_07_is_adf, "ADF?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_08_is_param, "PARAM?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_09_is_quote, "QUOTE?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_10_is_list, "LIST?", 1, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_11_int_plus, "+", 2, GP::OPT_REQ_INT, GP::OPT_REQ_LIST, true),
+	FuncData(func_12_int_minus, "-", 2, GP::OPT_REQ_INT, GP::OPT_REQ_LIST, true),
+	FuncData(func_13_int_mult, "*", 2, GP::OPT_REQ_INT, GP::OPT_REQ_LIST, true),
+	FuncData(func_14_int_div, "DIV", 2, GP::OPT_REQ_INT, GP::OPT_REQ_LIST, true),
+	FuncData(func_15_int_mod, "MOD", 2, GP::OPT_REQ_INT, GP::OPT_REQ_LIST, true),
+	FuncData(func_16_equal, "EQ", 2, GP::OPT_NONE, GP::OPT_BOOL, false),
+	FuncData(func_17_and, "AND", 2, GP::OPT_BOOL, GP::OPT_BOOL, false),
+	FuncData(func_18_or, "OR", 2, GP::OPT_BOOL, GP::OPT_BOOL, false),
+	FuncData(func_19_int_less, "<", 2, GP::OPT_REQ_INT, GP::OPT_BOOL, false),
+	FuncData(func_20_int_greater, ">", 2, GP::OPT_REQ_INT, GP::OPT_BOOL, false),
+	FuncData(func_21_int_equal, "==", 2, GP::OPT_REQ_INT, GP::OPT_BOOL, false),
+	FuncData()
 };
 
 /// \brief CONS - Construct list.

src/libfunctions/functions.h

 #define _FUNCTIONS_H_
 
 #include "vm/environment.h"
+#include "ga_utils.h"
 
 using namespace VM;
 
 void func_20_int_greater(const std::vector<Object>& args, Object *result);
 void func_21_int_equal(const std::vector<Object>& args, Object *result);
 
-extern Environment::Func func_array[];
+struct FuncData : public Environment::Func
+{
+	FuncData(FunctionPtr func_, const std::string& name_, unsigned char number_param_, GP::OptimizeMode mode_, GP::OptimizeMode returnERRORat_, bool return0atBOOL_)
+		: Environment::Func(func_, name_, number_param_)
+		, mode(mode_)
+		, returnERRORat(returnERRORat_)
+		, return0atBOOL(return0atBOOL_)
+	{
+	}
+	FuncData()
+		: Environment::Func()
+	{
+	}
+	GP::OptimizeMode mode;
+	GP::OptimizeMode returnERRORat;
+	bool return0atBOOL;
+};
+
+extern FuncData func_array[];
 
 #endif