[Caml-list] static variables in a function

[Caml-list] static variables in a function

[Shannon --jj Behrens]

Hi,

What is the correct OCAML idiom for achieving the
following psuedocode?

let get_chunk () =
  static chunks_list;

  if List.is_empty chunks_list
  then chunks_list = get_more_chunks ();
  shift chunks_list
;;

Thanks You,
-jj

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Stefano Zacchiroli]

On Fri, Jun 14, 2002 at 10:08:30AM -0700, Shannon --jj Behrens wrote:
> Hi,
> 
> What is the correct OCAML idiom for achieving the
> following psuedocode?
> 
> let get_chunk () =
>   static chunks_list;
> 
>   if List.is_empty chunks_list
>   then chunks_list = get_more_chunks ();
>   shift chunks_list
> ;;

an approximation (not tested) may be:

   let chunks_list = ref [] in
   let get_chunk () =
     if List.is_empty !chunks_list then
        chunks_list := get_more_chunks ();
     shift !chunks_list
   in
   (* code where you use get_chunk *)

Cheers.

-- 
Stefano Zacchiroli - undergraduate student of CS @ Univ. Bologna, Italy
zack@cs.unibo.it | ICQ# 33538863 | http://www.cs.unibo.it/~zacchiro
"I know you believe you understood what you think I said, but I am not
sure you realize that what you heard is not what I meant!" -- G.Romney
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Yutaka OIWA]

>> On Fri, 14 Jun 2002 10:08:30 -0700 (PDT), Shannon --jj Behrens <jjinux@yahoo.com> said:

Shannon> Hi,
Shannon> What is the correct OCAML idiom for achieving the
Shannon> following psuedocode?

Shannon> let get_chunk () =
Shannon>   static chunks_list;

Shannon>   if List.is_empty chunks_list
Shannon>   then chunks_list = get_more_chunks ();
Shannon>   shift chunks_list
Shannon> ;;

How about this?

let get_chunk =
  let chunks_list = ref [] in
  fun () ->
    ...

-- 
Yutaka Oiwa              Yonezawa Lab., Dept. of Computer Science,
      Graduate School of Information Sci. & Tech., Univ. of Tokyo.
      <oiwa@yl.is.s.u-tokyo.ac.jp>, <yutaka@oiwa.shibuya.tokyo.jp>
PGP fingerprint = C9 8D 5C B8 86 ED D8 07  EA 59 34 D8 F4 65 53 61
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Shannon --jj Behrens]

Thank you all for your speedy, helpful responses!  I
am also happy to see rough concensus in the correct
way to do this.

Thanks Again,
-jj

--- Yutaka OIWA <oiwa@yl.is.s.u-tokyo.ac.jp> wrote:
> >> On Fri, 14 Jun 2002 10:08:30 -0700 (PDT), Shannon
> --jj Behrens <jjinux@yahoo.com> said:
> 
> Shannon> Hi,
> Shannon> What is the correct OCAML idiom for
> achieving the
> Shannon> following psuedocode?
> 
> Shannon> let get_chunk () =
> Shannon>   static chunks_list;
> 
> Shannon>   if List.is_empty chunks_list
> Shannon>   then chunks_list = get_more_chunks ();
> Shannon>   shift chunks_list
> Shannon> ;;
> 
> How about this?
> 
> let get_chunk =
>   let chunks_list = ref [] in
>   fun () ->
>     ...
> 
> -- 
> Yutaka Oiwa              Yonezawa Lab., Dept. of
> Computer Science,
>       Graduate School of Information Sci. & Tech.,
> Univ. of Tokyo.
>       <oiwa@yl.is.s.u-tokyo.ac.jp>,
> <yutaka@oiwa.shibuya.tokyo.jp>
> PGP fingerprint = C9 8D 5C B8 86 ED D8 07  EA 59 34
> D8 F4 65 53 61


__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Max Kirillov]

Hello.

The code you write will generate a new (empty) ref at every
call. 

You can do like this:

--- chunks.ml
type chunk = ...
<...>
let chunks_list = ref ([]:chunk ref);; -- a separate value in a module
let get_chunk () = <youraction>
--- EOF

You can hide chunks_list by module interface.

--- chunks.mli
type chunk
<...>
(*val chunks_list: chunk list ref -- comment it away *)
val get_chunk: unit -> <returntype>
--- EOF

