if 0 {Richard Suchenwirth 2004-12-04 - John Backus turned 80 these days. For creating FORTRAN and the BNF style of language description, he received the ACM Turing Award in 1977. In his Turing Award lecture,
Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs. (Comm. ACM 21.8, Aug. 1978, 613-641)
he developed an amazing framework for functional programming, from theoretical foundations to implementation hints, e.g. for installation, user privileges, and system self-protection. I'm far from having digested it all, but like so often, interesting reading prompts me to do Tcl experiments, especially on weekends. I started with Backus' first Functional Program example,
Def Innerproduct = (Insert +) o (ApplyToAll x) o Transpose
and wanted to bring it to life - slightly adapted to Tcl style, especially by replacing the infix operator "o" with a Polish prefix style:
Def Innerproduct = {o {Insert +} {ApplyToAll *} Transpose}Unlike procs or lambdas, more like APL or RPN, this definition needs no variables - it declares (from right to left) what to do with the input; the result of each step is the input for the next step (to the left of it). In an RPN language, the example might look like this:
/Innerproduct {Transpose * swap ApplyToAll + swap Insert} defwhich has the advantage that execution goes from left to right, but requires some stack awareness (and some swaps to set the stack right ;^)
Implementing Def, I took an easy route by just creating a proc that adds the catch-all args argument and leaves it to the "functional" to do the right thing (with some quoting heaven :-) }
proc Def {name = functional} {
proc $name args "\[$functional\] \$args"
}if 0 {For functional composition, where, say for two functions f and g,
[{o f g} $x] == [f [g $x]]again a proc is created that does the bracket nesting: }
proc o args {
set body return
foreach f $args {append body " \[$f"}
set name [info level 0]
proc $name x "$body \$x [string repeat \] [llength $args]]"
set name
}if 0 {Why Backus used Transpose on the input, wasn't first clear to me, but as he (like we Tclers) represents a matrix as a list of rows, which are again lists (also known as vectors), it later made much sense to me. This code for transposing a matrix uses the fact that variable names can be any string, including those that look like integers, so the column contents are collected into variables named 0 1 2 ... and finally turned into the result list: }
proc Transpose matrix {
set cols [iota [llength [lindex $matrix 0]]]
foreach row $matrix {
foreach element $row col $cols {
lappend $col $element
}
}
set res {}
foreach col $cols {lappend res [set $col]}
set res
}if 0 {An integer range generator produces the variable names, e.g
iota 3 => {0 1 2}}
proc iota n {
set res {}
for {set i 0} {$i<$n} {incr i} {lappend res $i}
set res
}#-- This "functional form" is mostly called map in more recent FP:
proc ApplyToAll {f list} {
set res {}
foreach element $list {lappend res [$f $element]}
set res
}if 0 {...and Insert is better known as fold, I suppose. My oversimple implementation assumes that the operator is one that expr understands:}
proc Insert {op arguments} {expr [join $arguments $op]}#-- Prefix multiplication comes as a special case of this:
interp alias {} * {} Insert *#-- Now to try out the whole thing:
Def Innerproduct = {o {Insert +} {ApplyToAll *} Transpose}
puts [Innerproduct {1 2 3} {6 5 4}]if 0 { which returns 28 just as Dr. Backus ordered (= 1*6 + 2*5 + 3*4). Ah, the joys of weekend Tcl'ing... - and belatedly, Happy Birthday, John! :)
Category Functional Programming | Arts and crafts of Tcl-Tk programming }