Discussion page for [L1 ], a proposal for Higher Order Functions in Tcl that is intended to result in a TIP.
escargo 15 Apr 2010 - There appears to be some damage to the page in the reference link. One heading is tr;dr. Headings for "Introduction, Motivation and Goals," "A review of FP and higher order functions in Tcl," and "The design of this proposal" appear to be missing.
One feature of the design of the proposal is described like this:
filter predicate list is a filter over a list, and predicate is a cmdprefix that must return a boolean.
This is somewhat imprecise in that Tcl does not have a boolean data type. More firmly specified would be to say that cmdprefix must return 0 or 1.
The discussion about optional arguments would be clarified if the distinction between formal arguments and actual arguments were more clearly drawn.
While proponents of functional programming might know about left fold and right fold an explanatory reference for the rest of us would be welcome.
Twylite 2010/04/16: No damage; the "missing" headings are external links. I have updated the doc to make this more readily apparent (I hope).
The concept of a "boolean" is defined in the man page for if - I have updated the doc to refer to this definition.
Thanks for the comments on the "optional arguments" proposal. I will improve this proposal in time; it will not form part of the Higher Order Functions TIP and should probably be a TIP in its own right. The idea is rather rough at the moment but I wanted to get it down and hear some opinions.
The tl;dr is deliberately brief, take a look at the manual (link is now more obvious, in the ToC) for more detail and a link to the Wikipedia.
Lars H: While I certainly agree with the proposal's philosophy that a command prefix should be considered the normal Tcl equivalent of an abstract function, I'm somewhat at a loss as to what the TIP is supposed to actually propose. The whole thing just looks like a collection of observations.
Twylite 2010/04/16 Fair point. The TIP will do two things:
The doc has been updated to indicate this (at the top of the tl;dr).
The rationale for including these commands in the core is given in the Introduction, Motivation and Goals section.
Twylite 2010/04/16 Andreas Kupries made a point that this proposal does not support infinite lists. That is true. I experimented with [coforeach] and [cofoldl] implementations, and decided that two paradigm shifts (functional programming, and iterators instead of lists) would be going too far in Tcl 8.x. The fold/map/filter constructs for Tcl 8.x should support the familiar data types of Tcl 8.x, i.e. finite lists. There have been some discussions about moving towards an iterator approach in Tcl 9, which would be an appropriate time to make the higher-order functions iterate over infinte lists.
Put another way, I see it as the job of another TIP to propose [coforeach], [cofoldl] and friends that accept iterators (as coroutines the yield values) rather than lists. It would also make sense to have an [iterator] helper to iterate over lists, making the following two statements equivalent in function:
foreach element $list { ... }
coforeach element [iterator $list] { ... }Tcl 9 proposals to remove the command/variable dichotomy could further simplify the syntax.
dkf - 2010-04-16 04:22:07
I want a map that supports the full power of foreach. Why? Because it will also allow us to do
What's more, we don't need any new bytecodes to do this efficiently. It's essentially just reusing the machinery we already have for foreach, but keeping the value from each time round the loop (on normal result).
AMG: What about the crazy foreach+Python hybrid list/dict/whatever comprehension I posted [L2 ]? By the way, mixing short-circuit evaluation with continue is very clever. ;^)
Twylite 2010/04/16 Hmmm, so a capturing [foreach] that assigns values to variables and evals a block, rather than something that invokes a function with arguments. Out of scope for this proposal ;p
Very cute though; this would provide list comprehension functionality in a construct that is familiar to Tclers.
So I will see your [map], and raise you multiple output elements per iteration:
proc mapfor {args} {
set coro ::__mapfor_[incr ::__mapfor_id]
set a [coroutine $coro foreach {*}$args]
set out [list]
while { ($a ne {}) || [llength [info commands $coro]] } {
lappend out $a
set a [$coro]
}
return $out
}
# Return multiple output elements per iteration
% mapfor a {1 2 3 4 5} { yield [expr { $a * 2 }] ; yield x }
2 x 4 x 6 x 8 x 10 x
# Zipping
% set list1 {1 2 3 4 5 6}
% set list2 {a b c d e f}
% set zipped [mapfor a $list1 b $list2 {yield [list $a $b]}]
{1 a} {2 b} {3 c} {4 d} {5 e} {6 f}
# Consuming several values at once
% set sums [mapfor {a b} $list1 {yield [::tcl::mathop::+ $a $b] }]
3 7 11
# Filtering
% proc isEven {x} { expr { $x % 2 == 0 } }
% set goodOnes [mapfor x $list1 { yield [expr {[isEven $x] ? $x : [continue]}] }]
# Taking a prefix of the list
% proc isGood {x} { expr { $x < 4 } }
% set prefix [mapfor x $list1 { yield [expr {[isGood $x] ? $x : [break]}] }]
1 2 3
# Performance
% set values {}; for {set i 0} {$i < 1000000} {incr i} { lappend values $i }
% set out {} ; time { foreach i $values { lappend out [expr { $i * 5 }] } }
921000 microseconds per iteration
% time { mapfor i $values { yield [expr { $i * 5 }] } }
1828000 microseconds per iterationDKF: Oh wow! Neat, but the performance of mapfor becomes relatively worse when the iteration is done inside a procedure/lambda:
% time {apply {{} {
set out {} ;foreach i $::values {lappend out [expr {$i*5}]};return $out
}}}
4126981 microseconds per iteration
% time {apply {{} {
mapfor i $::values { yield [expr { $i * 5 }] }
}}}
33906295 microseconds per iterationThis is because foreach is significantly faster when there's a local variable context (that's because that lets the bytecode compiler kick in; it doesn't bother otherwise) and the trick with coroutine foreach defeats the compiler.
escargo 15 Apr 2010 - I'm looking at the control::functional page [L3 ].
It seems that either the metalanguage for describing optional arguments is insufficient or ambiguous.
How would range 1 be interpreted?
How would range 2 2 be interpreted?
Or is it "understood" that the third argument can only be present if the first two are present?
The way it looks to me, in the two-argument case, you can't tell if the first or the third argument is missing.
Twylite 2010/04/16 This is related to the idea of enhancing support for optional arguments, so that there is a common understanding of behaviour in this sort of situation.
Parameters (given by the caller) are assigned to arguments (vars in the arglist) from left to right (i.e. iterate over the argument vars and assign to each the next available parameter). If an optional argument is encountered and the number of available parameters remaining is less than or equal to the number of mandatory arguments that have not yet received a parameter value, then assign the default value to the optional arg (and don't consume a parameter).
Perhaps this is more succinctly stated by rephrasing your words: an optional argument can only be assigned a parameter if every optional argument to the left of it has been assigned a parameter.
In the case [range ?from? to ?step?]: