Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #32667 > unrolled thread

Re: Vocabularies

Back to article view | Back to comp.lang.forth

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Vocabularies chitselb <chitselb@gmail.com> - 2014-07-25 20:30 -0700
    Re: Vocabularies bruce.mcfarling@gmail.com - 2014-07-25 23:00 -0700
    Re: Vocabularies "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-26 05:40 -0400
      Re: Vocabularies Mark Wills <markwills1970@gmail.com> - 2014-07-26 04:29 -0700
        Re: Vocabularies "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-07-26 07:41 -0400
          Re: Vocabularies "Elizabeth D. Rather" <erather@forth.com> - 2014-07-26 13:58 +0000
            Re: Vocabularies chitselb <chitselb@gmail.com> - 2014-07-26 16:13 -0700
              Re: Vocabularies bruce.mcfarling@gmail.com - 2014-07-26 23:32 -0700
                Re: Vocabularies chitselb <chitselb@gmail.com> - 2014-08-01 13:48 -0700
                  Re: Vocabularies albert@spenarnc.xs4all.nl (Albert van der Horst) - 2014-08-19 11:09 +0000

#32667 — Re: Vocabularies

On Thursday, June 2, 2011 8:39:08 AM UTC-4, Mark Wills wrote:
> A vocabulary may be created using:
> 
> VOCABULARY <NAME>
> 
> Question: When a new vocabulary is created, does it become the CURRENT
> vocabulary at the same time?
> 
> Mark.

http://lars.nocrew.org/dpans/dpansa16.htm says, in part,

"Search-order specification and control mechanisms vary widely. The FIG-Forth, Forth-79, polyFORTH, and Forth-83 vocabulary and search order mechanisms are all mutually incompatible. The complete list of incompatible mechanisms, in use or proposed, is much longer. The ALSO/ONLY scheme described in a Forth-83 Experimental Proposal has substantial community support. However, many consider it to be fundamentally flawed, and oppose it vigorously.

Recognizing this variation, this Standard specifies a new primitive set of tools from which various schemes may be constructed. This primitive search-order word set is intended to be a portable construction set from which search-order words may be built, rather than a user interface. ALSO/ONLY or the various vocabulary schemes supported by the major Forth vendors can be defined in terms of the primitive search-order word set."

This makes me wonder, what are the available approaches?  Considering this question in the context of my own project, I came up with four.

1) no vocabularies at all, because c'mon it's only got 32K RAM or maybe 64K on the C=64 port
2) Linked lists with the $81A0 word at the end of a vocabulary chain (a 1-byte length, word name is " ", high bits are set on length byte and on last byte of name field for TRAVERSE.  Found in Blazin' Forth)
3) Vocabularies are implemented by appending a "vocab id" byte to the end of a word and setting the "V" bit (true meaning "I belong to a Vocabulary, take a look at the last byte in the Name Field to find out which one")
4) Implement the optional ANS Forth Search Order Wordset described at http://lars.nocrew.org/dpans/dpansa16.htm (I guess I'm calling this the "vocabulary construction kit" approach)

And then if I implement vocabularies, there's the question of search order, I'm not really sure what I want to do yet.  What makes some people hate on ONLY/ALSO ?  I've never really used them before.  If someone put a gun to my head and said "describe your preferred Vocabulary design NOW, in one paragraph, or I'll shoot" I would say something like:

Words that belong to a non-Core vocabulary get a byte appended to the end, their length increases by one, and that limits the longest word within a vocabulary to 30 characters in length.  (approach 3).  For search order, there's a queue, maximum length 10, of bytes.  FIND will process this queue from left to right, and stop after processing a "0", which searches the core wordlist.  VOCABULARY FOO creates a new vocabulary inside the CURRENT vocabulary, invoking FOO makes foo be the first entry searched in the vocabulary queue, and FOO DEFINITIONS makes foo the CURRENT vocabulary.   

[toc] | [next] | [standalone]

#32668

On Friday, July 25, 2014 11:30:41 PM UTC-4, chitselb wrote:
> Words that belong to a non-Core vocabulary get a byte appended to the end, their length increases by one, and that limits the longest word within a vocabulary to 30 characters in length.  (approach 3).

