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:

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

GerryJacksonavatar of 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.

AntonErtlavatar of AntonErtl

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?

GerryJacksonavatar of GerryJackson

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).

AntonErtlavatar of AntonErtl

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

ruvavatar of 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.

AntonErtlavatar of AntonErtl

Addressed in this proposal.

Closed
Reply New Version

ruvavatar of 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

ruvavatar of ruvNew Version: TRAVERSE-WORDLIST must not expose the current definition

Show differences

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  OVER = SWAP L = AND  -> TRUE }T

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

lmravatar of 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)?

AntonErtlavatar of AntonErtl

  • 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

lmravatar of 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)...?

AntonErtlavatar of AntonErtl

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.

lmravatar of lmr

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

AntonErtlavatar of AntonErtl

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.

AntonErtlavatar of AntonErtl

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

ruvavatar of ruv

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.

AntonErtlavatar of AntonErtl

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.

ruvavatar of ruv

So the intention was to give no guarantees about that.

Yes, but this intention (concerning "duplicated nodes") is not reflected in the normative parts.

Maybe we should put that intention explicitly in the standard text.

I prefer to have access to shadowed definitions. And for introspection purposes, it's better if a Forth system does not skip shadowed words in traverse-wordlist. (From time to time people even ask how to access a shadowed word in Forth, see an example on StackOverflow).

Alternatively, if you want a guarantee, investigate existing practice, and, if it agrees with your preference, make a proposal for standardizing that.

From the formal point of view, we already have this guarantee: the text description says that xt is executed once for every word in the word list. And nothing in the normative text says that traverse-wordlist can skip shadowed words in a word list. It means, it cannot skip the shadowed words.

Thus, to allow traverse-wordlist to skip shadowed words, a proposal should be created to change the normative text description.

ruvavatar of ruv

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

I can't agree with this.
"Every word in the word list" means every word that was placed in the word list and was not subsequently removed from the word list. That is, shadowing does not change anything in this regard.

ruvavatar of ruv

Just for reference. We forgot that the change in wording for traverse-wordlist was accepted in 2020. And it says that the old wording (i.e., that in Forth-2012) already gives guarantee that the shadowed words are visited.

Reply New Version