This document is produced by TC X3J14 as its clarification of questions raised about ANSI X3.215-1994, American National Standard for Information Systems - Programming Languages - Forth.

The questions covered herein were raised by query

Q0002, regarding the significance of defining search orders in which a given wordlist occurs more than once.

There are four parts in this document:

  1. The original question as received.
  2. The TC's reply.
  3. The Letter Ballot issued by TC Chair.
  4. TC Chair's statement of ballot results.

Q0002 as received

The following query has been assigned number Q0002 and has been tentatively assigned to Mitch Bradley for drafting a response. - Greg Bailey, by direction, Tue, 21 Mar 95 12:44:17 PST
Subject: request for interpretation
To: x3j14@minerva.com
Cc: beebeebee@aol.com
From: John Rible 
Date: Fri, 17 Mar 1995 01:46:52 -0800
Message-Id: <199503170944.BAA21566@mail3.netcom.com>
Received: from cruzio.com by med3.minerva.com   ; Fri, 17 Mar 1995 01:48 PST
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
>From jrible Fri Mar 17 01:46:52 0800 1995 remote from cruzio.com
Received: from cruzio.com by mail3.netcom.com (8.6.10/Netcom) id BAA21566; 
Fri, 17 Mar 1995 01:44:27 -0800
Received: from cruzio38.cruzio.com by cruzio.cruzio.com id aa29048; 17 Mar 95 
1:40 PST
X-Sender: jrible@cruzio.com
X-Mailer: 
Content-Length: 2656
folks-

A friend has implemented wordlists using a linked-list to maintain the search order. He put two links in each wordlist structure, one for a static list of wordlists, the other a dynamic link for the search order. This avoided having to allocate an arbitrary amount of space for the search order list/stack.

After arguing with him that this is not compliant with the standard, I can't find anything explicit that backs me up. The problem with his method is that each wordlist can only appear ONCE in the search order. Well, that's not a problem in itself, but when a wordlist already in the search order is added to the top its previous location is lost! Again, that's not a real problem if the complete search order is always set explicitly, since the deeper occurrance will never produce a match.

But it sure messes up partial search order changes, such as using ALSO or PREVIOUS to temporarily change the order. For example, the following sequence will hang his system:

ONLY FORTH
VOCABULARY HIDDEN
...
ALSO HIDDEN ALSO FORTH  \ so FORTH is searched first
...
PREVIOUS                \ FORTH is no longer in the search order!!!
The requirement that I can't find, but believe that we intended, based on extensive common practice, would require the phrase set-order get-order to have no effect on the stack (as long as set-order got valid arguments, anyway). The problem sure seemed obvious to me, but he doesn't think it is, and even came up with the following definitions to deal with the issue:
' NIP  VALUE 'ALSO

: ALSO ( - ) ['] 1+  TO 'ALSO ;
: ONLY ( - ) -1 SET-ORDER  ['] NIP  TO 'ALSO ;
: PREVIOUS ( - ) GET-ORDER  NIP 1-  SET-ORDER ;
:  ( wid - ) \ wid is the address of the wordlist data structure
   >R GET-ORDER  'ALSO EXECUTE  R> SWAP  SET-ORDER  ['] NIP  TO 'ALSO ;

: FORTH ( - ) FORTH-WORDLIST  ;
: VOCABULARY ( 'name' - )  CREATE  ...  DOES>  ;

While these deal with some of the situations of adding and removing search-order entries, I've seen a lot of places (in Sun's OpenBoot, for example) where existing code would go up in flames if temporarily adding and removing a vocabulary that happened to already be in the search order took it out completely, as in my example above. Of course, the pathological (but currently working) ONLY FORTH ALSO PREVIOUS also leaves his search order empty.

Thanks for your responses (even the "you're a *&^#@*$%# idiot for wasting my time" ones add a data point!-)

