HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Interfaces
The interface implies a "contract" between two entities. The interface also signifies a relationship and can be decorated to indicate a different relationship to different set of entities. Another aspect of interface is the semantics of what is passed between the entities.
Contract view
Consider an interface, such as:
return_val do_something( passed_val)
The do_something indicates an expectation of the contract, some of these are well understood and others aren't. It is assumed that the caller and the called are in perfect sync on the semantics of this contract. The contract says:
If passed a valid passed_val as per the contract, the do_something entity will "do something" using that passed_val and return a return_val which can be interpreted.
What exactly constitutes the contract is actually outside the scope of the declaration of the contract itself.Yet, the do_something is nothing but the definition of that contract itself.
Consider x == (2 + 2) as a statement, it implies a contract of the "==" function that takes two parameters and returns them as equal, if the difference of these is equal to 0.
However, it does not indicate it as part of it's declaration. For example the "=" operator will not even work for a type for which it cannot know how to subtract them. Consider the definition of a point which can be defined as:
struct point{
char isxy_rth;
float x;
float y;
float r;
float th;
};
The points p1{1, 2.0, 2.0, 0, 0}, p2{ 0, 0, 0, 2, 45} are same points and p1 == p2 will not be able to indicate that.
So the contract is the actual implementation of do_something() entity itself. So, the interface does not describe a contract. It, however, does indicate the exchange of entities involved in that contract.
Relationship
The interface can be decorated in multiple ways to indicate a diverse set anticipated relationships that this interface may have with the external world. For example, one can indicate that this interface in "bundled" or encapsulated with a particular abstract data type and hence can only be used for that data type. Though this is essentially scoping the interface, but is tantamount to decorating the interface with the property scope.
Another feature that is prevalent in Object Oriented Languages is the control exercised on inheritance. An interface can be decorated with a tag that allows or forbids the interface to be used by inherited data types to the type which contains the interface. An example of this in c++ is the "protected" tag, it means that the interface can be inherited only by the immediate children of the type in the inheritance tree; the public or private tags are other tags to control the scope of the interface. These tags or decoration control what types can/cannot use these interfaces.
OO languages have introduced a full fledged object for interface; so an interface is no longed a mechanism of invoking a functionality by providing data to it, but it is sophisticated enough to do translations/adaptations/aggregations before invoking the interfaces of the other objects. This permits the interfaces to change without making changes to the objects that provide functionality of that interface. The separation of the interface to its implementation breaks the complexity of pre-processing of the data passed and actual processing into two different objects.
Parametrization
An interface requires data to be passed to it for the desired manipulation. The interface manipulated the data and can return the modified copy of the data or do modifications in place (means modify the data in the caller's context), in addition, several ways exist to provide "return" information from the interface back to the caller. It can be in the form of return values, modification to global tokens and/or passing information back to the caller in caller's context. The interesting aspect of this rich variety of parameter passing is that another interface can be passed to this interface, such that one can create truly extensible interfaces that do not make any implicit assumptions on the nature of the passed data.
The aims of generality
Any user of a service/function needs to get "something" done on a data set that one has. The twin aims of the provider of the interface are:
1. To provide flexibility of passing the data.
2. To keen the interface as simple/basic as possible.
However the two goals are orthogonal to each other. One two extreme positions are to develop a completely flexible interface "class", which can pre-process any type of data set, changes behaviour as per the type of data set and is highly customizable. On the other had a minimal set such as c language function:
int stcmp (char *s1, char *s2) specifies a bare bone minimum that compares (alphabetically) s1 and s2 which are assumed to be null terminated character arrays.
The function interface is hardly adaptable, cannot be extended and has no notion on being encapsulated with any data type.
The C language implementation of interfaces
C language interface specification is nearly a minimal set for an interface definition. In theory one could define an interface as do_something(<copy/ref>dataset, what_happened<data>).
where do_something is a procedure/function that hides a functionality and exposes it by the interface do_something. The do_something works on the dataset (either in place or on a copy), the results can be expressed in "what_happened" data set and/or the original dataset can be modified. The what_happened can also be a reference or a copy.
c language actually provides for building an interface as trivial as do_something() or as minimal as the above. However, c language provides a very powerful interface mechanism by the addition of two key language features:
1. The void pointer.
2. Function pointer.
These two language features make it possible to pass any unknown dataset to a function which need not be written to depend on the property of a dataset. The function pointer can be used to express the properties and operations on the passed dataset.
Using these features, completely generic algorithm implementations can be written.
An example
The GNU c library function for quick sorting has the signature:
void qsort (void *array, size_t count, size_t size, comparison_fn_t compare)
It is a nice example of a "somewhat generic" interface, the void *array is the array of "count" elements, each of size "size". The elements can be compared (>,< or ==) by the "compare" function.
There are several assumptions made implicitly by the interface definition of the qsort:
1. The elements are stored in an "array" i.e. contiguous memory.
2. The elements are of the same size.
3. The elements can be "located", just by the element count and the offset (count * size).
4. Compare compares the addresses, so if two elements are compared based on some sub-element, it can fail.
Yet,despite the assumptions, the interface still is elegant and works nicely for primitive/basic types. It is not completely generic though.
Could one write a completely generic sorting function??
Let's examine the heart of a sorting algorithm (for the sake of simplicity we use a bubble sort):
for(i=1; i<N; i++)
{
j = i;
while((A[j] < A[j-1]) && (j>0))
{
swap(&s[j], &s[j-1]);
j = j - 1;
}
}
Analyzing the code segment above, we find that we can rewrite the above in completely generic terms (where we do not rely on any built-in operator for primitive types) as:
for( i = 1; i < num_elem; i++)
{
j = i;
while( (j > 0)&& is_greater( prev(at(list +
j)),at(list + j)))
{
swap(at(list + j), prev(at(list + j)));
j--;
}
}
The above segment shows how comparision between hitherto unknown data types is captured by "is_greater" function, how an element is "located" by the "at" function and how "prev" or "next" functions enable iteration. "swap" functions allows swapping of elements in the list. So all the functions/operators that are specific to the dataset to be sorted has been abstracted into functions and the "heart" of the algorithm has no dependency/assumption on the type of dataset provided to it.
So, the completely generic interface for sorting is:
void ins_sort( void *list, int num_elem, void *(*is_greater)(void *, void *), void (*swap)(void *, void *), void *(*next)(void *), void *(*prev)(void *), void * (*at)(int));
One can easily implement the function with assumptions such as it at is null, we assume an array storage, if is_greater is null, we assume integer comparision and so on. Appendix contains a complete code listing without the "at" function.
Discussion and summary
We have seen that the interface as a contract is a misconception as the contract is encapsulted in the function itself. The relationship of an interface to the datasets is a construct of object oriented languages and is quite artificial. By its very nature it prohibits to make "generic" interfaces as interfaces get encapsulated into "collections". The parameterization is a strong feature of languages such as C, that is used to pass values (c language does not support pass by reference though) and return values. Parameterization with generic pointer type and function pointers can be used to build truly generic interface as was shown in the sorting example.
We have seen that a truly generic interface requires user of the interface to provide for functions specific to his dataset, which can be used to build "this" functionality. While a truly generic interface can be adapted to handle most "default" cases without user having to provide the basic function, it is still quite overwhelming in its detail.
The general purpose non-generic interfaces make strong assumptions on the datasets provided, a user needs to be acutely aware of these before picking up his favourite library function.
Appendix:
// the code listing below does not implement the "at" function, which is a trivial change and left to readers amusement.
- include <stdio.h>
- define MAX 100
void ins_sort(void *list, int num_elem, void *(*is_greater)(void *, void *), void (*swap)(void *, void *), void *(*next)(void *), void *(*prev)(void *));
int is_greater_def(int *i, int *j);
void swap_def(int *i, int *j);
int *next_def(int *i);
int *prev_def(int *i);
int main()
{
int i, n;
int inp[MAX] = {1,2,3,4,5,0};
int (*is_greater_num)(void *, void *) = NULL;
void (*swap_num)(void *, void *) = NULL;
int *(*next_num)(void *) = NULL;
int *(*prev_num)() = NULL;
i = 0;
while(1)
{
scanf("%d",&inp[i++]);
if(inp[i-1] == 0)
break;
}
n = i - 1;
ins_sort(inp, n, is_greater_num, swap_num, next_num,
prev_num);
printf("Insertion sort:\n");
i = 0;
while(1)
{
printf("%d ",inp[i++]);
if(inp[i-1] == 0)
break;
}
}
void ins_sort( void *list, int num_elem, void *(*is_greater)(void *, void *), void (*swap)(void *, void *), void *(*next)(void *), void *(*prev)(void *))
{
int i, j,k;
if(!is_greater)
{
is_greater = is_greater_def;
swap = swap_def;
next = next_def;
prev = prev_def;
}
for( i = 1; i < num_elem; i++)
{
j = i;
while( (j > 0)&& is_greater( prev((int *)list +
j),(int *)list + j))
{
swap((int *) list + j, prev((int *) list + j));
j--;
}
}
}
int is_greater_def(int *i, int *j)
{
int k, l;
k = *i;
l = *j;
printf("comparing d\n", k, l);
return ( (k > l) ? 1 : 0);
}
void swap_def(int *i, int *j)
{
printf("swapping d \n", (int)*i, *j);
int t;
t = *i;
*i = *j;
*j = t;
printf("swapped d \n", *i, *j);
}
int *next_def(int *i)
{
printf("the next is %d \n", *(i+1));
return((i+1));
}
int *prev_def(int *i)
{
printf("the prev is %d \n", *i);
return((i-1));
}
Category: Software
Comments
