Category: Uncategorized

Logic programming is a Programming based on the notion of logical deduction in symbolic logic. Its implementation is typically based on mechanisms for automatic theorem proving

History and Goals of Logic Programming 

• “A constructive proof that for every list L there is a corresponding sorted list S composed of the same elements as L yields an algorithm for sorting a list.”
• Philosophy is shared by others not working on “logic programming” – Constable at Cornell, Martin-L¨of in Sweden, Calculus of Constructions group in France. – These groups want to extract (more traditional) program from constructive proofs.
• Very-High-Level Languages – non-procedural
• State what must be done, not how to do it. Idea is to separate logic from control.

---

Introduction to Prolog

Prolog (PROgramming in LOGic) is first and most important logic programming language. Developed in 1972 by Alain Colmerauer in Marseilles.Relational rather than functional programming language  Often best to start out as thinking of Prolog in terms of language for working with a data base.

Pure Prolog

There are three types of statements:

1. Facts (or hypotheses): father(albert,jeffrey).
2. Rules (or conditions): grandparent(X,Z) :- parent(X,Y),parent(Y,Z). (read “:-” as “if”)
3. Queries (or goals): ?-grandparent(X,jeffrey).

We should think of language as non-deterministic (or non-procedural). Looks for all answers satisfying query

Example:Facts

father(ralph,john). father(ralph,mary). father(bill,ralph).

mother(sue,john). mother(sue,mary). mother(joan,ralph).

male(john). male(ralph). male(bill).

female(mary). female(sue).

Example: Rules

is_mother(M) :- mother(M,Y).

parent(M,X) :- mother(M,X).

parent(F,X) :- father(F,X).

parents(M,F,X) :- mother(M,X), father(F,X).

sister(X,S) :- female(S), parents(M,F,X), parents(M,F,S), S\=X.

ancester(X,Y) :- parent(X,Y).

ancester(X,Y) :- parent(X,Z),ancester(Z,Y).

Selection Sort

sel_sort([],[]).

sel_sort(L,[Small|R]) :-

smallest(L,Small) ,

delete(Small,L,Rest) ,

sel_sort(Rest,R) .

/*smallest(List, Small) results in Small being the smallest element in List.*/

smallest([Small],Small) .

smallest([H|T],Small) :-

smallest(T,Small) ,

Small=<H.

smallest([H|T],H).

 

/* delete(Elt,List,Result) has Result as List after deleting Elt. */

delete(Elt,[],[]) .

delete(Elt,[Elt|T],T) .

delete(Elt,[H|T],[H|NuTail]) :-

delete(Elt,T,NuTail)

Insertion Sort

ins_sort([],[]) .

ins_sort([H|T],Sorted) :-

ins_sort(T,Rest),

insert(H,Rest,Sorted) .

/* insert(Elt,List,Result) – if List is sorted, Result is obtained by putting Elt where it fits in order in List. */

insert(Elt,[],[Elt]) .

insert(Elt,[H|T],[Elt,H|T]) :-

(Elt=<H)

insert(Elt,[H|T],[H|Sorted]) :-

insert(Elt,T,Sorted) .

 

QuickSort

/* sep(List,Key,Less,More) separates the List into the set of elements less than or equal to Key (in Less) and those greater than or equal to Key (in More) */

sep([],Key,[],[]) .

sep([H|T],Key,Less,[H|More]) :-

(H>Key) ,

sep(T,Key,Less,More) .

sep([H|T],Key,[H|Less],More) :-

(H=<Key) ,

sep(T,Key,Less,More) .

 

quick_sort([],[]) .

quick_sort([H|T],Sorted) :-

sep(T,H,Less,More) ,

quick_sort(Less,L_sorted) ,

quick_sort(More,M_sorted) ,

concat(L_sorted,[H|M_sorted],Sorted) .

/* concat(First, Second, List) results in List = concatenation of First and Second. */

concat([],L,L) .

concat([H|T],L,[H|C]) :- concat(T,L,C) .

 

Permutations

Can take advantage of reversibility since computing with relations rather than functions.

append([],L,L) .

append([H|T],L,[H|R]) :- append(T,L,R) .

 

permute([],[]) .

permute(L,[H|T]) :-

append(V,[H|U],L) ,

/* V,U stand for the part of L before and after H */

append(V,U,W) ,

permute(W,T) .

 

Logical vs Procedural Reading of Programs

• Can read Prolog program as specifying solution or computation.
• How does a prolog program compute an answer?

father(ralph,john). father(ralph,mary). father(bill,ralph).

mother(sue,john). mother(sue,mary). mother(joan,ralph).

parent(M,X) :- mother(M,X).

parent(F,X) :- father(F,X).

ancester(X,Y) :- parent(X,Y).

ancester(X,Y) :- parent(X,Z),ancester(Z,Y).

 

?-ancester(joan,X).

• Backtracking

– First succeeds with X = ralph

– Second X= john

– Third X = mary

 

Operators in Prolog

Operators in Prolog Usually used as prefix, can force to be in infix or postfix and give precedence as well.

Example: arithmetic operators: 2+3*5 abbreviates +(2,*(3,5)) • Operations are not evaluated .Better to think of operations as forming tags on values

– Forming records

– Don’t really compute anything

– Typically uninterpreted

Relations =, \=, , == (note order of composite relations) are evaluated. digit(N):- N>=0,N<10.

 

Example of Using Operations

• Trees

– Tree is either nil or is of form maketree(tree1,X,tree2).

– Programs to manipulate trees use pattern matching like in ML

• Arithmetic

– If actually wish to calculate, must use is.

– Ex. area(L,W,A) :- A is L*W.

– Can only compute A from L,W — not reversible

 

Graphs

Look at this program to find paths in graph

edge(a,b).

edge(a,f).

edge(b,c).

edge(c,a).

edge(d,e).

edge(e,a).

edge(e,c).

dumb_path(Start,Finish) :- edge(Start,Finish).

dumb_path(Start,Finish) :- edge(Start,Next),dumb_path(Next,Finish).

And then what will happens if we type:

?- dumb_path(a,c). ?- dumb_path(a,e).

The Problem will continues to go through same vertex multiple times.But if we use a more smarter program , it will keeps track of vertices which are visited.

path(Start,Finish) :- smart_path(Start,Finish,[]).

smart_path(Current,Target,Visited) :- edge(Current,Target).

smart_path(Current,Target,Visited) :-

edge(Current,Next),non_member(Next,Visited),

smart_path(Next,Target,[Next|Visited]).

non_member(Elt,[]).

non_member(Elt,[Hd | Tl]) :- Elt \== Hd, non_member(Elt,Tl).

 

Adjacency Lists

Note that database representation of graph is not only possibility. We can use adjacency list representation. Write graph as list of vertices and corresponding edges:

– Each vertex included with list of all edges going from it.

– E.g. node a represented by v(a,[b,f])

– Whole graph given by [v(a,[b,f]), v(b,[c]), v(c,[a]), v(d,[e]),v(e,[a,c])].

The advantage of adjacency lists is that it can add vertices and edges during a computation.

Write:

– vertex(Graph,Vertex) which tells if Vertex is in Graph:

vertex([v(Vert,Edge) | Rest],Vert).

vertex([_ | Rest],Vert) :- vertex(Rest,Vert).

– edge(Graph,X,Y) true if there is an edge from X to Y.

edge(Graph,X,Y) :-     member(v(X,Edges),Graph),

member(Y,Edges).

Edge(Graph,X,Y) :-    member(v(Y,Edges),Graph),

member(X,Edges).

And the rest of program for paths is as before.

 

Russian Farmer Puzzle

Variation of missionary and cannibals

Farmer taking goat and (giant) cabbage to market. Wolf following farmer. Come to river with no bridge, but only tiny boat big enough to hold farmer and one object. How can farmer get all three across river without goat eating cabbage or wolf eating goat?

Specify solution

– At any time during solution, describe current state by noting which side of river each of farmer, goat, cabbage and wolf are on (call them north/south).

– Can write down all states and all allowable transitions and then find path. (Like finding path in graph)

 

Representation

Really only 4 possible actions: Farmer crosses with one of goat, cabbage, and wolf, or farmer crosses alone. We write rules for each of it.Then,we describe states by terms — state(F,G,C,W) where each of F, G, C, W is one of north, south.We also need predicate “opposite” like : opposite(north,south). opposite(south,north).

 

Axiomatizing Actions

• Action 1: Farmer crosses with goat — need farmer and goat to start on same side, no danger of wolf eating cabbage.

transition(state(F0,F0,C,W),state(F1,F1,C,W)) :- opposite(F0,F1).

• Action 2: Farmer crosses with cabbage — need farmer and cabbage to start on same side, wolf and goat must be on opposite sides of river so goat is safe.

transition(state(F0,G,F0,W),state(F1,G,F1,W)) :-

opposite(F0,F1), opposite(G,W).

• Action 3: Farmer crosses with wolf — need farmer and wolf to start on same side, goat must be on opposite side from cabbage.

