strategies for implementation of USES?

To avoid any misunderstandings up front: This is *not* a proposal for
standardizing a new word in Forth.

The discussion of advanced tools programming in Forth touched on the
subject of being able to generate dependency trees for words. Such a
tool would likely be useful both academically and practically. It
seems to me that the basic factors for writing this tool are TRAVERSE-
WORDLIST and a word such as "USES?". The word USES? might have the
following stack diagram:

USES? ( wid1 nt1 wid2 nt2 -- flag )

where the pair (wid1, nt1) uniquely represents a word in wid1 and the
pair (wid2, nt2) uniquely represents a word in wid2. The returned flag
is true if the word represented by (wid1, nt1) is used in the
definition of the word represented by (wid2, nt2), and false
otherwise.

Now, one way of implementing such a word is for the Forth system to
generate and save the required data at compile time, so that USES? can
simply look up the flag. But, that seems prohibitively expensive and
wasteful. Are there more efficient/realistic strategies for
implementing USES? . Or perhaps, USES? isn't the correct factor for
accomplishing the desired goal?

Krishna

On Feb 4, 5:47*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
....
> The discussion of advanced tools programming in Forth touched on the
> subject of being able to generate dependency trees for words. ...

Oops. I realize now that the term "dependency tree" is strictly not
correct. According to Wikipedia, in graph theory, "a tree is an
undirected graph in which any two vertices are connected by exactly
one simple path". Dependencies between words (vertices) do not fit
this description. What is the topologically correct term for a
dependency graph?

Krishna

On Feb 4, 10:25*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> What is the topologically correct term for a
> dependency graph?

Yes.

IOW, dependency graph *is* the correct term, meaning a directed graph
representing dependencies of several objects towards each other.

On Feb 4, 9:37*pm, BruceMcF <agil...@netscape.net> wrote:
> On Feb 4, 10:25*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
>
> > What is the topologically correct term for a
> > dependency graph?
>
> Yes.
>
> IOW, dependency graph *is* the correct term, meaning a directed graph
> representing dependencies of several objects towards each other.

Some graphs have names. For example, see

http://en.wikipedia.org/wiki/Gallery_of_named_graphs

I was wondering if a word dependency graph fit the structure of a
known, named graph. I'd be surprised if computer science doesn't have
a specific name, since such a dependency graph is of far more general
applicability than to Forth words.

Krishna

On Feb 4, 10:16*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> On Feb 4, 9:37*pm, BruceMcF <agil...@netscape.net> wrote:
>
> > On Feb 4, 10:25*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
>
> > > What is the topologically correct term for a
> > > dependency graph?
>
> > Yes.
>
> > IOW, dependency graph *is* the correct term, meaning a directed graph
> > representing dependencies of several objects towards each other.
>
> Some graphs have names. ...


You're right. The correct term does appear to be "dependency graph":

http://en.wikipedia.org/wiki/Dependency_graph

Thanks.

Krishna

On Feb 4, 6:47*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:

> Now, one way of implementing such a word is for the Forth system to
> generate and save the required data at compile time, so that USES? can
> simply look up the flag. But, that seems prohibitively expensive and
> wasteful. Are there more efficient/realistic strategies for
> implementing USES? . Or perhaps, USES? isn't the correct factor for
> accomplishing the desired goal?

Is the individual word the correct unit of analysis? I think of
dependencies in Forth in terms of depencies between sets of words.

On Feb 5, 7:26*am, BruceMcF <agil...@netscape.net> wrote:
> On Feb 4, 6:47*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
>
> > Now, one way of implementing such a word is for the Forth system to
> > generate and save the required data at compile time, so that USES? can
> > simply look up the flag. But, that seems prohibitively expensive and
> > wasteful. Are there more efficient/realistic strategies for
> > implementing USES? . Or perhaps, USES? isn't the correct factor for
> > accomplishing the desired goal?
>
> Is the individual word the correct unit of analysis? I think of
> dependencies in Forth in terms of depencies between sets of words.

