[Caml-list] [Q]: Co(ntra)variance and subtyping?

[Caml-list] [Q]: Co(ntra)variance and subtyping?

[Clemens Hintze]

Hello,

I am already lurking on this list for some days. Now I would like to
introduce myself. To earn my living I am working for a company writing
software in area of transportation automatisation. There we are using
mainly C/C++, PL/SQL, Perl and some other scripting languages.

But programming is not only my business but also my hobby. So I try to
grasp as much different paradigms and languages as I can get. The
imperative and declarative programming (using Prolog) is already known
to me (I have not said 'mastered' ;-).

Now I have thought about learning functional programming. I had a
closer look to OCaml, Haskell and Erlang for ca. two weeks. Although
Haskell has impressed me a lot and nearly won me, I had decided to
begin my first steps in OCaml. Partly due to the fact that the
paradigms I am already comfortable with, are also supported, partly
because of its really nice type inference scheme and modularity
capabilities and last but not least due to the fact, that OCaml offers
very nice compilers and a very comprehensive library to work with.

But where is light, there is also some shadow. I find OCaml a really
complex language -- perhaps more complex than Haskell. But, ey, C++ or
Perl also can hardly be called a simple language, isn't it? And I was
able to gain enough knowledge to use C++ successfully at my daily
work.  So I think complexity should not hinder me :-)

As I have decided to learn OCaml, I am sure that I will have several
questions in future, that I would like to ask here on the list, as I
found comp.lang.functional do not seem very busy with OCaml topics.

Two things I would like to ask you right now:

- What does subtyping exactly mean in OCaml resp. functional
  programming?
- What means covariance and contravariance of types and subtypes?

I have already learned that in OCaml classes are not types like in
C++. So subclasses are not be considered as subtypes. But those
co(ntra)variance thingy?  I have read many messages of that list in
the archive. I have found some messages that deal with those terms. I
have also read the OCaml documentation. I think I've got a feeling
what it could mean, but if I should explain it to others, I would
surely fail, i.e. I would not bet my life that I have understood these
terms ;-)

OTOH, these terms seem to be very important in dealing with OCaml or
functional programming.

So excuse me, if I ask a very stupid question, but I really had not
found any me-convincing answer to this. Google also did not help me
here.

So if you wouldn't mind, please try to explain those terms to me. If
possible with some examples.

Let me thank you all in advance and happy OCaml'ing :-)


Regards,
Clemens.

PS: Sorry, if my english is not flawless, but it is not my
    mother-tongue, and I do not speak french a bit, unfortunately.

--
Clemens Hintze  mailto: c.hintze@gmx.net
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Mark Wotton]

On Fri, 16 Nov 2001, Clemens Hintze wrote:

> Two things I would like to ask you right now:
> 
> - What does subtyping exactly mean in OCaml resp. functional
>   programming?
> - What means covariance and contravariance of types and subtypes?

Not being an Ocaml guru, I shan't attempt the first question.
The second's pretty easy, though: covariance is the sane way of doing OO,
and contravariance is bizarre. (Right, if there's any Eiffel devotees on
here, I've just started a flamewar. :)

Seriously: contravariance breaks the assumption that a subtype is capable
of everything that its parent can do. Essentially, it allows you to narrow
arguments to functions: to use some weird eiffelish pseudocode i had
lying around, you can do this.

class bar

class bar_child is bar

class garment public foo(b: bar ) 
class toga is garment public foo(b: bar_child)
/* narrowing the argument of foo */


class tester public main = let p:garment = toga{} in p.foo(bar{})
/* attempting to call foo method of toga object using object of type bar:
   fails at runtime */


Basically, you expect to be able to call "foo" on any garment, and the
only requirement is that the argument be of type "bar". "toga" narrows it
to "bar_child" and the whole thing falls down in a heap.

Covariance doesn't let this happen. You can actually widen the type in a
child class, I believe: this isn't generally particularly useful, though.


> Regards,
> Clemens.
> 
> PS: Sorry, if my english is not flawless, but it is not my
>     mother-tongue, and I do not speak french a bit, unfortunately.

It's an odd thing: most of the posts with apologies for bad English I've
seen on Usenet have been flawless as far as composition goes.

mrak


-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Mark Wotton]

On Sun, 18 Nov 2001, Mark Wotton wrote:

> On Fri, 16 Nov 2001, Clemens Hintze wrote:
> 
> > Two things I would like to ask you right now:
> > 
> > - What does subtyping exactly mean in OCaml resp. functional
> >   programming?
> > - What means covariance and contravariance of types and subtypes?
> 
> Not being an Ocaml guru, I shan't attempt the first question.
> The second's pretty easy, though: covariance is the sane way of doing OO,
> and contravariance is bizarre. (Right, if there's any Eiffel devotees on
> here, I've just started a flamewar. :)

Of course, in a post talking about someone else's English, it's almost
inevitable that I'm going to get it wrong myself. s/there's/there are/g.

mrak
looking forward to the mistake in this one.


-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Clemens Hintze]

Mark,

let me first thank you for trying to answer my question. But
unfortunately I am still not convinced, that I properly understood it
...

On Sun, Nov 18, 2001 at 01:18:22AM +1100, Mark Wotton wrote:
> On Fri, 16 Nov 2001, Clemens Hintze wrote:
> 
> > Two things I would like to ask you right now:
> > 
> > - What does subtyping exactly mean in OCaml resp. functional
> >   programming?
> > - What means covariance and contravariance of types and subtypes?
> 
> Not being an Ocaml guru, I shan't attempt the first question.
> The second's pretty easy, though: covariance is the sane way of doing OO,
> and contravariance is bizarre. (Right, if there's any Eiffel devotees on
> here, I've just started a flamewar. :)

I am not a Eiffel devotee, so nothing to fear here from me ;-)

> Seriously: contravariance breaks the assumption that a subtype is capable
> of everything that its parent can do. Essentially, it allows you to narrow
> arguments to functions: to use some weird eiffelish pseudocode i had
> lying around, you can do this.

As I have understood, co(ntra)variance has someting to do with types
and not with classes, right? And classes in OCaml are not types, right
too?

So it should not an issue about subclassing, if I understood
correctly. So there has to be more about these, as only in area of
OOP, shouldn't it?

I can understand your explanation, though, but I fear that there is
something more that is not covered by this example. What I have found
during investigating this question via google and the mailinglist
archive was this:

- Covariance means that a specialized class also specialize the
  arguments of overloaded methods. You use 'narrow' instead of
  'specializing' ...
- Contravariance, however, is generalizing arguments of overloaded
  methods in specialized classes.

So in this light, your example should demonstrate covariance, isn't
it? But what I do not like in the explanation above, is that it also
only refer to OOP and not types. 

Another explanation I've found, was (a --> b means a subtypes b):

- Covariance means, that if t' --> t ==> t' list --> t list
- Contravariance, however, if t' --> t ==> t list --> t' list