> For search order, there's a queue, maximum length 10, of bytes.  FIND will process this queue from left to right, and stop after processing a "0", which searches the core wordlist.  VOCABULARY FOO creates a new vocabulary inside the CURRENT vocabulary, invoking FOO makes foo be the first entry searched in the vocabulary queue, and FOO DEFINITIONS makes foo the CURRENT vocabulary.

That's a bit more intricate than the simplest WORDLIST based system, where a WORDLIST is just a cell in dataspace that holds the address of the last word in the wordlist, initialized to 0. Newly defined words get added to the wordlist pointed to by CURRENT and the inner factor for FIND / HUNT or etc. takes the most recent word in a wordlist as a factor, so the outer loop is just a step down a cell stack until the stack is exhausted or the word is found.

[toc] | [prev] | [next] | [standalone]

#32683

On Fri, 25 Jul 2014 23:30:41 -0400, chitselb <chitselb@gmail.com> wrote:

> "Search-order specification and control mechanisms vary widely. The  
> FIG-Forth, Forth-79, polyFORTH, and Forth-83 vocabulary and search order  
> mechanisms are all mutually incompatible. The complete list of  
> incompatible mechanisms, in use or proposed, is much longer. The  
> ALSO/ONLY scheme described in a Forth-83 Experimental Proposal has  
> substantial community support. However, many consider it to be  
> fundamentally flawed, and oppose it vigorously.
>
> Recognizing this variation, this Standard specifies a new primitive set  
> of tools from which various schemes may be constructed. This primitive  
> search-order word set is intended to be a portable construction set from  
> which search-order words may be built, rather than a user interface.  
> ALSO/ONLY or the various vocabulary schemes supported by the major Forth  
> vendors can be defined in terms of the primitive search-order word set."
>
> This makes me wonder, what are the available approaches?

Good question.

> Considering this question in the context of my own project, I came up  
> with four.
>
> 1) no vocabularies at all, because c'mon it's only got 32K RAM or maybe  
> 64K on the C=64 port

My understanding, which may be incomplete, is that you need at least one.
Otherwise, Forth can't FIND any words to EXECUTE .

> 2) Linked lists with the $81A0 word at the end of a vocabulary chain (a  
> 1-byte length, word name is " ", high bits are set on length byte and on  
> last byte of name field for TRAVERSE.  Found in Blazin' Forth)

I'm wondering what is the advantage of this?

> 3) Vocabularies are implemented by appending a "vocab id" byte to the  
> end of a word and setting the "V" bit (true meaning "I belong to a  
> Vocabulary, take a look at the last byte in the Name Field to find out  
> which one")

...

> 4) Implement the optional ANS Forth Search Order Wordset described at  
> [link] (I guess I'm calling this the "vocabulary construction kit"  
> approach)

I haven't looked at this for my own Forth.  I'd probably convert to
it later on, if I think it makes sense.  I clearly didn't start with
this, and think it's probably not necessarily a good idea to do so.
You want something which works, first.  You can then fix it, once
you understand why it is wrong, or should be changed.

> And then if I implement vocabularies, there's the question of search  
> order, I'm not really sure what I want to do yet.  What makes some  
> people hate on ONLY/ALSO ?  I've never really used them before.

...

> If someone put a gun to my head and said "describe your preferred  
> Vocabulary design NOW, in one paragraph, or I'll shoot" I would say  
> something like:
>
> Words that belong to a non-Core vocabulary get a byte appended to the  
> end, their length increases by one, and that limits the longest word  
> within a vocabulary to 30 characters in length.  (approach 3).  For  
> search order, there's a queue, maximum length 10, of bytes.  FIND will  
> process this queue from left to right, and stop after processing a "0",  
> which searches the core wordlist.  VOCABULARY FOO creates a new  
> vocabulary inside the CURRENT vocabulary, invoking FOO makes foo be the  
> first entry searched in the vocabulary queue, and FOO DEFINITIONS makes  
> foo the CURRENT vocabulary.
>

There are other ways than just length to reduce dictionary search time.
E.g., you can use hash values to reduce string comparison, or use the
first character to reject incorrect strings faster.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#32689

I never bothered implementING them in my system for two reasons:

* its only got 32k of ram
* find is written in machine code and can search the dictionary in the blink of an eye. 

[toc] | [prev] | [next] | [standalone]

#32690

On Sat, 26 Jul 2014 07:29:11 -0400, Mark Wills <markwills1970@gmail.com>  
wrote:

