15.6.2.2297 TRAVERSE-WORDLIST TOOLS EXT

( i * x xt wid -- j * x )

Remove wid and xt from the stack. Execute xt once for every word in the wordlist wid, passing the name token nt of the word to xt, until the wordlist is exhausted or until xt returns false.

The invoked xt has the stack effect ( k * x nt -- l * x flag ).

If flag is true, TRAVERSE-WORDLIST will continue with the next name, otherwise it will return. TRAVERSE-WORDLIST does not put any items other than nt on the stack when calling xt, so that xt can access and modify the rest of the stack.

TRAVERSE-WORDLIST may visit words in any order, with one exception: words with the same name are called in the order newest-to-oldest (possibly with other words in between).

An ambiguous condition exists if words are added to or deleted from the wordlist wid during the execution of TRAVERSE-WORDLIST.

See:

A.15.6.2.2297 TRAVERSE-WORDLIST, 15.6.2.1909.40 NAME>STRING,
15.6.2.1909.20 NAME>INTERPRET, 15.6.2.1909.10 NAME>COMPILE.

Rationale:

Typical use:

: WORDS-COUNT ( x nt -- x' f ) DROP 1+ TRUE ;
0 ' WORDS-COUNT FORTH-WORDLIST TRAVERSE-WORDLIST .

prints a count of the number of words in the FORTH-WORDLIST.

: ALL-WORDS NAME>STRING CR TYPE TRUE ;
' ALL-WORDS GET-CURRENT TRAVERSE-WORDLIST

prints the names of words in the current compilation wordlist.

: CONTAINS-STRING
NAME>STRING 2OVER SEARCH IF CR TYPE THEN FALSE ;
S" COM" ' CONTAINS-STRING GET-CURRENT TRAVERSE-WORDLIST

prints the name of a word containing the string "COM", if it exists, and then terminates.

ContributeContributions

GerryJackson [19] TRAVERSE-WORDLIST is in the wrong word setComment2016-05-22 20:03:53

Despite TRAVERSE-WORDLIST being regarded as a programming tool it cannot be used or tested unless wordlists can be created which requires at least some of the words in the Search-Order word set. Therefore it belongs in the Search-Order word set.

AntonErtl [r22] 2016-05-24 13:27:38

Yes, the search order wordset might have been a better place. However, given that TRAVERSE-WORDLIST is in Forth-2012 is in the TOOLS wordset, and there is little point in changing that (given that we don't have wordset queries for Forth-2012, it has no effect on programming). Also, the NAME>... words from the same proposal have nothing to do with the search-order wordset; should we distribute the words from this proposal over several wordsets?

GerryJackson [r40] 2016-11-22 10:29:50

Ok but I don't see why the NAME>... words shouldn't also go in the Search-Order word set. They and TRAVERSE-WORDLIST are a family of words that belong together and wouldn't be much use without wordlists. Your argument could be used to exclude WORDLIST from the Search-Order wordset as it's only creating a wordlist not affecting the search order (I'm not seriously suggesting that).

AntonErtl [r41] 2016-12-08 09:38:00

Once we have FIND-NAME, NAME>... makes perfect sense without search order words.

As for the programming tools, it contains two sets of words: words like SEE that are normally used just for debugging and not used inside colon definitions (except for debugging purposes); and words like AHEAD that some in the Forth community consider unnecessary for application programming; NAME>... is in the latter category.

Reply New Version

ruv [118] Unfindable definitionsComment2019-09-20 23:23:52

If a definition is available via TRAVERSE-WORDLIST, can we say that it is findable in the dictionary?

Perhaps, for clarity, we should mention that unfindable definitions (e.g. not ended, or nameless, or quotations) shall not be available via TRAVERSE-WORDLIST. Otherwise, among other issues, SEARCH-WORDLIST cannot be correctly implemented via TRAVERSE-WORDLIST factor.

AntonErtl [r454] 2020-09-01 17:43:40

Addressed in this proposal.

Closed

Reply New Version

ruv [312] TRAVERSE-WORDLIST must not expose the current definitionSuggested Testcase2023-10-23 10:04:08

TRAVERSE-WORDLIST is not allowed to visit the current definition, unfinished or hidden definitions (see also the accepted proposal #153 Traverse-wordlist does not find unnamed/unfinished definitions).

Some systems place the current definition into the compilation word list and change its header in such a way that this definition cannot be found via FIND-NAME-IN or SEARCH-WORDLIST. By a mistake, nt for this definition can be exposed by TRAVERSE-WORDLIST.

This test ensured that the current definition is not exposed, and that the correct number of names is placed into the compilation word list.

: WORDLIST-LENGTH ( wid -- u )
  >R 0 [: DROP 1+ TRUE ;] R> TRAVERSE-WORDLIST
;
: L ( -- u ) GET-CURRENT WORDLIST-LENGTH ;

T{ L :NONAME [ L ] LITERAL ;  EXECUTE  L =  = -> TRUE }T

T{ L : TW1 [ L ] LITERAL ;  TW1 OVER = SWAP 1+ L = AND  -> TRUE }T

ruvNew Version: [312] TRAVERSE-WORDLIST must not expose the current definition [r1123] 2023-10-23 10:08:02

Hide differences

This test ensured that the current definition is not exposed, and that the correct number of names is placed into the compilation word list.

: WORDLIST-LENGTH ( wid -- u )
  >R 0 [: DROP 1+ TRUE ;] R> TRAVERSE-WORDLIST
;
: L ( -- u ) GET-CURRENT WORDLIST-LENGTH ;

~~T{ L :NONAME [ L ] LITERAL ; EXECUTE L = = -> TRUE }T~~

T{ L :NONAME [ L ] LITERAL ; EXECUTE OVER = SWAP L = AND -> TRUE }T

T{ L : TW1 [ L ] LITERAL ; TW1 OVER = SWAP 1+ L = AND -> TRUE }T

Reply New Version

lmr [319] Nested invocation, ret stack Request for clarification2023-12-18 04:59:48

What assumptions can XT make about TWL and viceversa?

can XT invoke another TWL recursively?
can TWL save information on the return stack, e.g can I implement TWL using two nested DO loops (an inner one to iterate over wordlist indices, and a "dummy" outer one just to make wid available as J)?

AntonErtl [r1143] 2023-12-18 08:49:57

Yes, there is no stated restriction on what the xt passed to TRAVERSE-WORDLIST is allowed to do, so the xt is allowed to call TRAVERSE-WORDLIST.
Yes, in a standard system TRAVERSE-WORDLIST can use the return stack, because in a standard program words of which xts can be taken are not allowed to access return stack entries that they have not pushed on the return stack themselves.

Closed

Reply New Version

lmr [326] shadowed namesRequest for clarification2023-12-26 18:09:55

[…] words with the same name are called in the order newest-to-oldest

Does this mean the system needs to keep around word definitions even after they are shadowed by a re-definition (thus precluding a simple hash-table implementation of wordlists)...?

AntonErtl [r1158] 2023-12-26 18:32:05

The CfV says:

Whether duplicated nodes are visited or not by TRAVERSE-WORDLIST is undefined.

The text of the CfV was condensed, and this particular clause was omitted, but IIRC there was no intent to change the meaning.

However, note that if you implement marker or forget, you may want to keep the shadowed names anyway.

lmr [r1160] 2023-12-26 19:03:45

if you implement marker or forget, you may want to keep the shadowed names anyway

Yes, but I can implement MARKER as a "clojure" around deep copies of

the wid-indexed "all-wordlists" vector of word-name -> name-token hashtables
the "current-wid" pointer to the top of the "all-wordlists" vector (as per the MARKER comment https://forth-standard.org/standard/core/MARKER#reply-1159 — I previously thought that some MARKER usage patterns could leave "holes" in this vector, thus requiring the maintenance of some kind of free-list; upon reflecting this doesn't seem possible), and
the "search-order" vector of wid's

It's probably still necessary to maintain shadowed name-tokens (or at least shadowed XTs?) since the user could have saved them using FIND, SEARCH-WORDLIST or the FIND-NAME[-IN] extensions

AntonErtl [r1161] 2023-12-27 06:53:10

I forgot to write the conclusion of the statement about the intent: Forth-2012 says: "Execute xt once for every word in the wordlist wid", but does not say whether "every word" includes shadowed words or not. This is compatible with the intent that the system implementor can do either. However, it probably is a good idea to make this intent more explicit.

AntonErtl [r1162] 2023-12-27 06:54:42

Yes, shadowing does not invalidate existing nts and xts. You can even get at the name with NAME>STRING.

ruv [r1213] 2024-03-06 20:55:19

Forth-2012 says: "Execute xt once for every word in the wordlist wid", but does not say whether "every word" includes shadowed words or not.

If some standard word removes anything from a word list — this action must be explicitly specified.
There are only two such words: 15.6.2.1580 FORGET and 6.2.1850 MARKER.

Creating a named definition implies placing it into the compilation word list. This does not imply removing anything from the compilation word list (otherwise it should be specified). Before the word TRAVERSE-WORDLIST was introduced, a program could not detect whether the system removes a shadowed word from the word list, so the system was implicitly allowed to do it. But now a Forth system is not allowed to remove shadowed names from the compilation word list, I think.

AntonErtl [r1214] 2024-03-07 18:41:03

Yes, a system that implements marker or forget needs to make words visible again that were shadowed by or after defining the marker or the forgotten word.

Looking at the CfP, it says explicitly:

Whether duplicated nodes are visited or not by TRAVERSE-WORDLIST is undefined.

and gives an example. So the intention was to give no guarantees about that. Maybe we should put that intention explicitly in the standard text. Alternatively, if you want a guarantee, investigate existing practice, and, if it agrees with your preference, make a proposal for standardizing that.

Reply New Version