Edit detail for SandBoxCachedFunction revision 4 of 10

A generic way to define function that cache their values.

)abbrev domain CACHEDF CachedFunction                                             
++ Author: Ralf Hemmecke                                                          
++ Date Created: 2009                                                             
++ Date Last Updated: Oct 27, 2009                                                
++ Basic Operations:                                                              
++ Related Domains: Table, AssociationList                                        
++ Also See:                                                                      
++ AMS Classifications:
++ Keywords:
++ Examples:
++ References:
++ Description:
++   This domain is a domain of functions with associated cache.
CachedFunction(A: SetCategory, B: SetCategory): Exports == Implementation where
    Exports ==> with
        function: % -> (A -> B)
        cachedFunction: (A -> B) -> %
        apply: (%, A) -> B
        recursiveDefine: (%, f: A -> B) -> %

    Implementation ==> add

        Rep := Record(cache: Table(A, B), fun: A -> B);

        function(x: %): A -> B == x.fun

        cachedFunction(f: A -> B): % == [empty()$Table(A, B), f]

        apply(x: %, a: A): B ==
            c := x.cache
            u: Union(B, "failed") := search(a, c)
            if u case B
               then u :: B
               else
                 f: A -> B := x.fun
                 c.a := f(a)

        recursiveDefine(x: %, f: A -> B): % ==
            x.fun := f;
            x

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/8303643491408128431-25px001.spad using 
      old system compiler.
   CACHEDF abbreviates domain CachedFunction 
   processing macro definition Exports ==> -- the constructor category 
   processing macro definition Implementation ==> -- the constructor capsule 
------------------------------------------------------------------------
   initializing NRLIB CACHEDF for CachedFunction 
   compiling into NRLIB CACHEDF 
   compiling exported function : $ -> A -> B
      CACHEDF;function;$M;1 is replaced by QCDR 
Time: 0.04 SEC.

   compiling exported cachedFunction : A -> B -> $
Time: 0.01 SEC.

   compiling exported apply : ($,A) -> B
Time: 0.01 SEC.

   compiling exported recursiveDefine : ($,A -> B) -> $
Time: 0 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |CachedFunction| REDEFINED

;;;     ***       |CachedFunction| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor CachedFunction
      Time: 0.06 seconds

   finalizing NRLIB CACHEDF 
   Processing CachedFunction for Browser database:
--->-->CachedFunction((function ((Mapping B A) %))): Not documented!!!!
--->-->CachedFunction((cachedFunction (% (Mapping B A)))): Not documented!!!!
--->-->CachedFunction((apply (B % A))): Not documented!!!!
--->-->CachedFunction((recursiveDefine (% % (Mapping B A)))): Not documented!!!!
--------constructor---------
; compiling file "/var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.lsp" (written 29 OCT 2009 09:52:57 AM):
; compiling (/VERSIONCHECK 2)
; compiling (PUT (QUOTE |CACHEDF;function;$M;1|) ...)
; compiling (DEFUN |CACHEDF;function;$M;1| ...)
; compiling (DEFUN |CACHEDF;cachedFunction;M$;2| ...)
; compiling (DEFUN |CACHEDF;apply;$AB;3| ...)
; compiling (DEFUN |CACHEDF;recursiveDefine;$M$;4| ...)
; compiling (DEFUN |CachedFunction| ...)
; compiling (DEFUN |CachedFunction;| ...)
; compiling (MAKEPROP (QUOTE |CachedFunction|) ...)

; /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.fasl written
; compilation finished in 0:00:00.142
------------------------------------------------------------------------
   CachedFunction is now explicitly exposed in frame initial 
   CachedFunction will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF

)set message time on

I := Integer

(1)

Time: 0.06 (OT) = 0.06 sec
f(n:I): I ==1

   Function declaration f : Integer -> Integer has been added to
      workspace.

Time: 0.01 (IN) = 0.01 sec
fib: CachedFunction(I,I) := cachedFunction(f)

