generic functions

generic functions

[wiedergaenger]

I just got from LISP to OCaml, and wondered if there is an equivalent of
generic functions from LISP (CLOS) in OCaml. In the Common Lisp Object
System methods don't belong to certain objects/classes. They are just
function specializing on the argument types. So basically I want to
write something like:

let foo (x : int) = x*x;;
let foo (x : float) = x*.x;;

This, obviously, will not work since foo is just redefined by the second
statement. One would think, that having methods not being belonging to
objects/classes, is rather pointless. Well 95% of the time, there is no
necessity for that. But in the other 5%, it is really helpful. 

Re: [Caml-list] generic functions

[Richard Jones]

On Sun, Jan 09, 2005 at 02:19:29PM +0100, wiedergaenger@fastmail.fm wrote:
> I just got from LISP to OCaml, and wondered if there is an equivalent of
> generic functions from LISP (CLOS) in OCaml. In the Common Lisp Object
> System methods don't belong to certain objects/classes. They are just
> function specializing on the argument types. So basically I want to
> write something like:
> 
> let foo (x : int) = x*x;;
> let foo (x : float) = x*.x;;
> 
> This, obviously, will not work since foo is just redefined by the second
> statement. One would think, that having methods not being belonging to
> objects/classes, is rather pointless. Well 95% of the time, there is no
> necessity for that. But in the other 5%, it is really helpful. 

The general solution is GCaml
(http://pauillac.inria.fr/~furuse/generics/README.gcaml) which is not
part of OCaml core.

Rich.

-- 

Re: [Caml-list] generic functions

[Brian Hurt]

On Sun, 9 Jan 2005 wiedergaenger@fastmail.fm wrote:

> I just got from LISP to OCaml, and wondered if there is an equivalent of
> generic functions from LISP (CLOS) in OCaml. In the Common Lisp Object
> System methods don't belong to certain objects/classes. They are just
> function specializing on the argument types. So basically I want to
> write something like:
> 
> let foo (x : int) = x*x;;
> let foo (x : float) = x*.x;;
> 
> This, obviously, will not work since foo is just redefined by the second
> statement. One would think, that having methods not being belonging to
> objects/classes, is rather pointless. Well 95% of the time, there is no
> necessity for that. But in the other 5%, it is really helpful. 
> 

The short answer is no.  For two reasons- first, Ocaml doesn't keep type 
information (in most cases) of data at run time, the type information is 
used during compilation and then tossed.  Which means that Ocaml doesn't 
have a way at run time to tell which version of the function to call.  And 
second, and more importantly, overloading (like you're doing above) would 
make type inference extremely difficult if not impossible.

There are several ways to "work around" this limitation in Ocaml, 
depending upon what exactly you are doing.

1) Just use different functions.  Do:
	let ifoo x = x * x;;
	let ffoo x = x *. x;;
and just call the correct one.  This is generally not as bad a solution as 
you might think.

2) Use variant types:
	type number = Int of int | Float of float;;
	let foo = function
		| Int(x) -> Int(x*x)
		| Float(x) -> Float(x*.x)
	;;
The tags in this case are the type information Ocaml would normally "throw 
away".

3) Use modules:
	module type Mult = sig
		type t
		val mul : t -> t -> t
	end
	module type Foo = sig
		type t
		val foo : t -> t
	end
	module Make(M: Mult) : Foo with type t = M.t = struct
		type t = M.t
		let foo x = M.mul x x
	end;;
	module IMult = struct
		type t = int
		let mul x y = x * y
	end;;
	module IFoo = Make(IMult);;
	module FMult = struct
		type t = float
		let mul x y = x *. y
	end
	module FFoo = Make(FMult);

For this simple example, modules and functors are clunky- but they allow 
the user of your code to create new foo functions, which is usefull.

With the exception of certain artificial contests (Paul Graham) I've never 
met a real world problem that needed overloading, or even benefitted 
signifigantly from overloading that didn't benefit just as much or more 
from one of the solutions above.

Brian

Re: [Caml-list] generic functions

[David McClain]

> With the exception of certain artificial contests (Paul Graham) I've never
> met a real world problem that needed overloading, or even benefitted
> signifigantly from overloading that didn't benefit just as much or more
> from one of the solutions above.

I would mention ad-hoc, interactive, engineering computing, e.g., NML,
Mathematica, MatLab, where generic functions and overloading are extremely
useful. But none of these languages can produce safe code, and I would never
recommend using any of them for production releases of software. OCaml =
strong safety. NML and others = fast interactive exploratory programming,
but not safe.

