CSC/ECE 517 Fall 2011/ch6 6c p: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
(Created page with "<p style="font-size: 24px">'''Generics'''</p> =='''Introduction'''== In a broad definition, generic programming is a style of computer programming in which algorithms are writ...")
 
No edit summary
Line 1: Line 1:
<p style="font-size: 24px">'''Generics'''</p>
<p style="font-size: 24px">'''Generics'''</p>


=='''Introduction'''==
=='''Introduction'''==
Line 7: Line 6:


=====Why Generics?=====
=====Why Generics?=====
This approach involves writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication.
This approach involves writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication.


Line 14: Line 12:
=====Problems with code duplication=====
=====Problems with code duplication=====


====Unit====
====Avoiding bulk code====
A unit is the building block of a code. It can be a class, typically individual methods or lines within methods, an interface etc.
Code duplication frequently creates long, repeated sections of code that differ in only a few lines or characters. The length of such routines can make it difficult to quickly understand them. Hence, code duplication is discouraged.
 
====What does Unit Testing mean?====
[http://expertiza.csc.ncsu.edu/wiki/index.php/CSC/ECE_517_Fall_2010/ch1_1f_vn Unit testing] is the process of testing a code by focusing on a small chunk (unit) of code at a time, checking whether it functions properly, to give the desired results.
 
====Why Unit Testing?====
 
=====Benefits of Unit Testing:=====
 
 Fast – It gives instant feedback on the accuracy of your code.
 
 Design – For testing, the code is designed as small modules facilitating the reusability of the units.
 
 Individuality – Each unit is designed independent of each other and tested individually making error identification easy.
 
 Efficiency - Bugs can be scanned in the probable bug prone code areas making debugging efficient.
 
 Understanding – Helps any reader, easily understand the methods’ functionality.
 
=====Limitations of Unit Testing:=====
 
 Tedious Job for Complex Codes – Implementing and running test cases for complex codes is time consuming. Moreover, coding a unit test is as tedious as coding the target program itself.
 
 Impact of Change in the Code Requirements - In an agile project that is accompanied with periodic changes in requirements will result in constant updating of test cases to match the latest developments.
 
 
=='''Testing Techniques'''==
 
====Test-Driven Development(TDD)====
[http://en.wikipedia.org/wiki/Test-driven_development Test Driven Development (TDD)]is an advanced technique of using automated unit tests to drive the design of software. The result of using this practice is a comprehensive suite of unit tests that can be run at any time to keep track of the code development.  
 
Here
 Test cases are written initially keeping in mind the final result.
 
The initial test is conducted which eventually fails because of absence of a target code.
 
 The test suggests further steps to build/refactor an error free code and only those programs associated with the tests go into production.
 
 Tests are then re-conducted until satisfactory results are achieved.
 
[[File:TDD development cycle.png|thumb|400px|center|Development Cycle of TDD]]
 
====Behavior driven development (BDD)====
 
[http://en.wikipedia.org/wiki/Behavior_Driven_Development Behavior driven development (BDD)]is a software development technique that relies on the use of simple vocabulary. Tests are designed using natural language so that even a non-technical participant will be able to follow. BDD is an evolution in the thinking behind Test Driven Development but stresses extensively on the behavior aspect of the methods used in the code.
 
 
Eg: Tests result such as “the point cannot be created without code description” is more understandable than something like Test_category_ThrowsArgumentNullException .
 
 
=='''Frameworks'''==
 
A framework is a tool to support writing and running of a program. A Unit Test framework is a set of reusable libraries or classes for a software system. Code is written in these frameworks, they are capable of running and checking the test code by themselves.
 
Here, a unit test framework will evaluate the code based on a variety of inputs provided in the test case and check for the accuracy of results.
 
====Testing Framework Parlance:====
 
a. '''Test Case:'''  It is a main class where test methods are coded. All the units to be tested are inherited to this class.
 
 
b. [http://ruby-doc.org/stdlib/libdoc/test/unit/rdoc/classes/Test/Unit/Assertions.html '''Assertions (Test::Unit::Assertions):''']  An assertion is the main condition that when held true would result in successful culmination of the test. If the assertion fails then the test would generate an error message with pertinent information so that the programmer can make necessary changes.
 
 
c. '''Test Fixture:'''  A test fixture is used to clean up methods for conducting more than one test, eliminating duplication of methods.
 
 
d. '''Test Method:'''  It is a process to handle individual units referred for testing.
 
 
e. '''Test Runners:'''  Test Runners GUI’s that are used to conduct testing and provide with the results. Test runners such as Test::Unit::UI::Console::Test Runner and GTK test runners are used.
 
 
f. '''Test Suite:'''    It is a collection of tests.
 
 
 
We need a target code to conduct tests.
 
====Example Problem Statement for Target Code:====
To find whether a given point lies on the x-axis, y-axis or the origin.
 
Solution:  We write a class to define the position (x-axis, y-axis or origin) of the point.
 
====Code : Position of a Point====
class Point
attr_writer :xcoordinate
attr_writer :ycoordinate
def initialize(xcoordinate,ycoordinate)
  @xcoordinate = xcoordinate
  @ycoordinate = ycoordinate
end
#-----------Location of point on X-axis ----------------#
def isOnXaxis?
    if @ycoordinate == 0
    return true 
  end
end
#---------- Location of point on Y-axis ----------------#
  def isOnYaxis?
    if @xcoordinate == 0
      return true
  end
  end
#---------- Location of point on Origin-----------------#
  def isOnOrigin?
    if @xcoordinate == 0 && @ycoordinate == 0
    return true
  end
  end
end
 
=='''Testing Frameworks'''==
 
====Test::Unit====
 
=====Overview=====
 
a. It is based on the Test Driven Development Technique (TDD).
 
b. The Test::Unit framework integrates the following features:
1. Way of expressing individual tests.
 
2. Provides a framework for structuring the tests.
 
3. Has flexible ways of invoking the tests.
 
=====Process of Testing=====
 
=====a. Installation=====
 
Test::Unit framework is pre-installed on all Ruby versions.
 
=====b. Algorithm=====
 
 We use a UI is used to run the Test code and display the gathered results. Here, we have used the web based UI.
 
 Structuring the tests: Inherit the required classes.
 
a. Here, “point” class is inherited to call the target units which have to be tested.
 
b. The “test/unit” class is inherited for methods required to conduct testing.
 
 Write the test methods.
 
 Test methods are prefixed with test. Eg: test_examp where examp is the unit being tested.
 
 In the methods write Assertions comparing them with expected results for the target units.
 
 Text fixtures are optional; they can be used to clean the methods.
 
 Run the tests as Test::Unit test class name.rb
 
 To run only a particular method we can its name as classname.rb --name method
 
 If there are bugs, refactor the code.
 
 Repeat testing until all the bugs are fixed.
 
=====Flowchart=====
[[File:Test unit flowchart.png|thumb|400px|center|Development Cycle of TDD]]
 
=====CODE Test::Unit=====
require "Point"
require "test/unit"
class TestCase_Point < Test::Unit::TestCase
  def test_isOnXaxis
    assert(Point.new(3,0).isOnXaxis?)
    end
  def test_isOnYaxis
      assert(Point.new(0,4).isOnYaxis?)
  end
  def test_isOnOrigin
      assert(Point.new(3,4).isOnOrigin?)
  end
end
 
=====Result Test::Unit=====
Below are the test results that are obtained after running the above test cases.
 
=====Failed output=====
This is how the failed test cases are shown once we run the test cases,
[[File:Testunit failed.png|center|700px|center|Development Cycle of TTD]]
 
=====Passed output=====
[[File:Testunit passed.png|center|800px|center|Development Cycle of TTD]]
 
=====Storing Test Files=====
Test files can be stored in the same directory as the target file but eventually the directory gets bloated storing 2 files for the same target code. Instead we can store it in a separate test directory for better organization. Here, one must take care to clearly specify the path of the target code for inheritance purpose in the test file.
 
Eg: If point.rb is stored in the directory lib and test_point.rb is stored in the test directory then to inherit point.rb we specify the path.
require “../lib/point”
----
 
 
====Shoulda====


=====Overview=====
====Purpose masking====
The repetition of largely identical code sections makes it difficult to identify how they differ from one another, and therefore, identifying the specific purpose of each code section. Often, the only difference is in a parameter value. The best practice in such cases is a reusable subroutine. If the parameter type differs then it is called a generic case.


a. Shoulda is a library that allows us to write better and easily understandable test cases for the ruby applications compared to Test::Unit.
====Update anomalies====
Any modification to a redundant piece of code must be made for each duplicate separately which is very tedious.  At worst, some locations may be missed, and for example bugs thought to be fixed may persist in duplicated locations for months or years. The best practice here is a code library.


b. It allows us to use the "it"-blocks from RSpec to define nice error-messages if a test fails.  
The generics approach was popularized by Ada - programming language.
Code set written using generic programming are known as generics. They are used in programming languages like Ada, Java, C++ and Visual Basic .NET. Generics create dynamically high parameterized software which can be difficult to follow.


c. In other words it is improvised form of Test::Unit and Rspec. It works inside the Test::Unit — you can even mix Shoulda tests with regular Test::Unit test methods.
The term generic programming was originally coined by David Musser and Alexander Stepanov.


=====Process of Testing=====
=====Popular Example of Generics=====
Early examples of this programming approach were implemented in Ada, although the best example is the  [http://en.wikipedia.org/wiki/Standard_Template_Library Standard Template Library (STL)] in which iterators are used to access different values of an algorithm and provide them with varying datatype inputs.


====The Standard Template Library (STL)====
It is the C++'s Standard software library. It provides four components such algorithms, containers, functors, and iterators. We are mainly concerned with the algorithm and iterators.  Here, as mentioned above algorithms are accessed with iterators where the values provided through iterators and make the algorithm work with different data types having same functionality.


=====a. Installation=====
The STL provides a ready-made set of common classes for C++, such as containers and associative arrays, that can be used with any built-in type and with any user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library.


Shoulda is installed by running “gem install shoulda” in command prompt after setting the environment path as “…\Ruby\bin”
=='''Understanding Generics'''==
Let us consider an example in STI.  A sequence of data structures, e.g. a vector etc., and some algorithms to operate on them, e.g. find, sort etc., a direct approach would implement each algorithm specifically for each data structure which would be highly impossible.
In the generic programming approach, each data structure returns a model of an iterator concept (a simple value type which can be dereferenced to retrieve the current value, or changed to point to another value in the sequence) and each algorithm is instead written generically with arguments of such iterators. Thus, reducing the data structure-algorithm combinations need be implemented and extensive reusability.


=====b. Algorithm=====
Iterators are of different types for e.g. forward iterators only provide movement to the next value in a sequence (e.g. suitable for a singly linked list), whereas a random-access iterator also provides direct constant-time access to any element of the sequence (e.g. suitable for a vector). An important point is that a data structure will return a model of the most general concept that can be implemented efficiently—computational complexity requirements are explicitly part of the concept definition.  


 Inherit all the classes involved in testing i.e. the target class and the shoulda library class. To achieve this add require "rubygems", require ”Point” and require "shoulda" to the test class.
Here, Arrays and Structs can be viewed as predefined generic types. Every usage of an array or struct type instantiates a new concrete type, or reuses a previous instantiated type. Array element types and struct element types are parameterized types, which are used instantiate the corresponding generic type. All this is usually built-in in the compiler and the syntax differs from other generic constructs.


 Then setup up a context “Point” (context is nothing but a region of code which deals with the functionality you are interested in.)
=='''Generics in Object Oriented Programming Languages'''==
Generic programming first appeared in Ada and was subsequently adopted by many object-oriented languages. Implementation in languages such as Java and C++ are formally based on the notion of parametricity.


 Then define a method starting with should “method name” do and then describe the entire method.
=====Generics=====
Define Common Block
{ Code statements
}


 Make proper assertions to test the functionality in your method.
Main Program
{ Call Common Block  // For different data types and values.
}


=====Code shoulda=====
=====Example of generic programming[http://www.boost.org/community/generic_programming.html [1]]=====
require "rubygems"
Let us consider the memcpy() function to copy a set of array values and then generalize it using generics approach.
require “Point”
require "test/unit"
require "shoulda"
class TestCase_Point_Shoulda < Test::Unit::TestCase
  context "Point" do
  should "lie on the X-axis " do
      assert(Point.new(3,0).isOnXaxis?)
  end
  should "lie on the Y-axis " do
      assert(Point.new(0,4).isOnYaxis?)
  end
  should "lie on the Origin" do
    assert(Point.new(0,4).isOnOrigin?)
  end
  end
end


=====Result=====
void* memcpy(void* region1, const void* region2, size_t n)
Below are the test results that are obtained after running the above test cases,
{
  const char* first = (const char*)region2;
  const char* last = ((const char*)region2) + n;
  char* result = (char*)region1;
  while (first != last)
    *result++ = *first++;
  return result;
}


=====Failed Output=====
The memcpy() function is used to copy arrays of different kinds of data. Now considering the case were the data we would like to copy is not in an array? Perhaps it is in a linked list. We can generalize a copy function to any sequence of elements? Looking at the body of memcpy(), the function's minimal requirements are that it needs to traverse through a sequence using pointer to access elements, write them to the destination, and compare pointers to know when to stop. The C++ standard library groups requirements such as these into concepts, in this case the Input Iterator concept (for region2) and the Output Iterator concept (for region1).
[[File:Shoulda failed.png|center|800px|center|Development Cycle of TTD]]


=====Passed output=====
=====Generic approach code=====
[[File:Shoulda passed.png|center|600px|center|Development Cycle of TTD]]
template <typename InputIterator, typename OutputIterator>
----
OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
  while (first != last)
    *result++ = *first++;
  return result;
}


Using the above generic copy() function, we can now copy elements from any kind of sequence, including a linked list that exports iterators such as std::list.


====RSpec====
#include <list>
#include <vector>
#include <iostream>


=====Overview=====
int main()
a. RSpec is Behavior Driven Development Unit test tool for ruby.
{
  const int N = 3;
  std::vector<int> region1(N);
  std::list<int> region2;


b. It allows us to write an initial code specifications (spec) document. The spec document talks about the program’s function.
  region2.push_back(1);
  region2.push_back(0);
  region2.push_back(3);
 
  std::copy(region2.begin(), region2.end(), region1.begin());


c. Thereby, we can write the code based on the specifications (spec file).
  for (int i = 0; i < N; ++i)
    std::cout << region1[i] << " ";
  std::cout << std::endl;
}


d. The (spec) document is written in Domain Specific Language which makes it simple for the programmer to handle.  
=====Generics in ADA=====
In a generic a parameter is a value, a variable, a constant, a type, a subprogram, or even an instance of another, designated, generic unit that is used in the generic routine. For generic formal types, the syntax distinguishes between discrete, floating-point, fixed-point, access (pointer) types, etc. Some formal parameters can have default values.


e. Better understanding of the test cases compared to shoulda as the cases and notifications are more descriptive.  
To instantiate a generic unit, the programmer passes actual parameters for each formal. The generic instance then behaves just like any other unit. It is possible to instantiate generic units at run-time, for example inside a loop.  


f. In other words it is improvised form of Test::Unit and Rspec. It works inside the Test::Unit — you can even mix Shoulda tests with regular Test::Unit test methods.
One of the ways in which the Ada language supports this characteristic is by means of generic units.  


=====Process of Testing=====
The generic here uses a package which contains a general operation to be performed.


=====a. Installation=====
====The specification of a generic package[http://en.wikibooks.org/wiki/Ada_Programming/Generics [2]]====
RSpec is installed by running “gem install rspec” in command prompt after setti ng the environment path as “…\Ruby\bin”
generic
  type Element_T is private;  -- Generic formal type parameter
procedure Swap (X, Y : in out Element_T);


=====b. Algorithm=====
procedure Swap (X, Y : in out Element_T) is
  Temporary : constant Element_T := X;
begin
  X := Y;
  Y := Temporary;
end Swap;


 We start by describing what our application behaves like. So we write down a specifications file.
The Swap subprogram is said to be generic. The subprogram specification is preceded by the generic formal part consisting of the reserved word generic followed by a list of generic formal parameters which may be empty. The entities declared as generic are not directly usable, it is necessary to instantiate them.


 Using RSpec's “describe” block we describe the basic functions of the application.
To use the generic we instantiate by
procedure Instance_Swap is new Swap (Float);
procedure Instance_Swap is new Swap (Integer);
procedure Instance_Swap is new Swap (Element_T => Stack_T);


 We then write the behaviors/expectations defining what we expect our system to behave like (expectations are similar to assertions in Test::Unit framework).
Here, the parameters passed have different data types making the generic widely usable.


 There are two methods available for checking expectations: should() and should_not(). Spec::Expectations - Object#should(matcher) and Object#should_not(matcher).
====A generic using a sub program====
It is possible to pass a subprogram as a parameter to a generic. The generic specifies a generic formal subprogram, complete with parameter list and return type (if the subprogram is a function). The actual must match this parameter profile. It is not necessary that the names of parameters match, though.


 The code returns list of all the methods to be implemented.
generic
  type Element_T is private;
  with function "*" (X, Y: Element_T) return Element_T;
function Square (X : Element_T) return Element_T;


 Main code implementing all the specified methods is written.


 Then, a recheck is done for fulfillment of all the expectations.
Function description


=====Code RSpec=====
function Square (X: Element_T) return Element_T is
begin
  return X * X;  -- The formal operator "*".
end Square;


======Initial Requirement(spec)======


In the below code describe() method returns an ExampleGroup class(similar to TestCase in Test::Unit).
Usage of the generic
The it()method returns an instance of the ExampleGroup in which that example is run.
with Square;
with Matrices;
procedure Matrix_Example is
  function Square_Matrix is new Square
    (Element_T => Matrices.Matrix_T, "*" => Matrices.Product);
  A : Matrices.Matrix_T := Matrices.Identity;
begin
  A := Square_Matrix (A);
end Matrix_Example;


require "Point"
To instantiate a generic unit, use the keyword new
describe "The location of a point" do
  it "should check whether point lies on X-axis correctly"                       
  it " should check whether point lies on Y-axis correctly "
  it " should check whether point lies on Origin correctly "
end


The are two methods available to check the expectations and they are should and should_not.
function Square_Matrix is new Square
The result obtained by running the initial requirement doc by using $ spec rspec_test.rb is
  (Element_T => Matrices.Matrix_T, "*" => Matrices.Product);
****
Pending:
The location of a point should check whether point lies on X-axis correctly (Not Yet Implemented)
./02file.rb:2
The location of a point should check whether point lies on Y-axis correctly (Not Yet Implemented)
./02file.rb:3
The location of a point should check whether point lies on Origin correctly (Not Yet Implemented)
./02file.rb:5
Finished in 0.021001 seconds
4 examples, 0 failures, 4 pending
Hence it clearly says that the above methods are yet to be implemented. This helps us in developing the code more efficiently such that they pass the above tests
Code block with expectations :


require “Point”
====Advantages====
require "rubygems"
The language syntax allows precise specification of constraints on generic formal parameters. For example, it is possible to specify that a generic formal type will only accept a modular type as the actual. It is also possible to express constraints between generic formal parameters; for example:
describe "The location of a point" do
  before(:each) do
    @point = Point.new(0,2)
  end
  it "should check whether point lies on X-axis correctly" do
    @point.isOnXaxis?.should be_true
  end
  it "should check whether point lies on Y-axis correctly" do
    @point.isOnYaxis?.should be_true
  end
  it "should check whether point lies Origin correctly" do
    @point.isOnOrigin?.should be_true
  end
end


=====Failed output=====
generic
Below are the test results that are obtained after running the above test cases,
    type Index_Type is (<>); -- must be a discrete type
[[File:Rspec failed.png|center|600px|center|Development Cycle of TTD]]
    type Element_Type is private; -- can be any nonlimited type
----
    type Array_Type is array (Index_Type range <>) of Element_Type;


In this example, Array_Type is constrained by both Index_Type and Element_Type. When instantiating the unit, the programmer must pass an actual array type that satisfies these constraints.


====Cucumber====
All instances of a generic being exactly the same, it is easier to review and understand programs written by others; there are no "special cases" to take into account.


Cucumber is becoming highly popular because of its easy coding features.
====Limitations====
Ada does not allow specialized generic instances, unlike C++ and requires that all generics be instantiated explicitly but all instantiations being explicit, there are no hidden instantiations that might make it difficult to understand the program.


=====Overview=====
Ada does not permit "template metaprogramming", because it does not allow specializations.


a. Cucumber is a Behavior Driven Development Unit test tool for ruby.


b. It follows a similar pattern of RSPEC with some added features.


c. It allows the behavior of a system to be written in the native language of the programmer as either specs or functional tests.


d. It implements the GWT (Given, When, Then) pattern. Given is a behavior, accordingly coding is done. When all the specifications are met, then the tests are deemed successful.


e. Cucumber itself is written in Ruby.


=====Process of Testing=====


=====a. Installation=====
If your Environment path is set to " ...\Ruby\bin" then open command prompt and run gem install cucumber.


=====b. Algorithm=====
 We first create a feature file to describe about our requirements.


 Then we will create a ruby file to give a code to implement the function.
=====Generic approach code=====
=====Generic approach code=====


 Then, a recheck is done for fulfillment of all the expectations.


=====Code Cucumber=====


The requirement(spec) file for the cucumber is given below,
Feature: Check the point location
  In order perform check
  As a user
  I want the two coordinates of a point
  Scenario: check the location on X-axis
  Given I have entered <xcoordinate>
  And  I have entered <ycoordinate>
  When  I give check
  Then  The result should be <output>


The code implementation based on the above Requirement for Cucumber is as shown below,
require “Point”
require "rubygems"
Before do
@xcoordinate=3
@ycoordinate=0
end
Given /^I have entered <input(\d+)>$/ do |arg1|
  @point = Point.new(@xcoordinate,@ycoordinate)
end
When /^I give check$/ do
  @result = @point.isOnXaxis?
end
Then /^The result should be <output>$/ do
puts @result
end
----


====RIOT====


RIOT aids in speedy execution of test cases.


=====Overview=====


a. Riot does not run a setup and teardown functions before and after each test like in case of Test::Unit.


b. This is what speeds up the test execution.


c. Tests are written differently in RIOT. We only receive a Boolean output for our test case.


c. Here, assertions are done using a generalized attribute instead of specific variables.


=====Process of Testing=====


=====a. Installation=====


This can be installed by running “gem install riot” in command prompt after setting the environment path as “…\Ruby\bin”


=====b. Algorithm=====


 We inherit all the classes that are required.


 A “Context” block is used to specify behavior of the class.


 Now, a setup block does not use specific variables but instead uses a generalized attribute “topic” to access objects in assertions.


 Assertions only return a boolean value. When using asserts, true indicates a pass while false indicates a fail.


=====Code RIOT=====
require “Point”
require "rubygems"
context "The point locater" do
  setup{Point.new(3,0)}
  asserts("Location on Xaxis") {topic.isOnXaxis?}.nil
end
----




=='''Comparision between Frameworks'''==
[[File:Comparision.jpg]]




=='''Conclusion'''==
Test::unit is the traditionally used unit testing framework as it comes by default with ruby but based on the readability of the test cases Rspec is preferred by majority.
Below is the plot showing the comparison of the times taken to execute the test cases in various unit test frameworks,


[[File:Conclusion.png|center|600px|center|Development Cycle of TTD]]


Hence we can infer from the above tabulation that riot is faster compared to majority of the unit test Frameworks


Each of the frameworks have their specific advantages and are used depending upon the situation.


==See also==
==See also==

Revision as of 19:18, 16 November 2011

Generics

Introduction

In a broad definition, generic programming is a style of computer programming in which algorithms are written in terms of to-be-specified-later types that are then instantiated when needed for specific types provided as parameters.

Why Generics?

This approach involves writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication.

Duplicate code is a computer programming term for a sequence of source code that occurs more than once, either within a program or across different programs owned or maintained by the same entity. Duplicate code is generally considered undesirable.

Problems with code duplication

Avoiding bulk code

Code duplication frequently creates long, repeated sections of code that differ in only a few lines or characters. The length of such routines can make it difficult to quickly understand them. Hence, code duplication is discouraged.

Purpose masking

The repetition of largely identical code sections makes it difficult to identify how they differ from one another, and therefore, identifying the specific purpose of each code section. Often, the only difference is in a parameter value. The best practice in such cases is a reusable subroutine. If the parameter type differs then it is called a generic case.

Update anomalies

Any modification to a redundant piece of code must be made for each duplicate separately which is very tedious. At worst, some locations may be missed, and for example bugs thought to be fixed may persist in duplicated locations for months or years. The best practice here is a code library.

The generics approach was popularized by Ada - programming language. Code set written using generic programming are known as generics. They are used in programming languages like Ada, Java, C++ and Visual Basic .NET. Generics create dynamically high parameterized software which can be difficult to follow.

The term generic programming was originally coined by David Musser and Alexander Stepanov.

Popular Example of Generics

Early examples of this programming approach were implemented in Ada, although the best example is the Standard Template Library (STL) in which iterators are used to access different values of an algorithm and provide them with varying datatype inputs.

The Standard Template Library (STL)

It is the C++'s Standard software library. It provides four components such algorithms, containers, functors, and iterators. We are mainly concerned with the algorithm and iterators. Here, as mentioned above algorithms are accessed with iterators where the values provided through iterators and make the algorithm work with different data types having same functionality.

The STL provides a ready-made set of common classes for C++, such as containers and associative arrays, that can be used with any built-in type and with any user-defined type that supports some elementary operations (such as copying and assignment). STL algorithms are independent of containers, which significantly reduces the complexity of the library.

Understanding Generics

Let us consider an example in STI. A sequence of data structures, e.g. a vector etc., and some algorithms to operate on them, e.g. find, sort etc., a direct approach would implement each algorithm specifically for each data structure which would be highly impossible. In the generic programming approach, each data structure returns a model of an iterator concept (a simple value type which can be dereferenced to retrieve the current value, or changed to point to another value in the sequence) and each algorithm is instead written generically with arguments of such iterators. Thus, reducing the data structure-algorithm combinations need be implemented and extensive reusability.

Iterators are of different types for e.g. forward iterators only provide movement to the next value in a sequence (e.g. suitable for a singly linked list), whereas a random-access iterator also provides direct constant-time access to any element of the sequence (e.g. suitable for a vector). An important point is that a data structure will return a model of the most general concept that can be implemented efficiently—computational complexity requirements are explicitly part of the concept definition.

Here, Arrays and Structs can be viewed as predefined generic types. Every usage of an array or struct type instantiates a new concrete type, or reuses a previous instantiated type. Array element types and struct element types are parameterized types, which are used instantiate the corresponding generic type. All this is usually built-in in the compiler and the syntax differs from other generic constructs.

Generics in Object Oriented Programming Languages

Generic programming first appeared in Ada and was subsequently adopted by many object-oriented languages. Implementation in languages such as Java and C++ are formally based on the notion of parametricity.

Generics

Define Common Block { Code statements }

Main Program { Call Common Block // For different data types and values. }

Example of generic programming[1]

Let us consider the memcpy() function to copy a set of array values and then generalize it using generics approach.

void* memcpy(void* region1, const void* region2, size_t n) {

 const char* first = (const char*)region2;
 const char* last = ((const char*)region2) + n;
 char* result = (char*)region1;
 while (first != last)
   *result++ = *first++;
 return result;

}

The memcpy() function is used to copy arrays of different kinds of data. Now considering the case were the data we would like to copy is not in an array? Perhaps it is in a linked list. We can generalize a copy function to any sequence of elements? Looking at the body of memcpy(), the function's minimal requirements are that it needs to traverse through a sequence using pointer to access elements, write them to the destination, and compare pointers to know when to stop. The C++ standard library groups requirements such as these into concepts, in this case the Input Iterator concept (for region2) and the Output Iterator concept (for region1).

Generic approach code

template <typename InputIterator, typename OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result) {

 while (first != last)
   *result++ = *first++;
 return result;

}

Using the above generic copy() function, we can now copy elements from any kind of sequence, including a linked list that exports iterators such as std::list.

  1. include <list>
  2. include <vector>
  3. include <iostream>

int main() {

 const int N = 3;
 std::vector<int> region1(N);
 std::list<int> region2;
 region2.push_back(1);
 region2.push_back(0);
 region2.push_back(3);
 
 std::copy(region2.begin(), region2.end(), region1.begin());
 for (int i = 0; i < N; ++i)
   std::cout << region1[i] << " ";
 std::cout << std::endl;

}

Generics in ADA

In a generic a parameter is a value, a variable, a constant, a type, a subprogram, or even an instance of another, designated, generic unit that is used in the generic routine. For generic formal types, the syntax distinguishes between discrete, floating-point, fixed-point, access (pointer) types, etc. Some formal parameters can have default values.

To instantiate a generic unit, the programmer passes actual parameters for each formal. The generic instance then behaves just like any other unit. It is possible to instantiate generic units at run-time, for example inside a loop.

One of the ways in which the Ada language supports this characteristic is by means of generic units.

The generic here uses a package which contains a general operation to be performed.

The specification of a generic package[2]

generic

 type Element_T is private;  -- Generic formal type parameter

procedure Swap (X, Y : in out Element_T);

procedure Swap (X, Y : in out Element_T) is

 Temporary : constant Element_T := X;

begin

 X := Y;
 Y := Temporary;

end Swap;

The Swap subprogram is said to be generic. The subprogram specification is preceded by the generic formal part consisting of the reserved word generic followed by a list of generic formal parameters which may be empty. The entities declared as generic are not directly usable, it is necessary to instantiate them.

To use the generic we instantiate by procedure Instance_Swap is new Swap (Float); procedure Instance_Swap is new Swap (Integer); procedure Instance_Swap is new Swap (Element_T => Stack_T);

Here, the parameters passed have different data types making the generic widely usable.

A generic using a sub program

It is possible to pass a subprogram as a parameter to a generic. The generic specifies a generic formal subprogram, complete with parameter list and return type (if the subprogram is a function). The actual must match this parameter profile. It is not necessary that the names of parameters match, though.

generic

 type Element_T is private;
 with function "*" (X, Y: Element_T) return Element_T;

function Square (X : Element_T) return Element_T;


Function description

function Square (X: Element_T) return Element_T is begin

 return X * X;   -- The formal operator "*".

end Square;


Usage of the generic with Square; with Matrices; procedure Matrix_Example is

 function Square_Matrix is new Square
   (Element_T => Matrices.Matrix_T, "*" => Matrices.Product);
 A : Matrices.Matrix_T := Matrices.Identity;

begin

 A := Square_Matrix (A);

end Matrix_Example;

To instantiate a generic unit, use the keyword new

function Square_Matrix is new Square

  (Element_T => Matrices.Matrix_T, "*" => Matrices.Product);

Advantages

The language syntax allows precise specification of constraints on generic formal parameters. For example, it is possible to specify that a generic formal type will only accept a modular type as the actual. It is also possible to express constraints between generic formal parameters; for example:

generic
   type Index_Type is (<>); -- must be a discrete type
   type Element_Type is private; -- can be any nonlimited type
   type Array_Type is array (Index_Type range <>) of Element_Type;

In this example, Array_Type is constrained by both Index_Type and Element_Type. When instantiating the unit, the programmer must pass an actual array type that satisfies these constraints.

All instances of a generic being exactly the same, it is easier to review and understand programs written by others; there are no "special cases" to take into account.

Limitations

Ada does not allow specialized generic instances, unlike C++ and requires that all generics be instantiated explicitly but all instantiations being explicit, there are no hidden instantiations that might make it difficult to understand the program.

Ada does not permit "template metaprogramming", because it does not allow specializations.





Generic approach code
Generic approach code

See also

External Links:

References:

R.Venkat Rajendran, White Paper on Unit Testing

Benchmark Conclusions