Compiling function f with type Integer -> Integer 

 LISP output:
(#<HASH-TABLE :TEST EQUAL :COUNT 0 {1005984391}> #<FUNCTION |*1;f;1;initial|>)

Time: 0.03 (OT) = 0.03 sec
recursiveDefine(fib,(n:I):I+->if n<2 then 1 else fib(n-1) + fib(n-2))

 LISP output:
(#<HASH-TABLE :TEST EQUAL :COUNT 0 {1005984391}> #<FUNCTION
|*1;anonymousFunction;0;initial;internal|>)

Time: 0.02 (IN) + 0.02 (OT) = 0.04 sec
fib 40

(2)

Time: 0.01 (IN) = 0.01 sec
g(n:I): I == if n<2 then 1 else g(n-1)+g(n-2)

   Function declaration g : Integer -> Integer has been added to
      workspace.

Time: 0 sec
g 40

Compiling function g with type Integer -> Integer

(3)

Time: 11.67 (EV) + 0.02 (OT) = 11.69 sec
h: I -> I := function fib

(4)

Time: 0 sec
h 40

(5)

Time: 0 sec

Caching a function with more than one argument

We need to combine more than one domain into a single domain in a universal manner like a cross-product. There are seveal ways to do this in Axiom including List, Record, Product and DirectProduct. For example:

-- combine two domain in one using Record
Pair:=Record(x1:Integer,x2:Integer)

(6)

Time: 0 sec
pair(x:Integer,y:Integer):Pair == [x,y]

   Function declaration pair : (Integer,Integer) -> Record(x1: Integer,
      x2: Integer) has been added to workspace.

Time: 0 sec
--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)

   Function declaration gcd2 : Record(x1: Integer,x2: Integer) ->
      Integer has been added to workspace.

Time: 0 sec
gcd2cached:CachedFunction(Pair,Integer):=new gcd2

   There are 1 exposed and 0 unexposed library operations named new
      having 1 argument(s) but none was determined to be applicable.
      Use HyperDoc Browse, or issue
                               )display op new
      to learn more about the available operations. Perhaps
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named new
      with argument type(s)
                            FunctionCalled(gcd2)

      Perhaps you should use "@" to indicate the required return type,
      or "$" to specify which version of the function you need.
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)

   Function declaration gcdCached : (Integer,Integer) -> Integer has
      been added to workspace.

Time: 0 sec

)set message time on

for i in 1..1000 repeat for j in 1..100 repeat gcd(i,j)

Time: 3.88 (EV) = 3.88 sec
for i in 1..1000 repeat for j in 1..100 repeat gcdCached(i,j)

Compiling function pair with type (Integer,Integer) -> Record(x1: 
      Integer,x2: Integer)

Compiling function gcdCached with type (Integer,Integer) -> Integer 

   Though gcd2cached has declared type (or partial type) CachedFunction
      (Record(x1: Integer,x2: Integer),Integer) it does not have an 
      assigned value. You must give it one before it can be so used.

)set message time off

testhash() ==
  for i in 1..100 repeat for j in 1..100 repeat
    if gcdCached(i,j)~=gcd(i,j) then error "bad hash!"
  "good"

testhash()

Compiling function testhash with type () -> String 

   Though gcd2cached has declared type (or partial type) CachedFunction
      (Record(x1: Integer,x2: Integer),Integer) it does not have an 
      assigned value. You must give it one before it can be so used.

I was rather disappointed with the performance of the cache! So I took a look at the source code for Table and it seems that Table only uses an efficient hashing method if hashable(Key)$Lisp is true, where Key is the first domain of Table(Key,Entry). This is true for Integer and hashable(String)$Lisp but not Record(x1:Integer,x2:Integer) or even List(Integer).

hashable(Integer)$Lisp

(7)

hashable(String)$Lisp

(8)

hashable(Record(x1:Integer,x2:Integer))$Lisp

(9)

hashable(List Integer)$Lisp

(10)

