[Caml-list] A G'Caml question

[Caml-list] A G'Caml question

[Brian Rogoff]

Hi,
    One of the important issues with overloading is whether one has 
to define a "generic" function all in one place or if you can build it up 
piecemeal from already existing generic functions. I played a bit, learned 
some things, and now I have some questions. 

I start with the obvious "plus" function, and extend it so that in 
concatenates strings. 

# generic plus = case
    int -> int -> int => (+)
  | float -> float -> float => (+.) ;;  
val plus : $a -> $a -> $a [ int -> int -> int 
                          | float -> float -> float  ] =
  <fun>
# plus 1 2;;
- : int = 3
# plus 1.0 2.0;;
- : float = 3
# plus "1" "2";;
This generic full instance is used with type string -> string -> string
 which is not its valid instance of 
$a -> $a -> $a [ int -> int -> int 
               | float -> float -> float  ]
# generic plus = case 
  string -> string -> string => (^) 
  | $a -> $a -> $a => plus ;;  
val plus : $a -> $a -> $a
  [ string -> string -> string 
  | $a -> $a -> $a && plus : $a -> $a -> $a  ] = <fun>
# plus 1 1;;
- : int = 2
# plus "1" "2.0";;
- : string = "12.0"

Cool, for some very simple cases, it we can incrementally build up a 
generic function from pieces. I think it's obvious that we'll get into 
trouble with recursive generics. 

# generic rec print = case 
  | int -> unit => print_int
  | string -> unit => print_string
  | $a list -> unit => 
      function [] -> ()
      |   x :: xs -> print x; print xs
  ;;            
  val print : $a -> unit
  [ int -> unit 
  | string -> unit 
  | $a list -> unit && print : $a -> unit && print : $a list -> unit  ] =
  <fun>
# print 23;;
23- : unit = ()
# print 23.0;;
This generic full instance is used with type float -> unit
 which is not its valid instance of 
$a -> unit
[ int -> unit 
| string -> unit 
| $a list -> unit && print : $a -> unit && print : $a list -> unit  ]

OK, lets try the same thing as before, 

# generic rec print = case float -> unit => print_float | $a -> unit =>
print;;
val print : $a -> unit
  [ float -> unit 
  | $a -> unit && print : $a -> unit  ] = <fun>

# print 1.0;;
1- : unit = ()
# print 1 (* infinite loop! *)

Well, that should be expected, since we try and print an int, which isn't
a float, so we try (from $a -> unit => print) to print, ad infinitum. Is
there a way out? If we try and rename print and call that, it still won't work, 
since we want a form of "open recursion" here: if I add a case for float I 
want to be able to print float lists. With the original print
reinstalled...