John Rible  QuickSand  "hardware, software, and so forth"  jrible@cruzio.com
            317 California Street, Santa Cruz, CA  95060-4215   408-458-0399

TC Reply to Q0002

From: Erather@aol.com
Subject: Official Response to Q0002
To: X3J14 Technical Committee
Cc: lbarra@itic.nw.dc.us
Date: Fri, 31 Mar 95 12:52:24 PST  
Doc#:  X3J14/Q0002R
Reference Doc#:  X3.215.1994 ANS Forth
Date:  March 31, 1995
Title: Response to Request for Interpretation Q0002, Clarification of Search
Orders
Q0002 DRAFT rev 1
Key
Indicates lines from the original inquiry. The entiry text of the inquiry is cited in this way.
Indicates excerpts from the standard
Unmarked lines comprise the response to the inquiry.
A friend has implemented wordlists using a linked-list to maintain the search order. He put two links in each wordlist structure, one for a static list of wordlists, the other a dynamic link for the search order. This avoided having to allocate an arbitrary amount of space for the search order list/stack.

After arguing with him that this is not compliant with the standard, I can't find anything explicit that backs me up. The problem with his method is that each wordlist can only appear ONCE in the search order. Well, that's not a problem in itself, but when a wordlist already in the search order is added to the top its previous location is lost! Again, that's not a real problem if the complete search order is always set explicitly, since the deeper occurrance will never produce a match.

In the following excerpt from the definition of SET-ORDER, the phrase "word lists" means "sequence of word lists".
Set the search order to the word lists identified by widn ... wid1. Subsequently, ...
GET-ORDER must return exactly the same sequence of wids "widn .. wid1" that appeared in the arguments to the most recent execution of SET-ORDER, even if a particular word list identifier appears more than once in that sequence.

A Standard System is permitted to optimize its searching process so that the existence of repetetions in the search order need not result in redundant searches, but if so (a) the behavior of GET-ORDER and SET-ORDER must be as described in the preceding paragraph, and (b) the results of a search must be indistinguishable in all cases from the results were there no such optimizations.

But it sure messes up partial search order changes, such as using ALSO or PREVIOUS to temporarily change the order. For example, the following sequence will hang his system:
ONLY FORTH
VOCABULARY HIDDEN
...
ALSO HIDDEN ALSO FORTH  \ so FORTH is searched first
...
PREVIOUS                \ FORTH is no longer in the search order!!!
Historically, in most implementations of the ALSO .. ONLY search order mechanism, the sequence shown would result in the search order containing
 <minimum search order> <FORTH wordlist> <HIDDEN wordlist>
The standard intends to codify that existing practice.
The requirement that I can't find, but believe that we intended, based on extensive common practice, would require the phrase "set-order get-order" to have no effect on the stack (as long as set-order got valid arguments, anyway). The problem sure seemed obvious to me, but he doesn't think it is, and even came up with the following definitions to deal with the issue:
' NIP  VALUE 'ALSO

: ALSO ( - ) ['] 1+  TO 'ALSO ;
: ONLY ( - ) -1 SET-ORDER  ['] NIP  TO 'ALSO ;
: PREVIOUS ( - ) GET-ORDER  NIP 1-  SET-ORDER ;
:  ( wid - ) \ wid is the address of the wordlist data structure
   >R GET-ORDER  'ALSO EXECUTE  R> SWAP  SET-ORDER  ['] NIP  TO 'ALSO ;

: FORTH ( - ) FORTH-WORDLIST  ;
: VOCABULARY ( 'name' - )  CREATE  ...  DOES>  ;
With these definitions, the sequence "ALSO GET-ORDER" would not yield the result specified by the standard.
While these deal with some of the situations of adding and removing search-order entries, I've seen a lot of places (in Sun's OpenBoot, for example) where existing code would go up in flames if temporarily adding and removing a vocabulary that happened to already be in the search order took it out completely, as in my example above. Of course, the pathological (but currently working) ONLY FORTH ALSO PREVIOUS also leaves his search order empty.
The ANS Forth search order wordset is intended to provide a predictable mechanism for managing search orders in arbitrary ways, albeit subject to the system-dependent limitation on the maximum number of word lists. Some applications, for example, choose to use the search order as a "stack", adding and removing word lists without regard to whether or not those word lists already appear in the search order.

