Click here to Skip to main content
Click here to Skip to main content

Primel: C++ Infinite List Library in Policy-based Design

, 7 Sep 2013
Rate this:
Please Sign up or sign in to vote.
An infinite list seen in Haskell. Moreover, you can choose its concurrent behavior through the policy.

Introduction

I am a reader of the book 'Modern C++ Design' written by Alexandrescu, Andrei. Policy based design is first seen in this book. This article assumes this book was read, so the explanation about the concept of policy based is omitted. Anyways, do you try or enjoy any kind of the pthread programming? In the abstract approach, such Policy based programming we bothered to do is simple but has many lock-unlock codes yet. Libraries must be for decreasing the number of the source code lines. Something goes bad. But the lapping libraries are useless because callers always manage dead lock free, etc., then conceptually nothing is lapped. Although it induces some limitations, the concept of infinite list with lazy evaluation is introduced. Its semantics are valid in the list comprehension of functional programming. This list comprehension is sequential programming basically but limited eager evaluation which makes possible concurrent and out of order execution can be used with it.

Background

The concept of list comprehension evokes a sequential execution because the word 'list' means in order but there is no rule of the sequential execution mathematically and so the concurrent programming is applicable. An element of a certain aggregate is accessed in order only means the code executed in one thread and in multithread order doesn't mean data but aggregate(list) management information. Absolutely 'infinite' is not computable but in some functional programming languages such like Haskell programmers can express codes without data size concerns but lazy evaluation is a minimal data instantiate scheduler. Some template parameters make it possible to ignore data size if you want with Peano axioms.

Using the Code

