containers.xml
No OneTemporary
Actions

Subscribers

None

File Metadata

Created: Thu, Jul 9, 2:42 AM

containers.xml
View Options

	<?xml version="1.0" encoding="UTF-8"?>
	<chapter version="5.1" xmlns="http://docbook.org/ns/docbook"
	xmlns:xlink="http://www.w3.org/1999/xlink"
	xmlns:xila="http://www.w3.org/2001/XInclude/local-attributes"
	xmlns:xi="http://www.w3.org/2001/XInclude"
	xmlns:trans="http://docbook.org/ns/transclusion"
	xmlns:svg="http://www.w3.org/2000/svg"
	xmlns:m="http://www.w3.org/1998/Math/MathML"
	xmlns:html="http://www.w3.org/1999/xhtml"
	xmlns:db="http://docbook.org/ns/docbook">
	<?xxe-sn 2ahi4rjnvuo 2h?>

	<title><?xxe-sn 2ahi4rjnvuo 2i?>Containers</title>

	<section>
	<?xxe-sn 2alsjvonojk 1g?>

	<title><?xxe-sn 2alsjvonojk 1h?>Syntax</title>

	<para><?xxe-sn 2alsjvonojk 1z?>Container operations:</para>

	<itemizedlist>
	<?xxe-sn 2alsjvonojk 20?>

	<listitem>
	<?xxe-sn 2alsjvonojk 21?>

	<para><?xxe-sn 2alsjvonojk 22?><code><?xxe-sn 2alsjvonojk 23?>access(serial)</code>
	Denotes operation's type as a sequential access. <link
	xlink:href="#operation-access-serial"><?xxe-sn 2alsjvonojk 41?>More</link>...</para>
	</listitem>

	<listitem>
	<?xxe-sn 2alsjvonojk 24?>

	<para><?xxe-sn 2alsjvonojk 25?><code><?xxe-sn 2alsjvonojk 26?>access(rand)</code>
	Denotes operation's type as a random access. <link
	xlink:href="#operation-access-rand"><?xxe-sn 2alsjvonojk 42?>More</link>...</para>
	</listitem>
	</itemizedlist>

	<para><?xxe-sn 2alsjvonojk 1i?>Container implementations:</para>

	<itemizedlist>
	<?xxe-sn 2alsjvonojk 1j?>

	<listitem>
	<?xxe-sn 2alsjvonojk 1k?>

	<para><?xxe-sn 2alsjvonojk 1l?><code><?xxe-sn 2alsjvonojk 1y?>container(onthefly)</code>
	Lazy data structure that generates elements on the fly when needed.
	<link xlink:href="#implementation-container"><?xxe-sn 2alsjvonojk 27?>More</link>...</para>
	</listitem>

	<listitem>
	<?xxe-sn 2alsjvonojk 1n?>

	<para><?xxe-sn 2alsjvonojk 1o?><code><?xxe-sn 2alsjvonojk 28?>container(solid)</code>
	Array or data structure that occupies contiguous memory region <link
	xlink:href="#implementation-container-1"><?xxe-sn 2alsjvonojk 29?>More</link>...</para>
	</listitem>
	</itemizedlist>
	</section>

	<section>
	<?xxe-sn 2ahi4rjnvuo 2j?>

	<title><?xxe-sn 2ahi4rjnvuo 2k?>Introduction</title>

	<para><?xxe-sn 2ahi4rjnvuo 2m?><emphasis><?xxe-sn 2ahi4rjnvuo 4g?>Containers</emphasis>
	is a general term referring to the data structures that contain a group of
	elements of certain type.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2n?>Considering that virtually every program
	use containers to store, retrieve, search or otherwise process aggregate
	data, obviously efficiency of containers implementation is a priority for
	Xreate design.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2p?>There are many different data structures
	invented to serve as a containers, each of them having different
	characteristics and peculiarities with no obvious winner but rather each
	one suits the best in appropriate situations. Usually it is software
	developer's knowledge and responsibility to be able to select the most
	appropriate container's implementation for a particular use case. That
	said, Xreate goes further and gathers information on <emphasis><?xxe-sn 2ahi4rjnvuo 4h?>how
	containers are used</emphasis>, by analysing the program sources. On this
	ground it's possible to choose semi-automatically the most appropriate
	data structure for container implementation to efficiently fulfil
	particular needs in a particular situation.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2q?>In order to do this, the following approach
	is used. The way a container is defined is associated with one or more
	possible implementations it supports. On the other side, operations over
	container demand certain "good" implementations to efficiently process
	container data. Viewing it as <emphasis><?xxe-sn 2ahi4rjnvuo 53?>supply
	and demand</emphasis> setting, with a list of several acceptable
	implementations from either side, the most appropriate tradeoff is chosen
	as implementation for a given container to fulfill both sides with regard
	to defaults, preferences, constraints and other ways to guide inference
	process.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2r?>In short example below</para>

	<programlisting xml:id="Intr_1"><?xxe-sn 2ahi4rjnvuo 2s?>name = "tests/containers.cpp: Containers.Doc_Intr_1"
	//container definition:
	a= {1, 2, 3, 4, 5}:: [num]; container(solid).


	//container's operation
	x= a[0]:: num; access(rand). </programlisting>

	<para><?xxe-sn 2ahi4rjnvuo 2t?>container's <emphasis><?xxe-sn 2ahi4rjnvuo 4i?>offer</emphasis>
	<code><?xxe-sn 2apiasqubk0 c?>container(solid)</code> and operation's
	<emphasis><?xxe-sn 2ahi4rjnvuo 4j?>demand</emphasis> <code><?xxe-sn 2apiasqubk0 d?>access(rand)</code>
	are explicitly expressed by annotations for clarity purposes.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2u?>Annotation <code><?xxe-sn 2alsjvonojk 2p?>container(solid)</code>
	depicts that container <code><?xxe-sn 2ahi4rjnvuo 4l?>a</code> supports
	implementation <code><?xxe-sn 2ahi4rjnvuo 4m?>solid</code>, that is plain
	contiguous memory region or array. On the other side, annotation
	<code><?xxe-sn 2ahi4rjnvuo 4n?>access(rand)</code> expresses nature of
	<emphasis><?xxe-sn 2ahi4rjnvuo 54?>retrieving by index</emphasis>
	operation (variable <code><?xxe-sn 2ahi4rjnvuo 4p?>x</code>) and it
	requires selected data structure to support <emphasis><?xxe-sn 2ahi4rjnvuo 55?>random
	access</emphasis> to be efficiently executed.</para>

	<para><?xxe-sn 2ahi4rjnvuo 2v?>Obviously, implementation <code><?xxe-sn 2ahi4rjnvuo 4r?>solid</code>
	allows efficient random access and so it's assumed as a container
	<code><?xxe-sn 2ahi4rjnvuo 4s?>a</code>'s implementation by inference
	process.</para>

	<para><?xxe-sn 2ahi4rjnvuo 4t?>Semi-automatic, guided container's
	implementation selection has some advantages, such as:</para>

	<itemizedlist>
	<?xxe-sn 2ahi4rjnvuo 4u?>

	<listitem>
	<?xxe-sn 2ahi4rjnvuo 4v?>

	<para><?xxe-sn 2ahi4rjnvuo 4w?><emphasis><?xxe-sn 2ahi4rjnvuo 4x?>Less
	manual work</emphasis>. Inferring adequate implementations with little
	to no additional input from developer saves time to concentrate on
	more important aspects. Other approach to achieve the same, namely to
	assign default one-size-fits-all implementation with an average
	performance, is simpler but can not compete with more careful
	strategy.</para>
	</listitem>

	<listitem>
	<?xxe-sn 2ahi4rjnvuo 4y?>

	<para><?xxe-sn 2ahi4rjnvuo 4z?><emphasis><?xxe-sn 2ahi4rjnvuo 50?>Rapid
	development and optimization antagonism</emphasis>. It is important to
	keep in mind, that rapid development and frequent code changes
	somewhat contradict optimization efforts. Each round of optimization
	is leveraged by relying on concrete and particular program properties,
	overt or hidden connections and other observations. Once program
	undergo further development most of the previously sound optimization
	techniques became obsolete, irrelevant or plainly wrong. Selecting(as
	often as needed) the most efficient data structures keeps reasonable
	efficiency level automatically and does not impede possibly fast
	development pace.</para>
	</listitem>

	<listitem>
	<?xxe-sn 2ahi4rjnvuo 56?>

	<para><?xxe-sn 2ahi4rjnvuo 57?><emphasis><?xxe-sn 2ahi4rjnvuo 58?>Regression
	resistance</emphasis>. Xreate encourages frequent changes, adjusting
	and recombination in software components, libraries and modules by
	automatically reevaluating and reassigning most appropriate data
	structures in the new conditions or signalling error if it's
	impossible. This somewhat alleviates problem of <emphasis><?xxe-sn 2apiasqubk0 g?>fragile
	software</emphasis> and gives more confidence for refactoring.</para>
	</listitem>
	</itemizedlist>
	</section>

	<section>
	<?xxe-sn 2ahi4rjnvuo 32?>

	<title><?xxe-sn 2ahi4rjnvuo 33?>Container Implementations</title>

	<para><?xxe-sn 2ahi4rjnvuo 35?>Xreate supports container implementations
	presented below:</para>

	<section>
	<?xxe-sn 2ahi4rjnvuo 5g?>

	<title><?xxe-sn 2ahi4rjnvuo 5h?>Implementation
	'container(onthefly)'</title>

	<para><?xxe-sn 2alsjvonojk 2f?>Source: range list operator
	<code><?xxe-sn 2alsjvonojk 2i?>[from .. to]</code>.</para>

	<para><?xxe-sn 2alsjvonojk 2g?>Supported operations: <code><?xxe-sn 2alsjvonojk 2h?>access(serial)</code>.</para>

	<para><?xxe-sn 2ahi4rjnvuo 5j?>This is elementary implementation that
	represents <emphasis><?xxe-sn 2ahi4rjnvuo 5k?>lazy</emphasis> data
	structure — sequence of elements is generated by recurrence equation
	applied to a current element to compute next element of the sequence. It
	does not keep actual data in the memory, but instead computes necessary
	elements when accessed. This kind of implementation is rather memory
	efficient since occupied memory does not depend on container's
	size.</para>

	<para><?xxe-sn 2ahi4rjnvuo 5l?>For example, range list <code><?xxe-sn 2alsjvonojk 2a?>[1..10]</code>
	supports <code><?xxe-sn 2alsjvonojk 2b?>onthefly</code> implementation
	by using internally recurrent function <code><?xxe-sn 2alsjvonojk 2c?>x[i+1] = x[i] + 1, 1<= x <= 10</code>,
	that generates successive element <code><?xxe-sn 2alsjvonojk 2d?>x[i+1]</code>
	given <code><?xxe-sn 2alsjvonojk 2e?>x[i]</code>.</para>

	<para><?xxe-sn 2ahi4rjnvuo 5p?>Recurrent elements generation is suited
	for sequential access and can't serve random access operations.</para>
	</section>

	<section>
	<?xxe-sn 2ahi4rjnvuo 5q?>

	<title><?xxe-sn 2ahi4rjnvuo 5r?>Implementation
	'container(solid)'</title>

	<para><?xxe-sn 2alsjvonojk 2l?>Source: list operator.</para>

	<para><?xxe-sn 2alsjvonojk 2m?>Supported operations: <code><?xxe-sn 2alsjvonojk 2n?>access(serial)</code>,
	<code><?xxe-sn 2alsjvonojk 2o?>access(rand)</code>.</para>

	<para><?xxe-sn 2ahi4rjnvuo 5t?>This is implementation from the opposite
	side of the memory/computation space. It stores all the container's data
	in memory occupying contiguous region, known as <emphasis><?xxe-sn 2alsjvonojk 2j?>array</emphasis>.
	As opposed to the implementation <code><?xxe-sn 2alsjvonojk 2k?>onthefly</code>,
	it's computationally efficient for there is no need for any additional
	computations apart from simple offset calculation to get an element
	requested by an index.</para>

	<para><?xxe-sn 2ahi4rjnvuo 5u?>Due to the fact that all elements are
	present in the memory, the implementation supports sequential access as
	well as random access operations.</para>
	</section>
	</section>

	<section>
	<?xxe-sn 2ahi4rjnvuo 3f?>

	<title><?xxe-sn 2ahi4rjnvuo 3g?>Container Operations</title>

	<para><?xxe-sn 2ahi4rjnvuo 3i?>In order to describe requirements for a
	container all the operations are broken down into several categories as
	presented below.</para>

	<section>
	<?xxe-sn 2alsjvonojk 2q?>

	<title><?xxe-sn 2alsjvonojk 2r?>Operation 'access(serial)'</title>

	<para><?xxe-sn 2alsjvonojk 2s?>Operators: <code><?xxe-sn 2alsjvonojk 3e?>loop map</code>,
	<code><?xxe-sn 2alsjvonojk 3f?>loop fold</code>.</para>

	<para><?xxe-sn 2alsjvonojk 3s?>Annotation denotes sequential access
	operation, such as <code><?xxe-sn 2alsjvonojk 3t?>map loop</code> or
	<code><?xxe-sn 2alsjvonojk 3u?>map fold</code>.</para>

	<para><?xxe-sn 2alsjvonojk 43?>Example:</para>

	<programlisting xml:id="OpAccessSeq_1"><?xxe-sn 2alsjvonojk 44?>name = "tests/containers.cpp: Containers.Doc_OpAccessSeq_1"
	import raw("scripts/containers/containers.lp").

	test = function :: int; entry
	{
	range = [1..5] :: [int]; container(onthefly).
	sum = loop fold(range->el:: int, 0->acc):: [int]; access(serial)
	{
	acc + el
	}.

	sum
	}</programlisting>
	</section>

	<section>
	<?xxe-sn 2alsjvonojk 2t?>

	<title><?xxe-sn 2alsjvonojk 2u?>Operation 'access(rand)'</title>

	<para><?xxe-sn 2alsjvonojk 2v?>Operators: index</para>

	<para><?xxe-sn 2alsjvonojk 3v?>Annotation denotes random access
	operation.</para>

	<para><?xxe-sn 2apiasqubk0 1?>Example:</para>

	<programlisting xml:id="OpAccessRand_1"><?xxe-sn 2apiasqubk0 2?>name = "tests/containers.cpp: Containers.Doc_OpAccessRand_1"
	import raw("scripts/containers/containers.lp").

	test = function:: num; entry
	{
	a = {1, 2, 3, 4, 5}:: [num]; container(solid).
	a[1]:: num; access(rand)
	}</programlisting>
	</section>
	</section>

	<section>
	<?xxe-sn 2apiasqubk0 5?>

	<title><?xxe-sn 2apiasqubk0 6?>AST Attachments</title>

	<para><?xxe-sn 2apiasqubk0 7?>In order to bypass tedious writing of
	necessary annotations for each line of code that works with containers
	there are appropriate annotations already defined for common operations.
	All it takes for a client's code is to include transcend script
	<code><?xxe-sn 2apiasqubk0 8?>scripts/dfa/ast-attachments.lp</code> that
	allows to assign predefined annotations for syntactic constructs and
	operators.</para>

	<para><?xxe-sn 2apiasqubk0 9?>Example below includes <code><?xxe-sn 2apiasqubk0 e?>ast-attachments.lp</code>
	that feeds compiler with default annotations sparing developer of
	specifying them manually.</para>

	<programlisting xml:id="ASTAttach_1"><?xxe-sn 2apiasqubk0 a?>name = "tests/containers.cpp: Containers.Doc_ASTAttach_1"
	import raw("scripts/containers/containers.lp").
	import raw("scripts/dfa/ast-attachments.lp").

	test = function :: int; entry
	{
	range = [1..5] :: [int].
	sum = loop fold(range->el:: int, 0->acc):: [int]
	{
	acc + el
	}.

	sum
	}</programlisting>
	</section>
	</chapter>
	<?xxe-revisions
	#1 2019-03-07T18:26:00Z pgess
	?>

containers.xmlNo OneTemporaryActions

File Metadata

containers.xmlView Options

Event Timeline

containers.xml
No OneTemporary
Actions

containers.xml
View Options