NAME

cru_fold - specification for operating on a set of operands

SYNOPSIS

#include <cru/cru.h>

typedef struct cru_fold_s
{
   cru_top map;
   cru_bop bmap;
   cru_bop reduction;
   cru_nop vacuous_case;
   cru_destructor r_free;
   cru_destructor m_free;
} *cru_fold;

DESCRIPTION

With each field in a cru_fold structure pointing to a user-defined function of the indicated type, applications pass it to various cru library functions that use it to compute a user-defined result from a set of arbitrarily many edge labels, vertices, or properties in a graph.

There are two main ways of organizing the computation. The simpler way starts with the map or the bmap function being applied to every member of the set of operands. Then the reduction is applied to pairs of result values returned by it if there are more than one, which are discarded afterwards. Then the reduction is further applied to pairs of results obtained by previous reductions if any, which are also discarded. Sufficiently many reductions are evaluated with intermediate results discarded until only a single result remains.

In the other way of organizing the computation, the map or bmap is also applied initially to every member of the set, and in addition, the vacuous_case is evaluated. If there are any operands in the set, the reduction is then applied to the pair of a map result as its left operand and the vacuous_case result as its right, both of which are discarded. While any unused results remain, the reduction is evaluated with one of them as its left operand and the previous reduction result as its right, both of which are discarded. The result overall is that of the vacuous_case if the set of operands is empty, or the last reduction evaluated otherwise.

Applications select the simpler way by initializing the vacuous_case field to NULL and the other way by initializing it as a pointer to a user-defined nullary operator. Some differences necessarily follow.

• The simpler way is defined only for non-empty sets of operands.
• The simpler way requires the results of the map and the reduction to have identical types.
• The simpler way requires both operands of the reduction to have the same type as its result.

In the alternative:

• The result overall for any empty set of operands is given by the vacuous_case.
• The reduction and the vacuous_case must have identical result types.
• Only the right operand of the reduction must match its result type.
• The map or bmap can have any result type, but the left operand type of the reduction must match it.

In either case, functions given by the two destructor fields reclaim the discarded intermediate results. The r_free function reclaims results returned by the reduction, and the m_free function reclaims results returned by the map or bmap. These destructors must be suitable for their operand types. Either or both of these fields can be set to NULL, in which case cru infers that the corresponding result type is a scalar in no need of reclamation. Some other inferences are then possible:

• If all of the m_free, map and bmap fields are NULL, then cru may infer a default map operator that unconditionally returns its middle operand.
• If both the r_free and the reduction fields are NULL, then cru infers a default reduction operator that returns the lesser of its two operands cast as unsigned integers.

At most one map or bmap function may be defined in any cru_fold. The bmap, being a cru_bop, is expected to take only two operands and an error code as arguments, whereas the map, being a cru_top, is expected to take three operands and an error code. If a bmap is defined, it is passed only the left and middle operands that would have been passed to a map.

ERRORS

It is an error to omit a destructor when the corresponding result is dynamically allocated. This error is not detectable by cru but may cause memory leaks. Other errors are reportable by whatever API function is being called under these circumstances:

CRU_UNDVAC

Evaluation is requested on an empty set of operands but no vacuous_case is defined.

CRU_UNDMAP

A map operator is required but not specified or inferrable.

CRU_UNDRED

A reduction operator is required but not specified or inferrable.

CRU_TPCMPR

No vacuous_case is specified but the destructors differ, indicating that the map and reduction result types are incompatible. If the cru_fold structure is the vertex field of a cru_prop structure belonging to a cru_mapreducer top level structure, then this error is reported whenever the destructors differ, with or without a vacuous_case defined.

If neither destructor is specified because both result types are scalars, type conflicts are still an error but are not detected.

NOTES

Applications should ensure that the vacuous case result is semantically appropriate for the reduction. For example, the sum of an empty set of numbers is zero, the product of an empty set of numbers is conventionally taken to be unity, etcetera.

There is no specified ordering among the operands to a reduction. Applications relying on stronger assumptions will likely fail intermittently or be broken completely by an eventual update to cru. To ensure deterministic results, the reduction r must satisfy r ( x, r ( y, z) ) = r ( y, r ( x, z) ) for map results x and y if there is a vacuous_case defined, or must be associative and commutative otherwise.

The cru_fold structure is part of the cru_prop and cru_kernel derived structures, and the cru_inducer top level structure. Defining a bmap instead of a map is useful when an application requires a vertex mutation to depend on the incident or outgoing edges of the vertices, but it is prohibited from depending on adjacent vertices because the graph is cyclic and the traversal priority therefore must be unconstrained. When the cru_fold in the incident or outgoing field in a cru_prop specifies a bmap instead of a map, and the cru_prop is the v_op field in a cru_kernel that is the mu_kernel field in a cru_mutator, the bmap function's operands are the mutable vertex and the edge label, but not the adjacent vertex.

EXAMPLE

Given two user-defined functions as shown,

uintptr_t
sum (uintptr_t l, uintptr_t r, int *err)
{
   return (l + r);
}

uintptr_t
square (uintptr_t l, uintptr_t m, uintptr_t r, int *err)
{
   return (m * m);
}

this example declares the structure sum_of_squares of type struct cru_fold_s to specify the computation of the sum of the squares of a non-empty set of numbers.

struct cru_fold_s sum_of_squares = {
   .reduction = (cru_bop) sum,
   .map = (cru_top) square};

FILES

/usr/local/include/cru/function_types.h

/usr/local/include/cru/data_types.h

/usr/local/include/cru/error_codes.h

SEE ALSO

cru, cru_bop, cru_bpred, cru_builder, cru_built, cru_cbop, cru_classifier, cru_class_of, cru_class_size, cru_composed, cru_composer, cru_connect, cru_connector, cru_cqop, cru_crossed, cru_crosser, cru_ctop, cru_ctop_pair, cru_ctop_quad, cru_data_types, cru_deduplicated, cru_destructor, cru_destructor_pair, cru_edge_count, cru_fabricated, cru_fabricator, cru_filter, cru_filtered, cru_free_kill_switch, cru_free_later, cru_free_now, cru_free_partition, cru_function_types, cru_get, cru_hash, cru_induced, cru_inducer, cru_kernel, cru_kill, cru_killed, cru_mapreduced, cru_mapreducer, cru_merged, cru_merger, cru_mutated, cru_mutator, cru_new_kill_switch, cru_nop, cru_order, cru_order_pair, cru_partition_of, cru_plan, cru_postponed, cru_postponer, cru_prop, cru_prop_pair, cru_pruner, cru_qop, cru_qpred, cru_set, cru_sig, cru_singleton, cru_split, cru_splitter, cru_spread, cru_strerror, cru_stretch, cru_stretched, cru_stretcher, cru_subconnector, cru_terminus_count, cru_top, cru_tpred, cru_united, cru_uop, cru_vertex_count, cru_zone

AUTHOR

Dennis Furey (milonga@delayinsensitive.com)

PROJECT PAGE

https://github.com/gueststar/cru