Edit detail for SandBoxCachedFunction revision 8 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.06 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.01 SEC.

   Cumulative Statistics for Constructor CachedFunction
      Time: 0.09 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 10:28:10 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.141
------------------------------------------------------------------------
   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.01 (IN) + 0.08 (OT) = 0.09 sec
f(n:I): I ==1

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

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

Compiling function f with type Integer -> Integer 

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

Time: 0.01 (EV) + 0.02 (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 {10058B5391}> #<FUNCTION
|*1;anonymousFunction;0;initial;internal|>)

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

(2)

Time: 0.01 (IN) + 0.01 (OT) = 0.02 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: 13.63 (EV) + 0.01 (OT) = 13.64 sec
h: I -> I := function fib

(4)

Time: 0 sec
h 40

(5)

Time: 0 sec

)set message time off

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)

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

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

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

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

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

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

 LISP output:
(() #<FUNCTION |*1;gcd2;1;initial|>)

gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)

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

)set message time on

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

Time: 0.43 (EV) = 0.43 sec
for i in 1..100 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

Time: 0.01 (IN) + 6.57 (EV) + 0.01 (OT) = 6.59 sec

)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

(7)

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

(8)

hashable(String)$Lisp

(9)

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

   Compiled code for gcd2 has been cleared.

(10)

hashable(List Integer)$Lisp

(11)

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-25px007.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.04 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 SEC.

(time taken in buildFunctor:  10)

;;;     ***       |CachedFunction| REDEFINED

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

   Cumulative Statistics for Constructor CachedFunction
      Time: 0.06 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 10:30:00 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.051
------------------------------------------------------------------------
   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)

(12)

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):=cachedFunction gcd2

   There are 30 exposed and 3 unexposed library operations named elt
      having 2 argument(s) but none was determined to be applicable.
      Use HyperDoc Browse, or issue
                               )display op elt
      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 elt
      with argument type(s)
                       Record(x1: Integer,x2: Integer)
                                   Integer

      Perhaps you should use "@" to indicate the required return type,
      or "$" to specify which version of the function you need.
   FriCAS will attempt to step through and interpret the code.

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

 LISP output:
(#<HASH-TABLE :TEST EQUAL :COUNT 0 {100572D591}> #<FUNCTION #:G11004>)

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..100 repeat for j in 1..100 repeat gcd(i,j)

Time: 0.01 (IN) + 0.53 (EV) = 0.54 sec
for i in 1..100 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 

   x1 is declared as being in Integer but has not been given a value.

)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 

   x1 is declared as being in Integer but has not been given a value.

)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 {1005545A21}> #<FUNCTION
|*1;anonymousFunction;1;initial;internal|>)

Time: 0.01 (EV) + 0.01 (OT) = 0.02 sec
fib2 40

(13)

Time: 0 sec

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