transition(state(F0,G,C,F0),state(F1,G,C,F1)) :-

opposite(F0,F1), opposite(G,C).

• Action 4: Farmer crosses alone — need cabbage and wolf on same side, goat on opposite side.

transition(state(F0,G,C,C),state(F1,G,C,C)) :-

opposite(F0,F1),opposite(G,C).

• Finding solution to problem is like finding path in graph.

 

Cut

Cut — curtails backtracking. pred(. . .):-cond1, . . . , condk, !, condk+1, . . . , condn. Cut ! is always satisfied — freezes all previous choices .If we get to point where no more solutions to condk+1,. . ., condn then all of pred(. . .) fails and no other clause or rule for pred will hold. Backtracks until ! satisfied and then never backtracks over it.

Uses of Cut :

1. Only want one rule to be applicable, so keep from trying another.
2. Cut indicates have reached a point where cannot succeed.
3. Only want one solution — avoid generating others.

Cut Examples

• sum to(N,X) should give 1 + 2 + … + N.

sum_to(1,1).

sum_to(N,Sum) :- Pred is N-1, sum_to(Pred,Partial_sum),

Sum is Partial_sum + N.

• First answer for sum to(1,X) is sum
• Second attempt goes into infinite loop.
• Most likely happens as part of resatisfying something complex. e.g. sum to(1,X),foo(apples)
• Fix by putting in sum to(1,1) :- !.

Fail

The program might result in Fail If we can exclude some cases early on, Can use cut to terminate search. Possible_Pres(willy) :- !,fail. Possible_Pres(X) :- NativeBorn(X).Fail is predicate that is never satisfied.

Problems with Cut

• Sometimes get strange behavior if not careful.
• Suppose have following program: likes(joe,pizza) :- !. likes(jane,Anything).
• What happens if put in query: ?- like(Person,pizza). Then we will get answer of joe, but not jane. Yet likes(jane,pizza) is true!

 

Cut and Reversibility

• Using cut may hinder reversibility.
• Example: append([],X,X) :- !. append([A|B],C,[A|D]) :- append(B,C,D)

. • Now only get one answer (when running either direction).

 

Formal Basis for Prolog

• Prolog based on resolution theorem proving!
• Understand program as either proof or set of procedure calls.

– The fact A(a,b,c) is just treated as an atomic statement which is asserted to be true.

– The rule A(X,Y) :- B(X,Y),C(X,Y). is understood as logical statement ∀X, Y.(B(X, Y ) ∧ C(X, Y ) → A(X, Y ))

 

Horn Clauses

• Formulas of the form ∀X1, . . . , Xm.(B1(X1, . . . , Xm) ∧ . . . ∧ Bn(X1, . . . , Xm) → A(X1, . . . , Xm)) are said to be Horn clause formulas (notice fact is degenerate case where n = 0).
• Program is understood as a collection of Horn clause formulas.
• Query ?- D(X,Y) is understood as ∃X, Y.D(X, Y ).

 

Resolution Theorem Proving

Is there a proof of ∃X, Y.D(X, Y ) from statements in program? To answer this question we need Resolution Theorem Proving. Resolution theorem proving works by attempting to show that hypotheses and negation of conclusion (i.e. ∀X, Y. ∼ D(X, Y )) generate a contradiction. Contradiction is essentially found by finding values for X, Y such that D(X, Y ).

 

Prolog and Horn Clauses

• Prolog is a restriction of Horn clause logic.
• Clause contains at most one positive atomic formula

. • Prolog does not implement resolution correctly.

