From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.1.3 Received: from discorde.inria.fr (discorde.inria.fr [192.93.2.38]) by yquem.inria.fr (Postfix) with ESMTP id 3F099BC69 for ; Thu, 5 Jul 2007 14:39:17 +0200 (CEST) Received: from ipmail03.adl2.internode.on.net (ipmail03.adl2.internode.on.net [203.16.214.135]) by discorde.inria.fr (8.13.6/8.13.6) with ESMTP id l65CdEYY031443 for ; Thu, 5 Jul 2007 14:39:16 +0200 X-IronPort-AV: E=Sophos;i="4.16,503,1175437800"; d="scan'208";a="111966091" Received: from ppp121-44-3-31.lns4.syd7.internode.on.net (HELO [192.168.1.201]) ([121.44.3.31]) by ipmail03.adl2.internode.on.net with ESMTP; 05 Jul 2007 22:09:07 +0930 Subject: Re: [Caml-list] Incremental, undoable parsing in OCaml as the general parser inversion From: skaller To: oleg@pobox.com Cc: psnively@mac.com, caml-list@inria.fr In-Reply-To: <20070705081338.D090BAD43@Adric.metnet.fnmoc.navy.mil> References: <20070705081338.D090BAD43@Adric.metnet.fnmoc.navy.mil> Content-Type: text/plain Date: Thu, 05 Jul 2007 22:39:11 +1000 Message-Id: <1183639151.12890.19.camel@rosella.wigram> Mime-Version: 1.0 X-Mailer: Evolution 2.10.1 Content-Transfer-Encoding: 7bit X-Miltered: at discorde with ID 468CE672.000 by Joe's j-chkmail (http://j-chkmail . ensmp . fr)! X-Spam: no; 0.00; ocaml:01 parser:01 oleg:01 monadic:01 delimited:01 syntax:01 re-writing:01 lexer:01 monadic:01 ocaml:01 parser:01 syntax:01 inverts:01 subroutines:01 statically:01 On Thu, 2007-07-05 at 01:13 -0700, oleg@pobox.com wrote: > Paul Snively wrote: > > I've attempted to rewrite this in terms of your > > monadic version of delimited continuations, as included in the > > pa_monad syntax extension distribution. > > I'm afraid that cannot be done. That is, short of re-writing > make_lexer and all other library functions in the monadic style. That was my original point. You wrote: "This message is to show that the incremental parsing in OCaml is a solved problem -- essentially for any parser. Moreover, the procedure to convert from a regular parser to an incremental one is independent of the parser implementation." But this isn't so, because you confuse the meaning of 'parser' and 'implementation' to a programmer, as compared to a theoretician. A programmer thinks an 'implementation' is concrete syntax .. i.e. an actual text file.. a theoretician's 'concrete syntax' is still an abstract encoding. What you've shown is that it is possible to *manually* control invert a given algorithm. Now you should note what Felix does. It *mechanically* control inverts any algorithm encoded with Felix procedures. And I mean *concrete syntax* here :) That translation is universal and generated code is expensive to run due to many closures, but the cost is reduced by the optimiser so that code not requiring control inversion reduces to plain old subroutines. [Literally, procedure calls are converted to yielding the procedure to call, etc .. it's continuation passing] I am guessing my technique differs from what you describe in that the 'continuations' aren't statically delimited. That's a serious drawback of the current Felix implementation. The effect is that the inverted code only works with channels at the top level, that is, not inside a functional closure, because the latter use the machine stack and do cannot yield to the driver (scheduler). BTW: procedural code is just 'code written in a monadic style'. Every imperative programming language is just a purely functional one with monads.. This shows that monads have all the same problems as ordinary imperative code if you over use them (as of course is common practice in low level procedural programming languages). -- John Skaller Felix, successor to C++: http://felix.sf.net