You mean dependencies among wordlists? Yes, that can be useful too.
Just as with dependencies among Forth modules, the graph of which we
envision could be generated automatically.

However, I think the utility of such dependency graphs extends down to
the individual unit of a word in a specific wordlist. High level words
may end up having dozens of words (even excluding intrinsic Forth
words) in their dependency graph. Such a graph may be very useful in
the systematic analysis of the execution failure of such words.

Krishna

On Feb 5, 8:51*am, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> On Feb 5, 7:26*am, BruceMcF <agil...@netscape.net> wrote:
>
> > On Feb 4, 6:47*pm, Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
>
> > > Now, one way of implementing such a word is for the Forth system to
> > > generate and save the required data at compile time, so that USES? can
> > > simply look up the flag. But, that seems prohibitively expensive and
> > > wasteful. Are there more efficient/realistic strategies for
> > > implementing USES? . Or perhaps, USES? isn't the correct factor for
> > > accomplishing the desired goal?
>
> > Is the individual word the correct unit of analysis? I think of
> > dependencies in Forth in terms of depencies between sets of words.
>
> You mean dependencies among wordlists?

No, I meant dependencies among sets of words, since a capacity is so
often provided by a set of words rather than by an individual word.

But dependencies among wordlists would also be interesting.

Krishna Myneni <krishna.myneni@ccreweb.org> wrote:
> To avoid any misunderstandings up front: This is *not* a proposal for
> standardizing a new word in Forth.
>
> The discussion of advanced tools programming in Forth touched on the
> subject of being able to generate dependency trees for words. Such a
> tool would likely be useful both academically and practically. It
> seems to me that the basic factors for writing this tool are TRAVERSE-
> WORDLIST and a word such as "USES?". The word USES? might have the
> following stack diagram:
>
> USES? ( wid1 nt1 wid2 nt2 -- flag )
>
> where the pair (wid1, nt1) uniquely represents a word in wid1 and the
> pair (wid2, nt2) uniquely represents a word in wid2. The returned flag
> is true if the word represented by (wid1, nt1) is used in the
> definition of the word represented by (wid2, nt2), and false
> otherwise.
>
> Now, one way of implementing such a word is for the Forth system to
> generate and save the required data at compile time, so that USES? can
> simply look up the flag. But, that seems prohibitively expensive and
> wasteful.

I don't think it is: on the contrary, I think that's exactly the right
way to do it. You don't need to do this all the time.

Andrew.

On Feb 7, 3:13*am, Andrew Haley <andre...@littlepinkcloud.invalid>
wrote:
> Krishna Myneni <krishna.myn...@ccreweb.org> wrote:
> > To avoid any misunderstandings up front: This is *not* a proposal for
> > standardizing a new word in Forth.
>
> > The discussion of advanced tools programming in Forth touched on the
> > subject of being able to generate dependency trees for words. Such a
> > tool would likely be useful both academically and practically. It
> > seems to me that the basic factors for writing this tool are TRAVERSE-
> > WORDLIST and a word such as "USES?". The word USES? might have the
> > following stack diagram:
>
> > *USES? *( wid1 nt1 *wid2 nt2 *-- flag )
>
> > where the pair (wid1, nt1) uniquely represents a word in wid1 and the
> > pair (wid2, nt2) uniquely represents a word in wid2. The returned flag
> > is true if the word represented by (wid1, nt1) is used in the
> > definition of the word represented by (wid2, nt2), and false
> > otherwise.
>
> > Now, one way of implementing such a word is for the Forth system to
> > generate and save the required data at compile time, so that USES? can
> > simply look up the flag. But, that seems prohibitively expensive and
> > wasteful.
>
> I don't think it is: on the contrary, I think that's exactly the right
> way to do it. *You don't need to do this all the time.
>
> Andrew.

