nested loops
Russell Trleleaven
for a long time I have been writing test automation scripts that are
basically a bunch of nested loops to iterate over combinations of things
and test the permutations.
Given the example below
Is there a better way to express this than nested loops.
Possibly a recursive function.
I tried to write something but it got real ugly real quick.
Also I believe that there is a limit to the number of recursions but I
don't know what it is.
#example
set flowControls [ list on off ]
set pllms [ list on off ]
set modulations [ list 7 6 5 4 3 2 1 0 ]
set channelWidths [ list 40 20 10 ]
set modes [ list 2 1 0 ]
foreach flowcontrol $flowControls {
foreach pllm $pllms {
foreach modulation $modulations {
foreach channelWidth $channelWidths {
foreach mode $modes {
test $flowcontrol \
$pllm \
$modulation \
$channelWidth \
$mode
}
}
}
}
}
Neil Madden
> Hi,
>
> for a long time I have been writing test automation scripts that are
> basically a bunch of nested loops to iterate over combinations of things
> and test the permutations.
> Given the example below
> Is there a better way to express this than nested loops.
> Possibly a recursive function.
> I tried to write something but it got real ugly real quick.
> Also I believe that there is a limit to the number of recursions but I
> don't know what it is.
There is a recursion limit in each interpreter. You can configure it in
newer versions of Tcl, but it's still a fixed limit.
> #example
> set flowControls [ list on off ]
> set pllms [ list on off ]
> set modulations [ list 7 6 5 4 3 2 1 0 ]
> set channelWidths [ list 40 20 10 ]
> set modes [ list 2 1 0 ]
> foreach flowcontrol $flowControls {
> foreach pllm $pllms {
> foreach modulation $modulations {
> foreach channelWidth $channelWidths {
> foreach mode $modes {
> test $flowcontrol \
> $pllm \
> $modulation \
> $channelWidth \
> $mode
> }
> }
> }
> }
> }
There's nothing wrong with using nested loops, of course, but reducing
the nesting could improve the readability. I can think of two ways to
go. Firstly, write a procedure to generate all the combinations and then
use foreach:
foreach {flowcontrol pllm ...} \
[combinations $flowControls $pllms ...] {
...
}
Or create a custom control structure just for this:
foreach-combination flowcontrol $flowControls \
pllm $pllms ... {
...
}
The advantage of the latter is that you only have to generate the
combinations as they are required, so if you exit the loop early using
[break] or an error then you haven't spent time computing unneeded
computations. Given that rationale, here's an implementation:
proc foreach-combination args {
set body [lindex $args end]
foreach {var ops} [lrange $args 0 end-1] {
set body [list foreach $var $ops $body]
}
uplevel 1 $body
}
-- Neil
Jonathan Bromley
wrote:
Seems to me that you need a proc. that can accept any number of
variable/list pairs, and does the "nested foreach" thing for you
automatically. Something like this:
foreach_nested var1 list1 var2 list2 ..... varN listN {script}
And since you are doing some testing in {script}, which I imagine
will take a little while, it probably doesn't matter too much
how (in)efficient the implementation of [foreach_nested] might be.
So it would be easy enough to make it recursive. Something like
this (comments and criticisms welcomed):
proc foreach_nested {args} {
# check that args has an odd number of elements
if {([llength $args] % 2) == 0} {
error "foreach_nested: wrong number of args"
}
# Check to see if we've reached the bottom of the recursion.
if {[llength $args] == 1} {
# If so, just execute the script.
uplevel 1 [lindex $args 0]
} else {
# More looping to do.
upvar 1 [lindex $args 0] v
foreach v [lindex $args 1] {
uplevel 1 foreach_nested [lrange $args 2 end]
}
}
}
Try it out thus:
foreach_nested a {1 2 3} b {A B} c {4 5} {puts "$a $b $c"}
I don't think you'll run out of stack-limit for any
realistic situation.
Sheesh, I LOVE Tcl :-)
--
Jonathan Bromley, Consultant
DOULOS - Developing Design Know-how
VHDL * Verilog * SystemC * e * Perl * Tcl/Tk * Project Services
Doulos Ltd., 22 Market Place, Ringwood, BH24 1AW, UK
jonathan...@MYCOMPANY.com
http://www.MYCOMPANY.com
The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.
suchenwi
> Also I believe that there is a limit to the number of recursions but I
> don't know what it is.
As usual in Tcl, this is quite easily found out:
% proc f x {puts $x; f [incr x]}
% f 1
1
2
3
...
871
872
873
too many nested evaluations (infinite loop?)
%
That's on Win XP, Tcl 8.4.1 (sic)
Uwe Klein
#/usr/bin/tclsh
package require Tclx
proc permloop {level script singlearg arglist } {
lappend script $singlearg
if {0 == [llength $arglist]} {
# puts stderr "finished : $script"
uplevel $level [if 1 $script]
} else {
set items [lvarpop arglist]
foreach singlearg $items {
permloop $level $script $singlearg $arglist
}
}
}
proc permute {format args} {
set level [ uplevel info level ]
set script [ list format $format ]
set items [ lvarpop args ]
foreach singlearg $items {
permloop $level $script $singlearg $args
}
}
set itemA {a b c d e f}
set itemB {A B C D E F}
set itemC {1 2 3 4 4 5}
permute {puts "TEST: A:%s B:%s c:%s"} $itemA $itemB $itemC
uwe
M. Strobel
Hi Neil, Jonathan, Richard, Uwe,
just a spontaneous idea: might an "obfuscated tcl contest" be a good
idea? ;-)
Honestly, I find the original code far more readable.
Max
sleb...@gmail.com
wrote:
Seriously? More readable than:
Uwe Klein
>
> Honestly, I find the original code far more readable.
>
> Max
in a script you would only see this:
set itemsA {a b c d e f}
set itemsB {A B C D E F}
set itemsC {1 2 3 4 4 5}
permute {puts "TEST: A:%s B:%s c:%s"} $itemsA $itemsB $itemsC
uwe
M. Strobel
Jonathan and Uwe,
you gave me both the same reaction, and yes, the call to the testproc
looks fine.
But then I said *the code*, and reading the proposed code parts I
thought: hey, evolution goes to the more sophisticated, this is fun.
Where will it end?
Max
Bruce Hartweg
Actually, combine would be a 'better' name than permute ;)
Bruce
Bruce Hartweg
yes putting into a proc makes the top level script cleaner/easier
*but* looking at the implementation of that proc, I would leave it
as a set of nested loops than forcing it into a recursive mess.
For problems that are recursive in nature recursion is nice, for
problems that are iterative in nature for loops are better.
Bruce
Neil Madden
...
> Jonathan and Uwe,
>
> you gave me both the same reaction, and yes, the call to the testproc
> looks fine.
>
> But then I said *the code*, and reading the proposed code parts I
> thought: hey, evolution goes to the more sophisticated, this is fun.
> Where will it end?
This is the nature of abstraction. When you read that part of the code,
all you will see is the
foreach-combination ... { ... }
bit (or whatever), which is nice and clear and to the point. The
implementation (which can be as complex as you like) can be put in some
completely different file, far far away from sensitive eyes. Besides, I
think *my* contribution also has a rather neat implementation :-)
proc foreach-combination args {
set body [lindex $args end]
foreach {var ops} [lrange $args 0 end-1] {
set body [list foreach $var $ops $body]
}
uplevel 1 $body
}
Arguably, that's even shorter and less complex than the original nested
loops.
-- Neil
Bruce Hartweg
yep - an inline code generator - nicely done.
Bruce
sleb...@gmail.com
wrote:
> slebet...@yahoo.com schrieb:
First off, I'm not Jonathan. My nick on the internet is slebetman (so
far there is only one slebetman on the internet on any newsgroup or
forum). My real name is Adly.
> you gave me both the same reaction, and yes, the call to the testproc
> looks fine.
>
> But then I said *the code*,
But the "call" IS the code. Think of it as a new control structure
like while, for or foreach. Indeed, Jonathan's foreach_nested
maintains so much of the semantics of foreach that it looks natural in
tcl. To illustrate:
# regular foreach, doesn't do the same thing but
# just wanted to show the similarity of syntax:
foreach a {1 2 3} b {A B} c {4 5} {
puts "processing: $a $b $c"
process $a $b $c
}
# foreach_nested, foreach with simple premutation:
foreach_nested a {1 2 3} b {A B} c {4 5} {
puts "processing: $a $b $c"
process $a $b $c
}
The "implementation" may be messy but even here Jonathan's
implementation of [foreach_nested] is surprisingly clean and easy to
read. But then again the implementation of other commands we take for
granted are equally or even more messy, [http::geturl] or
[fileutil::foreachLine] for example.
Artur
> Possibly a recursive function.
If you are seriously interested about recursion
get a look into a book:
How to design programs
http://www.htdp.org
It is about functional language Scheme but it is very good.
(see chapter about lists)
Standard sample with foreach
proc map list {
foreach a $list {
foo $a
}
}
with recusive proc
proc maprek list {
if {[llength $list]>0} {
# proc first element
foo [lindex $list 0]
# handle the rest of list with self-call
maprek [lrange $list 1 end]
}
}
Recursion is the first method to solve problems in many languages
(Lisp, Scheme, Haskell, ...)
Tcl does not offer so called tail-end recursion optimization so it is
quite
expensive and not fast (every call needs extra memory)
But recursion is also very usable in Tcl to traverse recursive
structures (for example trees)
or to define some complex operations so it is quite usable to know
about it.
Artur
iu2
...
> There is a recursion limit in each interpreter. You can configure it in
> newer versions of Tcl, but it's still a fixed limit.
>
This is a little bit off the subject, but I'm quite surprised by that.
I've always assumed that one of the (many) advantages of a scripting
language over C, for example, is recursion (dynamic stack, or scope) -
you don't have to worry about exceeding the stack.
1. Is there any plan to change that for tcl?
2. Is there a way to change the limit from tcl?
Thanks
Christian Gollwitzer
>>There is a recursion limit in each interpreter. You can configure it in
>>newer versions of Tcl, but it's still a fixed limit.
> I've always assumed that one of the (many) advantages of a scripting
> language over C, for example, is recursion (dynamic stack, or scope) -
> you don't have to worry about exceeding the stack.
There is no such limit in "C". Maybe some broken Windows implementations
like VC6 have problems with fixed stack sizes, but on Linux you can
recurse until all memory is eaten up (or you hit the limit set by
"ulimit" to prevent a broken program to bring down the system).
Christian
Jonathan Bromley
Neil Madden <n...@cs.nott.ac.uk> wrote:
>I think *my* contribution also has a rather neat implementation :-)
> proc foreach-combination args {
> set body [lindex $args end]
> foreach {var ops} [lrange $args 0 end-1] {
> set body [list foreach $var $ops $body]
> }
> uplevel 1 $body
> }
I entirely agree, but there are two things about it that
a user might find counter-intuitive:
* the first var/list pair is scanned fastest, isn't it?
* the behaviour of [break] and [continue] in the body
might be somewhat surprising (unless you really
wanted the effect of a bunch of nested [foreach]).
In response to Bruce Hartweg:
> For problems that are recursive in nature recursion
> is nice, for problems that are iterative in
> nature for loops are better.
I have absolutely no shame about using a recursive
implementation to an iterative problem, if it makes
my life easier! Not only are recursive solutions
often easier to code, but I usually find them
easier to reason about than iterative solutions -
especially if the number of nested iterations is
not known in advance.
sleb...@gmail.com
wrote:
> slebet...@yahoo.com schrieb:
> > Seriously? More readable than:
>
> > <jonathan.brom...@MYCOMPANY.com> wrote:
> >> foreach_nested a {1 2 3} b {A B} c {4 5} {puts "$a $b $c"}
>
> Jonathan and Uwe,
First off, I'm not Jonathan.
> you gave me both the same reaction, and yes, the call to the testproc
> looks fine.
>
> But then I said *the code*, and reading the proposed code parts I
> thought: hey, evolution goes to the more sophisticated, this is fun.
> Where will it end?
>
But the "call" IS the "code". Or are you one of those people who also
insist on reading the source for [http::geturl] before using it?
Nothing wrong with reading the implementation of course. IIRC
Fredderic even likes to read Tcl's C sources to figure out what
commands like [source] actually does.
Think of it as a new control structure (which it is) instead of simply
a function. Jonathan's foreach_nested is similar enough to foreach
that it even looks natural in Tcl. To illustrate the similarity:
# foreach:
foreach a {1 2 3} b {A B} c {4 5} {
puts "processing $a $b $c"
process $a $b $c
}
# foreach with premutation:
foreach_nested a {1 2 3} b {A B} c {4 5} {
Neil Madden
> On Tue, 24 Apr 2007 15:13:44 +0100,
> Neil Madden <n...@cs.nott.ac.uk> wrote:
>
>> I think *my* contribution also has a rather neat implementation :-)
>> proc foreach-combination args {
>> set body [lindex $args end]
>> foreach {var ops} [lrange $args 0 end-1] {
>> set body [list foreach $var $ops $body]
>> }
>> uplevel 1 $body
>> }
>
> I entirely agree, but there are two things about it that
> a user might find counter-intuitive:
> * the first var/list pair is scanned fastest, isn't it?
Yes. That is easily fixed if you care about the order in which
combinations are tried:
foreach {ops var} [lreverse [lrange $args 0 end-1]] { ... }
> * the behaviour of [break] and [continue] in the body
> might be somewhat surprising (unless you really
> wanted the effect of a bunch of nested [foreach]).
This is potentially more serious. It is a problem with all the solutions
given, though, not just mine. Note that [continue] works fine, it's just
[break] that may be a problem. Given that the code is replacing an
existing set of nested loops (which therefore have the exact same
behaviour), it's a minor concern. However, if you really want this, it's
not too much more difficult:
proc foreach-comb args {
set body [lindex $args end]
foreach {ops var} [lreverse [lrange $args 0 end-1]] {
set body [list foreach $var $ops $body]
}
proc break {} { return -code 9999 }
set rc [catch { uplevel 1 $body } res ops]
proc break {} { return -code break }
if {$rc == 9999} { return } else { return -options $ops $res }
}
-- Neil
Neil Madden
...
> proc foreach-comb args {
> set body [lindex $args end]
> foreach {ops var} [lreverse [lrange $args 0 end-1]] {
> set body [list foreach $var $ops $body]
> }
> proc break {} { return -code 9999 }
> set rc [catch { uplevel 1 $body } res ops]
> proc break {} { return -code break }
> if {$rc == 9999} { return } else { return -options $ops $res }
> }
Replying to myself, but it occurred to me that there already exist good
solutions to this on the wiki, for labelled break statements:
http://wiki.tcl.tk/3402 . Using my version from there, you can keep the
original short version of foreach-comb and just do:
block out: foreach-comb a {A B C} b {1 2 3 4} {
if {$a eq "B"} { break out: }
puts "$a $b"
}
-- Neil
sleb...@gmail.com
> <Multiple similar posts>
Crap, looks like google was having some problems. I'm sorry for the
multiple posts unfortunately from work the web is the only access I
get.
Darren New
> There is no such limit in "C".
Actually, it's undefined in C. There are many C implementations with
small stacks.
> (or you hit the limit set by
> "ulimit" to prevent a broken program to bring down the system).
Wow. I'd rather have a known fixed-size limit than have bugs bring down
the system. ;-)
--
Darren New / San Diego, CA, USA (PST)
His kernel fu is strong.
He studied at the Shao Linux Temple.
sleb...@gmail.com
> On Apr 24, 2:51 am, Neil Madden <n...@cs.nott.ac.uk> wrote:
> ...> There is a recursion limit in each interpreter. You can configure it in
> > newer versions of Tcl, but it's still a fixed limit.
>
> I've always assumed that one of the (many) advantages of a scripting
> language over C, for example, is recursion (dynamic stack, or scope) -
"C", the language, doesn't have a stack limit. Your OS on the other
hand may or may not implement one. Indeed one of the *improvements* in
Tcl compared to C is the introduction of the recursion limit so that a
buggy program is less likely to take down the system (it can still be
done but there is one less vector to do it in).
> you don't have to worry about exceeding the stack.
This is exactly why the stack limit is implemented so that even if you
DO have a rouge program that may exceed the stack limit you're still
safe.
> 1. Is there any plan to change that for tcl?
Probably not for the reasons stated above.
> 2. Is there a way to change the limit from tcl?
Yes:
# Find out current recursion depth:
puts [interp recursionlimit {}]
# Change recursion depth to 2000
interp recursionlimit {} 2000
Though it should be noted that that the man page says:
The command sets the maximum size of the Tcl call stack only. It
cannot by itself prevent stack overflows on the C stack being used by
the application. If your machine has a limit on the size of the C
stack, you may get stack overflows before reaching the limit set by
the command. If this happens, see if there is a mechanism in your
system for increasing the maximum size of the C stack.
M. Strobel
Shure this is the newsgroup of the experts, and the goal is short code
for a complex task.
I'm looking at it from a pedagogic point of view, where this code would
be challenging for the instructor, and possibly deterrent for the
participants. Pedagogical point of views seem to be fallow ground in tcl.
Or am I still shocked by the one who said binding an event proc to
focusin and focusout of an entry widget is too difficult...
Max
M. Strobel
I apologize, slebetman. Maybe we just omit the names until having
finished the first bottles of beer.
>> you gave me both the same reaction, and yes, the call to the testproc
>> looks fine.
>>
>> But then I said *the code*,
>
> But the "call" IS the code.
Not an important point, but to be precise IMHO we are actually comparing
the implementation.
Max
Donal K. Fellows
> Though it should be noted that that the man page says:
>
> The command sets the maximum size of the Tcl call stack only. It
> cannot by itself prevent stack overflows on the C stack being used by
> the application. If your machine has a limit on the size of the C
> stack, you may get stack overflows before reaching the limit set by
> the command. If this happens, see if there is a mechanism in your
> system for increasing the maximum size of the C stack.
We try very hard to detect when we would otherwise blow up because of
exceeding the end of the stack (this is *hard*, especially if you want
to do so with some semblance of portability). Also note that Tcl 8.5 can
go much deeper than Tcl used to be able to (assuming you turn up the
depth limit, of course) since it now puts a lot less data on the C stack
than it used to. This was (largely) enabled by Miguel Sofer's work on
re-engineering the bytecode engine's workspace, and the rest critically
depends on knowing what code is reentrant. It also always assumes that
the heap is bigger than the stack; good thing that's true. :-)
Donal (testing whether posting directly via work gets to the outside world.)
Jonathan Bromley
<yykon...@maxstrobelyyy.deyy> wrote:
>I'm looking at it from a pedagogic point of view,
Most of the time, so am I - that's my job :-)
> where this code would
>be challenging for the instructor, and possibly deterrent for the
>participants.
Really? I don't see why either my or Neil's implementations
are anything other than a non-trivial example of the use of
[uplevel] to create new control constructs. In our course
we present [uplevel] as a solution to how you could write
your own bottom-test loop in Tcl, providing the new command:
do {script} while {condition}
but the nested-foreach thing would perhaps be a nice
second step.
I would be fascinated to know how you would implement
[foreach-combination] (or whatever you like to call it)
in a way that meets the need of a user - make it look like
a nice built-in Tcl command - and also satisfies your
criteria for clarity of the implementation.
> Pedagogical point of views seem to be fallow ground in tcl.
Maybe. I'm not sure I agree. There is plenty of good
published and Web material, and some brilliant advice
available here - I've been grateful for it many times.
It's perhaps a little scattergun, but the quality is
excellent.
>Or am I still shocked by the one who said binding an event proc to
>focusin and focusout of an entry widget is too difficult...
If you want to be *shocked* by a newsgroup, c.l.t is the wrong
place to go... everyone's entitled to their opinion about
what's difficult (as, indeed, this thread shows).
sleb...@gmail.com
wrote:
> slebet...@yahoo.com schrieb:
> >> But then I said *the code*,
>
> > But the "call" IS the code.
>
> Not an important point, but to be precise IMHO we are actually comparing
> the implementation.
>
To be even more percise, at the point I was replying we were not yet
seriously talking about comparing implementation so it IS an important
point. In fact, for what I was replying it IS the point. I was
replying to the comment: "I find the original code far more readable".
Google, unfortunately being google delayed my post.
sleb...@gmail.com
wrote:
> Neil Madden schrieb:
>
> > M. Strobel wrote:
> > ...
> >> Jonathan and Uwe,
>
> >> you gave me both the same reaction, and yes, the call to the testproc
> >> looks fine.
>
> >> But then I said *the code*, and reading the proposed code parts I
> >> thought: hey, evolution goes to the more sophisticated, this is fun.
> >> Where will it end?
>
> > This is the nature of abstraction. When you read that part of the code,
> > all you will see is the
>
> > foreach-combination ... { ... }
>
> > bit (or whatever), which is nice and clear and to the point. The
> > implementation (which can be as complex as you like) can be put in some
> > completely different file, far far away from sensitive eyes. Besides, I
> > think *my* contribution also has a rather neat implementation :-)
>
> > proc foreach-combination args {
> > set body [lindex $args end]
> > foreach {var ops} [lrange $args 0 end-1] {
> > set body [list foreach $var $ops $body]
> > }
> > uplevel 1 $body
> > }
>
> > Arguably, that's even shorter and less complex than the original nested
> > loops.
>
> for a complex task.
>
> I'm looking at it from a pedagogic point of view, where this code would
> be challenging for the instructor, and possibly deterrent for the
> participants.
I don't understand. What, exactly, is challenging? Tcl is one of the
clearest language to read since it says exactly what it does. Let's
take Neil's code for example:
> > proc foreach-combination args {
Here even the proc name is instructional. It's a foreach like control
structure.
> > set body [lindex $args end]
The code "body" of this foreach-like command is the last argument
supplied. See the nice self-documenting "end" index?
> > foreach {var ops} [lrange $args 0 end-1] {
The remaining arguments in $args, from 0 to end-1, are key-value pairs
in the form {variable_name value_list} (admittedly "ops" is a bad name
for this, I would have used {var val} instead).
> > set body [list foreach $var $ops $body]
> > }
Consturct a nested foreach loop for each {var ops} pair we find.
Unclear? well..
> > [list ...]
is just quoting, the code we're constructing looks like: "foreach $var
$ops $body". Now that we have wrapped $body in a foreach and stored it
in a string (actually a list at the moment since we've used the [list]
command to quote) we store it back in the variable $body. We keep
doing this, wrapping $body in a foreach loop, again and again until
we've run out of {var ops} pairs. Do you see what's happening? We're
constructing the original nested foreach in code rather than type them
by hand!
> > uplevel 1 $body
> > }
After constructing the code, execute it in the caller's context
thereby making it behave like a control structure rather than a
function.
> Pedagogical point of views seem to be fallow ground in tcl.
The code above is highly instructional in demonstrating several very
Tclish concepts:
- data is or can be code and code is data
- modify the language (in this case introduce a new control structure)
to suit your problem rather than describing the problem in the
language.
- automatic "end" index for lists (it's documented but beginners may
not notice it)
- tcl's foreach can do lots of funky things (again documented but may
not be noticed at first)
- the use of $args
To top it off, Neil's code is very simple to understand and would not
be considered challenging at all to someone who is a Tcl instructor.
Challenging to beginners yes but certainly not to an instructor unless
the instructor himself is just a beginner (of course, I've been to
several courses where this is indeed the case).
Sean Woods
> Hi,
>
> for a long time I have been writing test automation scripts that are
> basically a bunch of nested loops to iterate over combinations of things
> and test the permutations.
> Given the example below
> Is there a better way to express this than nested loops.
> Possibly a recursive function.
> Also I believe that there is a limit to the number of recursions but I
> don't know what it is.
>
What I like to do is put all of the permutations into a list, and then
run in a single foreach loop.
> #example
> set flowControls [ list on off ]
> set pllms [ list on off ]
> set modulations [ list 7 6 5 4 3 2 1 0 ]
> set channelWidths [ list 40 20 10 ]
> set modes [ list 2 1 0 ]
proc permutate largs {
set result {}
set subs [lrange $largs 1 end]
if { $subs == {} } {
return [lindex $largs 0]
}
set block [permutate $subs]
set N [llength $block]
set L [llength $subs]
foreach val [lindex $largs 0] {
for {set x 0} {$x < $N} {incr x $L} {
eval lappend result $val [lrange $block $x [expr $x + $L -
1]]
}
}
return $result
}
set conditions [permutate $flowControls $plims $modulations
$channelWidths $modes]
foreach {flowcontrol plim modulation channelWidth mode] $conditions {
test $flowcontrol \
$pllm \
$modulation \
$channelWidth \
$mode
}
> foreach flowcontrol $flowControls {
> foreach pllm $pllms {
> foreach modulation $modulations {
> foreach channelWidth $channelWidths {
> foreach mode $modes {
> > }
> }
> }
> }
>
> }