containers.remarkup
No OneTemporary

File Metadata

Created
Sat, Nov 21, 7:19 AM

containers.remarkup

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 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.

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

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.
  • 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.

Container implementations

Xreate natively supports container implementations presented below

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.

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.

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]
}

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 seqaccesscompliant 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.

CategoryOperationsSupported implementations
op(seqaccess) map loop, map foldimpl(on_the_fly), impl(solid)
op(randaccess)index retrievingimpl(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] }

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.

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.

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(...))

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.

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.

Add operation. To provide more information on requirements for a container it's possible to use annotation op(..).

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.

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.

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.

Event Timeline