Generic Programming

GENERIC PROGRAMMING

In the simplest definition, generic programming is a style of computer programming in which algorithms are written in terms of types to-be-specified-later that are then instantiated when needed for specific types provided as parameters. This approach, pioneered by ML in 1973, permits writing common functions or types that differ only in the set of types on which they operate when used, thus reducing duplication. Such software entities are known as generics in Ada, Delphi, Eiffel, Java, C#, F#, Swift, and Visual Basic .NET; parametric polymorphism in ML, Scala and Haskell (the Haskell community also uses the term "generic" for a related but somewhat different concept); templates in C++ and D; and parameterized types in the influential 1994 book Design Patterns. The authors of Design Patterns note that this technique, especially when combined with delegation, is very powerful but that "[dynamic], highly parameterized software is harder to understand than more static software."

•        Define software components with type parameters

–   A sorting algorithm has the same structure, regardless of the types being sorted

–   Stack primitives have the same semantics, regardless of the

–   objects stored on the stack.

•        Most common use: algorithms on containers: updating, iteration, search

•        C model: macros (textual substitution)

•        Ada model: generic units and instantiations

•        C++ model: templates

•        Construct    parameter   supplying parameter

1. Type parameter

•         The generic type declaration specifies the class of types for which an instance of the generic will work:

•        type T is private;  --       any type with assignment (Non-limited)

•        type T is limited private;         --       any type (no required operations)

•        type T is range <>;        --       any integer type (arithmetic operations)

•        type T is (<>);      --  any discrete type (enumeration or

•                  --       integer)

•        type T is digits <>;        --       any floating-point type

•        type T is delta <>;         --       any fixed-point type

•        Within the generic, the operations that apply to any type of the class can be used.

•        The instantiation must use a specific type of the class

2. A generic function

generic

type T is range <>;              -- parameter of some integer type

type Arr is array (Integer range <>) of T;

-- parameter is array of those

function Sum_Array (A : Arr) return T;

-- Body identical to non-generic version function Sum_array (A : Arr) return T is

Result : T := 0;     --       some integer type, so literal 0 is legal

begin          

for J in A’range loop     --       some array type, so attribute is available

Result := Result + A (J);          --       some integer type, so “+” available.

end loop;             

return Result;                

end;            

Instantiating a generic function                  

type Apple is range 1 .. 2 **15 - 1;

type Production is array (1..12) of Apple; type Sick_Days is range 1..5;

type Absences is array (1 .. 52) of Sick_Days;

function Get_Crop is new Sum_array (Apple, Production); function Lost_Work is new Sum_array (Sick_Days, Absences);

generic private types

•          Only available operations are assignment and equality.

generic

type T is private;

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

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

Temp :  constant T := X;

begin

X := Y;

Y := Temp;

end Swap;

3. Subprogram parameters

• A generic sorting routine should apply to any array whose components are comparable, i.e. for which an ordering predicate exists. This class includes more that the numeric types:

generic

type T is private;                           -- parameter

with function “<“ (X, Y : T) return Boolean; -- parameter

type Arr is array (Integer range <>) of T; -- parameter

procedure Sort (A : in out Arr);

Supplying subprogram parameters

•     The actual must have a matching signature, not necessarily the same name:

procedure Sort_Up         is new Sort (Integer, “<“, …);

procedure Sort_Down is new Sort (Integer, “>”, … );

type Employee is record .. end record;

function Senior (E1, E2 : Employee) return Boolean;

function Rank is new Sort (Employee, Senior, …);

Value parameters

Useful to parametrize containers by size:

generic

type Elem is private;        -- type parameter

Size : Positive;                   -- value parameter

package Queues is

type Queue is private;

procedure Enqueue (X : Elem; On : in out Queue); procedure Dequeue (X : out Elem; From : in out Queue); function Full (Q : Queue) return Boolean;

function Empty (Q : Queue) return Boolean; private

type Contents is array (Natural range <>) of Elem; type Queue is record

Front, Back: Natural; C : Contents (0 .. Size);

end record; end Queues