On Thu, Aug 23, 2001 at 03:02:28PM +0400, S.D.Mechveliani wrote:
(1): As I wrote earlier, Haskell instances cannot model such domains as the residue ring Integer/(n), when n changes dynamically. This is why the BAL library applies the sample argument approach, and this somewhat complicates the program meaning.
Now, we observe in the Aldor manual (http:/www.aldor.org), Section 7.8: `` Zmod(n: Integer) : Ring with { if prime? n then Field; } == Integer add { if prime? n then {inv (x: %) : % == ...} }
Z_n, the domain of integers modulo n, is always a Ring. However, if n is prime, then Z_n is also a Field, meaning that it should provide a multiplicative inverse for nonzero values. In an `add' expression, a definition which appears in the consequence of an `if' expression is said to be a conditional definition ... ''
Z_n indeed sometimes supports additional operations. But how is the user expected to use these operations in a type-safe, statically checked way? Any use of 'inv' for Z_n will necessarily involve a run-time check on n to see whether it is prime. In the context of a statically checked language like Haskell, you could easily arrange to have a function that (a) checks if the modulus is prime and (b) if so, returns a corresponding element of a type that supports the new operations. [assuming you only want 'inv' to be defined for prime moduli, which is not 100% clear.] I'm sure there are cases where algorithms are more efficient when n is a prime, but again, this can (and should) be special cased.
(2) I wrote in the BAL paper that meaningful standard algebraic categories (classes) may, in principle, help the compiler to optimize programs using the properties related to the category names (associativity, commutativity ...). On the other hand, people write now and then, that they consider such possible properties only as intended, saying that the language does not provide room for their explicit usage (the latter was also said by the referee of this paper).
It occurs to me now that there may be certain misunderstanding. I kept in mind implicitly that as soon as these categories enter a library standard their names can also be added to the _key words of a language_. In this way the compiler is enabled to use the relevant properties. There remains a question of expressions like _|_ + 1 === 1 + _|_, but this is another matter, maybe, a matter of flags for the compiler and language version.
One question I have here is, how much are compilers prepared to take advantage of such knowledge? (Also, does it really belong in the compiler? In, e.g., FFTW, all this is optimized by a user program rather than the compiler.) I'm slightly skeptical: it's not entirely obvious how to take proper advantage of commutativity/associativity, and this seems like something I'd want to program directly rather than trust the compiler to do. But I haven't thought about this much; other opinions? Best, Dylan Thurston