Dylan Thurston dpt@math.harvard.edu
Thu, 23 Aug 2001 18:13:03 -0400

```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