Macro memo

macro_rules! memo {
    ( [ $nmop:expr ] ? $fun:expr ; $( $lab:ident :$arg:expr ),* ) => { ... };
    ( [ $nmop:expr ] ? $fun:expr ; $( $lab:ident :$arg:expr ),* ;; $( $lab2:ident : $arg2:expr ),* ) => { ... };
    ( $nm:expr =>> $fun:expr , $( $lab:ident : $arg:expr ),* ) => { ... };
    ( $nm:expr =>> $fun:expr , $( $lab1:ident : $arg1:expr ),* ;; $( $lab2:ident : $arg2:expr ),* ) => { ... };
}

Wrappers for creating and forcing thunks (engine::thunk and engine::force).

Memoization

Memoization provides a mechanism for caching the results of subcomputations; it is a crtical feature of Adapton’s approach to incremental computation.

In Adapton, each memoization point has three ingredients:

• A function expression (of type Fn)

• Zero or more arguments. Each argument type must have an implementation for the traits Eq + Clone + Hash + Debug. The traits Eq and Clone are both critical to Adapton’s caching and change propagation engine. The trait Hash is required when Adapton’s naming strategy is structural (e.g., where function names are based on the hashes of their arguments). The trait Debug is useful for debugging, and reflection.

• An optional name, which identifies the function call for reuse later.

  • When this optional name is None, the memoization point may be treated in one of two ways: either as just an ordinary, uncached function call, or as a cached function call that is identified structurally, by its function pointer and arguments. Adapton permits structural subcomputations via the engine’s structural function.

  • When this is Some(name), the memoization point uses name to identify the work performed by the function call, and its result. Critically, in future incremental runs, it is possible for name to associate with different functions and/or argument values.

Optional name version

The following form is preferred:

memo!( [ optional_name ]? fnexp ; lab1 : arg1, ..., labk : argk )

It accepts an optional name, of type Option<Name>, and an arbitrary function expression fnexp (closure or function pointer). Like the other forms, it requires that the programmer label each argument.

Example 1

Optional name:

// Choose an optional name:
let opnm : Option<Name> = Some(name_unit());

let (t,z) : (Art<usize>, usize) = 
  memo!([opnm]?
    |x:usize,y:usize|{ if x > y { x } else { y }};
     x:10,   y:20   );

assert_eq!(z, 20);
assert_eq!(force(&t), 20);

Example 2

Function pointers as arguments:

fn max(x:usize,y:usize) -> bool { 
  if x > y { true } else { false } 
};

let (t,z) : (Art<usize>, usize) = 
  memo!([Some(name_unit())]?
    |x:usize,y:usize,choose:fn(usize,usize)->bool|{ 
       if choose(x,y) { x } else { y }
    }; x:10, y:20, f:max );

assert_eq!(z, 20);
assert_eq!(force(&t), 20);

Spurious arguments

Sometimes, we need to pass arguments that do not admit the traits required by Adapton thunks Eq + Hash + Debug + Clone.

For instance, suppose that we want to pass Fns around, which are not Debug, Eq or Hash. Though generally unsound, we can use the ;; syntax below to append arguments to thunks that do not admit these traits. For soundness, it is critical that the name and/or other arguments (before the ;;) functionally determine the arguments that follow the ;;, which are stored and never updated, nor tested for changes.

let (t,z) : (Art<usize>, usize) = memo!(
  [Some(name_unit())]?
    |x:usize,y:usize,
      choose:Rc<Fn(usize,usize)->bool>|{ 
        if choose(x,y) { x } else { y }
    };
    x:10, y:20 ;; 
    f:Rc::new(|x,y| if x > y { true } else { false })
  );

assert_eq!(z, 20);
assert_eq!(get!(t), 20);