Files F2731341

No OneTemporary
Actions

File Metadata

Created
Sat, Mar 14, 4:38 AM

View Options

diff --git a/core/containers.lp b/core/containers.lp
index 8a46e89..aa8e996 100644
--- a/core/containers.lp
+++ b/core/containers.lp
@@ -1,41 +1,40 @@
%1. Domain definitions:
impl(solid; on_the_fly; linked_list).
op(seqaccess; randaccess).
relation(recommends; satisfied; unsupported).
relation_score(satisfied, 0).
relation_score(recommends, 1).
score(0..1).
%2. Domain facts:
relation_op(seqaccess, on_the_fly, recommends).
relation_op(randaccess, solid, recommends).
relation_op(randaccess, on_the_fly, unsupported).
bind(X, impl(solid)):- bind(X, dfa_operator(list)).
bind(X, impl(on_the_fly)):- bind(X, dfa_operator(list)).
- bind(X, op(seqaccess)) :- bind(X, dfa_operator(loop_fold)).
- bind(X, op(randaccess)) :- bind(X, dfa_operator(index)).
+ bind(X, l0_op(seqaccess)) :- bind(X, dfa_operator(loop_fold)).
+ bind(X, l0_op0(randaccess)) :- bind(X, dfa_operator(index)).
%5. Manual input
%2. Supplies
%4. Best implemetation search:
score(op(OP), IMPL, SCORE):- SCORE = #sum{SCORE1, SCORE1: relation_score(RL, SCORE1), relation_op(OP, IMPL, RL)}; op(OP); impl(IMPL); not relation_op(OP, IMPL, unsupported).
{score(v(VAR), IMPL, SCORE)}:- score(op(OP), IMPL, SCORE); bind(VAR, op(OP)); bind(VAR, impl(IMPL)).
:- 2{score(v(VAR), IMPL, SCORE): v(VAR)}.
#maximize { SCORE, (VAR, SCORE): score(v(VAR), _, SCORE) }.
%5. Output
- %resolution(var, impl)
+ bind_decision(VAR, SUBJECT, RESOLUTION) :- SUBJECT=implementation; RESOLUTION=IMPL; score(v(VAR), IMPL, _).
-
%1. DFA input
v(a).
bind(a, dfa_operator(list)).
bind(a, dfa_operator(loop_fold)).
diff --git a/cpp/src/clasplayer.cpp b/cpp/src/clasplayer.cpp
index 76509c6..59eb970 100644
--- a/cpp/src/clasplayer.cpp
+++ b/cpp/src/clasplayer.cpp
@@ -1,279 +1,311 @@
#include "clasplayer.h"
#include <iostream>
#include "utils.h"
#include <boost/format.hpp>
#include <boost/algorithm/string/join.hpp>
#include <gringo/scripts.hh>
#include "analysis/aux.h"
#include "analysis/DominatorsTreeAnalysisProvider.h"
#include "analysis/cfagraph.h"
#include "analysis/dfagraph.h"
using namespace std;
//TODO escape identifiers started from upper case symbol
namespace xreate {
void
ClaspLayer::printWarnings(std::ostream& out)
{
const std::string warningTag = "warning";
auto warningsRange = __model.equal_range(warningTag);
for (auto warning=warningsRange.first; warning!= warningsRange.second; ++warning) {
unsigned int warningId;
Gringo::Symbol params;
std::tie(warningId, params) = parse<unsigned int, Gringo::Symbol>(warning->second);
cout << "Warning: " << __warnings.at(warningId) << " ";
params.print(out);
out<<params;
}
}
bool
ClaspLayer::handleSolution(Gringo::Model const &model) {
std::list<std::string> warnings;
cout << "Model: " << endl;
const string& atomBindVar = Config::get("clasp.bindings.variable");
const string& atomBindFunc = Config::get("clasp.bindings.function");
const string& atomBindScope = Config::get("clasp.bindings.scope");
for (Gringo::Symbol atom : model.atoms(clingo_show_type_atoms)) {
atom.print(cout);
cout <<" | "<< endl;
string atomName(atom.name().c_str());
if (atomName == atomBindVar || atomName == atomBindFunc || atomName == atomBindScope){
string name = std::get<1>(parse<Gringo::Symbol, Gringo::Symbol>(atom)).name().c_str();
__model.emplace(move(name), move(atom));
}
__model.emplace(atomName, move(atom));
}
return true;
}
void
ClaspLayer::setCFAData(xreate::analysis::CFAGraph* graph) {
dataCFA.reset(graph);
}
void
ClaspLayer::setDFAData(xreate::analysis::DFAGraph* graph){
dataDFA.reset(graph);
}
void
ClaspLayer::addRuleWarning(const RuleWarning &rule) {
//__partGeneral << rule << endl;
list<string> domains;
boost::format formatDef("%1%(%2%)");
std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(domains, domains.begin()),
[&formatDef](const std::pair<std::string, DomainAnnotation> &argument) {
string domain;
switch (argument.second) {
case DomainAnnotation::FUNCTION:
domain = "function";
break;
case DomainAnnotation::VARIABLE:
domain = "variable";
break;
}
return boost::str(formatDef % domain % argument.first);
});
list<string> vars;
std::transform(rule.__args.begin(), rule.__args.end(), std::inserter(vars, vars.begin()),
[](const std::pair<std::string, DomainAnnotation> &argument) {
return argument.first.c_str();
});
list<list<string>> guardsRaw;
std::transform(rule.__guards.begin(), rule.__guards.end(), std::inserter(guardsRaw, guardsRaw.begin()),
[this](const Expression &guard) {
return xreate::analysis::compile(guard);
});
const list<string>& guards = xreate::analysis::multiplyLists(std::move(guardsRaw));
list<string> &&branches = xreate::analysis::compileNeg(rule.__condition);
boost::format formatWarning("warning(%1%, (%2%)):- %3%, %4%, %5%.");
for (const string &guardsJoined: guards)
for (const string &branch: branches) {
unsigned int hook = registerWarning(string(rule.__message));
__partGeneral << formatWarning
%(hook)
%(boost::algorithm::join(vars, ", "))
%(branch)
%(guardsJoined)
%(boost::algorithm::join(domains, ", "))
<<endl;
}
}
unsigned int
ClaspLayer::registerWarning(std::string &&message) {
static int warningId = 0;
__warnings.emplace(warningId, message);
return warningId++;;
}
void
ClaspLayer::involveImports() {
ostream &out = __partGeneral;
for (string fn: ast->__rawImports)
{
std::ifstream file(fn);
if (!file) continue;
while(!file.eof()){
string line;
std::getline(file, line);
out << line << endl;
}
}
}
void
ClaspLayer::addRawScript(std::string&& script){
__partGeneral << script;
}
void
ClaspLayer::run() {
involveImports();
if (this->dataDFA){
this->dataDFA->print(__partGeneral);
}
if (this->dataCFA){
this->dataCFA->print(__partGeneral);
}
DominatorsTreeAnalysisProvider providerDominators;
providerDominators.run(this);
providerDominators.print(__partGeneral);
ostringstream program;
program << __partTags.str() << __partGeneral.str();
cout << FYEL(program.str()) << endl;
std::vector<char const *> args{"clingo", nullptr};
DefaultGringoModule moduleDefault;
Gringo::Scripts scriptsDefault(moduleDefault);
ClingoLib ctl(scriptsDefault, 0, args.data(), {}, 0);
ctl.add("base", {}, program.str());
ctl.ground({{"base", {}}}, nullptr);
// solve
Gringo::SolveResult result = ctl.solve([this](Gringo::Model const &model) {
this->handleSolution(model);
return true;
}, {});
if (result.satisfiable() == Gringo::SolveResult::Satisfiable) {
cout << FGRN("SUCCESSFULLY") << endl;
} else {
cout << FRED("UNSUCCESSFULLY") << endl;
}
// invoke all query plugins to process clasp data
for (auto q: __queries)
{
q.second->init(this);
}
}
+ bool
+ ClaspLayer::checkScript(std::string&& script, std::string&& atomCheckSuccess){
+ //init
+
+ std::vector<char const *> args{"clingo", nullptr};
+ DefaultGringoModule moduleDefault;
+ Gringo::Scripts scriptsDefault(moduleDefault);
+ ClingoLib ctl(scriptsDefault, 0, args.data(), {}, 0);
+
+ ctl.add("base", {}, program.str());
+ ctl.ground({{"base", {}}}, nullptr);
+
+ bool flagCheck = false;
+ Gringo::SolveResult result = ctl.solve([this, &flagCheck, const &atomCheckSuccess](Gringo::Model const &model) {
+ for (Gringo::Symbol atom : model.atoms(clingo_show_type_atoms)) {
+
+ string atomName(atom.name().c_str());
+ if (atomName == atomCheckSuccess){
+ flagCheck = true;
+ break;
+ }
+
+ return true;
+ }}, {});
+
+ if (!result.satisfiable()){
+ return false;
+ }
+
+ return flagCheck
+ }
+
ClaspLayer::ClaspLayer() {
}
ClaspLayer::ModelFragment
ClaspLayer::query(const std::string& atom)
{
if (! __model.count(atom)){
return boost::none;
}
return ModelFragment(__model.equal_range(atom));
}
ScopePacked
ClaspLayer::pack(CodeScope* const scope) {
auto pos = __indexScopes.emplace(scope, __indexScopes.size());
if (pos.second)
__registryScopes.push_back(scope);
return pos.first->second;
}
size_t
ClaspLayer::getScopesCount() const{
return __registryScopes.size();
}
SymbolPacked
ClaspLayer::pack(const Symbol& symbol, std::string hintSymbolName)
{
SymbolPacked result;
result.scope = pack(symbol.scope);
result.identifier = symbol.identifier;
__indexSymbolNameHints.emplace(result, hintSymbolName);
return result;
}
Symbol
ClaspLayer::unpack(const SymbolPacked& symbol)
{
return Symbol{symbol.identifier, __registryScopes[symbol.scope]};
};
std::string
ClaspLayer::getHintForPackedSymbol(const SymbolPacked& symbol){
if (!symbol.categoryTransient) {
auto result = __indexSymbolNameHints.find(symbol);
return (result == __indexSymbolNameHints.end())? "" : result->second;
} else {
return "anonym(" + to_string(symbol.identifier) + ")";
}
}
bool operator==(const SymbolPacked& s1, const SymbolPacked& s2)
{
return s1.identifier == s2.identifier && s1.scope == s2.scope;
}
bool operator<(const SymbolPacked& s1, const SymbolPacked& s2)
{
return s1.scope < s2.scope || (s1.scope == s2.scope && s1.identifier < s2.identifier);
}
IQuery*
ClaspLayer::registerQuery(IQuery *query, const QueryId& id) {
return __queries.emplace(id, query).first->second;
}
IQuery*
ClaspLayer::getQuery(const QueryId& id){
assert(__queries.count(id) && "Undefined query");
return __queries.at(id);
}
}
diff --git a/cpp/src/clasplayer.h b/cpp/src/clasplayer.h
index ad8da19..4c9ee84 100644
--- a/cpp/src/clasplayer.h
+++ b/cpp/src/clasplayer.h
@@ -1,227 +1,228 @@
#ifndef CLASPLAYER_H
#define CLASPLAYER_H
#include "ast.h"
#include "contextrule.h"
#include <clingo/clingocontrol.hh>
#include <string>
#include <climits>
#include <boost/bimap.hpp>
#include <boost/bimap/multiset_of.hpp>
#include <boost/optional.hpp>
#include <boost/scoped_ptr.hpp>
#include <list>
namespace xreate {
typedef unsigned int ScopePacked;
struct SymbolPacked {
VID identifier;
ScopePacked scope;
bool categoryTransient = false;
};
bool operator==(const SymbolPacked& s1, const SymbolPacked& s2);
bool operator<(const SymbolPacked& s1, const SymbolPacked& s2);
enum class DFGConnection {
STRONG, WEAK, PROTOTYPE
};
class IAnalysisData {
public:
void print(std::ostringstream& output) const;
virtual ~IAnalysisData(){};
};
class IQuery {
public:
virtual void init(ClaspLayer* clasp) = 0;
virtual ~IQuery() {}
};
enum class QueryId {
ContainersQuery,
ContextQuery,
PtrvalidQuery
};
namespace analysis{
class DFAGraph;
class CFAGraph;
}
class ClaspLayer {
friend class ContextRule;
//PROVIDERS:
public:
boost::scoped_ptr<xreate::analysis::DFAGraph> dataDFA;
void setDFAData(xreate::analysis::DFAGraph* graph);
boost::scoped_ptr<xreate::analysis::CFAGraph> dataCFA;
void setCFAData(xreate::analysis::CFAGraph* graph);
void addRawScript(std::string&& script);
private:
void involveImports();
//QUERIES
public:
IQuery* registerQuery(IQuery* query, const QueryId& id);
IQuery* getQuery(const QueryId& id);
template<class ...Types>
static std::tuple<Types...> parse(const Gringo::Symbol& atom);
typedef std::multimap<std::string, Gringo::Symbol>::const_iterator ModelIterator;
typedef boost::optional<std::pair<ClaspLayer::ModelIterator, ClaspLayer::ModelIterator>> ModelFragment;
ModelFragment query(const std::string& atom);
size_t getScopesCount() const;
SymbolPacked pack(const Symbol& symbol, std::string hintSymbolName = "");
ScopePacked pack(CodeScope * const scope);
Symbol unpack(const SymbolPacked& symbol);
std::string getHintForPackedSymbol(const SymbolPacked& symbol);
private:
std::map<QueryId, IQuery*> __queries;
std::multimap<std::string, Gringo::Symbol> __model;
std::map<SymbolPacked, std::string> __indexSymbolNameHints;
std::unordered_map<const CodeScope*, unsigned int> __indexScopes;
std::vector<CodeScope*> __registryScopes;
//WARNINGS
//TODO move to separate provider/query
public:
void addRuleWarning(const RuleWarning &rule);
unsigned int registerWarning(std::string &&message);
private:
std::map<unsigned int, std::string> __warnings;
void printWarnings(std::ostream& out);
//DEFAULT
public:
AST *ast;
ClaspLayer();
void run();
+ bool checkScript(std::string&& script, std::string&& atomCheckSuccess);
private:
std::ostringstream __partTags;
std::ostringstream __partGeneral;
bool handleSolution(Gringo::Model const &model);
};
template<class typ>
struct ParseImplAtom {
static typ get(const Gringo::Symbol& atom) {
return atom.num();
}
};
template<>
struct ParseImplAtom<std::string> {
static std::string get(const Gringo::Symbol& atom) {
switch (atom.type()) {
case Gringo::SymbolType::Str: return atom.string().c_str();
case Gringo::SymbolType::Fun: return atom.name().c_str();
default: break;
}
assert(false && "Inappropriate symbol type");
}
};
template<>
struct ParseImplAtom<SymbolPacked> {
static SymbolPacked get(const Gringo::Symbol& atom) {
auto result = ClaspLayer::parse<unsigned int, unsigned int>(atom);
return SymbolPacked{std::get<0>(result), std::get<1>(result)};
}
};
template<>
struct ParseImplAtom<Gringo::Symbol> {
static Gringo::Symbol get(const Gringo::Symbol& atom) {
return atom;
}
};
template<>
struct ParseImplAtom<Expression> {
static Expression get(const Gringo::Symbol& atom) {
switch (atom.type()) {
case Gringo::SymbolType::Num: return Expression(atom.num());
case Gringo::SymbolType::Str: return Expression(std::string(atom.string().c_str()));
case Gringo::SymbolType::Fun:
{
//ID
if (!atom.args().size){
return Expression(std::string(atom.name().c_str()));
}
//FUNC
Expression result(Operator::CALL,{Expression(std::string(atom.name().c_str()))});
for (const Gringo::Symbol& arg : atom.args()) {
result.addArg(ParseImplAtom<Expression>::get(arg));
}
return result;
}
default:
{
assert(false);
}
}
}
};
template<class Tuple, size_t index>
struct Parse_Impl {
static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) {
const size_t tupleSize = std::tuple_size<Tuple>::value;
typedef typename std::tuple_element < tupleSize - index, Tuple>::type ElType;
ElType& el = std::get < tupleSize - index > (tup);
Gringo::Symbol atom = *arg;
el = ParseImplAtom<ElType>::get(atom);
Parse_Impl<Tuple, index - 1 > ::parse(tup, ++arg);
}
};
template<class Tuple>
struct Parse_Impl<Tuple, 0> {
static void parse(Tuple& tup, Gringo::SymSpan::iterator arg) {
}
};
template<class ...Types>
std::tuple<Types...>
ClaspLayer::parse(const Gringo::Symbol& atom) {
typedef std::tuple < Types...> Tuple;
Tuple tup;
Parse_Impl<Tuple, std::tuple_size<Tuple>::value>::parse(tup, atom.args().first);
return tup;
}
}
#endif
diff --git a/cpp/tests/containers.cpp b/cpp/tests/containers.cpp
index 9d044d5..d5cdf0e 100644
--- a/cpp/tests/containers.cpp
+++ b/cpp/tests/containers.cpp
@@ -1,96 +1,124 @@
/*
* containers.cpp
*
* Created on: Jun 9, 2015
* Author: pgess
*/
#include "passmanager.h"
#include "query/containers.h"
#include "Parser.h"
#include "gtest/gtest.h"
using namespace std;
using namespace xreate;
using namespace containers;
TEST(Containers, ListAsArray){
PassManager* man = PassManager::prepareForCode(
R"Code(
main = function(x:: int):: int;entry {
a = [1, 2, 3]:: [int].
a[x]
}
)Code" );
void* mainPtr = man->run();
int (*main)(int) = (int (*)(int))mainPtr;
ASSERT_EQ(2, main(1));
delete man;
}
TEST(Containers, ListAsArray2){
PassManager* man = PassManager::prepareForCode(
R"Code(
main = function:: int;entry {
a= [1, 2, 3]:: [int].
b= loop map(a->el:: int):: [int]{
2 * el
}.
sum = loop fold(b->el:: int, 0->acc):: int {
acc + el
}.
sum
}
)Code" );
void* mainPtr = man->run();
int (*main)() = (int (*)())mainPtr;
ASSERT_EQ(0, main());
delete man;
}
+
+
+//TEST(){
+// function test1(i:: num):: num{
+// a = [1..10]:: [num].
+//
+// b = loop map(a->el:: num):: [num]{
+// a * a
+// }
+//
+// b[i]
+// }
+//
+// function test2(){
+// a= [1..10]:: [num].
+//
+// b = loop map(a->el:: num):: [num]{
+// a * a
+// }
+//
+// c = loop fold(b->el, 0->sum>)::num {
+// sum + el
+// }
+//
+// c
+// }
+//}
+
TEST(Containers, ContanierLinkedList1){
FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r");
assert(input != nullptr);
Scanner scanner(input);
Parser parser(&scanner);
parser.Parse();
AST& ast = parser.root;
CodeScope* body = ast.findFunction("test")->getEntryScope();
Symbol symb_chilrenRaw = body->findSymbol("childrenRaw");
containers::ImplementationLinkedList iLL(symb_chilrenRaw);
ASSERT_EQ(true, static_cast<bool>(iLL));
ASSERT_EQ("next", iLL.fieldPointer);
Implementation impl = Implementation::create(symb_chilrenRaw);
ASSERT_NO_FATAL_FAILURE(impl.extract<ON_THE_FLY>());
ImplementationRec<ON_THE_FLY> recOnthefly = impl.extract<ON_THE_FLY>();
ASSERT_EQ(symb_chilrenRaw, recOnthefly.source);
}
TEST(Containers, Implementation_LinkedListFull){
FILE* input = fopen("scripts/testspass/Containers_Implementation_LinkedList1.xreate","r");
assert(input != nullptr);
std::unique_ptr<PassManager> program(PassManager::prepareForCode(input));
void* mainPtr = program->run();
int (*main)() = (int (*)())(intptr_t)mainPtr;
int answer = main();
ASSERT_EQ(17, answer);
fclose(input);
}
diff --git a/documentation/Concepts/containers.remarkup b/documentation/Concepts/containers.remarkup
index 3e1602d..850f276 100644
--- a/documentation/Concepts/containers.remarkup
+++ b/documentation/Concepts/containers.remarkup
@@ -1,29 +1,62 @@
==Introduction==
A //Containers// is a general name for data structures intended to hold group of elements of certain type.
Considering that almost every program needs containers to store, retrieve, search or otherwise process aggregate data,
obviously efficiency of containers implementation is one of the top priorities for Xreate design.
-Main idea behind containers in Xreate is to gather information on //how containers are used//, inferred from program sources.
-On this ground it's possible to choose semi-automatically most appropriate data structure for container implementation to efficiently fullfil particular needs.
+Main idea behind containers in Xreate is to gather information on //how containers are used//, by inferring from program sources.
+On this ground it's possible to choose semi-automatically the most appropriate data structure for container implementation to efficiently fullfil particular needs.
a= [1, 2, 3, 4, 5]:: [num]; impl(solid). //container definition
b= a[0]:: num; op(randaccess). //operation on container
In this example, definition of container(variable `a`) offers one or several implementations it supports, that is `impl(solid)` which
is explicilty provided for clarity. On the other side, //retrieving by index// operation(variable `b`) demands certain implementations
-to operate. Annotation `op(randaccess)` explicitly describes operation nature, i.e. it requires any data structure that supports //random access// .
-Based on gathered information, most appropriate tradeoff //in supply and demand// is applied as given container implementation, i.e. `impl(solid)` in this simple case.
+to operate on. Annotation `op(randaccess)` explicitly describes operation nature, i.e. it requires any data structure that supports //random access// .
+
+Based on gathered information, most appropriate tradeoff //in supply and demand// is assumed as implementation for a given container , i.e. `impl(solid)` in the case above.
+
+Here is a more complex example:
+
+ function test1(i:: num):: num{
+ a = [1..10]:: [num].
+
+ b = loop map(a->el:: num):: [num]{
+ a * a
+ }
+
+ b[i]
+ }
+
+Implementation of `b` assumed to be `impl(soild)` for index operation `b[i]` demands `randaccess` and `impl(solid)` is a most appropriate implementation operator `list` could provide(variable `a`). However, after slight changes as shown below
+
+ function test2:: num {
+ a= [1..10]:: [num].
+
+ b = loop map(a->el:: num):: [num]{
+ a * a
+ }
+
+ c = loop fold(b->el, 0->sum>)::num {
+ sum + el
+ }
+
+ c
+ }
+
+the situation is different. Definitions of `a` as well as `b` are intact, but there is different operaton over `b`, which is iterating to calculate sum of `b` elements. Iteration represented as `op(seqaccess)` depicting //sequental access// to a container data. Different container use leads implementation inference to a different outcomes, `impl(on_the_fly)` in this case.
+
+To conclude, the examples show ability to automatically reassign best suited implementations for a container variables reflecting how exactly variables are processed.
In order to exppress possible and required implementations, describe operations, constraints and preferences an annotations are used, either manually provided or automatically inferred from program sources.
==Container definitions==
==Container operations==
| `map` loop | `op(seqaccess)` | `impl(on_the_fly)`, `impl(solid)`
| `fold` loop | `op(seqaccess)`| `impl(on_the_fly)`, `impl(solid)`
| index retrieving | `op(randaccess` | `impl(solid)`
\ No newline at end of file

Event Timeline

Email: pr.h7@xreate.org · 2019 Xreate.org · Powered by Phabricator