From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA25999; Tue, 21 May 2002 22:03:36 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id WAA26032 for ; Tue, 21 May 2002 22:03:35 +0200 (MET DST) Received: from holmes.infopro.spb.su (holmes.infopro.spb.su [195.242.2.2]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g4LK3YL20666 for ; Tue, 21 May 2002 22:03:35 +0200 (MET DST) Received: from stapleton.peterlink.ru (stapleton.peterlink.ru [195.242.2.5]) by holmes.infopro.spb.su (8.9.1/8.9.1) with ESMTP id AAA11433; Wed, 22 May 2002 00:03:34 +0400 (MSD) Received: from intellij.com (IDENT:mitya@spb-2-154.dialup.peterlink.ru [195.242.17.154]) by stapleton.peterlink.ru (8.12.3/8.12.3) with ESMTP id g4LK3TZk082259; Wed, 22 May 2002 00:03:31 +0400 (MSD) Message-ID: <3CEAA891.5070807@intellij.com> Date: Wed, 22 May 2002 00:05:37 +0400 From: Dmitry Lomov Organization: SPbSU User-Agent: Mozilla/5.0 (X11; U; Linux i586; en-US; rv:0.9.8) Gecko/20020206 X-Accept-Language: en-us MIME-Version: 1.0 To: Remi VANICAT CC: caml-list@inria.fr Subject: Dynamic Caml vs. MetaOCaml [long] (Was: Re: [Caml-list] ANN: Dynamic Caml v0.2 is released) References: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Remi, sorry for the late answer - I've been offline for a (somewhat prolonged :)) weekend. I'll answer your second question first, and then I'll try to explain the differences between approaches of MetaOCaml and Dynamic Caml. Remi VANICAT wrote: > Dmitry Lomov writes: >>I am pleased to announce the availability of Dynamic Caml v.0.2 > > But it seem also (I may be wrong) that MetaOCaml enable more easily > multi stage generation (that is program that generate program that > generate program) Is this feasible with dml ? > It is true that MetaOcaml supports multi-stage generation on a syntactic level: let f x = .< fun y -> .< fun z -> x + y + z >. >. let i = (.! (.! f 1) 2) 3 (* 6 *) Dynamic Caml currently does not have this kind of syntax, i.e. it does not support {< ... >} inside {< ... >}. But that does not mean that you cannot do multistage generation with Dynamic Caml. As often, if some consruct is not supported in Dynamic Caml, you can simulate it by functional wrappers. If dml supported embedded {< >}, the above code would look like: let f x = {< fun y -> {< fun z -> ``x + `y + z >} >} let i = (eval ((eval (f 1) 2) 3 (note the number of backquotes before x and y). One can manually translate this into dynamically generated applications of Rtcg primitives - replacing "{< fun z -> ... >}" with (apply (quote abstr) (abstr (fun z -> ...))), "`y" with "(apply (quote quote) y)" etc, resulting in the following: let plus o1 o2 = int_bin o1 IOpADD o2 let f x = abstr (fun y -> apply (quote abstr) (abstr (fun z -> (apply (apply (quote plus) (apply (apply (quote plus) (quote (quote x)) (*1*) ) (apply (quote quote) y) ) ) z ) ) ) ) let i = (eval ((eval (f 1) 2) 3 (* 1: direct translation of ``x will be (apply (quote quote) (quote x)), but this can be obviously optimized *) This works, though this looks ugly of course :) (so you probably wont be able to do any serious multi-staging this way). As you see, it is not impossible to add multi-staging to dml. The main reason why I have not done this yet is probably lack of motivation - not many real-life problems seriously benefit from more than 2 stages of computation. Even in benchmarks provided with MetaOCaml there are no programs with more than two stages. You may find further information on how to go from two-stage to multi-stage generation (for Scheme) in Robert Gluck and Jesper Jorgensen's paper "Efficient Multi-level Generating Extensions for Program Specialization" (they study multi-level partial evaluators, that is DCG with "implicit", or "BTA-style", annotations, but their implementation includes a multi-level DCG framework). > > As I see it, the main difference is that MetaOcaml is a modification > of the ocaml compiler, and dml is an external library, but is there > any more in depth difference between the two ? (By the way, MetaOCaml > lack a good documentation). > MetaOCaml is more of the research tool for multi-stage computations, while my motivation for Dynamic Caml was to build something moreless usable in real life. I believe that multi-stage features are nice to have in the language, but they are not (at current stage of research?) useful enough to dedicate a whole language (or even non-trivial compiler modifications) for :). I think also that tools like CamlP4 is indispensable for making this kind of external libraries - nicely integrated into language and still keeping the core language and technologies :) behind it intact. Now, to real stuff :). You are right in saying that the main difference between MetaOCaml and Dynamic Caml is the former being a new language while the latter is an external library. All other differences stem from this principal difference. 1. Types. Main research efforts in types as related to DCG concentrate in avoiding the thing called "arguquoting" in dml manual, that is the code variable escaping its evaluation scope. There are two flavours of arguquoting: * "external arguquoting" can be demonstrated by the following: let f = eval {< fun x -> `x >} in let g = eval (abstr (fun y -> f 27)) in ... Here x escapes its evaluation scope in f. * "internal arguquoting" happens when code variable is evaluated before it's value is known: let f = eval {< fun x -> @(eval {< x >}) >} in ... Although x is defined in "eval {< x >}", evaluation of "eval {< x >}" happens before construction of the function, and thus value of x is undefined (not known yet). MetaOCaml fights "external arguquoting" with a technique called Cross-Stage Persistence (CSP). That is, MetaOCaml does not give the user access to "quote" primitive (or "`" operator) - it infers necessary "quoting level" from type of variable (that is, the level of .< >. surronding its declaration) and insert the neccessary amount of quotes. However, MetaOCaml is unable to detect "internal arguquoting" statically. Basically, all research around MetaML was, I believe, concentrated on finding the type system that prevents these two kinds of arguquoting without prohibiting "legal" programs. The core of the problem is that the term given to "eval" should not be contain any free variables from stages higher or equal to that at which eval is executed. In the latest papers on the subject (Walid Taha et al. "An Idealized MetaML: Simpler, and More Expressive") this seems to be achived, but at the cost of quite verbose syntax. However, it is still unclear AFAIK whether all legal programs are valid. Walid Taha's excellent papers on the subject are very interesting (they are available from his web page). Dynamic Caml, being just a library, cannot modify the type system, and hence cannot employ CSP, so it has to provide an explicit "quote" operator. The above examples of arguquoting will type check in Dynamic Caml, but their execution will result in exception UndefinedVariable. The first example is impossible in MetaOCaml, but the second is: let f = .< fun x -> .~(.! .< x >.) >. MetaOCaml _fully type-checks_ the dynamically generated code at run-time, and the above will result in TypeCheckingException. So, MetaOCaml is probably more "sound" than Dynamic Caml, but this comes at a price of compiler and run-time system modification. 2. Implementation First thing to say is that Dynamic Caml is faster than MetaOCaml. I implemented the benchmarks that come with MetaOCaml in Dynamic Caml, and code generation times of the latter are 3 to 8 times less than of the former, and the execution time of generated code (i.e. generated code quality)is the same. I believe this is due to the facts that Dynamic Caml does not do the type checking at code generation time (while still detecting all the problems :)) and that Dynamic Caml uses a specially designed lightweight code generator and lower level internal program representation (MetaOCaml reuses ocamlc code generator which probably was not written with speed very much in mind :). In fact, the only code generation cost layer that has been removed in MetaOCaml is parsing. Type-checking, type inference etc. is there.) But, of course, not knowing type information at code generation time in Dynamic Caml leads to quite some problems. There are may constructs that are not supported natively. For example, getting a field of a record is tricky because at run-time there is no way to obtain an offset of a field. Dynamic Caml here inlines a functional wrapper (in fact, it get the information about the offset from the bytecode of a wrapper!). So it could probably benefit from a little help from his friend, ocaml compiler :). Hope this helps, and feel free to criticise this and ask if something's unclear. Friendly, Dmitry -- Dmitry Lomov Chair of Software Engineering, Fcaulty of Mathmatics and Mechanics, St.-Petersburg State University ------------------- 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