constructing a bwise graph from a formula
by 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. In general one could also take a big leap in programming, and look at what C compilers are already supposed to do for decades: Bwise defining itself as Bwise blocks .
As an example to make clear what I mean, let's 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 intermediate 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 pretty-print 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 \
) \
) \
]
}immediately 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 use Maxima to render the formula in a human readable (though not typeset) 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 placement is rather random), the formula can be rendered as a graph of connected function blocks in bwise, where c equals constant and s is slider:
as can be seen on the above mentioned 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 exercise 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 its structure as the first attempt to automatically make a block structure which corresponds to it, preferably in a invertible sense.
Let's 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 let's make the tcl nested function 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 car_deep. It returns a list of 'function' names at depth $level. It simply returns the main (last or toplevel, end of tree) function by calling it with level=0.
Let's try it a nice way, and start with some 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
}
proc unbrace t {
set i 1000;
while {[string range $t 0 0]=="\{" && [incr i -1] > 0 } {
if {[llength $t] <2} {
set t [lindex $t 0]
}
}
return $t
}
proc car_repeated_unbrace { {list} {level} } {
set r {}
foreach i $list {
lappend r [unbrace [car $i]]
}
return $r
}
proc cdr_unbrace_repeated { {list} {level} } {
set r {}
foreach i $list {
set t [unbrace [cdr $i]]
#puts "$i.$t."
if {$t != {}} {
lappend r $t
}
}
return $r
}
proc cardeep { {l} {d {1}} } {
set r $l
# set l [unbrace $l]
set l [list $l]
while {[incr d -1] >= 0} {
# puts "r: $r\nl: $l"
set r [car_repeated_unbrace $l 0]
set l [unbrace [cdr_unbrace_repeated $l 0]]
}
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), and a remover of redundant (for my purpose) braces, and conbinations thereof. The end result is planned to be of simple repeated function call kind, with no explicit stacks or recursion, though that without question is possible, too.
Now let's give de main proc 'cardeep' meaning the beginning of sublists at certain depth, our extracted list structure (from the page about constructing formulas with blocks in this case), and see if it gives us what we want:
for {set i 0} {$i <6} {incr i} {puts "depth $i, cardeep: [cardeep $cc $i]"}
depth 0, cardeep: divide {slider } {add {double {const } } {slider } }
depth 1, cardeep: divide
depth 2, cardeep: slider add
depth 3, cardeep: double slider
depth 4, cardeep: const
depth 5, cardeep:The index 0 result is not really congruent, but intentional, and indeed the whole at first sight (and with this test data...) appears to be according to plan now.
This result can be used to do the next task: making the actual graphical bwise blocks, by applying the main function from Automatically generate Bwise blocks from procedures, in this case adapted with an extra argument to determine the positioning of the resulting block on the canvas:
proc proc_toblock { {procname} {args {}} {blockname {}} {xy {300 200}} } {
if {$blockname== ""} {set blockname $procname}
set blockname [block_genname $blockname]
set c "$procname"
foreach i [info args $procname] {
append c " \$\{$blockname.[list $i]\}"
}
set ret [eval pro_args newproc "{{f {set $blockname.out \[$c\] }} {in {[info args $procname]}} {out {out}} {x [lindex $xy 0]} {y [lindex $xy 1]} {name $blockname} } " ]
puts $ret
eval $ret
foreach i [info args $procname] {
uplevel #0 "info default $procname $i $procname.$i"
}
foreach i $args {
# puts $i
uplevel #0 "set $blockname.[lindex $i 0] [lindex $i 1 end]"
}
return $blockname
}This proc makes use of the normal tcl recorded 'proc' function arguments to create a graphical block with pins for arguments.
Now our first graph creation step is to put the blocks corresponding to the nested formula on the canvas, assuming there are tcl functions corresponding with each sub-formula command, starting at the right upper hand, indenting to the left for each level of deeper nesting:
proc nested_toblocks { {c} } {
set cs {} ; set ca {}
set j 0;
set x 440
set y 40
set cc [join [split [join [split $c \[] \{] \]] \}]
# puts $cc
# set pp [proc_toblock [lindex $cc 0] {} {} [list $x $y]]
incr x -100
set y 40
# set pp [block_get_pinnames $pp typein]
set i 0
set r {}
while {[incr i] < 100 && [set l [cardeep $cc $i]] != {}} {
lappend r $l
foreach k $l {
lappend rr [proc_toblock [lindex $k 0] {} {} [list $x $y]]
# [block_get_pinnames $rr typein]
incr y 60
}
incr x -100
set y 40
}
return $rr
}And indeed this starts to give us the intended result, a graph for a/the given formula:above, resulting from starting with an empty canvas and this call:
set t [nested_toblocks $c]
gives as printed output:
newproc {set divide.out [divide ${divide.num} ${divide.den}] } divide {num den} out 40 {} {} 340 40
newproc {set slider.out [slider] } slider {} out 40 {} {} 240 40
newproc {set add.out [add ${add.i1} ${add.i2}] } add {i1 i2} out 40 {} {} 240 100
newproc {set double.out [double ${double.in}] } double in out 40 {} {} 140 40
newproc {set slider1.out [slider] } slider1 {} out 40 {} {} 140 100
newproc {set const.out [const] } const {} out 40 {} {} 40 40
divide slider add double slider1 constand as graph:
Now we can start drawing the connections, which should be fairly easy. The return value of the previous proc has been stored in t and is:
puts $t divide slider add double slider1 const
Which is the order in which the blocks have been created from the formula. Using that order, we can assume in the case that our graph represents a perfect function, so that all pins are connected. so we can make use of our implicit ordering and do:
set ii {} ; set io {};
foreach j $t {
foreach i1 [block_get_pinnames $j typein] {
lappend ii [list $j $i1]
} ;
foreach i1 [block_get_pinnames $j typeout] {
lappend io [list $j $i1]
}
}
puts $ii,$io
{divide num} {divide den} {add i1} {add i2} {double in},{divide out} {slider out} {add out} {double out} {slider1 out} {const out}making use of bwise procs to get all input or output pins of a named block we get a list of all input and a list of all output pins, as tuples with the corresponding block name.
Now we can generate the connect commands necessary to command bwise to draw connections:
set o {};
for {set i 0} {$i < [llength $ii]} {incr i} {
set i1 [lindex $ii $i];
set i2 [lindex $io [expr $i+1]];
append o "connect {} $i1 $i2\n"
}Resulting in:
puts $o
connect {} divide num slider out
connect {} divide den add out
connect {} add i1 double out
connect {} add i2 slider1 out
connect {} double in const outnow
eval $o
gives the complete graph:
When all leaves of the tree are '(net_)funprop'-ed, the outcome is also the same as for the original formula, even though branch reuse isn't done in this case (leaving us with 2 'slider' blocks).
TV (dec 7 '04) Mind that the directly above was only a hack, I don't guarantee it is in finished working order, in fact when I messed around with some other example I wasn't all too sure it was correct, even after trying to mind the {}'s... :) At the risk of playing the (unpaid...) professor, it's a decent and useful assignment to make it (what's suggested in the title) work right, when someone (or I) has some time to spare.
TV (jun 30 '08) Apparently, nobody has.
See also: Constructing a Bwise Graph from a Maxima Formula