[PN] 2007.10.20 This page is dedicated to Knuth sections 7.2.1.1 and 7.2.1.2 All the routines on this page generate a sequence of objects, so they are all objects of an iterative type. An ''iterate'' type provides for 3 basic functions, ''init'', ''next'' and ''more''. ''init'' gets things rolling and returns the first value in the sequence. ''next'' gives you the next value in the sequence or an invalid value ''more'' tells you if the last value you just got with ''init'' or ''next'' is a valid value or not. Typically a value of an empty list is the standard invalid value. Because all these routines return a sequence of values which mean something in relation to each other, the empty list {} is never a valid returned value. However in some cases {{}},the empty set, may be returned as a valid value. The ''iterate'' command returns a handle to an interative type of the kind that you have requested in the command. There is a seemingly endless variety of these as this page will demonstrate. The handle is ''it'' followed by a self appointed number, e.g. ''it4''. This handle is an iterative object and is typically invoked in this way: set o [iterate ....] for {set i [$o init]} {[$o more]} {set i [$o next]} { do something with $i } "type delete" $o When you are iterating a number of sequences in the same program this form of expression is easier to use than the namespace version. Because they all have the same ''init'', ''next'' and ''more'' commands, the commands have to be disambiguated by using the object name all the time. Therefore these iterative objects have been implemented in the form of something I call a '''type'''. A type consists of a namespace for the object, plus, in the case of these iterative types, the 3 commands implemented as object procedures: "$o init", "$o next" and "$o more". To avoid having to use quotes everywhere the '''[["type create"]]''' command makes these availbale at a more readable level. The contents of the namespace remains private. The '''[[iterate]]''' command uses '''[["type create"]]''' inside it as part of creating the iterative object. For now I have decided not to have the objects self-destruct when they have completed their tour of duty, just in case the user wants to start them from the begining again. So for now the user is responsible for destroying the object. You do this using the '''type delete''' command as seen above. This deletes the namespace ''::$o'', the command ''$o'' which was created by '''[["type create"]]''' and the commands '''[["$o *"]]'''. Some of these iterative objects could have a '''[[prev]]''' and a '''[[less]]''' command as well but in the interests of brevity I have not included these. The iterative objects are designed to be able to be restarted by invoking '''[[init]]''' again, but '''they are not reentrant'''. This means you cannot be in two different places at once within the one object. Most of the iterative objects have been implemented using list structures instead of arrays as these appeared to be the most efficient. However, I was bemused to discover that [[lset]] was no improvement on the old [[lreplace]] and appeared marginally slower much of the time, but [[lset]] is more readable, so I have used [[lset]]. To begin, here are the [[type]] commands. I have not to applied '''[["type create"]]''' to '''type''' itself, though this is valid and would make type into a universal metaobject. '''[["type create"]]''' is not used much and is usually hidden inside something else. '''[["type delete"]]''' is easy enough to type the few times you need it. I also choose not to type '''[[type]]''' because this name is probably polluted enough already. In [TOOT] this same '''[["type create"]]''' command is used to replace the ''''[[unknown]]''' command. This has the effect of making everything potentially typed. I choose not to do this because I like to have more control over what is typed and what isn't. Also I already reuse '''[[unkown]]''' to '''expand''' the inital command word (instead of compacting the first two words which is the intention of [["type create"]]) so as to enable currying within lambda expressions. If you try to do both without careful structure you can end up in a curry/type loop, forever expanding and contracting the command word. proc "type create" t { set str " proc $t {cmd args} { set p \"$t \$cmd\"" append str { if { [ info proc $p ] == {} } { global errorInfo error "No proc: $p" $errorInfo return } uplevel 1 [ linsert $args 0 $p ] } append str " }" eval $str } proc "type delete" t { namespace delete $t foreach i [info proc "$t *"] {rename $i {} } rename $t {} } I keep these two routines in my personal '''lambda''' package which includes other essential items like: proc {} {} {} and '''[[set-]]''' the uncomplaining [[set]]. ---- '''[[iterate count''' ''radix length'' ''']]''' Useage: iterate count 2 5 This is the basic counting routine, but implemented as a list with the 0 index changing the most frequently, which is the reverse of the usual numer system paradigm. Both ''radix'' and ''length'' are both integhers. They should be >= 2. I have included a time check, though I am unsure what the best protocol is for handling this. In a more verbose version of the routine, a check could be made for tk and a continue/cancel dialogue box posted. [[count]] doesnt need a private namespace. "type create" iterate proc "iterate count" {radix length} { # get an object name for {set i 0} { [info proc ::it$i] != {} } { incr i} {} "type create" [set obj it$i] set cb \] if { $radix < 2 || $length < 2} { error "Iterate count radix and length must both be greater than 2" return } # roughly 1,000,000 iterations per minute if { [set i [expr $length*log10($radix)-6]] > 1 } { puts "iteration will take roughly [expr round(pow(10,$i))] minutes" } set str " namespace eval ::$obj { variable curr }" eval $str set str " proc \"$obj init\" {} { return \[set ::${obj}::curr [list [string repeat "0 " $length ]] $cb }" eval $str set str " proc \"$obj more\" {} { return \[expr {\$::${obj}::curr != {} } $cb }" eval $str set str " proc \"$obj next\" {} { for {set i 0} {\$i < $length } {incr i} { if { \[set j \[lindex \$::${obj}::curr \$i $cb$cb < [expr $radix -1] } { return \[lset ::${obj}::curr \$i \[expr \$j +1$cb$cb } else { lset ::${obj}::curr \$i 0 } } return \[set ::${obj}::curr {} $cb }" eval $str return $obj } The important special case is radix=2 for a binary list. The '''[[next]]''' command could be fine-tuned for this special case. In the binary case the result can be used as a mask over another list of any kinds of objects to step through the elements of a powerset over the objects: proc mask {set mask} { set p [list] foreach i $set m $mask { if { $m != 0 } {lappend p $i} } return $p } Creating a special powerset iterative object is more trouble than it is worth. It is simpler to use something like the following: set a { feet shod soft press grass } set o [iterate count 2 [llength $a]] for { set i [mask $a [$o init]]} {[$o more]} {set i [mask $a [$o next]]} { puts $i } "type delete" $o It would be better to create a functional object which operates on iterative objects. ---- '''Binary Gray''' '''[[iterate gray''' ''length'' ''']]''' Usage: iterate gray 26 Gray Code is a form of enumeration where only one digit changes with each invocation. '''[[iterate gray]]''' iterates binary numbers in standard Gray order. This is Knuth 7.2.1.1 Alg G proc "iterate gray" length { # get an object name for {set i 0} { [info proc ::it$i] != {} } { incr i} {} "type create" [set obj it$i] set cb \] set str " namespace eval ::$obj { variable curr variable parity 0 }" eval $str set str " proc \"$obj init\" {} { set ::${obj}::parity 0 return \[set ::${obj}::curr [list [string repeat "0 " $length ]] $cb }" eval $str set str " proc \"$obj more\" {} { return \[expr {\$::${obj}::curr != {}} $cb }" eval $str set str " proc \"$obj next\" {} { if { \$::${obj}::curr == {} } { return {}} set ::${obj}::parity \[expr {1 - \$::${obj}::parity} $cb if { \$::${obj}::parity == 1 } { set j 0 } else { for { set j 1 } { \[lindex \$::${obj}::curr \[expr \$j -1 $cb $cb == 0 } { incr j} {} } if { \$j == $length } { return \[set ::${obj}::curr {} $cb } return \[lset ::${obj}::curr \$j \[expr {1 -\[lindex \$::${obj}::curr \$j $cb } $cb$cb }" eval $str return $obj } set o ["iterate gray" 5] for { set i [$o init] } { [$o more]} {set i [$o next]} { puts $i } "type delete" $o ---- The next iterator is the "Loopless Gray" from Knuth 7.2.1.1 Alg L. This uses extra housekeeping to run a bit faster. proc "iterate looplessGray" length { for {set i 0} { [info proc ::it$i] != {} } { incr i} {} "type create" [set obj it$i] set cb \] set str " namespace eval ::$obj { variable curr variable f }" eval $str set str " proc \"$obj init\" {} { for {set i 0} {\$i <= $length } {incr i} {set ::${obj}::f(\$i) \$i } return \[set ::${obj}::curr [list [string repeat "0 " $length ]] $cb }" eval $str set str " proc \"$obj more\" {} { return \[expr {\$::${obj}::curr != {}} $cb }" eval $str set str " proc \"$obj next\" {} { if { \$::${obj}::curr == {} } { return {}} set j \$::${obj}::f(0) set ::${obj}::f(0) 0 if { \$j >= $length } { return \[set ::${obj}::curr {} $cb } lset ::${obj}::curr \$j \[expr { 1 -\[lindex \$::${obj}::curr \$j $cb } $cb set ::${obj}::f(\$j) \$::${obj}::f(\[incr j $cb) set ::${obj}::f(\$j) \$j return \$::${obj}::curr }" eval $str return $obj } time { set o ["iterate looplessGray" 15] for { set i [$o init] } { [$o more]} {set i [$o next]} { } "type delete" $o } 10