Richard Suchenwirth 2001-12-12 - More steps towards functional programming... When reading about, and playing Haskell, I met the concept of functional composition again, where you conglomerate some functions into one, so in pseudocode the application of the functional object (f . g) to a variable x
(f . g)(x)
is equivalent to
f(g(x))
This, of course, can again be had in Tcl - we just have to compromise that the infix operator "." as used in Haskell must be moved to prefix position (before the arguments), as Polish notation requires - but this allows us to pass any number of arguments, not just two. Also, considering that this code should be runnable in a wish, "." is a (maybe the only) taboo name for a proc: defining "proc ." destroys the primary toplevel window, often causing wish to exit. So I changed the name to the slightly bigger, but harmless comma: ",".
The code below will create a new procedure, which needs a name. I have first found out in Lambda in Tcl that [info level 0] makes a nice self-referential name: it tells how the "," proc was called. As opposed to just counting up a lambda index, this has the added advantage that it avoids memory leaks - execute the same code as often as you wish, the name is always the same and thus overwrites the previous instance...
For now I assume that the generated procedure takes a single argument (call it "x") - but that could be a list. However, the functions to be nested are not restricted to a single word. Rather, if you brace (or quote) them, they may have more leading arguments (in technical terms, currying- see Custom curry), as demonstrated by the "string toupper" example below. In Tcl's glorious spirit of "everything is a string" (so don't be afraid of nothing ;-), we just build up a well-formed proc body (the closing braces were factored out to prevent over-long lines), declare that with the fancy name and the boring "x" argument, return the name, and off we go...
proc , args {
set name [info level 0]
set closing [string repeat {]} [expr [llength $args]-1]]
set body "[join $args { [}] \$x $closing"
proc $name x $body
set name
}if 0 {Now testing... both use cases of "on-the-fly", and saving the generated name in a variable for subsequent use: the first example is strictly alphabetic, while in the second, "T" comes before "c" and" "l" - where it belongs ;-}
% [, lsort {string toupper}] {z R a}
A R Z
% set try [, {string tolower} lsort]
, {string tolower} lsort
% info body $try
string tolower [lsort $x ]
% $try {l c T}
t c lif 0 { Final note: Reading on Haskell, I sometimes have a vague feeling of inferiority: They have so much (at a cost of increased syntax complexity, types and all) - but then again, our simple Tcl can catch up in 7 lines of code...
Reinhard Max contributed this condensed version:
proc · {args} {
proc [set name [info level 0]] x "[join $args { [}] \$x [string repeat \] [expr {[llength $args]-1}]]"
set name
} (RS)...or this one-liner:-)
proc , args {append _ [proc [set _ [info level 0]] x "[join $args { [}] \$x [string repeat \] [expr {[llength $args]-1}]]"]}CL: There are deep things to say about functional composition. Meta-summary: functions are a sufficient model for *anything* interesting/significant, and composition is the natural operation on functions, so functional composition is a universally-expressive idiom. 'Nother way to say the same: we do SOOOOOOO much with the duality between code and data. Well, look at functional composition: it's the natural first step in viewing code (operation, function) as data (subject of algebraic analysis).
See Playing Joy for a Forth-like language that does everything with functional composition.
DKF remarked in the chat: "Actually, the most well known combinator of all is 'o' (usually written inline) which does function composition: o(f,g)(x) == f(g(x))" - RS likes "o" better than the comma.
Good usage examples (with the fancy "o" name) are at Functional imaging.
TV Is aware of the relevance of the subject in various ways, and thought it might be interesting to include functional composition with more than one argument function for the sake of example on this page take 3 functions:
f: x1,x2 --> f(x1,x2) g: x --> g(x) h: x --> h(x)
Then one could make
k: x1,x2 --> k(g(x1),h(x2))
The function evaluation order becomes permutable in this case, to compute the value of k, one can compute
g(x1), h(x2), f(g,h)
or
h(x1), g(x2), f(g,h)
Of course it is quite possible to directly implement this in tcl.
In fact I'll make a bwise page starting with the subject of automatically decomposing a nested function into a bwise graph of composed functions , which is in fact an important part of the target graphs of bwise, though by no means all.
Once one has the functions and their composition it is useful to have a good representation of their composition, to optimize (re-use of intermediate subfunction results), think, and re-compose.
Lars H: Composition of multivariate functions is considerably more complicated than composition of univariate functions. Univariate functions under composition form an algebraic structure known as a semigroup, which is fairly easy. The corresponding algebraic structure for multivariate functions under composition is known as an operad, and already stating the axioms for that beast places one in a serious risk of drowning in indices.
It can actually be easier to begin with the next step generalisation, which is known as a PROP. (There is a formal definition in Section 2 of [L1 ], but unless you're familiar with category theory you probably won't get much out of it.) Informally, the elements of a PROP can be viewed as functions with an arbitrary number of inputs and an arbitrary number of outputs. (Normal functions only have one output.) If F and G are elements of a PROP and the number of inputs of F is equal to the number of outputs of G then one can form the composition FoG which will have the same number of outputs as F and the same number of inputs as G.
Besides compositions, one can also form the tensor product of two PROP elements F and G. If F has k inputs and l outputs, and G has m inputs and n outputs, then their tensor product will have k+m inputs and l+n outputs, of which the first k (and l, resp.) will go to F and the last m (and n, resp.) come from G.
The subset of a PROP consisting of all elements with precisely one output is an operand.
(TV Well, composition of single variate functions is a bit limited, it's just putting functions on a row, not much more to be said about, the execution order is fixed, and transformations on the result aren't possible unless the functions are quite special. Useful though, of course.)
RS 2005-04-04: Years later, I like simple code better - today I'd write composition of two functions (the typical use case) like this:
proc o {f g x} {$f [$g $x]}This needs hardly any explanation, I'd say, as it just implements the spec pretty literally. For usage example, here's good old factorial:
interp alias {} factorial {} o product iota1See Functional Programming for the details :)
gold 10/11/2020. Added appendix below, but original source code and text above was unchanged.
Please place any comments here, Thanks.
| Category Numerical Analysis | Category Toys | Category Calculator | Category Mathematics | Category Example | Toys and Games | Category Games | Category Application |