Definition of Generic function

Question

1)

Below is a python function summation, that can perform sum of cubes/squares/.., similar operations.

def identity(k):
    return k

def cube(k):
    return pow(k, 3)

def square(k):
    return pow(k,2)

def summation(n, term):
    if n == 0:
        return 0
    else:
        return term(n) + summation(n-1, term)

def sum_cubes(n):
    return summation(n, cube)

if __name__ == '__main__':
    sum = sum_cubes(4)
    print(sum)

 """ In C, We can implement the same using function pointers. Goal is, to    
    perform similar operations(Sum of ..) using single function summation()"""  

---

2)

Consider, below sorting api from C,

void qsort(void *base, size_t nmemb, size_t size,
                            int (*compar)(const void *, const void *));

Here, qsort can sort data of any type, array of floats/file names in a directory/strings/...

---

Question:

How to define a Generic function?

Is summation a generic function?

or

Is qsort a generic function?

or

Given two examples, Is Generic function an invalid terminology?

Note: Motivation-To term qsort or any sort function that I design

Answer 1

There are several meanings to "generic".

Informal definition

"generic" in everyday language something that shares common properties but is less specific in some ways.

Under this perspective, you could consider qsort() as generic : the code of this function is able to sort any fixed size data structure for which you can define a comparison function by using the QSORT algorithm.

The same applies to your summation() function, which summarizes terms obtained using any functions with one parameter.

Formal definition

Programming languages like C++ or Java allow for generic programming with the use of templates or generics:

Definition from the C++14 standard: A template defines a family of classes or functions or an alias for a family of types.

The principle is that a class or a function's implementation can be parametrized by types.

According to this more formal point of view, qsort() is not a generic function. Its implementation doesn't need to determine any type at compilation, and its behavior is type independent. The only thing it needs, is the size of the elements being sorted, and this size is an ordinary argument that is processed at run-time.

For a language that is not statically typed such as Python, I'm not sure what to answer for summation(). I think it is not generic because its implementation and its behavior is not type dependent : this function is just a function of higher order, with the argument term being a function. It doesn't use any feature that would alter the behavior of this function based on types.

For illustration of a generic function, you could take a look at the C++ standard function std::sort() : its implementation depends on the type of its arguments (and optionally a comparison function with arguments of a determined type). By using the features of C++ templates, it can sort any container of any type, under the condition that it has the operators/member functions/traits/iterators that are required by the implementation of the generic function.

Can a dynamic typed language have generic functions

Dynamically typed language require less generic code than statically typed languages.

For example, if you have a container of objects of dynamic type, a qsort function could generically sort the container, as long as any combination of two elements in the container can be compared.

But even in such a flexible environment, generic --type dependent-- programming could be helpful. The typical use case is multimethods , where the behavior or the code depends on the type of the arguments or even the combination of types (such as for determining the intersection between two different shapes). For additional information see:

• Generic programming package for python: multidispatching
• Making generic functions usable in smalltalk
• Example of generic function in Common Lisp

Answer 2

Generic functions take the type of at least one function argument generically at compile time. That is, the compiler finds out which type is used at a certain place and applies exactly this type where it is used in the function. E.g. if you have a generic argument in your function that is used with a + operator, the type must have appropriate methods. For strings/arrays this would in many case be a concatenation and for and integer/float an addition. The compiler can detect that an apply the correct operation. Your C routine is not generic in that sense, since it's the programmer that applies some size information and not the compiler detecting the type and using the correct size.

E.g. in some fictive language

func add(p1,p2) {
  return p1+p2
}

print add("a", "b") // yields "ab"
print add(1, 2) // yields 3

Here the compiler detects in the first case that two strings are applied and will internally expand something like

func add(p1:string, p2:string) 

and treat the + as concatenation while in the second case it would expand

func add(p1:int, p2:int)

as per supplied integer parameters. Generic means, the compiler generates individual code during compile time. Python for example is untyped and would do that kind of substitution during runtime. Means: Python does not have generic functions since everything is sort of generic.

Answer 3

I'm going to start this from the perspective of C++, then work my way into C.

In statically-typed languages like C, C++, Java, etc., a "generic" function allows you to specify the function operations once, using placeholders for any types that may vary between different calls (which means functions like qsort and bsearch are most definitely not generic functions). Ideally, you'd also like the compiler to automagically detect any calls to this generic function and generate the actual code as necessary.

C++ makes this easy¹ by offering templates:

template <typename T>
T summation( T *values, size_t numValues )
{
  T result = 0;
  for ( size_t i = 0; i < numValues; i++ )
    result += values[i];
  return result;
}

