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 3126C801CD for ; Thu, 17 Aug 2017 14:49:04 +0200 (CEST) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=gabriel.scherer@gmail.com; spf=Pass smtp.mailfrom=gabriel.scherer@gmail.com; spf=None smtp.helo=postmaster@mail-qt0-f181.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of gabriel.scherer@gmail.com) identity=pra; client-ip=209.85.216.181; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of gabriel.scherer@gmail.com designates 209.85.216.181 as permitted sender) identity=mailfrom; client-ip=209.85.216.181; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="gabriel.scherer@gmail.com"; 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-qt0-f181.google.com) identity=helo; client-ip=209.85.216.181; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="gabriel.scherer@gmail.com"; x-sender="postmaster@mail-qt0-f181.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AdISTCRWoisY0JC4Je9Gcb38rFvnV8LGtZVwlr6E/?= =?us-ascii?q?grcLSJyIuqrYZhWAt8tkgFKBZ4jH8fUM07OQ6P+wHzFYqb+681k8M7V0Hycfjs?= =?us-ascii?q?sXmwFySOWkMmbcaMDQUiohAc5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aMlzFOAF0?= =?us-ascii?q?PuX4HJLJx4Tyjrjqus6bXwIdrzqnYKhuKw22miVPucQMyd9pKrww0QfOunsOe+?= =?us-ascii?q?Nbym5yDVmemxvm78C28dho9CEG6Nw78MsVfqzwZaU1SfRjBzQrKW0vrJnkvBPZ?= =?us-ascii?q?TAaLoGAXUmgMnwBgDA3M7RW8VZD05Hip/tFh0TWXaJWlBYs/Xi6vuuIyEEfl?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AnAgATkJVZf7XYVdFUCR0BBQELARcBA?= =?us-ascii?q?QQBAQoBAYQTgRUHhSaYd4FuiSiMcw6CBCyFGwKEUAdAFwEBAQEBAQEBAQEBEgE?= =?us-ascii?q?BCQsLCCYxgjMFAR4BBYI8AQICASMdARsJFAEDAQsGAwILNwICIgERAQUBHAYTC?= =?us-ascii?q?IoPAQMNCBCMIJEbP4wKggQFARyDCQWDZgoZJw1Wg0ABAQEBAQEEAQEBAQEBARk?= =?us-ascii?q?CAQUSgxaCAoFMhQqEPQxXgmaCYQWgSYIohSyMbpJclFQVH4EVIQGBPzIhJF4ah?= =?us-ascii?q?G6CFD42h2MqRIFTAQEB?= X-IPAS-Result: =?us-ascii?q?A0AnAgATkJVZf7XYVdFUCR0BBQELARcBAQQBAQoBAYQTgRU?= =?us-ascii?q?HhSaYd4FuiSiMcw6CBCyFGwKEUAdAFwEBAQEBAQEBAQEBEgEBCQsLCCYxgjMFA?= =?us-ascii?q?R4BBYI8AQICASMdARsJFAEDAQsGAwILNwICIgERAQUBHAYTCIoPAQMNCBCMIJE?= =?us-ascii?q?bP4wKggQFARyDCQWDZgoZJw1Wg0ABAQEBAQEEAQEBAQEBARkCAQUSgxaCAoFMh?= =?us-ascii?q?QqEPQxXgmaCYQWgSYIohSyMbpJclFQVH4EVIQGBPzIhJF4ahG6CFD42h2MqRIF?= =?us-ascii?q?TAQEB?= X-IronPort-AV: E=Sophos;i="5.41,387,1498514400"; d="scan'208,217";a="234668552" Received: from mail-qt0-f181.google.com ([209.85.216.181]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 17 Aug 2017 14:49:02 +0200 Received: by mail-qt0-f181.google.com with SMTP id p3so36683550qtg.2; Thu, 17 Aug 2017 05:49:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=BksoDNUvGCFfelb6Zr9MPia6OYMi/v9e8SECDrSlzqQ=; b=r0gacl54HcXX+a5LYFcAEtbCBI15aHLnPSvAbpwpI+WzHOvWE9lT7utWlIUwwjuicx z5v+KLDtNGi+CPAYsYLVuFKOhwoB7KDfGhwBIYxWQORZSx6Z9AbkkT3o+b8qtXgm3mWp F1ykN2NP9qyrMckcwsWBD1THLiVzhajLaxThKtoinQ235xUynmJhrNhm2Emd/DzxxTjd EMjG6+RMDDs9WIj05FjJFfmPt6N87aYJV6lV8FKUjw+1b/r3G1kFYAi8sy5Lv7VRbceZ tTNmpZ0+Z2nljSrqCOtdeB3y2gLADfj8h/pW7aJcKfjrpFtSl1GgDUlaSYlj0en+/ZlG xLZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=BksoDNUvGCFfelb6Zr9MPia6OYMi/v9e8SECDrSlzqQ=; b=NMi7Di1gOrD8mhywaSpw8y5YdagEdzmJc+NL2ZVmfdDtJRNbcRFVCpoHo7suKNHlhX wysooNyFZODUp2wZFWsZWo/t6xmJCvDxrBAn6C2xGsczTb2IYIZS+2G7c5NJ7Q5a/qQ/ ABLOv/NNb0/0PqHOVAw/oanHQzpUUKi3964+07Tz34NRXB02WPAndFI+qpz+fatZSBCl 2NPKYwBVaM2rR58xZLStLGgFnlV2lLhpk+tqCnRwPujmLiqflAx3IFZJcHY0d0a2F+xf C17bZEVRnJ7rAEh/2MMKA5Q0Srcx6vKkNCcwPO7DCGRG8fgRztGFGgCkbjbFJuMkcLMx lLbA== X-Gm-Message-State: AHYfb5ghZG4lcNnqlNdyKrmcJIKRrrgQ/I7B7ODaLZO9mWVMw40JckHE SNmWvOMCmDnI+9YrzuS5mg7fhzjba7qX X-Received: by 10.200.35.188 with SMTP id q57mr7013912qtq.238.1502974141478; Thu, 17 Aug 2017 05:49:01 -0700 (PDT) MIME-Version: 1.0 Received: by 10.12.184.148 with HTTP; Thu, 17 Aug 2017 05:48:21 -0700 (PDT) In-Reply-To: References: From: Gabriel Scherer Date: Thu, 17 Aug 2017 14:48:21 +0200 Message-ID: To: =?UTF-8?Q?Christoph_H=C3=B6ger?= Cc: OCaml Mailing List , Francois Pottier Content-Type: multipart/alternative; boundary="001a113fddcecf3d0d0556f26fe0" Subject: Re: [Caml-list] default fold for visitors --001a113fddcecf3d0d0556f26fe0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable This is only a minor comment not addressing the main question, but I was surprised by Christoph's assumption that folding on a tree (repeatedly calling Set.add) would be more efficient than a divide-and-conquer merge approach (repeatedly calling Set.union), at least with a balanced-search-tree implementation of sets. I would rather have assumed that a divide-and-conquer merge may be faster, on the vague hunch that merging whole trees instead of single leaves (adding a key is like merging a leave) allows to reuse information between comparing the root of a tree and merging its substrees. I wrote a quick benchmark ( https://gitlab.com/gasche-snippets/tree-fold-merge-benchmark ) that collects leaves of a binary tree into a set, and it turns out that which is faster depends on the key ordering. If the keys are completely random, then the fold-based code is twice faster. If the keys are mostly sorted, then the merge-based code is twice faster. The fold-based code performance seems independent of the key distribution, it is the merge-based code that goes from twice slower to twice faster depending on the scenario. My proposed explanation would be that merging two trees where all the keys in a tree are larger than almost all the keys in the other is fast (this is the case where little rebalancing is needed), so this hits a good case where tree-form indeed reuses comparison information. On the contrary, random trees are not faster than just calling add on all leaves. (I would guess that in complexity tree union is always as good as repeated-add or better, for all key distributions, but that the constant factors of the current implementation are higher because we manipulate more slightly complex data structures.) On Thu, Aug 17, 2017 at 1:57 PM, Christoph H=C3=B6ger < christoph.hoeger@celeraone.com> wrote: > Dear all (especially Francois), > > I am currently porting a DSL to OCaml and wanted to use the most modern > ppx approach for the typical boilerplate. One of the first things is the > implementation of the free variables with the help of ppx_visitors. > Naturally, the set of free variables forms a monoid, so I can comfortably > use the reduce variety. But that allocates quite a lot of temporary sets, > so I had a look into the fold variety. > > If I understand the documentation correctly, this class requires to define > a build method for each variant of the datatype. I wonder if there is a w= ay > to have a "default" function, namely the identity of the result value? > > Consider, for example the simple lambda calculus: > > > type expr =3D Abs of (string[@opaque]) * expr | App of expr * expr | Var = of > (string[@opaque]) [@@deriving visitors { variety =3D "fold" }] > > In that case, you'd want to define > > method build_Abs () x =3D StrSet.remove x > method build_Var () =3D StrSet.singleton > > but also have to > > method build_App () =3D StrSet.union > > According to the manual, the visitor should be something like this: > > method visit_App () l r fvs0 =3D > let fvs1 =3D self#visit_expr () l fvs0 in > let fvs2 =3D self#visit_expr () l fvs1 in > self#build_App () fvs1 fvs2 (* Why is this /always/ > necessary ? *) > > I suppose this final step of building the results allows some flexibility, > but in my case I could as well just yield fvs2. I wonder if it would be > possible to have a default implementation like this: > > method build_App () _ r =3D r > > For now, I am perfectly fine with the reduce variety, but I suppose that > there are some use cases where you would actually need to fold, but only > some variants actually do something. Is this a reasonable idea or is there > some caveat in the design of ppx_visitors that makes it impossible? > > thanks, > > Christoph > --001a113fddcecf3d0d0556f26fe0 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
This is only a minor comment not addressing the = main question, but I was surprised by Christoph's assumption that foldi= ng on a tree (repeatedly calling Set.add) would be more efficient than a di= vide-and-conquer merge approach (repeatedly calling Set.union), at least wi= th a balanced-search-tree implementation of sets. I would rather have assum= ed that a divide-and-conquer merge may be faster, on the vague hunch that m= erging whole trees instead of single leaves (adding a key is like merging a= leave) allows to reuse information between comparing the root of a tree an= d merging its substrees.

I wrote a quick benchmark ( https://g= itlab.com/gasche-snippets/tree-fold-merge-benchmark ) that collects lea= ves of a binary tree into a set, and it turns out that which is faster depe= nds on the key ordering. If the keys are completely random, then the fold-b= ased code is twice faster. If the keys are mostly sorted, then the merge-ba= sed code is twice faster. The fold-based code performance seems independent= of the key distribution, it is the merge-based code that goes from twice s= lower to twice faster depending on the scenario.

My proposed e= xplanation would be that merging two trees where all the keys in a tree are= larger than almost all the keys in the other is fast (this is the case whe= re little rebalancing is needed), so this hits a good case where tree-form = indeed reuses comparison information. On the contrary, random trees are not= faster than just calling add on all leaves.

(I would guess that in= complexity tree union is always as good as repeated-add or better, for all= key distributions, but that the constant factors of the current implementa= tion are higher because we manipulate more slightly complex data structures= .)



On Thu, Aug 17, 2017 at 1:57 PM, Christoph H=C3=B6ger = <chr= istoph.hoeger@celeraone.com> wrote:
Dear all (especially Francois),

I am curre= ntly porting a DSL to OCaml and wanted to use the most modern ppx approach = for the typical boilerplate. One of the first things is the implementation = of the free variables with the help of ppx_visitors. Naturally, the set of = free variables forms a monoid, so I can comfortably use the reduce variety.= But that allocates quite a lot of temporary sets, so I had a look into the= fold variety.

If I understand the documentation correctly, this cl= ass requires to define a build method for each variant of the datatype. I w= onder if there is a way to have a "default" function, namely the = identity of the result value?

Consider, for example the simple lamb= da calculus:


type expr =3D Abs of (string[@opaque]) * expr | App= of expr * expr | Var of (string[@opaque]) [@@deriving visitors { variety = =3D "fold" }]

In that case, you'd want to define
<= br>method build_Abs () x =3D StrSet.remove x
method build_Var () =3D St= rSet.singleton

but also have to

method build_App () =3D StrSe= t.union

According to the manual, the visitor should be something lik= e this:

method visit_App () l r fvs0 =3D
=C2=A0 let fvs1 =3D self= #visit_expr () l fvs0 in
=C2=A0 let fvs2 =3D self#visit_expr () l fvs1 i= n
=C2=A0 self#build_App () fvs1 fvs2=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0= =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 (* Why is this /alwa= ys/ necessary ? *)

I suppose this final step of building the results= allows some flexibility, but in my case I could as well just yield fvs2. I= wonder if it would be possible to have a default implementation like this:=

method build_App () _ r =3D r

For now, I am perfectly fine w= ith the reduce variety, but I suppose that there are some use cases where y= ou would actually need to fold, but only some variants actually do somethin= g. Is this a reasonable idea or is there some caveat in the design of ppx_v= isitors that makes it impossible?

thanks,

Christoph

--001a113fddcecf3d0d0556f26fe0--