if 0 {[Richard Suchenwirth] 2005-04-17 - I found the term "tacit programming" (tacit: ''implied: indicated by necessary connotation though not expressed directly'') in a fascinating article [http://elliscave.com/APL_J/EasyJ.pdf] about the J programming language (the "blessed successor" to APL, see [Playing APL], where "every function is an infix or prefix operator", x?y (dyadic) or ?y (monadic), for ? being any pre- or user-defined function). [http://www.cs.trinity.edu/About/The_Courses/cs2322/zippy.gif] "Tacit programming" is one of the styles possible in J, and means coding by combining functions, without reference to argument names. This idea may have been first brought up in [Functional programming (Backus 1977)], if not in [Forth] and [Joy], and it's an interesting simplification compared to the [lambda] calculus. For instance, here's a breathtakingly short J program to compute the mean of a list of numbers: mean=.+/%# Let's chew this, byte by byte :) =. is assignment to a local variable ("mean") which can be called +/%# is the "function body" + (dyadic) is addition / folds the operator on its left over the list on its right +/ hence being the sum of a list % (dyadic) is division, going double on integer arguments when needed # (monadic) is tally, like Tcl's [llength] resp. [string length] Only implicitly present is a powerful function combinator called "fork". When J parses three operators in a row, gfh, where f is dyadic and g and h are monadic, they are combined like the following [Tcl] version does:} proc fork {f g h x} {$f [$g $x] [$h $x]} if 0 {In other words, f is applied to the results of applying g and h to the single argument. Note that +/ is considered one operator, which applies the "adverb" folding to the "verb" addition (one might well call it "sum"). When two operands occur together, the "hook" pattern is implied, which might in Tcl be written as:} proc hook {f g x} {$f $x [$g $x]} if 0 {As [KBK] pointed out in the [Tcl chatroom], the "hook" pattern corresponds to the S combinator (see [Hot Curry] and [Combinator Engine]), while "fork" is called S' there. Unlike in earlier years when I was [playing APL], this time my aim was not to parse and emulate J in Tcl - I expected hard work for a dubitable gain, and this is a weekend fun project after all. I rather wanted to explore some of these concepts and how to use them in Tcl, so that in slightly more verbose words I could code (and call) Def mean = fork /. sum llength following Backus' FP language with the "Def" command. So let's get the pieces together. My "Def" creates an [interp alias], which is a good and simple Tcl way to compose partial scripts (the definition, here) with one or more arguments, also known as "currying":} proc Def {name = args} {eval [list interp alias {} $name {}] $args} if 0 {The second parameter, "=", is for better looks only and evidently never used. Testing early and often is a virtue, as is documentation - to make the following code snippets clearer, I tuned my little tester for better looks, so that the test cases in the source code also serve as well readable examples - they look like comments but are code! The cute name "e.g." was instigated by the fact that in J, "NB." is used as comment indicator, both being well known Latin abbreviations:} proc e.g. {cmd -> expected} { catch {uplevel 1 $cmd} res if {$res != $expected} {puts "$cmd -> $res, not $expected"} } if 0 {Again, the "->" argument is for eye-candy only - but it feels better to me at least. See the examples soon to come. For recursive functions and other arithmetics, [func] makes better reading, by accepting [expr] language in the body:} proc func {name argl body} {proc $name $argl [list expr $body]} if 0 {We'll use this to turn [expr]'s infix operators into dyadic functions, plus the "slashdot" operator that makes division always return a real number, hence the dot :} foreach op {+ - * /} {func $op {a b} "\$a $op \$b"} e.g. {+ 1 2} -> 3 e.g. {/ 1 2} -> 0 ;# integer division func /. {a b} {double($a)/$b} e.g. {/. 1 2} -> 0.5 ;# "real" division #-- Two abbreviations for frequently used list operations: proc head list {lindex $list 0} e.g. {head {a b c}} -> a proc tail list {lrange $list 1 end} e.g. {tail {a b c}} -> {b c} if 0 {For "fold", this time I devised a recursive version:} func fold {neutral op list} { $list eq [] ? $neutral : [$op [head $list] [fold $neutral $op [tail $list]]] } e.g. {fold 0 + {1 2 3 4}} -> 10 #-- A "Def" alias does the same job: Def sum = fold 0 + e.g. {sum {1 2 3 4}} -> 10 #-- So let's try to implement "mean" in tacit Tcl! Def mean = fork /. sum llength e.g. {mean {1 2 3 40}} -> 11.5 if 0 {Tacit enough (one might have picked fancier names like +/ for "sum" and # as alias for [llength]), but in principle it is equivalent to the J version, and doesn't name a single argument. Also, the use of [llength] demonstrates that any good old Tcl command can go in here, not just the artificial Tacit world that I'm just creating... In the next step, I want to reimplement the "median" function, which for a sorted list returns the central element if its length is odd, or the mean of the two elements adjacent to the (virtual) center for even length. In J, it looks like this: median=.(mean@:\{~medind@#)@sortu medind=.((<.,>.)@half) ` half @.(2&|) half=.-:@<: NB. halve one less than rt. argument sortu=.\{~/: NB. sort upwards which may better explain why I wouldn't want to code in J :^) J has [ASCII]fied the zoo of APL strange character operators, at the cost of using braces and brackets as operators too, without regard for balancing, and extending them with dots and colons, so e.g. - monadic: negate; dyadic: minus -. monadic: not -: monadic: halve J code sometimes really looks like an accident in a keyboard factory... I won't go into all details of the above code, just some: @ ("atop") is strong linkage, sort of functional composition <. (monadic) is floor() >. (monadic) is ceil() (<.,>.) is building a list of the floor and the ceiling of its single argument, the comma being the concatenation operator here, comparable to Backus' "construction" or Joy's ''cleave''. The pattern a ` b @. c is a kind of conditional in J, which could in Tcl be written if {[$c $x]} {$a $x} else {$b $x} but my variant of the median algorithm doesn't need a conditional - for lists of odd length it just uses the central index twice, which is idempotent for "mean", even if a tad slower. J's "from" operator \{ (without the backslash, but unbalanced braces are troublesome in Tcl code, which this page is) takes zero or more elements from a list, possibly repeatedly. For porting this, [lmap] is a good helper, even though not strictly functional:} proc lmap {_v list body} { upvar 1 $_v v set res {} foreach v $list {lappend res [uplevel 1 $body]} set res } e.g. {lmap i {1 2 3 4} {* $i $i}} -> {1 4 9 16} #-- So here's my 'from': proc from {indices list} {lmap i $indices {lindex $list $i}} e.g. {from {1 0 0 2} {a b c}} -> {b a a c} if 0 {We furtheron borrow some more content from [expr]:} func ceil x {int(ceil($x))} func floor x {int(floor($x))} e.g. {ceil 1.5} -> 2 e.g. {floor 1.5} -> 1 e.g. {fork list floor ceil 1.5} -> {1 2} if 0 {We'll need [functional composition], and here's a recursive de-luxe version that takes zero or more functions, hence the name o*:} func o* {functions x} { $functions eq []? $x : [[head $functions] [o* [tail $functions] $x]] } e.g. {o* {} hello,world} -> hello,world if 0 {Evidently, identity as could be written proc I x {set x} is the neutral element of variadic functional composition, when called with no functions at all. If composite functions like 'fork' are arguments to o*, we'd better [let unknown know] that we want auto-expansion of first word:} proc know what {proc unknown args $what\n[info body unknown]} know { set cmd [head $args] if {[llength $cmd]>1} {return [eval $cmd [tail $args]]} } if 0 {Also, we need a numeric sort that's good for integers as well as reals ("Def" serves for all kinds of aliases, not just combinations of functions):} Def sort = lsort -real e.g. {sort {2.718 10 1}} -> {1 2.718 10} e.g. {lsort {2.718 10 1}} -> {1 10 2.718} ;# lexicographic #-- And now for the ''median'' test: Def median = o* {mean {fork from center sort}} Def center = o* {{fork list floor ceil} {* 0.5} -1 llength} func -1 x {$x - 1} e.g. {-1 5} -> 4 ;# predecessor function, when for integers #-- Trying the whole thing out: e.g. {median {1 2 3 4 5}} -> 3 e.g. {median {1 2 3 4}} -> 2.5 if 0 {As this file gets tacitly [source]d, I am pretty confident that I've reached my goal for this weekend - even though my ''median'' doesn't remotely look like the J version: it is as "wordy" as Tcl usually is. But the admittedly still very trivial challenge was met in truly function-level style, concerning the definitions of ''median'', ''center'' and ''mean'' - no variable left behind. And that is one, and not the worst, Tcl way of [Tacit programming]... ---- Somehow [pipe]s as used in Unix and even DOS/Windows qualify for tacit programming too - they act like [functional composition], with the implicit context often being understood as lines of text: grep -v error | sed s/warning/greeting/ | sort -u | wc -l ---- [AM] (18 april 2005) Very similar things can actually be done in Fortran 90 and with the array-processing extension to Tcl, [NAP]. That is, use high-level commands/statements that completely hide the details: real, dimension(1:5) :: array array = (/ 1, 2, 3, 4, 5 /) mean = sum(sin(array))/size(array) ! Determine the mean of the sine of a list of numbers In NAP: nap "array = {1 2 3 4 5}" nap "mean = sum(sin(array))/nels(array)" puts [$mean] ---- [RS] Yes, but Backus' point is that combining functions (i.e. without going into the details of variables, like ''array'' in your example) is "lambda-free" programming at a higher level. That [vector arithmetics] can make code very much simpler, is a valid point of course - [APL] and J also have it built-in. Conceptually I tend to agree to Backus' purity, but I also have to admit that quite a lot of works were needed to get ''median'' afloat, while in good old imperative programming it's a matter of a few lines, without dependencies to other code: proc median list { set i [expr {[llength $list]/2}] expr {[llength $list]%2==1? [lindex $list $i] : ([lindex $list $i]+[lindex $list [incr i -1]])/2.} } ---- '''hypot''': For this classic function, we need the classic [map]: proc map {f list} {lmap i $list {$f $i}} e.g. {map floor {1.5 2.5}} -> {1 2} And some math helpers: func square x {$x*$x} func sqrt x {sqrt($x)} That's all, let's go! Def hypot = o* {sqrt sum {map square}} e.g. hypot {3 4} -> 5.0 In contrast to [expr]'s hypot(), this function can also compute Euclidian distances in >2-dimensional space. ---- [Category Functional Programming] | [Arts and crafts of Tcl-Tk programming] }