But as far as I can see the implementation of List and Record in Axiom do satisfy the requirements for the use of HashTable?:

  ++   This creates a \spadtype{HashTable} if equal for the Key
  ++   domain is consistent with Lisp EQUAL otherwise an
  ++   \spadtype{AssociationList}

if their component domains do. So I think it would be a good idea to make the hashable function in 'spad.lisp':

  (defun |knownEqualPred| (dom)
    (let ((fun (|compiledLookup| '= '((|Boolean|) <img alt="LatexWiki Image" class="equation" src="images/3644510302787779389-18.0px.png" width="1" height="1"/>) dom)))
      (if fun (get (bpiname (car fun)) '|SPADreplace|)
        nil)))

  (defun |hashable| (dom)
    (memq (|knownEqualPred| dom)
          #-Lucid '(EQ EQL EQUAL)
          #+Lucid '(EQ EQL EQUAL EQUALP)
          ))

a little smarter. This test only seems to check if the compiler was able to optimize equality to a lisp operator. I suppose we could improve the compiler but even failing that, there should be a way to recognize it at this level. I think it's something like having the Canonical property "all the way down".

We can test this for now by using HashTable? explicitly and just assuming that that domain A satisfies the requirement:

)abbrev domain CACHEDF CachedFunction                                             
CachedFunction(A: SetCategory, B: SetCategory): Exports == Implementation where
    Exports ==> with
        function: % -> (A -> B)
        cachedFunction: (A -> B) -> %
        apply: (%, A) -> B
        recursiveDefine: (%, f: A -> B) -> %

    Implementation ==> add

        Rep := Record(cache: HashTable(A, B, "UEQUAL"), fun: A -> B);

        function(x: %): A -> B == x.fun

        cachedFunction(f: A -> B): % == [empty()$HashTable(A, B, "UEQUAL"), f]

        apply(x: %, a: A): B ==
            c := x.cache
            u: Union(B, "failed") := search(a, c)
            if u case B
               then u :: B
               else
                 f: A -> B := x.fun
                 c.a := f(a)

        recursiveDefine(x: %, f: A -> B): % ==
            x.fun := f;
            x

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/6894297888104578709-25px005.spad using 
      old system compiler.
   CACHEDF abbreviates domain CachedFunction 
   processing macro definition Exports ==> -- the constructor category 
   processing macro definition Implementation ==> -- the constructor capsule 
------------------------------------------------------------------------
   initializing NRLIB CACHEDF for CachedFunction 
   compiling into NRLIB CACHEDF 
   compiling exported function : $ -> A -> B
      CACHEDF;function;$M;1 is replaced by QCDR 

;;;     ***       |CACHEDF;function;$M;1| REDEFINED
Time: 0.05 SEC.

   compiling exported cachedFunction : A -> B -> $

;;;     ***       |CACHEDF;cachedFunction;M$;2| REDEFINED
Time: 0.01 SEC.

   compiling exported apply : ($,A) -> B

;;;     ***       |CACHEDF;apply;$AB;3| REDEFINED
Time: 0 SEC.

   compiling exported recursiveDefine : ($,A -> B) -> $

;;;     ***       |CACHEDF;recursiveDefine;$M$;4| REDEFINED
Time: 0.01 SEC.

(time taken in buildFunctor:  0)

;;;     ***       |CachedFunction| REDEFINED

