2 points on language. Continuing
S.D.Mechveliani
mechvel@math.botik.ru
Fri, 24 Aug 2001 10:30:29 +0400
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