T is a placeholder for any type², so you can call it as

int ivals[]    = {1,2,3,4,5,6,7,8,9};
double dvals[] = {1,2,3,4,5,6,7,8,9};

int sumi    = summation( ivals, 10 );
double sumd = summation( dvals, 10 );

When the code is compiled, the compiler sees the two calls to summation and deduces the types of the arguments. For each different type, it generates a new instance of the function, giving it a unique name:

int summation_i( int *values, size_t numValues )  // actual compilers will generate
{                                                 // more complex "mangled" names
  int result = 0;                                 // than this
  ...
}

double summation_d( double *values, size_t numValues )
{
  double result = 0;
  ...
}

It then generates code such that the result of summation_i is assigned to sumi and summation_d is assigned to sumd.

C doesn't offer anything similar to the template feature. Traditionally, we've attacked generic programming in one of two ways - either by using macros or by using void * everywhere and delegating type-aware operations to other functions.

Here's a bad example of a macro-based solution:

#include <stdio.h>

#define SUMMATION_DEF(t) \
t summation_##t( t *values, size_t numValues ) \
{                                              \
  t result = 0;                                \
  for ( size_t i = 0; i < numValues; i++ )     \
    result += values[i];                       \
  return result;                               \
}

#define SUMMATION(t,x,s)  summation_##t(x, s)

SUMMATION_DEF(int)
SUMMATION_DEF(double)

int main( void )
{
  int ivals[] = {1, 2, 3, 4, 5};
  double dvals[] = {1, 2, 3, 4, 5};

  int sumi = SUMMATION(int, ivals, 5);
  double sumd = SUMMATION(double, dvals, 5);

  printf( "sumi = %d\n", sumi );
  printf( "sumd = %f\n", sumd );

  return 0;
}

The SUMMATION_DEF is roughly similar to a template in that it specifies the function operations, using the macro parameter t as a type placeholder. We also use t as part of the function name - the ## is the token pasting operator, and the preprocessor will expand t and append that value to the name of the function³.

Where it differs from C++ is the fact that a macro is just a dumb text substitution. It doesn't trigger any special operations on the part of the compiler. The actual function instances aren't automatically generated based on any invocations of the SUMMATION macro - we have to explicitly generate the functions we want (hence the SUMMATION_DEF(int) and SUMMATION_DEF(double) before main). It also means that when we call summation_xxx through the SUMMATION macro, we have to pass the type as part of the macro argument list, such that the right function gets called. What a pain.

The C 2011 standard added the _Generic keyword, which can make life a little easier in that respect:

#include <stdio.h>

#define SUMMATION_DEF(t) \
t summation_##t( t *values, size_t numValues ) \
{                                              \
  t result = 0;                                \
  for ( size_t i = 0; i < numValues; i++ )     \
    result += values[i];                       \
  return result;                               \
}

#define SUMMATION(x,s)  _Generic((x),                         \
                                 int *     : summation_int,   \
                                 double *  : summation_double \
                                )(x, s)

SUMMATION_DEF(int)
SUMMATION_DEF(double)

int main( void )
{
  int ivals[] = {1, 2, 3, 4, 5};
  double dvals[] = {1, 2, 3, 4, 5};

  int sumi = SUMMATION(ivals, 5);
  double sumd = SUMMATION(dvals, 5);

  printf( "sumi = %d\n", sumi );
  printf( "sumd = %f\n", sumd );

  return 0;
}

The _Generic keyword allows you to evaluate expressions based on types; thus, if the type of the first argument to SUMMATION is int *, we call summation_int; it's it's double *, we call summation_double. This way we don't have to specify the type name in the macro arguments.

The other approach, as you've seen, is to use void * and to delegate type-aware operations to other functions. Like I said above, that's not really "generic" programming, since you have to manually implement each comparison function for each type. You can't just code it once and be done with it. And by using void *, you basically throw type safety out the window and into oncoming traffic.

And before anyone complains - no, none of these summation functions check for or deal with arithmetic overflow. That's a subject for another day.

---

1. For sufficiently loose definitions of "easy". The metaprogramming language used to support templates is Turing-complete, so you can do *really amazing* and impossible to understand things with it.
2. For sufficiently loose definitions of "any type". Note that whatever type you use must support the += operator, otherwise the compiler will yell at you.
3. This code will break for types like unsigned int or long double since they have whitespace in the name. I don't immediately know the solution to that problem, and I've spent enough time on this answer as it is.