;;;     ***       |CachedFunction| REDEFINED
Time: 0 SEC.

   Cumulative Statistics for Constructor CachedFunction
      Time: 0.07 seconds

   finalizing NRLIB CACHEDF 
   Processing CachedFunction for Browser database:
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((function ((Mapping B A) %))): Not documented!!!!
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((cachedFunction (% (Mapping B A)))): Not documented!!!!
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((apply (B % A))): Not documented!!!!
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((recursiveDefine (% % (Mapping B A)))): Not documented!!!!
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction(constructor): Not documented!!!!
--->/var/zope2/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction(): Missing Description
; compiling file "/var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.lsp" (written 29 OCT 2009 09:53:52 AM):
; compiling (/VERSIONCHECK 2)
; compiling (PUT (QUOTE |CACHEDF;function;$M;1|) ...)
; compiling (DEFUN |CACHEDF;function;$M;1| ...)
; compiling (DEFUN |CACHEDF;cachedFunction;M$;2| ...)
; compiling (DEFUN |CACHEDF;apply;$AB;3| ...)
; compiling (DEFUN |CACHEDF;recursiveDefine;$M$;4| ...)
; compiling (DEFUN |CachedFunction| ...)
; compiling (DEFUN |CachedFunction;| ...)
; compiling (MAKEPROP (QUOTE |CachedFunction|) ...)

; /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.fasl written
; compilation finished in 0:00:00.122
------------------------------------------------------------------------
   CachedFunction is already explicitly exposed in frame initial 
   CachedFunction will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF

Now let's try that again.

-- combine two domain in one
Pair:=Record(x1:Integer,x2:Integer)

(11)

pair(x:Integer,y:Integer):Pair == [x,y]

   Function declaration pair : (Integer,Integer) -> Record(x1: Integer,
      x2: Integer) has been added to workspace.
   Compiled code for pair has been cleared.
   Compiled code for gcdCached has been cleared.
   Compiled code for testhash has been cleared.
   1 old definition(s) deleted for function or rule pair

--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)

   Function declaration gcd2 : Record(x1: Integer,x2: Integer) ->
      Integer has been added to workspace.
   1 old definition(s) deleted for function or rule gcd2

gcd2cached:CachedFunction(Pair,Integer):=new gcd2

   There are 1 exposed and 0 unexposed library operations named new
      having 1 argument(s) but none was determined to be applicable.
      Use HyperDoc Browse, or issue
                               )display op new
      to learn more about the available operations. Perhaps
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named new
      with argument type(s)
                            FunctionCalled(gcd2)

      Perhaps you should use "@" to indicate the required return type,
      or "$" to specify which version of the function you need.
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)

   Function declaration gcdCached : (Integer,Integer) -> Integer has
      been added to workspace.
   1 old definition(s) deleted for function or rule gcdCached

)set message time on

for i in 1..1000 repeat for j in 1..100 repeat gcd(i,j)

Time: 3.68 (EV) = 3.68 sec
for i in 1..1000 repeat for j in 1..100 repeat gcdCached(i,j)

Compiling function pair with type (Integer,Integer) -> Record(x1: 
      Integer,x2: Integer)

Compiling function gcdCached with type (Integer,Integer) -> Integer 

   Though gcd2cached has declared type (or partial type) CachedFunction
      (Record(x1: Integer,x2: Integer),Integer) it does not have an 
      assigned value. You must give it one before it can be so used.

)set message time off

testhash() ==
  for i in 1..100 repeat for j in 1..100 repeat
    if gcdCached(i,j)~=gcd(i,j) then error "bad hash!"
  "good"

   1 old definition(s) deleted for function or rule testhash

testhash()

Compiling function testhash with type () -> String 

   Though gcd2cached has declared type (or partial type) CachedFunction
      (Record(x1: Integer,x2: Integer),Integer) it does not have an 
      assigned value. You must give it one before it can be so used.

)set message time on

)lib CACHEDF

   CachedFunction is already explicitly exposed in frame initial
   CachedFunction will be automatically loaded when needed from
      /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF
fib2: CachedFunction(INT,INT):= cachedFunction (n+->
    if n<2 then 1 else fib2(n-1)+fib2(n-2)
  )

 LISP output:
(#<HASH-TABLE :TEST EQUAL :COUNT 0 {1004B3F511}> #<FUNCTION
|*1;anonymousFunction;1;initial;internal|>)

Time: 0.03 (OT) = 0.03 sec
fib2 40

(12)

Time: 0.01 (OT) = 0.01 sec

Looks like the time difference (if any) is not significant.