Why no standard words for traversing a wordlist?

[Krishna Myneni]

Others must have brought up this question previously, but I'm
wondering why there are no standard words in Forth for traversing a
wordlist and obtaining basic information about each node? While
standard Forth provides a great many features for extensibility of the
language (with CREATE ... DOES> being the classic example), standard
Forth seems to be lacking the basic capability of traversing the
wordlist as a part of the language. Such a capability is needed to
provide some kinds of advanced programming tools. For example, I may
want to determine all instances of word name overlaps in all of the
wordlists in the current search order. AFAIK, there is no standard way
to do that presently.

On first thought, the minimum set of wordlist traversal words needed
are,

a) Set the current node to the head or the tail of the wordlist --
only one is sufficient if we restrict ourselves to a single direction
for the traversal.

b) Advance to the next node or backup to the previous node (again,
only one will suffice).

c) Obtain the xt of the current node

d) Obtain the name of the current node (i.e. name of the word)

Note that the term node is only used descriptively -- there does not
need to be an actual linked list in the underlying system
implementation of wordlists. The above set of functions should be
independent of the implementation details, but maybe I'm overlooking
something. Perhaps embedded systems do not retain word names in their
run-time environment (but, then, emdedded systems do not have to
support this set of words).

Some Forth systems may support the above functions partially or fully.
What is the existing practice in Forth systems?

Krishna

[Mark Wills]

On Jan 16, 12:36 pm, Krishna Myneni <krishna.myn...@ccreweb.org>
wrote:

I'm inclined to agree. As you point out, embedded or tethered systems
may not maintain a dictionary, but I would agree that there is some
mileage in looking at an optional word-set to provide wordlist
manipulation facilities.

[Mark Wills]

On Jan 16, 12:36 pm, Krishna Myneni <krishna.myn...@ccreweb.org>
wrote:

One of the difficulties would be that the dictionary/wordlist is 'free
format', in so far as an implementer is free to determine how his
dictionary works. Therefore, his dictionary may or may not contain
certain fields. For example, most dictionaries would contain a back-
pointer (or link field) which contains the address of the previous
node. Others, where the code and dictionary are mixed in the same
memory space, may also contain a forward pointer also, but not
necessarily! Some dictionaries contain the names of their words in
full, including a length field. Some store only the first three
characters, and thus don't have a name field. Some have neither, and
store a hash of the word!

The goal, from a standards perspective would probably be to find the
lowest common denominator that *most* systems would have, and build
from that.

Quite daunting!

Mark

[Krishna Myneni]

For the moment, I'm only interested in examining wordlist entries, and
even then, only a minimal set of fields for each "node" -- its xt and
name. I don't advocate providing words to actually modify a wordlist
-- even if this is Forth, an interface to modify wordlists sounds like
it would be begging for misuse.

Krishna

[Krishna Myneni]

Right! As you mention, nearly all dictionaries will have a back
pointer -- traversal in only the back direction is sufficient, as long
as we can position the node pointer at the correct end of the
wordlist, which would be the most recent word. An xt certainly must
exist for the node, if it's standard Forth. The name field returned by
a standard word can be a variable type, with an associated value to
indicate the type of quantity (e.g. full character name, or partial
name/hash value). That's about all we need. I think it's doable.

Krishna

[Mark Wills]

I agree. If the new suite of words revolved the address of the back-
pointer, that would probably be the lowest common denominator.

So, for example (I'm using F83 here, but hopefully you can follow
along):

S" THING" FIND DROP

Returns the xt of THING (the 'flags' portion (immediate etc) is
dropped).

From there, one could do:

>LINK ( cfa --- link_addr)

That gives us our back-pointer address/link-field address.

And from there:

>LENGTH ( link_addr -- length_addr)
Gives us the address of the length field*.

>NAME ( link_addr -- name_addr)
Gives us the address of the name field*.

>FLAGS ( link_addr -- flags_addr)
Gives the address of the flags field*.

*On a lot of systems it is common for a single cell to hold multiple
datums. For example, the length of word's name, and it's flags
(immediate, compile-only etc) are often stored in the same cell, as
they are in my system. In this case, carnal knowledge of the
dictionary structure would be required, and a potential portability
issue exists. Therefore, a small set of extra words, supplied by the
implementer could be proposed that abstract the inner complexities of
the dictionary structure away from the user:

@FLAGS ( link_addr -- n)
Returns the flags of the associated word, right justified. Note the
address of the LINK field is passed in. @FLAGS takes care of the nitty
gritty.

!FLAGS ( n link_addr -- ) writes right-justified n to the flag bits. !
FLAGS internally masks and rotates as required. E.g. if there are only
3 flag bits in use, and the user writes FFFF then only the lower three
3 bits of the FFFF are written into the flags bits (to guard against
obliterating adjacent bits/datums in the cell).

@NAME ( link_addr -- addr len)
Returns the name as address/length pair on the stack (e.g. suitable
for use with TYPE).

!NAME ( addr len link_addr -- )
Writes the new name into the dictionary entry and updates the name
length pointer, if present. If the new name is longer than the
original name, the name is truncated.

...
...
...

You get the idea!

These words are already in use on my home-brew systems, which has >
100 users, so they are 'in the wild', at least in my case. Though my
system is just for home retro computing enthusiasts. The above is only
suggested as a starting point... "Grit for the mill" as we would
say...

Mark

[Anton Ertl]

Krishna Myneni <krishna...@ccreweb.org> writes:
>Others must have brought up this question previously, but I'm
>wondering why there are no standard words in Forth for traversing a
>wordlist and obtaining basic information about each node?

Nobody has proposed it for standardization. And I guess it would be
hard work, because even pre-proposals for fixing FIND have led to
long, fruitless discussions because some people hate the idea of
tokens representing named words and want to use the xt instead (and
rename it into "universal token"), while others point out that this
cannot be implemented in some Forth systems without major
implementation changes. Any proposal for traversing wordlists and
accessing the words in the wordlist would have to take a stand on this
issue and would take fire from either one or the other side of this
debate, and would certainly not make progress.

Or maybe you can help decide this issue: decide for one of the
alternatives; of course the other side will not implement your
proposal at first, but if you have killer applications for your words,
there will be quite a bit of motivation to implement the wordset; so
either the first side will implement the words even though it does not
require other systems to adopt a universal token, oder the other side
will change their implementations to make it possible to support words
that require a universal token. The question is: Do you have such a
killer application?

In the early 90s some people (including me) discussed standardizing
wordlist traversal and other introspection capabilities, but that
effort petered out after a while. In the meantime I found hardly any
cases where I wanted such capabilities (and if I did. I did it in a
system-specific way).

> While
>standard Forth provides a great many features for extensibility of the
>language (with CREATE ... DOES> being the classic example), standard
>Forth seems to be lacking the basic capability of traversing the
>wordlist as a part of the language.

Yes, introspection capabilities have been neglected in
standardization.

> Such a capability is needed to
>provide some kinds of advanced programming tools.

There is a tendency among some to neglect capabilities needed for
building tools, because supposedly application programmers don't use
them (and apparently only application programmers count).

>Some Forth systems may support the above functions partially or fully.
>What is the existing practice in Forth systems?

If you want to do such things, you use "carnal knowledge" of the
particular Forth system.

- anton
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2011: http://www.euroforth.org/ef11/

[Mark Wills]

On Jan 16, 2:30 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

I feel your pain, Anton. However, I think things were a little
different with FIND because we were talking about (IIRC) actually
changing its behavior, so there would have been passionate arguments
both ways.

I think it's different with any forthcoming proposal on dictionary
manipulation words, simply because it would only ever be proposed as
an optional extension, so far less controversial (one would hope) ;-)

Mark

[Anton Ertl]

Mark Wills <markrob...@yahoo.co.uk> writes:
>I feel your pain, Anton. However, I think things were a little
>different with FIND because we were talking about (IIRC) actually
>changing its behavior, so there would have been passionate arguments
>both ways.

No, the discussion was always about new words that perform the
functionality that FIND should perform (but with a better interface
and well-specified). And the main issue of contention recently was
not if we should do such a thing, but whether to use a "universal
token" (same as the xt) or whether to use a name token that may (but
is not required to) be different from the xt.

>I think it's different with any forthcoming proposal on dictionary
>manipulation words, simply because it would only ever be proposed as
>an optional extension, so far less controversial (one would hope) ;-)

Well, the token issue would have to be decided, and that's the most
controversial thing about the FIND replacement at the moment.

And I doubt that the universal-token fraction will accept a name token
in this proposal just because it is optional; after all, there would
have no problem implementing a name-token-based interface on a
universal-token system for the FIND replacement, either (the name
token would be implemented as universal token there), yet is dead set
against it.

And I also doubt that the name token fraction would vote for a
proposal based on the universal token, either, even if it is optional,
because that would mean standardizing an interface that they cannot
implement (at least not without significant changes to the internals
of system) for a functionality that they can implement (with a
different interface).

[Andrew Haley]

Krishna Myneni <krishna...@ccreweb.org> wrote:
> Others must have brought up this question previously, but I'm
> wondering why there are no standard words in Forth for traversing a
> wordlist and obtaining basic information about each node?

I don't think I've ever seen a request for such a thing before.

Andrew.

[Krishna Myneni]

On Jan 16, 8:30 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Krishna Myneni <krishna.myn...@ccreweb.org> writes:
> >Others must have brought up this question previously, but I'm
> >wondering why there are no standard words in Forth for traversing a
> >wordlist and obtaining basic information about each node?
>
> Nobody has proposed it for standardization.  And I guess it would be
> hard work, because even pre-proposals for fixing FIND have led to
> long, fruitless discussions because some people hate the idea of
> tokens representing named words and want to use the xt instead (and
> rename it into "universal token"), while others point out that this
> cannot be implemented in some Forth systems without major
> implementation changes.  Any proposal for traversing wordlists and
> accessing the words in the wordlist would have to take a stand on this
> issue and would take fire from either one or the other side of this
> debate, and would certainly not make progress.
>

Hmm... I'm afraid I must not have been paying attention and missed
this debate. Did it take place mostly in c.l.f.?

> Or maybe you can help decide this issue: decide for one of the
> alternatives; of course the other side will not implement your
> proposal at first, but if you have killer applications for your words,
> there will be quite a bit of motivation to implement the wordset; so
> either the first side will implement the words even though it does not
> require other systems to adopt a universal token, oder the other side
> will change their implementations to make it possible to support words
> that require a universal token.  The question is: Do you have such a
> killer application?
>

I won't claim a killer application. The query is in connection with
some ideas for useful tools a programmer might use to examine
potential issues with name resolution in a search order. Such tools
are being considered for a future version of our modules system -- a
first release of the modules system is close at hand, we believe,
although recent bouts of clarity have forced us to re-examine and
modify the design.

Apart from the application, implementing such capabilities in my own
Forth system seems to be almost a triviality. However, I wanted to
understand what subset of the mentioned features were already being
provided by other Forth systems, e.g. Gforth.

> In the early 90s some people (including me) discussed standardizing
> wordlist traversal and other introspection capabilities, but that
> effort petered out after a while.  In the meantime I found hardly any
> cases where I wanted such capabilities (and if I did. I did it in a
> system-specific way).
>

I really like the term, "introspection capabilities"! Is this an
established term in computer science?

> > While
> >standard Forth provides a great many features for extensibility of the
> >language (with CREATE ... DOES> being the classic example), standard
> >Forth seems to be lacking the basic capability of traversing the
> >wordlist as a part of the language.
>
> Yes, introspection capabilities have been neglected in
> standardization.
>
> > Such a capability is needed to
> >provide some kinds of advanced programming tools.
>
> There is a tendency among some to neglect capabilities needed for
> building tools, because supposedly application programmers don't use
> them (and apparently only application programmers count).
>

I'm not qualified to comment on the division of labor among
programmers, but, it seems to me that application programmers who
eschew useful tools must spend a significant amount of time doing
maintenance.

> >Some Forth systems may support the above functions partially or fully.
> >What is the existing practice in Forth systems?
>
> If you want to do such things, you use "carnal knowledge" of the
> particular Forth system.
>

But Forth systems may provide non-standard words, within their Forth
wordlist, for such purposes. Which systems have such words, and what
are their names? If I find a set I like, I'd have no hesitation to
implement them.

> - anton
> ...


Krishna

[Alex McDonald]

My Forth;

name>xt ( nfa -- xt ) ( get the xt for this name )

This isn't a FIND, as it assumes that the NFA (name field address) is
in a correct header in a wordlist. The reverse operation is

>name ( xt -- nfa ) ( nfa is a counted string )

I believe that operation is not possible in some Forths. To iterate
over a vocabulary;

voc-iterate ( xt voc -- )

The xt called has the stack effect of ( i*x nfa -- i*x x|0 ).
Returning zero terminates the loop. Example;

