help links subscribe changes refresh edit

	SandBox
SandBoxCS224 ←	↑	→ SandBoxCategories

SandBoxCachedFunction

Edit detail for SandBoxCachedFunction revision 6 of 10

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

added:


changed:
-'Integer' and 'hashable(String)$Lisp' but not
-'Record(x1:Integer,x2:Integer)' or even 'List(Integer)'.
'Integer' and 'String' but not 'Record(x1:Integer,x2:Integer)'
or even 'List(Integer)'.

changed:
-  ++   This creates a \spadtype{HashTable} if equal for the Key
  ++   This creates a 'HashTable' if equal for the Key

changed:
-  ++   \spadtype{AssociationList}
  ++   'AssociationList'

A generic way to define function that cache their values.

fricas

(1) -> <spad>

fricas

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

fricas

Compiling FriCAS source code from file 
      /var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad
      using old system compiler.
   CACHEDF abbreviates domain CachedFunction 
------------------------------------------------------------------------
   initializing NRLIB CACHEDF for CachedFunction 
   compiling into NRLIB CACHEDF 
   compiling exported function : % -> A -> B
      CACHEDF;function;%M;1 is replaced by QCDR 
Time: 0 SEC.

   compiling exported cachedFunction : A -> B -> %
Time: 0 SEC.

   compiling exported apply : (%,A) -> B
Time: 0 SEC.

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

(time taken in buildFunctor:  3040)
Time: 0 SEC.

   Cumulative Statistics for Constructor CachedFunction
      Time: 0 seconds

   finalizing NRLIB CACHEDF 
   Processing CachedFunction for Browser database:
--------constructor---------
--->-->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!!!!
; compiling file "/var/aw/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.lsp" (written 16 SEP 2026 04:28:30 PM):

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

fricas

)set message time on

I := Integer

$\label{eq1}\hbox{\axiomType{Integer}\ }$

(1)

Type: Type

fricas

Time: 0 sec
f(n:I): I ==1

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

Type: Void

fricas

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

fricas

Compiling function f with type Integer -> Integer 

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

Type: CachedFunction?(Integer,Integer)

fricas

Time: 0 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 {10021CABB3}> #<FUNCTION |*1;anonymousFunction;0;initial;internal|>)

Type: CachedFunction?(Integer,Integer)

fricas

Time: 0 sec
fib 40

$\label{eq2}165580141$

(2)

Type: PositiveInteger?

fricas

Time: 0 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

fricas

Time: 0 sec
g 40

fricas

Compiling function g with type Integer -> Integer

$\label{eq3}165580141$

(3)

Type: PositiveInteger?

fricas

Time: 1.59 (EV) = 1.59 sec
h: I -> I := function fib

$\label{eq4}\mbox{theMap (...)}$

(4)

Type: (Integer -> Integer)

fricas

Time: 0 sec
h 40

$\label{eq5}165580141$

(5)

Type: PositiveInteger?

fricas

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:

fricas

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

$\label{eq6}\hbox{\axiomType{Record}\ } \left({{x 1 : \hbox{\axiomType{Integer}\ }}, \:{x 2 : \hbox{\axiomType{Integer}\ }}}\right)$

(6)

Type: Type

fricas

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.

Type: Void

fricas

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.

Type: Void

fricas

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

fricas

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)

fricas

Time: 0 sec
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)

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

Type: Void

fricas

Time: 0 sec

fricas

)set message time on

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

Type: Void

fricas

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

fricas

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

fricas

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

Type: Void

fricas

Time: 153.07 (EV) = 153.08 sec

fricas

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

Type: Void

fricas

testhash()

fricas

Compiling function testhash with type () -> String

$\label{eq7}\verb#"good"#$

(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 String but not Record(x1:Integer,x2:Integer) or even List(Integer).

fricas

hashable(Integer)$Lisp

$\label{eq8}\left(\hbox{\axiomType{EQL}\ } \ \hbox{\axiomType{EQUAL}\ } \right)$

(8)

Type: SExpression?

fricas

hashable(String)$Lisp

$\label{eq9}\left(\hbox{\axiomType{EQUAL}\ } \right)$

(9)

Type: SExpression?

fricas

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

   Compiled code for gcd2 has been cleared.

$\label{eq10}\left(\right)$

(10)

Type: SExpression?

fricas

hashable(List Integer)$Lisp

$\label{eq11}\left(\right)$

(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 'HashTable' if equal for the Key
  ++   domain is consistent with Lisp EQUAL otherwise an
  ++   '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=" " title=" " class="equation" src="images/3644510302787779389-16.0px.png" align="bottom" Style="vertical-align:text-bottom" width="1" height="2"/>) 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:

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/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/6894297888104578709-25px005.spad
      using old system compiler.
   CACHEDF abbreviates domain CachedFunction 
------------------------------------------------------------------------
   initializing NRLIB CACHEDF for CachedFunction 
   compiling into NRLIB CACHEDF 
Local variable Rep type redefined: (Join (SetCategory) (CATEGORY domain (SIGNATURE construct ((Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) (HashTable A B UEQUAL) (Mapping B A))) (SIGNATURE ~= ((Boolean) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))))) (SIGNATURE coerce ((OutputForm) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))))) (SIGNATURE elt ((HashTable A B UEQUAL) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) cache)) (SIGNATURE elt ((Mapping B A) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) fun)) (SIGNATURE setelt! ((HashTable A B UEQUAL) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) cache (HashTable A B UEQUAL))) (SIGNATURE setelt! ((Mapping B A) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) fun (Mapping B A))) (SIGNATURE copy ((Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))) (Record (: cache (HashTable A B UEQUAL)) (: fun (Mapping B A))))))) to (Join (SetCategory) (CATEGORY domain (SIGNATURE construct ((Record (: cache (Table A B)) (: fun (Mapping B A))) (Table A B) (Mapping B A))) (SIGNATURE ~= ((Boolean) (Record (: cache (Table A B)) (: fun (Mapping B A))) (Record (: cache (Table A B)) (: fun (Mapping B A))))) (SIGNATURE coerce ((OutputForm) (Record (: cache (Table A B)) (: fun (Mapping B A))))) (SIGNATURE elt ((Table A B) (Record (: cache (Table A B)) (: fun (Mapping B A))) cache)) (SIGNATURE elt ((Mapping B A) (Record (: cache (Table A B)) (: fun (Mapping B A))) fun)) (SIGNATURE setelt! ((Table A B) (Record (: cache (Table A B)) (: fun (Mapping B A))) cache (Table A B))) (SIGNATURE setelt! ((Mapping B A) (Record (: cache (Table A B)) (: fun (Mapping B A))) fun (Mapping B A))) (SIGNATURE copy ((Record (: cache (Table A B)) (: fun (Mapping B A))) (Record (: cache (Table A B)) (: fun (Mapping B A)))))))
   compiling exported function : % -> A -> B
      CACHEDF;function;%M;1 is replaced by QCDR 

;;;     ***       |CACHEDF;function;%M;1| REDEFINED
Time: 0 SEC.

   compiling exported cachedFunction : A -> B -> %

;;;     ***       |CACHEDF;cachedFunction;M%;2| REDEFINED
Time: 0 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:  0)

;;;     ***       |CachedFunction| REDEFINED

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

   Cumulative Statistics for Constructor CachedFunction
      Time: 0 seconds

   finalizing NRLIB CACHEDF 
   Processing CachedFunction for Browser database:
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction(constructor): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((function ((Mapping B A) %))): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((cachedFunction (% (Mapping B A)))): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((apply (B % A))): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction((recursiveDefine (% % (Mapping B A)))): Not documented!!!!
--->/var/lib/zope2.10/instance/axiom-wiki/var/LatexWiki/8303643491408128431-25px001.spad-->CachedFunction(): Missing Description
; compiling file "/var/aw/var/LatexWiki/CACHEDF.NRLIB/CACHEDF.lsp" (written 16 SEP 2026 04:32:07 PM):

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

Now let's try that again.

fricas

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

$\label{eq12}\hbox{\axiomType{Record}\ } \left({{x 1 : \hbox{\axiomType{Integer}\ }}, \:{x 2 : \hbox{\axiomType{Integer}\ }}}\right)$

(12)

Type: Type

fricas

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

Type: Void

fricas

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

Type: Void

fricas

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

   There are 29 exposed and 5 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.

fricas

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

   >> System error:
   bad arg to MAKE_HASHTABLE

perhaps recursiveDefine not necessary --Bill Page, Wed, 28 Oct 2009 22:06:18 -0700 reply

fricas

)set message time on

fricas

)lib CACHEDF

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

   >> System error:
   bad arg to MAKE_HASHTABLE

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