This explanation is not based on OOP, fine! But to be honest, I do not
understand this explanation nor its consequences. I would not be able
right now, to build an example describing this above ... :-(

And then there is still the term 'invariance' that I've even not asked
so far (hoping it will explain itself if I had understand the other
variances so far) :-/

So I need the explanation about type, subtype, co(ntra)variance,
invariance and all these in OO and non-OO in OCaml.

> It's an odd thing: most of the posts with apologies for bad English I've
> seen on Usenet have been flawless as far as composition goes.

Thank you for this :-)

I know that my english should be good enough for being understood. But
sometimes, some wrong phrases seem to spring in, and other feel
necessary to flame me, then. So if I am new to a group, I want to
state, that I am not a native speaker, hoping others will be mercy
instead of flaming me :-)


Ciao,
Clemens

-- 
Clemens Hintze  mailto: c.hintze@gmx.net
-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Mark Wotton]

On Sat, 17 Nov 2001, Clemens Hintze wrote:

> - Covariance means that a specialized class also specialize the
>   arguments of overloaded methods. You use 'narrow' instead of
>   'specializing' ...
> - Contravariance, however, is generalizing arguments of overloaded
>   methods in specialized classes.
> 
> So in this light, your example should demonstrate covariance, isn't
> it? But what I do not like in the explanation above, is that it also
> only refer to OOP and not types. 

You're quite right. I had it the wrong way around. Too little sleep...

> Another explanation I've found, was (a --> b means a subtypes b):
> 
> - Covariance means, that if t' --> t ==> t' list --> t list

With this relationship, you would expect that "t' list" would be able to
do anything that "t list" could do, as it's a subtype: therefore, you'd
expect to be able to add a t to the front. With covariance, you
can't: it's expecting the more specialised type t'.

> - Contravariance, however, if t' --> t ==> t list --> t' list

This way, you can take "t list" and add either "t" or "t'" to the
front. Therefore, "t list" can do anything that "t' list" can, and the
intuitive notion of subtypes is preserved.

Apologies for getting it wrong the first time. It's doubly embarrassing as
it seems I made the same mistake in the thesis I just handed in...

mrak


-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Clemens Hintze]

On Sun, Nov 18, 2001 at 10:17:51AM +1100, Mark Wotton wrote:

(...)

> This way, you can take "t list" and add either "t" or "t'" to the
> front. Therefore, "t list" can do anything that "t' list" can, and
> the intuitive notion of subtypes is preserved.

Ahh ... I have the slight feeling, that I slowley get it ... thank
you. But I have to ask some more qustions to be sure ...

- In the context you have mentioned above: 'invariant' means the two
  types have *no* relationship to each other, yes?
