Proposal: find-name

amforth has FIND-NAME since ever and FIND-NAME-IN under the name SEARCH-NAME following SEARCH-WORDLIST ( c-addr u wid -- 0 | xt 1 | xt -1 ).

If I've got this right, a definition of FIND using FIND-NAME :

   :  EXPLICIT?  ( nt -- int-xt 0 | comp-xt -1 ) 
                             NAME>COMPILE  ['] EXECUTE =  ;

   : FIND   dup count parse-name find-name dup IF
                 ( c-addr nt )  nip dup name>interpret swap
                ( int-xt nt )  explicit?  IF  
                ( int-xt comp-xt )  state @ IF nip ELSE  drop THEN 
                                           1 ELSE 
                                    nip -1 THEN  ; 

Should be:

 :  EXPLICIT?  ( nt -- int-xt 0 | comp-xt -1 ) 
                             NAME>COMPILE  ['] EXECUTE =  ;

   : FIND   dup count parse-name find-name dup IF
                 ( c-addr nt )  nip dup name>interpret swap
                ( int-xt nt )  explicit?  IF  
                ( int-xt comp-xt )  state @ IF nip ELSE  drop THEN 
                                           1 ELSE 
                                    drop  -1 THEN  
                                                                                      THEN  ; 

Why not have FIND-NAME return both the interpretation and compilation XTs simultaneously, then you can simply DROP or NIP to keep the XT that you're interested in:

FIND-NAME ( c-addr u -- compXT|0 intXT|0 )

Now, we don't need NAME>INTERPRET and NAME>COMPILE at all.

Additionally, NAME>INTERPRET and NAME>COMPILE are erroneously named, since you don't pass a name to them. The "name" (in the form of addr u) is passed into FIND-NAME. NAME>INTERPRET and NAME>COMPILE both take an execution token, so they should be named XT>INTERPRET and XT>COMPILE.

However, as noted above, it seems much simpler to have FIND-NAME return both tokens, and the programmer DROP or NIP as appropriate.

Regards

Mark Wills

I would implement FIND using FIND-NAME as follows (untested):

: find ( c-addr -- c-addr 0 | xt 1 | xt -1 )
  dup find-name dup if
   nip state @ if
    name>compile ' execute = if 1 else -1 then
   else
    name>interpret 1
   then
  then ;

This assumes that NAME>COMPILE returns the xt of EXECUTE or that of COMPILE, on the TOS. If NAME>COMPILE can also return other xts on the TOS, FIND may need to be implemented in a different way. Whether interpretive FIND returns 1 or -1 does not play a role for the classical text interpreter. However, if other applications need it, one might extract the proper value from NAME>COMPILE; an application that relies on the flag returned in interpret state is also likely to rely on the corresponding xt as representing a part of the compilation semantics, and that does not work for all words on all systems (it might be good enough for a specific system or a specific set of words, though).

As for a word that returns an interpretation xt and a compilation xt: It has no existing practice, in contrast to FIND-NAME. It's also bad factoring, because it does two things at once while we usually need only one of them. The wisdom of having a name token (nt) and factoring these operations into FIND-NAME, NAME>INTERPRET and NAME>COMPILE is demonstrated by the introduction of TRAVERSE-WORDLIST, which also produces nts, that then can be processed with NAME>INTERPRET. Another problem of the suggested word is that it returns just one xt for the compilation semantics, which would require a costly production of these xts for many words. Finally, such a word would also be harder to write and read, because both writer and reader would have to look up how NIP and DROP correspond to interpretation and compilation semantics.

NAME >INTERPRET returns 0 for a compile-only word that the system has marked as such. That's not a valid output for FIND.

To cover that (but with the other assumptions as above), FIND would look as follows:

: find ( c-addr -- c-addr 0 | xt 1 | xt -1 )
  dup find-name dup if
   state @ if
    nip name>compile ['] execute = if 1 else -1 then
   else
    name>interpret dup if nip 1 then
   then
  then ;

I now have an NDCS version of VFX Forth that passes all of Gerry Jackson's test suite, plus the previous tests for [COMPILE]. The NDCS VFX works fine with FIND. The sole reason for FIND-NAME is to allow for multiple words with the same xt, i.e. the nt identifies a named word and xts identify the actions. We have to recognise that people with xt-based systems are not going to abandon them, they will simply use FIND-WORD or some such that returns an xt. I really feel that we should slow down and resolve issues such as NDCS words before we redesign the text interpreter. Given recognisers, this may be too late, but we need to work our way through the issues before we make changes that we may regret. Note that the compilation issues caused by NDCS ("non-default compilation semantics") have taken 20+ years to emerge.

Stephen Pelc wrote

The NDCS VFX works fine with FIND.

Does the same FIND allow NCDS words to be used wirh legacy code that either EXECUTEs or COMPILE,s the xt returned?

The sole reason for FIND-NAME is to allow for multiple words with the same xt, i.e. the nt identifies a named word and xts identify the actions.

Does this mean that

synonym foo bar

' foo  ' bar = .
-1 ok

? That seems sensible if it can be done. It means syonyms of CREATE ... DOES> words should simply work with definitions that use ' >BODY and, by extension, synonyms of deferred wordsand values should also work as expected. It also makes it clear that you can't change the definition of a synonym with IMMEDIATE or DOES> because that would affect the original.

We have to recognise that people with xt-based systems are not going to abandon them, they will simply use FIND-WORD or some such that returns an xt.

Of course, but the name token stuff has been around for twenty years and more now, and it's not going away either.

I really feel that we should slow down and resolve issues such as NDCS words before we redesign the text interpreter. Given recognisers, this may be too late, but we need to work our way through the issues before we make changes that we may regret.

Practically, we need to clarify when FIND-WORD is being used as a synonym for FIND-NAME and when for FIND-NAME NAME>INTERPRET . Whether an xt should be COMPILE,ed or EXECUTEd is determined by the dictionary header that returned it, not by the bare xt itself.

Note that the compilation issues caused by NDCS ("non-default compilation semantics") have taken 20+ years to emerge.

That's because normally it makes no sense to execute an NCDS word except as a part of normal compilation. So you could get away with defining COMPILE, as meaning 'perform the compilation semantics' and using LITERAL EXECUTE when you meant 'append the execution semantics.'

Jenny said: Stephen Pelc wrote

The NDCS VFX works fine with FIND.

Does the same FIND allow NCDS words to be used wirh legacy code that either EXECUTEs or COMPILE,s the xt returned?

That's one of the results of permitting NDCS words that are not IMMEDIATE. If we keep the restriction that COMPILE, must not parse or have additional stack effects, we need a word, then we can either introduce a compiling word that can parse, e.g. : compile-word \ ix xt -- jx \ *G process an XT for compilation. dup ndcs? \ NDCS or normal if ndcs, else compile, then ; or we could just lift the restrictions on COMPILE, so that the requirements of NDCS can be supported by COMPILE, itself. The second option leads to very little change. In the VFX with COMPILE-WORD, the word NDCS, is used only once in the kernel and COMPILE-WORD replaces COMPILE, in the vast majority of cases.

It is worth noting that VFX ran with this non-compliant COMPILE, for several years and the only complaint about it came from Anton ... because it was non-compliant. Note that my exploration of NDCS is not about preserving single xt and so on, it was an attempt to understand compilation in Forth. One of the side effects of this exploration is the realisation that STATE-smart words can be re-implemented as dual-behaviour words which are standard compliant.

Note that my exploration of NDCS is not about preserving single xt and so on, it was an attempt to understand compilation in Forth. One of the side effects of this exploration is the realisation that STATE-smart words can be re-implemented as dual-behaviour words which are standard compliant.

Yes, but your method and Anton's sèem to imply different methods of specifying NDCS. Your method requires that the compilation xt. expects the interpretation xt on the stack. His (I think) requires that it doesn't.

My view is that if you want dual-behaviour words then you need to implement the consequences outlined in my paper. However this is implemented, a way of performing the word that I called NDCS, is required. Anton's implementations hide most of this.

Full reference implementation using TRAVERSE-WORDLIST:

\ find-name and find-name-in

\ this file is in the public domain

: >lower ( c1 -- c2 )
    dup 'A' 'Z' 1+ within bl and or ;
: istr= ( addr1 u1 addr2 u2 -- flag )
   rot over <> IF  2drop drop false  EXIT  THEN
    bounds ?DO
        dup c@ >lower I c@ >lower <> IF  drop false  unloop  EXIT  THEN
        1+
    LOOP  drop true ;

: find-name-in ( addr u wid -- nt / 0 )
    >r 0 -rot r>
    [: dup >r name>string 2over istr= IF
            rot drop r> -rot false
        ELSE  rdrop true  THEN
    ;] swap traverse-wordlist 2drop ;
: find-name {: c-addr u -- nt | 0 :}
    get-order 0 swap 0 ?do ( widn...widi nt|0 )
        dup 0= if
            drop c-addr u rot find-name-in
        else
            nip
        then
    loop ;

The sole reason for FIND-NAME is to allow for multiple words with the same xt, i.e. the nt identifies a named word and xts identify the actions.

Yes, words with different names and the same interpretation semantics xt are a reason for FIND-NAME, but not the only one.

The main reason is that it (together with the already-standardized NAME>INTERPRET and NAME>COMPILE) provides a good factoring that separates the jobs ob looking up the named word (FIND-NAME), accessing the interpretation semantics (NAME>INTERPRET) and accessing the compilation semantics (NAME>COMPILE) into separate words.

This is the replacement for FIND that you asked for.

We have to recognise that people with xt-based systems are not going to abandon them

Nobody is asking them to, whatever you mean with "xt-based system". The only thing that FIND-NAME NAME>INTERPRET NAME>COMPILE etc. are not a good fit for are multi-header systems like cmForth and Mark Humphries' system (but I have outlined how to implement these words on the latter).

I really feel that we should slow down and resolve issues such as NDCS words before we redesign the text interpreter. Given recognisers, this may be too late, but we need to work our way through the issues before we make changes that we may regret. Note that the compilation issues caused by NDCS ("non-default compilation semantics") have taken 20+ years to emerge.

These issues emerged in my experience in 1996 (two years after Forth-94 was released), and FIND-NAME etc. have been implemented and used in the text interpreter of Gforth since then. We have collected experience with them since then (i.e., for 22 years), for several implementation approaches for NDCS words (including the current one in Gforth, which can be described as "xt-based"), and the experience is that these words provide a good implementation-independent interface.

Given that the problem has been recognized by the time of Forth-83 (35 years ago) at the latest, this solution has 22 years of experience, and you asked for a FIND replacement, your call for slowing down even more is not helpful. These issues have been discussed again and again for a long time, so they are not going away; therefore we need to go forward. You asked for this proposal, here it is!

That's one of the results of permitting NDCS words that are not IMMEDIATE. If we keep the restriction that COMPILE, must not parse or have additional stack effects, we need a word, then we can either introduce a compiling word that can parse, e.g. : compile-word \ ix xt -- jx \ *G process an XT for compilation. dup ndcs? \ NDCS or normal if ndcs, else compile, then ;

The other option is to use EXECUTE as the word that can parse and have additional stack effects. Of course then FIND will report these NDCS words as "immediate", and will return different xts in different STATEs for NDCS words, as allowed by Forth-94 and Forth-2012.

or we could just lift the restrictions on COMPILE, so that the requirements of NDCS can be supported by COMPILE, itself. The second option leads to very little change. In the VFX with COMPILE-WORD, the word NDCS, is used only once in the kernel and COMPILE-WORD replaces COMPILE, in the vast majority of cases.

The real requirement (aka restriction) of COMPILE, is that it appends the same semantics that EXECUTE executes, i.e., that it is equivalent to

: compile, postpone literal postpone execute ;

That it has the stack effect ( xt -- ) and that it does not parse follows from that. And I have seen quite a lot of uses of COMPILE, that make use of this equivalence (most uses of COMPILE, that are not in text interpreters).

It is worth noting that VFX ran with this non-compliant COMPILE, for several years and the only complaint about it came from Anton ... because it was non-compliant.

And lots of people report "no problems" with STATE-smart words. Others, like me, tripped over them.

A broken COMPILE, would not be so bad if it only affected VFX and only S" and TO. But the disease was spreading to Gforth, where not just a few words with broken COMPILE, were implemented, but many; and, in addition, it contained defining words that made each of their children have a broken COMPILE,. I am not sure if this disease has been fully cured yet.

My view is that if you want dual-behaviour words then you need to implement the consequences outlined in my paper. However this is implemented, a way of performing the word that I called NDCS, is required.

This view is refuted by the many systems that have implemented dual-behaviour words correctly, but differently from what you outlined in the paper, and in particular, without having a word like your NDCS,.

In any case, FIND-NAME NAME>INTERPET NAME>COMPILE abstract from the implementation (except for being a better fit for a single-header system than for a multi-header system), as demonstrated by the fact that they have been implemented on several different systems, and can be implemented on VFX.

I have adopted the reference implementation by Bernd Paysan and added a few adjustments. I have also added more test cases that test using FIND-NAME for a simple variant of a user-defined text interpreter, and using it for interpreting all the hard cases: S" and TO (both interpretation semantics and compilation semantics) and locals (definition, use, and TO semantics). The result works on development Gforth (with both the Gforth implementation of FIND-NAME and with the reference implementation), and on VFX 4.72.

You can find them here: Reference Implementation, Testcases

One wrinkle is that you need carnal knowledge for proper handling of locals in FIND-NAME. This has been included for Gforth and VFX in the reference implementation, but not (yet) for other systems.

However, both approaches have been known for at least two decades, and have seen little to no uptake in standard systems. And we have good approaches for implementing systems with name tokens, so excluding these approaches is not a significant loss.

I dislike the idea of excluding other approaches. Particularly, NAME>INTERPRET and NAME>COMPILE are suitable for "dual-xt" approach only, but they are in TOOLS EXT word set, so they don't exclude other approaches (e.g. "state-smart" approach).

This proposal does not mention in what word set the FIND-NAME and FIND-NAME-IN words should be located. Since these words are useless without the NAME>STRING and NAME>INTERPRET words that are in the TOOLS EXT word set, these words should be in the TOOLS EXT too. In such case this proposal is not excluding other approaches.

Regarding the critiques of SEARCH-WORDLIST

1. It produces results with a varying number of stack items. In some situations that makes it more cumbersome to use.

It is a weak argument, since in other situations that makes it less cumbersome to use. Sometimes I would even prefer ( xt immediate-flag true ), where imediate-flag is -1 for immediate and 0 otherwise.

2. Its interface is designed for single-xt+immediate-flag systems,

Strong argument. Actually it means that the dual-semantics words that are not implemented as immediate cannot be represented as a result of this word.

An example. In Gforth "action-of" forth-wordlist search-wordlist says that the returned xt is for a word whose compilation semantics is to perform the given execution semantics (in the compilation state, by my inference). But performing this compilation semantics does not produce the result that standard ACTION-OF should. Therefore, the result of search-wordlistdoes not represent the standard action-of word, but something else.

It is either incorrect result or an implicit ambiguous condition (the same as for Tick). Whatever the truth, I would say that more correct is to return 0 in this case.

3. In the general case, given that the xt part of the result does not represent a part of the compilation semantics, the 1/-1 part of the result is pointless.

In a Forth system that implements dual-semantics words as a state-smart, the result (xt code pair) properly represents the compilation semantics (as well as interpretation semantics) in the general case.

In any standard Forth system 1/-1 part of the result is not pointless for standard or user-defined immediate words.

NAME>INTERPRET ( nt -- xt ) and NAME>COMPILE ( nt -- xt1 xt2 ) are fine with a STATE-smart implementation of TO: Xt and xt1 are the same, and represent the STATE-smart definition. Xt2 is the xt of EXECUTE. If the standard allowed a STATE-smart implementation of FILE S", it would be the same.

It is not the proponent's job to decide which wordset a word should be added to, but the committee's. If the committee sees this as an optional feature, it will probably add these words to TOOLS EXT. If it sees this in the long term as a replacement for FIND and SEARCH-WORDLIST, it will probably add FIND-NAME to CORE and FIND-NAME-IN to SEARCH.

SEARCH-WORDLIST problems:

1. The interface of SEARCH-WORDLIST is inferior to that of FIND when you do not immediately have a DUP IF or somesuch following the SEARCH-WORDLIST, but want to AND the flag with something you have on the stack. With FIND, you could do ROT AND, but with SEARCH-WORDLIST you cannot. And indeed, an stack effect ( c-addr u wid -- c-addr u false | xt false true | xt true true ) would be better.

2. What you write does not have anything to do with the specification of SEARCH-WORDLIST. SEARCH-WORDLIST does not return an xt representing the compilation semantics; and it does not have the text that FIND has that suggests that it may be STATE-dependent, and may return an xt representing the compilation semantics. As stated in the proposal, in Gforth the result of SEARCH-WORDLIST represents the interpretation semantics of the found word, plus an immediate flag.

3. The practical usage case for SEARCH-WORDLIST (as specified) that I have found is for a lookup table. Put a number of words in a wordlist, then use search-wordlist to look them up. I have not used IMMEDIATE in that usage, but it could be used to put an additional bit of information on the word that you do not want to store in the data field. So yes, the 1/-1 result could be used for something.

2. Well, it is better to discuss this aspect of Gforth standard compliance in another place.

3. Yes, in practical usage the -1|1 difference is detected and used very rare. By my roughly evaluation, not more than in 1% cases (excluding implementing the standard features).

NAME>INTERPRET for STATE-smart implementation of TO

NAME>INTERPRET ( nt -- xt ) and NAME>COMPILE ( nt -- xt1 xt2 ) are fine with a STATE-smart implementation of TO: xt and xt1 are the same, and represent the STATE-smart definition. xt2 is the xt of EXECUTE. If the standard allowed a STATE-smart implementation of FILE S", it would be the same.

The issue is that in this case ( xt1 'execute ) doesn't represent the compilation semantics of TO. Usually, to perform the compilation semantics we need to just execute xt2 (regardless of the STATE, even in interpretation state). But in this case we need to also set compilation state before execution xt2. Therefore, ( xt1 'execute ) does not bring all required information to perform the compilation semantics. Therefore, it does not represent the compilation semantics. Actually, it represents the execution semantics of TO.

A possible solution is to return ( xt1 'execute-compiling ) — they brings all required information to perform the compilation semantics of TO (see EXECUTE-COMPILING in the comment for POSTPONE). But this solution cannot be used for NAME>INTERPRET.

Similarly, ( xt ) doesn't represent the interpretation semantics of TO, since it doesn't bring all required information, namely that we need to set interpretation state. But in this case we don't have a place to return special 'execute-interpreting.

So NAME>INTERPRET is not fine with a STATE-smart implementation of "dual-semantics" words.

Accepted 9/0/1 (Yes/No/Abstain) in 2018

Diaperglu has words similar to FIND-NAME and FIND-NAME-IN except they return an execution token. This execution token is the index of a name value pair, where the name is the word's name, and the value is the header containing the PFA and CFA for the word. I tried to digest everything that was said above, my question is, would an implementation that treated name tokens and execution tokens as being the same thing cause any problems? Basically NAME>INTERPRET and NAME>COMPILE would still be in the wordlist but do nothing to the token.

Also I have to agree with the comment that NAME>INTERPRET and NAME>COMPILE are misnamed if NAME is going to be shorthand for a name token for these definitions, and mean something else in others. If the term NAME is going to be shorthand for name token across the board then I think it's a good idea. Up to now I was thinking the term 'name' was the replacement for 'word' which meant a series of non white-space delimiter characters. If name is going to mean name token, what is the replacement term for a series of non white-space delimiter characters? (Please do not pick NW-SDC :-)

If you don't implement SYNONYM, and don't implement FILE S" (i.e., the interpretation semantics of S") or other dial-semantics words, you can implement xt=nt. For an extensive discussion, read Section 3 of The new Gforth Header.

would an implementation that treated name tokens and execution tokens as being the same thing cause any problems?

A Forth system can be implemented in such a way that nt and xt are the same thing without any problems with compliance to the standard. Some operation just would be a bit slower.

NAME>INTERPRET and NAME>COMPILE would still be in the wordlist but do nothing to the token.

In such case, NAME>COMPILE for the FILE S" word cannot return xt of EXECUTE at the top. It should return xt of some special EXECUTE-COMPILING word.

  : token-compile-for-s" ( -- x xt ) nt-of-s"  ['] execute-compiling ;

Another variant is that NAME>COMPILE for S" returns another nt and xt of EXECUTE.

  : token-compile-for-s" ( -- x xt ) nt-of-s"-compiling  ['] execute ;

If you don't implement SYNONYM

Also, I don't see any problem to implement SYNONYM.