Re: [Caml-list] functors with style?

Re: [Caml-list] functors with style?

[Marcin 'Qrczak' Kowalczyk]

Mon, 19 Nov 2001 14:10:25 -0800, Shivkumar Chandrasekaran <shiv@ece.ucsb.edu> pisze:

> For example, in Clean (which has type classes not functors of course), 
> instants of basic types be prevented from using dictionary passing. Not 
> sure what happens in haskell though...

GHC tries to specialize code which uses overloaded functions during
optimization.

Generally dictionaries are optimized out when the type is statically
known *or* the overloaded function is small enough to be inlined or
explicitly marked as inline (so they will be optimized out at call
site if types are known there).

You can also request generation of specializations of functions or
instances for particular types:

{-# SPECIALISE maximum :: [Int] -> Int #-}
{-# SPECIALISE minimum :: [Int] -> Int #-}
maximum, minimum        :: (Ord a) => [a] -> a
maximum []              =  errorEmptyList "maximum"
maximum xs              =  foldl1 max xs

minimum []              =  errorEmptyList "minimum"
minimum xs              =  foldl1 min xs

You can even substitute arbitrary definitions used for specialized
types; the compiler doesn't check if they have the same semantics.
They are used when the compiler statically knows the type (perhaps
after inlining at call site). For example:

fromIntegral :: (Integral a, Num b) => a -> b
fromIntegral = fromInteger . toInteger

{-# RULES
"fromIntegral/Word8->Int16"  fromIntegral = \(W8# x#) -> I16# (word2Int# x#)
"fromIntegral/Int8->Int16"   fromIntegral = \(I8# x#) -> I16# x#
"fromIntegral/Int16->Int16"  fromIntegral = id :: Int16 -> Int16
"fromIntegral/a->Int16"      fromIntegral = \x -> case fromIntegral x of I# x# -> I16# (narrow16Int# x#)
"fromIntegral/Int16->a"      fromIntegral = \(I16# x#) -> fromIntegral (I# x#)
  #-}

(RULES are even more powerful: the lhs doesn't have to be an identifier).

nhc and Hugs do less optimizations and I would guess they don't
optimize out class dictionaries at all. hbc did some optimizations
and had SPECIALISE pragmas too.

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] functors with style?

[Krishnaswami, Neel]

William Harold Newman [mailto:william.newman@airmail.net] wrote:
> 
> If I did use explicit functor expressions everywhere, it'd be readable
> enough: if my intent is make the things exactly parallel, then using
> the explicit functor expressions everywhere would make that obvious,
> so I'd be happy. But because my previous closest approach to functors
> was using templates in g++, I'm predisposed to worry about the
> compiler emitting multiple copies of the functor expansion if I don't
> give the functor expansion a home in a particular file. Is that an
> issue in Ocaml?

If I understand the papers that the people at INRIA wrote, 
there is no such template-expansion-like problem in Ocaml.

A functor is compiled to what is essentially a function that
takes a record as an argument (the module it receives as an
argument), and returns a record of functions and values. So
code generation happens only once for each functor, and each
functor application takes a very small amount of memory at
link time.

A lot of the issues surrounding functors become much clearer
when you get an operational model for how it works: think of
the ML module language as a small functional language, with
functors mapping to lambdas and functor applications mapping
to function applications. Then your intuition about how
(for example) closures are represented can guide you towards
understanding how modules and functors work. 

When I got this I was seriously impressed with how elegantly
it all works out. (Or as we said in my native South Carolina:
Them ML hackers sure are pretty smart, ain't they? :)

--
Neel Krishnaswami
neelk@cswcasa.com
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] functors with style?

[Shivkumar Chandrasekaran]

On Monday, November 19, 2001, at 10:32 AM, Krishnaswami, Neel wrote:

>
> A functor is compiled to what is essentially a function that
> takes a record as an argument (the module it receives as an
> argument), and returns a record of functions and values. So
> code generation happens only once for each functor, and each
> functor application takes a very small amount of memory at
> link time.
>

Which of course is a problem at the "small-scale". For example I would 
like to develop a functor that is generic over the representation of 
reals (float32_elt, float64_elt, fixed_point, etc.). But now if I 
instantiate it for float64_elt and do arithmetic over float64_elt even 
simple operations will be looked-up at run-time leading to a terrible 
performance loss.

Ideally I would prefer it if the compiler allowed the programmer to 
decide which functor applications lead to compile-time code generation 
and which are through dictionary-passing.

For example, in Clean (which has type classes not functors of course), 
instants of basic types be prevented from using dictionary passing. Not 
sure what happens in haskell though...

--shiv--
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] functors with style?

[Brian Rogoff]

On Mon, 19 Nov 2001, Shivkumar Chandrasekaran wrote:
> On Monday, November 19, 2001, at 10:32 AM, Krishnaswami, Neel wrote:
> > A functor is compiled to what is essentially a function that
> > takes a record as an argument (the module it receives as an
> > argument), and returns a record of functions and values. So
> > code generation happens only once for each functor, and each
> > functor application takes a very small amount of memory at
> > link time.
> 
> Which of course is a problem at the "small-scale". For example I would 
> like to develop a functor that is generic over the representation of 
> reals (float32_elt, float64_elt, fixed_point, etc.). But now if I 
> instantiate it for float64_elt and do arithmetic over float64_elt even 
> simple operations will be looked-up at run-time leading to a terrible 
> performance loss.

Indeed, I find that this very issue has annoyed me for many years. When I 
first started playing with C++ I was involved in scientific computing and 
I was less interested in the OO features than I was in overloading,
templates, and operator redefinition. I'd actually prefer the C++ style 
expansion in the case you describe above, and in many others. 

The other issue I have with functorial programming is the inability to
have types and functor applications in a recursive relationship, but this 
is a well known problem and I think people at INRIA are working on it.

> Ideally I would prefer it if the compiler allowed the programmer to 
> decide which functor applications lead to compile-time code generation 
> and which are through dictionary-passing.

There's also an evil fact that's unkown to many people, namely that 
DEC^H^H^HCompaq^H^H^H^H^H^H, ummm, HP?, has a patent which may cover 
some helpful techniques. DEC had implemented their own Ada 83 compiler, 
and, unlike C++ templates, Ada generics can be implemented by sharing as
well as by "macro expansion", and some of the DEC implementors had
patented a scheme which did both sharing and expansion. I'm not sure if 
this matters, but I can try and find the reference if anyone is really
interested. 

-- Brian
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] functors with style?

[William Harold Newman]

I have some questions about functorial programming style.

First, a general question. I've used the ocaml-3.02 source as an
example when I couldn't guess something about normal style, but it
doesn't seem to use functors much. Since it looks like a great deal of
work has been done on functors, I expect that there are applications
which depend on them. Is there any publicly available Ocaml code which
someone could recommend as an example of good functorial style?

Then, some specific questions about this toy confidence_interval.mli:

module type ORDERING =
  sig
    type t
    val are_ordered: t -> t -> bool
  end

module F:
functor (Ordering: ORDERING) ->
  sig
    type t
    val new_t: Ordering.t -> Ordering.t -> t
    val lo: t -> Ordering.t
    val hi: t -> Ordering.t
  end

module Int:
    sig
      type t
      val new_t: int -> int -> t
      val lo: t -> int
      val hi: t -> int
    end

module Float:
    sig
      type t
      val new_t: float -> float -> t
      val lo: t -> float
    end

As you can see from this example, my impulse is to give names to
modules like $Confidence_interval.Int$ and $Confidence_interval.Float$
(which are defined in confidence_interval.ml as $F(Int_ordering)$ and
$F(Float_ordering)$), but that leads to annoyances:
 * It's annoying to have to specify the redundant signatures for
   $Int_confidence_interval$ and $Float_confidence_interval$.
   They're exactly parallel by intent, so I'd like to 
   construct the signatures with a functor-like thing, but from the
   syntax in section 6.10 of the manual, I'm pretty sure that I can't.
 * I can't find a way to use the $F$ to define anything
   in the top level namespace, e.g. $Int_confidence_interval$
   or $My_custom_type_confidence_interval$, so I end up 
   with  $Confidence_interval.Int$ here and then, when I use $F$
   later for other things, $My_custom_type.Confidence_interval$,
   and the slightly-baroque and not-at-all-parallel names are annoying.

It occurs to me that these annoyances could be avoided by keeping the
functor-constructed modules anonymous, using explicit functor
expressions (e.g. $Confidence_interval.F(Int_order)$ and
$Confidence_interval.F(My_custom_type)$) in any code which uses the
modules. Would that be a good way to do it? Or is there some other
good way?

If I did use explicit functor expressions everywhere, it'd be readable
enough: if my intent is make the things exactly parallel, then using
the explicit functor expressions everywhere would make that obvious,
so I'd be happy. But because my previous closest approach to functors
was using templates in g++, I'm predisposed to worry about the
compiler emitting multiple copies of the functor expansion if I don't
give the functor expansion a home in a particular file. Is that an
issue in Ocaml?

-- 
William Harold Newman <william.newman@airmail.net>
"Furious activity is no substitute for understanding." -- H. H. Williams
PGP key fingerprint 85 CE 1C BA 79 8D 51 8C  B9 25 FB EE E0 C3 E5 7C
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] functors with style?

[Francisco Valverde Albacete]

Hi, please read on,

William Harold Newman wrote:

> I have some questions about functorial programming style.
>
> First, a general question. I've used the ocaml-3.02 source as an
> example when I couldn't guess something about normal style, but it
> doesn't seem to use functors much. Since it looks like a great deal of
> work has been done on functors, I expect that there are applications
>

> which depend on them. Is there any publicly available Ocaml code which
> someone could recommend as an example of good functorial style?

But I think functors are about SW reuse, and most of the solutions in the
distribution should be handcrafted...

|Then, some specific questions about this toy confidence_interval.mli:

>
> module type ORDERING =
>   sig
>     type t
>     val are_ordered: t -> t -> bool
>   end

I suggest you adopted a total ordering like the one in Pervasives.compare here...
It's more useful...
module type TOTAL =
    sig
        type t
        val compare : t -> t -> int
        (* See the conventions in the manual *)
    end


> module F:
> functor (Ordering: ORDERING) ->
>   sig
>     type t
>     val new_t: Ordering.t -> Ordering.t -> t
>     val lo: t -> Ordering.t
>     val hi: t -> Ordering.t
>   end
>
> module Int:
>     sig
>       type t
>       val new_t: int -> int -> t
>       val lo: t -> int
>       val hi: t -> int
>     end
>
> module Float:
>     sig
>       type t
>       val new_t: float -> float -> t
>       val lo: t -> float
>     end
>
> As you can see from this example, my impulse is to give names to
> modules like $Confidence_interval.Int$ and $Confidence_interval.Float$
> (which are defined in confidence_interval.ml as $F(Int_ordering)$ and
> $F(Float_ordering)$), but that leads to annoyances:
>  * It's annoying to have to specify the redundant signatures for
>    $Int_confidence_interval$ and $Float_confidence_interval$.
>    They're exactly parallel by intent, so I'd like to
>    construct the signatures with a functor-like thing, but from the
>    syntax in section 6.10 of the manual, I'm pretty sure that I can't.

You should make use of signatures in defining and constraining these modules as
well:
module type INTERVAL =
    sig
        type bound
        type t
        val new_t : bound -> bound -> t
        val hi : t -> bound
        val lo : t -> bound
    end

then build the functor like:

module F:
    functor (Order : TOTAL) ->
    sig
        include INTERVAL with type bound = Order.t
        (* you can constrain further here
    end

module Int : INTERVAL with type bound = int

module Float : INTERVAL with type bound = float
    (* there's a spurious fun "hi" here, but you could take that away as well *)

>  * I can't find a way to use the $F$ to define anything
>    in the top level namespace, e.g. $Int_confidence_interval$
>    or $My_custom_type_confidence_interval$, so I end up
>    with  $Confidence_interval.Int$ here and then, when I use $F$
>    later for other things, $My_custom_type.Confidence_interval$,
>    and the slightly-baroque and not-at-all-parallel names are annoying.

SUpposing:
module TotalInt = struct type t = int let compare = (-) end
module TotalFloat = struct type t = float let compare = (Pervasives.compare: float
-> float -> int)

exist then you shoul be able to make:

module IntInterval = Confidence_interval.F (TotalInt)
module FloatInterval = Confidence_interval.F (TotalFloat)

> It occurs to me that these annoyances could be avoided by keeping the
> functor-constructed modules anonymous, using explicit functor
> expressions (e.g. $Confidence_interval.F(Int_order)$ and
> $Confidence_interval.F(My_custom_type)$) in any code which uses the
> modules. Would that be a good way to do it? Or is there some other
> good way?

If you wnat to re-use any of these XXIntervals, then provide them in a library
module of their own like
interval_basics (this is where I create and export heavily used instantiations of
functors). Otherwise just
use, abuse and dispose of them in an application.

> If I did use explicit functor expressions everywhere, it'd be readable
> enough: if my intent is make the things exactly parallel, then using
> the explicit functor expressions everywhere would make that obvious,
> so I'd be happy. But because my previous closest approach to functors
> was using templates in g++, I'm predisposed to worry about the
> compiler emitting multiple copies of the functor expansion if I don't
> give the functor expansion a home in a particular file. Is that an
> issue in Ocaml?

Hum!! Functor application, I guess, is not to be used casually, as functions
applications. It incurs in heavy costs in my experience... Better instantiate
modules in libraries, and then reuse... You can make some nice initialisation of
objects by mixing module instantiation and object creation within them...

Regards,

            Francisco Valverde


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr