Tuesday, May 6, 2014

Functional equivalence in value-level programming

When you construct a container like Set or Map, you need to either explicitly pass the functions used for comparing or hashing elements, or automatically pick them up based on the types of the elements. "Value-level programming" tries to discourage type-directed dispatch, so we need to pass the functions explicitly. That leads to a problem when you need to quickly merge two Sets or Maps. The merging function cannot assume that the same hashing function was used in both containers, so it might need to rehash all elements, while with type-directed dispatch it could assume that the hashing function for the same type is always the same and skip the rehashing.

That's a genuine problem with value-level programming. There are several possible solutions:

1) If two containers have pointers to the same hashing function, that means it's safe to skip rehashing. This approach is guaranteed to be safe, but it's sometimes too conservative.

2) Each hashing function could contain an explicit ID, so the merging function can skip rehashing if the IDs match. This approach is not guaranteed to be safe, but it seems to discourage programmer errors pretty well.

3) The compiler could enforce the fact that there's only one value of a specific type, like HashFunction<String>. That can be done with private constructors in Java, or with abstract data types in functional languages. This approach is guaranteed to be safe, but it needs an escape hatch, possibly in the form of (1) or (2).

Overall it seems to me that value-level solutions to the above problem are not worse than type-directed solutions. I don't know if there are other, more severe variants of that problem.

No comments:

Post a Comment