> I never bothered implementING them in my system for two reasons:
>
> * its only got 32k of ram
> * find is written in machine code and can search the dictionary in the  
> blink of an eye.

I'm taking it I've conflated two things: dictionary and vocabularies.


Rod Pemberton

[toc] | [prev] | [next] | [standalone]

#32696

On 7/26/14 11:41 AM, Rod Pemberton wrote:
> On Sat, 26 Jul 2014 07:29:11 -0400, Mark Wills <markwills1970@gmail.com>
> wrote:
>
>> I never bothered implementING them in my system for two reasons:
>>
>> * its only got 32k of ram
>> * find is written in machine code and can search the dictionary in the
>> blink of an eye.
>
> I'm taking it I've conflated two things: dictionary and vocabularies.

Yes. The dictionary is where all word headers are. It is searchable, 
whether you have the option of multiple search orders or not. If you 
have multiple search orders, the usual approach is to have the address 
of the most recent definition in a place referenced by CONTEXT, and that 
is the top of a chain through the dictionary. CURRENT is the top of the 
chain that new words are to be linked to.

"Vocabularies" are an implementation specification for managing multiple 
search orders, including setting CONTEXT and CURRENT.

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."
==================================================

[toc] | [prev] | [next] | [standalone]

#32701

In the implementation I'm doing, there are no linked lists.  Symbols ("heads") are separated from code in the dictionary.  There are 16 threads ordered by size, balanced and distinguished from one another by a Pearson hash on the word name itself.  The 17th thread is marked at the beginning by SYMNEW and at the end by SYMTAIL, where new names are appended.  FORGET/REHASH empties out SYMNEW and rebalances the 16 threads.  

Vocabularies are implemented by setting a bit on the name's flags/size byte and appending a Vocabulary ID at the end of the name.  0x01 is the ID reserved for the ASSEMBLER vocabulary.  My intent is to have a queue of Vocabulary IDs that terminates with 0x00 (search FORTH last) and somehow manage that queue to establish search order.

I've seen tree-structured vocabularies before, where a Vocabulary might nest within a parent vocabulary.  I'm also considering a flat approach, with FORTH  the immediate parent of every other vocabulary and first-to-last processing of the queue determines search order.  When I saw this in the ANS standard comments, I wanted to find out what else was possible, what had been tried, and what the detractors of the ALSO/ONLY method would say.

[toc] | [prev] | [next] | [standalone]

#32707

On Saturday, July 26, 2014 7:13:15 PM UTC-4, chitselb wrote:
> In the implementation I'm doing, there are no linked lists.  Symbols ("heads") are separated from code in the dictionary.  There are 16 threads ordered by size, balanced and distinguished from one another by a Pearson hash on the word name itself.  The 17th thread is marked at the beginning by SYMNEW and at the end by SYMTAIL, where new names are appended.  FORGET/REHASH empties out SYMNEW and rebalances the 16 threads.  

 
> Vocabularies are implemented by setting a bit on the name's flags/size byte and appending a Vocabulary ID at the end of the name.  0x01 is the ID reserved for the ASSEMBLER vocabulary.  My intent is to have a queue of Vocabulary IDs that terminates with 0x00 (search FORTH last) and somehow manage that queue to establish search order.

Note that with the bit, the vocabulary byte can be implicit, and doesn't need to be included in the count.

If the system starts with Forth as the sole entry in the stack and FORTH resets the stack to one with nothing but FORTH ~ you don't need to rig the system to search FORTH last, the search order will do it naturally.

If you don't include the vocabulary byte in the hash, you can stop on a match. Step down the cell stack to see how far from the top that vocabulary is ... if its further up the stack than a previous match, it replaces the previous match. Go to the end of the set of words, and any surviving match is highest in the search order. If you match out of the top vocabulary in the search order, you know that's the one and don't have to search further.

> I've seen tree-structured vocabularies before, where a Vocabulary might nest within a parent vocabulary.  I'm also considering a flat approach, with FORTH  the immediate parent of every other vocabulary and first-to-last processing of the queue determines search order.

If you want FORTH to be the parent of all other vocabularies, then have the vocabulary defining word automatically define into FORTH, and have FORTH be the word that resets the search order.

[toc] | [prev] | [next] | [standalone]

#32818

