|
|
|
last edited 15 years ago by Bill Page |
Edit detail for SandBoxCachedFunction revision 5 of 10
| 1 2 3 4 5 6 7 8 9 10 | ||
|
Editor: Bill Page
Time: 2009/10/29 10:00:22 GMT-7 |
||
| Note: Caching a function with more than one argument | ||
changed: -gcd2cached:CachedFunction(Pair,Integer):=new gcd2 gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2 changed: -gcd2cached:CachedFunction(Pair,Integer):=new gcd2 gcd2cached:CachedFunction(Pair,Integer):=cachedFunction gcd2
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 \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,ProductandDirectProduct. 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) )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 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 thatTableonly uses an efficient hashing method ifhashable(Key)$Lispis true, whereKeyis the first domain ofTable(Key,Entry). This is true forIntegerandhashable(String)$Lispbut notRecord(x1:Integer,x2:Integer)or evenList(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 ofListandRecordin 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
hashablefunction 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
Canonicalproperty "all the way down".We can test this for now by using HashTable? explicitly and just assuming that that domain
Asatisfies 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) )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 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/5132263765150484496-25px.axmChecking 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.05 SEC.
compiling exported cachedFunction : A -> B -> $ Time: 0 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.07 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:55:58 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.072 ------------------------------------------------------------------------ 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.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 {1005F3E391}> #<FUNCTION |*1;f;1;initial|>) Type: CachedFunction(Integer,Integer) Time: 0.01 (IN) + 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 {1005F3E391}> #<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 (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. Type: Void Time: 0 sec g 40
Compiling function g with type Integer -> Integer
$$ 165580141 \leqno(7) $$
Type: PositiveInteger Time: 11.48 (EV) + 0.02 (OT) = 11.50 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 (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 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 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 Time: 0.01 (IN) = 0.01 sec 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) Time: 0.01 (OT) = 0.01 sec gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair(x1,x2)
Function declaration gcdCached : (Integer,Integer) -> Integer has been added to workspace. Type: Void Time: 0.01 (IN) = 0.01 sec )set message time on
for i in 1..1000 repeat for j in 1..100 repeat gcd(i,j)
Type: Void Time: 3.78 (EV) = 3.78 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 (./8464277529264492172-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: `setspace6.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 8464277529264492172-18.0px.sage (./8464277529264492172-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)) (./8464277529264492172-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 125--125 []\OT1/cmtt/m/n/12 gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair( x1,x2)[] [3] [4] (/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) [5] [6] Overfull \hbox (17.5502pt too wide) in paragraph at lines 184--184 []\OT1/cmtt/m/n/12 gcdCached(x1:Integer,x2:Integer):Integer == gcd2cached pair( x1,x2)[] [7] [8] [9] Misplaced alignment tab character &. l.207 $,A -& gt; B) -> $ Misplaced alignment tab character &. l.207 $,A -> B) -& gt; $ [10] [11] [12] [13] [14] [15] [16] [17] (./8464277529264492172-18.0px.aux) ) (see the transcript file for additional information) Output written on 8464277529264492172-18.0px.dvi (17 pages, 7348 bytes). Transcript written on 8464277529264492172-18.0px.log.