On second thought, I agree with your statement. Let's say we have a
medium sized dictionary of 10,000 words. Assume that the average word
directly uses on the order of 10 distinct words (excluding standard
Forth words) -- that's probably an over estimate. Then, the overhead
in storage for each word is 20 cells, where each of the 10
dependencies requires 2 cells to hold the wid and nt. Thus, for our
10K dictionary, we have an overhead of 200K cells to be able to
represent the internal dependencies between words. Furthermore, if the
nt uniquely identifies a word, in all wordlists, the overhead reduces
to 100K cells. So, it wouldn't be practical to store such information
on a number of embedded systems, but certainly should not be a problem
for desktop systems.

Another concern is the impact on compiler speed, although since the
compiler has to look up the word tokens anyway, it might not be much
of a hit in efficiency for the compiler to store the dependency list
for a word.

Krishna

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Krishna Myneni <krishna.myneni@ccreweb.org> wrote:
>> The discussion of advanced tools programming in Forth touched on the
>> subject of being able to generate dependency trees for words. Such a
>> tool would likely be useful both academically and practically. It
>> seems to me that the basic factors for writing this tool are TRAVERSE-
>> WORDLIST and a word such as "USES?". The word USES? might have the
>> following stack diagram:
>>
>> USES? ( wid1 nt1 wid2 nt2 -- flag )
>>
>> where the pair (wid1, nt1) uniquely represents a word in wid1 and the
>> pair (wid2, nt2) uniquely represents a word in wid2. The returned flag
>> is true if the word represented by (wid1, nt1) is used in the
>> definition of the word represented by (wid2, nt2), and false
>> otherwise.

That appears inefficient to me. You would need to enumerate all words
to find out which ones are used. It's also incomplete because you
wouldn't see uses of anonymous words or words in private wordlists.
It seems to me that a word that enumerates the xts of words called by
a given colon definition would be as easy or hard to implement as
USES? and would lead to a more efficient and complete dependency
graph.

>> Now, one way of implementing such a word is for the Forth system to
>> generate and save the required data at compile time, so that USES? can
>> simply look up the flag. But, that seems prohibitively expensive and
>> wasteful.
>
>I don't think it is: on the contrary, I think that's exactly the right
>way to do it. You don't need to do this all the time.

It's certainly an approach I would have used in recent decades because
the executable code became more opaque; in contrast, in the 80s I
wrote such a tool for fig-Forth that worked on the threaded code.

Anyway, for a tool that works during compilation rather than on the
compiled code, it would be very useful to have hooks in the text
interpreter or in COMPILE,.

- 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/

In the "Valentine Bingo" thread I tried writing an implementation and
was surprised to see that there seems to be no random number generator
in the gforth library. Since (AFAIK) gforth is a full featured ANS
implementation, I infer that there's no RNG specified in the standard.
It looks like VFX supplies something called "CHOOSE" which I guess is
non-standard. I ended up supplying my own RNG, using a fairly poor
algorithm that I felt was ok for a simple demo program of this nature,
but choosing and coding a good algorithm requires knowing what you're
doing. So it wouldn't surprise me if there's an awful lot of Forth code
out there containing crappy RNG's.

It therefore seems worthwhile to me that the standard include a PRNG
spec, not for the algorithm itself, but something library implementers
can code to. Something like:

: RANDSEED ( addr n -- ) ... ;

takes n bytes from memory and crunches them to some internal state
that seeds the PRNG

: RANDUPDATE ( addr n -- ) ... ;

takes n bytes and folds them into the existing state.

: RANDSIZE ( -- n ) ... ;

puts the size of the internal state onto the stack. n should be a fixed
parameter of the PRNG algorithm, i.e. RANDSIZE should normally always
return the same result in a given implementation. (It's ok if an
implementation has some additional parametrization words that change n
explicitly).

: RANDCLONE ( addr n -- ) ... ;

