To my recent message
(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 ...). [..] 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.
Dylan Thurston <dpt@math.harvard.edu> responds on 23 Aug 2001
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?
I am skeptical too. Anyway, if a compiler `knows' the word CommutativeRing, knows that by definition, CommutativeRing requires associativity, commutativity ..., observes the instance CommutativeRing T for some type T in some program, sees further expr = (2*a + b) - (a+a) :: T and sees the language version (compiler) flag -fignore-bottom, (something of this sort) then, has it right to convert expr --> b :: T ? To my mind, there is something more in this than intension. In practice, the users do not write explicitly such expressions as expr. But they write them implicitly, by applying functions in special cases, for example, one has f(x,y) and applies f(x,2*x) ... I do not ask compilers to exploit now this possibility. Only noted that a meaningful category organization provides, in principle, room for such optimization. Am I missing something? For I can mistake. Further, to my
(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 ... ''
Dylan Thurston <dpt@math.harvard.edu> writes
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. [..]
I believe, Aldor checks some types at run-time. And it has types as values. In fact, the above Zmod is a _function_ that takes values in a type called Ring. Each value Zmod(n) is a domain (abstract data type) of type Ring. Regards, ----------------- Serge Mechveliani mechvel@botik.ru