Letter Ballot

From: Erather@aol.com
Subject: Letter Ballot 013
To: X3J14 Technical Committee
Cc: lbarra@itic.nw.dc.us
Date: Fri, 31 Mar 95 12:54:18 PST  
X3 Subgroup Letter Ballot
Authorized by X3 Procedures - Distributed by X3 Subgroup X3J14  Project:
 X3J14, ANS Forth
Doc#:  X3J14/LB013
Reference Doc#s:  X3J14/Q0002R, X3.215.1994 ANS Forth
Date:  March 31, 1995
Title: Response to Request for Interpretation Q0002
Ballot Period:  30 Days
Ballot Closes NOON DATE:  April 30, 1995
Respond to:  greg@minerva.com
        or:  Elizabeth D. Rather, Chair
             FORTH, Inc.
             111 N. Sepulveda Blvd.  Suite 300
             Manhattan Beach, CA  90266
             (310) 372-8493    FAX (310) 318-7130

Statement:
    Document X3J14/Q0002R contains a proposed Response to Request for
    Interpretation Q0002.

Question:
    Do you agree that this response represents the intended interpretation of
    X3.215.1994 ANS Forth?

YES____ NO____ ABSTAIN____  [NO or ABSTAIN votes require an explanation]

Signature:  [not required for email ballots]
Name:
Organization:

INSTRUCTIONS:
Please return the entire letter ballot with your response _either_ by email
to greg@minerva.com _or_ by regular mail or fax to me at the above address,
before the closing date & time.

All TC members must vote.  Failure to vote in two consecutive ballots may
cause you to lose your voting rights in X3J14.

Thank you for your participation.

Elizabeth D. Rather, Chair, X3J14

Results of Letter Ballot

From: Erather@aol.com
Subject: Letter Ballot Results
To: X3J14 Technical Committee
Date: Fri, 05 May 95 18:50:18 PDT  
Letter ballots [12 and] 13 have closed.  Both passed.  Results follow.

[...]

Letter ballot 13:  13 yes, 1 no, 0 abstaining.

[...]

Jax [Jack Woehr] voted No on LB13.  His comments follow:

LB13, Woehr: I made a proposal which was drowned out in Mitch's discus-
sion with himself on the maillist. It was letting Mitch make all the
decisions in consultation with himself that got us in trouble at the
spring meeting in Oregon in 1992 and delayed the standard by about a
year. I expect my proposals to be heard, even if not adopted, in hopes
we can avoid similar problems in the future.

---------  FOR THE RECORD  -----------------------------------
[Here is the e-mail message to which Woehr refers.  The active
part of the discussion occurred over a three day period, involved
about a dozen e-mail messages, and had seven participants who
posted.]

>
> > I think Mitch has gotten the issue here backward.

<...>

>   the arguments that it passes to SET-ORDER be mutually distinct?
>
> I believe that the answer is emphatically "no".


 I agree with Mitch whole-heartedly. I would move to add that:

"It is the sense of the X3J14 TC that no element of SEARCH ORDER Wordset
introduces novelty into general Forth praxis, with the exception
that a WORDLIST now has a tangible representation on the stack, whereas
FORTH-83 VOCABULARY had no such tangible representation. In all other
respects the de-facto behavior of Forth search order operations are
utterly unchanged from Forth-83."

 Do I hear a second?

  =jax=

[...]

Thank you all for your participation.  Of the 14 votes received, 9 came by
email, and the rest by fax (plus mine!).

Regards...
Elizabeth