David McClain
Senior Corporate Scientist
Avisere, Inc.

+1.520.390.7738 (USA)
david.mcclain@avisere.com

Re: [Caml-list] generic functions

[brogoff]

On Sun, 9 Jan 2005, David McClain wrote:
(unsnipped from Brian Hurt, don't remove quoted attributions if you don't
 want your name misattributed ;)
> > With the exception of certain artificial contests (Paul Graham) I've never
> > met a real world problem that needed overloading, or even benefitted
> > signifigantly from overloading that didn't benefit just as much or more
> > from one of the solutions above.

Our experiences differ significantly then. I'd say that overloading is a
benefit in many "real world" cases, and that type inference is largely
unnecessary (to be more precise, it's useful for small helper functions,
otherwise, the type (scheme) is useful documentation) and in fact in
that now old ML2000 proposal type inference was under question. Yes, I read
the  original ML discussion about why it was wanted in theorem provers and
all that, but I'm not convinced.

All of the workarounds you mention are ugly workarounds, IMO. I'm not trying to
open this perennial argument again, since I believe it's been proven that no
one has ever changed their mind on account of internet email or usenet
postings, just to make it clear to anyone asking that the opinion epressed
doesn't have unanimous support.

> I would mention ad-hoc, interactive, engineering computing, e.g., NML,
> Mathematica, MatLab, where generic functions and overloading are extremely
> useful. But none of these languages can produce safe code, and I would never
> recommend using any of them for production releases of software. OCaml =
> strong safety. NML and others = fast interactive exploratory programming,
> but not safe.

That's because these languages (don't know about NML) and CLOS are at best
dynamically typed, not because they have overloading. And you have to define
"unsafe" in a special way, dynamically typed garbage collected languages
shouldn't seg fault, but you may get run time errors, as you can with ML. Once
again, I know what you mean, and ML is by some measure "safer", but I don't
think it fair to lump Lisps or Mathematica with unsafe languages.

-- Brian

Re: [Caml-list] generic functions

[padiolea]

> On Sun, 9 Jan 2005 wiedergaenger@fastmail.fm wrote:
>
>> I just got from LISP to OCaml, and wondered if there is an equivalent of
>> generic functions from LISP (CLOS) in OCaml. In the Common Lisp Object
>> System methods don't belong to certain objects/classes. They are just
>> function specializing on the argument types. So basically I want to
>> write something like:
>>
>> let foo (x : int) = x*x;;
>> let foo (x : float) = x*.x;;
>>
>> This, obviously, will not work since foo is just redefined by the second
>> statement. One would think, that having methods not being belonging to
>> objects/classes, is rather pointless. Well 95% of the time, there is no
>> necessity for that. But in the other 5%, it is really helpful.
>>
>
...

> 1) Just use different functions.  Do:
...

> 2) Use variant types:
...

> 3) Use modules:
...

I would add 4)  use objects.
see http://caml.inria.fr/ocaml/htmlman/manual005.html
and define a class ofloat, and oint (for object float and objects int)
and define
  let foo x = x#mul x
Note that foo does not have to belong to the classes. It can be defined
outside of the class defintion.
Of course if your definition of foo would have been
 let foo (x : int) = x+x;; (* * have been replaced by + *)
 let foo (x : float) = x*.x;;
then, it does not work anymore.



>
> With the exception of certain artificial contests (Paul Graham) I've never
> met a real world problem that needed overloading, or even benefitted
> signifigantly from overloading that didn't benefit just as much or more
> from one of the solutions above.

I guess that's because you never been involved in real world problems.
Overloading, which is adhoc polymorphism is as useful as
parametric polymorphism. Ask the haskell folks if they would accept
to forget about type classes.
Of course functors can emulate some of the advantages of overloading,
but not totally. Objects are better for this.

>
> Brian
>
>
> _______________________________________________
> Caml-list mailing list. Subscription management:
> http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
> Archives: http://caml.inria.fr
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

Re: [Caml-list] generic functions

[skaller]

On Mon, 2005-01-10 at 02:48, Brian Hurt wrote:

> > let foo (x : int) = x*x;;
> > let foo (x : float) = x*.x;;

