Callbacks in the abstact data types and extra contextual data

Callbacks in the abstact data types and extra contextual data

[Marc Nieper-Wißkirchen]

Hi,

a number of modules (like the hash module or the list module) allow
the user to specify callbacks (e.g. a comparison function).
Unfortunately, these procedures do not take a context parameter, which
can be a problem because C lacks closures.

The original qsort function in stdlib.h has the same problem. Glibs
has remedied the problem by introducing qsort_r.

It would be nice if the modules hash, list, xlist, oset, xoset, ...
are extended in a similar way. We would essentially need new
constructors, say with the '_r' suffix.

Marc

Re: Callbacks in the abstact data types and extra contextual data

[Bruno Haible]

Hi Marc,

> a number of modules (like the hash module or the list module) allow
> the user to specify callbacks (e.g. a comparison function).
> Unfortunately, these procedures do not take a context parameter, which
> can be a problem because C lacks closures.

Is this a practical, actual problem, or only a theoretical one?

I would hesitate to change (or duplicate) public API, when there is no
practical need.

Note that the lack of context can be remedied by
  - use of per-thread variables, or
  - use of nested functions [1], or
  - storing a pointer to the necessary context in the list elements.

> The original qsort function in stdlib.h has the same problem. Glibs
> has remedied the problem by introducing qsort_r.

qsort_r is only portable to glibc systems, FreeBSD, and macOS. And yet,
no one has requested a substitute for it in gnulib. IMO this indicates
that few programs need this function.

Bruno

[1] https://gcc.gnu.org/onlinedocs/gcc-10.1.0/gcc/Nested-Functions.html

Re: Callbacks in the abstact data types and extra contextual data

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am Do., 9. Juli 2020 um 22:16 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> > a number of modules (like the hash module or the list module) allow
> > the user to specify callbacks (e.g. a comparison function).
> > Unfortunately, these procedures do not take a context parameter, which
> > can be a problem because C lacks closures.
>
> Is this a practical, actual problem, or only a theoretical one?

It is a practical one; in a computer algebra application, I have lots
of small entities (two words each), whose sort order is determined by
the extra data.

> I would hesitate to change (or duplicate) public API, when there is no
> practical need.
>
> Note that the lack of context can be remedied by
>   - use of per-thread variables, or

That's doable, but thread-local variables are like dynamically scoped
variables, which makes reasoning about the program a bit harder.
Moreover, for decent speed, native thread locals would have to be
supported.

>   - use of nested functions [1], or

I don't want to use non-portable functions.

>   - storing a pointer to the necessary context in the list elements.

In my use case, this would be an increase of 50% in the size of the
elements everywhere they appear.

> > The original qsort function in stdlib.h has the same problem. Glibs
> > has remedied the problem by introducing qsort_r.
>
> qsort_r is only portable to glibc systems, FreeBSD, and macOS. And yet,
> no one has requested a substitute for it in gnulib. IMO this indicates
> that few programs need this function.

I haven't yet needed specifically qsort_r as well in portable code
(and only once in non-portable private code), but I have mentioned it
because it illustrates the fundamental problem with a missing context
argument.

I see the point that one shouldn't lightly double an API. Although I
think that the current API is flawed with respect to a missing context
parameter, we cannot change it either without breaking old code.

One could use some macro-metaprogramming technique to get two versions
for each module.

Or one could add a global flag to the configuration (which ends in
config.h) and which changes the behavior globally for the application
(I am not sure whether this technique has been employed before).

Marc

Re: Callbacks in the abstact data types and extra contextual data

[Bruno Haible]

Hi Marc,

> > > a number of modules (like the hash module or the list module) allow
> > > the user to specify callbacks (e.g. a comparison function).
> > > Unfortunately, these procedures do not take a context parameter, which
> > > can be a problem because C lacks closures.
> >
> > Is this a practical, actual problem, or only a theoretical one?
> 
> It is a practical one; in a computer algebra application, I have lots
> of small entities (two words each), whose sort order is determined by
> the extra data.

OK. Then let's take the problem seriously.

I think it's time to solve the problem once and for all. I propose to add
a module that defines a function 'partial_function_last' such that, when
you have a function pointer

   int (*cmp3) (void *arg1, void *arg2, void *context)

then

   cmp2 = partial_function_last (cmp3, context);

produces a function pointer

   int (*cmp2) (void *arg1, void *arg2)

that invokes cmp3 with the given context.

Wikipedia calls it "partial function application".

The module will also have a function 'partial_function_free' that frees
a function that was constructed in this way.

Give me a couple of days to implement that.

Bruno

Re: Callbacks in the abstact data types and extra contextual data

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am Fr., 10. Juli 2020 um 20:38 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> OK. Then let's take the problem seriously.

If your solution can be implemented portable, that will be the best
solution by far.

For GCC one can use nested functions, but how can
'partial_function_last' be implemented in ISO C?

> I think it's time to solve the problem once and for all. I propose to add
> a module that defines a function 'partial_function_last' such that, when
> you have a function pointer
>
>    int (*cmp3) (void *arg1, void *arg2, void *context)
>
> then
>
>    cmp2 = partial_function_last (cmp3, context);

partial_function_last has to return the address of an existing
function. But this function has no context accept for global (thread
local) variables. How can this function know about 'cmp3'?

Marc

Re: Callbacks in the abstact data types and extra contextual data

[Bruno Haible]

Marc Nieper-Wißkirchen wrote:
> For GCC one can use nested functions, but how can
> 'partial_function_last' be implemented in ISO C?

It can be implemented for each CPU type and ABI. But this is OK since the
number of CPU types are hardly increasing nowadays.

It cannot be implemented in ISO C.

> For GCC one can use nested functions

GCC handles each CPU type and ABI separately as well.

Bruno