Arrays as cached functions

Richard Suchenwirth 2002-11-03 - One of the amazing things about Tcl is that one can again and again discover new ways to use the built-in concepts: in this case, array and variable traces. Functions are typically implemented as procs, but here is an alternative - an array that acts like a function: it returns the result when the function body is applied to its arguments (the key). Like in expr functions, arguments are separated by commas instead of whitespace, to please the dollar parser which doesn't group on parens: the command

 set f(x y)

would assign the value "y)" to a scalar variable named "f(x" ! Instead, you call such a function with e.g. two arguments like this:

 puts $f($x,$y)

The first dollar sign substitutes it as a variable (which it really is), but the associated trace computes the function value, if the arguments are not an array element, as implemented in the few lines of code below. A function definition is modeled like a proc definition (no default values or args, though). We observe the following features:

• the body is evaled when necessary, hence not byte-compiled, hence slower
• previous results are cached (see Result caching), which may save time on lengthy calculations
• the cache will consume (but not leak!) memory if the function is called often with different arguments
• variable scope applies: functions defined at global scope must be marked as such when called inside a proc
• otoh, functions defined in a proc are truly local: not visible from elsewhere (except via uplevel); the array as well as its trace disappear on return from the defining proc

Like often, I'm not so sure what this construct is good for, compared to procs, but it sure made a nice Saturday evening braintwister. From the features above, I conclude that this may be helpful if you have calculations that run long even if byte-compiled, and call them repeatedly with same arguments, so caching makes sense. Also, you introduce the C-like calling style, with arguments separated by commas in parens, but this is still Tcl - and experience has taught me that it's best not to stray too far from the Tcl way.- Another consideration: In Braintwisters, "dynamic variables" were introduced whose value is computed when needed, and may change over time. At that time, I thought them "as powerful as an argument-less proc" - the array-based functions described here are (almost) as powerful as a proc with arguments. Just slower - but then again, maybe this little experiment may still be useful for whatever you're doing in Tcl...

 proc function {name argl body} {
    upvar 1 $name f
    array set f {} ;# make it exist (but add no elements)
    trace variable f rw [list runFunction $argl $body]
 }
 proc runFunction {argl body name el op} {
    if {$op=="w"} {error "can't set function value for $name"}
    upvar 1 $name f
    if {![info exists f($el)]} {
        foreach $argl [split $el ,] break
        set f($el) [eval $body]
    } else {set f($el)}
 }
 # Testing... (expected results in front of each puts)
 #--define an array-based function
 function sq2 {x z} {expr {$x*$x + $z}}
 #-- try to call it from global scope
 puts "42? $sq2(6,6)"
 #-- try to call it from inside a proc
 proc test1 {} {puts $sq2(7,7)}
 catch test1 res
 puts "error? $res" ;# should raise "unknown variable" error
 #-- try again, but marked as global this time
 proc test2 {} {puts "56? $::sq2(7,7)"}
 test2
 #-- try a function defined locally inside a proc
 proc test3 {} {
    function local {x y z} {expr {$x*$y-$z}}
    puts "5? $local(3,2,1)"
 }
 test3
 #-- try to call it from global scope
 catch {set local(4,3,2)} res
 puts "error? $res" ;# should raise the same error

escargo 11/04/2002: I have heard this kind of behavior as memoizing, and it is something used in other languages as well:

• Python [L1 ]
• Scheme [L2 ]

See the Memorization class I did (Cacheable class) which provides a generic method to cache method results in XOTcl. Works with absolutely anything and provides a good example of how XOTcl's strengths can be used. Warning: hasn't been tested with newer versions of XOTcl where there have been some changes to filters. Please let me know if there's a problem --Setok

Note: There was a shift in terminology introduced in your code: What I saw described as memoization you have implemented as memorization. -- escargo 6 Nov 2002

AM I realised that this might be a useful technique for a calculator script I wrote some time ago, as a replacement for the UNIX command "bc" (so that I can use it under Windows too). Its specialty is that you can define "macros", but I would rather use the functional approach. (Mental note: Must wikify it.)

I first thought that functions can even be faster than procs, but the error came because the cache was never reset over hundreds of calls (as typically used with time to get more precise results). Here's a fair comparison, running the test (a simple recursive factorial) just once:

 proc pfac x {
    expr {$x<2? 1: $x * [pfac [incr x -1]]}
 }
 function afac x {
    expr {$x<2? 1: $x * $::afac([incr x -1])}
 }
 puts pfac:[time {pfac 30} 1]
 puts afac:[time {set afac(30)} 1]

Solaris:

 pfac:950 microseconds per iteration
 afac:12570 microseconds per iteration