On Sunday, July 27, 2014 2:32:22 AM UTC-4, bruce.m...@gmail.com wrote:
> On Saturday, July 26, 2014 7:13:15 PM UTC-4, chitselb wrote:
> 
> > In the implementation I'm doing, there are no linked lists.  Symbols ("heads") are separated from code in the dictionary.  There are 16 threads ordered by size, balanced and distinguished from one another by a Pearson hash on the word name itself.  The 17th thread is marked at the beginning by SYMNEW and at the end by SYMTAIL, where new names are appended.  FORGET/REHASH empties out SYMNEW and rebalances the 16 threads.  
> 
> 
> 
>  
> 
> > Vocabularies are implemented by setting a bit on the name's flags/size byte and appending a Vocabulary ID at the end of the name.  0x01 is the ID reserved for the ASSEMBLER vocabulary.  My intent is to have a queue of Vocabulary IDs that terminates with 0x00 (search FORTH last) and somehow manage that queue to establish search order.
> 
> 
> 
> Note that with the bit, the vocabulary byte can be implicit, and doesn't need to be included in the count.
> 
> 
> 
> If the system starts with Forth as the sole entry in the stack and FORTH resets the stack to one with nothing but FORTH ~ you don't need to rig the system to search FORTH last, the search order will do it naturally.
> 
> 
> 
> If you don't include the vocabulary byte in the hash, you can stop on a match. Step down the cell stack to see how far from the top that vocabulary is ... if its further up the stack than a previous match, it replaces the previous match. Go to the end of the set of words, and any surviving match is highest in the search order. If you match out of the top vocabulary in the search order, you know that's the one and don't have to search further.
> 
> 
> 
> > I've seen tree-structured vocabularies before, where a Vocabulary might nest within a parent vocabulary.  I'm also considering a flat approach, with FORTH  the immediate parent of every other vocabulary and first-to-last processing of the queue determines search order.
> 
> 
> 
> If you want FORTH to be the parent of all other vocabularies, then have the vocabulary defining word automatically define into FORTH, and have FORTH be the word that resets the search order.

Thanks, Bruce!  The trick with using the flag in lieu of extending the size, I had not thought of.  Having the imprimatur of someone whose opinions I respect makes it easier to depart from the well-trodden path of vocabulary implementation.  I'll be doing (something very like) what you suggest.

The vocabulary stack ( VSTACK ) will be a 10-byte list of one-byte Vocabulary IDs (vocid).  Invoking a vocabulary will push it to the front of VSTACK, and invoking FORTH will empty VSTACK.   

CONTEXT and CURRENT are gone.  VSTACK replaces the functionality of CONTEXT, and CURRENT is replaced by VCURRENT, which holds the vocid of the vocabulary where new definitions are created.  

VOCABULARY is the exception to this.  New vocabularies are always defined as members of the root vocabulary, ignoring but not modifying VCURRENT. This vocabulary model is flat.  There are no nested vocabularies, just simple left-to-right processing of VSTACK until 0 is encountered.  FORTH/core/root/main vocabulary is always searched last.

The development system will ship with one non-root vocabulary, the ASSEMBLER wordset as vocid=0x01.

Here's FIND

: find ( name -- [c|n]fa flag )
    dup bloom# >bit bloom + cbit@       \ check Bloom filter
    if
        >r  vstack
 ( vstack ) ( R; name )
        begin
            c@+ r@ over
            ?: (vocfind) (find)
 ( vptr voc nfa cfa found? ) ( R; name )
            ?dup
            if
                rdrop 2>r 3drop 2r> exit   \ found?  leave with prejudice
            then
            2drop 0=
        until
        drop r>
    then 
    false ;

[toc] | [prev] | [next] | [standalone]

#32964

