1 (* [memoize (hash, eq, f)] builds a memoizing version of the function [f], 2 using an internal hash table based on the provided hash and equality 3 functions. *) 4 5 (* If [f] has type [a -> b], the types [a] and [b] must be duplicable, 6 because arguments and results will be stored in the internal hash 7 table. *) 8 9 (* The function [f] may have a side effect, represented by [s]. This must be 10 used with caution: it often does not make sense to memoize a function that 11 has a side effect. Furthermore, when it does make sense, one might prefer 12 to hide the side effect before applying [memoize], so [memoize] is applied 13 to a function that does not require a permission. The parameter [s] is 14 useful only when memoizing a function that has an intentionally non-hidden 15 side effect. *) 16 17 val memoize: 18 [a, b, s : perm] 19 duplicable a => duplicable b => 20 (hash: a -> int, eq: (a, a) -> bool, f: (a | s) -> b) -> 21 (a | s) -> b 22 23 (* Now, a memoizing fixpoint combinator. Here, the argument [f] is not a 24 closed function, but an open recursive function, i.e., it is parameterized 25 over [self]. So, [f] should have type [(self: a -> b, x: a) -> y: b]. *) 26 27 (* Actually, we require [f] to have a slightly more general type, which is 28 parametric in an unknown permission [p]. Thus, we tell our client that 29 [self] may have a side effect, and that (of course) we expect the 30 application of [f] to [self] to have the same side effect. Incidentally, 31 note that this type prevents [f] from storing [self] and re-using after 32 [f] has returned! So, we are telling [f], ``you can use [self] now if 33 you wish, but you are not allowed to use it later''. *) 34 35 val fix: 36 [a, b] 37 duplicable a => duplicable b => 38 ( 39 hash: a -> int, 40 eq: (a, a) -> bool, 41 f: [p : perm] ((a | p) -> b, a | p) -> b 42 ) -> 43 a -> b 44