Assume two threads and one Lock exists. Lock-unlock is executed exclusively so two threads are ordered in time. For what is this semantics useful? In many cases, it is for checking the RAW hazard (the program can't read data before writing data). Consequently, data is aggregated in not-so-precise time order. An aggregated data in order is a list and so the list comprehension is useful and each element is executed out of order because RAW semantics is not deterministic but only if CPU can lock. Thus the primel library supports the bijection of natural numbers and data elements. Here Peano axioms, axioms of the natural numbers are needed to be induced. This library does not support scheduling so lazy evaluation programming is needed but limited eager evaluation is partially supported. Each axiom and policy choices are followed.

Primel2 axioms:

  1. Every natural number has its successor natural number, suc(a). suc(a) is intuitively a+1.
  2. if a!=b then suc(a)!=suc(b).

Policy choices:

template <class E>
class NotSized

template <class E>
class Sized

Axiom (1) is one choice so is merged Axiom (2). Slist seen in STL consists of Axiom (1) and (2). But does all previous relevant data have to be in memory? If the user algorithm implies the limited number of the data is needed, 'Sized' can be chosen. Or 'NotSized' is chosen if the data size is unpredictable. (Stop when out of memory occurred and slower).

Primel3 axiom: (3) number 0 exists.

Policy choices:

template <class E>
class InOrderRead

template <class E>
class OutOfOrderRead

template <class E>
class NoCheckRead

Reading can start with Axiom (3). Then how to end the reading is Policy choice. 'InOrderRead' will lock the reading element so only one data element can be read and erased. 'OutOfOrderRead' checks every data element status is reading or erasable. Multithread program which ends out of order fits this policy. 'NoCheckRead' forces to erase the earliest data element whether the caller sets any parameters. This occurs in the sequential program that is scheduled sequentially although it starts out of order. In short, this is a caller algorithm.

Primel5 axiom: (4)suc(n)!=0 where n is a natural number. Policy choices:

template <class E>
class InOrderWrite

template <class E>
class ReorderWrite

template <class E>
class StableInOrderWrite

template <class E>
class StableReorderWrite

template <class E>
class StableDelayWrite

Writing is related with Axiom (4) because where the first element must be written is decidable. Besides it, how to call methods follows. After the initialize with EagerSize() which limits the maximum number of active data and when it is full, this buffer changes to the lazy mode which rejects writing a new element. (Note: The meaning of active depends on the policy choice). Front() which means new in this infinite list container is called to start write data. Write() is called when the data element writing is complete. After the call, the data element is buffered. Read() is called to pass one element from the buffer to the caller with 'Pointer.' Erase() means Pointer::delete and informs the completion of the element reading. Now that phases of the data elements is defined, we return to the policy choices in terms of EagerSize() implies the lazy evaluation. 'InOrderWrite' will lock the writing element so only one data element can be written or pushed into the buffer at a time. The number of the elements of the buffered phase is not limited. EagerSize() is ignored so we can say it is not the lazy evaluation and/or EagerSize() is set to the buffer maximum size. 'ReorderWrite' will check a certain element is writing and receive the write completion by Write() out of order. But only continuous data elements is passed to the buffered phase. Eagersize() is ignored. 'StableInOrderWrite' will lock the one writing element so the number of writing phase element is 0 or 1. EagerSize() limits the sum number of the writing phase element and the buffered phase elements. 'StableReorderWrite' will check a certain element is writing and receive the write completion by Write() out of order. But only continuous data elements is passed to the buffered phase. EagerSize() limits the sum number of the writing phase elements, written but out of order data elements and the buffered phase elements. 'StableDelayWrite' will check a certain element is writing and receive the write completion by Write() out of order. But only continuous data elements is passed to the buffered phase. EgaerSize() limits the number of buffered phase elements.

Now that a container can be the element of another container, class PrimelTreePointer that makes the tree-structure data buffer available is prepared. But its FIFO Buffer depends on class Primel so two big restrictions exist; the Tree must be read and write in postorder and read from the tree must be once, then data disappears from the tree-structure. Is it useful? Yes, parse tree is one big application and LL(k) parser is corresponding to it. Generally speaking, parsers have the feature that sequential data stream changes to
independent data fragments are executed concurrently. And in practice as follows.

In class Primel::Pointer, new 4 functions are added:
Construct() is the element constructor but no container it owns. Destruct() is the element destructor for no container supported element. Null() makes Pointer::*this points no element. IsNull() returns whether Pointer::*this points no element or not. Why these functions are needed depends on its tree structure. An element can have also one container, then the container owns children elements, then each child element can have each container. If data in the element is constant or already has calculated, it has no container and is called 'leaf'. But where do the parents also called 'node' go? Parents have its parents but this circle never ends, so 'Root' is needed. 'Root' has children but is owned by no parent. Because no parent means no container, the root must be constructed in Pointer class not in Primel container class. So Pointer class is modified.

In class PrimelTreePointer, some functions are devoted to the parse tree. First of all, SetupLeaf() is called to construct a root element. (In class PrimelTreePointer, class Primel is invisible, so all objects are elements) TerminateLeaf() is called to destruct the root element constructed SetupLeaf(). But now, the root element is a leaf so SeupTree() is called and it changed to the parent node. Then the parent node can contain child elements but the node is classified elements and its container is the internal code. A child element is a leaf at first and can change to the node in the same manner of calling SetupTree(). TerminateTree() terminates internal container of the node and changed to the leaf. IsLeaf() returns 1 when the element is not the node but the leaf. How to write or read elements corresponds to that of class Primel but the container of a certain child element is known internally so Write() and Erase() can omit the parent node parameter. And the new feature for the parse tree is added. ParseUp() informs more child element is not written to the node FIFO except already FrontChild() has called and returns 1 when all child elements complete writing and only FIFO reading is expected. And also Write (int *written) is revised to be able to know this Write() call is the last Write() after ParseUp() call. *written is 1 when the last Write() is called. This is when the buffered data is calculated.

Sample program (main.c) is sieve of Eratosthenes. Each thread corresponds to each prime number and when another prime number is discovered, the new thread is created. Thread is only passed the number n where n%(the prime number of the thread)!=0 to next thread. 'passing' is list comprehension itself. Scheduler(signaling) is only used when list is (eager) full or empty.

Sample program (main2.c) is a calculater supporting +-*/(). PrimelTreePointer is used to make the parse tree and to buffer the data before evaluating. Once evaluating starts, it runs concurrently.

Points of Interest

If someone imagines Policy is axiom, it is not precise. When you decide the policy choice, you induce its Axiom and not change the Axiom itself. I suppose choices are corresponding to weak redexes of the SKI combinator Axiom. An algorithm about the large aggregation is a mathematical subclass of that about the infinite list. But infinite means a certain big number so that extending to its infinite list algorithm is not difficult. Practically infinite is treated as the theorem of producing the latest partial result of the aggregation. The word 'latest' implies 'next' so the aggregation in order is called infinite list. Once order is introduced, lazy evaluation and list comprehension must be applied. That is why infinite aggregation is treat as lazy list. Prime is named for the Go:del numbering. The prime number of the policy choices is the sufficient condition of the orthogonality. But the mathematical background of the prime numbered system is unclear. Anyway when you are confused, I recommend to write a sequential version in Haskell for its algorithm verification.

History

  • Ver 0.1 Dec. 2012
  • Ver 0.2 Jan. 2013
  • Ver 0.3 Sep. 2013

License

This article, along with any associated source code and files, is licensed under The BSD License

About the Author

T. Ogawa 2012
Software Developer
Japan Japan
I'm an old programer. My Skill starts from i8085 assembler
coding. The Object oriented programing is over 20 years
and I achived the Policy based programing. Latest interests
are pthreads and pararell programings.

Comments and Discussions

 
GeneralMy vote of 5 PinmvpMichael Haephrati מיכאל האפרתי8-Jan-13 10:29 
QuestionMy goodness Pinmemberdruidmechanics29-Dec-12 8:09 
GeneralMy vote of 5 PinmemberJerry Fish 4046-Dec-12 8:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web03 | 2.8.140709.1 | Last Updated 7 Sep 2013
Article Copyright 2012 by T. Ogawa 2012
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid