[Caml-list] About polymorphic methods and recursive classes

[Caml-list] About polymorphic methods and recursive classes

[Sébastien Briais]

Hello,

(I tried to send this mail yesterday, but apparently it did not work.
So I send it again:)

I tried to encode lists with objects.
I defined a class list which is virtual and that contains only a visit 
method
which is polymorphic.
I have defined also a virtual class visitor to visit the lists.
The ocaml toplevel indicated me there was an error in my piece of code
but since I didn't understand the error message, I have simplified my piece
in order to understand which part is not accepted by ocaml.

Here is the simplified code

 > ledit ocaml
         Objective Caml version 3.06

# class virtual ['a] visitor =
   object
     method virtual caseNil : 'a
   end
   and virtual int_list =
   object
     method virtual visit : 'a.('a visitor -> 'a)
   end
   ;;
class virtual ['a] visitor : object method virtual caseNil : 'a end
class virtual int_list : object method virtual visit : 'a visitor -> 'a end

# class nil =
   object
     inherit int_list
     method visit v = v#caseNil
   end
   ;;
This expression has type 'a visitor
It has no method caseNil

This is this last message that I do not understand.

I tried also to remove the 'and' in the recursive class definitions
(since here, the two classes are not really recursive because I have
removed the caseCons method in the visitor) and ocaml accepts this
modified code.

I tried also to instantiate the 'a type parameter with int (so I have
caseNil:int and visit:visitor->int) and this is also accepted.

Why is my code rejected ? What does mean the error message ?

Thank you

Regards

Sébastien


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

Re: [Caml-list] About polymorphic methods and recursive classes

[Damien]

On Sat, 22 Mar 2003 12:22:44 +0100
Sébastien Briais <sebastien.briais@epfl.ch> wrote:

> Hello,
hello

> # class virtual ['a] visitor =
>    object
>      method virtual caseNil : 'a
>    end
>    and virtual int_list =
>    object
>      method virtual visit : 'a.('a visitor -> 'a)
>    end
>    ;;
> class virtual ['a] visitor : object method virtual caseNil : 'a end
> class virtual int_list : object method virtual visit : 'a visitor ->
> 'a end
> 
> # class nil =
>    object
>      inherit int_list
>      method visit v = v#caseNil
>    end
>    ;;
> This expression has type 'a visitor
> It has no method caseNil

it seems to work with class types :

#   class type ['a] visitor_t = object 
	method caseNil: 'a 
end;;
  class type ['a] visitor_t = object method caseNil : 'a end

# class type int_list_t = object 
	method visit: 'a. ('a visitor_t) -> 'a
end;; 
  class type int_list_t = object method visit : 'a visitor_t -> 'a end

# class nil: int_list_t = object
  method visit: 'a. ('a visitor_t) -> 'a = fun v -> v#caseNil
end;;
      class nil : int_list_t


damien

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

Re: [Caml-list] About polymorphic methods and recursive classes

[Sebastien Briais]

>
>
>># class virtual ['a] visitor =
>>   object
>>     method virtual caseNil : 'a
>>   end
>>   and virtual int_list =
>>   object
>>     method virtual visit : 'a.('a visitor -> 'a)
>>   end
>>   ;;
>>class virtual ['a] visitor : object method virtual caseNil : 'a end
>>class virtual int_list : object method virtual visit : 'a visitor ->
>>'a end
>>
>># class nil =
>>   object
>>     inherit int_list
>>     method visit v = v#caseNil
>>   end
>>   ;;
>>This expression has type 'a visitor
>>It has no method caseNil
>>    
>>
>
>it seems to work with class types :
>  
>
ok, but it does not answer my question.

I am still puzzled by the answer of the interpreter which says me that
"v has type 'a visitor; It has no method caseNil"
although it has inferred just before that
"class virtual ['a] visitor : object method virtual caseNil : 'a end"

Moreover, it seems odd to me that it works with class types but not without.
These class types should be inferred by Ocaml, shouldn't they ? (and 
they seems
to be correctly inferred in my example (in the first part of it))

So I ask again : how should I interpret the error message given by ocaml ?

Regards

Sébastien



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

Re: [Caml-list] About polymorphic methods and recursive classes

[Jacques Garrigue]

From: Sebastien Briais <sebastien.briais@epfl.ch>
> >># class virtual ['a] visitor =
> >>   object
> >>     method virtual caseNil : 'a
> >>   end
> >>   and virtual int_list =
> >>   object
> >>     method virtual visit : 'a.('a visitor -> 'a)
> >>   end
> >>   ;;
> >>class virtual ['a] visitor : object method virtual caseNil : 'a end
> >>class virtual int_list : object method virtual visit : 'a visitor ->
> >>'a end
> 
> I am still puzzled by the answer of the interpreter which says me that
> "v has type 'a visitor; It has no method caseNil"
> although it has inferred just before that
> "class virtual ['a] visitor : object method virtual caseNil : 'a end"
> 
> Moreover, it seems odd to me that it works with class types but not without.
> These class types should be inferred by Ocaml, shouldn't they ? (and 
> they seems
> to be correctly inferred in my example (in the first part of it))