: x ( val nfa -- val' flag ) cr count type 1+ true ;
0 ' x ' forth voc-iterate .

will print individual names and count the total number of entries in
the vocabulary FORTH. It's a useful factor for implementing words like
WORDS and so on.

name>xtimm ( nfa -- xt 1|-1 )

returns immediacy, but it's only required to make FIND ANS compatible,
since the compiler does not use STATE or check for immediacy directly.
All the other, header-specific, words are based from the NFA address,
and are specific to this implementation. They include execution &
compilation tokens, the file and line number where the word is
defined, and various other flags & values used in debugging.

[Anton Ertl]

Krishna Myneni <krishna...@ccreweb.org> writes:
>On Jan 16, 8:30=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>wrote:

>> And I guess it would be
>> hard work, because even pre-proposals for fixing FIND have led to
>> long, fruitless discussions because some people hate the idea of
>> tokens representing named words and want to use the xt instead (and
>> rename it into "universal token"), while others point out that this
>> cannot be implemented in some Forth systems without major

>> implementation changes. =A0Any proposal for traversing wordlists and

>> accessing the words in the wordlist would have to take a stand on this
>> issue and would take fire from either one or the other side of this
>> debate, and would certainly not make progress.
>>
>
>Hmm... I'm afraid I must not have been paying attention and missed
>this debate. Did it take place mostly in c.l.f.?

Partly.

>I really like the term, "introspection capabilities"! Is this an
>established term in computer science?

Actually, the more established term is "reflection"
<http://en.wikipedia.org/wiki/Reflection_(computer_programming)>,
although "introspection" is also used
<http://rosettacode.org/wiki/Introspection>.

>> If you want to do such things, you use "carnal knowledge" of the
>> particular Forth system.
>>
>
>But Forth systems may provide non-standard words, within their Forth
>wordlist, for such purposes. Which systems have such words, and what
>are their names? If I find a set I like, I'd have no hesitation to
>implement them.

In Gforth this stuff (used in WORDS) is too low-level to be a useful
basis for a common interface; it reveals too much of the
implementation. I guess that will be true of most other systems, too.

[Krishna Myneni]

On Jan 16, 11:41 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Krishna Myneni <krishna.myn...@ccreweb.org> writes:
> >On Jan 16, 8:30=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
> >wrote:
> >> And I guess it would be
> >> hard work, because even pre-proposals for fixing FIND have led to
> >> long, fruitless discussions because some people hate the idea of
> >> tokens representing named words and want to use the xt instead (and
> >> rename it into "universal token"), while others point out that this
> >> cannot be implemented in some Forth systems without major
> >> implementation changes. =A0Any proposal for traversing wordlists and
> >> accessing the words in the wordlist would have to take a stand on this
> >> issue and would take fire from either one or the other side of this
> >> debate, and would certainly not make progress.
>
> >Hmm... I'm afraid I must not have been paying attention and missed
> >this debate. Did it take place mostly in c.l.f.?
>
> Partly.
>
> >I really like the term, "introspection capabilities"! Is this an
> >established term in computer science?
>
> Actually, the more established term is "reflection"
> <http://en.wikipedia.org/wiki/Reflection_(computer_programming)>,
> although "introspection" is also used
> <http://rosettacode.org/wiki/Introspection>.
>

As expected, from your second link above, Lisp has already been here
with "list-all-packages" and "do-symbols":

--
The list-all-packages and do-symbols forms enable a lisp program to
examine all symbols and these can be tested to identify integer
variables.

(let ((sum 0)
(ints '()))
(loop for pkg in (list-all-packages)
do (do-symbols (s pkg)
(when (and (boundp s)
(integerp (symbol-value s)))
(push s ints)
(incf sum (symbol-value s)))))
(format t "there are ~d integer variables adding up to ~d~%"
(length ints) sum))
--

Krishna

[Krishna Myneni]

...

> voc-iterate ( xt voc -- )
>
> The xt called has the stack effect of ( i*x nfa -- i*x x|0 ).
> Returning zero terminates the loop. Example;
>
> : x ( val nfa -- val' flag ) cr count type 1+ true ;
> 0 ' x ' forth voc-iterate .
>
> will print individual names and count the total number of entries in
> the vocabulary FORTH. It's a useful factor for implementing words like
> WORDS and so on.

> ...

Interesting. So you don't expose the underlying traversal words, and
maybe they are not needed. However, I expect in some situations you
may want to exit the traversal early, rather than being forced to
iterate through the entire list. Also, for compatibility with standard
Forth, I think it would be best to provide WID-ITERATE , which would
iterate over a wordlist rather than a vocabulary.

Krishna

[Paul Rubin]

Krishna Myneni <krishna...@ccreweb.org> writes:
> As expected, from your second link above, Lisp has already been here
> with "list-all-packages" and "do-symbols":

That is pretty crufty Lisp style and normally only a compiler or
debugger, or some analysis tool, would do something like that. The more
"pure" Lisp dialects (e.g. Scheme) don't have such features.

[Alex McDonald]

voc-iterate is based on a wordlist iteration :-)

To iterate only the first 10 words;

: x ( val nfa -- val' flag ) cr count type 1+ dup 10 < ;
0 ' x ' forth voc-iterate cr . ." words"

[Bruce.McFarling]

Under that approach you *can* exit the traversal early ~ the xt
replaces the nfa with either 0 or non-zero, on 0 the traversal
terminates, on non-zero the traversal continues.

However, the names in dictionary structures are allowed to be counted
strings, counted strings with a reserved bit field, nul-terminated
strings, strings with the count at the tail rather than the head, and
etc. However, with versions that takes an xt with the stack effects:
( x*i ca u xt -- x*i flag )

... that would seem to be a reasonable way to expose the range of
different specific wordlist traversal processes in implementation-
specific portability harnesses.

Then:

wordlist-iterate ( i*x xt wid -- )

This is more a library level approach than a language standard level
approach.

[Albert van der Horst]

In article <55425cb4-628c-4adb...@i25g2000vbt.googlegroups.com>,

Alex McDonald <bl...@rivadpm.com> wrote:
>>
>> > - anton
>> > ...
>>
>> Krishna
>
>My Forth;
>
>name>xt ( nfa -- xt ) ( get the xt for this name )
>
>This isn't a FIND, as it assumes that the NFA (name field address) is
>in a correct header in a wordlist. The reverse operation is
>
>>name ( xt -- nfa ) ( nfa is a counted string )
>
>I believe that operation is not possible in some Forths. To iterate
>over a vocabulary;
>
>voc-iterate ( xt voc -- )

I have that too in ciforths, assuming ``voc'' is a word list identifier
in the sene of ISO. It is called FOR-WORDS.

: WORDS 'ID. CONTEXT @ FOR-WORDS ;

>
>The xt called has the stack effect of ( i*x nfa -- i*x x|0 ).


>Returning zero terminates the loop. Example;
>
>: x ( val nfa -- val' flag ) cr count type 1+ true ;
>0 ' x ' forth voc-iterate .

My xt has the stack effect ( i*x dea -- i*x )
I think FOR-WORDS must take care of ending the loop.
Now you must always define a new word for each use.
: my-ID. ID. TRUE ; ' my-ID CONSTANT 'my-ID
: WORDS 'my-ID. CONTEXT @ FOR-WORDS ;

If only nameless xt's were easier ;-(
: WORDS [{ ID. TRUE }] CONTEXT @ voc-iterate ;
would not be so bad.

>
>will print individual names and count the total number of entries in
>the vocabulary FORTH. It's a useful factor for implementing words like
>WORDS and so on.

>
>name>xtimm ( nfa -- xt 1|-1 )
>
>returns immediacy, but it's only required to make FIND ANS compatible,
>since the compiler does not use STATE or check for immediacy directly.
>All the other, header-specific, words are based from the NFA address,
>and are specific to this implementation. They include execution &
>compilation tokens, the file and line number where the word is
>defined, and various other flags & values used in debugging.

Never needed this, but easy to make.

--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[BruceMcF]

On Jan 16, 5:20 pm, Albert van der Horst <alb...@spenarnc.xs4all.nl>
wrote:

> >The xt called has the stack effect of ( i*x nfa -- i*x x|0 ).
> >Returning zero terminates the loop. Example;
>
> >: x ( val nfa -- val' flag ) cr count type 1+ true ;
> >0 ' x ' forth voc-iterate .
>
> My xt has the stack effect  ( i*x dea -- i*x )
> I think FOR-WORDS must take care of ending the loop.

However then if the loop is supposed to terminate early, you have:

VARIABLE end-word-loop

: DO-STEP end-word-loop @ ?DUP AND IF ...
... THEN ;

... to repeatedly skip the operation if the early loop termination
condition is met.

Making a word that fits in with the other semantics that never
terminates early is simpler:

: DO-STEP ... TRUE ;

[Krishna Myneni]

On Jan 16, 2:27 pm, Paul Rubin <no.em...@nospam.invalid> wrote:

It seemed ironic to me that, in Forth, where the dictionary is based
on the abstraction of a linked list, a user could not traverse that
list. It is then even more ironic if Lisp, a language which boasts its
power from treating everything uniformly as a list, did not allow the
user to traverse a list of its own symbols!

Krishna

[BruceMcF]

Dictionary traverse at language level would be something like:

first-name ( wid -- nt flag )
next-name ( nt1 -- nt2 flag )
name>string ( nt -- ca u )
name>execute ( nt -- xt )
name>compile ( nt -- x xt )

"flag" would be true if the requested dictionary token exists, false
otherwise.

This also seems to be something that could be defined in a portability
harness for each supported implementation.

[Andrew Haley]

Krishna Myneni <krishna...@ccreweb.org> wrote:
> Others must have brought up this question previously, but I'm
> wondering why there are no standard words in Forth for traversing a
> wordlist and obtaining basic information about each node? While
> standard Forth provides a great many features for extensibility of the
> language (with CREATE ... DOES> being the classic example), standard
> Forth seems to be lacking the basic capability of traversing the
> wordlist as a part of the language. Such a capability is needed to
> provide some kinds of advanced programming tools. For example, I may
> want to determine all instances of word name overlaps in all of the
> wordlists in the current search order. AFAIK, there is no standard way
> to do that presently.
>
> On first thought, the minimum set of wordlist traversal words needed
> are,
>
> a) Set the current node to the head or the tail of the wordlist --
> only one is sufficient if we restrict ourselves to a single direction
> for the traversal.
>
> b) Advance to the next node or backup to the previous node (again,
> only one will suffice).
>
> c) Obtain the xt of the current node
>
> d) Obtain the name of the current node (i.e. name of the word)

I think you're not allowing for some possibilities. For example, it
might be that there is an array of lists, and the name of a word is
hashed with the wordlist in which it appears. This chooses the list
to search. This has the nice property that the length of the lists
you have to search is not a property of the length of the wordlist.
It still conforms to the standard. However, traversing a wordlist
isn't going to be easy.

Andrew.

[Bernd Paysan]

Andrew Haley wrote:
> I think you're not allowing for some possibilities. For example, it
> might be that there is an array of lists, and the name of a word is
> hashed with the wordlist in which it appears. This chooses the list
> to search. This has the nice property that the length of the lists
> you have to search is not a property of the length of the wordlist.
> It still conforms to the standard. However, traversing a wordlist
> isn't going to be easy.

In Gforth, we use such a hash as structure to search wordlists quickly -
it's a unified hash, so all words end up in the same hash (for different
wordlists at different buckets, because the wordlist id goes into the
hashing algorithm).

But then, we also keep the linked list, to implement WORDS and to build
up the hash at startup (and, since the hash search is not part of the
kernel, but loaded later, to convert existing linked list vocabularies
into hashed ones).

The right abstraction IMHO is the map abstraction, i.e. pass an xt and a
wordlist to a mapping function, which traverses whatever structure there
is. A traversal of such a hash is still possible, by filtering out all
the words that do not belong to the wordlist we are currently
traversing.

How to terminate such a traversal? I suggest using THROW with a special
"end of traversal" pseudo-error number. This works even when the
traversal function has to be recursive (tree traversal). The downside
is that THROW resets the stack pointer to before calling, so possible
return values have to be allocated on the data stack beforehand. But
it's doable.

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[Anton Ertl]

Andrew Haley <andr...@littlepinkcloud.invalid> writes:
>I think you're not allowing for some possibilities. For example, it
>might be that there is an array of lists, and the name of a word is
>hashed with the wordlist in which it appears. This chooses the list
>to search. This has the nice property that the length of the lists
>you have to search is not a property of the length of the wordlist.
>It still conforms to the standard. However, traversing a wordlist
>isn't going to be easy.

However wordlists are implemented, a system has to traverse a wordlist
to implement WORDS, so something like VOC-ITERATE is definitely
possible on any system that implements WORDS (and if the system does
not implement words, it will not implement VOC-ITERATE, either).
Bernd Paysan outlined how a system that implements wordlists in the
way you describe could implement VOC-ITERATE.

[Anton Ertl]

"Bruce.McFarling" <bruce.m...@gmail.com> writes:
>However, the names in dictionary structures are allowed to be counted
>strings, counted strings with a reserved bit field, nul-terminated
>strings, strings with the count at the tail rather than the head, and
>etc. However, with versions that takes an xt with the stack effects:
> ( x*i ca u xt -- x*i flag )
>
>... that would seem to be a reasonable way to expose the range of
>different specific wordlist traversal processes in implementation-
>specific portability harnesses.

That would certainly circumvent the universal-token vs. name-token
controversy, but the disadvantage is that it delivers only a part of
the information of a word. If we also want to know about compilation
semantics, or maybe other (non-standard features), we would need
WORDLIST-ITERATE2 etc.

[BruceMcF]

On Jan 18, 8:59 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> That would certainly circumvent the universal-token vs. name-token
> controversy, but the disadvantage is that it delivers only a part of
> the information of a word.  If we also want to know about compilation
> semantics, or maybe other (non-standard features), we would need
> WORDLIST-ITERATE2 etc.

Yes we would need another word to expose additional information.
That's pretty much an intrinsic of a portable wordset of either type.
For the first-word next-word nt>name nt>execute nt>compile
approach ... you also need an additional word to convey additional
information of a word entry.

[Krishna Myneni]

On Jan 18, 7:53 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Andrew Haley <andre...@littlepinkcloud.invalid> writes:
> >I think you're not allowing for some possibilities.  For example, it
> >might be that there is an array of lists, and the name of a word is
> >hashed with the wordlist in which it appears.  This chooses the list
> >to search.  This has the nice property that the length of the lists
> >you have to search is not a property of the length of the wordlist.
> >It still conforms to the standard.  However, traversing a wordlist
> >isn't going to be easy.
>
> However wordlists are implemented, a system has to traverse a wordlist
> to implement WORDS, so something like VOC-ITERATE is definitely
> possible on any system that implements WORDS (and if the system does
> not implement words, it will not implement VOC-ITERATE, either).
> Bernd Paysan outlined how a system that implements wordlists in the
> way you describe could implement VOC-ITERATE.
>

My understanding is that the ability to traverse a wordlist, then, is
independent of the debate about FIND, which is concerned with the
specific type of information to be returned by a FIND-like word. It
would certainly be possible to specify a minmial word set, say the
"introspection" word set, that implements WORDLIST-ITERATE (VOC-
ITERATE would not be standard), and then words to obtain the NAME
field or FIND's xt field. If FIND is later extended as a new word in
the standard, a corresponding field retrieval word can be added to the
introspection word set.

Also, I'm not sure I understand Bernd's rationale that the iteration
word, e.g. WORDLIST-ITERATE, perform a throw at the end of the
iteration. What is the disadvantage of simply returning with an exit
code?

Krishna

[Anton Ertl]

BruceMcF <agi...@netscape.net> writes:
>On Jan 18, 8:59=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)

