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

Edit detail for SandBoxCachedFunction revision 1 of 10

1 2 3 4 5 6 7 8 9 10
Editor: hemmecke
Time: 2009/10/27 16:17:37 GMT-7
Note:

changed:
-
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
\end{axiom}

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.02 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.08 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 27 OCT 2009 07:27:03 PM): ; 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.074 ------------------------------------------------------------------------ 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.07 (OT) = 0.07 sec
f(n:I): I ==1
Function declaration f : Integer -> Integer has been added to workspace.
Type: Void
axiom
Time: 0 sec
fib: CachedFunction(I,I) := cachedFunction(f)
axiom
Compiling function f with type Integer -> Integer 
LISP output: (#<HASH-TABLE :TEST EQUAL :COUNT 0 {1005B48391}> #<FUNCTION |*1;f;1;initial|>)
Type: CachedFunction?(Integer,Integer)
axiom
Time: 0.02 (IN) + 0.01 (EV) + 0.01 (OT) = 0.04 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 {1005B48391}> #<FUNCTION |*1;anonymousFunction;0;initial;internal|>)
Type: CachedFunction?(Integer,Integer)
axiom
Time: 0.03 (IN) + 0.01 (OT) = 0.04 sec
fib 40
LatexWiki Image(2)
Type: PositiveInteger?
axiom
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
axiom
Time: 0 sec
g 40
axiom
Compiling function g with type Integer -> Integer
LatexWiki Image(3)
Type: PositiveInteger?
axiom
Time: 11.48 (EV) + 0.01 (OT) = 11.49 sec