On Sat, Jun 15, 2002 at 02:58:45AM +0900, Yutaka OIWA wrote:
> let get_chunk =
>   let chunks_list = ref [] in
>   fun () ->
>     ...
> 

On Fri, Jun 14, 2002 at 10:08:30AM -0700, Shannon --jj Behrens wrote:
> What is the correct OCAML idiom for achieving the
> following psuedocode?
> 
> let get_chunk () =
>   static chunks_list;
> 
>   if List.is_empty chunks_list
>   then chunks_list = get_more_chunks ();
>   shift chunks_list
> ;;
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[John Prevost]

>>>>> "mk" == Max Kirillov <max630@mail.ru> writes:

    mk> Hello.  The code you write will generate a new (empty) ref at
    mk> every call.

Actually, it won't.  Take a look at the code that was sent by Yutaka OIWA:

let get_chunk =
  let chunks_list = ref [] in
  fun () ->
    ...

The ref is bound outside of the function definition, so it's created
once and kept in the closure, not allocated in each call.  If it were
written this way:

let get_chunk () =
  let chunks_list = ref [] in
  ...

or equivalently:

let get_chunk =
  fun () ->
    let chunks_list = ref [] in
    ...

it would be created separately for each call.  But the way it was
originally written is correct.

Your version also works, but creates a module-level binding for the
value as well, which isn't desirable for something like this, where
you want the value to be local to the function definition.

John.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Max Kirillov]

Oh, thank you for clarification. I'm very new to functional
programming, and didn't know yet about tricks like this. As
I understand, the point was to call 'ref' at initialization
stage. I thought about using 'lazy' for that, but still
placed it inside a full function definition, so it didn't
help.

This makes a possibility to write very funny
functions. For example:

# let acc v =
    let vR = ref v in
    fun f -> 
            let newV = f !vR in
          vR := newV;
          newV  ;;
val acc : 'a -> ('a -> 'a) -> 'a = <fun>
# let f1 = acc 12;;
val f1 : (int -> int) -> int = <fun>
# f1 ((+) 1);;
- : int = 13
# f1 ((+) 1);;
- : int = 14
# f1 ((+) 1);;
- : int = 15
# f1 ((+) 1);;
- : int = 16
# f1 ((+) 1);;
- : int = 17
# let f2 = acc "hello";;
val f2 : (string -> string) -> string = <fun>
# f2 ((^) " a");;       
- : string = " ahello"
# f2 ((^) " b");;
- : string = " b ahello"
# f2 ((^) " c");;
- : string = " c b ahello"

I'm not sure if this style of coding better than placing the
mutable values to be hidden inside modules or classes. Even
when possible (in other languages), I prefer to use
latter way to do. Well it's a matter of taste.

Max.

On Sat, Jun 15, 2002 at 02:36:03AM -0400, John Prevost wrote:
>>>>>> "mk" == Max Kirillov <max630@mail.ru> writes:
> 
>mk> Hello.  The code you write will generate a new (empty) ref at
>mk> every call.
> 
> Actually, it won't.  Take a look at the code that was sent by Yutaka OIWA:
> 
> let get_chunk =
>   let chunks_list = ref [] in
>   fun () ->
>     ...
> 
> The ref is bound outside of the function definition, so it's created
> once and kept in the closure, not allocated in each call. 
<...>
> Your version also works, but creates a module-level binding for the
> value as well, which isn't desirable for something like this, where
> you want the value to be local to the function definition.
> 
> John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[John Prevost]

>>>>> "mk" == Max Kirillov <max630@mail.ru> writes:

    mk> Oh, thank you for clarification. I'm very new to functional
    mk> programming, and didn't know yet about tricks like this. As I
    mk> understand, the point was to call 'ref' at initialization
    mk> stage. I thought about using 'lazy' for that, but still placed
    mk> it inside a full function definition, so it didn't help.

    mk> This makes a possibility to write very funny functions. For
    mk> example:

# let acc v =
    let vR = ref v in
    fun f -> 
            let newV = f !vR in
          vR := newV;
          newV  ;;

    mk> I'm not sure if this style of coding better than placing the
    mk> mutable values to be hidden inside modules or classes. Even
    mk> when possible (in other languages), I prefer to use latter way
    mk> to do. Well it's a matter of taste.

It also depends precisely what you're trying to do.  In the case we
first saw (we have a specific function that wants to have an input
buffer, essentially), I'm not sure it makes a great amount of sense.
The problem is that using a variable in the closure doesn't help do
anything except hide the value from the rest of the module.  And,
well, we'd probably be better off leaving it open to the module and
using the module interface to hide it from other modules.

If we change our focus, howeverm the technique becomes more
interesting.  Take a look at this, for example:

type 'a memoval =
  | Val of 'a
  | Exn of exn

let memoize f =
  let stow = Hashtbl.create 20 in
  fun x -> begin
    if not (Hashtbl.mem stow x) then begin
      try (let v = f x in Hashtbl.replace stow x (Val v))
        with e -> Hashtbl.replace stow x (Exn e)
     end;
    match Hashtbl.find stow x with
      | Val x -> x
      | Exn e -> raise e
  end

(* this is the fibonacci sequence, but we delaying "binding" the
   recursion until later. *)
let fib' fib' =
  function
    | 0 -> 1
    | 1 -> 1
    | n -> fib' (n-1) + fib' (n-2);;

(* example of how to bind the recursion in a simple way *)
let rec fib_r1 x =
  fib' fib_r1 x

(* and now binding it "through" the memoize function *)
let rec fib_r2 x =
  memoize (fib' fib_r2) x

In this case, the whole point of the function is that it produces a
function identical in every way to the original function, except that
it memoizes its work so as not to repeat.  There's no convenient
"object" to stuff the value into, because the function *is* our
object.  The only way we can store the data correctly is to have the
information somehow attached to the function we're creating.

There are a number of places where this is useful.  The key insight is
that in a functional language, the primary objects in the system are
functions, and this mechanism we're using above is simply what happens
when a variable goes out of scope for everything except the function
in question.

JOhn.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Max Kirillov]

[-- Attachment #1: Type: text/plain, Size: 2419 bytes --]

On Sat, Jun 15, 2002 at 12:14:09PM -0400, John Prevost wrote:
<...>
> If we change our focus, howeverm the technique becomes more
> interesting.  Take a look at this, for example:
<...>
> let memoize f =

Hmm... this isn't executed at read time because function has
a parameter...

>   let stow = Hashtbl.create 20 in
>   fun x -> begin
>     if not (Hashtbl.mem stow x) then begin
>       try (let v = f x in Hashtbl.replace stow x (Val v))
>         with e -> Hashtbl.replace stow x (Exn e)
>      end;
>     match Hashtbl.find stow x with
>       | Val x -> x
>       | Exn e -> raise e
>   end
<...>
> let rec fib_r2 x =
>   memoize (fib' fib_r2) x

The function memoize (and even "memoize (fib' fib_r2)" with
a variable first parameter) as called at every recursion
step and therefore no caching will be performed. (I've
tested it).

The working way is:

let fib_r3 = memoize fib_r1

which is, btw, very similar to

let fib_r3 = new memoize fib_r1

> In this case, the whole point of the function is that it produces a
> function identical in every way to the original function, except that
> it memoizes its work so as not to repeat.  There's no convenient
> "object" to stuff the value into, because the function *is* our
> object.  The only way we can store the data correctly is to have the
> information somehow attached to the function we're creating.

Well, OO-biased programmer would say it's a good reson to
_make_ an object with only one exported method. Nearly any
programmer would say that we should make an object to
provide additional control, say, to clear the cache.

I've played with it a bit, and discover that there are many
ways to do the job. Three files attached contains three ways
of doing the same things via function returned from
initialization func (accPart.ml), commonly known OO-patterns
(accClass.ml) and modules system (accMod.ml). Tha task is to
remember a function and initial value, then sending operands
for successive applications of function.

To allow several "methods" to deal with data object we must
return several function, not just one. Moreover, we cannot
use inheritance, as we can with classes.

accMod.ml discovers generally the same features as
accClass.ml, but contains a bit more verbose writing. Maybe,
modules is not a good way to contain persistent mutable
value.

Max.

PS: maybe in version2 one could use record with labelled
things, to make it a bit nicer.

[-- Attachment #2: accPart.ml --]
[-- Type: text/plain, Size: 641 bytes --]

let p s n = print_string (s^string_of_int n^"\n"); flush stdout

(*version 1*)
let acc f init =
    let vR = ref init in
    let fApp x =
	let newX = f !vR x in
	vR := newX;
	newX in
    fApp

let f1 = acc (+) 0

let _ = p "f1:" (f1 1)
let _ = p "f1:" (f1 1)
let _ = p "f1:" (f1 1)

(*version 2*)
let acc' f init =
    let vR = ref init in
    let fApp x =
	let newX = f !vR x in
	vR := newX;
	newX
    and fIni x = (vR := x) in
    (fApp,fIni)

let (f1a,f1i) = acc' (+) 0

let _ = p "f1a:" (f1a 1)
let _ = p "f1a:" (f1a 1)
let _ = p "f1a:" (f1a 1)
let _ = f1i (-5)
let _ = p "f1a:" (f1a 1)
let _ = p "f1a:" (f1a 1)
let _ = p "f1a:" (f1a 1)

[-- Attachment #3: accClass.ml --]
[-- Type: text/plain, Size: 667 bytes --]

let p s n = print_string (s^string_of_int n^"\n"); flush stdout

(*version 1*)
class ['a,'b] acc f init = object
    val mutable v = (init:'a)
    val func = (f:'a -> 'b -> 'a)
    method app x =
	let newX = func v x in
	v <- newX;newX
end

let f1 = new acc (+) 0

let _ = p "f1:" (f1#app 1)
let _ = p "f1:" (f1#app 1)
let _ = p "f1:" (f1#app 1)

(*version 2*)
class ['a,'b] acc' f init = object
    inherit ['a,'b] acc f init
    method init x = v <- x
end

let f2 = new acc' (+) 0

let _ = p "f2:" (f2#app 1)
let _ = p "f2:" (f2#app 1)
let _ = p "f2:" (f2#app 1)
let _ = f2#init (-5)
let _ = p "f2:" (f2#app 1)
let _ = p "f2:" (f2#app 1)
let _ = p "f2:" (f2#app 1)

[-- Attachment #4: accMod.ml --]
[-- Type: text/plain, Size: 951 bytes --]

let p s n = print_string (s^string_of_int n^"\n"); flush stdout

module type AccArgT = sig
    type t and t1
    val init: t
    val f: t -> t1 -> t
end

module AccArgInt(I:sig val init:int val f:int->int->int end) = struct
    type t = int and t1 = int
    let init = I.init and f = I.f
end

(*version 1*)
module Acc(T:AccArgT) = struct
    let vR = ref T.init
    let func = T.f
    let app x =
	let newX = func !vR x in
	vR := newX;newX
end

module F1 = Acc(AccArgInt(struct let init = 0 and f = (+) end))

let _ = p "f1:" (F1.app 1)
let _ = p "f1:" (F1.app 1)
let _ = p "f1:" (F1.app 1)

(*version 2*)
module Acc1(T:AccArgT) = struct
    module A = Acc(T)
    include A
    let init x = vR:=x
end

module F2 = Acc1(AccArgInt(struct let init = 0 and f = (+) end))

let _ = p "f2:" (F2.app 1)
let _ = p "f2:" (F2.app 1)
let _ = p "f2:" (F2.app 1)
let _ = F2.init (-5)
let _ = p "f2:" (F2.app 1)
let _ = p "f2:" (F2.app 1)
let _ = p "f2:" (F2.app 1)

Re: [Caml-list] static variables in a function

[John Prevost]

>>>>> "mk" == Max Kirillov <max630@mail.ru> writes:

    mk> Hmm... this isn't executed at read time because function has a
    mk> parameter...

Yup.  I messed up.  The dangers of writing code in email without testing it...

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Remi VANICAT]

Max Kirillov <max630@mail.ru> writes:

> On Sat, Jun 15, 2002 at 12:14:09PM -0400, John Prevost wrote:
> <...>
>> If we change our focus, howeverm the technique becomes more
>> interesting.  Take a look at this, for example:
> <...>
>> let memoize f =
>
> Hmm... this isn't executed at read time because function has
> a parameter...

this code :
let memoize f =
  let stow = Hashtbl.create 20 in
  fun x -> begin
    if not (Hashtbl.mem stow x) then begin
      try (let v = f x in Hashtbl.replace stow x (Val v))
        with e -> Hashtbl.replace stow x (Exn e)
     end;
    match Hashtbl.find stow x with
      | Val x -> x
      | Exn e -> raise e
  end

was correct :
it create a new Hastable for each different function one want to
memoize. Otherwise the hastable will be shared between different
function, what we realy don't want.

look at this for a proof of what I'm saying :

# let print_once = memoize print_endline;;
val print_once : string -> unit = <fun>
# print_once "foo";;
foo
- : unit = ()
# print_once "bar";;
bar
- : unit = ()
# print_once "bar";;
- : unit = ()
# 

the last time, the value isn't recompile (and then nothing is
printed), so the memoization have worked.


-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Memoizing (was: static variables...)

[Benedikt Rosenau]

Remi Vanicat wrote:

[...]

> let memoize f =
>   let stow = Hashtbl.create 20 in
>   fun x -> begin
>     if not (Hashtbl.mem stow x) then begin
>       try (let v = f x in Hashtbl.replace stow x (Val v))
>         with e -> Hashtbl.replace stow x (Exn e)
>      end;
>     match Hashtbl.find stow x with
>       | Val x -> x
>       | Exn e -> raise e
>   end

I tried to memoize the Ackermann function

# let rec ack m n =
    if m = 0 then n + 1
    else if n = 0 then ack (m - 1) 1
    else ack (m - 1) (ack m (n - 1))
val ack : int -> int -> int = <fun>
# let my_ack = memoize ack;;
val my_ack : int -> int -> int = <fun>


The type checker deals with the 'a being an (int -> int).
However, I noticed no speedup. So, I transformed the
Ackermann to the tupled version, ie "let ackermann (m, n)...",
but to no avail.

What is the mistake?

Regards,
   Benedikt
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[William Lovas]

On Mon, Jun 17, 2002 at 03:56:04PM +0200, Benedikt Rosenau wrote:
> I tried to memoize the Ackermann function
> 
> # let rec ack m n =
>     if m = 0 then n + 1
>     else if n = 0 then ack (m - 1) 1
>     else ack (m - 1) (ack m (n - 1))
> val ack : int -> int -> int = <fun>
> # let my_ack = memoize ack;;
> val my_ack : int -> int -> int = <fun>
> 
> 
> The type checker deals with the 'a being an (int -> int).
> However, I noticed no speedup. So, I transformed the
> Ackermann to the tupled version, ie "let ackermann (m, n)...",
> but to no avail.
> 
> What is the mistake?

Benedikt,

I think the problem is something like this: when you call memoize (and bind
the result, for that matter), you create a new closure (above, you call it
`my_ack').  This *closure* is memoized, but recursive calls inside it,
which refer to the original closure (`ack') are not.  

Since Ackermann's function does a lot of repeated computation (correct me
if i'm wrong), it would benefit from a sort of "total memoization", but
i've been having a hard time figuring out how that would work in O'Caml.
I think this is what John Prevost was aiming to solve with his "delayed
binding" recursion, but i haven't managed to contrive a complete solution
using that method -- either we have only top-level calls to the function
being memoized, or no memoization goes on at all.  E.g.,

    let recfib recfib = function
      | 0 | 1 -> 1
      | n -> recfib (n-1) + recfib (n-2);;

    (* simple binding *)
    let rec fib n = recfib fib n;;

    (* through memoize *)
    let rec wrong_fib_1 n = memoize (recfib wrong_fib_1) n;;

    (* another way, also wrong *)
    let wrong_fib_2 = memoize fib;;

    (* *boggle* -- too tired to think about it, but also doesn't work *)
    let rec wrong_fib_3 n = recfib (memoize (recfib wrong_fib_3)) n;;

Now, if we do:

    wrong_fib_1 30;; (* takes a very long time *)
    wrong_fib_1 30;; (* still takes a very long time -- not memoized 
                        at all *)

    wrong_fib_2 30;; (* takes a very long time -- shouldn't, if fully
                        memoized *)
    wrong_fib_2 30;; (* instantaneous -- top-level is memoized *)

    wrong_fib_3 30;; (* like wrong_fib_1, very slow *)
    wrong_fib_3 30;; (* still slow -- no memoization happening *)

Note that we can observe the correct behaviour by writing the memoized
`fib' directly, e.g.:

    let rec memo_fib =
        let hash = Hashtbl.create 20 in
        function
          | 0 | 1 -> 1
          | n -> if Hashtbl.mem hash n
                    then Hashtbl.find hash n
                    else let v = memo_fib (n-1) + memo_fib (n-2) in
                         (Hashtbl.replace hash n v; 
                         v)
    ;;

    memo_fib 30;; (* instantaneous -- all recursive calls are memoized *)

Unfortunately, this is not a very general solution.  I suspect a
general solution, like for example Mark-Jason Dominus's Perl module 
Memoize.pm, requires a stateful environment (i think the Perl version
uses code references).  The problem with an elegant O'Caml solution, i
think, is that the inner recursive calls are part of the definition
environment of the recursive function (i.e. part of the closure), and 
there's no way to change them without writing a new function (and thus
creating a new closure).

Does anyone have any thoughts on this?  Am i missing something obvious?

William
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[Jacek Chrzaszcz]

> 
> Unfortunately, this is not a very general solution.  I suspect a
> general solution, like for example Mark-Jason Dominus's Perl module 
> Memoize.pm, requires a stateful environment (i think the Perl version
> uses code references).  The problem with an elegant O'Caml solution, i
> think, is that the inner recursive calls are part of the definition
> environment of the recursive function (i.e. part of the closure), and 
> there's no way to change them without writing a new function (and thus
> creating a new closure).
> 
> Does anyone have any thoughts on this?  Am i missing something obvious?
> 
> William

If you write it like this, it works:

let memoize f = 
  let hash = Hashtbl.create 20 in
  let rec f' a = 
    try Hashtbl.find hash a 
    with Not_found ->
      let b = f f' a in
	Hashtbl.add hash a b; b
  in
    f';;


let recfib recfib = function
  | 0 | 1 -> 1
  | n -> recfib (n-1) + recfib (n-2);;                                      

let fib = memoize recfib;;


Now fib 30 is instantaneous! The clue is to contruct a new
hash and a new recursive function once for each application of
memoize.

Jacek

PS. In caml you can write anything ;)
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[William Lovas]

On Tue, Jun 18, 2002 at 11:16:13AM +0200, Jacek Chrzaszcz wrote:
> If you write it like this, it works:
> 
> [memoize snipped]
> 
> let recfib recfib = function
>   | 0 | 1 -> 1
>   | n -> recfib (n-1) + recfib (n-2);;                                      
> 
> let fib = memoize recfib;;
> 
> 
> Now fib 30 is instantaneous! The clue is to contruct a new
> hash and a new recursive function once for each application of
> memoize.

Aha, cool.  Thanks!

Of course, the limitation here is that you have to change all the recursive
definitions to the "delayed binding" sort (aside: does this construct have
a name in the theory?), so it's still not completely general.  I don't
suppose there's much that can be done about that, is there?

> PS. In caml you can write anything ;)

Of course!  It's just a matter of what looks nice :)

William
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[Christopher Quinn]

William Lovas wrote:
> Does anyone have any thoughts on this?  Am i missing something obvious?
> 

One problem is the creation of the memoized function.
it has to be:

let rec mack v = memoize (ack mack) v

leaving out the v parameter is not possible and hence invocation of 
memoize is per invocation of mack, hence the hash is recreated empty 
each time.
Putting the hash into the top level solves this but then reclamation 
would need to be dealt with to avoid leakage.

Another point is that ack must be tuple-ized otherwise the memoization 
hash is a map int -> (int -> int),
which means actual results are not being stored.

That said, I do not understand the memoization function itself. Perhaps 
John Prevost could comment on the use of Val|Exn - in particular I 
cannot see how an initial Exn can be stored in the first place as an 
exception can only be caused by the presence of an Exn!

What is the advantage over specifying it this way? :

let stow = Hashtbl.create 20
let memoize f =
   fun x -> try
     Hashtbl.find stow x
   with Not_found ->
     let v = f x in
     Hashtbl.add stow x v;
     v

- chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[Remi VANICAT]

Christopher Quinn <cq@htec.demon.co.uk> writes:

[...]

> That said, I do not understand the memoization function
> itself. Perhaps John Prevost could comment on the use of Val|Exn - in
> particular I cannot see how an initial Exn can be stored in the first
> place as an exception can only be caused by the presence of an Exn!

no, an exception can be caused by the evaluation of the function to
memoize. then the result of evaluating the function (which is the Exn)
will be stored.

By the way, one shouldn't catch the Stack_overflow exception, as it is
not really the result of the evaluation...

>
> What is the advantage over specifying it this way? :
>
> let stow = Hashtbl.create 20
> let memoize f =
>    fun x -> try
>      Hashtbl.find stow x
>    with Not_found ->
>      let v = f x in
>      Hashtbl.add stow x v;
>      v

this memoize function have several problem : 
- it is not fully polymorphic (you have '_a type)
- you cannot apply this function to two different function :

let even' odd' x =
  if x = 0 then true
  else (odd' (x - 1))

let odd' even' x =
  if x = 0 then false 
  else (even' (x - 1))

let rec even x =
  even' odd x
and odd x =
  odd' even x

this work, but 

let rec meven x =
  even' (memoize modd) x
and modd x =
  odd' (memoize meven) x

won't (as they will both use the same hastable)

the only way I see to resolve all those problem is to make:

let new_memoize () =
  let stow = Hashtbl.create 20
  fun f x -> try
     Hashtbl.find stow x
  with Not_found ->
     let v = f x in
     Hashtbl.add stow x v;
     v

each call to new_memoize () will make a new memoize function that
could be apply to one function.



-- 
Rémi Vanicat
vanicat@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[Christopher Quinn]

Remi VANICAT wrote:
> 
> no, an exception can be caused by the evaluation of the function to
> memoize. then the result of evaluating the function (which is the Exn)
> will be stored.

Yes, but assuming you do not intend for the function to be memoized 
itself to raise an exception, there is no opportunity in the code as 
given to create an initial Exn. So there is no chance of memoize raising 
an exception itself.

> this memoize function have several problem : 
> - it is not fully polymorphic (you have '_a type)
> - you cannot apply this function to two different function :
> 
[snip]
> 
> the only way I see to resolve all those problem is to make:
> 
> let new_memoize () =
>   let stow = Hashtbl.create 20
>   fun f x -> try
>      Hashtbl.find stow x
>   with Not_found ->
>      let v = f x in
>      Hashtbl.add stow x v;
>      v
> 
> each call to new_memoize () will make a new memoize function that
> could be apply to one function.
> 

I was, rather, interested in the purpose of Val|Exn in the original. But 
thanks for this improvement!

- chris

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[John Max Skaller]

William Lovas wrote:

>
>    let recfib recfib = function
>      | 0 | 1 -> 1
>      | n -> recfib (n-1) + recfib (n-2);;
>

>
>Does anyone have any thoughts on this?  Am i missing something obvious?
>

let fib = ref (function | _ -> 1);;
fib := function  | 0 | 1 -> 1 | n-> !fib (n-1) + !fib (n-2) ;;
let memo h f x = (if not (Hashtbl.mem h x) then Hashtbl.add h  x (f x); 
Hashtbl.find h x);;
let h = Hashtbl.create 97;;
fib := memo h !fib;;



-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Memoizing (was: static variables...)

[Pierre Weis]

> let fib = ref (function | _ -> 1);;
> fib := function  | 0 | 1 -> 1 | n-> !fib (n-1) + !fib (n-2) ;;
> let memo h f x = (if not (Hashtbl.mem h x) then Hashtbl.add h  x (f x); 
> Hashtbl.find h x);;
> let h = Hashtbl.create 97;;
> fib := memo h !fib;;
>
> John Max Skaller, mailto:skaller@ozemail.com.au

A slightly more functional way of defining a memo function (i.e. with
no ref to define the memoized function):

let memo f =
  let h = Hashtbl.create 11 in
  fun x ->
    try Hashtbl.find h x with
    | Not_found ->
        let r = f x in
        Hashtbl.add h x r;
        r;;

open Lazy;;

let fib =
  let rec f =
    lazy (memo (
    function
    | 0 | 1 -> 1
    | n -> force f (n - 1) + force f (n - 2))) in
  force f;;

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] static variables in a function

[Shannon --jj Behrens]

For any of you that are interested, here's the code
(based on a combination of your comments).  This code
has the following benefits:

1) The calling functions don't need to deal with
passing in a ref [].

2) Multiple "instances" of this function can be used
independently.

3) Only one match clause is needed, so there is no
repeated code (in my case, an exception will be thrown
for EOF).

(* 
 * Return a function that has the interface of a 
 * lexer and can act as a token buffer.
 *)
let get_token_buffer () = 
  let token_list = ref [] in
  let rec get_token token_list () =
    match !token_list with
      head :: tail -> token_list := tail;
      head
    | [] -> token_list := [1; 2; 3]; (* replace me *)
      get_token token_list () in 
  get_token token_list;;

(* Try it out. *)
let token_buffer = get_token_buffer () in
while true do
  print_int (token_buffer ())
done


__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners