login  home  contents  what's new  discussion  bug reports     help  links  subscribe  changes  refresh  edit
SandBox
SandBoxCS224  ← ↑ →  SandBoxCategories

SandBoxCachedFunction
  
last edited 15 years ago by Bill Page

Edit detail for SandBoxCachedFunction revision 7 of 10
1 2 3 4 5 6 7 8 9 10
Editor: Bill Page
Time: 2009/10/29 10:21:17 GMT-7
Note: Caching a function with more than one argument 
changed:
-\end{axiom}
)set message time off
\end{axiom}

removed:
-

added:
\end{axiom}
\begin{axiom}

added:
\end{axiom}
\begin{axiom}

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

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

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

added:
\end{axiom}
\begin{axiom}

added:
\end{axiom}
\begin{axiom}


A generic way to define function that cache their values.


\begin{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
\end{spad}




\begin{axiom}
)set message time on
I := Integer
f(n:I): I ==1
fib: CachedFunction(I,I) := cachedFunction(f)
recursiveDefine(fib,(n:I):I+->if n<2 then 1 else fib(n-1) + fib(n-2))
fib 40
g(n:I): I == if n<2 then 1 else g(n-1)+g(n-2)
g 40
h: I -> I := function fib
h 40
)set message time off
\end{axiom}


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:
\begin{axiom}
-- combine two domain in one using Record
Pair:=Record(x1:Integer,x2:Integer)
pair(x:Integer,y:Integer):Pair == [x,y]
--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)
gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
\end{axiom}
\begin{axiom}
)set message time on
for i in 1..1000 repeat for j in 1..100 repeat gcd(i,j)
for i in 1..1000 repeat for j in 1..100 repeat gcdCached(i,j)
)set message time off
\end{axiom}
\begin{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"
testhash()
\end{axiom}
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).
\begin{axiom}
hashable(Integer)$Lisp
hashable(String)$Lisp
hashable(Record(x1:Integer,x2:Integer))$Lisp
hashable(List Integer)$Lisp
\end{axiom}
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".


We can test this for now by using HashTable? explicitly and just
assuming that that domain A satisfies the requirement:
\begin{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
\end{spad}




Now let's try that again.
\begin{axiom}
-- combine two domain in one
Pair:=Record(x1:Integer,x2:Integer)
pair(x:Integer,y:Integer):Pair == [x,y]?
--
gcd2(arg:Pair):Integer == gcd(arg.x1,arg.x2)
gcd2cached:CachedFunction?(Pair,Integer):=cachedFunction gcd2
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
\end{axiom}
\begin{axiom}
)set message time on
for i in 1..1000 repeat for j in 1..100 repeat gcd(i,j)
for i in 1..1000 repeat for j in 1..100 repeat gcdCached(i,j)
)set message time off
\end{axiom}
\begin{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"
testhash()
\end{axiom}






perhaps recursiveDefine not necessary --Bill Page,  Wed, 28 Oct 2009 22:06:18 -0700 reply
\begin{axiom}
)set message time on
)lib CACHEDF
fib2: CachedFunction?(INT,INT):= cachedFunction (n+->
    if n<2 then 1 else fib2(n-1)+fib2(n-2)
  )
fib2 40
\end{axiom}
Looks like the time difference (if any) is not significant.



    Some or all expressions may not have rendered properly,
    because Axiom returned the following error:
Error: export AXIOM=/usr/local/lib/fricas/target/x86_64-unknown-linux; export ALDORROOT=/usr/local/aldor/linux/1.1.0; export PATH=$ALDORROOT/bin:$PATH; export HOME=/var/zope2/var/LatexWiki; ulimit -t 240; $AXIOM/bin/AXIOMsys < /var/zope2/var/LatexWiki/1139478978446583876-25px.axm


Checking for foreign routines
AXIOM="/usr/local/lib/fricas/target/x86_64-unknown-linux"
spad-lib="/usr/local/lib/fricas/target/x86_64-unknown-linux/lib/libspad.so"
foreign routines found
openServer result -2
                 FriCAS (AXIOM fork) Computer Algebra System 
                         Version: FriCAS 2009-10-26
              Timestamp: Tuesday October 27, 2009 at 17:02:14 
-----------------------------------------------------------------------------
   Issue )copyright to view copyright notices.
   Issue )summary for a summary of useful system commands.
   Issue )quit to leave FriCAS and return to shell.
-----------------------------------------------------------------------------


(1) -> (1) -> (1) -> (1) -> (1) -> <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:15:34 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.070
------------------------------------------------------------------------
   CachedFunction is now explicitly exposed in frame initial 
   CachedFunction will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/CACHEDF.NRLIB/CACHEDF


(1) -> )set message time on


I := Integer


$$
Integer 
\leqno(1)
$$
                                                                 Type: Domain
                                                   Time: 0.06 (OT) = 0.06 sec
f(n:I): I ==1


   Function declaration f : Integer -> Integer has been added to 
      workspace.
                                                                   Type: Void
                                                                  Time: 0 sec
fib: CachedFunction(I,I) := cachedFunction(f)


   Compiling function f with type Integer -> Integer 


 LISP output:
(#<HASH-TABLE :TEST EQUAL :COUNT 0 {1005C30391}> #<FUNCTION |*1;f;1;initial|>)
                                        Type: CachedFunction(Integer,Integer)
                           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 {1005C30391}> #<FUNCTION |*1;anonymousFunction;0;initial;internal|>)
                                        Type: CachedFunction(Integer,Integer)
                                       Time: 0.02 (IN) + 0.01 (OT) = 0.03 sec
fib 40




$$
165580141 
\leqno(5)
$$
                                                        Type: PositiveInteger
                                                   Time: 0.01 (EV) = 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.
                                                                   Type: Void
                                                                  Time: 0 sec
g 40


   Compiling function g with type Integer -> Integer 




$$
165580141 
\leqno(7)
$$
                                                        Type: PositiveInteger
                                     Time: 11.66 (EV) + 0.01 (OT) = 11.67 sec
h: I -> I := function fib




$$
\mbox{theMap(...)} 
\leqno(8)
$$
                                                   Type: (Integer -> Integer)
                                                                  Time: 0 sec
h 40




$$
165580141 
\leqno(9)
$$
                                                        Type: PositiveInteger
                                                                  Time: 0 sec
)set message time off






(10) ->


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




$$
\mbox{\rm Record(x1: Integer,x2: Integer)} 
\leqno(10)
$$
                                                                 Type: Domain
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
--
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
gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2


   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)
gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
   Function declaration gcdCached : (Integer,Integer) -> Integer has 
      been added to workspace.
                                                                   Type: Void
(15) -> )set message time on






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


                                                                   Type: Void
                                                   Time: 3.86 (EV) = 3.86 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
Some or all expressions may not have rendered properly, because Latex returned the following error:
This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6)
 \write18 enabled.
 %&-line parsing enabled.
entering extended mode
(./549056191196321642-18.0px.tex
LaTeX2e <2005/12/01>
Babel <v3.8h> and hyphenation patterns for english, usenglishmax, dumylang, noh
yphenation, arabic, farsi, croatian, ukrainian, russian, bulgarian, czech, slov
ak, danish, dutch, finnish, basque, french, german, ngerman, ibycus, greek, mon
ogreek, ancientgreek, hungarian, italian, latin, mongolian, norsk, icelandic, i
nterlingua, turkish, coptic, romanian, welsh, serbian, slovenian, estonian, esp
eranto, uppersorbian, indonesian, polish, portuguese, spanish, catalan, galicia
n, swedish, ukenglish, pinyin, loaded.
(/usr/share/texmf-texlive/tex/latex/base/article.cls
Document Class: article 2005/09/16 v1.4f Standard LaTeX document class
(/usr/share/texmf-texlive/tex/latex/base/size12.clo))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty
For additional information on amsmath, use the `? option.
(/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty
(/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty))
(/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty)
(/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty))
(/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty)
(/usr/share/texmf-texlive/tex/latex/amsfonts/amssymb.sty)
(/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty)
(/usr/share/texmf-texlive/tex/latex/setspace/setspace.sty
Package: `setspace 6.7 <2000/12/01>
) (/usr/share/texmf-texlive/tex/generic/xypic/xy.sty
(/usr/share/texmf-texlive/tex/generic/xypic/xy.tex Bootstrap'ing: catcodes,
docmode, (/usr/share/texmf-texlive/tex/generic/xypic/xyrecat.tex)
(/usr/share/texmf-texlive/tex/generic/xypic/xyidioms.tex)


 Xy-pic version 3.7 <1999/02/16>
 Copyright (c) 1991-1998 by Kristoffer H. Rose <krisrose@ens-lyon.fr>
 Xy-pic is free software: see the User's Guide for details.


Loading kernel: messages; fonts; allocations: state, direction,
utility macros; pictures: \xy, positions, objects, decorations;
kernel objects: directionals, circles, text; options; algorithms: directions,
edges, connections;  Xy-pic loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyall.tex
 Xy-pic option: All features v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xycurve.tex
 Xy-pic option: Curve and Spline extension v.3.7 curve, circles, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyframe.tex
 Xy-pic option: Frame and Bracket extension v.3.7 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycmtip.tex
 Xy-pic option: Computer Modern tip extension v.3.3
(/usr/share/texmf-texlive/tex/generic/xypic/xytips.tex
 Xy-pic option: More Tips extension v.3.3 loaded) loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyline.tex
 Xy-pic option: Line styles extension v.3.6 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyrotate.tex
 Xy-pic option: Rotate and Scale extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xycolor.tex
 Xy-pic option: Colour extension v.3.3 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xymatrix.tex
 Xy-pic option: Matrix feature v.3.4 loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xyarrow.tex
 Xy-pic option: Arrow and Path feature v.3.5 path, \ar, loaded)
(/usr/share/texmf-texlive/tex/generic/xypic/xygraph.tex
 Xy-pic option: Graph feature v.3.7 loaded) loaded))
(/usr/share/texmf-texlive/tex/latex/graphics/graphicx.sty
(/usr/share/texmf-texlive/tex/latex/graphics/keyval.sty)
(/usr/share/texmf-texlive/tex/latex/graphics/graphics.sty
(/usr/share/texmf-texlive/tex/latex/graphics/trig.sty)
(/etc/texmf/tex/latex/config/graphics.cfg)
(/usr/share/texmf-texlive/tex/latex/graphics/dvips.def)))
(/usr/share/texmf-texlive/tex/latex/graphics/color.sty
(/etc/texmf/tex/latex/config/color.cfg)
(/usr/share/texmf-texlive/tex/latex/graphics/dvipsnam.def))
(/usr/share/texmf-texlive/tex/latex/tools/verbatim.sty)
(/usr/share/texmf/tex/latex/graphviz/graphviz.sty
(/usr/share/texmf-texlive/tex/latex/psfrag/psfrag.sty))
(/usr/share/texmf/tex/latex/sagetex.sty
Writing sage input file 549056191196321642-18.0px.sage
(./549056191196321642-18.0px.sout))
(/usr/share/texmf-texlive/tex/latex/gnuplottex/gnuplottex.sty
(/usr/share/texmf-texlive/tex/latex/base/latexsym.sty)
(/usr/share/texmf-texlive/tex/latex/moreverb/moreverb.sty))
(./549056191196321642-18.0px.aux) [1]
Overfull \hbox (36.07521pt too wide) in paragraph at lines 110--110
[]\OT1/cmtt/m/n/12 recursiveDefine(fib,(n:I):I+->if n<2 then 1 else fib(n-1) + 
fib(n-2))[] 
[2]
Overfull \hbox (17.5502pt too wide) in paragraph at lines 126--126
[]\OT1/cmtt/m/n/12 gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(
x1,x2)[] 
[3] [4] [5] [6] (/usr/share/texmf-texlive/tex/latex/amsfonts/umsa.fd)
(/usr/share/texmf-texlive/tex/latex/amsfonts/umsb.fd)
(/usr/share/texmf-texlive/tex/latex/base/ulasy.fd) [7] [8]
Overfull \hbox (17.5502pt too wide) in paragraph at lines 191--191
[]\OT1/cmtt/m/n/12 gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(
x1,x2)[] 
[9] [10] [11] [12] [13]
 Misplaced alignment tab character &.
l.220 $,A -&
            gt; B) -&gt; $
 Misplaced alignment tab character &.
l.220 $,A -&gt; B) -&
                     gt; $
[14] [15] [16] [17] [18] [19] [20] [21] (./549056191196321642-18.0px.aux) )
(see the transcript file for additional information)
Output written on 549056191196321642-18.0px.dvi (21 pages, 8176 bytes).
Transcript written on 549056191196321642-18.0px.log.