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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 940A3BC6B for ; Fri, 30 Nov 2007 11:53:44 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAB96T0eBrw8Eh2dsb2JhbACPQAEBAQgKKQ X-IronPort-AV: E=Sophos;i="4.23,233,1194217200"; d="scan'208";a="19842709" Received: from ext.lri.fr ([129.175.15.4]) by mail4-smtp-sop.national.inria.fr with ESMTP; 30 Nov 2007 11:53:44 +0100 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id 3F9A3A48B3; Fri, 30 Nov 2007 11:53:44 +0100 (CET) X-Virus-Scanned: Debian amavisd-new at lri.fr Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id yBGxVx0OTcFo; Fri, 30 Nov 2007 11:53:44 +0100 (CET) Received: from [129.175.4.117] (lri4-117 [129.175.4.117]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ext.lri.fr (Postfix) with ESMTP id 225E3A4864; Fri, 30 Nov 2007 11:53:44 +0100 (CET) Message-ID: <474FEE12.6080000@lri.fr> Date: Fri, 30 Nov 2007 12:03:46 +0100 From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?= User-Agent: Thunderbird 1.5.0.14pre (X11/20071023) MIME-Version: 1.0 To: Jon Harrop Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Help with simple ocaml memoization problem References: <200711290811.29007.jon@ffconsultancy.com> <474E7F2B.6090007@lri.fr> <200711292225.33048.jon@ffconsultancy.com> In-Reply-To: <200711292225.33048.jon@ffconsultancy.com> X-Enigmail-Version: 0.94.2.0 OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 ocaml:01 memoization:01 unions:01 computed:01 traversing:01 nodes:01 lri:01 filliatr:01 wrote:01 clearer:01 caml-list:01 grammar:02 Jon Harrop wrote: > Incidentally, what are the pedagogical applications of shared maps? Here is an example: when computing the FIRST and FOLLOW sets of a grammar, you typically make unions of already computed sets for same or other non-terminals. It potentially results in sharing between the various sets. More generally, static analysis traversing AST and computing sets (or maps) for various nodes (liveness analysis, etc.) are likely to build data structures which share subparts (when they are tree-based data structures typically). I hope it makes my point a little clearer. -- Jean-Christophe Filliātre http://www.lri.fr/~filliatr/