login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit

Edit detail for SandBoxCachedFunction revision 9 of 10

1 2 3 4 5 6 7 8 9 10
Editor: Bill Page
Time: 2009/10/29 10:46:48 GMT-7
Note: Caching a function with more than one argument

changed:
-    (let ((fun (|compiledLookup| '= '((|Boolean|) $ $) dom)))
    (let ((fun (|compiledLookup| '= '((|Boolean|) \$ \$) dom)))

added:
\begin{axiom}
)clear completely
\end{axiom}


added:


A generic way to define function that cache their values.

spad
)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
spad
   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 10:44:51 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.071 ------------------------------------------------------------------------ CachedFunction is now explicitly exposed in frame initial CachedFunction will be automatically loaded when needed from /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF

axiom
)set message time on
I := Integer
LatexWiki Image(1)
Type: Domain
axiom
Time: 0.06 (OT) = 0.06 sec
f(n:I): I ==1
Function declaration f : Integer -> Integer has been added to workspace.
Type: Void
axiom
Time: 0.01 (IN) = 0.01 sec
fib: CachedFunction(I,I) := cachedFunction(f)
axiom
Compiling function f with type Integer -> Integer 
LISP output: (#<HASH-TABLE :TEST EQUAL :COUNT 0 {1005685391}> #<FUNCTION |*1;f;1;initial|>)
Type: CachedFunction?(Integer,Integer)
axiom
Time: 0.01 (IN) + 0.01 (EV) + 0.01 (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 {1005685391}> #<FUNCTION |*1;anonymousFunction;0;initial;internal|>)
Type: CachedFunction?(Integer,Integer)
axiom
Time: 0.02 (IN) + 0.01 (OT) = 0.03 sec
fib 40
LatexWiki Image(2)
Type: PositiveInteger?
axiom
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.
Type: Void
axiom
Time: 0 sec
g 40
axiom
Compiling function g with type Integer -> Integer
LatexWiki Image(3)
Type: PositiveInteger?
axiom
Time: 11.58 (EV) + 0.02 (OT) = 11.60 sec
h: I -> I := function fib
LatexWiki Image(4)
Type: (Integer -> Integer)
axiom
Time: 0 sec
h 40
LatexWiki Image(5)
Type: PositiveInteger?
axiom
Time: 0 sec
axiom
)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:

axiom
-- combine two domain in one using Record
Pair:=Record(x1:Integer,x2:Integer)
LatexWiki Image(6)
Type: Domain
axiom
pair(x:Integer,y:Integer):Pair == [x,y]
Function declaration pair : (Integer,Integer) -> Record(x1: Integer, x2: Integer) has been added to workspace.
Type: Void
axiom
--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)
Function declaration gcd2 : Record(x1: Integer,x2: Integer) -> Integer has been added to workspace.
Type: Void
axiom
gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2
axiom
Compiling function gcd2 with type Record(x1: Integer,x2: Integer)
       -> Integer 
LISP output: (() #<FUNCTION |*1;gcd2;1;initial|>)
Type: CachedFunction?(Record(x1: Integer,x2: Integer),Integer)
axiom
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
Function declaration gcdCached : (Integer,Integer) -> Integer has been added to workspace.
Type: Void

axiom
)set message time on
for i in 1..100 repeat for j in 1..100 repeat gcd(i,j)
Type: Void
axiom
Time: 0.44 (EV) = 0.44 sec
for i in 1..100 repeat for j in 1..100 repeat gcdCached(i,j)
axiom
Compiling function pair with type (Integer,Integer) -> Record(x1: 
      Integer,x2: Integer)
axiom
Compiling function gcdCached with type (Integer,Integer) -> Integer
Type: Void
axiom
Time: 6.53 (EV) + 0.02 (OT) = 6.55 sec
axiom
)set message time off

axiom
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"
Type: Void
axiom
testhash()
axiom
Compiling function testhash with type () -> String
LatexWiki Image(7)
Type: String

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).

axiom
hashable(Integer)$Lisp
LatexWiki Image(8)
Type: SExpression?
axiom
hashable(String)$Lisp
LatexWiki Image(9)
Type: SExpression?
axiom
hashable(Record(x1:Integer,x2:Integer))$Lisp
Compiled code for gcd2 has been cleared.
LatexWiki Image(10)
Type: SExpression?
axiom
hashable(List Integer)$Lisp
LatexWiki Image(11)
Type: SExpression?

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|) $ $) 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".

axiom
)clear completely
All user variables and function definitions have been cleared. All )browse facility databases have been cleared. Internally cached functions and constructors have been cleared. )clear completely is finished.

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

spad
)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
spad
   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/6894297888104578709-25px008.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.01 SEC.
compiling exported recursiveDefine : ($,A -> B) -> $
;;; *** |CACHEDF;recursiveDefine;$M$;4| REDEFINED Time: 0 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 10:45:54 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 now 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.

axiom
-- combine two domain in one
Pair:=Record(x1:Integer,x2:Integer)
LatexWiki Image(12)
Type: Domain
axiom
pair(x:Integer,y:Integer):Pair == [x,y]
Function declaration pair : (Integer,Integer) -> Record(x1: Integer, x2: Integer) has been added to workspace.
Type: Void
axiom
--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)
Function declaration gcd2 : Record(x1: Integer,x2: Integer) -> Integer has been added to workspace.
Type: Void
axiom
gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2
axiom
Compiling function gcd2 with type Record(x1: Integer,x2: Integer)
       -> Integer 
LISP output: (#<HASH-TABLE :TEST EQUAL :COUNT 0 {1004FEFBF1}> #<FUNCTION |*1;gcd2;1;initial|>)
Type: CachedFunction?(Record(x1: Integer,x2: Integer),Integer)
axiom
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
Function declaration gcdCached : (Integer,Integer) -> Integer has been added to workspace.
Type: Void

axiom
)set message time on
for i in 1..100 repeat for j in 1..100 repeat gcd(i,j)
Type: Void
axiom
Time: 0.52 (EV) = 0.52 sec
for i in 1..100 repeat for j in 1..100 repeat gcdCached(i,j)
axiom
Compiling function pair with type (Integer,Integer) -> Record(x1: 
      Integer,x2: Integer)
axiom
Compiling function gcdCached with type (Integer,Integer) -> Integer
Type: Void
axiom
Time: 0.02 (IN) + 0.27 (EV) = 0.29 sec
axiom
)set message time off

axiom
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"
Type: Void
axiom
testhash()
axiom
Compiling function testhash with type () -> String
LatexWiki Image(13)
Type: String

perhaps recursiveDefine not necessary --Bill Page, Wed, 28 Oct 2009 22:06:18 -0700 reply
axiom
)set message time on
axiom
)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 {100553C941}> #<FUNCTION |*1;anonymousFunction;1;initial;internal|>)
Type: CachedFunction?(Integer,Integer)
axiom
Time: 0.01 (IN) + 0.02 (OT) = 0.03 sec
fib2 40
LatexWiki Image(14)
Type: PositiveInteger?
axiom
Time: 0.01 (IN) = 0.01 sec

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