From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 7849ABB91 for ; Sat, 25 Dec 2004 12:00:00 +0100 (CET) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id iBPAxwSI013305 for ; Sat, 25 Dec 2004 11:59:59 +0100 Received: from localhost (suiren [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.13.1/8.13.1) with ESMTP id iBPAxnUU014346; Sat, 25 Dec 2004 19:59:49 +0900 (JST) Date: Sat, 25 Dec 2004 19:59:32 +0900 (JST) Message-Id: <20041225.195932.18223648.garrigue@math.nagoya-u.ac.jp> To: nystrom@cs.cornell.edu Cc: caml-list@yquem.inria.fr, andru@cs.cornell.edu Subject: Re: [Caml-list] Possibility of Nested Classes and Nested Inheritance? From: Jacques Garrigue In-Reply-To: References: <20041217184433.GA1036@balm.cs.cornell.edu> X-Mailer: Mew version 4.0.64 on Emacs 21.3 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Miltered: at concorde with ID 41CD482E.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 cornell:01 ocaml:01 ocaml:01 recursion:01 variants:01 cited:01 compiler:01 scalable:01 variants:01 wwwfun:01 compiler:01 datatypes:01 defaults:01 recursion:01 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: From: Nate Nystrom Thank you for your answer. I'm happy to see you're interested in the functional view. > From: Jacques Garrigue > > 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 oc= aml > 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 har= d > > to answer precisely, but there are already a few techniques in ocam= l 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, usi= ng > > 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 n= ew = > 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=E9my and J=E9= r=F4me > > Vouillon gave a detailed "refutation". > > http://pauillac.inria.fr/~remy/work/virtual/ > = > This paper shows that you can use parametric polymorphism to solve th= e > 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 patter= n, > you will have to parameterize the visitor class on every AST node cla= ss. 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