[Agda] parameterized modules?

Serge D. Mechveliani mechvel at botik.ru
Wed Oct 17 12:42:35 CEST 2012


On Wed, Oct 17, 2012 at 08:36:28AM +0200, Andreas Abel wrote:
> On 15 Oct 2012, at 7:09 PM, Serge D. Mechveliani wrote:
[..]
>> are you sure that Agda really needs parameterized modules?
>> For example, Haskell has not such and still looks all right
>
> It looks alright, but you cannot really do abstract developments.  For  
> the other end of the spectrum of module systems, see ML functors.
>
>> (except absence of dependent types).
>> If they are replaced with classes and instances by records, then the
>> implementors could save effort.
>
> Classes cannot replace modules, since classes are inferred automatically 
> and thus need unique instances.
>


Sorry, this is somewhat not so clear to me, looks rather generic.
Consider an example of a parametrized module for several functions 
related to sorting a list:  

 module Sort (A : Set) (_<=_ : Rel A _) 
                       (isDTO : IsDecidableTotalOrder \equiv _<=_)
   where
   insert : A -> List A -> List A
   insert x []       = x :: []
   insert x (y :: ys)  with x <=? y
   ...               | yes _  = x :: y :: ys
   ...               | no _   = y :: insert x ys

   <other related functions>

(the examples in this letter were not tried to compile).

I understand its idea as follows.   
module Sort-T-l = Sort T lessEQ  
produces a module  Sort-T-l  which is ready to perform `insert' for 
for this given particular type T and this given DTO ordering  lessEq  on  
T  (T and lessEq  are uniformly substituted for  A and _<=_).
And then, a programmer can choose different pairs (T , lessEq).

Now I try to replace a parameterized module with using classes:

  insert : {A : Set} -> {_<=_ : Rel A _} ->
           (isDTO : IsDecidableTotalOrder \equiv _<=_) -> A -> [A] -> [A]

  open IsDecidableTotalOrder {{...}}
  insert _     x []         =  x :: []
  insert isDTO x (y :: xs)  with x <=? y
  ...               | true  = x :: y :: ys
  ...               | false = y :: insert isDTO x ys

Now, having any given  T : Set,  any given  lessEq : Rel T _,
and a record value
                   isDTO : IsDecidableTotalOrder \equiv lessEq
for this lessEq,
a call             insert isDTO x xs

performs the insertion for any  x : T,  xs :: List T.
Fetching to `insert' different pairs (T , lessEq) will do the needed 
thing.
The effect is the same as in a parameterized module.
Is not it?
If it is the same, why does one need a parameterized module?

I see only the following reason.
Suppose that the above parameterized module  Sort  has many types and 
functions:  insert, sort, merge, merge-sort ...,
and they depend on the _same_ above parameters  (A, _<=_, isDTO).
A parameterized module allows to _skip uniformly_ the part
  (A : Set) (_<=_ : Rel A _) (isDTO : IsDecidableTotalOrder \equiv _<=_)

in all these item declarations
(no matter whether they are denoted as implicit by `{}').

Now, I think that:
a parameterized module is a tool for an automatic insertion of some 
common declaration prefix to many declarations in this module.
Is it for something else?

Well, this may be a reason for supporting parameterized modules.


> Classes cannot replace modules, since classes are inferred automatically
> and thus need unique instances.

Can you illustrate this on the above sorting example?
In the above my example,   IsDecidableTotalOrder  stands for something 
like a  class,  and each value pair  (lessEq, isDTO)  stands for an 
instance of this class.
Right? 
Where is an automatic class inference, where is an unique instance?

A programmer has a choice:
(PM) to program the sorting-related functions by using a parameterized 
     module, as in the first example,
(C) instead of using a parameterized module to use the class denotations
    in each sorting-related function (as in the second example).

(C) replaces (PM) at the cost of inserting a repeating prefix in the 
    declarations in each related function.

And I suspect that choosing (PM) one looses a certain imporant 
possibility as compared with (C). 
This will be visible in the case when sorting is lifted to a tower
of types built by repeated applying of several type constructors
(for example, the tower over the set {Nat, \times, List}). 

This year I had such an unlucky experience with  parsing  designed via 
parameterized modules  as compared with its design via  classes.
This was with the  Spad  language which has _categories_ for classes
and _packages_ for parameterized modules.
>From this time, I a bit fear of parameterized modules, have an 
impression that they tend to lead to a wrong field. 

Thank you for explanations,

------
Sergei



More information about the Agda mailing list