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=1.7 required=5.0 tests=AWL,DNS_FROM_RFC_ABUSE, HTML_MESSAGE,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id A6458BC68 for ; Sat, 30 Sep 2006 21:19:26 +0200 (CEST) Received: from nf-out-0910.google.com (nf-out-0910.google.com [64.233.182.188]) by concorde.inria.fr (8.13.6/8.13.6) with ESMTP id k8UJJQbI021306 for ; Sat, 30 Sep 2006 21:19:26 +0200 Received: by nf-out-0910.google.com with SMTP id y38so1259411nfb for ; Sat, 30 Sep 2006 12:19:25 -0700 (PDT) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com; h=received:message-id:date:from:to:subject:cc:in-reply-to:mime-version:content-type:references; b=JqmAAL3e/LbaMaGhWpf8jCloymA1VTZc2l1G2ujxqRTm35eA/9vldohoVYtdjNCqxVTR38t3XN15rK2Lu3KLk2dJubsdECzvNoWkzSRYb3ULTl2J6PpYUad9kmBvwZtCfaqftv7Nvw0H0fcjmgfrtvBnd92IZWnagdVZGwGUivk= Received: by 10.48.210.20 with SMTP id i20mr7010806nfg; Sat, 30 Sep 2006 12:19:25 -0700 (PDT) Received: by 10.49.32.12 with HTTP; Sat, 30 Sep 2006 12:19:25 -0700 (PDT) Message-ID: Date: Sat, 30 Sep 2006 21:19:25 +0200 From: Tom To: "Diego Olivier FERNANDEZ PONS" Subject: Re: [Caml-list] More problems with memoization Cc: caml-list@inria.fr In-Reply-To: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="----=_Part_27044_29990263.1159643965793" References: <20060930200125.bjpzgnh7kkkogkgk@webmail.etu.upmc.fr> X-j-chkmail-Score: MSGID : 451EC33E.000 on concorde : j-chkmail score : X : 0/20 1 X-Miltered: at concorde with ID 451EC33E.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; memoization:01 ocaml:01 ocaml:01 memoize:01 inference:01 memoization:01 memoize:01 inference:01 W8:98 W6:98 W6:98 polymorphic:01 polymorphic:01 partial:01 partial:01 X-Attachments: cset="UTF-8" cset="UTF-8" ------=_Part_27044_29990263.1159643965793 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Content-Disposition: inline In case you know me, you probably know what kind of solution I am going to tell you... Well, in case you don't... my solution is going to be dirty, is going to use the undocumented Obj module (Obj.magic lets you change an ocaml value into another ocaml value of any type). ----------- The solution is to memoize the very make_mem function! let make_mem' = function f -> let table = ref [] in function n -> try List.assoc n !table with Not_found -> let f_n = f n in table := (n, f_n) :: !table; f_n;; let make_mem = make_mem' make_mem' Well, the problem is, that the ocaml type inference forbids a function to return a polymorphic value, so the type of make_mem' is only ('_a -> '_b) -> '_a -> '_b. So the right thing to do here (as this type is, obviously, incorrect) is to use Obj.magic: let make_mem'' = Obj.magic make_mem' let make_mem = (make_mem'' : ('a -> 'b) -> 'a -> 'b) Now, the fibb will work as expected (instantaneously) and memoization will be simple to apply. A bit of thinking is needed, of course, to reckon whether my implementation is optimal and safe (not yielding unexpected results, for example when you rename functions, use partial evaluation, etc.). But it works. Have fun, Tom ------=_Part_27044_29990263.1159643965793 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit Content-Disposition: inline In case you know me, you probably know what kind of solution I am going to tell you...

Well, in case you don't... my solution is going to be dirty, is going to use the undocumented Obj module (Obj.magic lets you change an ocaml value into another ocaml value of any type).

-----------

The solution is to memoize the very make_mem function!

let make_mem' = function f ->
      let table = ref [] in
      function n ->
      try
       List.assoc n !table
      with Not_found ->
       let f_n = f n in
         table := (n, f_n) :: !table;
   f_n;;

let make_mem = make_mem' make_mem'

Well, the problem is, that the ocaml type inference forbids a function to return a polymorphic value, so the type of make_mem' is only ('_a -> '_b) -> '_a -> '_b. So the right thing to do here (as this type is, obviously, incorrect) is to use Obj.magic:

let make_mem'' = Obj.magic make_mem'

let make_mem = (make_mem'' : ('a -> 'b) -> 'a -> 'b)

Now, the fibb will work as expected (instantaneously) and memoization will be simple to apply. A bit of thinking is needed, of course, to reckon whether my implementation is optimal and safe (not yielding unexpected results, for example when you rename functions, use partial evaluation, etc.). But it works.

Have fun, Tom


------=_Part_27044_29990263.1159643965793--