Next: , Previous: , Up: Top   [Index]

8 Memoizing

In prolog there is a notion of memoizing datastructures, guile-log elaborates on these datastructures somwhat and also define structures that can work as a sledgehammer in order to handle recursive datastructures, also memoizing somthing that is wrong means that the memoizer in the most general situation needs to backtrack, there is possibility however to cut corners in e.g. algorithms where there is no state storage or where there is no backtracking. The interface is as follows, memo, memo-rec, tabling can all be use as functors in guile log prolog with he help of functorize wrapper.

G.L. (memo fkn arg ...) This will assume that fkn only have one result and uses simplified logic to memoize the result and when similar args is available then it will use the old value.

G.L. (memo-rec fkn arg ...) The same as above but in stead the function can call itself this means that

(<define> (ff x) (f x))
(<define> (f z) (memo-rec ff x))

Will not diverge and yield a solution.

G.L. (tabling fkn arg ...), as above but it can handle many solutions for the same arguments at the beginning of the funciton, this function also behaves well for recursive definitions and will cut the tree search and yield mostly recursive or rational datastructures. This function is not perfect and the same answer might be given multiple times, there is no garantee

Scm (rec f guard action) This creates a guile log goal funciton that modifies f, f is taking the same vars as the lambda, and make sure to call action if it sees the an old term that have already been processed action takes a list of all incoming args. The guard is of the following signature, G.L. (guard inp s), with inp the list of vars and s the state data that flows with the guile-log program. Rec is a pretty expensive function that behaves well under backtracking and state store and restore. Use this ideom and it’s sibling ideoms as a prolog functor as

/* prolog code comes here */

f(X) :- ....

/* end prolog */

Scm (rec-once f guard action) An optimized verison of rec for cases when you only take one value of f

Scm (rec-00 f guard action) Does nothing fancy and is therefore fast, assume that there is no backtracking in f and that it is atomic in the sense that no state store restore is done inside it.

rec-lam, rec-lam-once, rec-lam-00 The same as the three above but the resulting goal has the signature,

G.L. (*-lam-* action arg ...), with action beeing executed just like the overall action in the mother functor.

G.L. (rec-action action x) Will execute action in case a term show up a second time in scanning the datastructure x.

G.L. (rec-action00 action x) Will execute action in case a term show up a second time in scanning the datastructure x. This assume no backtracking in action.

G.L. (rec= X Y) , a recursive safe unify procedure. G.L. (rec== X Y), a recursive safe eqvivalence procedure.

(recursive f arg ...), this functor can be used to modify f so that it will do all of it’s work using recursive safe unifyeres etc. This can be used as a functor modifyier in prolog.

Next: , Previous: , Up: Top   [Index]