[Caml-list] double-functors for types and values

[Caml-list] double-functors for types and values

[Brian Naylor]

It frequently happens that I have a module/functor A parameterized by
module B, but B depends on types that are part of A.  Those types of A in
turn depend on the types of B.  Wow, I've confused myself already.  Let me
try to make this clearer:

    let A.avalue = ... B.bvalue ...
    val B.bvalue : ... A.atype ...
    type A.atype = ... B.btype ...

This results in the following kind of double-functor, one functor for the
types and the second internal functor for the values:

module A = struct

  module Types (B_types : sig type btype end) = struct

    type atype = ... B_types.btype ...

    module Values (B_values : sig val bvalue : ... atype ... end) = struct

      let avalue = ... B_values.bvalue ...

    end
  end
end

module B = struct

  type btype = ...

  module A_types = A.Types (struct type btype = B.btype end)

  let bvalue = ...

  module A_values = A_types.Values (struct let bvalue = B.bvalue end)

  let _ = ... A_values.avalue ...

end

So, my questions are:

(1) is this a normal way of structuring this kind of thing?  I know I could
    use polymorphic types instead of trying to make it work in the module
    system, but I like the idea that all my types are made explicit.

(2) do I pay a run-time cost for functor applications that only contain
    types?  In other words, does A_values.avalue suffer a double
    indirection since it is buried two functors deep?  Or do you only pay
    the indirection cost for values that are passed across functorial
    boundaries?


__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] double-functors for types and values

[Jacques Garrigue]

From: Brian Naylor <bwv211mail@yahoo.com>

> It frequently happens that I have a module/functor A parameterized by
> module B, but B depends on types that are part of A.  Those types of A in
> turn depend on the types of B.  Wow, I've confused myself already.  Let me
> try to make this clearer:
> 
>     let A.avalue = ... B.bvalue ...
>     val B.bvalue : ... A.atype ...
>     type A.atype = ... B.btype ...
> 
> This results in the following kind of double-functor, one functor for the
> types and the second internal functor for the values:
[..] 
> module B = struct
> 
>   type btype = ...
> 
>   module A_types = A.Types (struct type btype = B.btype end)
> 
>   let bvalue = ...
> 
>   module A_values = A_types.Values (struct let bvalue = B.bvalue end)
> 
>   let _ = ... A_values.avalue ...
> 
> end

There 's something fishy in struct type btype = B.btype end:
if you're still inside B, you cannot refer to yourself as B.
The compiler might let you do that if you've already got a B.cmi
around, but you won't be able to compile from scratch.

So this should actually be even more nested:

module B = struct
  module Types = struct type btype = ... end

  module A_types = A.Types (Types)

  module Values = struct let bvalue = ... end

  module A_values = A_types.Values (Values)

  let _ = ... A_values.avalue ...

end

> So, my questions are:
> 
> (1) is this a normal way of structuring this kind of thing?  I know I could
>     use polymorphic types instead of trying to make it work in the module
>     system, but I like the idea that all my types are made explicit.

I wouldn't call it normal, but this looks sound.
If you like things to be complicated.

> (2) do I pay a run-time cost for functor applications that only contain
>     types?  In other words, does A_values.avalue suffer a double
>     indirection since it is buried two functors deep?  Or do you only pay
>     the indirection cost for values that are passed across functorial
>     boundaries?

No. Type information is extracted at compile time.
For indirections, a module is just a big record, so if you have a
direct handle on it, its original nesting should not matter.
Am I correct?

Functors should incur three costs:
* type abstraction cost: if you depend on abstract types, some data
  structure accesses cannot be optimized.
* function abstraction cost: all imported functions and (some?)
  exported functions cannot be called directly. Expensive.
* structure access cost: you have to dereference to get to your
  closures. I believe it's cheap compared to the function abstraction
  cost. Xavier Leroy had recently some figures showing that a method
  call (double indirection) was not that much more expensive than an
  abstract function call.

Efficiency is a relative problem. As long as you're not calling an
abstract function doing a single addition inside you super-optimized
for-loop, this should be ok...

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] double-functors for types and values

[Brian Naylor]

--- Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp> wrote:
> There 's something fishy in struct type btype = B.btype end:
> if you're still inside B, you cannot refer to yourself as B.

Whoops, sorry.  You're right - the actual code uses more nested modules or type
renaming, which I left out of the sample code.

> Functors should incur three costs:
> * type abstraction cost: if you depend on abstract types, some data
>   structure accesses cannot be optimized.

I would like to see an example of an unoptimizable case

> * function abstraction cost: all imported functions and (some?)
>   exported functions cannot be called directly. Expensive.

So in the following code:

module MakeA (A : sig type x end) = struct
  let foo = ...
  module MakeB (B : sig val quux : ... end) = struct
    let bar = ...
  end
end

Both [foo] and [bar] will not cost anything to evoke, but [quux] will cost an
extra indirection since it was imported in the functor parameter?

> * structure access cost: you have to dereference to get to your
>   closures. I believe it's cheap compared to the function abstraction
>   cost. Xavier Leroy had recently some figures showing that a method
>   call (double indirection) was not that much more expensive than an
>   abstract function call.

Is this referring to closures over over local modules (using [let module])
only, or does it have an impact on top-level modules as well?

Can someone come up with a link to the figures mentioned above?

Thanks.

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners