Maki (maki.Maki)

Maki is a system for memoizing costly OCaml functions using the disk. It requires the functions to be pure, that is, to always return the same result given that the set of dependencies declared by the function doesn't change.

type 'a or_error = ('a, string) Result.result

type 'a lwt_or_error = 'a or_error Lwt.t

type 'a printer = Format.formatter ‑> 'a ‑> unit

val error : string ‑> _ or_error

val errorf : ('a, Format.formatter, unit, 'b or_error) Pervasives.format4 ‑> 'a

Basic types

type path = string

type program = string

type time = float

type hash = string

type encoded_value = string

module E : sig ... end

Error Handling

Controlling Parallelism

module Limit : sig ... end

module Codec : sig ... end

Codec

Persistent storage

We use a generic interface for persistent storage, in the form of a dictionary string -> string. The default storage just uses one file per pair.

module Storage : sig ... end

Time Utils

module Time : sig ... end

module Lifetime : sig ... end

lifetime for a value on disk

Values Stored on Disk

module File_ref : sig ... end

module Program_ref : sig ... end

module Ref : sig ... end

Reference to On-Disk Value

Hash function

module Hash : sig ... end

Memoized Functions

This is the heart of the library: a wrapper around pure functions from Arg arguments to a Codec-aware type. Such functions are supposed to always return the same value given the same arguments and dependencies (a typical dependency is an external program that might have several version).

The call function is used to actually evaluate a wrapped function, or return its memoized result if the computation was done already.

We need to name functions because, from one execution to another, the results of a function call must be stored on disk. Names are used to map function calls to their result. If two different functions share the same name (even across programs), the results will be unpredictable.

High-Level API

module Fun : sig ... end

val return_ok : 'a ‑> 'a or_error Lwt.t

val return_fail : string ‑> 'a or_error Lwt.t

val mk1 : (name:string ‑> 'a Hash.t ‑> 'ret Codec.t ‑> f:('a ‑> 'ret or_error Lwt.t) as f ‑> 'f) Fun.call_wrap

mk1 ~name h codec ~f behaves like the unary function f : 'a -> 'ret but uses the hash function h to hash arguments, and codec to save/restore values from the cache when f has already been evaluated on a given value.

Parameter name: is used to distinguish calls to f from calls to other functions that have the same signature.

Example: memoizing a recursive function:

let fib =
  let rec fib = lazy Maki.(
      mk1 ~name:"fib" Hash.int Codec.int ~lifetime:Lifetime.one_minute
        ~f:(fun x -> if x <= 1
          then return_ok 1
          else E.(Lazy.force fib (x-1) >>= fun x1 ->
              Lazy.force fib (x-2) >|= fun x2 -> x1+x2))
    ) in
  Lazy.force fib;;

fib 42 ;;
(* returns [Ok 42] *)

val mk2 : (name:string ‑> 'a Hash.t ‑> 'b Hash.t ‑> 'ret Codec.t ‑> f:('a ‑> 'b ‑> 'ret or_error Lwt.t) as f ‑> 'f) Fun.call_wrap

val mk3 : (name:string ‑> 'a Hash.t ‑> 'b Hash.t ‑> 'c Hash.t ‑> 'ret Codec.t ‑> f:('a ‑> 'b ‑> 'c ‑> 'ret or_error Lwt.t) as f ‑> 'f) Fun.call_wrap

val mk4 : (name:string ‑> 'a Hash.t ‑> 'b Hash.t ‑> 'c Hash.t ‑> 'd Hash.t ‑> 'ret Codec.t ‑> f:('a ‑> 'b ‑> 'c ‑> 'd ‑> 'ret or_error Lwt.t) as f ‑> 'f) Fun.call_wrap

val mk5 : (name:string ‑> 'a Hash.t ‑> 'b Hash.t ‑> 'c Hash.t ‑> 'd Hash.t ‑> 'e Hash.t ‑> 'ret Codec.t ‑> f:('a ‑> 'b ‑> 'c ‑> 'd ‑> 'e ‑> 'ret or_error Lwt.t) as f ‑> 'f) Fun.call_wrap

Low-Level API

module Arg : sig ... end

To memoize a function, Maki must be able to hash the function's input arguments. Arguments that hash to the same value are considered identical. We use a cryptographic hash to ensure that the probability of collisions is astronomically low.

val call : ?⁠bypass:bool ‑> ?⁠storage:Storage.t ‑> ?⁠lifetime:Lifetime.t ‑> ?⁠limit:Limit.t ‑> ?⁠tags:string list ‑> name:string ‑> args:Arg.t list ‑> returning:'a Codec.t ‑> (unit ‑> 'a or_error Lwt.t) ‑> 'a or_error Lwt.t

Call the function iff its result has not been cached yet

Parameter bypass: if true, then cache is disabled
Parameter storage: the storage used for caching values (default Storage.get_default ())
Parameter lifetime: how long to keep the cached value (default: `CanDrop)
Parameter limit: if given, call will acquire a handle from limit before calling the (potentially costly) function
Parameter name: the name of the function, should be unique!
Parameter deps: the dependencies (arguments) of the function
Parameter returning: how to encode/decode the result on disk

val call_pure : ?⁠bypass:bool ‑> ?⁠storage:Storage.t ‑> ?⁠lifetime:Lifetime.t ‑> ?⁠limit:Limit.t ‑> ?⁠tags:string list ‑> name:string ‑> args:Arg.t list ‑> returning:'a Codec.t ‑> (unit ‑> 'a Lwt.t) ‑> 'a or_error Lwt.t

module GC_info : sig ... end

module On_disk_record : sig ... end

module GC : sig ... end

Utils

module Util = Maki__.Maki_utils

val last_mtime : path ‑> time or_error

Last modification time of the file

val sha1 : path ‑> string or_error Lwt.t

sha1 f hashes the file f

val sha1_of_string : string ‑> string

hash the given string

val abspath : path ‑> path

Make the path absolute

val shell : ?⁠timeout:float ‑> ?⁠stdin:string ‑> string ‑> (string * string * int) or_error Lwt.t

shell cmd runs the command cmd and returns stdout, sterr, errcode.

Parameter stdin: optional input to the sub-process

val shellf : ?⁠timeout:float ‑> ?⁠stdin:string ‑> ('a, Format.formatter, unit, (string * string * int) or_error Lwt.t) Pervasives.format4 ‑> 'a

Same as shell but with a format string. Careful with escaping!

val read_file : File_ref.t ‑> string or_error Lwt.t

Read the content of the file

val walk : ?⁠filter:(path ‑> bool) ‑> ?⁠recursive:bool ‑> ?⁠which:[ `File | `Dir ] list ‑> path ‑> path list or_error Lwt.t

walk dir traverses the directory and yields its content, by absolute path.

Parameter which: filters on the type of the content
Parameter recursive: if true, walks into subdirectories too
Parameter filter: filters the absolute path of objects and yields only these which satisfy the predicate

Module Maki

Maki: Persistent Incremental Computations