diff --git a/core/containers.lp b/core/containers.lp index a8c53b8..4bda981 100644 --- a/core/containers.lp +++ b/core/containers.lp @@ -1,42 +1,48 @@ %3. Domain definitions: implementation(solid; on_the_fly; linked_list). op(seqaccess; randaccess). relation(recommends; satisfied; unsupported). relation_score(satisfied, 0). relation_score(recommends, 1). score(0..1). %4. Domain facts: relation_op(seqaccess, on_the_fly, recommends). relation_op(randaccess, solid, recommends). relation_op(randaccess, on_the_fly, unsupported). bind(X, variant(l0_implementation(solid; on_the_fly))):- bind(X, dfa_operator(list)). bind(X, variant(implementation(IMPL))):- bind(X, variant(l0_implementation(IMPL))); not bind(X, -variant(implementation(IMPL))). - bind(X, l0_op(seqaccess)) :- bind(X, dfa_operator(loop_fold)). - bind(X, l0_op(randaccess)) :- bind(X, dfa_operator(index)). - bind(X, op(OP)):- bind(X, l0_op(OP)); #count{OP1: bind(X, op(OP1)), OP1 <> OP}=0. + bind(X, op(seqaccess)) :- bind(X, dfa_operator(loop_fold)). + bind(X, op(randaccess)) :- bind(X, dfa_operator(index)). + %bind(X, op(OP)):- bind(X, l0_op(OP)); #count{OP1: bind(X, op(OP1)), OP1 <> OP}=0. -% Transfunction inference - bind(Vactual, op(Op)) :- - bind(Vres, variant(implementation(..))) :- - %5. Best implemetation search: score(op(OP), IMPL, SCORE):- SCORE = #sum{SCORE1, SCORE1: relation_score(RL, SCORE1), relation_op(OP, IMPL, RL)}; op(OP); implementation(IMPL); not relation_op(OP, IMPL, unsupported). score(v(VAR), IMPL, SCORE):- bind(VAR, implementation(IMPL)); score(op(OP), IMPL, SCORE); bind(VAR, op(OP)). #maximize { SCORE, (VAR, SCORE): score(v(VAR), _, SCORE) }. %6. Output - bind(VAR, implementation(IMPL)): bind(VAR, variant(implementation(IMPL))):- bind(VAR, op(OP)). + 1{ bind(VAR, implementation(IMPL)): bind(VAR, variant(implementation(IMPL))), score(op(OP), IMPL, _) }1 :- bind(VAR, op(OP)); 1{bind(VAR, variant(implementation(IMPL)))}. %1. DFA input % bind(X, dfa_operator(...) %2. Manual input % bind(V, variant(implementation(...))). -- add variant % bind(V, -variant(implementation(...))). -- remove variant % bind(V, op(..)). --set op demand % bind(V, implementation(..)). --set decision + +% Transfunction inference + +%a) output only: + bind(Vactual, implementation(ImplRet)) :- bind(VarRet, implementation(ImplRet)); dfa_fnret(VarRet, Fn); bind(Vactual, dfa_operator(call, (Fn))). + bind(VarRet, op(OpActual)) :- bind(VarActual, op(OpActual)); dfa_fnret(VarRet, Fn); bind(VarActual, dfa_operator(call, (Fn))). + +%b) input only: + bind(Vactual, op(OpFormal)) :- dfa_arglist(Vformal, Vactual, _); bind(Vformal, op(OpFormal)). + bind(Vformal, implementation(ImplActual)) :- bind(Vactual, implementation(ImplActual)); dfa_arglist(Vformal, Vactual, _). diff --git a/cpp/tests/containers.cpp b/cpp/tests/containers.cpp index ab41c1c..2f5a6f8 100644 --- a/cpp/tests/containers.cpp +++ b/cpp/tests/containers.cpp @@ -1,219 +1,237 @@ /* * containers.cpp * * Created on: Jun 9, 2015 * Author: pgess */ #include "passmanager.h" #include "query/containers.h" #include "analysis/dfagraph.h" #include "analysis/cfagraph.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(Containers, InferenceManualControlSupply_add){ string program = R"SCRIPT( #include "core/containers.lp". %1. DFA input v(a). bind(a, dfa_operator(loop_fold)). %2. Manual input bind(a, variant(implementation(on_the_fly))). success :- bind(a, implementation(on_the_fly)). )SCRIPT"; ClaspLayer* solver = new ClaspLayer(); ASSERT_TRUE(solver->checkScript(move(program), "success")); delete solver; } TEST(Containers, InferenceManualControlSupply_delete){ string program = R"SCRIPT( #include "core/containers.lp". %1. DFA input v(a). bind(a, dfa_operator(loop_fold)). bind(a, dfa_operator(list)). %2. Manual input bind(a, -variant(implementation(on_the_fly))). success :- bind(a, implementation(solid)). )SCRIPT"; ClaspLayer* solver = new ClaspLayer(); ASSERT_TRUE(solver->checkScript(move(program), "success")); delete solver; } TEST(Containers, InferenceManualControlDemand_set){ string program = R"SCRIPT( #include "core/containers.lp". %1. DFA input v(a). bind(a, dfa_operator(loop_fold)). bind(a, dfa_operator(list)). %2. Manual input bind(a, op(randaccess)). success :- bind(a, implementation(solid)). )SCRIPT"; ClaspLayer* solver = new ClaspLayer(); ASSERT_TRUE(solver->checkScript(move(program), "success")); delete solver; } TEST(Containers, InferenceManualControlImpl_set){ string program = R"SCRIPT( #include "core/containers.lp". %1. DFA input v(a). bind(a, dfa_operator(loop_fold)). bind(a, dfa_operator(list)). %2. Manual input bind(a, implementation(solid)). success :- bind(a, implementation(solid)). )SCRIPT"; ClaspLayer* solver = new ClaspLayer(); ASSERT_TRUE(solver->checkScript(move(program), "success")); delete solver; } +TEST(Containers, Negative){ +R"SCRIPT( + #include "core/containers.lp" + + v(a; b; c). + + bind(a, dfa_operator(list)). + bind(a, dfa_operator(loop_fold)). + bind(b, dfa_operator(list)). + bind(b, dfa_operator(index)). + + bind(c, dfa_operator(loop_fold)). + + dfa_arglist(c, a, 1). + dfa_arglist(c, b, 2). +)SCRIPT"; +} + //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(iLL)); ASSERT_EQ("next", iLL.fieldPointer); Implementation impl = Implementation::create(symb_chilrenRaw); ASSERT_NO_FATAL_FAILURE(impl.extract()); ImplementationRec recOnthefly = impl.extract(); 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 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/Articles/gestalts.remarkup b/documentation/Articles/gestalts.remarkup index 449df72..24e2914 100644 --- a/documentation/Articles/gestalts.remarkup +++ b/documentation/Articles/gestalts.remarkup @@ -1,22 +1,27 @@ ==Computational gestalts== There are number of commonly accepted concepts that are redefined or reevaluated in Xreate. -* Interface is comprised of common subset of features supported by all concrete implementations. +* Interface as subset. Interface is comprised of common subset of features supported by all concrete implementations. See [[concepts/containers]] -* Top-down annotations(like function, objects annotations) are exposed to and could be intospected by client code or caller. - Most usefull is exposing of caller annotations to a callee code or bottom-up annotations. +* Top-down annotations(like function, objects annotations) are exposed to and could be intospected by client code or caller. Most usefull is exposing of caller annotations to a callee code or bottom-up annotations. -* Lazy/eager execution atnagonism. +* Lazy/eager execution antagonism. It's possible to determine which sites of using resource should treat it as lazy resource or eager otherwise. See [[concepts/exploitation]] for details. * Static/dynamic antagonism +* Rapid development and optimization antagonism +from Concepts/containers, "Rapid development and optimization antagonism" * High-level feast or famine ===Static/dynamic antagonism=== +Abstractions - hide implementation details. + +Inclusive development. + ===Polymorphism=== Either instantiations or indirect calls \ No newline at end of file diff --git a/documentation/Aspects/highlevel.remarkup b/documentation/Aspects/highlevel.remarkup index f724e71..44f9e48 100644 --- a/documentation/Aspects/highlevel.remarkup +++ b/documentation/Aspects/highlevel.remarkup @@ -1,5 +1,27 @@ High-level: +ability to quiclky adjust and apply software to a different tasks +To begin with, in Xreate we treat defininiton of "high-level" as practical term, meaning ability +to adapt, alter, adjust component or whole program to comply with new changed requirements or environment in general. +The more "high-level" techniques language provides, the less efforts need to be done for such transformation, given all else things being equal. + +TODO To reduce high-level or abstraction penalty .... *Focus on current task *Program Addtitivity -*Reduce refactoring needs \ No newline at end of file +*Reduce refactoring needs + +*Inlcusive development - adapting heterogenous components to seamlessly work with each other w/o connection costs. +Software product usually consists of unrelated components written by different teams at different time with different goals in mind. Components doesn't know how are they used .... +(concepts/containers) + +autooptimization in future when new impls are available +(concepts/containers) + +**Regression resistance** for containers, etc. +from Concepts/containers, Regression resistance + +==On refactoring== +Refactoring: necessary step of preparation for further program modifications. + +reduce refactoring dimensions by 2. +2D refactoring: (rigid-soft software axe, memory-computation on the fly axe) is unnecessary and covered by additive annotations. diff --git a/documentation/Aspects/refactoring.remarkup b/documentation/Aspects/refactoring.remarkup deleted file mode 100644 index 5623b2a..0000000 --- a/documentation/Aspects/refactoring.remarkup +++ /dev/null @@ -1,4 +0,0 @@ -Refactoring - ability to quiclky adjust and apply software to a different tasks - -reduce refactoring dimensions by 2. -2D refactoring: (rigid-soft software axe, memory-computation on the fly axe) is unnecessary and covered by additive annotations. \ No newline at end of file diff --git a/documentation/Concepts/cache.remarkup b/documentation/Concepts/cache.remarkup index d7984e0..e69de29 100644 --- a/documentation/Concepts/cache.remarkup +++ b/documentation/Concepts/cache.remarkup @@ -1,7 +0,0 @@ -* enclosed(parent-child) cache storage - -* sequential flow cache storage - -* cache implemented as set of cache invariant annotations, like: -//sin = function (x:: num)::num; cache(ResultDependsOnArgumentsOnly)// - diff --git a/documentation/Concepts/containers.remarkup b/documentation/Concepts/containers.remarkup index 850f276..cf51655 100644 --- a/documentation/Concepts/containers.remarkup +++ b/documentation/Concepts/containers.remarkup @@ -1,62 +1,125 @@ ==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//, 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. +Main idea behind containers in Xreate is to gather information on //how containers are used//, by speculating on 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 +Definition of container offers one or several implementations it supports. On the other side, operations on container demand certain implementations to efficiently process container data. Based on gathered information, most appropriate tradeoff //in supply and demand// is assumed as implementation for a given container with regard to defaults, preferences, constraints and other ways to guide inference process. + +In short example below + + a= [1, 2, 3, 4, 5]:: [num]; variant(implementation(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 on. Annotation `op(randaccess)` explicitly describes operation nature, i.e. it requires any data structure that supports //random access// . +container's //offer// and operation's //demand// are explicitly expressed by annotations for clarity purposes. + +Annotation `variant(implementation(solid))` depicts that container `a` supports possible `solid` implementation, that is plain contiguous memory region or array, in other words. On the other side, annotation `op(randaccess)` expresses nature of //retrieving by index// operation (variable `b`) for it requires any data structure that supports //random access//. + +Fortunately, `solid` implementation allows efficient //random access// so it's assumed as container `a` implementation by logic inference. + +==Advantages== +- **Rapid development and optimization antagonism**. It's expected for compiler to infer adequate implementations in many cases w/o any additional developer efforts thus saving valuable time to concentrate on more important aspects. Selecting the most efficient data sctructures encourages rapid development w/o sacrificing overall program optimization by keeping reasonble efficiency automatically in contrast to many other programming languages where default data structures choosed automatically. Default options can't by equally efficient all the time, so reasoning for each particular case gives more appealing results. -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. +- **Regression resistance**. Xreate encourages frequent changes and recombination in software components, libraries and modules by automatically reevaluating and reassigning most appropriate data structures in new conditions or signalling if it's impposible. This somewhat alleviates problem of //fragile software// and gives more confidence for refactoring. -Here is a more complex example: +==Container implementations== +Xreate natively supports container implementations presented below - function test1(i:: num):: num{ - a = [1..10]:: [num]. +**on_the_fly**. This is one of the most elementary implementations and represents actually no implementation at all, because it stores no data in memory. Formally speaking, it is extremely memory efficient implementation as there is no much room to further improvements for it's already has zero memory footprint. - b = loop map(a->el:: num):: [num]{ - a * a - } +It's intended to represent broad class of any data that can be generated following some formulas/algorithms on demand. More accuratelly, it represents sequence of data that can be described by some recurrence equation to compute next element of the sequence based on currrent element. - b[i] +For example, container `[1..10]` supports `on_the_fly` representation as //recurrent function // `x(i+1) = x(i) + 1, 1<= x <= 10`, that generates successive element `x(i+1)` given `x(i)`. + +Consequently, function in example below + series= function(a:: num, b:: num):: [num] { + [a..b] } - -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 +can be compiled as just recurrent function taking current element as parameter to return successive element without requiring storage for data given solver assigns`on_the_fly` implementation to a container. + +Obviously, recurrent generation is suited for //sequential access// and can't serve `randaccess` operations. Thus `on_the_fly` assigments allowed only for `seqaccess`compliant usage. + +**solid**. On the opposite side, `solid` implementation stores all the container's data in memory occupying contigous region, known as //array//. It's computationally efficient implementation as there is no need for any additional computations apart from simple offset calculating for requested element index. + +`solid` supports `seqccess` as well as `randaccess` compilant usage. + +==Container operations== +In order to describe requirements for container all the operations are broken down into categories or types. As of now Xreate recognizes two categories: `seqaccess`, `randaccess` to denote //sequential access// and //random access// respectively. + +|Category|Operations| Supported implementations +|---|---|--- +|`op(seqaccess) `|`map loop`, `map fold`|`impl(on_the_fly)`, `impl(solid)` +|`op(randaccess)`| index retrieving|`impl(solid)` + +==Interfunction inference== +Typically functions are compact small code pieces writen by one developer and unlikely undergo often code rewrites. Therefore within one function developer could easily assign appropriate implementations by hand and there is not much gain from automatic assignments. + +Entirely different situation with communication between different functions in unrelated components written by different developers. So most capacity of automatic inference lays in interfunction and intercomponent level of interaction. + +Here is example of solitary function which return some data: + + getSomeData= function:: [num] + { [1..10] } - function test2:: num { - a= [1..10]:: [num]. +By looking at the function alone it's impossible to accurately decide on what kind of container is most useful for returned data. Even manual assignment would be suboptimal if function actually used otherwise than was intended by author. It's often the case since a software product experiences drastic changes in architecture and environment on regular basis. - b = loop map(a->el:: num):: [num]{ - a * a - } +So, Xreate's approach is to leave it without any manual assignments to let compiler decide on the matter taking into account current function utilization. - c = loop fold(b->el, 0->sum>)::num { +For example, if function`getSomeData` is called only to get sum of all elements, the function compiled as having `on_the_fly` result implementation. + +If function result processed by operations of different kind, the implementation choosed to fullfil all the uses. + + Conversely, assume function `getSum` takes container as an argument, as in example below + + getSum:: function(x:: [num]):: num { + loop fold(x->el:: num, 0->sum){ sum + el - } + } + } + +Calling such function influences on source container implementation to allow elements iteration. + +==Manual control== +There are and always will be complicate cases when any reasoning doesn't matter how powerfull it is finds no soultion or comes up with wrong or suboptimal results. Basically, two strategies exist in order to overcome it: a) give to a developer some control over reasoning process and b) fallback to all-in-one busybody defaults as last resort. Generally Xreate offers both. However, here only the ways are uncovered to manually infere with reasoning process to either improve results or break down it completely. + +**Set implementation**. There is annotation to manually assign appropriate implementation for a variable - `implementation(...)` + + a= [1..10]:: [num]; implementation(solid). + + sum= loop fold(a->el::num; 0->accum):: num { + accum + el + } + +In the example container is processed in order to get sum of all elements. Automatic reasoning would pick up way more efficient implementation in this case, however developer manually sets `solid` implementation for container `a` regardless of reasoning outcome. + +**Add implementation variant**. To //suggest// that there are additional implementations the compiler can choose from, it's possible to use an annotation `variant(implementation(...))` - 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. + a= [1..10]:: [num]; variant(implementation(solid)). + + sum= loop fold(a->el::num; 0->accum):: num { + accum + el + } + +Thus compiler recieves not only implicit offers but also provided explicitly to choose most appropriate one. However it's only soft suggestion and broadening of choices for compiler to pick up. In this example, compiler choose more efficient solution than is suggested. -To conclude, the examples show ability to automatically reassign best suited implementations for a container variables reflecting how exactly variables are processed. +**Exclude implementation variant**. In order to //forbid// or to exclude variant from considerations, it's possible to use `-variant(implementation(...))` - this differs from previous case by leading minus sign, denoting negation or exclusion in this context. -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. +**Add operation**. To provide more information on requirements for a container it's possible to use annotation `op(..)`. -==Container definitions== + a= [1..10]:: [num]. + + sum= loop fold(a->el::num; 0->accum):: num; op(randaccess) { + accum + el + } +Compiler implicitly views `loop fold` operator as `seqaccess` operation, that is tries to choose best possible //sequential access// enabled container implementation. However, this example demonstrate ability to manually strengthen requirements by demanding `randaccess` that is //random access // enabled implementation. +NOTE: It leads to a compilation error if reasoner based on manully provided refinements choose variant that actually is not supported by container definition or is not suited enough for particular operation. -==Container operations== +==On low-level details== +Factory provided reasoning algorithm located in `core/containers.lp` file. File consists of several parts: preferred solutions, constraints, costs for every possible offer-demand combination, fitness function formula, etc. -| `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 +By providing additional rules It's possble to override factory settings and redefine values to get fine-grained control over reasoning. Or even include completely different custom reasoning algorithm for your software product. \ No newline at end of file diff --git a/documentation/index.remarkup b/documentation/index.remarkup index 596c373..59d75c1 100644 --- a/documentation/index.remarkup +++ b/documentation/index.remarkup @@ -1,18 +1,9 @@ Main idea behind Xreate is to employ logic inference to address practical day-to-day programming problems. Goals: - * Optimization * Security and safety * Virtualization * High-level -To begin with, in Xreate we treat defininiton of "high-level" as practical term, meaning ability -to adapt, alter, adjust component or whole program to comply with new changed requirements or environment in general. -The more "high-level" techniques language provides, the less efforts need to be done for such transformation, given all else things being equal. - -TODO To reduce high-level or abstraction penalty .... - -* - * Code readability * Literary programming \ No newline at end of file