copies the internal state to the supplied memory area. n must be
at least as large as the state size or else the word signals an error.

: NRAND ( -- n ) .... ;

generates a pseudorandom integer (uniform probability) and puts
it on the stack, updating the internal state.

: FRAND ( -- f:x ) ... ;

generates a pseudorandom floating point number uniformly distributed on
the unit interval, and puts it on the floating point stack, updating the
internal state.

: GENSEED ( -- ) \ optional, system dependent

Initializes the random state based on a non-deterministic source such as
reading the system timer.

The above words are supposed to supply pseudorandom streams with
reasonable statistical properties for purposes like simulations and
friendly games. Applications needing random numbers that withstand
adverserial attempts to predict the stream or recover the initial state
should use cryptographic algorithms and high-entropy physical randomness
sources.

I'm not really attached to the above specification. I only wrote it out
for the sake of having a concrete proposal that other people can
improve, instead of just making a vague suggestion that there should be
a PRNG.

On Feb 7, 11:56*am, stephen...@mpeforth.com (Stephen Pelc) wrote:
> On Tue, 7 Feb 2012 03:22:35 -0800 (PST), Krishna Myneni
>
> <krishna.myn...@ccreweb.org> wrote:
> >Let's say we have a
> >medium sized dictionary of 10,000 words. Assume that the average word
> >directly uses on the order of 10 distinct words (excluding standard
> >Forth words) -- that's probably an over estimate. Then, the overhead
> >in storage for each word is 20 cells, where each of the 10
> >dependencies requires 2 cells to hold the wid and nt. Thus, for our
> >10K dictionary, we have an overhead of 200K cells to be able to
> >represent the internal dependencies between words
>
> Just to give you a couple of real-world data points, a 300k binary
> cross-compiled embedded app produces a cross-reference file on VFX
> of 500kb. A 22Mb desktop app produces a 75Mb cross-reference file.
>

Thanks, Stephen. Can you give us the word counts for your embedded and
desktop apps (excluding standard Forth words)? Also, are the cross-
reference files text or binary, and do they contain additional info
beyond what is needed to generate a dependency graph? My simple
analysis suggests that an app using 10K of words requires additional
storage of < 1 MB to retain info needed to make a dependency graph.
This is not far out of line with your embedded app's cross reference
file.

Krishna

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>
> Anyway, for a tool that works during compilation rather than on the
> compiled code, it would be very useful to have hooks in the text
> interpreter or in COMPILE,.

Even better, and certainly more powerful, is the ability to write your
own text interpreter that we discussed a few months back. There's no
guarantee that an implementation uses COMPILE, ; it only has to
provide it.

Andrew.

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>
>> Anyway, for a tool that works during compilation rather than on the
>> compiled code, it would be very useful to have hooks in the text
>> interpreter or in COMPILE,.
>
>Even better, and certainly more powerful, is the ability to write your
>own text interpreter that we discussed a few months back.

That's certainly easier to agree on between different implementors
(although still hard enough). But I see two drawbacks compared to the
hook approach:

1) If you need to do something at the lowest layer of the text
interpreter, say "COMPILE,", you need to reimplement all of it. Sure,
words could be standardized that would help with that, but it would
still be significantly more cumbersome than just hooking into
"COMPILE,".

2) A hook would work even for invocations of the text interpreter that
the programmer had not considered in advance, like system-specific
words invoked by the user (who may be a different person than the
programmer).

In conclusion, both approaches have their advantages and
disadvantages, and they would complement each other: A few hooks in
places that every standard system must have (together with a
convention for dealing with having several independent things to plug
in), and fill in the rest by reimplementing the functionality with
provided words.

Anyway, that's a very long-term project as far as I can see.

> There's no
>guarantee that an implementation uses COMPILE, ; it only has to
>provide it.

Sure. So one would specify the hook in a more general way (if we want
a hook there at all).

- 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/