- If you believe that contravariance isn't generally particularly
  useful, as you stated in the mail before, why can I flag some type
  with (-'a) stating this is contravariant? What sense does this make?  
- What exactly are types and subtypes in OCaml? You know, I am coming
  mainly from the imperative world. There I use languages that makes
  no distinction between classes and types. Is 'int' a subtype of
  'float'? How can I decide if something is a subtype of another one?
  I do not ask in sense of OO inheritance but in OCaml terminology.
  
> Apologies for getting it wrong the first time. It's doubly
> embarrassing as it seems I made the same mistake in the thesis I
> just handed in...

Its ok for me that you get it wrong, because so I could detect the
flaw and ensure myself that I am of the way of understanding. But that
you probably had made same mistake in thesis is really unfortunate for
you, and I feel a pity therefore :-(


Thanks again and ciao,
Clemens.
-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Alain Frisch]

On Sun, 18 Nov 2001, Clemens Hintze wrote:

> - If you believe that contravariance isn't generally particularly
>   useful, as you stated in the mail before, why can I flag some type
>   with (-'a) stating this is contravariant? What sense does this make?

> - What exactly are types and subtypes in OCaml? You know, I am coming
>   mainly from the imperative world. There I use languages that makes
>   no distinction between classes and types. Is 'int' a subtype of
>   'float'? How can I decide if something is a subtype of another one?
>   I do not ask in sense of OO inheritance but in OCaml terminology.

If you don't do OO, you can live with OCaml without knowing what 'subtype'
means.

Types in Caml are syntactical expressions, whose full syntax is
given in section 6.4 of OCaml user's manual. As types may contain type
variables, there is a natural order 'less general' induced by
instantiating type variables. The type inference algorithm allows to
take instances, that is to use an expression of a more general type where
a less general type is expected. (this is an unaccurate description of the
algorithm).

What about objects ?  Let's have a look at:

# let f x = (x # value) + 1;;
val f : < value : int; .. > -> int = <fun>

The function f accepts any object with a method value (returning an int)
and possible others: the ".." really denotes a type variable that can
be instantiated to a row of other methods.

# class o = object method value = 2  method str = "abc" end;;
class o : object method str : string method value : int end
# f (new o);;
- : int = 3

Here ".." is instantiated with (str : string). This kind of type matching
allows to use objects with extra methods in a context that expects only
some methods. More precisely, it is the context that accepts more methods.

What you can't do with that is for instance:

# class o = object method x = 2  method y = "abc" end;;
class o : object method x : int method y : string end
# class p =  object method x = 3 end;;
class p : object method x : int end
# [new o; new p];;
This expression has type p = < x : int > but is here used with type
  o = < x : int; y : string >
Only the second object type has a method y


A list in OCaml is homogeneous: all the elements must have the _same_
type; you could say that [new o; new p] has type < x : int; .. > list,
but then ".." has to be unified with (y : string) and ()  [the empty
row of methods], which is impossible.

Here you have to help the type system, and coerce both objets
to a common supertype:

# type t = < x : int >;;
type t = < x : int >
# [(new o :> t); (new p :> t)];;
- : t list = [<obj>; <obj>]

Coercing to a supertype amounts to forget some methods (which is safe,
but never done automatically).

Now there is a subtyping relation on object types. But it is handy to have
it also on constructed types:

# let l1 = [new o; new o] and l2 = [new p; new p];;
val l1 : o list = [<obj>; <obj>]
val l2 : p list = [<obj>; <obj>]
# (l1 :> t list) @ (l2 :> t list);;
- : t list = [<obj>; <obj>; <obj>; <obj>]

To make l1 and l2 compatible, we again use a coercion, but now, we use
the subtyping relation over lists:  "o list is a subtype of
t list _because_ o is a subtype of t". This express the covariance
of the list type constructor.

Some constructors are contravariant. For instance, the arrow constructor
t->s is contravariant in t and covariant in s. This means that:
t1->s1 is a subtype of t2->s2 if and only if t2 is a subtype
of t1 and s1 is a subtype of s2. If the arrow constructor was
considered covariant in both arguments, it would be easy to break
the type system (runtime type error) with a coercion.


And some constructors are invariant, such as:
type 'a inv = A of 'a | B of 'a -> unit

t1 inv is a subtype of t2 inv if and only if t1 and t2 are equal
(modulo the subtyping relation).


Now, if you don't have the definition of a type constructor - say
it is an abstract type from your point of view -
you can't tell what its variance is w.r.t one of its arguments.
So OCaml allows to specify this information in module interface;
for instance, in map.mli:

module type S =
  sig
    type key
          (* The type of the map keys. *)
    type (+'a) t
          (* The type of maps from type [key] to type ['a]. *)
...


The '+' means that type t is covariant: a map from type key to type
t1 can be coerced to a map from type key to type t2 if and only
if t1 is a subtype of t2.

(I don't know why other modules such as Queue do not give variance
information ...)


So, the subtyping relation is only raised from object types to
all types using variance information for each type constructor
(actually, subtyping can also appears with polymorphic variants).
There is no subtyping between basic types: int is not a subtype of float.

One reason for it is that in OCaml, coercion to a super type does not
require any computation, thanks to the concrete representation of objects.
So coercing a list does not involve walking through all its elements.
As int representation is not compatible with float one, int is not a
subtype if float.



-- 
  Alain

-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Remi VANICAT]

Alain Frisch <frisch@clipper.ens.fr> writes:

> Now, if you don't have the definition of a type constructor - say
> it is an abstract type from your point of view -
> you can't tell what its variance is w.r.t one of its arguments.
> So OCaml allows to specify this information in module interface;
> for instance, in map.mli:
> 
> module type S =
>   sig
>     type key
>           (* The type of the map keys. *)
>     type (+'a) t
>           (* The type of maps from type [key] to type ['a]. *)
> ...
> 
> 
> The '+' means that type t is covariant: a map from type key to type
> t1 can be coerced to a map from type key to type t2 if and only
> if t1 is a subtype of t2.
> 
> (I don't know why other modules such as Queue do not give variance
> information ...)

because Queue are neither covariant nor contravariant :
- a Queue contain things, so it can't be contravariant,
- you can add things to queue, so it can't be covariant
infact, most of the mutable thing are neither contravariant nor
covariant. 
-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Marcin 'Qrczak' Kowalczyk]

Disclaimer: I have no experience in OCaml's object system.

Sun, 18 Nov 2001 10:16:36 +0100, Clemens Hintze <cle-ocaml@qiao.in-berlin.de> pisze:

> - In the context you have mentioned above: 'invariant' means the two
>   types have *no* relationship to each other, yes?

Yes.

> - If you believe that contravariance isn't generally particularly
>   useful, as you stated in the mail before, why can I flag some type
>   with (-'a) stating this is contravariant? What sense does this make?

For a concrete type you have little choice: either the type definition
allows covariant changes of the parameter type (list is an example of
such type), or it allows contravariant changes (type 'a f = 'a -> unit
is an example), or it doesn't allows any changes (array is an example).
It follows either from type definition (in the case of algebraic types)
or from primitive operations provided (for primitive types).

The compiler infers variance of concrete types itself. Explicit
annotations are useful for concrete types where it's not yet known
which type will be substituted. Abstract types are invariant by
default and in such case any type can be substituted (you will be
able to make use of its variance only in places where it's known
which concrete type is used).

You can mark an abstract type as covariant and then only covariant
concrete types can be substituted when matching a module to a module
type. Similarly - contravariant.

A concrete type can also allow both variances (if the type variable
of its parameter is not used in its body). AFAIK there is no syntax
to mark abstract types as such - it has little use anyway.

> - What exactly are types and subtypes in OCaml?

Subtypes are generated by object types (by including more methods,
or having the same method names with subtypes as their types),
by using a subtype as a parameter to a covariant type, by using a
supertype as a parameter to a contravariant type, and from making
this relation reflexive and transitive.

I don't know if that's all. I'm not sure how polymorphic variant types
interact with this. They are surely covariant wrt. argument types,
but coercions which extend the type by including more variants can
be implicit - they don't need the :> operator.

-- 
 __("<  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] [Q]: Co(ntra)variance and subtyping?

[Andreas Rossberg]

> - What does subtyping exactly mean in OCaml resp. functional
>   programming?

OCaml has two separate notions of subtyping:

- in the core language, to support objects
- in the module language, for signature matching

While subtyping for module types is rather standard from a superficial point
of view, OCaml's treatment of subtyping in the core language is somewhat
special because it does not provide so-called subsumption. Subsumption means
that wherever a value of type t is expected you may freely provide a value
of some subtype t'. This is not the case in OCaml: you have to explicitly
coerce the value to the required supertype first. This is necessary to make
type inference feasible.

Note however that OCaml's object system rarely requires the use of
subtyping, because it mainly relies on row polymorphism, which is more or
less superior (although it admittedly complicates things to have both).

> - What means covariance and contravariance of types and subtypes?

Variance is a property of type constructor arguments. Take the "list" type
constructor for example: it is said to be covariant in its argument because
it comes with the following subtyping rule:

    t' < t     =>     t' list < t list

where "<" stands for "is subtype of". This means that you can use a t' list
as a t list - the list type "varies" in the same direction as its argument,
thus the term "covariance".

The most important type constructor is "->", which has the following
subtyping rule:

    t' < t and u' < u    =>    (t -> u') < (t' -> u)

Note the order of t and t' here: it goes in the opposite direction!
Functions are covariant in their result type, but contravariant in their
argument type. This may seem a bit funny at first (and in fact there are
major programming languages that still insist on getting it plainly wrong -
you already know one ;-) but it is the only sound rule. Intuitively it means
that a function type is a subtype of another function type if it produces a
more specific result while putting less requirements on its argument.

In general, you have covariance for type components that are "produced" or
"readable", and contravariance for components that are "consumed" or
"writable". Another example of contravariance would be a polymorphic output
channel.

Of course, you cannot have both co- and contravariance for the same
argument. So if some type component is both readable and writable then it
has to be invariant. Consider arrays for example: there is no subtyping
relation between any two array types t array and u array, no matter what
relation t and u are in (with the only exception of t=u, then of course you
trivially have `subtyping' in either direction). In fact, mutable types
always have to be invariant (another thing that many popular OO languages do
wrong - some at least do runtime checks for compensation, some just crash).

> OTOH, these terms seem to be very important in dealing with OCaml or
> functional programming.

I hope my explanations clarified that these terms are mainly important if
you do OO in the presence of polymorphic types. Functional programming in
its purer forms usually does not use nor require subtyping, so need not
bother with them ;-)

Cheers,

    - Andreas


-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Pixel]

"Andreas Rossberg" <AndreasRossberg@web.de> writes:

> > - What does subtyping exactly mean in OCaml resp. functional
> >   programming?
> 
> OCaml has two separate notions of subtyping:
> 
> - in the core language, to support objects
> - in the module language, for signature matching
> 
> While subtyping for module types is rather standard from a superficial point
> of view, OCaml's treatment of subtyping in the core language is somewhat
> special because it does not provide so-called subsumption.

well, you forgot polymorphic variants, which do use subsumption:

# let switch = function `On -> `Off | x -> x;;
val switch : ([> `Off | `On] as 'a) -> 'a = <fun>
# (switch `On, switch `Whatever);;
- : _[> `Off | `On] * _[> `Off | `On | `Whatever] = `Off, `Whatever

> Subsumption means
> that wherever a value of type t is expected you may freely provide a value
> of some subtype t'. This is not the case in OCaml: you have to explicitly
> coerce the value to the required supertype first. This is necessary to make
> type inference feasible.

necessary is a small overstatement ;p

[...]

> The most important type constructor is "->", which has the following
> subtyping rule:
> 
>     t' < t and u' < u    =>    (t -> u') < (t' -> u)
> 
> Note the order of t and t' here: it goes in the opposite direction!
> Functions are covariant in their result type, but contravariant in their
> argument type. This may seem a bit funny at first (and in fact there are
> major programming languages that still insist on getting it plainly wrong -
> you already know one ;-)

if you want more about it, read the nice paper from Giuseppe Castagna:

Covariance And Contravariance: conflict Without A Cause 
  http://citeseer.nj.nec.com/castagna95covariance.html
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Jacques Garrigue]

From: Pixel <pixel@mandrakesoft.com>

> > While subtyping for module types is rather standard from a
> > superficial point of view, OCaml's treatment of subtyping in the
> > core language is somewhat special because it does not provide
> > so-called subsumption.
> 
> well, you forgot polymorphic variants, which do use subsumption:
> 
> # let switch = function `On -> `Off | x -> x;;
> val switch : ([> `Off | `On] as 'a) -> 'a = <fun>
> # (switch `On, switch `Whatever);;
> - : _[> `Off | `On] * _[> `Off | `On | `Whatever] = `Off, `Whatever

This, again, is row polymorphism, not subsumption.
The difference between (row/parametric) polymorphism and subsumption
is that for the former you must explicitely leave some free variable
in the type (the presence of which is proved by the "as 'a" or "_"),
while the latter also works on ground types (without variables).
Both polymorphic variants and objects uss both polymorphism and
subtyping, but without implicit subsumption.

> > Subsumption means that wherever a value of type t is expected you
> > may freely provide a value of some subtype t'. This is not the
> > case in OCaml: you have to explicitly coerce the value to the
> > required supertype first.  This is necessary to make type
> > inference feasible.
> 
> necessary is a small overstatement ;p

No, feasible should be defined more precisely :-)
In the ML world, we mean complete type inference. For this explicit
coercions are indeed necessary. If you're satisfied with partial
inference, then you may find disciplines where some coercions can be
inferred.

Cheers,

Jacques Garrigue
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[David Gurr]

X. Leroy has slides from lectures which can be reached from
his homepage (the second lecture is the one you want).  From 
www.ocaml.org, go to project crystal, personel, X.Leroy, 
teaching/lectures, or something like that.
-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Clemens Hintze]

I want to thank you all, who have contributed to answer my questions
about co(ntra)variance. Now I will have to read it all for a few times
(I guess a dozent will enough ;-) to try to understand what you gurus
tried to tell me ;-))

When I've reached that state, I would like to post a summary to beg
your comments to see, if I reached knowledge or not. In that summary,
there may pop up further questions, if something is still not clear to
me.

It may take some days for the dozent concentrated readings, though.

Thanks again for all help.


Ciao,
Clemens.

PS: Thanks also to Mark Wotton.
-------------------
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] Re: [Q]: Co(ntra)variance and subtyping?

[Markus Mottl]

Clemens Hintze schrieb am Montag, den 19. November 2001:
> I want to thank you all, who have contributed to answer my questions
> about co(ntra)variance. Now I will have to read it all for a few times
> (I guess a dozent will enough ;-) to try to understand what you gurus
> tried to tell me ;-))

Maybe a small excursion to logic makes things easier to understand. Just
consider types as propositions about values, for example "x is an integer"
or "f maps a foo to a bar". Let's focus on the latter case:

  foo -> bar  (1)

Whenever we find a case where "foo" holds (whenever we have a value of
type "foo"), then this implies "bar" (the result of function "f" will be
"bar").

We now add further elements to the type "bar", getting type "super_bar"
(it is a super type of the former by definition). Logically speaking,
this means:

  bar -> super_bar  (2)

Together with proposition (1), this allows us to derive:

  foo -> super_bar  (3)

One can prove this easily (e.g. using truth tables) by showing that the
following is a tautology (holds irrespective of our interpretation of
"foo" and "bar"):

  (foo -> bar) /\ (bar -> super_bar) -> (foo -> super_bar)  (4)

Therefore, if some context expects a function of type "foo -> super_bar",
(expects that "foo -> super_bar" holds), then it is sound to substitute
a function of type "foo -> bar" in it, given that "bar -> super_bar"
holds. The term that applies here is "covariance", because making
the proposition "bar" weaker (letting it apply to additional cases,
i.e. making it less strict) also makes "foo -> bar" weaker (and
vice-versa).

Let's consider adding elements to "foo" now, getting super type
"super_foo":

  foo -> super_foo  (5)

Would it be sound to assume the following? -

  (foo -> bar) /\ (foo -> super_foo) -> (super_foo -> bar)  (6)

Just try to prove this a tautology, and you'll quickly find out
that it isn't! It is also not an invalid argument (i.e. not false in
general), its satisfiability "depends". Surely, nobody would want to have
computer programs whose correctness "depends" on possibly unpredictable
eventualities!

In which cases can we safely assume that (6) holds? This is only the
case when our value of type "super_foo" is still a "foo" (which actually
means that "super_foo" must be a subtype of "foo"!):

  super_foo -> foo  (7)

But together with (5) this means that both types must be equivalent:

  super_foo <-> foo  (8)

Not very interesting a case for programmers. But this one looks much
nicer:

   (sub_foo -> foo) /\ (foo -> bar) -> (sub_foo -> bar)  (9)

Because we can easily prove that this is valid, we see that we have to
make the proposition "foo" stronger (apply to a subset only) to make
"foo -> bar" weaker (apply more generally).  We call this requirement of
making something "stronger" to get something "weaker" (and vice-versa)
"contravariance" as opposed to "covariance", which goes with weaker/weaker
(more general / more general) and stronger/stronger (more specific /
more specific).

Some OO-languages (e.g. Eiffel) assume that (6) always holds (is a
tautology). But this is unsound as we have seen, and one can therefore
find cases, where static type safety will break, which will either crash
the program or require expensive runtime checks.

I hope the logicians among you will now clean out all flaws in my
example... :-)

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Xavier Leroy]

> X. Leroy has slides from lectures which can be reached from
> his homepage (the second lecture is the one you want).  From 
> www.ocaml.org, go to project crystal, personel, X.Leroy, 
> teaching/lectures, or something like that.

A more comprehensive introduction to (and comparison between) objects,
classes and modules in OCaml can be found in Didier Rémy's APPSEM
course notes:
        http://pauillac.inria.fr/~remy/cours/appsem/

- Xavier Leroy
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Alain Frisch]

On Mon, 19 Nov 2001, Jacques Garrigue wrote:

> In the ML world, we mean complete type inference.

What does complete type inference mean ?  I would say that it implies
that no type annotation is mandatory (if a program typechecks with a type
annotation, it should also typecheck without). This property does not hold
in OCaml; you can't remove type annotation in:

class o = object method f (x : int) = x end

or in the toplevel structure:

let f () : [`A] = `A
let x = f ()


-- 
  Alain

-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Didier Remy]

Alain Frisch <frisch@clipper.ens.fr> writes:

> > In the ML world, we mean complete type inference.
> 
> What does complete type inference mean ?  I would say that it implies
> that no type annotation is mandatory (if a program typechecks with a type
> annotation, it should also typecheck without). This property does not hold
> in OCaml; you can't remove type annotation in:
> 
> class o = object method f (x : int) = x end

Just to mention that examples can also be found in (almost) the core
language as well, you could choose ``ref []'' alone, which program will be
rejected by the compiler.

                              ----------------

I take this opportunity to raise a question about the meaning of "type
inference". Indeed, the answer of whether a language has type inference may
be more subtle than it first appears.  Checking whether types are/must be
mentioned in source programs may not be sufficient. Consider data-type
declarations:

        type 'a list = [] | Cons of 'a * 'a list 

Is this a type annotation?  Indeed, this declaration amounts to later
implicitly annotate every occurrence of a Cons as carrying arguments of
types 'a and 'a list.

The situation apparently looks simpler for the raw lambda-calculus, which
comes in two flavors untyped and typed and where the untyped version does
not mention types at all.  However, there is no untyped version of ML (with
datatypes/exceptions, etc.)  in the sense that types would not be mentioned
at all.

Even in the lambda-calculus it should be fair to consider that (fun x -> a)
carries the (implicit) type annotations ('a -> 'b).  So, isn't it unfair to
make a difference between type annotations that are plugged into the syntax
and more elaborated type annotations that would are explicitly in the
syntax. Formally, the distinction is not obvious: syntactic nodes (_ : t)
can well be seen as (i.e. replaced by) built-in primitives of types t -> t
(and given the same semantics as the identity).

Hopefully, there is always a lot of type information in programs, whether it
is implicit or explicit ---otherwise, type inference could not do much.
Furthermore, the difference between explicit and implicit annotations is not
always so clear, certainly not a binary notion.

My conclusions are that 

 - the typed and untyped version cannot be left implicit when talking about
type inference.

 - the property of ``having type inference'' should rather be replaced by a
measure of ``how much type inference'' (1) or ``what are the properties of
type inference'' (2). 

Answers to (2) the later can be made formal.  Answers to (1) tend to be
informal ---but it would be interesting to find a formal criteria...

        Didier Rémy
-------------------
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] [Q]: Co(ntra)variance and subtyping?

[Pixel]

Jacques Garrigue <garrigue@kurims.kyoto-u.ac.jp> writes:

[...]

> > well, you forgot polymorphic variants, which do use subsumption:
> > 
> > # let switch = function `On -> `Off | x -> x;;
> > val switch : ([> `Off | `On] as 'a) -> 'a = <fun>
> > # (switch `On, switch `Whatever);;
> > - : _[> `Off | `On] * _[> `Off | `On | `Whatever] = `Off, `Whatever
> 
> This, again, is row polymorphism, not subsumption.
> The difference between (row/parametric) polymorphism and subsumption
> is that for the former you must explicitely leave some free variable
> in the type (the presence of which is proved by the "as 'a" or "_"),
> while the latter also works on ground types (without variables).

# let switch = function `On -> `Off | `Off -> `On;;
val switch : [< `On | `Off] -> [> `Off | `On] = <fun>
# `On;;
- : [> `On] = `On
# switch `On;;
- : _[> `Off | `On] = `Off

I still call this subsumption.

> Both polymorphic variants and objects uss both polymorphism and
> subtyping, but without implicit subsumption.

The subsumption is not implicit is the type of "switch", but it is implicit in
the use of the function. It is also implicit in the definition of "switch".
That's why for the programmer, it is subsumption.
-------------------
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] Re: variance, subtyping and monads... oh, my!

[james woodyatt]

everyone--

I would like to thank all of the OCaml experts who contributed responses 
to the thread about co-variance, contra-variance and subtyping issues.  
It helped me confirm for myself that I have a good intuitive grasp of 
the subject.  The next step is learning how to teach it.

I'm grateful for the bit about the binomial function type constructor 
that I can conceptually think about like this:

   type (+'domain,-'range) (->) = <fun>  (* yeah, this is pseudo-syntax *)

That helped a great deal.  Gives me a way to describe something I've 
never liked about C++ and Java.

Oh, and I have a quip to add to the mix, and a question of my own:

On Sunday, November 18, 2001, at 05:34 , Andreas Rossberg wrote:
>
> I hope my explanations clarified that these terms are mainly important 
> if
> you do OO in the presence of polymorphic types. Functional programming 
> in
> its purer forms usually does not use nor require subtyping, so need not
> bother with them ;-)

<quip>How do you do OOP in the *absence* of polymorphic types?</quip>

Now for the question.  First the background:

I'm guessing that these "purer forms" of functional programming involve 
convoluted gyrations with monads and the higher order "things" that you 
can construct with them by layering them one on top of the other.  (What 
would you call those things?  Molecules?)

Now, is it my imagination, or is all that research into what you can 
build out of monads primarily a way for Haskell people to rediscover 
everything we already know about polymorphism, inheritance and 
encapsulation?

My approach for abstracting DNS resource record types so that my client 
and server implementations have a modular interface for section 
processing uses polymorphic variant types and module signatures.  It 
seems pretty lightweight and does what I want.

For a brief moment there, I had this nagging concern that maybe I should 
learn more about these "monad" things before I move on to implementing 
the DNS client and server modules.  I looked into it a little bit, and I 
decided to stick with the interface I have.

As near as I can tell, OCaml doesn't keep me from building monads if I 
really feel a deep and burning need to do so, but for the life of me I 
can't figure out what I might get out of it that would be useful and new.

The covariant polymorphic type parameter trick that I saw posted to this 
list a month or so ago seems to produce the same degree of encapsulation 
and polymorphism I can get with a monad, and I don't *seem* to have all 
the overhead associated with lazy evaluation and building mad closure 
chains all over the place.

Here's my question: Am I missing some important clue about what monads 
will get me?  Other than further advancement in the Order of the Mystic 
Knights of the Lambda Calculus, of course.


--
j h woodyatt <jhw@wetware.com>
"...the antidote to misinformation is more information, not less."
                                                      --vinton cerf

-------------------
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] Re: variance, subtyping and monads... oh, my!

[Francois Pottier]

Hello everyone,

Just a few thoughts about this discussion. As Andreas and Alan said, there is
no need to understand ocaml's object system in order to experiment with
functional programming. The core features of ocaml are functions, (possibly
mutable) data structures and pattern matching, exceptions, and modules. These
features do not require subtyping at all. Notions of subtyping appear when
using objects or so-called `polymorphic' variants.

James Woodyatt wrote:
> I'm guessing that these "purer forms" of functional programming involve 
> convoluted gyrations with monads and the higher order "things" that you 
> can construct with them by layering them one on top of the other.

I don't think that's what Andreas meant. I think `pure' merely meant
`non-OO' here.

> Now, is it my imagination, or is all that research into what you can 
> build out of monads primarily a way for Haskell people to rediscover 
> everything we already know about polymorphism, inheritance and 
> encapsulation?

Isn't that a bit harsh? Monads offer abstraction with respect to the way
certain side effects are performed. Because of ocaml's natural support for
many side effects (references, exceptions, I/O, ...), monads are seldom
needed in ocaml. Furthermore, because of ocaml's lack of support for
overloading, their use is more cumbersome in ocaml than in Haskell.

Nevertheless, I am sure there are situations where abstracting your code
with respect to a monad is desirable. For instance, if you're writing
non-deterministic code, you may want the machinery that explores multiple
threads of evaluation, handles backtracking, etc. to be hidden inside a
monad.

> As near as I can tell, OCaml doesn't keep me from building monads if I 
> really feel a deep and burning need to do so, but for the life of me I 
> can't figure out what I might get out of it that would be useful and new.

Sounds perfectly OK.

-- 
François Pottier
Francois.Pottier@inria.fr
http://pauillac.inria.fr/~fpottier/
-------------------
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] Re: variance, subtyping and monads... oh, my!

[james woodyatt]

On Monday, November 19, 2001, at 12:11 , Francois Pottier wrote:
> James Woodyatt wrote:
>> Now, is it my imagination, or is all that research into what you can
>> build out of monads primarily a way for Haskell people to rediscover
>> everything we already know about polymorphism, inheritance and
>> encapsulation?
>
> Isn't that a bit harsh?

Maybe.  I'm more of a developer than a researcher.  As with any 
research, it's not useful to me until I know how and why to apply it.

If it *isn't* just my imagination, and it turns out that monadic 
programming is only a way to apply object-oriented programming 
techniques in purely functional languages, then I'd have to ask, "What's 
the point?"  We've already discovered object-oriented programming, as 
well as how to integrate it with a functional language, i.e. Objective 
Caml.

If by using monads, on the other hand, I can do something easily that 
would otherwise be very awkward, then I'm sold.  So far, I have only 
found examples of how to do things I can already do better with the 
imperative and object-oriented styles in OCaml.

Last month's Communications of the ACM (or was it the month before?) had 
a special on "aspect-oriented programming," which intrigued me.  Is 
there, perhaps, a natural application of monadic programming there?


--
j h woodyatt <jhw@wetware.com>
"somebody has to do something, and it's just incredibly
pathetic that it has to be us." --jerry garcia

-------------------
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] Re: variance, subtyping and monads... oh, my!

[Markus Mottl]

On Mon, 19 Nov 2001, james woodyatt wrote:
> On Monday, November 19, 2001, at 12:11 , Francois Pottier wrote:
> > Isn't that a bit harsh?
> 
> Maybe.  I'm more of a developer than a researcher.  As with any 
> research, it's not useful to me until I know how and why to apply it.

Even in OCaml people sometimes decide to apply monads. Just take a look
at the FFTW-library, whose code generator is implemented in OCaml:

  http://www.fftw.org

The simplification engine for DAGs used there represents rewrite rules
with monad operators. This way they "look" as if they were normal
tree-rewrite rules, whereas in fact the monad operators hide the whole
graph rewriting that happens "behind the scene". I could surely imagine
other, maybe even more efficient ways of doing it, but I fear it will be
difficult to find anything that is only closely as elegant (and easily
verifiable!).

> If by using monads, on the other hand, I can do something easily that 
> would otherwise be very awkward, then I'm sold.  So far, I have only 
> found examples of how to do things I can already do better with the 
> imperative and object-oriented styles in OCaml.

Objects are useful abstractions for states, whereas monads are
abstractions of computations (i.e. state transformations, like e.g.
rewriting steps as above). These two things solve different problems so
it wouldn't make much sense saying that one is "better" than the other.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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] Re: variance, subtyping and monads... oh, my!

[james woodyatt]

On Monday, November 19, 2001, at 01:58 , Markus Mottl wrote:
> On Mon, 19 Nov 2001, james woodyatt wrote:
>>
>> If by using monads, on the other hand, I can do something easily that
>> would otherwise be very awkward, then I'm sold.  So far, I have only
>> found examples of how to do things I can already do better with the
>> imperative and object-oriented styles in OCaml.
>
> Objects are useful abstractions for states, whereas monads are
> abstractions of computations (i.e. state transformations, like e.g.
> rewriting steps as above). These two things solve different problems so
> it wouldn't make much sense saying that one is "better" than the other.

That's probably what I needed to hear.  Thanks very much for the advice.

I'll take a look at that FFTW library for more clues about using the 
monadic style.  I hope to discover that I can use monads to address a 
particularly thorny class of problems that seems to arise again and 
again in my work, and which seems not to be well addressed by objects 
alone: cross-cutting concerns in the implementation of network 
application protocols.


--
j h woodyatt <jhw@wetware.com>
"...the antidote to misinformation is more information, not less."
                                                      --vinton cerf

-------------------
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] Re: variance, subtyping and monads... oh, my!

[Frank Atanassow]

Francois Pottier wrote (on 19-11-01 09:11 +0100):
> Isn't that a bit harsh? Monads offer abstraction with respect to the way
> certain side effects are performed. Because of ocaml's natural support for
> many side effects (references, exceptions, I/O, ...), monads are seldom
> needed in ocaml.

What may make monads less useful in Ocaml than in Haskell is not the native
support for side effects but rather the call-by-value evaluation. This is
illustrated by the fact that all the Haskell implementations which support the
IO monad also have native side effects, because that is the most efficient way
to implement references. (An alternative is to thread the state through
the computation explicitly, and do functional updates.)

Another way to say this is that Ocaml already supports a monad, namely the one
for CBV computations. It throws everything ("references, exceptions, I/O,
..") into this one monad, much like Haskell98 throws everything into the IO
monad.

Where Haskell has an advantage is that you can write new monads, and combine
them at will. "Monad transformers and Modular Interpreters" [1] is a good
example of the power this gives you.

Personally, I think Ocaml programs could benefit from being written in a
monadic style; I know I've been bitten by side effects on more than one
occasion. But I'm not sure if Ocaml's type system is up to the task, and I'm
also concerned that it won't optimize away all the consequent CPS-style code
the way GHC does.

[1] Sheng Liang, Paul Hudak, and Mark P. Jones. Monad Transformers and Modular
    Interpreters. In Conference Record of POPL'95: 22nd ACM SIGPLAN-SIGACT
    Symposium on Principles of Programming Languages, San Francisco, CA,
    January 1995. (http://www.cse.ogi.edu/~mpj/pubs/modinterp.html)

-- 
Frank Atanassow, Information & Computing Sciences, Utrecht University
Padualaan 14, PO Box 80.089, 3508 TB Utrecht, Netherlands
Tel +31 (030) 253-3261 Fax +31 (030) 251-379
-------------------
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] Re: variance, subtyping and monads... oh, my!

[Andreas Rossberg]

james woodyatt wrote:
> 
> I'm grateful for the bit about the binomial function type constructor
> that I can conceptually think about like this:
> 
>    type (+'domain,-'range) (->) = <fun>  (* yeah, this is pseudo-syntax *)

Almost, except for the inverted variance annotation. It should be:

	type (-'domain,+'range) (->)


> On Sunday, November 18, 2001, at 05:34 , Andreas Rossberg wrote:
> >
> > I hope my explanations clarified that these terms are mainly important
> > if
> > you do OO in the presence of polymorphic types. Functional programming
> > in
> > its purer forms usually does not use nor require subtyping, so need not
> > bother with them ;-)
> 
> <quip>How do you do OOP in the *absence* of polymorphic types?</quip>

By programming in Java, for example? ;-)

Seriously, when speaking about type systems the term "polymorphism"
usually refers to parametric polymorphism, witnessed by type
constructors like "list" or polymorphic functions like List.map, where
type variables pop up. Some OO languages have this kind of polymorphism,
e.g. Eiffel, or C++ with its templates (although the latter is rather a
macro language than a typeful concept). Many do not.

The OO world tends to use the same term to describe subtyping
polymorphism, but that arguably is a slight abuse of terminology, at
least IMHO.

There are even more forms of polymorphism, but I stop here.

> I'm guessing that these "purer forms" of functional programming involve
> convoluted gyrations with monads and the higher order "things" that you
> can construct with them by layering them one on top of the other.  (What
> would you call those things?  Molecules?)

No, as Francois suggested here I just meant functional programming
without mixing in OO.

> Now, is it my imagination, or is all that research into what you can
> build out of monads primarily a way for Haskell people to rediscover
> everything we already know about polymorphism, inheritance and
> encapsulation?

Mh, I don't see what monads have to do with object-oriented concepts.
Monads are (besides other things) useful to integrate imperative stuff
into a language without giving up referential transparency, or to
sequentialise actions in a non-strict language. But this is only related
to OO in the sense that OO usually builds upon imperative programming
(so that stateful objects have to live inside a monad in pure functional
languages).

Also, I am not sure what particular concept of encapsulation you are
referring to. Monads are a tool to build abstractions and as such they
of course encapsulate stuff. But I would argue that the sort of
encapsulation usually performed with classes and objects is more related
to modules and plain closures (1st-class functions).

> Here's my question: Am I missing some important clue about what monads
> will get me?

Maybe. I don't often use monads myself, so I am by no means an expert,
but there are quite some useful applications, even outside the realm of
lazy evaluation and purely functional languages. Examples are
encapsulating state, failure, non-determinism, etc. I think Markus Mottl
posted an OCaml example of a simple monadic evaluator some time ago. And
here is one of the more readable, not too Haskell-centric papers:


http://cm.bell-labs.com/cm/cs/who/wadler/topics/monads.html#marktoberdorf

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
 as kids, we would all be running around in darkened rooms, munching
 magic pills, and listening to repetitive electronic music."
 - Kristian Wilson, Nintendo Inc.
-------------------
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] Re: variance, subtyping and monads... oh, my!

[Markus Mottl]

Andreas Rossberg schrieb am Montag, den 19. November 2001:
> Maybe. I don't often use monads myself, so I am by no means an expert,
> but there are quite some useful applications, even outside the realm of
> lazy evaluation and purely functional languages. Examples are
> encapsulating state, failure, non-determinism, etc. I think Markus Mottl
> posted an OCaml example of a simple monadic evaluator some time ago.

Yes, you can get it here (called "IMP"):

  http://www.ai.univie.ac.at/~markus/home/ocaml_sources.html

It compares interpretation of a simple imperative language in monadic
style to explicit state passing. As was already mentioned, the lack of
overloading doesn't make monads as convenient as in Haskell.

Regards,
Markus Mottl

-- 
Markus Mottl                                             markus@oefai.at
Austrian Research Institute
for Artificial Intelligence                  http://www.oefai.at/~markus
-------------------
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] Kylix and OCaml

[Christophe Raffalli]

A friend of mine showed me Kylix (see Borland's home page:
http://www.borland.com)... It looks great to create 
user interfaces.

Moreover, some people have no problem changing the Pascal compiler into C++ ...
And it is compatible with corba and should have all the IDL files for the
various widget

So using CamlIDL, it should be easy to make Kylix use our favorite language and
get interfaces (portable under both Linux and Windows) in no time ?

I might have a look, but I know nothing about Kylix and IDL.

May be someone else, more competent than me, want to try ? Or at least give me
some advices (like "I know it will fails because ..." :-)


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
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] Kylix and OCaml

[Vitaly Lugovsky]

On Mon, 19 Nov 2001, Christophe Raffalli wrote:

> 
> A friend of mine showed me Kylix (see Borland's home page:
> http://www.borland.com)... It looks great to create 
> user interfaces.

 It is an illusion. Don't believe your eyes. Tools like Delphi/Kylix/...
will not help you at all - it's much faster to write an UI in Tk by hands
then using such a WYSIWIG.

 But, if you want WYSIWIG GUI tool, just use Glade - it produces a 
portable XML representation for GUI dialogs, and, I belive, it'll be 
pretty easy to use it from Caml.

> So using CamlIDL, it should be easy to make Kylix use our favorite language and
> get interfaces (portable under both Linux and Windows) in no time ?

 Why do you want such a havy and thick GUI layer? GUI is for scripts!
Use Wish, it's portable. Much more portable, then Bugland tools.


-------------------
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] Kylix and OCaml

[Christophe Raffalli]

Vitaly Lugovsky a écrit :
> 
> On Mon, 19 Nov 2001, Christophe Raffalli wrote:
> 
> >
> > A friend of mine showed me Kylix (see Borland's home page:
> > http://www.borland.com)... It looks great to create
> > user interfaces.
> 
>  It is an illusion. Don't believe your eyes. Tools like Delphi/Kylix/...
> will not help you at all - it's much faster to write an UI in Tk by hands
> then using such a WYSIWIG.

I will not comment for Kylix ... But I was a user of the not very unfamous
SUIT. And I can tell you are wrong. SUIT was design with two ideas:
- use real number for sizes to allow scaling (that was not really a good idea)
- each widget have properties (like colors, size, fonts, etc ...)
  - widgets can be grouped to share some properties (independetly of the fact  
    they are parents)
  -  AND each kind of property is associated with a widget to 
    allow its modification (for instance a font selection dialog, or 
    scroll bar for the position of an element in a window). 
    
With that it took only a couple of minutes to write a Text processor more
complete than you may think (possible to select fonts, short cuts, etc ..)
moreover, you only had to write very few lines of code (in fact only the
line saving the buffer in a file and reading a file)

And last point: SUIT produced its output in a readable interface description 
language and translated that (to C or C++ I can not remember). So you could use
it without graphical interface if you did not like that :-)

>  But, if you want WYSIWIG GUI tool, just use Glade - it produces a
> portable XML representation for GUI dialogs, and, I belive, it'll be
> pretty easy to use it from Caml.
> 
> > So using CamlIDL, it should be easy to make Kylix use our favorite language and
> > get interfaces (portable under both Linux and Windows) in no time ?
> 
>  Why do you want such a havy and thick GUI layer? GUI is for scripts!
> Use Wish, it's portable. Much more portable, then Bugland tools.

Kylix is in fact quite responsive and light (working on powerless PCs).
If you mean heavy because the professionnal edition has numerous widget (like
every thing to write a database client or a web browser in a couple of
minutes). In fact I am quite amased with the speed for a package of 120Mo when
installed for the pro version (I think that the 120Mo are mainly the widgets
and examples). It shows that it is well implemented (other software like
star-office let you see that they are big !)

But then I agree that they may be other solutions using a language to describe
the interface. 

But what are the solutions (language or WYSIWIG) immediately available for
OCaml ?

Are they complete (how many kind of widgets supported ?)




-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
-------------------
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] Kylix and OCaml

[Vitaly Lugovsky]

On Tue, 20 Nov 2001, Christophe Raffalli wrote:

> Vitaly Lugovsky a Иcrit :

> > > A friend of mine showed me Kylix (see Borland's home page:
> > > http://www.borland.com)... It looks great to create
> > > user interfaces.
> > 
> >  It is an illusion. Don't believe your eyes. Tools like Delphi/Kylix/...
> > will not help you at all - it's much faster to write an UI in Tk by hands
> > then using such a WYSIWIG.
> 
> I will not comment for Kylix ... But I was a user of the not very unfamous
> SUIT. And I can tell you are wrong. SUIT was design with two ideas:
> - use real number for sizes to allow scaling (that was not really a good idea)

 In this case you sould have a WYSIWYG tool. But containers approach
is much better: you don't need to know anything about sizes - just do a 
widgets placing - pack them in lines, tables, lists, may be using a kinda
boxes and glue approach like in TeX...

> >  Why do you want such a havy and thick GUI layer? GUI is for scripts!
> > Use Wish, it's portable. Much more portable, then Bugland tools.
> 
> Kylix is in fact quite responsive and light (working on powerless PCs).

 Hm... 500MHz Pentium-II is powerless? Be realistic...

> If you mean heavy because the professionnal edition has numerous widget (like
> every thing to write a database client or a web browser in a couple of
> minutes). In fact I am quite amased with the speed for a package of 120Mo when
> installed for the pro version (I think that the 120Mo are mainly the widgets
> and examples). It shows that it is well implemented (other software like
> star-office let you see that they are big !)

 And you really want to produce a native compiled n-megabytes monster for
any small dialog? Why? Nothing can be lighter then scripts.
 
> But then I agree that they may be other solutions using a language to describe
> the interface. 

 And this solution is much better and elegant. ;)

> But what are the solutions (language or WYSIWIG) immediately available for
> OCaml ?

 Tcl/Tk. Write your GUI in Tcl, and connect it to your OCaml application.
Application logic really MUST be separated from GUI, even if you only
calculates "2+2".

> Are they complete (how many kind of widgets supported ?)

 Tk is a very old and widespread toolkit, so, I think, you will find
anything you want there.


-------------------
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] Kylix and OCaml