>wrote:
>> That would certainly circumvent the universal-token vs. name-token
>> controversy, but the disadvantage is that it delivers only a part of

>> the information of a word. =A0If we also want to know about compilation

>> semantics, or maybe other (non-standard features), we would need
>> WORDLIST-ITERATE2 etc.
>
>Yes we would need another word to expose additional information.
>That's pretty much an intrinsic of a portable wordset of either type.
>For the first-word next-word nt>name nt>execute nt>compile
>approach ... you also need an additional word to convey additional
>information of a word entry.

Let's separate two issue:

1) Producing an NT/UT vs. producing some of the information contained
in the word (such as name and execution semantics). That's the issue
at hand in this subthread.

2) FIRST-WORD NEXT-WORD vs. VOC-ITERATE: this does not play a role for
the other issue, so let's ignore it for now.

Yes, if I want to get information on, say, the source code location of
a word (used for LOCATE), I would need to add a NAME>LOCATION word or
somesuch. However, this word would work with any word that produces
an NT, whether it is FIND-NAME or VOC-ITERATE.

In contrast, if I add a VOC-ITERATE3 to produce this information, I
would also have to add FIND-SOMETHING3 to be able to get at this
information through its name without funny workarounds.

In conclusion, having a token for the named word leads to better
factoring.

[Anton Ertl]

Krishna Myneni <krishna...@ccreweb.org> writes:
>My understanding is that the ability to traverse a wordlist, then, is
>independent of the debate about FIND, which is concerned with the
>specific type of information to be returned by a FIND-like word.

Well, if you standardize traversing a wordlist, you also have to
decide on the specific type of information to be produced by the
traversal word(s).

>Also, I'm not sure I understand Bernd's rationale that the iteration
>word, e.g. WORDLIST-ITERATE, perform a throw at the end of the
>iteration. What is the disadvantage of simply returning with an exit
>code?

It's not clear to me what that was aiming at. Either he was thinking
about implementation internals of the reversal word or he was thinking
of how the user code could perform an early exit if WORDLIST-ITERATE
does not have an interface that allows the user code to indicate an
early exit. Alex McDonald's VOC-ITERATE has the "x|0" argument that
indicates whether the iteration should be terminated.

[BruceMcF]

On Jan 18, 10:28 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> In conclusion, having a token for the named word leads to better
> factoring.

Aha, you were focusing on the details of what the traverse-wordlist
returns from the dictionary entry, not on the loop/flag behavior.

I don't much mind whether that part of the behavior is:

( x*i ca u xt -- x*i flag )

... or:
( x*i nt -- x*i flag )

... either is fine. I am, of course, against an xt as a "universal
token" that can always recover its name entry.

[Bernd Paysan]

Anton Ertl wrote:
>>Also, I'm not sure I understand Bernd's rationale that the iteration
>>word, e.g. WORDLIST-ITERATE, perform a throw at the end of the
>>iteration. What is the disadvantage of simply returning with an exit
>>code?
>
> It's not clear to me what that was aiming at. Either he was thinking
> about implementation internals of the reversal word or he was thinking
> of how the user code could perform an early exit if WORDLIST-ITERATE
> does not have an interface that allows the user code to indicate an
> early exit. Alex McDonald's VOC-ITERATE has the "x|0" argument that
> indicates whether the iteration should be terminated.

Yes, that's the point - have an early exit from the iteration without
requiring that each invocation has to return a flag. If you iterate
over all words, you would not do the THROW at all.

[Alex McDonald]

Either a ut or an xt; as long as it's an opaque value and can lead you
to an xt or a name entry, it matters little what it is.

[Elizabeth D. Rather]

A word that returns the name as (addr len) might be acceptable, as it
wouldn't constrain either the organization of the name field in memory
or its location wrt whatever an xt is in that implementation.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[BruceMcF]

On Jan 18, 5:10 pm, Alex McDonald <b...@rivadpm.com> wrote:
> Either a ut or an xt; as long as it's an opaque value and can
> lead you to an xt or a name entry, it matters little what it is.

Of course, requiring it to lead you to a name entry rules out xt's in
a variety of cases, so if it is an opaque value that can lead you to a
name entry, its distinct from an xt.

What's the difference between a "ut" and a "nt"?

traverse-wordlist ( xt wid -- u )
... where "xt" does ( x*i nt -- x*i u )
if u=0, traversal stops, otherwise traversal continues to the end of
the wordlist.

nt>name ( nt -- ca u )
nt>execute ( nt -- xt )
nt>compile ( nt -- x xt )

If the implementation offered other things that could be done with the
nt, that would be up to the implementation.

[Rod Pemberton]

"Krishna Myneni" <krishna...@ccreweb.org> wrote in message
news:152b663c-6530-4b03...@t8g2000yqg.googlegroups.com...

> Others must have brought up this question previously, but I'm
> wondering why there are no standard words in Forth for traversing a
> wordlist and obtaining basic information about each node? While
> standard Forth provides a great many features for extensibility of the
> language (with CREATE ... DOES> being the classic example), standard
> Forth seems to be lacking the basic capability of traversing the
> wordlist as a part of the language. Such a capability is needed to
> provide some kinds of advanced programming tools. For example, I may
> want to determine all instances of word name overlaps in all of the
> wordlists in the current search order. AFAIK, there is no standard way
> to do that presently.
>
> On first thought, the minimum set of wordlist traversal words needed
> are,
>
> a) Set the current node to the head or the tail of the wordlist --
> only one is sufficient if we restrict ourselves to a single direction
> for the traversal.
>
> b) Advance to the next node or backup to the previous node (again,
> only one will suffice).
>
> c) Obtain the xt of the current node
>
> d) Obtain the name of the current node (i.e. name of the word)
>

> Note that the term node is only used descriptively -- there does not
> need to be an actual linked list in the underlying system
> implementation of wordlists. The above set of functions should be
> independent of the implementation details, but maybe I'm overlooking
> something. Perhaps embedded systems do not retain word names in their
> run-time environment (but, then, emdedded systems do not have to
> support this set of words).

>
> Some Forth systems may support the above functions partially or fully.
> What is the existing practice in Forth systems?
>

If I were deciding on the basic functionality I needed for traversing a
linked-list in Forth, I'd at least want the following:

-a word in Forth to get the starting node
-a word in Forth to get the ending node
-a word in Forth to get the current node
-a word in Forth to get the prior node and
which updates the current node position
-a word in Forth to get the next node and
which updates the current node position
-a word in Forth to set the node traversal direction to backwards
-a word in Forth to set the node traversal direction to forwards
-a generic word in Forth which gets another node in the
traversal direction and which updates the current node position

The key thing here, that I didn't notice in the replies by others, is the
ability to set a general direction for traversal and a generic word to
continue traversing in that direction. This is useful for loops. I.e., you
can set the direction of traversal outside the loop or even in an unrelated
word. This can make the loop body independent of the traversal direction.

In the case of a Forth dictionary, those would probably be constructed to
return the xt or a numeric identifier for a specific entry. As you've
noted, the primary question is in regards to a Forth dictionary, in which
case, functionality is needed to get the xt and/or numeric identifier of the
dictionary entry, and the name of the dictionary entry from the xt or
identifier.


Rod Pemberton

[Alex McDonald]

On Jan 19, 1:36 am, BruceMcF <agil...@netscape.net> wrote:
> On Jan 18, 5:10 pm, Alex McDonald <b...@rivadpm.com> wrote:
>
> > Either a ut or an xt; as long as it's an opaque value and can
> > lead you to an xt or a name entry, it matters little what it is.
>
> Of course, requiring it to lead you to a name entry rules out xt's in
> a variety of cases, so if it is an opaque value that can lead you to a
> name entry, its distinct from an xt.
>
> What's the difference between a "ut" and a "nt"?

Universal vs name (although I suggested neither, that's what I'm
assuming).

>
> traverse-wordlist ( xt wid -- u )
> ... where "xt" does ( x*i nt -- x*i u )
> if u=0, traversal stops, otherwise traversal continues to the end of
> the wordlist.
>
> nt>name ( nt -- ca u )
> nt>execute ( nt -- xt )
> nt>compile ( nt -- x xt )

What is x in the diagram nt>compile ( nt -- x xt )?

[Alex McDonald]

On Jan 19, 8:10 am, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
wrote:
> "Krishna Myneni" <krishna.myn...@ccreweb.org> wrote in message

While they're suitable for traversing a linked list, many dictionaries/
wordlists/vocabularies are not based on them, and it would presume a
doubly linked list to support such a traversal scheme. For instance,
some are hash only, others hash & single linked lists.

[snipped]

[Anton Ertl]

BruceMcF <agi...@netscape.net> writes:
>What's the difference between a "ut" and a "nt"?

With a "ut" NAME>INT ( nt -- xt ) and >NAME ( xt -- nt ) are noops;
actually, there would not be such words if we did not make a
difference between xt and nt (i.e., if we had a ut).

[Stephen Pelc]

On Thu, 19 Jan 2012 12:24:48 GMT, an...@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>actually, there would not be such words if we did not make a
>difference between xt and nt (i.e., if we had a ut).

What in ANS and Forth200x stops an xt being a ut?

Nothing that I can see. After, that it's just a quality
of implementation issue.

Stephen


--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[BruceMcF]

On Jan 19, 6:03 am, Alex McDonald <b...@rivadpm.com> wrote:
>> What's the difference between a "ut" and a "nt"?

> Universal vs name (although I suggested neither, that's what I'm
> assuming).

Uh, yeah, that I'd caught, what I was asking was what is the
*substantial* difference between a "universal token" and a "name
token". I had though it was as Anton answered, that "universal token"
was the approach of adding more constraints on the xt and forcing it
to be an inefficient execution token in implementations where an
efficient execution token does not always lead back to the name entry.

Name token, on the other hand, is an opaque token that is distinct
from the xt and so does never forces any inefficiencies upon EXECUTE
when it consumes an xt.

>> traverse-wordlist ( xt wid -- u )
>> ... where "xt" does ( x*i nt -- x*i u )
>> if u=0, traversal stops, otherwise traversal continues to the end
>> of the wordlist.

>> nt>name ( nt -- ca u )
>> nt>execute ( nt -- xt )
>> nt>compile ( nt -- x xt )

> What is x in the diagram nt>compile ( nt -- x xt )?

It is an opaque input to xt in that behavior ~ it is often the execute
xt, with the xt on top being COMPILE, but it can also be an xt that
performs a special compilation action with the xt on the top of the
stack performing EXECUTE on that compilation action xt. And it could
in general be anything.

[BruceMcF]

On Jan 19, 8:02 am, stephen...@mpeforth.com (Stephen Pelc) wrote:
> On Thu, 19 Jan 2012 12:24:48 GMT, an...@mips.complang.tuwien.ac.at

> (Anton Ertl) wrote:
> >actually, there would not be such words if we did not make a
> >difference between xt and nt (i.e., if we had a ut).

> What in ANS and Forth200x stops an xt being a ut?

AFAIU, nothing, but then again I Am Not A (Language) Lawyer.

> Nothing that I can see. After, that it's just a quality
> of implementation issue.

Precisely, adding that constraint on the xt may in some implementation
approaches imply a slower EXECUTE on the xt. I would rather an xt that
is free to do its one thing well.

[BruceMcF]

On Jan 19, 6:08 am, Alex McDonald <b...@rivadpm.com> wrote:
> While they're suitable for traversing a linked list, many dictionaries/
> wordlists/vocabularies are not based on them, and it would presume a
> doubly linked list to support such a traversal scheme. For instance,
> some are hash only, others hash & single linked lists.

As long as the hash dictionaries have collision chains that would
apply to redefinitions in the same wordlist, so that the most recent
definition under a same name in the same dictionary is
distinguishable, then couldn't a traversal entail stepping through the
hash buckets in a set sequence, filtering out entries that are not in
the desired dictionary?

[JennyB]

Goedel's Incompleteness Theorem?

[Alex McDonald]

Which is exactly what some Forths do. Win32Forth (and in my Forth,
from which it's derived) produce a WORDS list that is in most recent
to least recent definition order from its hash-entry-plus-lists-for-
collisions tables. But there is no concept of previous or next from
one entry to another.

Gforth hashes everything into the same hash table. What information is
derivable from it, and how would it be "traversed"?

That's why I'm not too fond of the name "traverse-wordlist". Wordlists
are not being traversed, in the sense that we can't move from where we
are to some other specified place, like a previous or parent, from the
word that is invoked and does the work on a specific dictionary entry.
(Equally, "iterate" might imply some order, which is true in my
Forth's case, but not all.)

[Alex McDonald]

The xt should know what it needs to do without external assistance --
i.e. it should do only one thing, which is return the compilation
behaviour.

[Alex McDonald]

To be clear; "return the compilation behaviour" == "provide the
compilation behaviour"

[Anton Ertl]

steph...@mpeforth.com (Stephen Pelc) writes:
>On Thu, 19 Jan 2012 12:24:48 GMT, an...@mips.complang.tuwien.ac.at
>(Anton Ertl) wrote:
>
>>actually, there would not be such words if we did not make a
>>difference between xt and nt (i.e., if we had a ut).
>
>What in ANS and Forth200x stops an xt being a ut?

Nothing. The things I do with an nt and which you do with an xt have
not been standardized. So there is nothing in the standard that says
anything about them, nor about whether the nt and the xt are the same
or not.

>Nothing that I can see. After, that it's just a quality
>of implementation issue.

That would be fine, but as long as we don't standardize any of these
features, it isn't even that.

[Anton Ertl]

Alex McDonald <bl...@rivadpm.com> writes:
>On Jan 19, 1:37=A0pm, BruceMcF <agil...@netscape.net> wrote:

>> On Jan 19, 6:03=A0am, Alex McDonald <b...@rivadpm.com> wrote:
>> >> nt>compile ( nt -- x xt )
>> > What is x in the diagram nt>compile ( nt -- x xt )?
>>
>> It is an opaque input to xt in that behavior ~ it is often the execute
>> xt, with the xt on top being COMPILE, but it can also be an xt that
>> performs a special compilation action with the xt on the top of the
>> stack performing EXECUTE on that compilation action xt. And it could
>> in general be anything.
>
>The xt should know what it needs to do without external assistance --
>i.e. it should do only one thing, which is return the compilation
>behaviour.

Sure, it's possible to have, for every word with default compilation
semantics (e.g., "+"), a routine that compiles it, i.e. equivalent to

:noname ['] + compile, ;

and it would give us a more symmetric and elegant way to deal with
interpretation and compilation semantics. But it seems preferable to
me to have a slightly less elegant interface and avoid the need to
create such a routine for every word with default compilation
semantics (i.e., the vast majority of words).

[BruceMcF]

On Jan 19, 9:16 am, Alex McDonald <b...@rivadpm.com> wrote:
> On Jan 19, 1:50 pm, BruceMcF <agil...@netscape.net> wrote:
>
> > On Jan 19, 6:08 am, Alex McDonald <b...@rivadpm.com> wrote:
>
> > > While they're suitable for traversing a linked list, many dictionaries/
> > > wordlists/vocabularies are not based on them, and it would presume a
> > > doubly linked list to support such a traversal scheme. For instance,
> > > some are hash only, others hash & single linked lists.
>
> > As long as the hash dictionaries have collision chains that would
> > apply to redefinitions in the same wordlist, so that the most recent
> > definition under a same name in the same dictionary is
> > distinguishable, then couldn't a traversal entail stepping through the
> > hash buckets in a set sequence, filtering out entries that are not in
> > the desired dictionary?
>
> Which is exactly what some Forths do. Win32Forth (and in my Forth,
> from which it's derived) produce a WORDS list that is in most recent
> to least recent definition order from its hash-entry-plus-lists-for-
> collisions tables. But there is no concept of previous or next from
> one entry to another.

> Gforth hashes everything into the same hash table. What information is
> derivable from it, and how would it be "traversed"?

That's why I *prefer* traverse to iterate. Traverse means "travel
across or through" ~ traversing a hash table according to the
sequential order of the hash buckets themselves and inside each has
bucket the most recently added item to least recently added item in
the collision chain *is* traveling "across or through" the hash
buckets.

> That's why I'm not too fond of the name "traverse-wordlist". Wordlists
> are not being traversed, in the sense that we can't move from where we
> are to some other specified place, like a previous or parent, from the
> word that is invoked and does the work on a specific dictionary entry.

But they *are* being traversed in the sense that we are traveling
through the wordlist *in some way*. For me, I would prefer to only
specify that more recent words of the same name are encountered before
less recently defined words of that name ~ not to specify that it is
traversed in reverse order of addition to the wordlist.

> (Equally, "iterate" might imply some order, which is true in my
> Forth's case, but not all.)

To me the "iterate" implies a linear sequence, just as the:
first-entry ( wid -- nt flag )
next-entry ( nt1 -- nt2 flag )

... approach seems to do. A traverse only implies that you pass
through in some order, and traversing a hashed wordlist by stepping to
each bucket in turn, and for non-empty buckets stepping through their
collision chains ... that's every bit as much a traverse as traversing
a linked list by starting at one end and getting the next entry until
you are at the other end.

[Alex McDonald]

On Jan 19, 2:48 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Alex McDonald <b...@rivadpm.com> writes:
> >On Jan 19, 1:37=A0pm, BruceMcF <agil...@netscape.net> wrote:
> >> On Jan 19, 6:03=A0am, Alex McDonald <b...@rivadpm.com> wrote:
> >> >> nt>compile ( nt -- x xt )
> >> > What is x in the diagram nt>compile ( nt -- x xt )?
>
> >> It is an opaque input to xt in that behavior ~ it is often the execute
> >> xt, with the xt on top being COMPILE, but it can also be an xt that
> >> performs a special compilation action with the xt on the top of the
> >> stack performing EXECUTE on that compilation action xt. And it could
> >> in general be anything.
>
> >The xt should know what it needs to do without external assistance --
> >i.e. it should do only one thing, which is return the compilation
> >behaviour.
>
> Sure, it's possible to have, for every word with default compilation
> semantics (e.g., "+"), a routine that compiles it, i.e. equivalent to
>
> :noname ['] + compile, ;
>
> and it would give us a more symmetric and elegant way to deal with
> interpretation and compilation semantics.  But it seems preferable to
> me to have a slightly less elegant interface and avoid the need to
> create such a routine for every word with default compilation
> semantics (i.e., the vast majority of words).

The result of nt>compile and nt>execute in that case would be the same
xt; then it's not necessary to have separate compilation semantics. At
least, I can't see the need for such gymnastics.

[Anton Ertl]

Alex McDonald <bl...@rivadpm.com> writes:
>On Jan 19, 2:48=A0pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)

>wrote:
>> Alex McDonald <b...@rivadpm.com> writes:

>> >On Jan 19, 1:37=3DA0pm, BruceMcF <agil...@netscape.net> wrote:

>> >> On Jan 19, 6:03=3DA0am, Alex McDonald <b...@rivadpm.com> wrote:
>> >> >> nt>compile ( nt -- x xt )
>> >> > What is x in the diagram nt>compile ( nt -- x xt )?
>>
>> >> It is an opaque input to xt in that behavior ~ it is often the execute
>> >> xt, with the xt on top being COMPILE, but it can also be an xt that
>> >> performs a special compilation action with the xt on the top of the
>> >> stack performing EXECUTE on that compilation action xt. And it could
>> >> in general be anything.
>>
>> >The xt should know what it needs to do without external assistance --
>> >i.e. it should do only one thing, which is return the compilation
>> >behaviour.
>>
>> Sure, it's possible to have, for every word with default compilation
>> semantics (e.g., "+"), a routine that compiles it, i.e. equivalent to
>>
>> :noname ['] + compile, ;
>>
>> and it would give us a more symmetric and elegant way to deal with

>> interpretation and compilation semantics. =A0But it seems preferable to

>> me to have a slightly less elegant interface and avoid the need to
>> create such a routine for every word with default compilation
>> semantics (i.e., the vast majority of words).
>
>The result of nt>compile and nt>execute in that case would be the same
>xt;

Then you cannot perform the compilation semantics with EXECUTE,
whereas with the x xt approach you can.

It seems that you would have us perform the compilation semantics by
using COMPILE, (instead of EXECUTE) on the result of NT>COMPILE. Now
let's consider what would happen for words with non-default
compilation semantics, like IF. By performing the compilation
semantics with NT>COMPILE ( xt ) COMPILE, you get an orig on the
control-flow stack. That COMPILE, is not behaving according to the
standard stack comment.

Ok, one might argue that the xt is not derived in a standard way, so a
standard system is allowed to do anything with it; still, I don't see
the advantage over the other approach: In the COMPILE, approach I have
to have a different code path for performing the compilation
semantics, because I use a different word for performing (COMPILE,
instead of EXECUTE), in the double-cell approach I need a different
code path because the stack effect is different somewhere in there.

>then it's not necessary to have separate compilation semantics. At
>least, I can't see the need for such gymnastics.

There is some gymnastics necessary in any case, the question is where.

[Anton Ertl]

Bernd Paysan <bernd....@gmx.de> writes:
>Yes, that's the point - have an early exit from the iteration without
>requiring that each invocation has to return a flag. If you iterate
>over all words, you would not do the THROW at all.

Sure, that's possible. It would mean that such iteration words would
require the EXCEPTION wordset (at least if premature EXIT is desired),
but that may be a good idea anyway.

It's not clear that this is the better way, though. Ok, you get rid
of a TRUE if there is no early exit, but it seems to me that the code
becomes longer and more complex (especially wrt stack depth
correctness) if there can be an early exit, especially if there are
stack items that are passed through.

[Alex McDonald]

On Jan 19, 5:16 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)

OK, that I understand.

I've done it at a lower level, since COMPILE, and the header structure
gets the brunt of working out what to do with this xt. By keeping a
pointer before the xt, we can find the compilation token in the
header. Shown is a word where the compilation semantics are the
execution semantics.

begin-structure head%
...
lfield: head.comp \ [ gen "call" ] comp token; normally
generate a CALL
lfield: head.ct \ +---> [ ' compile, ] compile token action
lfield: head.xtptr \ | [ ptr to xt ] pointer to the xt
... \ |
end-structure \ |
\ |
\ +---- [ ct-off ] rel offset to head.ct
\ [ xt ] code (the xt)


: >ct ( xt -- ct ) dup cell- @ + ; \ given an xt, get the
ct
: >comp ( xt -- comp ) >ct cell- ; \ point to the comp
field
: compile, ( xt -- ) dup >comp @ execute ; \ compile xt on the
stack
: postpone, ( xt -- ) >ct 2@ execute ; \ fetch xt, execute the
ct

[BruceMcF]

On Jan 19, 12:16 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)

wrote:
> Alex McDonald <b...@rivadpm.com> writes:

>>then it's not necessary to have separate compilation semantics. At
>>least, I can't see the need for such gymnastics.

> There is some gymnastics necessary in any case, the question is where.

In particular, producer or consumer? I prefer the gymnastics in the
producer, so that the consumer does not have to program defensively
against a range of cases.

[BruceMcF]

On Jan 19, 12:13 pm, Alex McDonald <b...@rivadpm.com> wrote:
> The result of nt>compile and nt>execute in that case would be the same
> xt; then it's not necessary to have separate compilation semantics. At
> least, I can't see the need for such gymnastics.

"in that case" ~ therefore you would need a flag to indicate which
case is which. And then the specification of that flag has to forsee
all the distinct cases that might arise in a more complex
implementation.

The ( x xt ) approach avoids the need to flag cases, since every case
is the same at the level of the consumer: "execute xt on x". In a
simple implementation, the xt is returned as "x", then the immediate
flag is read, then if it is immediate the EXECUTE "xt" is return while
if it is not, the COMPILE, xt is returned.

If that does not suffice for some more complex implementation, then
the more complex implementation can provide a procedure to cope with
each of the more complex cases and return the xt that goes with each
case.

So, while it supports more complex implementations, it does not put
undue burden on small free standing implementations, and it does not
require the consumer to sort through a range of cases that may be
returned.

[Rod Pemberton]

"Alex McDonald" <bl...@rivadpm.com> wrote in message
news:5ecf1895-1629-44df...@u2g2000vbe.googlegroups.com...

> On Jan 19, 8:10 am, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
> wrote:

...

> > If I were deciding on the basic functionality I needed for traversing
> > a linked-list in Forth, I'd at least want the following:
>
> While they're suitable for traversing a linked list, many

> dictionaries/wordlists/vocabularies are not based on [linked lists],

> and it would presume a doubly linked list to support such a traversal
> scheme. For instance, some are hash only, others hash & single linked
> lists.

No, "it" wouldn't presume a doubly-linked list. The words would be
available for a doubly-linked list, e.g., for non-dictionary use too. If
the words were dictionary use only, then things change a bit, which is why I
didn't state for dictionary use. Let's assume they are dictionary use only.
If there was a singly-linked dictionary list, then the words for the
incorrect direction could be defined to do nothing. If there are no links
at all in the dictionary, i.e., hash, then the traversal words wouldn't need
to do anything would they? I.e., there is no traversing since there is no
need to traverse. The entire point of traversing is to locate the node. If
the hash or some other function does it for you and they are dictionary use
only, why define them to do something? The code used to confirm the correct
node via traversal would likely work differently on a hash system and call
the hash lookup and verify the correct node. I.e., the Forth traversal code
probably would have zero code changes for the node check on a hash system,
with only the traversal words being defined to do nothing. You'd only need
to work through a few sets of traversal word definitions and routines to
confirm the words with host specific definitions work for multiple
implementations. The standard would only need to support the top two or
three or four methods of dictionary implementations. Keeping with the Forth
"as generic as possible" spirit, I don't think dictionary specific words
should be created, unless absolutely required.


Rod Pemberton

[Bernd Paysan]

Anton Ertl wrote:

> Bernd Paysan <bernd....@gmx.de> writes:
>>Yes, that's the point - have an early exit from the iteration without
>>requiring that each invocation has to return a flag. If you iterate
>>over all words, you would not do the THROW at all.
>
> Sure, that's possible. It would mean that such iteration words would
> require the EXCEPTION wordset (at least if premature EXIT is desired),
> but that may be a good idea anyway.
>
> It's not clear that this is the better way, though. Ok, you get rid
> of a TRUE if there is no early exit, but it seems to me that the code
> becomes longer and more complex (especially wrt stack depth
> correctness) if there can be an early exit, especially if there are
> stack items that are passed through.

Well, it's a tradeoff. The code of the iterating word itself is less
complex, because it doesn't have to deal with premature exits. The code
for an iterator with premature exit is more complex when it wants to
return something (and the whole point of a premature exit usually *is*
to return something).

So from a usability point of view, returning the flag is better - non-
stop iterators simply say true at their end, and be done with it.

--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[Elizabeth D. Rather]

On 1/19/12 12:50 PM, Rod Pemberton wrote:
...

> Keeping with the Forth
> "as generic as possible" spirit, I don't think dictionary specific words
> should be created, unless absolutely required.

I don't recognize such a spirit. IMO the philosophy is to avoid
unnecessary generalization; solve only the problem at hand.

As someone noted, most Forths have a WORDS display of words in the
current search order (often with multiple options, such as words
containing or starting with a particular string) as user conveniences.
They all have the ability for the text interpreter to do searches. These
necessarily imply some sort of wordlist navigation. It would be hard to
standardize, though, because approaches to dictionary and wordlist
organization vary a lot.

If you need to traverse a doubly-linked list of some sort, you should
develop the necessary machinery to do that, but given that the vast
majority of Forth dictionaries are *not* doubly linked, it would be very
inappropriate to complicate words intended for the dictionary in that way.

[BruceMcF]

On Jan 19, 5:50 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
wrote:

> No, "it" wouldn't presume a doubly-linked list.  The words would be
> available for a doubly-linked list, e.g., for non-dictionary use too.
> If the words were dictionary use only, then things change a bit,
> which is why I didn't state for dictionary use.  Let's assume they
> are dictionary use only.

Since the original question is traversing a wordlist ~ lets assume
that they *are* for dictionary use, and would be for a linked list if
the dictionary happened to be implemented that way.

> If there was a singly-linked dictionary list, then the words for the
> incorrect direction could be defined to do nothing.  If there are no
> links at all in the dictionary, i.e., hash, then the traversal words
> wouldn't need to do anything would they?  I.e., there is no
> traversing since there is no need to traverse.  The entire point of
> traversing is to locate the node.

No, the point of traversing is to traverse through the wordlist. If
the wordlist is not organized as nodes in a linked list, then a linked-
list traverse would fail to traverse *the wordlist*.

> If the hash or some other function does it for you and they are
> dictionary use only, why define them to do something?  The code used
> to confirm the correct node via traversal would likely work
> differently on a hash system and call the hash lookup and verify the
> correct node.

What do you mean "find *the* correct node"? What if you wanted to do
something with *every* entry in the wordlist (as with WORDS)? What if
you wanted to do something with *a set of* words in the wordlist (eg,
"all words beginning with the character .")?

> I.e., the Forth traversal code probably would have zero code changes
> for the node check on a hash system, with only the traversal words
> being defined to do nothing.

If the traversal words are defined to do nothing, then they will not
be traversal words, because they will not traverse the wordlist.

> You'd only need to work through a few sets of traversal word
> definitions and routines to confirm the words with host specific
> definitions work for multiple implementations.  The standard would
> only need to support the top two or three or four methods of
> dictionary implementations.

That would be inappropriate for standardization at the language level.
It would be workable for a library standard that was was willing to
confine itself to implementations that followed those particular
methods of implementation.

> Keeping with the Forth "as generic as possible" spirit, I don't think
> dictionary specific words should be created, unless absolutely
> required.

I try to parse this sentence, but it does not seem to make sense to
me. It seems to argue that the reason we shouldn't have as generic
wordlist traversal words as possible is because of the spirit of
keeping things as generic as possible.

[BruceMcF]

On Jan 19, 6:01 pm, Bernd Paysan <bernd.pay...@gmx.de> wrote:
> Anton Ertl wrote:

> > Bernd Paysan <bernd.pay...@gmx.de> writes:
> >>Yes, that's the point - have an early exit from the iteration without
> >>requiring that each invocation has to return a flag.  If you iterate
> >>over all words, you would not do the THROW at all.
>
> > Sure, that's possible.  It would mean that such iteration words would
> > require the EXCEPTION wordset (at least if premature EXIT is desired),
> > but that may be a good idea anyway.
>
> > It's not clear that this is the better way, though.  Ok, you get rid
> > of a TRUE if there is no early exit, but it seems to me that the code
> > becomes longer and more complex (especially wrt stack depth
> > correctness) if there can be an early exit, especially if there are
> > stack items that are passed through.
>
> Well, it's a tradeoff.  The code of the iterating word itself is less
> complex, because it doesn't have to deal with premature exits.  The
> code for an iterator with premature exit is more complex when it
> wants to return something (and the whole point of a premature exit
> usually *is* to return something).

> So from a usability point of view, returning the flag is better - non-
> stop iterators simply say true at their end, and be done with it.

traverse-wordlist ( x*i xt wid -- x'*i u )
... where xt ( x*i nt -- x'*i u ), halt the traversal unless u=0.

nt>name ( nt -- ca u )
nt>execute ( nt -- xt )

[Krishna Myneni]

On Jan 19, 8:00 am, JennyB <jennybr...@googlemail.com> wrote:
> Goedel's Incompleteness Theorem?

First or second?

It's an interesting proposition. If we take the language standard,
e.g. ANS Forth standard, as the set of postulates, I wonder if a
statement to the effect that Forth is or is not capable of providing
such and such a feature, can be shown to be provable, i.e. logically
deduced.

Bernd has provided an example of such a statement, which is provable,
although he did not provide the formal proof:

Theorem: If an ANS-Forth system provides WORDS, then it must be
capable of performing an (ordered) traversal of a wordlist.

Now, the spec for WORDS does not specify any ordering, but in order
for the Forth system to be standard, i.e. compile the most recent
definition of a word, then the ordered search is implied, and the fact
that WORDS exists means that a traversal through the entire wordlist
is possible.

What if we take away the requirement that an ANS-Forth system provides
WORDS? Then, is the above theorem valid? That is, is there a logical
proof which can be deduced from the postulates (the declarations of
the standard) that the system is capable of performing an ordered
traversal of a wordlist? I expect the answer is yes, but would have to
think about the proof.

In any case, Goedel is not preventing any system implementor from
providing such a feature!

Krishna

[Krishna Myneni]

On Jan 19, 5:48 pm, "Elizabeth D. Rather" <erat...@forth.com> wrote:
> On 1/19/12 12:50 PM, Rod Pemberton wrote:
> ...
>
> > Keeping with the Forth
> > "as generic as possible" spirit, I don't think dictionary specific words
> > should be created, unless absolutely required.
>
> I don't recognize such a spirit. IMO the philosophy is to avoid
> unnecessary generalization; solve only the problem at hand.
>

Unfortunately, that is a self-limiting philosophy... appropriate for
tackling a specific requirement at hand, but not for evolving the
language to be functional in a wider range of environments
(application and development contexts).

Krishna

[Krishna Myneni]

On Jan 19, 7:32 pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> On Jan 19, 8:00 am, JennyB <jennybr...@googlemail.com> wrote:
>
> > Goedel's Incompleteness Theorem?
>
> First or second?
>
> It's an interesting proposition. If we take the language standard,
> e.g. ANS Forth standard, as the set of postulates, I wonder if a
> statement to the effect that Forth is or is not capable of providing
> such and such a feature, can be shown to be provable, i.e. logically
> deduced.
>
> Bernd has provided an example of such a statement, which is provable,
> although he did not provide the formal proof:
>
> Theorem: If an ANS-Forth system provides WORDS, then it must be
> capable of performing an (ordered) traversal of a wordlist.
>
> Now, the spec for WORDS does not specify any ordering, but in order
> for the Forth system to be standard, i.e. compile the most recent
> definition of a word, then the ordered search is implied, and the fact
> that WORDS exists means that a traversal through the entire wordlist
> is possible.
>
> What if we take away the requirement that an ANS-Forth system provides
> WORDS? Then, is the above theorem valid?

Let's tighten up our theorem to be proven.

DEFINITION: An "ordered traversal" of a wordlist is a procedure by
which a representation of every word present in the wordlist is
obtained once and once only, and the order by which each word's
representation is obtained is either in the order by which it has been
added to the wordlist, or in the reverse order.

THEOREM: Any Forth system which is consistent with the ANS-Forth
standard, and which provides the CORE and SEARCH ORDER wordsets is
capable of performing an ordered traversal of a wordlist.


Krishna

[Elizabeth D. Rather]

Well, it was Chuck's mantra, and has been influential to a generation of
Forth programmers.

It's fair to say that Chuck's ambition has never at any time been "to
evolve the language to be functional in a wider range of environments."
He (and his followers) have been content to have a simple and nimble
language with which to tackle the problem at hand. Not surprisingly, as
different problem domains have presented themselves over the years, the
language *has*, in fact, acquired more capabilities in different areas,
and long-time practitioners have developed personal libraries reflecting
capabilities needed by the projects they've done.

The Forth community has, of course, failed to promulgate a lot of those
capabilities and personal libraries as much as perhaps we should,
although FORTH, Inc, MPE, and probably other individuals and
organizations that see a lot of different projects have ways of sharing
within their communities (e.g. as libraries and options included with
their products).

But I would argue that a lot of Forth's efficiency and nimbleness is a
result of our avoiding the temptation to try to add a lot of generalized
features on spec or because other languages have them.

[Alex McDonald]

Unless you wish to indicate that there was an early termination by xt
to the caller of traverse-wordlist, the u in its stack diagram is
superfluous. It might be useful to indicate that (for instance) a
count is invalid, but strictly it's not required.

A minor correction on the halt condition of xt which should read "halt
the traversal if u=false".

[Rod Pemberton]

"BruceMcF" <agi...@netscape.net> wrote in message
news:dfa75e25-51ff-4d79...@f1g2000yqi.googlegroups.com...
...

> What if you wanted to do something with *every* entry in
> the wordlist (as with WORDS)?

How do hash based dictionaries do that now? Supposedly, from what a couple
people have just now stated, hash dictionaries are not linked ... If their
dictionaries aren't linked somehow, they aren't traversable are they? If
they aren't linked, WORDS wouldn't work. If WORDS does work, then they are
linked somehow, and therefore basic traversal words should work. Yes?
I.e., the linking may not be a pointer for a hash based system, but there is
some method to progress to the next dictionary entry. Somesuch behavior is
required to implements WORDS. Most likely, this behavior is "hidden" on
hash based systems and needs to be exposed via acceptable Forth words.

> What if you wanted to do something with *a set of* words
> in the wordlist (eg, "all words beginning with the character .")?

I don't see any issue here. Matching of the words is a separate operation
whether exact or with wildcards. I'd say it's *much* more difficult on a
hash based dictionary. I.e., no wildcard use possible with the hash ...
That could imply hash based dictionaries have a secondary matching method,
i.e., string compare. Of course, they do have a string compare to eliminate
hash collisions. So, if WORDS works for hash based dictionary implying a
linked-list and hash based dictionaries have a string compare operation,
then we are back to being able to traverse dictionaries via the old
linked-list method for all systems. Aren't we?

> > You'd only need to work through a few sets of traversal word
> > definitions and routines to confirm the words with host specific
> > definitions work for multiple implementations. The standard would
> > only need to support the top two or three or four methods of
> > dictionary implementations.
>
> That would be inappropriate for standardization at the language level.

Then, there is no point in entertaining the OP's original question, is
there? That's ignoring the fact that that reasoning would nullify the
entire purpose of and reason for the fig-Forth, F-79, F-83, and ANS Forth
specifications ... Everything they standardized would be inappropriate by
your reasoning.

> > Keeping with the Forth "as generic as possible" spirit, I don't think
> > dictionary specific words should be created, unless absolutely
> > required.
>
> I try to parse this sentence, but it does not seem to make sense to
> me. It seems to argue that the reason we shouldn't have as generic
> wordlist traversal words as possible is because of the spirit of
> keeping things as generic as possible.

I said that IMO Forth words for traversing linked-lists are appropriate, but
Forth words only for traversing dictionary entries aren't, because their
specificity violates the Forth ideology AIUI.


Rod Pemberton

[Anton Ertl]

Krishna Myneni <krishna...@ccreweb.org> writes:
>It's an interesting proposition. If we take the language standard,
>e.g. ANS Forth standard, as the set of postulates, I wonder if a
>statement to the effect that Forth is or is not capable of providing
>such and such a feature, can be shown to be provable, i.e. logically
>deduced.

You would have to formalize the standard to do such a thing, a job
that even the mathematophile Haskell people have not done completely.
And what you might then be able to prove is that a standard program
cannot do this ("Forth" is a wider concept IMO).

>Theorem: If an ANS-Forth system provides WORDS, then it must be
>capable of performing an (ordered) traversal of a wordlist.
>
>Now, the spec for WORDS does not specify any ordering, but in order
>for the Forth system to be standard, i.e. compile the most recent
>definition of a word, then the ordered search is implied, and the fact
>that WORDS exists means that a traversal through the entire wordlist
>is possible.

Yes, that's the informal argument. The claim is simple enough that
this argument should be convincing, in which case we don't need the
convincing powers of a formal proof (which, BTW, often convince people
of wrong things).

>What if we take away the requirement that an ANS-Forth system provides
>WORDS? Then, is the above theorem valid? That is, is there a logical
>proof which can be deduced from the postulates (the declarations of
>the standard) that the system is capable of performing an ordered
>traversal of a wordlist? I expect the answer is yes, but would have to
>think about the proof.

Theoretical possibility is not the most important question when it
comes to standardizing a feature. Of course, the feature must be
theoretically possible; next it must be practically possible (not too
expensive to implement in time and space), and the WORDS argument
already shows that; then there is the question of common practice, and
we don't have that yet.

Of course, if you are theoretically inclined, you want to get rid of
as many premises as possible, but in this case the result is then only
interesting to theorists.

[Anton Ertl]

Bernd Paysan <bernd....@gmx.de> writes:
>So from a usability point of view, returning the flag is better - non-
>stop iterators simply say true at their end, and be done with it.

I agree. And if somebody wants to use THROW to exit early, they still
can: Just put TRUE at the end of the called word, and use THROW for
the early exit.

[Alex McDonald]

On Jan 20, 11:06 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

Are there any Forth systems that don't support some form of WORDS?
That would surely be the common practice we're looking for.

I may be wrong, and I have been very wrong before on what Forth folks
find irresistible, but I suspect that given a standardised traverse-
wordlist (and yes Bruce, the name is growing on me), most system
implementors of WORDS would find it hard to avoid.

[Alex McDonald]

On Jan 19, 10:50 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
wrote:
> "Alex McDonald" <b...@rivadpm.com> wrote in message

I can't see this working in practice, since the generic "traversal"
words you propose are like methods of multiple classes operating
against objects. While that's possible, it's certainly not desirable
since it's not simple, and it adds a big layer of cruft over what is a
very simple proposal for a single word.

[Albert van der Horst]

In article <ef364a63-7b8c-4752...@18g2000vbx.googlegroups.com>,
Alex McDonald <bl...@rivadpm.com> wrote:
>On Jan 19, 1:50=A0pm, BruceMcF <agil...@netscape.net> wrote:

>> On Jan 19, 6:08=A0am, Alex McDonald <b...@rivadpm.com> wrote:
>>
>> > While they're suitable for traversing a linked list, many dictionaries/

>> > wordlists/vocabularies are not based on them, and it would presume a

>> > doubly linked list to support such a traversal scheme. For instance,
>> > some are hash only, others hash & single linked lists.
>>

>> As long as the hash dictionaries have collision chains that would
>> apply to redefinitions in the same wordlist, so that the most recent
>> definition under a same name in the same dictionary is
>> distinguishable, then couldn't a traversal entail stepping through the
>> hash buckets in a set sequence, filtering out entries that are not in
>> the desired dictionary?
>
>Which is exactly what some Forths do. Win32Forth (and in my Forth,
>from which it's derived) produce a WORDS list that is in most recent
>to least recent definition order from its hash-entry-plus-lists-for-
>collisions tables. But there is no concept of previous or next from
>one entry to another.
>
>Gforth hashes everything into the same hash table. What information is
>derivable from it, and how would it be "traversed"?
>

>That's why I'm not too fond of the name "traverse-wordlist". Wordlists
>are not being traversed, in the sense that we can't move from where we
>are to some other specified place, like a previous or parent, from the
>word that is invoked and does the work on a specific dictionary entry.

>(Equally, "iterate" might imply some order, which is true in my
>Forth's case, but not all.)

If I look at python I see dict's that are essentially hash tables.
It is customary to be able to do "something" for each element in
a dict, and the facility to do so is called an "iterator".
A similar facility is available in Java. So I think iterate/iterator
is a suitable name.

E.g. (Python)
for x in my_dict:
print x,my_dict[x]

prints all items in the dict, in an indeterminate order.
(The underlying system keeps track of what has been used up.)




--
--
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[Krishna Myneni]

On Jan 20, 5:06 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Krishna Myneni <krishna.myn...@ccreweb.org> writes:
> >It's an interesting proposition. If we take the language standard,
> >e.g. ANS Forth standard, as the set of postulates, I wonder if a
> >statement to the effect that Forth is or is not capable of providing
> >such and such a feature, can be shown to be provable, i.e. logically
> >deduced.
>
> You would have to formalize the standard to do such a thing, a job
> that even the mathematophile Haskell people have not done completely.
> And what you might then be able to prove is that a standard program
> cannot do this ("Forth" is a wider concept IMO).
>

Perhaps I'm wrong, but the goal of "formalizing" simply means to make
precise, i.e. free of ambiguity, using a standard terminology. The
standard does not have to be expressed in mathematical notation or use
mathematical terminology to be formal -- when applicable, the use of
such devices simply helps to free statements of ambiguity. We are
always running up against ambiguity in the statements of
specifications for certain words. Tightening up those specs *is* the
practice of formalization. Even without complete precision in a
language standard, which can probably never be achieved, one can still
make *convincing* logical arguments using the statements in the
standard as the postulates.

> >Theorem: If an ANS-Forth system provides WORDS, then it must be
> >capable of performing an (ordered) traversal of a wordlist.
>
> >Now, the spec for WORDS does not specify any ordering, but in order
> >for the Forth system to be standard, i.e. compile the most recent
> >definition of a word, then the ordered search is implied, and the fact
> >that WORDS exists means that a traversal through the entire wordlist
> >is possible.
>
> Yes, that's the informal argument.  The claim is simple enough that
> this argument should be convincing, in which case we don't need the
> convincing powers of a formal proof (which, BTW, often convince people
> of wrong things).
>

If the above argument is free of ambiguity, it *becomes* a formal
proof.

> >What if we take away the requirement that an ANS-Forth system provides
> >WORDS? Then, is the above theorem valid? That is, is there a logical
> >proof which can be deduced from the postulates (the declarations of
> >the standard) that the system is capable of performing an ordered
> >traversal of a wordlist? I expect the answer is yes, but would have to
> >think about the proof.
>
> Theoretical possibility is not the most important question when it
> comes to standardizing a feature.  Of course, the feature must be
> theoretically possible; next it must be practically possible (not too
> expensive to implement in time and space), and the WORDS argument
> already shows that; then there is the question of common practice, and
> we don't have that yet.
>

I'm just posing an academic question. I agree -- a proof of the
statement, " *Any* Forth system, consistent with the ANS Forth
standard, and providing X can implement wordlist traversal", does not
need to be given in order to standardize traversal and node
information words. We know that it is possible for many types of
implementations of Forth systems, which are consistent with the
standard, to provide such words. IMO, that is a sufficient condition.
As I said, Goedel is not tying the hands of system implementers.

> Of course, if you are theoretically inclined, you want to get rid of
> as many premises as possible, but in this case the result is then only
> interesting to theorists.
>

Many times, proofs also have practical value as well.

> - anton


Krishna

[BruceMcF]

Except when providing a function that can be functional in a wider
range of environments *is* the problem at hand. Then "solve the
problem at hand" would suggest solving the problem of being functional
in a wider range of environments.

[BruceMcF]

On Jan 20, 5:52 am, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
wrote:

> How do hash based dictionaries do that now?  Supposedly, from what a
> couple people have just now stated, hash dictionaries are not linked
> ...  If their dictionaries aren't linked somehow, they aren't
> traversable are they?

Of course they are.

> If they aren't linked, WORDS wouldn't work.  If WORDS does work, then
> they are linked somehow, and therefore basic traversal words should
> work.  Yes?

Of course not. If you know where the set of hash buckets is located,
you do not need to link the hash buckets together, you can just look
in each hash bucket, one after the other.

The rest snipped unread as if you think its impossible to traverse a
set of hash buckets, it doesn't seem like you are in a position to
suggest a set of behaviors that would work for a hashed dictionary
except by accident.

[BruceMcF]

On Jan 20, 5:19 am, Alex McDonald <b...@rivadpm.com> wrote:

>> traverse-wordlist ( x*i xt wid -- x'*i u )
>> ... where xt ( x*i nt -- x'*i u ), halt the traversal unless u=0.

> Unless you wish to indicate that there was an early termination by xt
> to the caller of traverse-wordlist, the u in its stack diagram is
> superfluous.

I agree: take away the purpose of u, and the u is superfluous. If u=0,
then the traversal ran the full course of the wordlist, if u<>0, then
the traversal was halted by execution of xt on one of the nt's of the
items in the wordlist, and that final execution of xt returned the
value u, which is not 0.

It is best if nt is defined as an unsigned nonzero integer, so that if
the traversal is to find a specific entry, then the nt can be returned
when the search succeeds to terminate the traversal.

> It might be useful to indicate that (for instance) a
> count is invalid, but strictly it's not required.

> A minor correction on the halt condition of xt which should read "halt
> the traversal if u=false".

No, as I said, its a "halt?" value, not a "continue?" value. Since
"not halting" is a non-exceptional result for the traverse, "don't
halt" is assigned 0, and "halt" is assigned to every value other than
0.

[Alex McDonald]

On Jan 20, 2:46 pm, BruceMcF <agil...@netscape.net> wrote:
> On Jan 20, 5:19 am, Alex McDonald <b...@rivadpm.com> wrote:
>
> >> traverse-wordlist ( x*i xt wid -- x'*i u )
> >> ... where xt ( x*i nt -- x'*i u ), halt the traversal unless u=0.
> > Unless you wish to indicate that there was an early termination by xt
> > to the caller of traverse-wordlist, the u in its stack diagram is
> > superfluous.
>
> I agree: take away the purpose of u, and the u is superfluous. If u=0,
> then the traversal ran the full course of the wordlist, if u<>0, then
> the traversal was halted by execution of xt on one of the nt's of the
> items in the wordlist, and that final execution of xt returned the
> value u, which is not 0.
>
> It is best if nt is defined as an unsigned nonzero integer, so that if
> the traversal is to find a specific entry, then the nt can be returned
> when the search succeeds to terminate the traversal.

That's the function of FIND.

>
> > It might be useful to indicate that (for instance) a
> > count is invalid, but strictly it's not required.
> > A minor correction on the halt condition of xt which should read "halt
> > the traversal if u=false".
>
> No, as I said, its a "halt?" value, not a "continue?" value. Since
> "not halting" is a non-exceptional result for the traverse, "don't
> halt" is assigned 0, and "halt" is assigned to every value other than
> 0.

Which leads to

: xt ( i nt -- i' flag )
drop 1+ dup 10 < ;
0 ' xt wid traverse-wordlist

Counter-intuitively, xt halts on the first node, not on the 10th.

[Alex McDonald]

On Jan 20, 3:56 pm, Alex McDonald <b...@rivadpm.com> wrote:
> On Jan 20, 2:46 pm, BruceMcF <agil...@netscape.net> wrote:
>
>
>
>
>
>
>
>
>
> > On Jan 20, 5:19 am, Alex McDonald <b...@rivadpm.com> wrote:
>
> > >> traverse-wordlist ( x*i xt wid -- x'*i u )
> > >> ... where xt ( x*i nt -- x'*i u ), halt the traversal unless u=0.
> > > Unless you wish to indicate that there was an early termination by xt
> > > to the caller of traverse-wordlist, the u in its stack diagram is
> > > superfluous.
>
> > I agree: take away the purpose of u, and the u is superfluous. If u=0,
> > then the traversal ran the full course of the wordlist, if u<>0, then
> > the traversal was halted by execution of xt on one of the nt's of the
> > items in the wordlist, and that final execution of xt returned the
> > value u, which is not 0.
>
> > It is best if nt is defined as an unsigned nonzero integer, so that if
> > the traversal is to find a specific entry, then the nt can be returned
> > when the search succeeds to terminate the traversal.
>
> That's the function of FIND.

Addedndum; I think you're conflating the 'u's. There is nothing to
prevent

traverse-wordlist ( x*i xt wid -- x'*i 0|nt )

where 0 indicates complete traversal, and nt is the value of the early
terminating node. Since traverse-wordlist knows the nt it's handing
off to xt, that's not an issue. Then we can still have

xt ( x*i nt -- x'*i flag )

where flag is "continue?" and the only meaningful values are non-zero
(yes) or zero (no).

[BruceMcF]

On Jan 20, 10:56 am, Alex McDonald <b...@rivadpm.com> wrote:
>> I agree: take away the purpose of u, and the u is superfluous. If
>> u=0, then the traversal ran the full course of the wordlist, if
>> u<>0, then the traversal was halted by execution of xt on one of the
>> nt's of the items in the wordlist, and that final execution of xt
>> returned the value u, which is not 0.

>> It is best if nt is defined as an unsigned nonzero integer, so that
>> if the traversal is to find a specific entry, then the nt can be
>> returned when the search succeeds to terminate the traversal.

> That's the function of FIND.

No, the function of FIND is to (1) determine if the word is in the
current namespace and, (2) if so, return the XT and the immediate
status.

There is no necessary connection between the XT returned and anything
else about the word entry in the dictionary.

>> No, as I said, its a "halt?" value, not a "continue?" value. Since
>> "not halting" is a non-exceptional result for the traverse, "don't
>> halt" is assigned 0, and "halt" is assigned to every value other than
>> 0.

> Which leads to

> : xt ( i nt -- i' flag )
>   drop 1+ dup 10 < ;
> 0 ' xt wid traverse-wordlist

> Counter-intuitively, xt halts on the first node, not on the 10th.

Its only counter-intuitive if you think of it as a continue?
condition. If you think of it as a halt? condition, its intuitive.
Halt when the count is less than 10? 1 is less than 10.

[Anton Ertl]

Krishna Myneni <krishna...@ccreweb.org> writes:
>On Jan 20, 5:06=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)

>wrote:
>> Krishna Myneni <krishna.myn...@ccreweb.org> writes:
>> >It's an interesting proposition. If we take the language standard,
>> >e.g. ANS Forth standard, as the set of postulates, I wonder if a
>> >statement to the effect that Forth is or is not capable of providing
>> >such and such a feature, can be shown to be provable, i.e. logically
>> >deduced.
>>
>> You would have to formalize the standard to do such a thing, a job
>> that even the mathematophile Haskell people have not done completely.
>> And what you might then be able to prove is that a standard program
>> cannot do this ("Forth" is a wider concept IMO).
>>
>
>Perhaps I'm wrong, but the goal of "formalizing" simply means to make
>precise, i.e. free of ambiguity, using a standard terminology. The
>standard does not have to be expressed in mathematical notation or use
>mathematical terminology to be formal

Yes, but: It's not going to be less work, and you would then have to
use your non-mathematical notation in your formal proofs, which even
fewer people would understand and check than if you used "mathematical
notation" (actually mathematicians and theoretical computer scientists
invent new notation all the time, but they typically base it on more
established mathematical notation).

[Anton Ertl]

Alex McDonald <bl...@rivadpm.com> writes:
>On Jan 20, 11:06=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
>wrote:

>> Theoretical possibility is not the most important question when it

>> comes to standardizing a feature. =A0Of course, the feature must be

>> theoretically possible; next it must be practically possible (not too
>> expensive to implement in time and space), and the WORDS argument
>> already shows that; then there is the question of common practice, and
>> we don't have that yet.
>
>Are there any Forth systems that don't support some form of WORDS?
>That would surely be the common practice we're looking for.

WORDS is more than common practice, WORDS is in the standard. But the
feature we are discussing, is not WORDS, but more general wordlist
traversal; that may be common practice, but if it is, we do not yet
have common words for it.

[Stephen Pelc]

On Mon, 16 Jan 2012 04:36:26 -0800 (PST), Krishna Myneni
<krishna...@ccreweb.org> wrote:

>Others must have brought up this question previously, but I'm
>wondering why there are no standard words in Forth for traversing a
>wordlist and obtaining basic information about each node?

VFX provides a number of words for this sort of stuff. They are used
15 times in the code tree, and always in conjunction with other
implementation-specific words such as displaying a word name or
a cross-reference structure.

In order to standardise dictionary traversal, you will have
to standardise a slew of other "stuff", nearly all of which
is system-specific "stuff" that probably should not be standardised.

I don't think that it is worth the effort.

Stephen


--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[Krishna Myneni]

On Jan 20, 11:21 am, stephen...@mpeforth.com (Stephen Pelc) wrote:
> On Mon, 16 Jan 2012 04:36:26 -0800 (PST), Krishna Myneni
>

> <krishna.myn...@ccreweb.org> wrote:
> >Others must have brought up this question previously, but I'm
> >wondering why there are no standard words in Forth for traversing a
> >wordlist and obtaining basic information about each node?
>
> VFX provides a number of words for this sort of stuff. They are used
> 15 times in the code tree, and always in conjunction with other
> implementation-specific words such as displaying a word name or
> a cross-reference structure.
>
> In order to standardise dictionary traversal, you will have
> to standardise a slew of other "stuff", nearly all of which
> is system-specific "stuff" that probably should not be standardised.
>
> I don't think that it is worth the effort.
>
> Stephen
>

For the use which I envisioned when I posted the question, which was
to provide a couple of tools to find instances of name reuse in the
search order, I only require two words such as WORDLIST-TRAVERSE
(similar to Alex McDonald's VOC-ITERATE), and another such as >NAME to
get the current word name in the traversal. With just these two words
alone, the Forth standard word, WORDS, can also be written in Forth.
An additional word to obtain information such as xt(s) may permit a
word to be written in Forth to find aliases/synonyms. Allowing remap
of xt(s) of a word may permit more serious applications such as Forth
debuggers to be written in Forth.

But, for now, I'd settle for the ability to traverse the wordlist and
obtain the word name at each node of the traversal. I haven't seen
anything in this thread to suggest that there would be any great
difficulty to providing such words within any existing Forth system.

Regards,
Krishna

[Krishna Myneni]

Exception noted.

Krishna

[Krishna Myneni]

On Jan 20, 10:48 am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

> Alex McDonald <b...@rivadpm.com> writes:
> >On Jan 20, 11:06=A0am, an...@mips.complang.tuwien.ac.at (Anton Ertl)
> >wrote:
> >> Theoretical possibility is not the most important question when it
> >> comes to standardizing a feature. =A0Of course, the feature must be
> >> theoretically possible; next it must be practically possible (not too
> >> expensive to implement in time and space), and the WORDS argument
> >> already shows that; then there is the question of common practice, and
> >> we don't have that yet.
>
> >Are there any Forth systems that don't support some form of WORDS?
> >That would surely be the common practice we're looking for.
>
> WORDS is more than common practice, WORDS is in the standard.  But the
> feature we are discussing, is not WORDS, but more general wordlist
> traversal; that may be common practice, but if it is, we do not yet
> have common words for it.
>
> - anton

...

With the addition of wordlist traversal (WORDLIST-TRAVERSE) and one
additional word to get the name of the current word in the traversal,
one could write WORDS, or just about any variant of it, in Forth!

Krishna

[Stephen Pelc]

On Fri, 20 Jan 2012 10:11:45 -0800 (PST), Krishna Myneni
<krishna...@ccreweb.org> wrote:

>But, for now, I'd settle for the ability to traverse the wordlist and
>obtain the word name at each node of the traversal. I haven't seen
>anything in this thread to suggest that there would be any great
>difficulty to providing such words within any existing Forth system.

Before you can standardise, you need common practice. A good way
to start is to keep a lot of systems on your working PC and to scan
the sources regularly.

The VFX traversal words are:

: WalkWordList \ xt wid --
\ Walk through a wordlist calling the definition XT for each word.
\ The definitions are walked in reverse chronological order.
\ The definition at XT will be passed the THREAD# and NFA.
\ The XT definition has the stack form:
\ *E : MyDef \ thread# nfa -- flag ; Return TRUE to continue

: WalkAllWordLists \ xt-to-call --
\ Call the given XT for each *\fo{WORDLIST}. The callback
\ is given the WID and a flag and will return TRUE to continue
\ the walk or false to abandon it. The FLAG supplied will be
\ TRUE if the WID represents a *\fo{VOCABULARY} and FALSE if
\ the WID represents a child of *\fo{WORDLIST}.
\ : MyDef \ wid flag -- t/f ; return TRUE to continue

: WalkAllWords \ xt --
\ Walk through all wordlists calling the given XT for each word.
\ The definitions are walked in reverse chronological order of
wordlists
\ and then by reverse chronological order within each wordlist.
\ When run, the XT will be passed the THREAD# and NFA.
\ ** The XT definition has the stack form:
\ : MyDef \ thread# nfa -- flag ; return TRUE to continue

[Elizabeth D. Rather]

The evidence shows that one can, and most do, write WORDS without
WORDLIST-TRAVERSE. The factors of WORDS are implementation-dependent and
very diverse. Yes, in theory, everyone could adopt a standard set of
factors and rewrite our WORDS, but I suspect there isn't enough
perceived need to justify doing it.

[BruceMcF]

On Jan 20, 11:13 am, Alex McDonald <b...@rivadpm.com> wrote:
> Addedndum; I think you're conflating the 'u's.

Quite: my suggestion conflated the u's, in that the u returned by the
last xt executed before the traverse halts is the u returned by
traverse-wordlist.

> There is nothing to prevent

> traverse-wordlist ( x*i xt wid -- x'*i 0|nt )

> where 0 indicates complete traversal, and nt is the value of the early
> terminating node.

That's a workable alternative approach. Mine is more general, and
yours may require some recapitulation of what the xt has already done,
but in any event it would only be recapitulated once, and if it makes
for simpler and hence more efficient xt's, they are executed on each
item in the wordlist.

In either event, nt would have to be defined as an unsigned nonzero
number.

[BruceMcF]

On Jan 20, 1:13 pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> Exception noted.

That exception would seem to be the case at hand.

[Marcel Hendrix]

steph...@mpeforth.com (Stephen Pelc) writes Re: Why no standard words for traversing a wordlist?

> On Fri, 20 Jan 2012 10:11:45 -0800 (PST), Krishna Myneni
> <krishna...@ccreweb.org> wrote:

> >But, for now, I'd settle for the ability to traverse the wordlist and
> >obtain the word name at each node of the traversal. I haven't seen
> >anything in this thread to suggest that there would be any great
> >difficulty to providing such words within any existing Forth system.

I have no time for a more thoughtful response, so here's just a
(limited) dump of the facilities exposed by iForth.


FORTH> help doWORDS
doWORDS IFORTH
( xt -- count-of-matched-entries )
The wordlist traversing factor of WORDS WORDS: and WORDS?
Supply the xt of a word that can filter ( addr -- bool ) where
addr is the address of a counted string (name of the next word
in the list). For example, to realize a clone of WORDS that only
prints short words you can do:
: SWORDS-XT ( addr -- bool ) C@ 3 < ; ' SWORDS-XT doWORDS DROP .
ok
FORTH> words: HEAD
>HEAD HEAD>exec HEAD>comp HEAD'
HEAD>FLAGS HEAD>LOCATE HEAD>FORGET HEAD>HASH
HEAD> LINK>HEAD HEAD>LINK HEAD>NAME
ok


Some examples:


FORTH> help HEAD>NAME
HEAD>NAME "head-to-name" IFORTH
( dea -- nfa )
nfa is the name field address of the dictionary entry identified by dea.
It contains a character string with the name of the dictionary entry.

FORTH> help >HEAD
>HEAD "to-head" IFORTH
( xt -- dea | 0 )
dea is the address of the dictionary entry whose execution token is xt .
If the conversion was not possible a 0 is returned.

FORTH> help HEAD>FLAGS
HEAD>FLAGS IFORTH
( dea -- ffa )
ffa is the flag field address of the dictionary entry identified by dea.
It is considered as an array of flags denoting properties of the
dictionary entry. It can be manipulated using bit-masks.
For example: the phrase flags =ANSI AND =ANSI = leaves true if flags
are the flags from an ANS standard word.
See also: =ANSI =COMP =IMMEDIATE =MACRO =PRIVATE =VISIBLE

FORTH> help .FLAGS
.FLAGS "dot-flags" IFORTH
( flags -- )
Display a summary of what flags means. Example:

FORTH> HEAD' IF HEAD>FLAGS @ CR .FLAGS
IMMEDIATE, COMPILE-ONLY, ANSI ok

See also: HEAD>FLAGS

-marcel

[Albert van der Horst]

In article <4f19b46d...@192.168.0.50>,

Stephen Pelc <steph...@INVALID.mpeforth.com> wrote:
>On Fri, 20 Jan 2012 10:11:45 -0800 (PST), Krishna Myneni
><krishna...@ccreweb.org> wrote:
>
>>But, for now, I'd settle for the ability to traverse the wordlist and
>>obtain the word name at each node of the traversal. I haven't seen
>>anything in this thread to suggest that there would be any great
>>difficulty to providing such words within any existing Forth system.
>
>Before you can standardise, you need common practice. A good way
>to start is to keep a lot of systems on your working PC and to scan
>the sources regularly.
>
>The VFX traversal words are:
>
>: WalkWordList \ xt wid --
>\ Walk through a wordlist calling the definition XT for each word.
>\ The definitions are walked in reverse chronological order.
>\ The definition at XT will be passed the THREAD# and NFA.
>\ The XT definition has the stack form:
>\ *E : MyDef \ thread# nfa -- flag ; Return TRUE to continue

This exact same word is present in ciforth called FOR-WORDS

<SNIP>

>
>Stephen

Groetjes Albert

[Rod Pemberton]

"BruceMcF" <agi...@netscape.net> wrote in message

news:6966483a-9850-4392...@h3g2000yqe.googlegroups.com...

> On Jan 20, 5:52 am, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
> wrote:

...

> If you know where the set of hash buckets is located,
> you do not need to link the hash buckets together, you
> can just look in each hash bucket, one after the other.

How do you get from one hash bucket to another? I.e., represented by your
phrase "just look in each hash bucket, one after the other".

The functionality to move from bucket to bucket represents a link, which is
what I said previously ... It could be simply summing an address of a fixed
bucket size from the starting address of the buckets. However, that
functionality - the functionality to move to the next bucket - is present
and codified. If you had understood what I wrote, you wouldn't have just
reiterated that.

> The rest snipped unread as if you think its impossible to

> traverse a set of hash buckets, [...]

I said no such thing. You simply failed to comprehend what I wrote.

> [...] it doesn't seem like you are in a position to suggest a set of

behaviors that would work for a hashed dictionary except by accident.

Whatever your apparent emotional problems are with what I suggested, I can't
fix that. Only you can. But, failed to stated what you thought was so
wrong. You could've said, "I don't like this wordset" because 1) they don't
word well with hash functions 2) they don't fit the way I've done things 3)
they don't work well with Forth in general 4) etc.


Rod Pemberton

[BruceMcF]

On Jan 21, 3:45 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
wrote:
> "BruceMcF" <agil...@netscape.net> wrote in message

> news:6966483a-9850-4392...@h3g2000yqe.googlegroups.com...> On Jan 20, 5:52 am, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
> > wrote:

> ...

> > If you know where the set of hash buckets is located,
> > you do not need to link the hash buckets together, you
> > can just look in each hash bucket, one after the other.

> How do you get from one hash bucket to another?  I.e., represented by
> your phrase "just look in each hash bucket, one after the other".

Instead of *fetching* the next address from a *link* field in the
item, you may, for example, increment the data bucket address and
compare the result to the end of the vector of hash buckets.

> The functionality to move from bucket to bucket represents a link,
> which is what I said previously ...

If you are redefining words from their normal meaning to some
idiosyncratic meaning, then say so up front ... the "functionality to
move from bucket to bucket" does not "represent a link". It performs
part of the same *function* as a link (though often only part, since
there may be a linked list of all hash collisions in a given hash
bucket) ... but it does not do so by *using a link address*. It does
so by some other means.

The point of the traverse-wordlist operations (plural, since as we've
seen there are a family of them both already implementation and
conceivable) is that the mechanics of traversing the wordlist does not
have to be first mapped to match the mechanics of traversing a linked
list. Instead, the direct mechanics of traversing the wordlist however
it is implemented is used.

> It could be simply summing an address of a fixed bucket size from the
> starting address of the buckets.

But then its no longer a link, its a *different* way to step through ~
a way to step through that depends on a different set of information
than a *linked* list. For example, you can use a do-loop to step
through a vector of hash buckets, which is an option that hiding the
actual hash buckets behind an abstraction that pretends that its a
linked list will hide.

> However, that functionality - the functionality to move to the next
> bucket - is present and codified.

Yes, and the functionality to move to the next bucket is provided by
something *other than* a link which you are mapping to a set of linked
list operations.

> If you had understood what I wrote, you wouldn't have just
> reiterated that.

> > The rest snipped unread as if you think its impossible to
> > traverse a set of hash buckets, [...]

> I said no such thing.  You simply failed to comprehend what I wrote.

You said if there is no link, there should be a no-op. Now you clarify
that when you said if there is no link, you did not mean what the
words would seem to say, that when there is no *actual* link, but
rather by link you meant something more general ~ neither a link nor
anything else which can be used to traverse the information.

The link for the hash bucket is a double ~ the index into the hash
bucket vector and the address for the item>next-item operation in the
hash collision change. Emulating that with a set of operators for a
linked list requires hiding state ~ likely the hash bucket vector
index ~ and that means that operations which *are* valid for a real
linked list will not be valid for the emulated linked list.

[BruceMcF]

On Jan 20, 1:43 pm, stephen...@mpeforth.com (Stephen Pelc) wrote:
> Before you can standardise, you need common practice. A good way
> to start is to keep a lot of systems on your working PC and to scan
> the sources regularly.

> The VFX traversal words are:

> : WalkWordList  \ xt wid --
> \ Walk through a wordlist calling the definition XT for each word.
> \ The definitions are walked in reverse chronological order.
> \ The definition at XT will be passed the THREAD# and NFA.
> \ The XT definition has the stack form:
> \ *E : MyDef    \ thread# nfa -- flag ; Return TRUE to continue

This seems to be the function under discussion ... I am assuming that
the nfa could be generalized to an nt as the cfa has been generalized
to an xt ~ but what is "thread#" in the argument to the xt?

[Rod Pemberton]

"BruceMcF" <agi...@netscape.net> wrote in message

news:1d937660-dc87-4d9b...@l19g2000yqj.googlegroups.com...

> On Jan 21, 3:45 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
> wrote:
> > "BruceMcF" <agil...@netscape.net> wrote in message

...

> > I said no such thing. You simply failed to comprehend what I wrote.
>
> You said if there is no link, there should be a no-op. Now you clarify
> that when you said if there is no link, you did not mean what the
> words would seem to say, that when there is no *actual* link, but
> rather by link you meant something more general ~ neither a link nor
> anything else which can be used to traverse the information.

You're confused, or willfully ignoring parts of the conversation.

> The link for the hash bucket is a double ~ the index into the hash
> bucket vector and the address for the item>next-item operation in the
> hash collision change. Emulating that with a set of operators for a
> linked list requires hiding state ~ likely the hash bucket vector
> index ~ and that means that operations which *are* valid for a real
> linked list will not be valid for the emulated linked list.

So, now you are saying such a system is also incapable of implementing
WORDS correctly ...

The required functionality needed to implement WORDS and
dictionary traversal are the same. How do you not recognize that?


Rod Pemberton

[BruceMcF]

On Jan 21, 9:15 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>

wrote:
> "BruceMcF" <agil...@netscape.net> wrote in message
>
> news:1d937660-dc87-4d9b...@l19g2000yqj.googlegroups.com...> On Jan 21, 3:45 pm, "Rod Pemberton" <do_not_h...@noavailemail.cmm>
> > wrote:
> > > "BruceMcF" <agil...@netscape.net> wrote in message
>
> ...
>
> > > I said no such thing. You simply failed to comprehend what I wrote.
>
> > You said if there is no link, there should be a no-op. Now you clarify
> > that when you said if there is no link, you did not mean what the
> > words would seem to say, that when there is no *actual* link, but
> > rather by link you meant something more general ~ neither a link nor
> > anything else which can be used to traverse the information.
>
> You're confused, or willfully ignoring parts of the conversation.
>
> > The link for the hash bucket is a double ~ the index into the hash
> > bucket vector and the address for the item>next-item operation in the
> > hash collision change. Emulating that with a set of operators for a
> > linked list requires hiding state ~ likely the hash bucket vector
> > index ~ and that means that operations which *are* valid for a real
> > linked list will not be valid for the emulated linked list.
>
> So, now you are saying such a system is also incapable of implementing WORDS correctly ...

No, obviously not. As with all the more general traverse words the
execute an xt on each entry and take a flag to continue, WORDS does
not require the full range of capabilities provided by a linked list
link address, and so an ability to perform WORDS does not imply an
ability to provide the full range of capabilies that must be supported
to effectively emulate general linked list functionality.

There is no need to be able to *step through* a wordlist item by item
using a single, atomic link in order to be able to traverse a
wordlist. Each and every word described already that applies an xt to
each item in a wordlist avoids the user having to program the step by
step process, and so adapt to a variety of distinct traversal
mechanisms, not just a linked list mechanism.

[Stephen Pelc]

On Sat, 21 Jan 2012 17:22:04 -0800 (PST), BruceMcF
<agi...@netscape.net> wrote:

>> : WalkWordList =A0\ xt wid --

>> \ Walk through a wordlist calling the definition XT for each word.
>> \ The definitions are walked in reverse chronological order.
>> \ The definition at XT will be passed the THREAD# and NFA.
>> \ The XT definition has the stack form:

>> \ *E : MyDef =A0 =A0\ thread# nfa -- flag ; Return TRUE to continue

>
>This seems to be the function under discussion ... I am assuming that
>the nfa could be generalized to an nt as the cfa has been generalized
>to an xt ~ but what is "thread#" in the argument to the xt?

Thread# (0..n-1) identifies which of n threads the name is in.

NFA could be an xt, but in the majority of cases the NFA is of
more use.

Given the number of ways of hashing/threading a dictionary and
the number of ways of building a "name field", there is a large
number of ways to specify a word such as this.

[BruceMcF]

On Jan 22, 1:31 pm, stephen...@mpeforth.com (Stephen Pelc) wrote:
> On Sat, 21 Jan 2012 17:22:04 -0800 (PST), BruceMcF

> <agil...@netscape.net> wrote:
> >> : WalkWordList =A0\ xt wid --
> >> \ Walk through a wordlist calling the definition XT for each word.
> >> \ The definitions are walked in reverse chronological order.
> >> \ The definition at XT will be passed the THREAD# and NFA.
> >> \ The XT definition has the stack form:
> >> \ *E : MyDef =A0 =A0\ thread# nfa -- flag ; Return TRUE to continue

> >This seems to be the function under discussion ... I am assuming that
> >the nfa could be generalized to an nt as the cfa has been generalized
> >to an xt ~ but what is "thread#" in the argument to the xt?

> Thread# (0..n-1) identifies which of n threads the name is in.

> NFA could be an xt, but in the majority of cases the NFA is of
> more use.

For a library routine to support portable code, the specification of
an "nt" would be to export some of those uses without making the
consumer code dependent on a specific dictionary implementation.

Thread# does not seem to be information that can be used independently
of dictionary implementation.

> Given the number of ways of hashing/threading a dictionary and
> the number of ways of building a "name field", there is a large
> number of ways to specify a word such as this.

Yes, but for the question at hand, much of the variety falls away,
since the question is what can be defined under the same name in a
variety of implementations that can be used by the same consumer
source code to arrive at the same result. An "nt" will in most cases
be some form of name field address, but the words that translate from
the nfa to the name, xt, and etc. would cover the differences in
implementation.

[Anton Ertl]

"Elizabeth D. Rather" <era...@forth.com> writes:
>The evidence shows that one can, and most do, write WORDS without
>WORDLIST-TRAVERSE. The factors of WORDS are implementation-dependent and
>very diverse. Yes, in theory, everyone could adopt a standard set of
>factors and rewrite our WORDS, but I suspect there isn't enough
>perceived need to justify doing it.

The wordlist traversal functionality is available through surprisingly
similar words in Win32Forth (VOC-ITERATE), VFX (WalkWordList), and
iForth (doWORDS). And anyway, systems having the same functionality
under different names and interfaces is a problem that standardization
is there to address (documenting cases where systems provide already
compatible interfaces is another, but less valuable one); if
implementation-dependency and diversity were unsurmountable obstacles,
we would not have the file wordset and many others now.

Concerning the need, Stephen Pelc reported 15 uses of such words in
the code tree of VFX and Krishna Myneni asked for such a word for a
specific application. And some people have complained that Gforth's
WORDS is useless because it does just what the standard demands. They
could implement a WORDS that's more to their liking with
WORDLIST-TRAVERSE.

More generally, the focus on "application programmers" seems to be
myopic. There are programmers who are interested in building tools;
and Forth could benefit from a tool-building community beyond the
system implementors.

When somebody is interested in building a Forth system, the advice is
to program in Forth instead, but when somebody is interested in
programming tools portably, and asks for language features for doing
that, the answer seems to be: No, application programmers don't ask
for such features, so we don't need these language features. One
might get the impression that Forth is not a language for building
programming tools (while it used to be an excellent language for
that).

[Alex McDonald]

On Jan 23, 12:25 pm, an...@mips.complang.tuwien.ac.at (Anton Ertl)
wrote:

Seconded.

Particularly the observation that Forth was (and can be) a language
for building programming tools.

In that spirit, here's a proposed RfD.

-----

RfD: traverse-wordlist
20 January 2012, Alex McDonald

Change history:

20120120 First version

Problem statement
-----------------

There are no standard words in Forth for traversing a wordlist and
obtaining basic information about each node. While standard Forth
provides a great many features for extensibility of the language
(with CREATE ... DOES> being the classic example), standard Forth
lacks the basic capability of traversing the wordlist as a part of
the specification.

Such a capability is needed to provide some kinds of advanced
programming tools. For example, the programmer may want to determine
all instances of word name overlaps in all of the wordlists in the
current search order; or count, display or modify words contained in
a specific wordlist.

Proposal
--------

TRAVERSE-WORDLIST ( x*i xt-node wid -- x'*i nt ) TOOLS

Traverse the wordlist wid in no specific or guaranteed order,
executing the user-specified word

xt-node ( x*i nt -- x'*i u )

without returning to the caller, and executing xt-node once only for
every node in the wordlist, and termintaing once all the nodes have
been exhausted or until xt-node returns the the flag u with the value
FALSE (0).

nt is a system-specific name token for the node. The word xt-node can
use this token to display, count, modify or perform any other action
on the node that the system providing nt permits.

To stop receiving nodes from TRAVERSE-WORDLIST and return to the
caller, xt-node returns u, a flag of FALSE (0). Any other value for u
will continue to receive nodes until all the nodes in the wordlist
have been exhausted.

The terminating nt is returned to the caller of TRAVERSE-WORDLIST if
the list is exhausted early by xt-node returning FALSE (0), and can
be used to determine if the traversal of the wordlist was terminated
before all nodes have been visited, and if so, which nt was the last
visited. Otherwise the value of nt is 0.

x*i is 0 or more stack parameters that are agreed on by the caller
of TRAVERSE-WORDLIST and xt-node. xt-node is free to modify them but
must return the same number of parameters on trhe stack. For example;

: WORDS-COUNT ( x nt -- x' u )
DROP 1+ TRUE ;

0 ' WORDS-COUNT WID TRAVERSE-WORDLIST .

returns x' TRUE, where x is a count of the total number of nodes in
the wordlist WID. This example works on all systems, regardless of
the system-specific format of nt.

Remarks
-------

Many systems provide the TOOLS word WORDS that provides human-readble
output from the current wordlists in CONTEXT. TRAVERSE-WORDLIST is a
usable factor for the implementation of WORDS.

The wordlist traversal functionality is available through very