Possibility of Nested Classes and Nested Inheritance?

Possibility of Nested Classes and Nested Inheritance?

[Jørgen Hermanrud Fjeld]

[-- Attachment #1: Type: text/plain, Size: 3773 bytes --]

Hi, 
I just read about the work by Nystrom, Chong and Myers on nested
inheritance, specifically the article "Scalable Extensibility via Nested
Inheritance".

The article does demonstrate fascinating, to me, use of inheritance, and
I wonder if it is possible to do something similar and object-oriented in OCaml.

To do something similar would, according to my understanding, require
both inner classes and super-class polymorphism.
In understand inner classes as implicitly polymorphic with respect to the enclosing class,
and polymorphism on the super class as the practical ability to extend
the type hierarchy upwards.

Do you know of any work that relate nested inheritance to OCaml, or that
address the similar issuesof inner classes and super-class polymorphism?

I have tried to search the mailing list history, but I have not
found relevant threads for these issues.

It seems to me that inner classes can always be written as parametric
classes, which means that OCaml could easily support inner classes. 
Is this correct? Are there other intrinsic reasons why OCaml does not
have inner classes, except of course that it would take an effort to
implement, which I understand.

Super-class polymorphism seems like a different beast, and I would very
much appreciate any ideas, especially theoretical ideas, on how that 
would interact with the OCaml type system.

I imagine the following OCaml'ish example:
class a =
    class b = object ... end
    class c = object inherit b ... end
    object
    ...
end

class d =
    class b' = object inherit b ... end
    (* The following is implicit
    class c' = object inherit b inherit b'  inherit c ... end *)
    object
      inherit a
      ...
end

The inner classes are parametrised by the outer class, thus for the
class a this could be written instead:

class a =
    object
    ...
end
class ['a] b = object ... end
class ['a] c = object inherit ['a] b ... end

Here i use 'a because the examples is from a nominal type system, 
as the name 'a suggests, although this is just coincidental for O'Caml.

The class d is not such a clear case to write out, here is a try:

class d =
    object
      inherit a
      ...
end

class ['d] b' = object inherit ['d] b ... end
(* The following is implicit
class ['d] c' = 
    object 
	inherit ['d] b' 
	inherit ['d] c 
	... 
    end 
*)

It is this implicit part that I suspect could use super-class
polymorphism, because then the class c could be rewritten as:

class ['a,'b] c = 
    object 
	inherit ['a] 'b 
	... 
    end

and then the class c' would be the same as c, except that c' 
is parametrised by [d,b'], while c is parametrised by [a,b].

With name shadowing of classes and explicit polymorphism 
code could be written as:

class a =
    class ['a] b = object ... end
    class ['a,'b] c = object inherit 'b ... end
    object
    ...
end

class d =
    class ['a] b = object inherit b ... end
    (* The following is implicit because b is connected to 'b by magic ;-)
    class ['a,'b] = object inherit b' ... end 
    *)
    object
      inherit a
      ...
end

I hope this demonstrates the idea.

The following code is from the paper by Nystrom, Chong and Myers, 
to give a sample of their intuition:
class A {
  class B { int x; }
  class C extends B {...}
  int m(B b) { return b.x }
  C n() { return new C(); }
  }

class A2 extends A {
  class B {int y; } 
  int m(B b) {return b.x + b.y }
  }



-- 
Sincerely | Homepage:
Jørgen    | http://www.hex.no/jhf
          | Public GPG key:
          | http://www.hex.no/jhf/key.txt

Mystics always hope that science will some day overtake them.
		-- Booth Tarkington


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance?

[John Prevost]

On Thu, 16 Dec 2004 15:59:07 +0100, Jørgen Hermanrud Fjeld <jhf@hex.no> wrote:
> It seems to me that inner classes can always be written as
> parametric classes, which means that OCaml could easily support
> inner classes.  Is this correct? Are there other intrinsic
> reasons why OCaml does not have inner classes, except of course
> that it would take an effort to implement, which I understand.

One typical feature of inner classes that you will never see in O'Caml
is access to the private state of the surrounding class.  On the other
hand:

class a (xa : int) =
    object
      val mutable xb = xa
      method get_x = xb
      method set_x x = xb <- x
      method new_b () = object
        method get_x = xb
        method set_x x = xb <- x
      end
    end;;


Here you see that you can create an object in which the fields of the
containing object are in scope.  But this inner object is not a class,
so it cannot be inherited from.

Anyway, I will look at the rest of your email and look up the papers
your mention some time later.

John.

Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance?

[Jacques Garrigue]

From: "Jørgen Hermanrud Fjeld" <jhf@hex.no>

> I just read about the work by Nystrom, Chong and Myers on nested
> inheritance, specifically the article "Scalable Extensibility via Nested
> Inheritance".
> 
> The article does demonstrate fascinating, to me, use of inheritance, and
> I wonder if it is possible to do something similar and
> object-oriented in OCaml.
> 
> To do something similar would, according to my understanding, require
> both inner classes and super-class polymorphism.
> In understand inner classes as implicitly polymorphic with respect
> to the enclosing class,
> and polymorphism on the super class as the practical ability to extend
> the type hierarchy upwards.
> 
> Do you know of any work that relate nested inheritance to OCaml, or that
> address the similar issuesof inner classes and super-class polymorphism?

Answer 1: there are no inner classes in ocaml.
Answer 2: there are plenty of other ways to obtain similar effects.

I don't know exactly what fascinated you in the paper, so it is hard
to answer precisely, but there are already a few techniques in ocaml to
solve the problems they describe.
(Of course they wouldn't cite them, as ocaml doesn't look like a
relevant language to them.)

Their compiler example seems to be a variant of the expression
problem.
There are several solutions to the expression problem in ocaml, using
either polymorphic variants
  http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/fose2000.html
or objects
  http://pauillac.inria.fr/~remy/work/expr/

On the more general question of virtual types, Didier Rémy and Jérôme
Vouillon gave a detailed "refutation".
  http://pauillac.inria.fr/~remy/work/virtual/

So you can see if you can do all what you need with the above methods.
If you find some unexpected limitation, please let us now.

Jacques Garrigue

Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance?

[Jacques Garrigue]

A small complement to my previous post.

From: Nate Nystrom <nystrom@cs.cornell.edu>

> Furthermore, to allow extension, recursion is left open for
> the functions implementing the compiler passes and then closed
> in order to invoke the function on a particular type.  Thus, when a new 
> variant is added, a small amount of code for each open recursive
> function needs to be written to close the recursion with the new type.

This kind of practical problems could be easily solved by syntactic
sugar.
Yet, you can see a direct approach (without sugar) in this code sample
  http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/mixin2.ml.txt
The idea is to use classes like modules with inheritance and
recursion (using lazyness to get a fixpoint). So we get closer to your
approach.
(I've cleaned-up a little, but this code has been at this URL for years.)


Another more general remark, which might seem somehow contradictory,
is that functional programs do not have the same notion of modularity.
In particular, as the typing helps a lot, this is not seen as a
problem to directly modify existing code (which modular extension
prohibits).
So one writes code with the possibility of future modifications in
mind, making it more robust by avoiding ad-hoc defaults. When you have
no default, the type checker can track changes to types, and force you
to modify relevant code.

Jacques Garrigue

Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance?

[Jacques Garrigue]

From: Nate Nystrom <nystrom@cs.cornell.edu>

Thank you for your answer.
I'm happy to see you're interested in the functional view.

> From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
> > Answer 1: there are no inner classes in ocaml.
> 
> Another alternative is to use nested inheritance with modules.  This
> likely requires that module inheritance be added to the language,
> although there may be other approaches that fit in better with the ocaml
> module system.  In fact, we expect that in Jx (our extension of Java 
> with nested inheritance) package inheritance will be the main use of
> nested inheritance.

I'm not sure of what you mean by nested inheritance with modules.
But it wouldn't solve the problem in caml, as modules do not contain
implicit recursion: added definitions will not change the behaviour of
previous ones.
This is actually an advantage for reasoning about the code: scope is
static and ordered. But this makes inheritance of limited practical
use. (You have already flat inheritance with include.)

> > Answer 2: there are plenty of other ways to obtain similar effects.
> >
> > I don't know exactly what fascinated you in the paper, so it is hard
> > to answer precisely, but there are already a few techniques in ocaml to
> > solve the problems they describe.
> > (Of course they wouldn't cite them, as ocaml doesn't look like a
> > relevant language to them.)
> 
> I admit I was unaware of polymorphic variants.  I certainly would
> have cited ocaml had I been aware of them.

I hope I didn't offend you. It was just a generic remark about the
limited interest functional approaches enjoy in the object-oriented
community, even when they solve the same problem.

> > Their compiler example seems to be a variant of the expression
> > problem.
> 
> The expression problem is an instance of what we call scalable
> extensibility.

Indeed.

> > There are several solutions to the expression problem in ocaml, using
> > either polymorphic variants
> >   http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/fose2000.html
> 
> I don't see how polymorphic variants solve the expression problem.
> As I understand them, if I were to implement a compiler using 
> polymorphic variants, I would create a variant for each term
> in the language, then write functions that match against those
> variants to implement the compiler passes.
> 
> However, if I want to add a new term to the language, I would
> have to add a new variant, then write new functions for each of
> the compiler passes to handle the new variant, delegating to the
> old functions for the old variants.  Thus if I have n passes
> implemented as functions, I have to write O(n) code to add a
> new term.  Please correct me if I'm wrong on this.
> Zenger and Odersky's ICFP'00 paper on extensible algebraic
> datatypes with defaults addresses this particular problem.
> 
> Furthermore, to allow extension, recursion is left open for
> the functions implementing the compiler passes and then closed
> in order to invoke the function on a particular type.  Thus, when a new 
> variant is added, a small amount of code for each open recursive
> function needs to be written to close the recursion with the new type.

You're right about the paper.
But this doesn't mean this does not solve the expression problem.
The expression problem is about the possibility of extension both by
adding new constructors and new operations. It is well known that
there are two types of solution for it: data-centered (or
object-oriented) and operation-centered (or functional decomposition).
By definition, the functional approach is operation-centered.
It means that adding a new constructor costs more than in the
data-centered approach, but adding a new operation costs less.
The cost of both is irrelevent to whether a solution is valid or not,
but if you want to compare you must consider the two kinds of
extensions.

By the way, if you just add a new construct in the language, it may
be better to simply go around modifying existing code, rather than
writing new delegation code, but this wouldn't solve the expression
problem.
Actually, I thought at first that this approach was too cumbersome to
be practical. But some people use it, and are satisfied with it.
And note that closing the recursion is in practice very light: you
just have to apply the pattern.

Another point, which John Skaller has just made, is that you can
perfectly define functions with default behaviours. I do it all the
time. The basic idea is to use a structural map or iter
function, which allows you to only code the non-standard cases.
This is dangerous, because your new constructors may actually require a
different handling. But the point here is that you can choose whether
you allow a default or not, and only have defaults when it is
reasonable to have them. So I would say that the functional approach
gives greater flexibility in your assumptions about future extensions.

> > or objects
> >   http://pauillac.inria.fr/~remy/work/expr/
> >
> > On the more general question of virtual types, Didier Rémy and Jérôme
> > Vouillon gave a detailed "refutation".
> >   http://pauillac.inria.fr/~remy/work/virtual/
> 
> This paper shows that you can use parametric polymorphism to solve the
> same problems virtual types were designed to address.  The problem to
> look out for with this approach is that you may end up parameterizing a
> class on a large number of related classes, e.g., parameterizing
> a compiler pass class on every AST node class (in our Java compiler,
> there are 40-50 such classes).  This paper argues that, in practice, you
> won't have too many parameters because you only need to parameterize on
> types on which there is actually a constraint.  I think this does not
> work with our compiler problem.  Using the traditional visitor pattern,
> you will have to parameterize the visitor class on every AST node class.

You should realize that you are not parameterizing with classes, but
with types. In practice you have only few types (or categories) of
nodes in an AST. In a functional language it would be 3: expressions,
patterns and types, with the previous not appearing inside the latter.
So it is reasonable to keep this kind of parameterization.

Cheers,

Jacques Garrigue

Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance?

[skaller]

On Sat, 2004-12-25 at 06:48, Nate Nystrom wrote:

>  Using the traditional visitor pattern,
> you will have to parameterize the visitor class on every AST node class.

Given a term for expressions, and a map_expr function
which is a functional visitor, I can write:

let rec cfold x = 
	match map_expr cfold x with
	| `Add (`Int a, `Int b) -> `Int (a + b)
	| other -> other

The fact that this formulation admits any number of extra
variants without change is a problem! I could add
a new term `Sub for subtraction and forget to add
the code to fold subtraction of constants.

In fact I have done just that, it took several hours 
to find the bug.

-- 
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] Possibility of Nested Classes and Nested Inheritance?

[Nate Nystrom]

From: Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>
> From: "Jørgen Hermanrud Fjeld" <jhf@hex.no>
>
>> I just read about the work by Nystrom, Chong and Myers on nested
>> inheritance, specifically the article "Scalable Extensibility via 
>> Nested Inheritance".
>>
>> The article does demonstrate fascinating, to me, use of inheritance, 
>> and I wonder if it is possible to do something similar and
>> object-oriented in OCaml.
>>
>> To do something similar would, according to my understanding, require
>> both inner classes and super-class polymorphism.
>> In understand inner classes as implicitly polymorphic with respect
>> to the enclosing class,
>> and polymorphism on the super class as the practical ability to extend
>> the type hierarchy upwards.
>>
>> Do you know of any work that relate nested inheritance to OCaml, or 
>> that
>> address the similar issuesof inner classes and super-class 
>> polymorphism?
>
> Answer 1: there are no inner classes in ocaml.

Another alternative is to use nested inheritance with modules.  This
likely requires that module inheritance be added to the language,
although there may be other approaches that fit in better with the ocaml
module system.  In fact, we expect that in Jx (our extension of Java 
with nested inheritance) package inheritance will be the main use of
nested inheritance.

> Answer 2: there are plenty of other ways to obtain similar effects.
>
> I don't know exactly what fascinated you in the paper, so it is hard
> to answer precisely, but there are already a few techniques in ocaml to
> solve the problems they describe.
> (Of course they wouldn't cite them, as ocaml doesn't look like a
> relevant language to them.)

I admit I was unaware of polymorphic variants.  I certainly would
have cited ocaml had I been aware of them.

>
> Their compiler example seems to be a variant of the expression
> problem.

The expression problem is an instance of what we call scalable
extensibility.

> There are several solutions to the expression problem in ocaml, using
> either polymorphic variants
>   http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/papers/fose2000.html

I don't see how polymorphic variants solve the expression problem.
As I understand them, if I were to implement a compiler using 
polymorphic variants, I would create a variant for each term
in the language, then write functions that match against those
variants to implement the compiler passes.

However, if I want to add a new term to the language, I would
have to add a new variant, then write new functions for each of
the compiler passes to handle the new variant, delegating to the
old functions for the old variants.  Thus if I have n passes
implemented as functions, I have to write O(n) code to add a
new term.  Please correct me if I'm wrong on this.
Zenger and Odersky's ICFP'00 paper on extensible algebraic
datatypes with defaults addresses this particular problem.

Furthermore, to allow extension, recursion is left open for
the functions implementing the compiler passes and then closed
in order to invoke the function on a particular type.  Thus, when a new 
variant is added, a small amount of code for each open recursive
function needs to be written to close the recursion with the new type.

> or objects
>   http://pauillac.inria.fr/~remy/work/expr/
>
> On the more general question of virtual types, Didier Rémy and Jérôme
> Vouillon gave a detailed "refutation".
>   http://pauillac.inria.fr/~remy/work/virtual/

This paper shows that you can use parametric polymorphism to solve the
same problems virtual types were designed to address.  The problem to
look out for with this approach is that you may end up parameterizing a
class on a large number of related classes, e.g., parameterizing
a compiler pass class on every AST node class (in our Java compiler,
there are 40-50 such classes).  This paper argues that, in practice, you
won't have too many parameters because you only need to parameterize on
types on which there is actually a constraint.  I think this does not
work with our compiler problem.  Using the traditional visitor pattern,
you will have to parameterize the visitor class on every AST node class.

> So you can see if you can do all what you need with the above methods.
> If you find some unexpected limitation, please let us now.
>
> Jacques Garrigue

Nate