[Benjamin Monate]

On Tue, 20 Nov 2001 05:05:22 +0300 (MSK)
Vitaly Lugovsky <vsl@ontil.ihep.su> wrote:
>  But, if you want WYSIWIG GUI tool, just use Glade - it produces a 
> portable XML representation for GUI dialogs, and, I belive, it'll be 
> pretty easy to use it from Caml.

Hi,

You may want to try a first snapshot of mlglade.

mlglade is a translator from glade xml file into a set of modules for
OCaml >= 3.01.

Very quick usage notice :
- Design a gui with glade.
- Generate the ocaml files using "mlglade"
- type "make". Now you have a caml application that reacts to events that
have been binded in glade.
- Edit the main file. Customize the callbacks in the class
"customized_callbacks" by overriding methods. 
- You may redesign the gui without loosing your customized callbacks.


This is still ugly, experimental and unfinished code. 
But it works most of the time for some projects.

The only documentation is the README.

You can download it from http://www.lri.fr/~monate/mlglade

Feel free to send bug reports, comments and patches.

-- 
| Benjamin Monate         | mailto:Benjamin.Monate@lri.fr |
| LRI - Bât. 490          | http://www.lri.fr/~monate/    |
| Université de Paris-Sud | phoneto: +33 1 69 15 42 32    |
| F-91405 ORSAY Cedex     | faxto: +33 1 69 15 65 86      |

-------------------
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] [Bug in an interface between C++ and OCAML due to some pointer encapsulation]

[Sylvain Kerjean]

I made some interesting stuff between C++ and OCaml in order to
interface the BeOS API (I have a drawing interface functioning).
All is fine, excepted that after a certain amount of time, i get a crash
in "oldify_local_roots".
I guess that i made some "classical" errors in encapsulating some C
pointer in a value, which might then be persistent in the OCaml heap and
at the end my heap must be all feed.
But i don't know how to solve this bug (no Baygon Vert is not the
solution ...).

Has anybody encountered the same kind of errors ?
-------------------
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] Kylix and OCaml

[Maxence Guesdon]

>  But, if you want WYSIWIG GUI tool, just use Glade - it produces a 
> portable XML representation for GUI dialogs, and, I belive, it'll be 
> pretty easy to use it from Caml.
I'm currently working on an interface builder for lablGtk,inspired 

from the radtest application of the lablgtk distrib. There should 

be a release within 2 or 3 weeks from now.


--
Maxence Guesdon

-------------------
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