A0002.HTM (17319B)
1 <title>ANS Forth RFI 0002: search orders in which a given wordlist 2 occurs more than once</title> 3 4 This document is produced by TC X3J14 as its clarification of questions 5 raised about ANSI X3.215-1994, American National Standard for Information 6 Systems - Programming Languages - Forth. 7 8 <p>The questions covered herein were raised by query 9 10 <p>Q0002, regarding the significance of defining search orders in 11 which a given wordlist occurs more than once. 12 13 <p>There are four parts in this document: 14 15 <ol> 16 <li><a href="#query">The original question as received.</a> 17 <li><a href="#reply">The TC's reply.</a> 18 <li><a href="#ballot">The Letter Ballot issued by TC Chair.</a> 19 <li><a href="#results">TC Chair's statement of ballot results.</a> 20 </ol> 21 22 <h2><a name="query">Q0002 as received</a></h2> 23 24 The following query has been assigned number Q0002 and has been 25 tentatively assigned to Mitch Bradley for drafting a response. 26 - Greg Bailey, by direction, Tue, 21 Mar 95 12:44:17 PST 27 <hr> 28 29 <pre> 30 Subject: request for interpretation 31 To: x3j14@minerva.com 32 Cc: beebeebee@aol.com 33 From: John Rible <jrible@cruzio.com> 34 Date: Fri, 17 Mar 1995 01:46:52 -0800 35 Message-Id: <199503170944.BAA21566@mail3.netcom.com> 36 Received: from cruzio.com by med3.minerva.com ; Fri, 17 Mar 1995 01:48 PST 37 Mime-Version: 1.0 38 Content-Type: text/plain; charset="us-ascii" 39 >From jrible Fri Mar 17 01:46:52 0800 1995 remote from cruzio.com 40 Received: from cruzio.com by mail3.netcom.com (8.6.10/Netcom) id BAA21566; 41 Fri, 17 Mar 1995 01:44:27 -0800 42 Received: from cruzio38.cruzio.com by cruzio.cruzio.com id aa29048; 17 Mar 95 43 1:40 PST 44 X-Sender: jrible@cruzio.com 45 X-Mailer: <PC Eudora Version 1.4> 46 Content-Length: 2656 47 </pre> 48 49 folks- 50 51 <p> 52 A friend has implemented wordlists using a linked-list to maintain the search 53 order. He put two links in each wordlist structure, one for a static list of 54 wordlists, the other a dynamic link for the search order. This avoided having 55 to allocate an arbitrary amount of space for the search order list/stack. 56 57 <p> 58 After arguing with him that this is not compliant with the standard, I can't 59 find anything explicit that backs me up. The problem with his method is that 60 each wordlist can only appear ONCE in the search order. Well, that's not a 61 problem in itself, but when a wordlist already in the search order is added 62 to the top its previous location is lost! Again, that's not a real problem if 63 the complete search order is always set explicitly, since the deeper 64 occurrance 65 will never produce a match. 66 67 <p> 68 But it sure messes up partial search order changes, such as using <a href=dpans16.htm#16.6.2.0715>ALSO</a> or 69 <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> to temporarily change the order. For example, the following sequence 70 will hang his system: 71 72 <pre> 73 <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> 74 VOCABULARY HIDDEN 75 ... 76 <a href=dpans16.htm#16.6.2.0715>ALSO</a> HIDDEN <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans6.htm#6.2.2535>\</a> so FORTH is searched first 77 ... 78 <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> <a href=dpans6.htm#6.2.2535>\</a> FORTH is no longer in the search order!!! 79 </pre> 80 81 The requirement that I can't find, but believe that we intended, based on 82 extensive common practice, would require the phrase set-order get-order to 83 have no effect on the stack (as long as set-order got valid arguments, 84 anyway). 85 The problem sure seemed obvious to me, but he doesn't think it is, and even 86 came 87 up with the following definitions to deal with the issue: 88 89 <pre> 90 <a href=dpans6.htm#6.1.0070>'</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2405>VALUE</a> 'ALSO 91 92 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.1.0290>1+</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 93 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans6.htm#6.1.0080>(</a> - ) -1 <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 94 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.1.0300>1-</a> <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.0460>;</a> 95 <a href=dpans6.htm#6.1.0450>:</a> <VOCABULARY> <a href=dpans6.htm#6.1.0080>(</a> wid - ) <a href=dpans6.htm#6.2.2535>\</a> wid is the address of the wordlist data structure 96 <a href=dpans6.htm#6.1.0580>>R</a> <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> 'ALSO <a href=dpans6.htm#6.1.1370>EXECUTE</a> <a href=dpans6.htm#6.1.2060>R></a> <a href=dpans6.htm#6.1.2260>SWAP</a> <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 97 98 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans16.htm#16.6.1.1595>FORTH-WORDLIST</a> <VOCABULARY> <a href=dpans6.htm#6.1.0460>;</a> 99 <a href=dpans6.htm#6.1.0450>:</a> VOCABULARY <a href=dpans6.htm#6.1.0080>(</a> 'name' - ) <a href=dpans6.htm#6.1.1000>CREATE</a> ... <a href=dpans6.htm#6.1.1250>DOES></a> <VOCABULARY> <a href=dpans6.htm#6.1.0460>;</a> 100 </pre> 101 102 <p> 103 While these deal with some of the situations of adding and removing 104 search-order 105 entries, I've seen a lot of places (in Sun's OpenBoot, for example) where 106 existing code would go up in flames if temporarily adding and removing a 107 vocabulary that happened to already be in the search order took it out 108 completely, as in my example above. Of course, the pathological (but currently 109 working) <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> also leaves his search order empty. 110 111 <p> 112 Thanks for your responses (even the "you're a *&^#@*$%# idiot for wasting my 113 time" ones add a data point!-) 114 115 <pre> 116 John Rible QuickSand "hardware, software, and so forth" jrible@cruzio.com 117 317 California Street, Santa Cruz, CA 95060-4215 408-458-0399 118 </pre> 119 120 <h2><a name="reply">TC Reply to Q0002</a></h2> 121 122 <pre> 123 From: Erather@aol.com 124 Subject: Official Response to Q0002 125 To: X3J14 Technical Committee 126 Cc: lbarra@itic.nw.dc.us 127 Date: Fri, 31 Mar 95 12:52:24 PST 128 Doc#: X3J14/Q0002R 129 Reference Doc#: X3.215.1994 ANS Forth 130 Date: March 31, 1995 131 Title: Response to Request for Interpretation Q0002, Clarification of Search 132 Orders 133 </pre> 134 135 Q0002 DRAFT rev 1 136 137 <hr> 138 Key 139 140 <i><blockquote> 141 Indicates lines from the original inquiry. The entiry text of the 142 inquiry is cited in this way. 143 </blockquote></i> 144 145 <b><blockquote> 146 Indicates excerpts from the standard 147 </blockquote></b> 148 149 Unmarked lines comprise the response to the inquiry. 150 <hr> 151 152 <i><blockquote> 153 A friend has implemented wordlists using a linked-list to maintain 154 the search order. He put two links in each wordlist structure, one for 155 a static list of wordlists, the other a dynamic link for the search 156 order. This avoided having to allocate an arbitrary amount of space 157 for the search order list/stack. 158 159 <p> 160 After arguing with him that this is not compliant with the standard, I 161 can't find anything explicit that backs me up. The problem with his 162 method is that each wordlist can only appear ONCE in the search 163 order. Well, that's not a problem in itself, but when a wordlist 164 already in the search order is added to the top its previous location 165 is lost! Again, that's not a real problem if the complete search order 166 is always set explicitly, since the deeper occurrance will never 167 produce a match. 168 </blockquote></i> 169 170 In the following excerpt from the definition of <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a>, the phrase 171 "word lists" means "sequence of word lists". 172 173 <b><blockquote> 174 Set the search order to the word lists identified by widn ... wid1. 175 Subsequently, ... 176 </blockquote></b> 177 178 <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> must return exactly the same sequence of wids "widn .. wid1" that 179 appeared in the arguments to the most recent execution of <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a>, even 180 if a particular word list identifier appears more than once in that sequence. 181 182 <p> 183 A Standard System is permitted to optimize its searching process so that 184 the existence of repetetions in the search order need not result in redundant 185 searches, but if so (a) the behavior of <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> and <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> must be as 186 described in the preceding paragraph, and (b) the results of a search must 187 be indistinguishable in all cases from the results were there no such 188 optimizations. 189 190 <i><blockquote> 191 But it sure messes up partial search order changes, such as using <a href=dpans16.htm#16.6.2.0715>ALSO</a> 192 or <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> to temporarily change the order. For example, the 193 following sequence will hang his system: 194 195 <pre> 196 <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> 197 VOCABULARY HIDDEN 198 ... 199 <a href=dpans16.htm#16.6.2.0715>ALSO</a> HIDDEN <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans6.htm#6.2.2535>\</a> so <a href=dpans16.htm#16.6.2.1590>FORTH</a> is searched first 200 ... 201 <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> <a href=dpans6.htm#6.2.2535>\</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> is no longer in the search order!!! 202 </pre> 203 </blockquote></i> 204 205 Historically, in most implementations of the <a href=dpans16.htm#16.6.2.0715>ALSO</a> .. <a href=dpans16.htm#16.6.2.1965>ONLY</a> search order 206 mechanism, the sequence shown would result in the search order containing 207 208 <pre> 209 <minimum search order> <FORTH wordlist> <HIDDEN wordlist> 210 </pre> 211 212 The standard intends to codify that existing practice. 213 214 215 <i><blockquote> 216 The requirement that I can't find, but believe that we intended, based 217 on extensive common practice, would require the phrase "set-order get-order" 218 to have no effect on the stack (as long as set-order got valid arguments, 219 anyway). The problem sure seemed obvious to me, but he doesn't think it 220 is, and even came up with the following definitions to deal with the issue: 221 222 <pre> 223 <a href=dpans6.htm#6.1.0070>'</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2405>VALUE</a> 'ALSO 224 225 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.1.0290>1+</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 226 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans6.htm#6.1.0080>(</a> - ) -1 <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 227 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.1.0300>1-</a> <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.0460>;</a> 228 <a href=dpans6.htm#6.1.0450>:</a> <VOCABULARY> <a href=dpans6.htm#6.1.0080>(</a> wid - ) <a href=dpans6.htm#6.2.2535>\</a> wid is the address of the wordlist data structure 229 <a href=dpans6.htm#6.1.0580>>R</a> <a href=dpans16.htm#16.6.1.1647>GET-ORDER</a> 'ALSO <a href=dpans6.htm#6.1.1370>EXECUTE</a> <a href=dpans6.htm#6.1.2060>R></a> <a href=dpans6.htm#6.1.2260>SWAP</a> <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> <a href=dpans6.htm#6.1.2510>[']</a> <a href=dpans6.htm#6.2.1930>NIP</a> <a href=dpans6.htm#6.2.2295>TO</a> 'ALSO <a href=dpans6.htm#6.1.0460>;</a> 230 231 <a href=dpans6.htm#6.1.0450>:</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans6.htm#6.1.0080>(</a> - ) <a href=dpans16.htm#16.6.1.1595>FORTH-WORDLIST</a> <VOCABULARY> <a href=dpans6.htm#6.1.0460>;</a> 232 <a href=dpans6.htm#6.1.0450>:</a> VOCABULARY <a href=dpans6.htm#6.1.0080>(</a> 'name' - ) <a href=dpans6.htm#6.1.1000>CREATE</a> ... <a href=dpans6.htm#6.1.1250>DOES></a> <VOCABULARY> <a href=dpans6.htm#6.1.0460>;</a> 233 </pre> 234 </blockquote></i> 235 236 With these definitions, the sequence "ALSO GET-ORDER" would not yield the 237 result specified by the standard. 238 239 <i><blockquote> 240 While these deal with some of the situations of adding and removing 241 search-order entries, I've seen a lot of places (in Sun's OpenBoot, 242 for example) where existing code would go up in flames if temporarily 243 adding and removing a vocabulary that happened to already be in the 244 search order took it out completely, as in my example above. Of course, 245 the pathological (but currently working) <a href=dpans16.htm#16.6.2.1965>ONLY</a> <a href=dpans16.htm#16.6.2.1590>FORTH</a> <a href=dpans16.htm#16.6.2.0715>ALSO</a> <a href=dpans16.htm#16.6.2.2037>PREVIOUS</a> also 246 leaves his search order empty. 247 </blockquote></i> 248 249 The ANS Forth search order wordset is intended to provide a predictable 250 mechanism for managing search orders in arbitrary ways, albeit subject to 251 the system-dependent limitation on the maximum number of word lists. Some 252 applications, for example, choose to use the search order as a "stack", 253 adding and removing word lists without regard to whether or not those 254 word lists already appear in the search order. 255 256 <h2><a name="ballot">Letter Ballot</a></h2> 257 258 <pre> 259 From: Erather@aol.com 260 Subject: Letter Ballot 013 261 To: X3J14 Technical Committee 262 Cc: lbarra@itic.nw.dc.us 263 Date: Fri, 31 Mar 95 12:54:18 PST 264 X3 Subgroup Letter Ballot 265 Authorized by X3 Procedures - Distributed by X3 Subgroup X3J14 Project: 266 X3J14, ANS Forth 267 Doc#: X3J14/LB013 268 Reference Doc#s: X3J14/Q0002R, X3.215.1994 ANS Forth 269 Date: March 31, 1995 270 Title: Response to Request for Interpretation Q0002 271 Ballot Period: 30 Days 272 Ballot Closes NOON DATE: April 30, 1995 273 Respond to: greg@minerva.com 274 or: Elizabeth D. Rather, Chair 275 FORTH, Inc. 276 111 N. Sepulveda Blvd. Suite 300 277 Manhattan Beach, CA 90266 278 (310) 372-8493 FAX (310) 318-7130 279 280 Statement: 281 Document X3J14/Q0002R contains a proposed Response to Request for 282 Interpretation Q0002. 283 284 Question: 285 Do you agree that this response represents the intended interpretation of 286 X3.215.1994 ANS Forth? 287 288 YES____ NO____ ABSTAIN____ [NO or ABSTAIN votes require an explanation] 289 290 Signature: [not required for email ballots] 291 Name: 292 Organization: 293 294 INSTRUCTIONS: 295 Please return the entire letter ballot with your response _either_ by email 296 to greg@minerva.com _or_ by regular mail or fax to me at the above address, 297 before the closing date & time. 298 299 All TC members must vote. Failure to vote in two consecutive ballots may 300 cause you to lose your voting rights in X3J14. 301 302 Thank you for your participation. 303 304 Elizabeth D. Rather, Chair, X3J14 305 </pre> 306 307 <h2><a name="results">Results of Letter Ballot</a></h2> 308 309 <pre> 310 From: Erather@aol.com 311 Subject: Letter Ballot Results 312 To: X3J14 Technical Committee 313 Date: Fri, 05 May 95 18:50:18 PDT 314 Letter ballots [12 and] 13 have closed. Both passed. Results follow. 315 316 [...] 317 318 Letter ballot 13: 13 yes, 1 no, 0 abstaining. 319 320 [...] 321 322 Jax [Jack Woehr] voted No on LB13. His comments follow: 323 324 LB13, Woehr: I made a proposal which was drowned out in Mitch's discus- 325 sion with himself on the maillist. It was letting Mitch make all the 326 decisions in consultation with himself that got us in trouble at the 327 spring meeting in Oregon in 1992 and delayed the standard by about a 328 year. I expect my proposals to be heard, even if not adopted, in hopes 329 we can avoid similar problems in the future. 330 331 --------- FOR THE RECORD ----------------------------------- 332 [Here is the e-mail message to which Woehr refers. The active 333 part of the discussion occurred over a three day period, involved 334 about a dozen e-mail messages, and had seven participants who 335 posted.] 336 337 > 338 > > I think Mitch has gotten the issue here backward. 339 340 <...> 341 342 > the arguments that it passes to <a href=dpans16.htm#16.6.1.2197>SET-ORDER</a> be mutually distinct? 343 > 344 > I believe that the answer is emphatically "no". 345 346 347 I agree with Mitch whole-heartedly. I would move to add that: 348 349 "It is the sense of the X3J14 TC that no element of <a href=dpans17.htm#17.6.1.2191>SEARCH</a> <a href=dpans16.htm#16.6.2.1985>ORDER</a> Wordset 350 introduces novelty into general Forth praxis, with the exception 351 that a <a href=dpans16.htm#16.6.1.2460>WORDLIST</a> now has a tangible representation on the stack, whereas 352 FORTH-83 VOCABULARY had no such tangible representation. In all other 353 respects the de-facto behavior of Forth search order operations are 354 utterly unchanged from Forth-83." 355 356 Do I hear a second? 357 358 =jax= 359 360 [...] 361 362 Thank you all for your participation. Of the 14 votes received, 9 came by 363 email, and the rest by fax (plus mine!). 364 365 Regards... 366 Elizabeth 367 </pre>