J
jacob navia
Prompted by the remark of "gwowen" in the "Design decisions" thread, I
have slightly modified the ccl to accomodate infinite arrays. Here is a
small blurb explaining how it works
-----------------------------------------------------------------------
Infinite arrays
---------------
We can conceptually define an array as a function that maps an input
value *index* into some output that is the *value* of the
array at that position.
In this context, an infinite array is a function that maps any member
from the set of positive natural numbers (a size_t) into some
resulting value. This function must have a value for all possible input
values of its size_t argument. For instance the function
value=(index+5)/(index-5) is not usable since it would provoke a
division by zero at index=5.
Infinite arrays exist in many computer languages.
o In APL they were proposed by McDonnel and Shallit in their paper
"Extending APL to Infinity" [1].
o Common lisp has the "Series" construct that is similar to infinite
arrays.
o The Translucid computer language features each variable as an
infinite array of all its values [2]
Since in the C language arrays must contain elements of the same type,
obvious restrictions apply: all C types have specific bounds (defined
in the appropiate headers) so that a conceptually correct function like
the Fibonacci function for instance, is not usable beyond a certain
value of the input index because of output overflow: the Fibonacci
numbers grow without limit.
To implement an infinite array using the library is relatively easy.
The iVector interface has the necessary hooks for doing this.
When an index error occurs, the library calls the error function of the
given vector passing it the name of the function, the integer constant
CONTAINER_ERROR_INDEX, and a pointer to the array and the requested
index. If the error function returns any other value than Null,
the Library will assume that it is a valid pointer to some result where
the real value of the array at that position is stored.
Using this information we can write this first simple implementation of
an in finite array. The array function will be the identity
function i.e. the array will contain the value of the index at each
position.
#include <stdarg.h>
#include <stdlib.h>
#include "containers.h"
static void *Fn(const char *msg,int errorCode,...)
{
va_list ap;
size_t idx;
static int value;
Vector *v;
if (errorCode != CONTAINER_ERROR_INDEX)
return iError.RaiseError(msg,errorCode);
va_start(ap,errorCode);
v = va_arg(ap,Vector *);
idx = va_arg(ap,size_t);
value = idx;
va_end(ap);
return &value;
}
Vector *CreateInfiniteArray(void)
{
VectorInterface *ivct;
Vector *result = iVector.Create(sizeof(int),1);
if (result == NULL) return result;
iVector.SetErrorFunction(result, Fn);
return result;
}
int main(void)
{
Vector *v = CreateInfiniteArray();
int i;
for (i=20; i<30;i++) {
printf("%d ",*(int *)iVector.GetElement(v,i));
}
printf("\n");
iVector.Finalize(v);
}
The central piece of the implementation is the Fn function that will be
our replacement of the default vector error function. This function
will only return something if the error is an error index. Otherwise it
calls the default function stored in a static pointer.
If the error is the expected index error, we fetch the arguments and we
set the value. The address of the static area is returned.
We have to write a special creation function that creates a vector and
replaces its error function with the our own, saving the old
value in a global variable.
We can now write our test program that returns 10 integers from our
array. Its output is:
20 21 22 23 24 25 26 27 28 29
have slightly modified the ccl to accomodate infinite arrays. Here is a
small blurb explaining how it works
-----------------------------------------------------------------------
Infinite arrays
---------------
We can conceptually define an array as a function that maps an input
value *index* into some output that is the *value* of the
array at that position.
In this context, an infinite array is a function that maps any member
from the set of positive natural numbers (a size_t) into some
resulting value. This function must have a value for all possible input
values of its size_t argument. For instance the function
value=(index+5)/(index-5) is not usable since it would provoke a
division by zero at index=5.
Infinite arrays exist in many computer languages.
o In APL they were proposed by McDonnel and Shallit in their paper
"Extending APL to Infinity" [1].
o Common lisp has the "Series" construct that is similar to infinite
arrays.
o The Translucid computer language features each variable as an
infinite array of all its values [2]
Since in the C language arrays must contain elements of the same type,
obvious restrictions apply: all C types have specific bounds (defined
in the appropiate headers) so that a conceptually correct function like
the Fibonacci function for instance, is not usable beyond a certain
value of the input index because of output overflow: the Fibonacci
numbers grow without limit.
To implement an infinite array using the library is relatively easy.
The iVector interface has the necessary hooks for doing this.
When an index error occurs, the library calls the error function of the
given vector passing it the name of the function, the integer constant
CONTAINER_ERROR_INDEX, and a pointer to the array and the requested
index. If the error function returns any other value than Null,
the Library will assume that it is a valid pointer to some result where
the real value of the array at that position is stored.
Using this information we can write this first simple implementation of
an in finite array. The array function will be the identity
function i.e. the array will contain the value of the index at each
position.
#include <stdarg.h>
#include <stdlib.h>
#include "containers.h"
static void *Fn(const char *msg,int errorCode,...)
{
va_list ap;
size_t idx;
static int value;
Vector *v;
if (errorCode != CONTAINER_ERROR_INDEX)
return iError.RaiseError(msg,errorCode);
va_start(ap,errorCode);
v = va_arg(ap,Vector *);
idx = va_arg(ap,size_t);
value = idx;
va_end(ap);
return &value;
}
Vector *CreateInfiniteArray(void)
{
VectorInterface *ivct;
Vector *result = iVector.Create(sizeof(int),1);
if (result == NULL) return result;
iVector.SetErrorFunction(result, Fn);
return result;
}
int main(void)
{
Vector *v = CreateInfiniteArray();
int i;
for (i=20; i<30;i++) {
printf("%d ",*(int *)iVector.GetElement(v,i));
}
printf("\n");
iVector.Finalize(v);
}
The central piece of the implementation is the Fn function that will be
our replacement of the default vector error function. This function
will only return something if the error is an error index. Otherwise it
calls the default function stored in a static pointer.
If the error is the expected index error, we fetch the arguments and we
set the value. The address of the static area is returned.
We have to write a special creation function that creates a vector and
replaces its error function with the our own, saving the old
value in a global variable.
We can now write our test program that returns 10 integers from our
array. Its output is:
20 21 22 23 24 25 26 27 28 29