Tacit programming
if 0 { EMJ 2014-03-25 : possibly not a good idea to remove RS's if 0 idiom - it makes the entire page readable by tclsh without error! (It has been spoiled already on some pages, but not this one.) See if 0 { }.
AMG: Unfortunately, having a close brace after the category listing confuses the wiki's "Add comments" feature. See [L1 ] for an example.
EMJ: Never use the feature, didn't see that one coming!
AMG: Ironically, your comment asserting that this page can be read by tclsh without error is itself the cause of an error when feeding this page into tclsh. The problem is mismatched braces! The link to the "if 0" page has an open brace but no close.
EMJ: Should have seen that one (and tested my own assertion). Oops! Now fixed. }
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 [L2 ] 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).
"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 Schönfinkel/Curry's 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.5if 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 upwardswhich may better explain why I wouldn't want to code in J :^) J has ASCIIfied 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,worldif 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.5if 0 {As this file gets tacitly sourced, 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 pipes 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 numbersIn 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.0In contrast to expr's hypot(), this function can also compute Euclidian distances in >2-dimensional space.
gold: When I run func by itself, I get an unknown variable messege in eTCL. Following console program seems to work:
console show
set aa 1
proc func {name argl body} {proc $name $argl [list expr $body]}
func pie aa sin($aa)
puts " [pie .5 ] "
#Tacit programming.mht,rs}