• Omits the “occurs check” during unification.
• Occurs check prevents matching a variable with a term that contains the same variable
• For example unifying a(Z,Z) with a(X,successor(X))
• Avoids infinite solutions to equations X = successor(successor(successor(successor(successor(…
• Can lead to incorrect conclusions.

 

Negation in Prolog

Negation is based on assumption of complete knowledge: if system cannot prove statement is true, then it must be false.In here there are three possible outcomes of proof: Succeeds, fails,and doesn’t terminate

Returns false only if it fails (finite failure).If attempt never terminates then don’t report it false!

Note that this is a non-monotonic rule of reasoning.

Built-in predicate not defined so that not(X) succeeds if an attempt to satisfy X fails.

not(X) fails if an attempt to satisfy X succeeds.

not(X) :- X,!,fail.

not(X).

Thus ?- not(father(shezad,kim)).

reports true.

However if add fact, father(shezad,kim), then will reverse answers.

In family program from above, since there is no fact corresponding to father(shezad,kim), system deduces that it is false.

 

Not Strangeness

• Suppose define the following rule

childless(X) :- not(father(Y,X)),not(mother(Z,X)).

– If fred not mentioned childless(fred) will return yes

– But childless(Z) returns no.

• Define the following rule but no rules for young

old(X) :- not(young(X)).

• If write the other direction,

young(X) :- not(old(X)).

get the opposite response, everything is young!

 

Not Cautions

• not does not always behave properly — in particular, not(not(term)) does not usually return same answers as term

. • Safest if only use not on predicates which have no free variables (i.e., make sure variables instantiated before calling it!).

 

Evaluation of Logic Programming and Prolog

• Keep in mind difference between Prolog and pure (Horn clause) logic programming
• Prolog has many faults
• Idea of logic programming may still be quite promising if can overcome deficiencies of Prolog. (For example, see uses of Datalog in knowledge-based database.)
• If when programming, can ignore issues of control and just worry about logic, then when works can worry about control to optimize without destroying correctness.
• Very high level — self documenting.
• Efficiency is problem with Prolog. (Can optimize with tail-recursion as in ML!)
• Effectiveness limited to two classes of programs:

1. Where efficiency not a consideration.
2. Where too complex for conventional language.

• Retains useful role as well for prototyping or as specification language.
• One of reasons Japanese chose Prolog is belief that it can be speeded up by use of highly parallel machines. OR-parallelism seems useful (work on different branches of search tree in parallel), but AND-parallelism (trying to satisfy various terms of right side of rule in parallel) seems more problematic.

– One of few examples of non-procedural languages. (well, sort of)

– Generalize by replacing unification by, e.g., solving systems of inequalities. Constraint logic    programming.

Functional Programming Languages

The design of the imperative languages is based directly on the von Neumann architecture. The design of the functional languages is based on mathematical functions

Simple Functions

A mathematical function is a mapping of members of one set, called the domain set, to another set, called the range set. Function definitions are often written as a function name, followed by a list of parameters in parentheses, followed by the mapping expression. For example, cube(x) ≡  x * x * x, where x is a real number.

A lambda expression specifies the parameter(s) and the mapping of a function in the following form for the function  cube(x) = x * x * x :

ë(x) x * x * x

Lambda expressions describe nameless functions. Lambda expressions are applied to parameter(s) by placing the parameter(s) after the expression. Application of the example lambda expression is denoted as in the following example: (ë (x)x * x * x)(2) which results in the value 8.

Functional Forms

A higher-order function, or functional form, is one that either takes one or more functions as parameters or yields a function as its result, or both. One common kind of functional form is function composition, which has two functional parameters and yields a function whose value is the first actual parameter function applied to the result of the second. Function composition is written as an expression, using ° as an operator, as in h ≡ f ° g

For example, if f (x) ≡ x + 2  and  g (x) ≡ 3 * x then h is defined as h (x) ≡ f ( g ( x)), or h(x) ≡ (3 * x) + 2.

Apply-to-all is a functional form that takes a single function as a parameter and yields a list of values obtained by applying the given function to each element of a list of parameters. Apply-to-all is denoted by á.

For h(x) ≡ x * x, á(h, (2, 3, 4))  yields  (4, 9, 16).

The following is the example of using lambda expression in C++:

auto f(std::vector) -> float;

auto g(std::string) -> std::vector;

auto h(std::istream&) -> std::string;

auto fgh = compose(f, g, h);

int x = fgh(std::cin); // x = f(g(h(std::cin)))

 

Functional Programming has a few core principles:

• Functions are first-class citizens.
• Immutable state.
• Composable, generic, reusable, pure functions.
• Make heavy use of the type system.

Reasons to program functionally in C++:

• Functional Programming is not very much about language features, as it is a way of thinking about programming.
• C++ programmers can often benefit a lot from thinking (and coding) functionally.
• Modern C++ has introduced a number of interesting functional features.

One of the main abstraction tools in Functional Programming is the concept of higher order functions. Functions that take other functions as arguments and return other functions. Functions in header <algorithm> are a good old example. The introduction of lambdas in C++11 allows to officialy say that this pattern is encouraged in C++.

Examples of lambda functions in C++:

// Sort by absolute value

class abs_cmp {

public:

bool operator()(int i, int j) const {

return std::abs(i) < std::abs(j);

}

};

std::sort(begin(v), end(v), abs_cmp{});

// Roughly equivalent to the following anonymous lambda expression

std::sort(begin(v), end(v), [](int i, int j){

return std::abs(i) < std::abs(j);

});

What’s great about C++ lambdas is that they do not introduce any runtime overhead:

Each lambda is an instance of its own separate anonymous type:

• The function body is put into the type’s operator() member function.
• Captured variables are put into data members.
• Plays nicely with how templates work and how compilers do inlining of function calls.

Each lambda object has its unique type. So, to pass a lambda to a non-template function or to store them for later use, we can enter std::function. Here are some explanations about std::functions:

• It is a polymorphic wrapper around any Callable object.
• Implemented through type-erasure techniques.
• It adds overhead because of the indirect call and the lack of inlining. The overhead is the same on every other language supporting lambdas.

An exception is a problem that arises during the execution of a program. A C++ exception is a response to an exceptional circumstance that arises while a program is running, such as an attempt to divide by zero.

Exceptions provide a way to transfer control from one part of a program to another. C++ exception handling is built upon three keywords: try, catch, and throw.

• throw: A program throws an exception when a problem shows up. This is done using a throw
• catch: A program catches an exception with an exception handler at the place in a program where you want to handle the problem. The catch keyword indicates the catching of an exception.
• try: A try block identifies a block of code for which particular exceptions will be activated. It’s followed by one or more catch blocks.

Assuming a block will raise an exception, a method catches an exception using a combination of the try and catch keywords. A try/catch block is placed around the code that might generate an exception. Code within a try/catch block is referred to as protected code, and the syntax for using try/catch looks like the following:

try

{

// protected code

}catch( ExceptionName e1 )

{

// catch block

}catch( ExceptionName e2 )

{

// catch block

}catch( ExceptionName eN )

{

// catch block

}

You can list down multiple catch statements to catch different type of exceptions in case your try block raises more than one exception in different situations.

---

Throwing Exceptions

Exceptions can be thrown anywhere within a code block using throw statements. The operand of the throw statements determines a type for the exception and can be any expression and the type of the result of the expression determines the type of exception thrown.

Following is an example of throwing an exception when dividing by zero condition occurs:

double division(int a, int b) {

if( b == 0 ) {

throw “Division by zero condition!”;

}    return (a/b);

}

---

 

Catching Exceptions

The catch block following the try block catches any exception. You can specify what type of exception you want to catch and this is determined by the exception declaration that appears in parentheses following the keyword catch.

 

try {

// protected code

}catch( ExceptionName e ) {

// code to handle ExceptionName exception

}

Above code will catch an exception of ExceptionName type. If you want to specify that a catch block should handle any type of exception that is thrown in a try block, you must put an ellipsis, …, between the parentheses enclosing the exception declaration as follows:

try {

// protected code

}catch(…) {

// code to handle any exception

}

The following is an example, which throws a division by zero exception and we catch it in catch block.

#include <iostream>

using namespace std;

 

double division(int a, int b) {

if( b == 0 ) {

throw “Division by zero condition!”;

}    return (a/b);

}

 

int main () {

int x = 50;

int y = 0;

double z = 0;

 

try {

z = division(x, y);

cout << z << endl;

}catch (const char* msg) {

cerr << msg << endl;

}

 

return 0;

}

Because we are raising an exception of type const char*, so while catching this exception, we have to use const char* in catch block. If we compile and run above code, this would produce the following result:

Division by zero condition!

---

C++ Standard Exceptions

C++ provides a list of standard exceptions defined in <exception> which we can use in our programs. These are arranged in a parent-child class hierarchy shown below:

Here is the small description of each exception mentioned in the above hierarchy:

Exception	Description
std::exception	An exception and parent class of all the standard C++ exceptions.
std::bad_alloc	This can be thrown by new.
std::bad_cast	This can be thrown by dynamic_cast.
std::bad_exception	This is useful device to handle unexpected exceptions in a C++ program
std::bad_typeid	This can be thrown by typeid.
std::logic_error	An exception that theoretically can be detected by reading the code.
std::domain_error	This is an exception thrown when a mathematically invalid domain is used
std::invalid_argument	This is thrown due to invalid arguments.
std::length_error	This is thrown when a too big std::string is created
std::out_of_range	This can be thrown by the at method from for example a std::vector and std::bitset<>::operator[]().
std::runtime_error	An exception that theoretically can not be detected by reading the code.
std::overflow_error	This is thrown if a mathematical overflow occurs.
std::range_error	This is occured when you try to store a value which is out of range.
std::underflow_error	This is thrown if a mathematical underflow occurs.

---

 

Define New Exceptions

You can define your own exceptions by inheriting and overriding exception class functionality. Following is the example, which shows how you can use std::exception class to implement your own exception in standard way:

#include <iostream>

#include <exception>

using namespace std;

 

struct MyException : public exception

{    const char * what () const throw ()

{       return “C++ Exception”;

}

};

 

int main() {

try {

throw

MyException();    }catch(MyException& e) {

std::cout << “MyException caught” << std::endl;

std::cout << e.what() << std::endl;

} catch(std::exception& e) {

//Other errors

}

}

This would produce the following result:

MyException caught
C++ Exception

 

Here, what() is a public method provided by exception class and it has been overridden by all the child exception classes. This returns the cause of an exception.

Concurrency

Necessity of Concurrency

1. Processor speed has slowed and we can use transistors from Moore’s law for parallelism to increase speed.

2. Concurrent programming is necessary to utilize parallel hardware.

3. Sometimes it is natural to describe a problem with multi-threads just like divide a problem into several steps.

---

 

CONCURRENCY INTRODUCED TO C++

Original C++ Standard was published in 1998 only support single thread programming. The new C++ Standard (referred to as C++11 or C++0x) was published in 2011. It will acknowledge the existence of multithreaded programs. Memory models for concurrency is also introduced

WHY WRITE CONCURRENT PROGRAMS

Dividing a problem into multiple executing threads is an important programming technique. Multiple executing threads may be the best way to describe a problem. With multiple executing threads, we can write highly efficient program by taking advantage of any parallelism available in computer system.

---

CONCURRENCY REQUIREMENT ON PROGRAMMING LANGUAGE

Thread creation – be able to create another thread of control.

Thread synchronization – be able to establish timing relationships among threads.

One thread waits until another thread has reached a certain point in its code. One threads is ready to transmit information while the other is ready to receive the message, simultaneously.

Thread communication – be able to correctly transmit data among threads.

THREAD CREATION

C++11 introduced a new thread library including utilities for starting and managing threads. Creating an instance of std::thread will automatically start a new thread. Two thread will be created. The main thread will launch a new thread when it encounter the code std::thread th( ) to executive the function threadFunction();

The join function here is to force the current thread to wait for the thread to th finish. Otherwise the main function may exit without the thread th finished.

CRITICAL SECTION

Data are usually shared between threads. There is a problem when multiple threads attempting to operate on the same object simultaneously.

If the operation is atomic(not divisible) which means no other thread can modify any partial results during the operation on the object, then it is safe. Otherwise, we are in a race condition. a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution

Preventing simultaneous execution of critical section by multiple thread is called mutual exclusion.

EXAMPLE

Shared objects between threads will lead synchronization issues. For example

5 threads created try to increase the counter 5000 times. This program has a synchronization problem. Here are some result obtained on my computer:

24138

20326

23345

25000

17715

It is not the same every time.

---

USING ATOMIC TYPES

C++11 concurrency library introduces atomic types as a template class: std::atomic. You can use any type you want with the template and the operation on that variable will be atomic and so thread-safe.

std::atomic<Type> object.

Different locking technique is applied according to the data type and size.

a. Lock-free technique: integral types like int, long, float. It is much faster than mutexes technique.

b. Mutexes technique: for big type(such as 2MB storage). There is no performance advantage for atomic type over mutexes.

---

 

SYNCHRONIZATION BETWEEN THREADS

Except for protecting shared data, we also need to synchronization action on separate threads. In C++ Standard Library, conditional variables and futures are provided to handle synchronization problems. The condition_variable class is a synchronization primitive that can be used to block a thread, or multiple threads at the same time, until:

a. a notification is received from another thread

b. a timeout expires

Any thread that intends to wait on std::condition_variable has to acquire a std::unique_lock first. The wait operations atomically release the mutex and suspend the execution of the thread. When the condition variable is notified, the thread is awakened, and the mutex is reacquired.

---

 

MORE ABOUT UNIQUE_LOCK

The condition variables require std::unique_lock rather than the std::lock_quard — the waiting thread must unlock the mutex while it is waiting , the lock it again afterwards and the std::lock_guard does not provide such flexibility.

The flexibility to unlock a std::unique_lock is not just used for the call to wait() , it is also used once we’ve got the data to process, but before processing it (#6): processing data can potentially be a time-consuming operation, and as we saw in chapter 3, it is a bad idea to hold a lock on a mutex for longer than necessary.

---

 

ONE-OFF EVENT WITH FUTURES

If a thread needs to wait for a specific one-off event, then it obtains a future representing this event. The thread can poll the future to see if the event has occurred while performing some other task.

Two sorts of futures templates in C++ Standard Library.

a. std::unique_furture<> — the instance is the only one that refers to its associated event.

b. std::shared_future<> — multiple instances of it may refer to the same event. All the instance become ready at the same time, and they may all access any data associated with the event.

---

 

MEMORY MODEL

Two aspects to the memory model:

a. the basic structural aspects — how things are laid out in memory

Every variable is an object, including those that are members of other objects. Every object occupies at least one memory location.

Variables of fundamental type such as int or char are exactly one memory location, whatever their size, even if they’re adjacent or part of an array. Adjacent bit fields are part of the same memory location.

b. The concurrency aspects

If there is no enforced ordering between two accesses to a single memory location from separate threads, these accesses is not atomic,if one or both accesses is a write, this is a data race, and causes undefined behavior.

---

 

OPERATIONS ORDERS

Each of the operations on atomic types has an optional memory-ordering argument that be used to specify the required memory-ordering semantics. These operations can be divided into three categories:

A. Store operation

which can have memory_order_relaxed, memorey_order_release or memory_order_seq_cst ordering

B. Load operations

which can have memory_order_relaxed, memory_order_consume, memory_order_acquire, or memory_order_seq_cst ordering

C. Read-modify-write operations

which can have memory_order_relaxed, memory_order_consume, memory_order_acquire, memory_order_release, memory_order_acq_rel, or memory_order_seq_cst ordering

---

 

CONCLUSION

C++ committee introduced the concurrency into C++0X and C++11 make it support multi-threads which make C++ a adaptive to the current programming style. To make concurrency possible, language should support threads launch, threads synchronization and threads communication.

The basic problem in concurrency is how to protected shared data and synchronize threads. Mutexes and atomic template are the solution to race conditions.

 

Lower level control based on memory models allow us to clear the semantic meaning in concurrency operation

OOP (Object Oriented Programming)

The concept of object-oriented programming had its roots in SIMULA 67 but was not fully developed until the evolution of Smalltalk resulted in Smalltalk 80 (in 1980, of course). Indeed, some consider Smalltalk to be the base model for a purely objectoriented programming language. A language that is object oriented must provide support for three key language features: abstract data types, inheritance, and dynamic binding of method calls to methods. Abstract data types were discussed in detail in Chapter 11, so this chapter focuses on inheritance and dynamic binding.

There are a few principle concepts that form the foundation of object-oriented programming:

1. Object

This is the basic unit of object oriented programming. That is both data and function that operate on data are bundled as a unit called as object.

 2. Class

When you define a class, you define a blueprint for an object. This doesn’t actually define any data, but it does define what the class name means, that is, what an object of the class will consist of and what operations can be performed on such an object.

There are several ways a derived class can differ from its parent. Following are the most common differences between a parent class and its subclasses:

1. The parent class can define some of its variables or methods to have private access, which means they will not be visible in the subclass.
2. The subclass can add variables and/or methods to those inherited from the parent class.
3. The subclass can modify the behavior of one or more of its inherited methods. A modified method has the same name, and often the same protocol, as the one of which it is a modification.

 3. Abstraction

Data abstraction refers to, providing only essential information to the outside world and hiding their background details, i.e., to represent the needed information in program without presenting the details.

For example, a database system hides certain details of how data is stored and created and maintained. Similar way, C++ classes provides different methods to the outside world without giving internal detail about those methods and data.

 4. Encapsulation

Encapsulation is placing the data and the functions that work on that data in the same place. While working with procedural languages, it is not always clear which functions work on which variables but object-oriented programming provides you framework to place the data and the relevant functions together in the same object.

 5. Inheritance

One of the most useful aspects of object-oriented programming is code re usability. As the name suggests Inheritance is the process of forming a new class from an existing class that is from the existing class called as base class, new class is formed called as derived class.

This is a very important concept of object-oriented programming since this feature helps to reduce the code size.

As a simple example of inheritance, consider the following: Suppose we have a class named Vehicles, which has variables for year, color, and make. A natural specialization, or subclass, of this would be Truck, which could inherit the variables from Vehicle, but would add variables for hauling capacity and number of wheels.

One disadvantage of inheritance as a means of increasing the possibility of reuse is that it creates dependencies among the classes in an inheritance hierarchy. This result works against one of the advantages of abstract data types, which is that they are independent of each other. Of course, not all abstract data types must be completely independent.

But in general, the independence of abstract data types is one of their strongest positive characteristics. However, it may be difficult, if not impossible, to increase the re-usability of abstract data types without creating dependencies among some of them. Furthermore, in many cases, the dependencies naturally mirror dependencies in the underlying problem space.

6. Polymorphism

The ability to use an operator or function in different ways in other words giving different meaning or functions to the operators or functions is called polymorphism. Poly refers to many. That is a single function or an operator functioning in many ways different upon the usage is called polymorphism.

 7. Overloading

The concept of overloading is also a branch of polymorphism. When the exiting operator or function is made to operate on new data type, it is said to be overloaded.

---

 

Issues for Object-Oriented Languages

A number of issues must be considered when designing the programming language features to support inheritance and dynamic binding. Those that we consider most important are discussed in this section.

A. The Exclusivity of Objects

A language designer who is totally committed to the object model of computation designs an object system that subsumes all other concepts of type. Everything, from a simple scalar integer to a complete software system, is an object in this mind-set. The advantage of this choice is the elegance and pure uniformity of the language and its use.

The primary disadvantage is that simple operations must be done through the message-passing process, which often makes them slower than similar operations in an imperative model, where single machine instructions implement such simple operations. In this purest model of objectoriented computation, all types are classes. There is no distinction between predefined and user-defined classes. In fact, all classes are treated the same way and all computation is accomplished through message passing.

One alternative to the exclusive use of objects that is common in imperative languages to which support for object-oriented programming has been added is to retain the complete collection of types from a traditional imperative programming language and simply add the object typing model. This approach results in a larger language whose type structure can be confusing to all but expert users.

Another alternative to the exclusive use of objects is to have an imperative style type structure for the primitive scalar types, but implement all structured types as objects. This choice provides the speed of operations on primitive values that is comparable to those expected in the imperative model. Unfortunately, this alternative also leads to complications in the language. Invariably, non object values must be mixed with objects. This creates a need for so-called wrapper classes for the non object types, so that some commonly needed operations can be implemented as methods of the wrapper class. When such an operation is needed for a non object value, the value is converted to an object of the associated wrapper class and the appropriate method of the wrapper class is used. This design is a trade of language uniformity and purity for efficiency.

B.Single and Multiple Inheritance

Another simple issue is: Does the language allow multiple inheritance (in addition to single inheritance)? Maybe it’s not so simple. The purpose of multiple inheritance is to allow a new class to inherit from two or more classes. Because multiple inheritance is sometimes highly useful, why would a language designer not include it? The reasons lie in two categories: complexity and efficiency. The additional complexity is illustrated by several problems.

First, note that if a class has two unrelated parent classes and neither defines a name that is defined in the other, there is no problem. However, suppose a subclass named C inherits from both class A and class B and both A and B define an inheritable method named display. If C needs to reference both versions of display, how can that be done? This ambiguity problem is further complicated when the two parent classes both define identically named methods and one or both of them must be overridden in the subclass. Another issue arises if both A and B are derived from a common parent, Z, and C has both A and B as parent classes. This situation is called diamond or shared inheritance. In this case, both A and B should include Z’s inheritable variables. Suppose Z includes an inheritable variable named sum. The question is whether C should inherit both versions of sum or just one, and if just one, which one? There may be programming situations in which just one of the two should be inherited, and others in which both should be inherited.

The question of efficiency may be more perceived than real. In C++, for example, supporting multiple inheritance requires just one additional array access and one extra addition operation for each dynamically bound method call, at least with some machine architectures (Stroustrup, 1994, p. 270). Although this operation is required even if the program does not use multiple inheritance, it is a small additional cost.

The use of multiple inheritance can easily lead to complex program organizations. Many who have attempted to use multiple inheritance have found that designing the classes to be used as multiple parents is difficult. Maintenance of systems that use multiple inheritance can be a more serious problem, for multiple inheritance leads to more complex dependencies among classes. It is not clear to some that the benefits of multiple inheritance are worth the added effort to design and maintain a system that uses it.

Interfaces are an alternative to multiple inheritance. Interfaces provide some of the benefits of multiple inheritance but have fewer disadvantages.

C.Allocation and Deallocation of Objects

There are two design questions concerning the allocation and deallocation of objects. The first of these is the place from which objects are allocated. If they behave like the abstract data types, then perhaps they can be allocated from anywhere. This means they could be allocated from the run-time stack or explicitly created on the heap with an operator or function, such as new. If they are all heap dynamic, there is the advantage of having a uniform method of creation and access through pointer or reference variables. This design simplifies the assignment operation for objects, making it in all cases only a pointer or reference value change. It also allows references to objects to be implicitly referenced, simplifying the access syntax.

If objects are stack dynamic, there is a problem with regard to sub types. If class B is a child of class A and B is a sub type of A, then an object of B type can be assigned to a variable of A type. For example, if b1 is a variable of B type and a1 is a variable of A type, then a1 = b1; is a legal statement. If a1 and b1 are references to heap-dynamic objects, there is no problem—the assignment is a simple pointer assignment. However, if a1 and b1 are stack dynamic, then they are value variables and, if assigned the value of the object, must be copied to the space of the target object. If B adds a data field to what it inherited from A, then a1 will not have sufficient space on the stack for all of b1. The excess will simply be truncated, which could be confusing to programmers who write or use the code. This truncation is called object slicing. The following example illustrates the problem.

class A { int x;

. . .

}; class B : A { int y;

. . .

}

The second question here is concerned with those cases where objects are allocated from the heap. The question is whether deallocation is implicit, explicit, or both. If deallocation is implicit, some implicit method of storage reclamation is required. If deallocation can be explicit, that raises the issue of whether dangling pointers or references can be created.

D.Dynamic and Static Binding

As we have discussed, dynamic binding of messages to methods is an essential part of object-oriented programming. The question here is whether all binding of messages to methods is dynamic. The alternative is to allow the user to specify whether a specific binding is to be dynamic or static. The advantage of this is that static bindings are faster. So, if a binding need not be dynamic, why pay the price?

E.Nested Classes

One of the primary motivations for nesting class definitions is information hiding. If a new class is needed by only one class, there is no reason to define it so it can be seen by other classes. In this situation, the new class can be nested inside the class that uses it. In some cases, the new class is nested inside a subprogram, rather than directly in another class.

The class in which the new class is nested is called the nesting class. The most obvious design issues associated with class nesting are related to visibility. Specifically, one issue is: Which of the facilities of the nesting class are visible in the nested class? The other main issue is the opposite: Which of the facilities of the nested class are visible in the nesting class?

---

 

Support for Object-Oriented Programming in C++

C++ evolved from C and SIMULA 67, with the design goal of support for object-oriented programming while retaining nearly complete backward compatibility with C. C++ classes, as they are used to support abstract data types. C++ support for the other essentials of object-oriented programming is explored in this section. The whole collection of details of C++ classes, inheritance, and dynamic binding is large and complex. This section discusses only the most important among these topics, specifically, those directly related to the design issues.

C++ was the first widely used object-oriented programming language, and is still among the most popular. So, naturally, it is the one with which other languages are often compared. For both of these reasons, our coverage of C++ here is more detailed than that of the other example languages.

A. Introduction to Data Abstraction

Data abstraction refers to, providing only essential information to the outside world and hiding their background details, i.e., to represent the needed information in program without presenting the details. Data abstraction is a programming (and design) technique that relies on the separation of interface and implementation.

Let’s take one real life example of a TV, which you can turn on and off, change the channel, adjust the volume, and add external components such as speakers, VCRs, and DVD players, BUT you do not know its internal details, that is, you do not know how it receives signals over the air or through a cable, how it translates them, and finally displays them on the screen.

Thus, we can say a television clearly separates its internal implementation from its external interface and you can play with its interfaces like the power button, channel changer, and volume control without having zero knowledge of its internals.

Now, if we talk in terms of C++ Programming, C++ classes provides great level of data abstraction. They provide sufficient public methods to the outside world to play with the functionality of the object and to manipulate object data, i.e., state without actually knowing how class has been implemented internally.

Classes in C++ language are based on C struct type and Simula 67 classes. All of the class instances of a class share a single copy of the member functions. Each instance of a class has its own copy of the class data members. Instances can be static, stack dynamic, or heap dynamic.

For example, your program can make a call to the sort() function without knowing what algorithm the function actually uses to sort the given values. In fact, the underlying implementation of the sorting functionality could change between releases of the library, and as long as the interface stays the same, your function call will still work.

In C++, we use classes to define our own abstract data types (ADT). You can use the cout object of class ostream to stream data to standard output like this:

#include <iostream> using namespace std;

int main( ) {

cout << “Hello C++” <<endl;

return 0;

}

Here, you don’t need to understand how cout displays the text on the user’s screen. You need to only know the public interface and the underlying implementation of cout is free to change.

---

B.Access Labels Enforce Abstraction

In C++, we use access labels to define the abstract interface to the class. A class may contain zero or more access labels:

• Members defined with a public label are accessible to all parts of the program. The data-abstraction view of a type is defined by its public members.

• Members defined with a private label are not accessible to code that uses the class. The private sections hide the implementation from code that uses the type.

There are no restrictions on how often an access label may appear. Each access label specifies the access level of the succeeding member definitions. The specified access level remains in effect until the next access label is encountered or the closing right brace of the class body is seen.

---

C.Benefits of Data Abstraction

Data abstraction provides two important advantages:

• Class internals are protected from inadvertent user-level errors, which might corrupt the state of the object.
• The class implementation may evolve over time in response to changing requirements or bug reports without requiring change in user-level code.

By defining data members only in the private section of the class, the class author is free to make changes in the data. If the implementation changes, only the class code needs to be examined to see what affect the change may have. If data are public, then any function that directly accesses the data members of the old representation might be broken.

---

 D.Data Abstraction Example

Any C++ program where you implement a class with public and private members is an example of data abstraction. Consider the following example:

#include <iostream>

using namespace std;

class Adder {    public: // constructor

Adder(int i = 0)

{          total = i; // interface to outside world

void addNum(int number) {

total += number;

} // interface to outside world

int getTotal() {

return total;

};

private:

// hidden data from outside world

int total;

};

int main( ) {

Adder a;

a.addNum(10);

a.addNum(20);

a.addNum(30);

cout << “Total ” << a.getTotal() <<endl;

return 0;

}

When the above code is compiled and executed, it produces the following result:

Total : 60

Above class adds numbers together, and returns the sum. The public members addNum and getTotal are the interfaces to the outside world and a user needs to know them to use the class. The private member total is something that the user doesn’t need to know about, but is needed for the class to operate properly.

---

 E.Designing Strategy

Abstraction separates code into interface and implementation. So while designing your component, you must keep interface independent of the implementation so that if you change underlying implementation then interface would remain intact.

In this case whatever programs are using these interfaces, they would not be impacted and would just need a recompilation with the latest implementation.

---

 

F. Encapsulation

All C++ programs are composed of the following two fundamental elements:

• Program statements (code): This is the part of a program that performs actions and they are called functions.
• Program data: The data is the information of the program which affected by the program functions.

Encapsulation is an Object Oriented Programming concept that binds together the data and functions that manipulate the data, and that keeps both safe from outside interference and misuse. Data encapsulation led to the important OOP concept of data hiding.

Data encapsulation is a mechanism of bundling the data, and the functions that use them and data abstraction is a mechanism of exposing only the interfaces and hiding the implementation details from the user.

C++ supports the properties of encapsulation and data hiding through the creation of user-defined types, called classes. We already have studied that a class can contain private, protected and public members. By default, all items defined in a class are private. For example:

class Box {    public:

double getVolume(void) {

return length * breadth * height;

}

private:       double length;      //

Length of a box       double breadth;     //

Breadth of a box       double height;      //

Height of a box

};

The variables length, breadth, and height are private. This means that they can be accessed only by other members of the Box class, and not by any other part of your program. This is one way encapsulation is achieved.

To make parts of a class public (i.e., accessible to other parts of your program), you must declare them after the public keyword. All variables or functions defined after the public specifier are accessible by all other functions in your program.

Making one class a friend of another exposes the implementation details and reduces encapsulation. The ideal is to keep as many of the details of each class hidden from all other classes as possible.

VII. Subprograms

Programming languages, in particular C++, not only provide a set of basic operations and statements, but also a means to define our own operations and statements. We call the operations and statements that we define functions and procedures, respectively. Procedures and functions (subprograms) may have parameters. These represent the objects from our program that are used in the subprogram.

Subprogram definitions may appear before or after the main program.

A function can only be used if previously declared. A function can be declared and used before its code is defined.

Once a subprogram has been declared, it can be used. Functions are used as operations within expressions. Procedures are used as statements. Example:

i = times (3, i + 2) + 1; // function … factors(i);           // procedure …

Appropriate use of subprograms:

1. Increases readability: programs are better structured and easier to understand.
2. Enables the use of abstraction in the program design.
3. Facilitates code reuse.

---

SUBPROGRAM WITH PARAMETER PASSING

When a subprogram is called, the arguments are passed to the subprogram, so that its code can be executed:

times (3, i + 2) + …int times(int x, int y) { … }

Each argument must have the same type as its corresponding parameter. In general, any expression can be the argument of a subprogram:

double maximum (double a, double b);

…

z = maximum (x, y);

…

r = maximum (3, gcd(s – 4, i) + alpha);

…

m = maximum (x, maximum (y + 3, 2*Pi*radius));

An object (a variable) is associated with a value and a memory location. In C++, there are two methods for parameter passing:

1. Passing the value (call-by-value) : This is denoted by just declaring the type and the name of the parameter.
2. Passing the memory location (call-by-reference) : This is denoted by adding the symbol & next to the parameter type.

void p (int x, int& y) { … }

1. Call-by-value makes a copy of the argument at the beginning of the subprogram. It is equivalent to having, a statement that assigns the value of each argument to the corresponding parameter:

times (3, i + 2)

is equivalent to:

int times (int x, int y) { x = 3; y = i + 2; int p = 0; … }

The effect of call-by-reference is that the parameter becomes the same object (variable) as the argument, i.e., the parameter becomes an alias of the argument.

Example: procedure to swap the value of two variables

void exchange (int& x, int& y) {

int z = x;

x= y;

y= z;

}

exchange (a, b);

Is equivalent to having:

void exchange (int& x, int& y) {

int z = a;

a = b;

b = z;

}

 

Control Structure

A control structure is a control statement and the collection of statements whose execution it controls.

A program is usually not limited to a linear sequence of instructions. During its process, it may bifurcate, repeat code or take decisions. For that purpose, C++ provides control structures that serve to specify what has to be done by our program, when and under which circumstances.

With the introduction of control structures we are going to have to introduce a new concept: the compound-statement or block. A block is a group of statements which are separated by semicolons (;) like all C++ statements, but grouped together in a block enclosed in braces “{ }”

{ statement1; statement2; statement3; }

Most of the control structures require a generic statement as part of its syntax. A statement can be either a simple statement which is a simple instruction ending with a semicolon or a compound statement which is several instructions grouped in a block, like the one just described. In the case that a simple statement, it does not need to enclose it in braces ({}). But in the case of a compound statements , it must be enclosed between braces ({}), forming a block.

---

 

A. Selection Statements

1. Two-Way Selection Statements

The if keyword is used to execute a statement or block only if a condition is fulfilled. Its form is:if (condition) statement

Where condition is the expression that is being evaluated. If this condition is true, statement is executed. If it is false, statement is ignored (not executed) and the program continues right after this conditional structure.

For example, the following code fragment prints x is 100 only if the value stored in the x variable is indeed 100:

if (x == 100)   cout << “x is 100”;

If we want more than a single statement to be executed in case that the condition is true we can specify a block using braces { } fulfilled by using the keyword else. Its form used in conjunction with if is :

if (condition) statement1 else statement2 ;

For example:

if (x == 100)   cout << “x is 100”;else cout << “x is not 100”;

The code prints on the screen x is 100 if indeed x has a value of 100, but if it has not and only if not It prints out x is not 100.

The if + else structures can be concatenated with the intention of verifying a range of values. The following example shows its use telling if the value currently stored in x is positive, negative or none of them (i.e. zero)executed, we must group them in a block by enclosing them in braces { }.

---

2. Nesting Selection Statements

if( boolean_expression 1) {// Executes when the boolean expression 1 is true    if(boolean_expression 2) {// Executes when the boolean expression 2 is true}

}

Nested if-else statements mean that you can use one if or else if statement inside another if or else if statements.

Example:

#include <iostream> using namespace std;

int main () {

// local variable declaration:

int a = 100;    int b = 200;

// check the boolean condition

if( a == 100 ) {

// if condition is true then check the following       i

f( b == 200 ) {

// if condition is true then print the following

cout << “Value of a is 100 and b is 200” << endl;

}

}

cout << “Exact value of a is : ” << a << endl;

cout << “Exact value of b is : ” << b << endl;

return 0;

}

When the above code is compiled and executed, it produces the following result:

Value of a is 100 and b is 200
Exact value of a is : 100
Exact value of b is : 200

---

3. Multiple-Way Selection Statements

Multiple-Way Selection Statements objective is to check several possible constant values for an expression. Something similar to what we did at the beginning of this section with the concatenation of several if and else if instructions. Its form is the following:

switch (expression)

{

case constant1:

group of statements 1;

break;    case constant2:

group of statements 2;

break;              default:

default group of statements

}

It works in the following way: switch evaluates expression and checks if it is equivalent to constant1, if it is, it executes group of statements 1 until it finds the break statement. When it finds this break statement the program jumps to the end of the switch selective structure.

If expression was not equal to constant1 it will be checked against constant2. If it is equal to this, it will execute group of statements 2 until a break keyword is found, and then will jump to the end of the switch selective structure.

Finally, if the value of expression did not match any of the previously specified constants (you can include as many case labels as values you want to check), the program will execute the statements included after the default: label, if it exists

(since it is optional).

Both of the following code fragments have the same behavior:

switch example	if-else equivalent
switch (x) {   case 1:     cout << “x is 1”;     break;   case 2:     cout << “x is 2”;     break;   default:cout << “value of x unknown”; }	if (x == 1) {   cout << “x is 1”;} else if (x == 2) {   cout << “x is 2”; } else {   cout << “value of x unknown”;    }

 

The switch statement is a bit peculiar within the C++ language because it uses labels instead of blocks. This forces us to put break statements after the group of statements that we want to be executed for a specific condition. Otherwise the remainder statements -including those corresponding to other labels- will also be executed until the end of the switchselective block or a break statement is reached.

 

For example, if we did not include a break statement after the first group for case one, the program will not automatically jump to the end of the switch selective block and it would continue executing the rest of statements until it reaches either a break instruction or the end of the switch selective block. This makes it unnecessary to include braces { }surrounding the statements for each of the cases, and it can also be useful to execute the same block of instructions for different possible values for the expression being evaluated. For example:

 

9   }

constants. Therefore we cannot put variables as labels (for example case n: where n is a variable) or ranges (case (1..3):) because they are not valid C++ constants.

If you need to check ranges or values that are not constants, use a concatenation of if and else if statements.

---

 

B. Iteration Statements

An iterative statement is one that causes a statement or collection of statements to be executed zero, one, or more times. An iterative statement is often called a loop. Iteration is the very essence of the power of the computer. If some means of repetitive execution of a statement or collection of statements were not possible, programmers would be required to state every action in sequence; useful programs would be huge and inflexible and take unacceptably large amounts of time to write and mammoth amounts of memory to store.

1. Counter-Controlled Loops

A counting iterative control statement has a variable, called the loop variable, in which the count value is maintained. It also includes some means of specifying the initial and terminal values of the loop variable, and the difference between sequential loop variable values, often called the stepsize. The initial, terminal, and stepsize specifications of a loop are called the loop parameters.Its format is: for (initialization; condition; increase) statement;

and its main function is to repeat statement while condition remains true, like the while loop. But in addition, the for loop provides specific locations to contain an initialization statement and an increase statement. So this loop is specially designed to perform a repetitive action with a counter which is initialized and increased on each iteration.

It works in the following way:

1. initialization is executed. Generally, it is an initial value setting for a counter variable. This is executed only once.
2. condition is checked. If it is true the loop continues, otherwise the loop ends and statement is skipped (not executed).
3. statement is executed. As usual, it can be either a single statement or a block enclosed in braces { }.
4. finally, whatever is specified in the increase field is executed and the loop gets back to step 2.
5. Here is an example of countdown using a for loop:

// countdown using a for loop#include <iostream> using namespace std; int main () { for (int n=10; n>0; n–) {     cout << n << “, “; } cout << “FIRE!\n”; return 0; }
Result :10, 9, 8, 7, 6, 5, 4, 3, 2, 1, FIRE!

The initialization and increase fields are optional. They can remain empty, but in all cases the semicolon signs between them must be written. For example we could write: for (;n<10;) if we wanted to specify no initialization and no increase; or for (;n<10;n++) if we wanted to include an increase field but no initialization (maybe because the variable was already initialized before).

Optionally, using the comma operator (,) we can specify more than one expression in any of the fields included in a forloop, like in initialization, for example. The comma operator (,) is an expression separator, it serves to separate more than one expression where only one is generally expected. For example, suppose that we wanted to initialize more than one variable in our loop:

{

//whatever here…

}

 

This loop will execute for 50 times if neither n or i are modified within the loop:

1 for ( n=0, i=100 ; n!=i ; n++, i– )  n starts with a value of 0, and i with 100, the condition is n! = i (that n is not equal to i). Because n is increased by one and i decreased by one, the loop’s condition will become false after the 50th loop, when both n and i will be equal to 50.

2. Logically Controlled Loops

Logically controlled loops are more general than counter-controlled loops. Every counting loop can be built with a logical loop, but the reverse is not true. Also, recall that only selection and logical loops are essential to express the control structure of any flowchart.

a. Pre-test Loop

In the pretest version of a logical loop (while), the statement or statement segment is executed as long as the expression evaluates to true.Its format is: while (expression) statement

and its functionality is simply to repeat statement while the condition set in expression is true.

For example, we are going to make a program to countdown using a while loop:

// custom countdown using while#include <iostream> using namespace std;   int main () {   int n; cout << “Enter the starting number > “;   cin >> n;   while (n>0) {     cout << n << “, “; –n; }   cout << “FIRE!\n”; return 0; }

 

Result :Enter the starting number > 8 8, 7, 6, 5, 4, 3, 2, 1, FIRE!

When the program starts the user is prompted to insert a starting number for the countdown. Then the while loop begins, if the value entered by the user fulfills the condition n>0 (that n is greater than zero) the block that follows the condition will be executed and repeated while the condition (n>0) remains being true.

The whole process of the previous program can be interpreted according to the following script (beginning in main):

1. User assigns a value to n
2. The while condition is checked (n>0). At this point there are two possibilities:
   • condition is         true:     statement         is         executed          (to        step      3)
   • condition is false: ignore statement and continue after it (to step 5)
3. Execute statement: cout << n << “, “;

–n;

(prints the value of n on the screen and decreases n by 1)

4. End of block. Return automatically to step 2
5. Continue the program right after the block: print FIRE! and end program.

When creating a while-loop, we must always consider that it has to end at some point, therefore we must provide within the block some method to force the condition to become false at some point, otherwise the loop will continue looping forever. In this case we have included –n; that decreases the value of the variable that is being evaluated in the condition (n) by one – this will eventually make the condition (n>0) to become false after a certain number of loop iterations: to be more specific, when n becomes 0, that is where our while-loop and our countdown end.

Of course this is such a simple action for our computer that the whole countdown is performed instantly without any practical delay between numbers.

b. Post-Test Loop

In the post test loop (do), the loop body is executed until the expression evaluates to false. The only real difference between the do and the while is that the do always causes the loop body to be executed at least once.

Its format is: do statement while (condition);

Its functionality is exactly the same as the while loop, except that condition in the do-while loop is evaluated after the execution of statement instead of before, granting at least one execution of statement even if condition is never fulfilled. For example, the following example program echoes any number you enter until you enter 0.

// number echoer #include <iostream> using namespace std;   int main () { unsigned long n; do { cout << “Enter number (0 to end): “;     cin >> n;     cout << “You entered: ” << n << “\n”; } while (n != 0);   return 0; }

Result :Enter number (0 to end): 12345 You entered: 12345 Enter number (0 to end): 160277 You entered: 160277 Enter number (0 to end): 0 You entered: 0

The do-while loop is usually used when the condition that has to determine the end of the loop is determined within the loop statement itself, like in the previous case, where the user input within the block is what is used to determine if the loop has to end. In fact, if you never enter the value 0 in the previous example you can be prompted for more numbers forever.

3.User-Located Loop Control Mechanisms

a. The break statement

Using break we can leave a loop even if the condition for its end is not fulfilled. It can be used to end an infinite loop, or to force it to end before its natural end. For example, we are going to stop the count down before its natural end

// break loop example #include <iostream> using namespace std;   int main () {   int n; for (n=10; n>0; n–) { cout << n << “, “;     if (n==3) { cout << “countdown aborted!”;       break; }   }   return 0; }

Result :10, 9, 8, 7, 6, 5, 4, 3, countdown aborted!

b. The continue statement

The continue statement causes the program to skip the rest of the loop in the current iteration as if the end of the statement block had been reached, causing it to jump to the start of the following iteration. For example, we are going to skip the number 5 in our countdown:

// continue loop example #include <iostream> using namespace std; int main () { for (int n=10; n>0; n–) {     if (n==5)

 

Result :10, 9, 8, 7, 6, 4, 3, 2, 1, FIRE!

c. The go to statement

goto allows to make an absolute jump to another point in the program. You should use this feature with caution since its execution causes an unconditional jump ignoring any type of nesting limitations.

The destination point is identified by a label, which is then used as an argument for the goto statement. A label is made of a valid identifier followed by a colon (:).

Generally speaking, this instruction has no concrete use in structured or object oriented programming aside from those that low-level programming fans may find for it. For example, here is our countdown loop using goto :

// goto loop example #include <iostream> using namespace std;   int main () {   int n=10;   loop:   cout << n << “, “; n–; if (n>0) goto loop;   cout << “FIRE!\n”; return 0; }

 

Result :10, 9, 8, 7, 6, 5, 4, 3, 2, 1, FIRE!

 

The exit function exit is a function defined in the cstdlib library. The purpose of exit is to  terminate the current program with a specific exit code. Its prototype is:

void exit (int exitcode);

The exitcode is used by some operating systems and may be used by calling programs. By convention, an exit code of 0means that the program finished normally and any other value means that some error or unexpected results happened.

---

4.Iteration Based on Data Structure

A general data-based iteration statement uses a user-defined data structure and a user-defined function (the iterator) to go through the structure’s elements. The iterator is called at the beginning of each iteration, and each time it is called, the iterator returns an element from a particular data structure in some specific order. For example, suppose a program has a user-defined binary tree of data nodes, and the data in each node must be processed in some particular order. A user-defined iteration statement for the tree would successively set the loop variable to point to the nodes in the tree, one for each iteration. The initial execution of the user defined iteration statement needs to issue a special call to the iterator to get the first tree element. The iterator must always remember which node it presented last so that it visits all nodes without visiting any node more than once. So, an iterator must be history sensitive. A user-defined iteration statement terminates when the iterator fails to find more elements.

A. Expression Statements

A combination of variables, constants and operators that represents a computation forms an expression. Depending upon the type of operands involved in an expression or the result obtained after evaluating expression, there are different categories of an expression. These categories of an expression are discussed here.

• Constant expressions: The expressions that comprise only constant values are called constant expressions. Some examples of constant expressions are 20, ‘ a‘ and 2/5+30 .
• Integral expressions: The expressions that produce an integer value as output after performing all types of conversions are called integral expressions. For example, x, 6*x-y and 10 +int (5.0) are integral expressions. Here, x and yare variables of type into.
• Float expressions: The expressions that produce floating-point value as output after performing all types of conversions are called float expressions. For example, 9.25, x-y and 9+ float (7) are float expressions. Here, x ‘and yare variables of type float.
• Relational or Boolean expressions: The expressions that produce a bool type value, that is, either true or false are called relational or Boolean expressions. For example, x + y<100, m + n==a-b and a>=b + c .are relational expressions.
• Logical expressions: The expressions that produce a bool type value after combining two or more relational expressions are called logical expressions. For example, x==5 &&m==5 and y>x I I m<=n are logical expressions.
• Bitwise expressions: The expressions which manipulate data at bit level are called bitwise expressions. For example, a >> 4 and b<< 2 are bitwise expressions.
• Pointer expressions: The expressions that give address values as output are called pointer For example, &x, ptr and -ptr are pointer expressions. Here, x is a variable of any type and ptr is a pointer.
• Special assignment expressions: An expression can be categorized further depending upon the way the values are assigned to the variables.
• Chained assignment: Chained assignment is an assignment expression in which the same value is assigned to more than one variable, using a single statement. For example, consider these statements.

 a = (b=20); or a=b=20;

In these statements, value 20 is assigned to variable b and then to variable a. Note that variables cannot be initialized at the time of declaration using chained assignment. For example, consider these statements.

int a=b=30; // illegal

int a=30, int b=30; //valid

• Embedded assignment: Embedded assignment is an assignment expression, which is enclosed within another assignment expression. For example, consider this statement

a=20+(b=30);   //equivalent to b=30;

a=20+30;

In this statement, the value 30 is assigned to variable b and then the result of (20+ 30) that is, 50 is assigned to variable a. Note that the expression (b=30) is an embedded assignment.

• Compound Assignment: Compound Assignment is an assignment expression, which uses a compound assignment operator that is a combination of the assignment operator with a binary arithmetic operator. For example, consider this statement.

a + =20; //equivalent to a=a+20;

In this statement, the operator += is a compound assignment operator, also known as short-hand assignment operator.

---

 

B. Type Conversion

An expression· may involve variables and constants either of same data type or of different data types. However, when an expression consists of mixed data types then they are converted to the same type while evaluation, to avoid compatibility issues. This is accomplished by type conversion, which is defined as the process of converting one predefined data type into another. Type conversions are of two types, namely, implicit conversions and explicit conversions also known as typecasting.

 1. Implicit Conversions

Implicit conversion, also known as automatic type conversion refers to the type conversion that is automatically performed by the compiler. Whenever compiler confronts a mixed type expression, first of all char and short int values are converted to int. This conversion is known as integral promotion. After applying this conversion, all the other operands are converted to the type of the largest operand and the result is of the type of the largest operand. Table 3.8 illustrates the implicit conversion of data type starting from the smallest to largest data type. For example, in expression 5 + 4.25, the compiler converts the int into float as float is larger than int and then performs the addition.

 

2. Typecasting

Typecasting refers to the type conversion that is performed explicitly using type cast operator. In C++, typecasting can be performed by using two different forms which are given here.

data_type (expression) //expression in parentheses

(data_type)expression //data type in parentheses where, data_type = data type (also known as cast operator) to which the

expression is to be converted. To understand typecasting, consider this example.

         float (num)+ 3.5; //num is of int type

In this example, float () acts as a conversion function which converts int to float. However, this form of conversion cannot be used in some situations. For example, consider this statement. ptr=int * (x) ;

In such cases, conversion can be done using the second form of typecasting (which is basically C-style typecasting) as shown here.

         ptr=(int*)x;

C. Assignment Statement in C++

It is essential that every variable in a program is given a value explicitly before any attempt is made to use it. It is also very important that the value assigned is of the correct type.The most common form of statement in a program uses the assignment operator, =, and either an expression or a constant to assign a value to a variable:

                                 variable = expression;

                                 variable = constant;

The symbol of the assignment operator looks like the mathematical equality operator but in C++ its meaning is different. The assignment statement indicates that the value given by the expression on the right hand side of the assignment operator (symbol =) must be stored in the variable named on the left hand side. The assignment operator should be read as “becomes equal to” and means that the variable on the left hand side has its value changed to the value of the expression on the right hand side. For the assignment to work successfully, the type of the variable on the left hand side should be the same as the type returned by the expression.

The statement in line 10 of the simple adder program is an example of an assignment statement involving an arithmetic expression.  total = a + b;

It takes the values of a and b, sums them together and assigns the result to the variable total. As discussed above, variables can be thought of as named boxes into which values can be stored. Whenever the name of a box (i.e. a variable) appears in an expression, it represents the value currently stored in that box. When an assignment statement is executed, a new value is dropped into the box, replacing the old one. Thus, line 10 of the program means “get the value stored in the box named a, add it to the value stored in the box named b and store the result in the box named total”.

The assignment statement:

total = total + 5;

is thus a valid statement since the new value of total becomes the old value of total with 5 added to it. Remember the assignment operator (=) is not the same as the equality operator in mathematics (represented in C++ by the operator ==).

---

 

Arithmetic expressions

Expressions can be constructed out of variables, constants, operators and brackets. The commonly used mathematical or arithmetic operators include:

Operator	Operation
+	addition
–	subtraction
*	multiplication
/	division
%	modulus (modulo division)

The definitions of the first four operators are as expected. The modulo division (modulus) operation with an integer is the remainder after division, e.g. 13 modulus 4 (13%4) gives the result 1. Obviously it makes no sense at all to use this operator with float variables and the compiler will issue a warning message if you attempt to do so.

Although addition, subtraction and multiplication are the same for both integers and reals (floating point numbers), division is different. If you write (see later for declaration and initialization of variables on the same line):

float a=13.0, b=4.0, result;
result = a/b;

Then a real division is performed and 3.25 is assigned to result. A different result would have been obtained if the variables had been defined as integers:

int i=13,j=4, result;
result = i/j;

when result is assigned the integer value 3.

The remainder after integer division can be determined by the modulo division (modulus) operator, %. For example, the value of i%j would be 1.

---

 

Precedence and nesting parentheses

The use of parentheses (brackets) is advisable to ensure the correct evaluation of complex expressions. Here are some examples:

4+2*3	equals 10
(4+2)*3	equals 18
-3 * 4	equals -12
4 * -3	equals -12 (but should be avoided)
4 * (-3)	equals -12
0.5(a+b)	illegal (missing multiplication operator)
(a+b) / 2	equals the average value of a and b only if they are of type float

The order of execution of mathematical operations is governed by rules of precedence. These are similar to those of algebraic expressions. Parentheses are always evaluated first, followed by multiplication, division and modulus operations. Addition and subtraction are last. The best thing, however, is to use parentheses (brackets) instead of trying to remember the rules.

---

Initialization of variables

Variables can be assigned values when they are first defined (called initialization):

type	variable = literal constant;
float	ratio = 0.8660254;
int	myAge = 19;
char	answer = ‘y’;
bool	raining = false;

The terms on the right hand side are called constants.

(Note the ASCII character set is represented by type char. Each character constant is specified by enclosing it between single quotes (to distinguish it from a variable name). Each char variable can only be assigned a single character. These are stored as numeric codes. The initialisation of words and character strings will be discussed later in the section on advanced topics.)

The declaration of a variable and the assignment of its value in the same statement can be used to define variables as they are needed in the program.

 type     variable = expression;

float   product = factor1*factor2;

The variables in the expression on the right hand side must of course have already been declared and had values assigned to them.

Warning: When declaring and initialising variables in the middle of a program, the variable exists (i.e. memory is assigned to store values of the variable) up to the first right brace that is encountered, excluding any intermediate nested braces, { }. For the simple programs described here, this will usually be the closing brace mark of the program. However we will see later that brace marks can be introduced in many parts of the program to make compound statements.

---

 

Expressions with mixed variable types

At a low level, a computer is not able to perform an arithmetic operation on two different data types of data. In general, only variables and constants of the same type, should be combined in an expression. The compiler has strict type checking rules to check for this.

In cases where mixed numeric types appear in an expression, the compiler replaces all variables with copies of the highest precision type. It promotes them so that in an expression with integers and float variables, the integer is automatically converted to the equivalent floating point number for the purpose of the calculation only. The value of the integer is not changed in memory. Hence, the following is legal:

int i=13;
float x=1.5;
x = (x * i) + 23;

since the values of i and 23 are automatically converted to floating point numbers and the result is assigned to the float variable x.

However the expression:

int i=13,j=4;

float result;

result = i/j;

is evaluated by integer division and therefore produces the incorrect assignment of 3.0 for the value of result. You should try and avoid expressions of this type but occasionally you will need to compute a fraction from integer numbers. In these cases the compiler needs to be told specifically to convert the variables on the right-hand side of the assignment operator to type float. This is done by casting.

In the C++ language this is done by using the construction: static_cast< type > expression (In the C language this is done by a different construction using: (type) expression.) For example:

int count=3, N=100;
float fraction;
fraction  = static_cast<float>(count)/N;

converts (casts) the value stored in the integer variable count into a floating point number, 3.0. The integer N is then promoted into a floating point number to give a floating point result.

---

 

Declaration and initialisation of symbolic constants

Like variables, symbolic constants have types and names. A constant is declared and initialized in a similar way to variables but with a specific instruction to the compiler that the value cannot be changed by the program. The values of constants must always be assigned when they are created.

const   type      constant-name = literal constant;

const   float    Pi = 3.14159265;  const   int      MAX = 10000;

The use of constants helps programmers avoid inadvertent alterations of information that should never be changed. The use of appropriate constant names instead of using the numbers also helps to make programs more readable.

Data Types

Data types in any of the language means that what are the various type of data the variables can have in that particular language. Information is stored in a computer memory with different data types. Whenever a variable is declared it becomes necessary to define data type that what will be the type of data that variable can hold.

There are two data types available in C++:

1. Primary Data Type character, integer, floating point, boolean, double floating point, void, wide character.
2. Additional Data Types typedef, enumerated.

---

Character Data Types

Data Type (Keywords)	Description	Size	Typical Range
char	Any single character. It may include a letter, a digit, a punctuation mark, or a space.	1 byte	-128 to 127 or 0 to 255
signed char	Signed character.	1 byte	-128 to 127
unsigned char	Unsigned character.	1 byte	0 to 255
wchar_t	Wide character.	2 or 4 bytes	1 wide character

---

Integer Data Types

Data Type (Keywords)	Description	Size	Typical Range
int	Integer.	4 bytes	-2147483648 to 2147483647
signed int	Signed integer. Values may be negative, positive, or zero.	4 bytes	-2147483648 to 2147483647
unsigned int	Unsigned integer. Values are always positive or zero. Never negative.	4 bytes	0 to 4294967295
short	Short integer.	2 bytes	-32768 to 32767
signed short	Signed short integer. Values may be negative, positive, or zero.	2 bytes	-32768 to 32767
unsigned short	Unsigned short integer. Values are always positive or zero. Never negative.	2 bytes	0 to 65535
long	Long integer.	4 bytes	-2147483648 to 2147483647
signed long	Signed long integer. Values may be negative, positive, or zero.	4 bytes	-2147483648 to 2147483647
unsigned long	Unsigned long integer. Values are always positive or zero. Never negative.	4 bytes	0 to 4294967295

---

Floating-point Data Types

Data Type (Keywords)	Description	Size	Typical Range
float	Floating point number. There is no fixed number of digits before or after the decimal point.	4 bytes	+/- 3.4e +/- 38 (~7 digits)
double	Double precision floating point number. More accurate compared to float.	8 bytes	+/- 1.7e +/- 308 (~15 digits)
long double	Long double precision floating point number.	8 bytes	+/- 1.7e +/- 308 (~15 digits)

---

Boolean Data Type

Data Type (Keywords)	Description	Size	Typical Range
bool	Boolean value. It can only take one of two values: true or false.	1 byte	true or false

---

Note: Variables sizes might be different in your pc from those shown in the above table, depending on the compiler you are using.

• Enum Data Type

This is an user defined data type having finite set of enumeration constants. The keyword ‘enum‘ is used to create enumerated data type.

Syntax:

enum enum-name {list of names} var-list;

enum mca(software, internet, seo);

• Typedef

It is used to create new data type. But it is commonly used to change existing data type with another name.

Syntax:

typedef [data_type] synonym;

or

typedef [data_type] new_data_type; 

Example:

typedef int integer;

integer rollno;