# let print' = print ;;
val print' : $a -> unit [ $a -> unit && print : $a -> unit  ] = <fun>
# generic rec print = case float -> unit => print_float | $a -> unit =>
print';;
val print : $a -> unit
  [ float -> unit 
  | $a -> unit && print' : $a -> unit  ] = <fun>
# print 1.0;;
1- : unit = ()
# print [1;2;3];;
123- : unit = ()
# print [1.0;2.0;3.0];; 
This generic full instance is used with type float list -> unit
 which is not its valid instance of 
$a -> unit [ float -> unit 
           | $a -> unit && print' : $a -> unit  ]

Is there some trick to build up recursive generics by parts? One thing 
to do is to break the recursive generic into a non-recursive generic
and a recursive function which applies the generic to the elements, 
but that feels like cheating. Maybe open recursion for generics would 
be desirable, so that I can add a new case and have the recursive call in 
an existing case call the new one? Yes, it's a half baked idea, but maybe 
a better cook can finish baking...

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

"Re: [Caml-list] A G'Caml question" + additional info

[Jun Furuse]

Hello,

Thanks your comment about the exntesion. It is natural idea to extend
generic values and it must be definitively required. This extension
of generic values cannot be handled by the normal redefinition which
is available in G'Caml. They essentially requires its own syntax and
typing, which are still not be implemented...

Let me explain details using your example:

> # generic rec print = case 
>   | int -> unit => print_int
>   | string -> unit => print_string
>   | $a list -> unit => 
>       function [] -> ()
>       |   x :: xs -> print x; print xs
>   ;;            
>
> # generic rec print = case float -> unit => print_float | $a -> unit =>
> print;;
> 
> # print 1.0;;
> 1- : unit = ()
> # print 1 (* infinite loop! *)
> 
> Well, that should be expected, since we try and print an int, which isn't
> a float, so we try (from $a -> unit => print) to print, ad
> infinitum. 

Yes, as you pointed out, your second definition of print will not
work, because its definition is completely independent from the first;
it uses the same name print, but it points to the new print. 
We can have the same thing even in the normal let rec expressions:

   let f () = print_string "hello";;
   let rec f () = f ()

The second f does not call the first f, but itself (and loops forever).

> # let print' = print ;;
>
> # generic rec print = case 
>   | float -> unit => print_float 
>   | $a -> unit => print'
>   ;;
>
> # print [1.0;2.0;3.0];; 
> This generic full instance is used with type float list -> unit
>  which is not its valid instance of ...

This does not work neither. Since what print recursively calls
is the original print, not the newly defined print. Therefore
we cannot use the interesting mixed case of float list -> unit...

> Is there some trick to build up recursive generics by parts? One thing 
> to do is to break the recursive generic into a non-recursive generic
> and a recursive function which applies the generic to the elements, 
> but that feels like cheating. Maybe open recursion for generics would 
> be desirable, so that I can add a new case and have the recursive call in 
> an existing case call the new one? Yes, it's a half baked idea, but maybe 
> a better cook can finish baking...

As we have seen, redefinitions cannot achieve what you (and I) want. 
We will need some special construction for the extension. We will have
the new "include" phrase to import the type case definitions of the
other generic values. For example:

	generic print' = case
	| include print
	| float -> unit => print_float
	;;

This newly defined print' will be semantically equivalent to the 
following generic definition:
 
	generic print' = case
	| int -> unit => print_int
	| string -> unit => print_float
	| $a list -> unit =>
	     function [] -> ()
		    | x :: xs -> print' x; print' xs  
	| float -> unit => print_float
	;;

Note that the recursive occurrences of print in the original
definition are now replaced by print', in order to point 
the newly defined generic value. In this sense, the include phrase is
not the pure inclusion of the source. Thus, the new print' can print
float lists:

      # print' [1.2; 3.4; 5.6];;
      1.23.45.6- : unit = ()

Thus, the generic values are "open" to the others who include them,
but it is not the open recursion you mentioned; print and print' are
different values and independent each other. 

  We do not want to introduce the full open recursion to generic
values. You could add new type cases easily using the open recursion
and it should be helpful in some cases. But it can also introduce
heavy semantic confusion to our programs, since in the open recursion
the semantics of generic values could not be fixed until all modules 
are linked together. 

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

Several people have courageously tried some module programming using
G'Caml and reported troubles. I am sorry but you cannot write .mli
files with extensional polymorphic values. At the time of the
implementation, we had not had clear idea to store generic constraints
in signatures... Please only use the toplevel.

I explained briefly the limitations of the current implementation at

  http://pauillac.inria.fr/~furuse/generics/

However, none of them are theoretical. 
They can be fixed when I will get some more time for coding!

Regards,

-----------------------------------------------------------------------
Jun P. Furuse 					 Jun.Furuse@inria.fr
-------------------
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: "Re: [Caml-list] A G'Caml question" + additional info

[Patrick M Doane]

On Mon, 25 Jun 2001, Jun Furuse wrote:

> Thus, the generic values are "open" to the others who include them,
> but it is not the open recursion you mentioned; print and print' are
> different values and independent each other. 
> 
>   We do not want to introduce the full open recursion to generic
> values. You could add new type cases easily using the open recursion
> and it should be helpful in some cases. But it can also introduce
> heavy semantic confusion to our programs, since in the open recursion
> the semantics of generic values could not be fixed until all modules 
> are linked together. 

I agree that this could make programs more difficult to follow, but I
think it is to be expected with generic programming these days.
Also, isn't this kind of semantic confusion already present with using the
object oriented system?

In the following example, writing definitions like MyProgram.print may get
very tedious in practice.

module Int = struct
  generic print = case int -> unit => print_int
end

module String = struct
  generic print = case string -> unit => print_string
end

module List = struct
  generic print =
   case $a list -> unit => function [] -> () | x :: xs -> print x; print xs
end

module MyProgram = struct
  generic print = case
  | include Int.print
  | include String.print
  | include List.print
    (*  all other print functions to follow *)
end

Given what is done with Haskell type classes and C++ templates, it seems
more confusing to me to not support open recursion.  Any thoughts?  

Patrick

-------------------
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: "Re: [Caml-list] A G'Caml question" + additional info

[Brian Rogoff]

On Wed, 27 Jun 2001, Patrick M Doane wrote:
> On Mon, 25 Jun 2001, Jun Furuse wrote:
> >   We do not want to introduce the full open recursion to generic
> > values. You could add new type cases easily using the open recursion
> > and it should be helpful in some cases. But it can also introduce
> > heavy semantic confusion to our programs, since in the open recursion
> > the semantics of generic values could not be fixed until all modules 
> > are linked together. 
> 
> I agree that this could make programs more difficult to follow, but I
> think it is to be expected with generic programming these days.
> Also, isn't this kind of semantic confusion already present with using the
> object oriented system?
> 
> In the following example, writing definitions like MyProgram.print may get
> very tedious in practice.
> 
> module Int = struct
>   generic print = case int -> unit => print_int
> end
> 
> module String = struct
>   generic print = case string -> unit => print_string
> end
> 
> module List = struct
>   generic print =
>    case $a list -> unit => function [] -> () | x :: xs -> print x; print xs
> end
> 
> module MyProgram = struct
>   generic print = case
>   | include Int.print
>   | include String.print
>   | include List.print
>     (*  all other print functions to follow *)
> end

Actually, that doesn't look too bad to me. Once generics play well with
modules and functors (and classes and polymorphic variants :), support the 
include syntax Jun described, and are in the release (along with a safer
marshaling) I'll be very pleased

The real issue which open recursion would solve is if you had, say, a
recursive generic for printing lists recursively, one for doing arrays
recursively, and one for doing tuples (up to some fixed arity). Here's 
how you'd write it now 

generic print_basic = case 
    | int -> unit => print_int
    | float -> unit => print_float
    | char -> unit => print_char
    | string -> unit => print_string
    | bool -> unit => 
	(function true -> print_string "true" 
         |        _ -> print_string "false")

generic rec print_seq = case 
    (* print_tuple *)
    | $a * $b -> unit => fun (u,v) -> print_seq u; print_seq v
    | $a * $b * $c -> unit => 
        fun (u,v,w) -> print_seq u; print_seq v; print_seq w
    | $a * $b * $c * $d  -> unit => 
        fun (u,v,w,x) -> 
	  (print_seq u; print_seq v; print_seq w;print_seq x)
    | $a * $b * $c * $d * $e -> unit => 
        fun (u,v,w,x,y) -> 
	   (print_seq u; print_seq v; print_seq w;print_seq x;print_seq y)
    (* print_array *)
    | $a array -> unit => fun a -> Array.iter print_seq a
    (* print_list *)
    | $a list  -> unit => fun l -> List.iter print_seq l
    | $a -> unit => print_basic;;

note that this can print a lot of stuff because of recursion:

# print_seq (1,2);;
12- : unit = ()
# print_seq (1,(2,(3,(4,(5,(6,(7,(8,9))))))));;
123456789- : unit = ()
# print_seq (1,[|(2,3);(4,5);(6,7)|],"8",9.0);;
123456789- : unit = ()

but you can't break it into parts print_tuple, print_list, print_array 
and construct print_seq by composing them. Oh well, they still give a
much needed overloading and have lots of power to spare. 

> Given what is done with Haskell type classes and C++ templates, it seems
> more confusing to me to not support open recursion.  Any thoughts?  

They're really powerful. Once the design and implementation are more
stable, we'll see how important the lack of open recursion is. I think
it's more important to have human understandable error messages and
inferred types. I'm already looking forward to the merger with OCaml
proper. 

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