> The short answer is no.  For two reasons- first, Ocaml doesn't keep type 
> information (in most cases) of data at run time, the type information is 
> used during compilation and then tossed.  Which means that Ocaml doesn't 
> have a way at run time to tell which version of the function to call.  And 
> second, and more importantly, overloading (like you're doing above) would 
> make type inference extremely difficult if not impossible.

Felix is an ML like language which does provide overloading.
It does overload resolution at compile time. As Brian mentions
this makes full type inference hard, however this isn't nearly so
much of a problem as you might think

You have to annotate function argument types, however function
return types and variable types are still deduced. For this extra
effort you get three positive benefits:

(a) better documented code
(b) better diagnostic messages on type errors
(c) overloading

In addition, some of the newer Ocaml features like polymorphic
variants require type annotations or coercions to be used
at times anyhow, and such annotation is common for functions
in separately compiled files, which often have interface
specifications (which require type annotations).

The two principal advantages of inference would appear to be:

(a) for quick and dirty code and small functions where
the extra clutter would reduce clarity and increase coding time.

(b) for complex functions with nasty types

The brevity argument is context dependent. I have just written in
Felix a function which converts a complex parse tree into
a string. This function has to decode around 100 variants
from 40 or so types to produce the result.

In Felix all these functions are called 'str', and I can just
write code like

fun str : product_list_t -> string =
  | product_list_1 (?s,?sl) => str s + " * " + str sl
  | product_list_2 ?s => str s
;


fun str : term_t -> string =
  | term_1 (?t,?p) => str t + " / " + str p
  | term_2 (?t,?p) => str t + " % " + str p
  | term_3 ?pr => str pr
;

..

Without overloading I would have to invent a discrete name for
each function, which would certainly reflect the argument type,
so this is balances out in favour of overloading. In the actual
use of the function there is no doubt that overloading is
briefer than inference without it, since I can use
the 'str' name without knowing which function is applied.

In Ocaml, this program would be almost untenable.
I would try to avoid this problem by using polymorphic variants
instead of ordinary ones (and then write one big 'str' function
for all the variants).

Bottom line: I have used two similar languages, one with
type inference and one with overloading, and in general
I could pick between them like this:

Overloading (in the Felix and C++ style) only works on direct 
calls where the function is named. It doesn't work with 
closures, for example variables containing function values,
including parameters. So I would say inference is better
when you're doing lots of higher order work, and overloading
is better for more mundane industrial applications.

BTW: it would be interesting to provide a better integration
of both features. G'Caml is one idea. Polymorphic variants
are another. In Felix you can write:

	fun swap(x,y) => y,x;

without type annotations: type variables are assumed but
they're independent. This precludes code like

	fun apply(f,x)=> f x;

but it is clear some localised inference in this case would
allow this. 

It is also known that overloading CAN work with
inference with some contraints -- there is a paper somewhere
on Citeseer on this topic (sorry don't have the URL at the
moment, if someone finds it please let me know..)


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net

Re: [Caml-list] generic functions

[Alex Baretta]

Brian Hurt wrote:
> On Sun, 9 Jan 2005 wiedergaenger@fastmail.fm wrote:
>
>>let foo (x : int) = x*x;;
>>let foo (x : float) = x*.x;;
>>

> With the exception of certain artificial contests (Paul Graham) I've never 
> met a real world problem that needed overloading, or even benefitted 
> signifigantly from overloading that didn't benefit just as much or more 
> from one of the solutions above.
> 
> Brian

As a member of the International Caml's Jihad, I'd like to spend two 
cents of dynamite on this topic: type inference is as good as honey in 
large scale industrial projects, where sometimes the typing of complex 
recursive polymorphic algorithms is not evident until you get the 
printout from the compiler or the toplevel. Thank you, O great 
Unification Algorithm.

But, then again, extensional polymorphism is also a much needed feature. 
In my company we depend heavily on on extensional polymorphism to create 
exstensibile functions. We have implemented this on top of explicitly 
polymorphic types: i.e. polymorphic variant types.

Let us all faithfully await the Coming of the the Gcaml... And meanwhile 
let us use polymorphic variants to get the same effect.

type poly_int = [ `Int of int ]
type poly_float = [ `Float of float ]

let foo_int foo = function
   | `Int x -> `Int(x * x)
   | other -> foo other

let foo_float foo = function
   | `Float x -> `Float(x *. x)
   | other -> foo other

let rec foo x = match x with
   | #poly_int -> foo_int foo x
   | #poly_float -> foo_float foo x


All hail Ocaml!

Alex, after too many nights spent writing typechecking code...

-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: [Caml-list] generic functions

[Olivier Andrieu]

 Alex Baretta [Mon, 10 Jan 2005]:
 > type poly_int = [ `Int of int ]
 > type poly_float = [ `Float of float ]
 > 
 > let foo_int foo = function
 >    | `Int x -> `Int(x * x)
 >    | other -> foo other
 > 
 > let foo_float foo = function 
 >    | `Float x -> `Float(x *. x) 
 >    | other -> foo other
 > 
 > let rec foo x = match x with
 >    | #poly_int -> foo_int foo x
 >    | #poly_float -> foo_float foo x

Hum, I would have written this in that way :
,----
| let foo_int   (`Int x)   = `Int   (x * x)
| let foo_float (`Float x) = `Float (x *. x)
| 
| let foo = function
|   | #poly_int   as x -> foo_int x
|   | #poly_float as x -> foo_float x
`----

What's the use for the `other -> foo other' clauses ?

-- 
   Olivier

Re: [Caml-list] generic functions

[Alex Baretta]

Olivier Andrieu wrote:
>  Alex Baretta [Mon, 10 Jan 2005]:
>  > type poly_int = [ `Int of int ]
>  > type poly_float = [ `Float of float ]
>  > 
>  > let foo_int foo = function
>  >    | `Int x -> `Int(x * x)
>  >    | other -> foo other
>  > 
>  > let foo_float foo = function 
>  >    | `Float x -> `Float(x *. x) 
>  >    | other -> foo other
>  > 
>  > let rec foo x = match x with
>  >    | #poly_int -> foo_int foo x
>  >    | #poly_float -> foo_float foo x
> 
> Hum, I would have written this in that way :
> ,----
> | let foo_int   (`Int x)   = `Int   (x * x)
> | let foo_float (`Float x) = `Float (x *. x)
> | 
> | let foo = function
> |   | #poly_int   as x -> foo_int x
> |   | #poly_float as x -> foo_float x
> `----
> 
> What's the use for the `other -> foo other' clauses ?

In my previous post I mentioned *extensible functions*. The first 
parameter of single instances of the polymorphic foo (i.e. foo_int and 
foo_float) allow the generalization of each of these to arbitrarily 
complex polymorphic type schema. We have exactly 7888 lines of code 
which contain such late-bound-recursive functions à la foo_int. 
Obviously it takes a relatively complex example to show why 
late-bound-recursion is essential to the implementation of a fairly 
extensional polymorphism with Ocaml's polymorphic variants.

Alex


-- 
*********************************************************************
http://www.barettadeit.com/
Baretta DE&IT
A division of Baretta SRL

tel. +39 02 370 111 55
fax. +39 02 370 111 54

Our technology:

The Application System/Xcaml (AS/Xcaml)
<http://www.asxcaml.org/>

The FreerP Project
<http://www.freerp.org/>

Re: generic functions

[Daniel Yokomizo]

"skaller" <skaller@users.sourceforge.net> escreveu na mensagem
news:1105316629.2647.119.camel@pelican.wigram...

> It is also known that overloading CAN work with
> inference with some contraints -- there is a paper somewhere
> on Citeseer on this topic (sorry don't have the URL at the
> moment, if someone finds it please let me know..)

System CT extends ML-style type inference for supporting overloading and
polymorphic recursion. The simplicity of core-ML type inference is
maintained, with no exception or special constructs included for coping with
overloading.

http://www.dcc.ufmg.br/~camarao/CT/

You can get this paper from citeseer too, so perhaps you had it in your
mind.

> -- 
> John Skaller, mailto:skaller@users.sf.net
> voice: 061-2-9660-0850,
> snail: PO BOX 401 Glebe NSW 2037 Australia
> Checkout the Felix programming language http://felix.sf.net

Best regards,
Daniel Yokomizo.

"I know this isn't the "right" way to do it, but it was quick, easy, and it
works pretty well."
 - John Hughes


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.832 / Virus Database: 566 - Release Date: 10/1/2005

Re: [Caml-list] generic functions

[Aleksey Nogin]

On 10.01.2005 01:55, Alex Baretta wrote:

> Let us all faithfully await the Coming of the the Gcaml...
> 
Is GCaml a part of an "official roadmap" for Caml? Can we expect (or at 
least hope) that GCaml will eventually have the same "mainstream Caml" 
status as OCaml currently has?

-- 
Aleksey Nogin

Home Page: http://nogin.org/
E-Mail: nogin@cs.caltech.edu (office), aleksey@nogin.org (personal)
Office: Jorgensen 70, tel: (626) 395-2907