Demand-driven computation

Arjen Markus (21 december 2005) Spreadsheets differ in the way they perform their computation from ordinary programs (in Tcl or Fortran or most other languages): you do not need to specify the order of the computations. Somehow they determine that themselves: you can refer to cell Z100 in the formula for cell A1, for instance.

Can we do the same? Yes, we can.

It is even possible without analysing the formulae for references to other variables.

The script below defines a simple set of computations, one for each variable. Then it prints the variable "volume" - without it having been set before....

Run it and you will see what happens!

We need a buzzword for this paradigm, so that is why I called the page Demand-driven computation or DDC. (But seriously, you could do interesting things this way)

# demand.tcl --
#     "Demand-driven" computation
#
package require Tcl 8.4         ;# Advanced [lindex]
namespace eval ::DemandDriven {
}

# compute --
#     Register the variables and the associated computations
# Arguments:
#     list         List of variable-expression pairs
# Result:
#     None
# Side effects:
#     The variables are defined in global namespace and
#     there are read traces attached to them
#
proc ::DemandDriven::compute {list} {

    foreach {v expr} $list {
        global $v
        trace add variable ::$v read [list ::DemandDriven::GetValue $expr]
    }
}

# GetValue --
#     Get the value of the variable
# Arguments:
#     expr         The expression by which to get the value
#     name         Name of the variable (it is global!)
#     dummy        Dummy in this context
#     op           Operation (dummy too)
# Result:
#     None
# Side effects:
#     The variable is set
#
proc ::DemandDriven::GetValue {expr name dummy op} {
    #
    # We need to take more care: traces are not nested ...
    if { ! [info exists ::$name] } {
        set count 0
        while { [catch {
                 uplevel #0 [string map [list NAME $name EXPR $expr] {set ::NAME [expr {EXPR}]}]
             } msg] } {
            if { [regexp {can't read "(.*)": no} $msg ==> varname] } {
                uplevel #0 [list set ::$varname \
                    "\[::DemandDriven::GetValue [list [lindex [trace info variable ::$varname] 0 1]] $varname {} read\]"]
                incr count
            } else {
                puts $errorInfo
                break
            }
            if { $count > 3 } { break }
        }
    }
}

# ask --
#     Print a question and ask for the answer
# Arguments:
#     question     The question to be posed
# Result:
#     Whatever the user types
#
proc ask {question} {
    puts -nonewline $question
    flush stdout
    gets stdin
}

# main --
#     Test this idea
#
::DemandDriven::compute {
   volume       {$sphere? $volumeSphere : $volumeCube}
   sphere       {[ask "Is it a sphere (1) or a cube (0)? "]}
   volumeSphere {4.0*$pi/3.0*pow($rad,3)}
   volumeCube   {pow($side,3)}
   pi           3.1415926
   side         {[ask "The side of the cube: "]}
   rad          {[ask "The radius of the sphere: "]}
}
puts "Compute the volume of a sphere or cube:"
puts "Volume: $volume"

NEM: Very nice! Mozart/Oz has the concept of a dataflow variable which is essentially very similar to this. A dataflow variable is like a logic variable in Prolog in that it is initially unbound and once given a value it keeps it (i.e., it is not mutable). However, dataflow variables are also used as a communication/condition synchronisation mechanism between threads: if one thread tries to get the value of an unbound variable it will suspend until another thread binds the variable (through unification). This allows for declarative programming of concurrency (see Concurrency concepts), and is really a very interesting technique as it really takes a lot of the complexity out of multi-threaded programming. The BOOK Concepts, Techniques, and Models of Computer Programming has much more on the subject.

HJG I get 'Error: can't read "volume": can't read "errorInfo": no such variable'. Maybe this uses a Tcl 8.5 feature ?

AM That is strange ... I use a Tcl 8.4 feature (lindex with two indices) but that is all. Are you using tclsh ? Wish on Windows will have a severe problem - [gets] is not working from a console. RS: Have a look at the gets workaround :)

In a wish console on Windows I get: % source demand.tcl Is it a sphere (1) or a cube (0)? can't read "volume": can't read "errorInfo": no such variable (tmp) 2 %

This brings to CL's mind, along with dataflow variables, inferencing in expert systems, generally under the rubric of "forward [or backward] chaining".

Category Concept