Version 9 of constructing a bwise graph from a formula
Updated 2004-11-08 12:28:39 by TVby TV, of course feel free to add/comment/correct as is normal on the wiki
Starting from the ideas from constructing mathematical formulas with Bwise blocks we will look at the reverse of that idea here: to make a bwise canvas with blocks representing a certain repeated function call formula automatically.
As an example to make clear what I mean, lets consider the formula (and its arguments, the variables s and c):
set s 2 set c 8 puts [expr $s / ( (2.0 * ($c) ) + $s ) ]
In this case the outcome of the expression formula is:
0.111111111111
of course we could change either or both of the variables, and get a different outcome. Clearly the expr can be written a bit shorter when taking into consideration normal precedence rules, for instance as: $s/(2.0*$c+$s), not changing the outcome when we used the expr rules right, and when we assume accuracy of intermedeate computations aren't influenced by our formula rewriting.
For clarity as to how the outcome of this, rather random, it has no special meaning for me, formula is formed, we can prettypring the parts making up the formula, like one would in regular C language formatting conventions for instance:
proc ourformula {s c} {
return [expr \
\
$s \
/ \
( \
( \
2.0 \- \
( \
$c \
) \
) \
+ \
( \
$s \
) \
) \
]
}immedeately forging it into a procedure, which has the nature of what would classically be called a function: an outcome based on a functional description based on arguments. Simplified by reducing syntactically superfluous braces:
proc ourformula {s c} {
return [expr \
\
$s / ( \
2.0 * $c \
+ $s \
) \
]
}Alternatively, we could us Maxima to render the formula in a human readable (though not typesetted) form:
f(s,c):= s / ( (2 * (c) ) + s ) ;
s
f(s, C) := -------
2 C + sso that we easily know what formula we're talking about, maybe in shortest form: $s/(2.0*$c+$s) for expr. Without embellishment(the block placementis rather random), the formula can be rendered as a graph of connected function blocks, where c equals constant and s is slider:
as can be seen on the abovementioned page.
For Tcl without complicated Expr, the rendering on that page as nested function calls is mathematically quite sound, such as in functional analysis:
divide $s [add [double $c ] $s ]
where divide is a function (called procedure in tcl) which returns its first argument divided by its second, add returns the numerical sum of its two arguments and double obviously returns the numerical double of its single argument. It is quite possible, but not an excercise I'll do here, to convert any expression into such nested function call equivalent. For the moment I'll convert the last formula representation, which is easily readable for humans and computers, with some practice, to a nested list representation first, because I'll use tcl list processing to tackle it's structure as the first attempt to automatically make a block structure which corresponds to it, preferably in a invertable sense.
Lets define the same functions (procs which have no memory or access to other data than their explicit arguments and a single return value) as on the reverse example:
proc divide {num den} { return [expr $num / $den] }
proc double { {in} } { return [expr 2.0*$in] }
proc slider {} { return "2" }
proc const {} {return 8}
proc add {i1 i2} {return [expr $i1+$i2]}
proc divide {num den} {return [expr $num/$den]}where I've only replaced the slider direct Tk access by a fixed "2".
Now lets make the tcl nested funciton call into a nested list of sublists with command names and arguments, which we can then analyze and split into connected blocks:
set c {divide [slider ] [add [double [const ] ] [slider ] ]}
set cc [join [split [join [ split $c \[] \{] \] ] \} ]
divide {slider } {add {double {const } } {slider } }I don't know split / join is the best principle here but it works easily in a short oneliner to in turn replace the [ with { and then the ] with } of the first result (especially special character quoting might be complicated).
Now before the whole project can be attempted, I want a function which will give me the blocks at a certain distance from the final function, which I called cdr_deep. It returns a list of lists of {function arguments ...} starting at depth $level, so it simply returns the whole function being implemented by calling it with level=0. Maxlevel is to prevent eternal recursions on error, a good practice with recursive procs.
proc cdr_deep { list {level 0} {maxdepth 100} } {
#puts "cdr_deep $list $level $maxdepth"
set r {}
if {$maxdepth <1} {return "RECURSION_LIMIT"}
if {$level == 0} {
return [lrange $list 0 end]
}
if {[llength $list] <2} { return $list }
foreach i [lrange $list 1 end] {
if {[llength $i] >1} {
set t [cdr_deep $i [expr $level-1] [expr $maxdepth-1]]
if {$t != {}} {
if {$r != {}} {
lappend r $t
} { set r $t }
}
}
if {[llength $i] ==1} {
set t [cdr_deep $i [expr $level-1] [expr $maxdepth-1]]
if {$t != $i} {
if {$r != {}} {
lappend r $t
} { set r $t }
}
}
}
#puts "return $r"
return $r}
Calling it with the above function/network description:
for {set i 0} {$i < 6} {incr i} {puts "$i: [cdr_deep $cc $i]" }
0: divide {slider } {add {double {const } } {slider } }
1: slider {add {double {const } } {slider }}
2: double {const } slider
3: const
4:
5: That's almost correct, so it needs a bit work, the 2nd result should be two lists, not 3. After that, I'll add the code to generate the blocks and the connections, which is then easier for the general case, I've tried on another machine already for a limited case. Stay tuned...
while I again take some time for this, maybe some will find it interesting to add a debugging trace to the routine, with indenting, I'll remove this when our little nested list slicing routine is done (he I'm not at a well paid univiversity position here teaching high quality first year programming practicum... I supposed to muck about a bit to see what I actually think..)
proc cdr_deep { {list} {level {0}} {maxdepth {100}} } {
set id ""
for {set i 0} {$i < [expr 5-$level] } {incr i} {
append id "| "
}
puts "$id cdr_deep $list $level $maxdepth"
set r {}
if {$maxdepth <1} {return "RECURSION_LIMIT"}
if {$level == 0} {
puts "$id level ==0"
return [lrange $list 0 end]
}
if {[llength $list] <2} {
puts "$id llength < 2"
return $list
}
foreach i [lrange $list 1 end] {
puts "$id i=$i"
if {[llength $i] >1} {
puts "$id length > 1"
set t [cdr_deep $i [expr $level-1] [expr $maxdepth-1]]
puts "$id t=$t"
if {$t != {}} {
if {$r != {}} {
lappend r $t
} { set r $t }
}
}
if {[llength $i] ==1} {
puts "$id length == 1"
set t [cdr_deep $i [expr $level-1] [expr $maxdepth-1]]
puts "$id t=$t"
if {$t != $i} {
if {$r != {}} {
lappend r $t
} { set r $t }
}
}
puts "$id r=$r"
}
puts "$id return $r"
return $r
}# Now debug call (all this being far from perfect or even claiming to be professional... :) ):
for {set i 0} {$i < 6} {incr i} {puts "$i: [cdr_deep $cc $i]" }
| | | | | cdr_deep divide {slider } {add {double {const } } {slider } } 0 100
| | | | | level ==0
0: divide {slider } {add {double {const } } {slider } }
| | | | cdr_deep divide {slider } {add {double {const } } {slider } } 1 100
| | | | i=slider
| | | | length == 1
| | | | | cdr_deep slider 0 99
| | | | | level ==0
| | | | t=slider
| | | | r=slider
| | | | i=add {double {const } } {slider }
| | | | length > 1
| | | | | cdr_deep add {double {const } } {slider } 0 99
| | | | | level ==0
| | | | t=add {double {const } } {slider }
| | | | r=slider {add {double {const } } {slider }}
| | | | return slider {add {double {const } } {slider }}
1: slider {add {double {const } } {slider }}
| | | cdr_deep divide {slider } {add {double {const } } {slider } } 2 100
| | | i=slider
| | | length == 1
| | | | cdr_deep slider 1 99
| | | | llength < 2
| | | t=slider
| | | r=
| | | i=add {double {const } } {slider }
| | | length > 1
| | | | cdr_deep add {double {const } } {slider } 1 99
| | | | i=double {const }
| | | | length > 1
| | | | | cdr_deep double {const } 0 98
| | | | | level ==0
| | | | t=double {const }
| | | | r=double {const }
| | | | i=slider
| | | | length == 1
| | | | | cdr_deep slider 0 98
| | | | | level ==0
| | | | t=slider
| | | | r=double {const } slider
| | | | return double {const } slider
| | | t=double {const } slider
| | | r=double {const } slider
| | | return double {const } slider
2: double {const } slider
| | cdr_deep divide {slider } {add {double {const } } {slider } } 3 100
| | i=slider
| | length == 1
| | | cdr_deep slider 2 99
| | | llength < 2
| | t=slider
| | r=
| | i=add {double {const } } {slider }
| | length > 1
| | | cdr_deep add {double {const } } {slider } 2 99
| | | i=double {const }
| | | length > 1
| | | | cdr_deep double {const } 1 98
| | | | i=const
| | | | length == 1
| | | | | cdr_deep const 0 97
| | | | | level ==0
| | | | t=const
| | | | r=const
| | | | return const
| | | t=const
| | | r=const
| | | i=slider
| | | length == 1
| | | | cdr_deep slider 1 98
| | | | llength < 2
| | | t=slider
| | | r=const
| | | return const
| | t=const
| | r=const
| | return const
3: const
| cdr_deep divide {slider } {add {double {const } } {slider } } 4 100
| i=slider
| length == 1
| | cdr_deep slider 3 99
| | llength < 2
| t=slider
| r=
| i=add {double {const } } {slider }
| length > 1
| | cdr_deep add {double {const } } {slider } 3 99
| | i=double {const }
| | length > 1
| | | cdr_deep double {const } 2 98
| | | i=const
| | | length == 1
| | | | cdr_deep const 1 97
| | | | llength < 2
| | | t=const
| | | r=
| | | return
| | t=
| | r=
| | i=slider
| | length == 1
| | | cdr_deep slider 2 98
| | | llength < 2
| | t=slider
| | r=
| | return
| t=
| r=
| return
4:
cdr_deep divide {slider } {add {double {const } } {slider } } 5 100
i=slider
length == 1
| cdr_deep slider 4 99
| llength < 2
t=slider
r=
i=add {double {const } } {slider }
length > 1
| cdr_deep add {double {const } } {slider } 4 99
| i=double {const }
| length > 1
| | cdr_deep double {const } 3 98
| | i=const
| | length == 1
| | | cdr_deep const 2 97
| | | llength < 2
| | t=const
| | r=
| | return
| t=
| r=
| i=slider
| length == 1
| | cdr_deep slider 3 98
| | llength < 2
| t=slider
| r=
| return
t=
r=
return
5:
Well, with some work I can get the update of the above ticking, but lets try a nicer way, and start with extended LISP basic functions:
proc car l {return [lrange $l 0 0] }
proc cdr l {return [lrange $l 1 end] }
proc car_repeated {list level} {
set r {}
foreach i $list {
lappend r [car $i]
}
return $r
}
proc cdr_repeated {list level} {
set r {}
foreach i $list {
set t [cdr $i]
#puts "$i.$t."
lappend r $t
}
return $r
}
proc rem_nulls { {l} } {
set r {};
foreach i $l {
if {$i != {}} {
lappend r $i
}
};
return $r
}
Basically the head and tail function, but then over all sublists of the offered list, and a remover of empty sublists (at first evaluation level, so {{}} would remain in place at the moment)
Category Mathematics Category Functional Programming Category Functional Analysis Category Graphics