Actually no. Polymorphic methods are not inferred, but declared.
And polymorphic type variables should not be used as parameters to
simultaneously defined types.
Actually, your mutually recursive definition should not be accepted to
begin with. It clearly results in a wrong internal type.

The problem is not virtual class vs. class types. The virtual class
version will work if you drop the recursion (replace "and" by "class").

> So I ask again : how should I interpret the error message given by ocaml ?

As a bug in the compiler. The error should be reported earlier.

   Jacques Garrigue

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

[Caml-list] Re: About polymorphic methods and recursive classes

[Andrzej M. Ostruszka]

On Mon, Mar 24 (2003), Sebastien Briais wrote:
> So I ask again : how should I interpret the error message given by ocaml ?

My guess it is a bug but FWIW

># class virtual ['a] visitor =
>   object
>     method virtual caseNil : 'a
>   end
>   and virtual int_list =
    ^^^
>   object
>     method virtual visit : 'a.('a visitor -> 'a)
>   end
>   ;;
[...]

the problem is with "and" above.  Change it to class (the two classes
are not recursive so there's no harm) and it'll be OK.

						Best regards
-- 
    ____   _  ___
   /  | \_/ |/ _ \		Andrzej Marek Ostruszka
  / _ |     | (_) | Instytut Fizyki, Uniwersytet Jagiellonski (Cracow)
 /_/ L|_|V|_|\___/	(PGP <-- finger ostruszk@order.if.uj.edu.pl)

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

Re: [Caml-list] About polymorphic methods and recursive classes

[Sebastien Briais]

Jacques Garrigue wrote:

>From: Sebastien Briais <sebastien.briais@epfl.ch>
>  
>
>>>># class virtual ['a] visitor =
>>>>  object
>>>>    method virtual caseNil : 'a
>>>>  end
>>>>  and virtual int_list =
>>>>  object
>>>>    method virtual visit : 'a.('a visitor -> 'a)
>>>>  end
>>>>  ;;
>>>>class virtual ['a] visitor : object method virtual caseNil : 'a end
>>>>class virtual int_list : object method virtual visit : 'a visitor ->
>>>>'a end
>>>>        
>>>>
>>I am still puzzled by the answer of the interpreter which says me that
>>"v has type 'a visitor; It has no method caseNil"
>>although it has inferred just before that
>>"class virtual ['a] visitor : object method virtual caseNil : 'a end"
>>
>>Moreover, it seems odd to me that it works with class types but not without.
>>These class types should be inferred by Ocaml, shouldn't they ? (and 
>>they seems
>>to be correctly inferred in my example (in the first part of it))
>>    
>>
>
>Actually no. Polymorphic methods are not inferred, but declared.
>And polymorphic type variables should not be used as parameters to
>simultaneously defined types.
>Actually, your mutually recursive definition should not be accepted to
>begin with. It clearly results in a wrong internal type.
>  
>
So, if I understand you well, it is not possible to write something like 
that in ocaml:

class virtual ['a,'b] list_visitor =
object
  method virtual caseNil : 'a
  method virtual caseCons : 'b -> 'b list -> 'a
end
and virtual ['b] list =
object
  method virtual visit : 'a.(('a,'b) list_visitor -> 'a)
end

class ['a] nil =
object
  inherit ['a] list
  method visit v = v#caseNil
end

class ['a] cons = fun h t ->
object
  inherit ['a] list
  method visit v = v#caseCons h t
end

and especially, the first definition should be considered as incorrect 
since the
polymorphic variable 'a of list is used as a parameter of the list_visitor.

But what is the reason of this limitation ? 
I do not see the reasons since for example, in Generic Java, such a 
definition is correct

abstract class Visitor<a, b> {
  abstract a caseNil();
  abstract a caseCons(b x, List<b> xs);
}

abstract class List<b> {
  abstract <a> a visit(Visitor<a, b> v);
}

Can you explain in more details your answer ?
Does it lead to type insafety or indecidability of typing to authorize 
polymorphic
type variables to be used as parameters to simulteanously defined types ?


Regards

Sébastien


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

Re: [Caml-list] About polymorphic methods and recursive classes

[Florian Hars]

Sebastien Briais wrote:
> But what is the reason of this limitation ? I do not see the reasons 
> since for example, in Generic Java, such a definition is correct

I don't know if it is directly related to your problem, but Generic Java 
is a bad reference point, because it's type inference is know to be unsound:

http://www.cis.upenn.edu/~bcpierce/types/archives/current/msg00849.html

Yours, Florian

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

Re: [Caml-list] About polymorphic methods and recursive classes

[Sebastien Briais]

Florian Hars wrote:

> Sebastien Briais wrote:
>
>> But what is the reason of this limitation ? I do not see the reasons 
>> since for example, in Generic Java, such a definition is correct
>
>
> I don't know if it is directly related to your problem, but Generic 
> Java is a bad reference point, because it's type inference is know to 
> be unsound:
>
> http://www.cis.upenn.edu/~bcpierce/types/archives/current/msg00849.html
>
> Yours, Florian
>
This problem in type inference has been fixed  since january 2002:

http://www.cis.upenn.edu/~bcpierce/types/archives/current/msg00921.html

Sébastien


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

Re: [Caml-list] About polymorphic methods and recursive classes

[Jacques Garrigue]

From: Sebastien Briais <sebastien.briais@epfl.ch>

> >Actually no. Polymorphic methods are not inferred, but declared.
> >And polymorphic type variables should not be used as parameters to
> >simultaneously defined types.
> >Actually, your mutually recursive definition should not be accepted to
> >begin with. It clearly results in a wrong internal type.
> >
> So, if I understand you well, it is not possible to write something like 
> that in ocaml:
> 
> class virtual ['a,'b] list_visitor =
> object
>   method virtual caseNil : 'a
>   method virtual caseCons : 'b -> 'b list -> 'a
> end
> and virtual ['b] list =
> object
>   method virtual visit : 'a.(('a,'b) list_visitor -> 'a)
> end

Right.
The only workaround I see is to unroll the recursion:

class type ['a,'b,'c] list_visitor_t = object
  method caseNil : 'a
  method caseCons : 'b -> 'c -> 'a
end
class type ['b] alist = object
  method visit : 'a. ('a,'b,'b alist) list_visitor_t -> 'a
end
class type ['a,'b] list_lisitor = ['a,'b,'b alist] list_visitor_t

class ['b] nil = object (_ : 'b #alist)
  method visit x = x#caseNil
end

class ['b] cons h t = object (_ : 'b #alist)
  method visit x = x#caseCons h t
end

I agree this is not a very intuitive solution.

> But what is the reason of this limitation ?
> I do not see the reasons since for example, in Generic Java, such a 
> definition is correct.

Generic Java is another language, and it does not have ML-style type
inference. It is very hard to compare. There are lots of tricks you
can do with type inference that you cannot do with a fully declared
language.

For those who remember old discussions about loss of polymorphism in
mutually recursive type definitions in earlier versions of caml, this
is related: in order to propagate type constraints, type variables in
class definitions are only generalized after then end of the whole
definition, which in this case is too late.

You can also see this as bug, and not so easy to fix.

> Can you explain in more details your answer ?
> Does it lead to type insafety or indecidability of typing to authorize 
> polymorphic type variables to be used as parameters to
> simulteanously defined types ?

According to the target you choose, this can probably lead to
indecidabilty. There should be some reasonnable solution,
avoiding going too far, but the interaction with constraints is going
to be really hard to avoid.
I was unaware of this problem until it was posted on this list.

Jacques Garrigue

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

Re: [Caml-list] About polymorphic methods and recursive classes

[Jacques Garrigue]

From: Sebastien Briais <sebastien.briais@epfl.ch>

> So, if I understand you well, it is not possible to write something like 
> that in ocaml:
> 
> class virtual ['a,'b] list_visitor =
> object
>   method virtual caseNil : 'a
>   method virtual caseCons : 'b -> 'b list -> 'a
> end
> and virtual ['b] list =
> object
>   method virtual visit : 'a.(('a,'b) list_visitor -> 'a)
> end
> 
> But what is the reason of this limitation ? 
> I do not see the reasons since for example, in Generic Java, such a 
> definition is correct.

My previous answer was a bit vague, but actually the problem is more
intrinsic to ocaml objects.
Contrary to Java, Ocaml object types are defined structurally, rather
than by name. For this reason, recursion has to be limited to cases
where recursive occurences of a type constructor have always the
same arguments. But in your example, 'b list in list_visitor expands
to < visit : 'a. ('a,'b) list_visitor -> 'a >, where list_visitor has
different arguments from its definition (the 'a here is an universal
variable, different from the normal 'a listed as parameter in the
definition).

As I showed, the only workaround is to untie the mutual recursion by
replacing 'b list by an extra parameter.

This is a bit similar to the reason you cannot define a map method:
class type ['a] list = object
  method map : 'b. ('a -> 'b) -> 'b list
end
but in that case you cannot untie the recursion: 'b in 'b list is
locally bound.

Jacques Garrigue

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