In article <17d4bdae-672b-40f5-b217-4a5c595f6d3d@googlegroups.com>,
chitselb  <chitselb@gmail.com> wrote:
>On Sunday, July 27, 2014 2:32:22 AM UTC-4, bruce.m...@gmail.com wrote:
>> On Saturday, July 26, 2014 7:13:15 PM UTC-4, chitselb wrote:
>>
>> > In the implementation I'm doing, there are no linked lists.  Symbols
>("heads") are separated from code in the dictionary.  There are 16
>threads ordered by size, balanced and distinguished from one another by
>a Pearson hash on the word name itself.  The 17th thread is marked at
>the beginning by SYMNEW and at the end by SYMTAIL, where new names are
>appended.  FORGET/REHASH empties out SYMNEW and rebalances the 16
>threads.
>>
>>
>>
>>
>>
>> > Vocabularies are implemented by setting a bit on the name's
>flags/size byte and appending a Vocabulary ID at the end of the name.
>0x01 is the ID reserved for the ASSEMBLER vocabulary.  My intent is to
>have a queue of Vocabulary IDs that terminates with 0x00 (search FORTH
>last) and somehow manage that queue to establish search order.
>>
>>
>>
>> Note that with the bit, the vocabulary byte can be implicit, and
>doesn't need to be included in the count.
>>
>>
>>
>> If the system starts with Forth as the sole entry in the stack and
>FORTH resets the stack to one with nothing but FORTH ~ you don't need to
>rig the system to search FORTH last, the search order will do it
>naturally.
>>
>>
>>
>> If you don't include the vocabulary byte in the hash, you can stop on
>a match. Step down the cell stack to see how far from the top that
>vocabulary is ... if its further up the stack than a previous match, it
>replaces the previous match. Go to the end of the set of words, and any
>surviving match is highest in the search order. If you match out of the
>top vocabulary in the search order, you know that's the one and don't
>have to search further.
>>
>>
>>
>> > I've seen tree-structured vocabularies before, where a Vocabulary
>might nest within a parent vocabulary.  I'm also considering a flat
>approach, with FORTH  the immediate parent of every other vocabulary and
>first-to-last processing of the queue determines search order.
>>
>>
>>
>> If you want FORTH to be the parent of all other vocabularies, then
>have the vocabulary defining word automatically define into FORTH, and
>have FORTH be the word that resets the search order.
>
>Thanks, Bruce!  The trick with using the flag in lieu of extending the
>size, I had not thought of.  Having the imprimatur of someone whose
>opinions I respect makes it easier to depart from the well-trodden path
>of vocabulary implementation.  I'll be doing (something very like) what
>you suggest.
>
>The vocabulary stack ( VSTACK ) will be a 10-byte list of one-byte
>Vocabulary IDs (vocid).  Invoking a vocabulary will push it to the front
>of VSTACK, and invoking FORTH will empty VSTACK.
>
>CONTEXT and CURRENT are gone.  VSTACK replaces the functionality of
>CONTEXT, and CURRENT is replaced by VCURRENT, which holds the vocid of
>the vocabulary where new definitions are created.

This is very similar to ciforth's model.
1.
I don't have a new word for CONTEXT. I have a VSTACK and call it CONTEXT.
If you fetch it you get the CONTEXT. I can do that because the VSTACK
contains cells.
2.
I don't end in a null, but in a worlist id that contains the words
of the minimum search order: the ONLY wordlist. ONLY can be like other
vocabularies putting its id on the stack, effectively hiding what was there.
It contains the word FORTH that will regain control towards a normal
system. Officially the way to gain control from the minimum search-order
is using FORTH-WORDLIST and SET-ORDER. I wonder how many people actually
do that.

3.
I can't see why you change the name of a word that has the ANSI
behaviour of CURRENT to something else.

>
>VOCABULARY is the exception to this.  New vocabularies are always
>defined as members of the root vocabulary, ignoring but not modifying
>VCURRENT. This vocabulary model is flat.  There are no nested
>vocabularies, just simple left-to-right processing of VSTACK until 0 is
>encountered.  FORTH/core/root/main vocabulary is always searched last.

As VOCABULARY is not a standard word, you can do this. It may be a
good idea. Now one has to follow vocabulary links, if implemented.

>
>The development system will ship with one non-root vocabulary, the
>ASSEMBLER wordset as vocid=0x01.
>
>Here's FIND
>
>: find ( name -- [c|n]fa flag )
>    dup bloom# >bit bloom + cbit@       \ check Bloom filter
>    if
>        >r  vstack
> ( vstack ) ( R; name )
>        begin
>            c@+ r@ over
>            ?: (vocfind) (find)
> ( vptr voc nfa cfa found? ) ( R; name )
>            ?dup
>            if
>                rdrop 2>r 3drop 2r> exit   \ found?  leave with prejudice
>            then
>            2drop 0=
>        until
>        drop r>
>    then
>    false ;
>

Groetjes Albert
-- 
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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web