This the first of a series of thoughts about implementing a language capability similar to Andl (which is in turn based on The Third Manifestoon C# for use by programs written in C# (as against Andl which has entirely its own type system). The intention is not to focus on C# specifics, but issues relevant to any strongly-typed language, with perhaps an OO focus.
The Relational Algebra can be seen as dealing with streams of tuples, where
- A tuple value is assumed to be a native type (plain old object/record/class/struct) already existing in the language
- The input stream source will create the values; two streams of the same tuple type might have different native types.
- The output stream is also a native type, not necessarily the same as any input. Client software needs familiar data sources.
- The native type for those values cannot be relied upon to provide value semantics, or anything else required by the implementation.
Consider the implementation of a simple algorithm such as Union:
- There are three types (left input, right input, output) which should be the same tuple type but may be different native types
- Removing duplicates can be done with a hash set, which in turn requires a hashing function that depends only on tuple type (not native type).
Possibilities:
- If native types are used in implementation algorithms, they need to be augmented post hoc with additional operations (equality, hashing, cloning). That’s hard.
- If the implementation uses its own augmented native types then every input tuple has to be copied, but outputs can be consumed directly by clients. Dynamically creating native types is hard too.
- The implementation could convert all tuple data into dicts (hashes) or arrays of values; but this requires copy/conversion on both input and output. This is probably the easiest (but not where I started out).
In C# much of the implementation requires reflection. The Andl implementation is similar to (3).