Features

Memoization

What is memoization?

For every new argument we calculate the return value and then redefine the function itself to speed up the next call with the same argument. We could also use other data structures to store the results.

So the function is "self-modifiying" or "learning", we could also name it "caching".

vlisp/vill doesn't store the function as list anymore so we have to to store the actual function definition in a special symbol, returned by (std-memoizated-funcname).

The term and usage of memoization is widely used in Common Lisp, but mostly implemented with local hash-tables, not self-modifying functions.

So far we only use simple memoized functions with no argument. There the return value is always the same, therefore we cache it in a global value and we have only have to decide if this global was initialized before.

We define two types of memoized functions:

At first (STD-%DEFMEMOIZE-NOARG-BOOL) for only boolean predicates which store the result in a variable containing either 0 for false, 1 for true or nil for not initialized.

Second, (STD-%DEFMEMOIZE-NOARG-VAL) for functions returning any value. Therefore nil may not be used to detect not-initialized functions, the value will be recalculated for every nil return value.

STD-%DEFMEMOIZE-NOARG-BOOL - Simple Predicates without Arguments

Cache the first return value, only works with predicates

1 is true, 0 is false

The actual code looks awful as long as no backquote/comma mechanism is supported

=>
`(defun ,funcname ,args
   (if (boundp ',memoized-var)
     (= ,memoized-var 1)
     (= 1 (setq ,memoized-var
          (if (progn ,@body) 1 0))))

STD-%DEFMEMOIZE-NOARG-VAL - Memoizing any value

Version to store any value (not only 0/1)

=>
`(defun ,funcname ,args
   (if (boundp ',memoized-var)
     ,memoized-var
     (setq ,memoized-var (progn ,@body))))

Defined and used in STDINIT. The actual stdlib code is not expanded at runtime by using the memoization functions. Instead the function definitions were generated automatically by applying the memoization functions. They are left in the libary to help you optimizing your own cached functions.

General memoizing functions accepting functions with arguments are left to extensions.