From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 9F63C7FA5C for ; Sat, 14 May 2016 23:29:02 +0200 (CEST) IronPort-PHdr: 9a23:ntr6qh9v8ESSa/9uRHKM819IXTAuvvDOBiVQ1KB91+8cTK2v8tzYMVDF4r011RmSDdSdsakP0rSO+4nbGkU+or+5+EgYd5JNUxJXwe43pCcHRPC/NEvgMfTxZDY7FskRHHVs/nW8LFQHUJ2mPw6anHS+4HYoFwnlMkItf6KuSt+U1Z/8jr7qs7ToICx2xxOFKYtoKxu3qQiD/uI3uqBFbpgL9x3Sv3FTcP5Xz247bXianhL7+9vitMU7q3cY6Lod8JtLWKD+OqA5VqBwDTI8Mmlz6te4mwPESF6h/PoQ038XmVJiBBXfpEX0RJr9vzH7vax33zSAFcn/Trk+UDLk6ap3Hky7wBwbPiI0pTmEwvd7i7hW9Uqs Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=frederic.bour@lakaban.net; spf=Pass smtp.mailfrom=frederic.bour@lakaban.net; spf=None smtp.helo=postmaster@mail.lakaban.net Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of frederic.bour@lakaban.net) identity=pra; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="frederic.bour@lakaban.net"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of frederic.bour@lakaban.net designates 213.251.185.180 as permitted sender) identity=mailfrom; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="frederic.bour@lakaban.net"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail.lakaban.net) identity=helo; client-ip=213.251.185.180; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="frederic.bour@lakaban.net"; x-sender="postmaster@mail.lakaban.net"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0CpBAC+lzdX/7S5+9VehDdTuXKBdoYRAoFcEgEBAQEBAQEBZCeCLYIWAQEDASMEEQgBATgECwsaAiYCAlcTCAEBiCMMsXhnhEEBAQWMBwEKAQEBGwiBAYcagleFC4I0glmYLIh2jmeFWo9BJw0ugXmBdWyIBgEBAQ X-IPAS-Result: A0CpBAC+lzdX/7S5+9VehDdTuXKBdoYRAoFcEgEBAQEBAQEBZCeCLYIWAQEDASMEEQgBATgECwsaAiYCAlcTCAEBiCMMsXhnhEEBAQWMBwEKAQEBGwiBAYcagleFC4I0glmYLIh2jmeFWo9BJw0ugXmBdWyIBgEBAQ X-IronPort-AV: E=Sophos;i="5.24,619,1454972400"; d="scan'208";a="177833388" Received: from pepper.lakaban.net (HELO mail.lakaban.net) ([213.251.185.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 May 2016 23:29:01 +0200 Received: from [192.168.1.49] (mtg91-4-78-206-197-34.fbx.proxad.net [78.206.197.34]) (Authenticated sender: defre@ygg-drasil.fr) by mail.lakaban.net (Postfix) with ESMTPSA id 3AFE25F51C1 for ; Sat, 14 May 2016 21:28:36 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=lakaban.net; s=default; t=1463261316; bh=EOmyGusgRFtrmR2C456M45wimebhlcNuX0rKUWrGJ7U=; h=Subject:To:References:From:Date:In-Reply-To:From; b=YmxKq0lesuvzIYJLM5Y+EpvqZAfazxHiFlAe9vHZOCqVWuiGieSnIlvvq4n1z+ZVX 9Q+QSrIuczZ9hk7q3YtmwGadUbd8kqLryB18tw01i1H1l+XeBz/uyQVIvijFmnxEhm 4lR+CZe3aBRdWK6xAsnlxPNqg+6eSGoLDkTi9n+k= To: caml-list@inria.fr References: From: =?UTF-8?B?RnLDqWTDqXJpYyBCb3Vy?= Message-ID: <8f56349e-0e8d-4e3f-ca8b-3ff0733f88d7@lakaban.net> Date: Sat, 14 May 2016 23:29:07 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Caml-list] ocamllex and polymorphic recursion On 05/14/2016 09:50 PM, Nicolas Ojeda Bar wrote: > Hi list, > > I am trying to write a parser using ocamllex for a language for which > the usual character -> token -> ast does not make sense and instead > one needs to produce the ast directly from the character level. > > Even though this is not its intended use case, it actually works quite > well! Except that, while I can define higher-order rules, such as > > rule sp item = parse > | ' ' { item lexbuf } > > I cannot actually use such a rule for 'item's which return different > types. As far as I can see this is because the set of all rules is > translated into a set of recursively defined functions and using 'sp' > with 'items' of different types would require the function > corresponding to 'sp' to have some explicit polymorphism annotation. > > Is there a way to twist ocamllex a little more to make this work ? Or > if not, would it make sense to expose a way for the user to provide > these annotations herself ? Here is how I would do it: 1) Polymorphic recursion: - define a record type with one field for each rule, making types explicit: type rules = { sp : 'a. (Lexing.lexbuf -> 'a) -> Lexing.lexbuf -> 'a; ... } - make each rule take an argument of this type, and refer to rules by projecting from the record: rule foo rules = parse | 'int' { rules.sp rules.int_item lexbuf } | 'string' { rules.sp rules.string_item lexbuf } - tie the knot outside of the lexer: let rec rules = { sp = (fun lexbuf -> sp rules lexbuf); ... } When invoking the lexer, pass the rules argument too. 2) Variation with open recursion: If you assume each rule take the "rules" argument, you can use type recursion and avoid some annoyances when tying the knot. You will have to pass the "rules" argument manually each time you call a rule. type rules = { sp : 'a. (rules -> Lexing.lexbuf -> 'a) -> rules -> Lexing.lexbuf -> 'a; ... } rule foo rules = parse | 'int' { rules.sp rules.int_item rules lexbuf } | 'string' { rules.sp rules.string_item rules lexbuf } 3) Perhaps there is no recursion in "sp" definition. You can simply define 'sp' rule in a different lexer (and then call "FirstLexer.sp"). I am not 100% sure this 3) will work, but I think there is no shared state in the lexbuf after a rule succeed. Calling a different lexer should be fine. > Thanks! > > - Nicolas