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

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

Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search

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

Contents

  Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-11 08:52 -0700
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-11 08:06 -1000
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 02:46 -0700
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-12 08:33 -1000
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:55 -0400
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-16 13:02 -1000
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Andrew Haley <andrew29@littlepinkcloud.invalid> - 2014-10-17 03:58 -0500
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 07:39 -1000
                Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-17 20:30 -0400
                  Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 14:39 -1000
                    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-17 21:33 -0400
                      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-17 21:51 -1000
                        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Bernd Paysan <bernd.paysan@gmx.de> - 2014-10-18 13:51 +0200
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search dwarman@davidwarman.net - 2014-10-17 08:38 -0700
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:54 -0400
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-17 19:33 -0700
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Bernd Paysan <bernd.paysan@gmx.de> - 2014-10-11 22:39 +0200
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 02:50 -0700
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Elizabeth D. Rather" <erather@forth.com> - 2014-10-12 08:38 -1000
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-11 15:05 -0700
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-12 12:14 +0200
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search mfanyikazi@gmail.com - 2014-10-12 10:06 -0700
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search hughaguilar96@yahoo.com - 2014-10-12 15:50 -0700
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-13 01:02 +0200
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search jfong@ms4.hinet.net - 2014-10-12 21:11 -0700
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search Michael Barry <barrym95838@yahoo.com> - 2014-10-12 22:01 -0700
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-14 02:06 +0200
            Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:11 -0400
              Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-17 11:38 +0200
        Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:06 -0400
          Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search awegel@arcor.de (Alexander Wegel) - 2014-10-17 11:38 +0200
      Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 18:04 -0400
    Re: Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search "Rod Pemberton" <buzzoff@nonamewhichexists.cmm> - 2014-10-16 17:53 -0400

Page 1 of 2  [1] 2  Next page →

#33842 — Just an idea : B-tree on-disk storage of FORTH dictrionary words for fast indexing and search

Ideally , the forth dictionary is a linked list of data , a nice conventional way to store data , but what if you need to store more than just a linked list of forth words , then stuff begins to get interesting , recently I have been working on several projects where I needed to apply some kick-ass ADT stuff to sort and index a large array and ummm I just though that some of the ideas that I was working with would properly organise forth and make it super optimal.

I must admit that I am not the first person to ask this or even think about it but could someone tell me why there hasn't been any serious work done in trying to store the dictionary using an alternative structure other than linked lists? I know Chuck Moore has used a bit of hash tables in his flavours of the language but is that the end of it?

Anyone else think that this is a good idea?

[toc] | [next] | [standalone]

#33844

On 10/11/14 5:52 AM, mfanyikazi@gmail.com wrote:
> Ideally , the forth dictionary is a linked list of data , a nice conventional way to store data , but what if you need to store more than just a linked list of forth words , then stuff begins to get interesting , recently I have been working on several projects where I needed to apply some kick-ass ADT stuff to sort and index a large array and ummm I just though that some of the ideas that I was working with would properly organise forth and make it super optimal.
>
> I must admit that I am not the first person to ask this or even think about it but could someone tell me why there hasn't been any serious work done in trying to store the dictionary using an alternative structure other than linked lists? I know Chuck Moore has used a bit of hash tables in his flavours of the language but is that the end of it?
>
> Anyone else think that this is a good idea?
>

There have been many approaches to dictionary linking. Common strategies 
include multiple linked lists, with a hash algorithm applied to the name 
to select the list. Wordlists can be implemented simply by adding an 
offset to the hash. In the 90's, FORTH, Inc. did some research and 
determined that 16 lists was optimum (32 did not yield a measurable 
advantage).

A major constraint is the requirement for maintaining the order in which 
words were defined, so that you will always search from the most recent 
definitions toward less-recent.

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]

#33857

On Saturday, October 11, 2014 9:06:42 PM UTC+3, Elizabeth D. Rather wrote:
> On 10/11/14 5:52 AM, mfanyikazi@gmail.com wrote:
> 
> > Ideally , the forth dictionary is a linked list of data , a nice conventional way to store data , but what if you need to store more than just a linked list of forth words , then stuff begins to get interesting , recently I have been working on several projects where I needed to apply some kick-ass ADT stuff to sort and index a large array and ummm I just though that some of the ideas that I was working with would properly organise forth and make it super optimal.
> 
> >
> 
> > I must admit that I am not the first person to ask this or even think about it but could someone tell me why there hasn't been any serious work done in trying to store the dictionary using an alternative structure other than linked lists? I know Chuck Moore has used a bit of hash tables in his flavours of the language but is that the end of it?
> 
> >
> 
> > Anyone else think that this is a good idea?
> 
> >
> 
> 
> 
> There have been many approaches to dictionary linking. Common strategies 
> 
> include multiple linked lists, with a hash algorithm applied to the name 
> 
> to select the list. Wordlists can be implemented simply by adding an 
> 
> offset to the hash. In the 90's, FORTH, Inc. did some research and 
> 
> determined that 16 lists was optimum (32 did not yield a measurable 
> 
> advantage).
> 
> 
> 
> A major constraint is the requirement for maintaining the order in which 
> 
> words were defined, so that you will always search from the most recent 
> 
> definitions toward less-recent.
> 
> 
> 

Thanks for pointing this out , but does this single constraint have to stand in
the way of alternative design ideas? I mean .. a b-tree can be connected semantically to indicate the most recent definitions working towards less-recent , actually I am in favour of designing the first semantically aware FORTH engine , I don't think anyone has done this yet but it seems promising for future applications that will anyway work in a knowledge driven world.So far linked lists and hash tables are extremely abstract structures that make it difficult to attach any type of meta-data , sure the semantically linked FORTH engine would be extremely complex to design , assuming that the dictionary will not only hold executable FORTH words but maybe some data also , like images , spatial information etc ... ummmm come to think of it , this would be a kick-ass way to develop a highly domain independent AI engine ... like the human brain ... jee-buz , imagine having a dictionary of not only FORTH words but also other data semantically linked in  ... with the forth words being capable of performing actions on these data to further process for human consumption , it seems interesting enough .. perhaps I will think up some ideas and make some FORTH code while I am @ it :)

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

#33863

On 10/11/14 11:46 PM, mfanyikazi@gmail.com wrote:
> On Saturday, October 11, 2014 9:06:42 PM UTC+3, Elizabeth D. Rather wrote:
...
>> A major constraint is the requirement for maintaining the order in which
>> words were defined, so that you will always search from the most recent
>> definitions toward less-recent.
>>
>
> Thanks for pointing this out , but does this single constraint have to stand in
> the way of alternative design ideas? I mean .. a b-tree can be connected semantically to indicate the most recent definitions working towards less-recent , actually I am in favour of designing the first semantically aware FORTH engine , I don't think anyone has done this yet but it seems promising for future applications that will anyway work in a knowledge driven world.So far linked lists and hash tables are extremely abstract structures that make it difficult to attach any type of meta-data , sure the semantically linked FORTH engine would be extremely complex to design , assuming that the dictionary will not only hold executable FORTH words but maybe some data also , like images , spatial information etc ... ummmm come to think of it , this would be a kick-ass way to develop a highly domain independent AI engine ... like the human brain ... jee-buz , imagine having a dictionary of not only FORTH words but also other data semantically linked in  ... with the forth words being capa
ble of performing actions on these data to further process for human consumption , it seems interesting enough .. perhaps I will think up some ideas and make some FORTH code while I am @ it :)

The requirement (from Forth 2000X) is "When searching a word list for a 
definition name, the system shall search each word list from its last 
definition to its first." There is no restriction on how the dictionary 
is organized or searched, providing that the most recent definition of a 
word will be found in preference to any prior definition that may exist 
in the current search order.

The thrust of Forth standards efforts since ANS Forth has been to 
prescribe behavior and not implementation. Any implementation strategy 
that produces the behavior that Forth programmers expect is fine. This 
philosophy has opened the door to many productive approaches, such as 
optimizing code compilers.

Enjoy your project!

Aloha,
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]

#33961

On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather  
<erather@forth.com> wrote:

> The requirement (from Forth 2000X) is "When searching a word list for a  
> definition name, the system shall search each word list from its last  
> definition to its first." There is no restriction on how the dictionary  
> is organized or searched, providing that the most recent definition of a  
> word will be found in preference to any prior definition that may exist  
> in the current search order.

Unfortunately, requiring that the most recent definition of a word to be
found requires that the order of *all* other words be preserved in time
order they were defined.

E.g.,

: TODO 1 . ;
: FIXME TODO ;
: HELP1 FIXME ;
: TODO  2 . ;
: FIXME TODO ;
: HELP2 FIXME ;

How do you intend to keep HELP1 and HELP2 emitting the correct integer
_without_ also preserving the exact time ordered list of definitions for
TODO and FIXME ?

So, I would says there clearly is some restriction on how the dictionary
is organized and searched.


Rod Pemberton

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

#33965

On 10/16/14 11:55 AM, Rod Pemberton wrote:
> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
> <erather@forth.com> wrote:
>
>> The requirement (from Forth 2000X) is "When searching a word list for
>> a definition name, the system shall search each word list from its
>> last definition to its first." There is no restriction on how the
>> dictionary is organized or searched, providing that the most recent
>> definition of a word will be found in preference to any prior
>> definition that may exist in the current search order.
>
> Unfortunately, requiring that the most recent definition of a word to be
> found requires that the order of *all* other words be preserved in time
> order they were defined.

That is correct. However, 40 years of use has found this not in the 
least "unfortunate" but rather an asset that most users depend upon. If 
you want to have changeable behavior, use DEFER.

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]

#33973

Elizabeth D. Rather <erather@forth.com> wrote:
> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>> <erather@forth.com> wrote:
>>
>>> The requirement (from Forth 2000X) is "When searching a word list for
>>> a definition name, the system shall search each word list from its
>>> last definition to its first." There is no restriction on how the
>>> dictionary is organized or searched, providing that the most recent
>>> definition of a word will be found in preference to any prior
>>> definition that may exist in the current search order.
>>
>> Unfortunately, requiring that the most recent definition of a word to be
>> found requires that the order of *all* other words be preserved in time
>> order they were defined.
> 
> That is correct. However, 40 years of use has found this not in the 
> least "unfortunate" but rather an asset that most users depend upon.

Actually not: it only requires that identically-named words be
preserved in the order they were defined.  Otherwise, hashed
dictionaries could not work.

Andrew.

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

#33982

On 10/16/14 10:58 PM, Andrew Haley wrote:
> Elizabeth D. Rather <erather@forth.com> wrote:
>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>> <erather@forth.com> wrote:
>>>
>>>> The requirement (from Forth 2000X) is "When searching a word list for
>>>> a definition name, the system shall search each word list from its
>>>> last definition to its first." There is no restriction on how the
>>>> dictionary is organized or searched, providing that the most recent
>>>> definition of a word will be found in preference to any prior
>>>> definition that may exist in the current search order.
>>>
>>> Unfortunately, requiring that the most recent definition of a word to be
>>> found requires that the order of *all* other words be preserved in time
>>> order they were defined.
>>
>> That is correct. However, 40 years of use has found this not in the
>> least "unfortunate" but rather an asset that most users depend upon.
>
> Actually not: it only requires that identically-named words be
> preserved in the order they were defined.  Otherwise, hashed
> dictionaries could not work.

Well, yes. I was concentrating on the effects/semantics. You need to 
find the most recent definition of any name you search for.

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]

#33990

On Fri, 17 Oct 2014 04:58:20 -0400, Andrew Haley  
<andrew29@littlepinkcloud.invalid> wrote:
> Elizabeth D. Rather <erather@forth.com> wrote:
>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>> <erather@forth.com> wrote:

>>>> The requirement (from Forth 2000X) is "When searching a word list for
>>>> a definition name, the system shall search each word list from its
>>>> last definition to its first." There is no restriction on how the
>>>> dictionary is organized or searched, providing that the most recent
>>>> definition of a word will be found in preference to any prior
>>>> definition that may exist in the current search order.
>>>
>>> Unfortunately, requiring that the most recent definition of a word to  
>>> be
>>> found requires that the order of *all* other words be preserved in time
>>> order they were defined.
>>
>> That is correct. However, 40 years of use has found this not in the
>> least "unfortunate" but rather an asset that most users depend upon.
>
> Actually not: it only requires that identically-named words be
> preserved in the order they were defined.  Otherwise, hashed
> dictionaries could not work.
>

Are you saying it's valid to change this defining order?

: TODO 1 . ;
: FIXME TODO ;
: HELP1 FIXME ;
: TODO  2 . ;
: FIXME TODO ;
: HELP2 FIXME ;

E.g., to this order?

: TODO 1 . ;
: TODO  2 . ;
: FIXME TODO ;
: FIXME TODO ;
: HELP1 FIXME ;
: HELP2 FIXME ;

That has the identically-named words preserved in the order
they were defined, which is what you just stated.  Clearly,
this doesn't and wouldn't ever work correctly.

RP> So, my I think my earlier question remains valid.  How do you
RP> intend to keep HELP1 and HELP2 emitting the correct integer
RP> _without_ also preserving the exact time ordered list of
RP> definitions for TODO and FIXME ?


Rod Pemberton

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

#33991

On 10/17/14 2:30 PM, Rod Pemberton wrote:
> On Fri, 17 Oct 2014 04:58:20 -0400, Andrew Haley
> <andrew29@littlepinkcloud.invalid> wrote:
>> Elizabeth D. Rather <erather@forth.com> wrote:
>>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>>> <erather@forth.com> wrote:
>
>>>>> The requirement (from Forth 2000X) is "When searching a word list for
>>>>> a definition name, the system shall search each word list from its
>>>>> last definition to its first." There is no restriction on how the
>>>>> dictionary is organized or searched, providing that the most recent
>>>>> definition of a word will be found in preference to any prior
>>>>> definition that may exist in the current search order.
>>>>
>>>> Unfortunately, requiring that the most recent definition of a word
>>>> to be
>>>> found requires that the order of *all* other words be preserved in time
>>>> order they were defined.
>>>
>>> That is correct. However, 40 years of use has found this not in the
>>> least "unfortunate" but rather an asset that most users depend upon.
>>
>> Actually not: it only requires that identically-named words be
>> preserved in the order they were defined.  Otherwise, hashed
>> dictionaries could not work.
>>
>
> Are you saying it's valid to change this defining order?
>
> : TODO 1 . ;
> : FIXME TODO ;
> : HELP1 FIXME ;
> : TODO  2 . ;
> : FIXME TODO ;
> : HELP2 FIXME ;
>
> E.g., to this order?
>
> : TODO 1 . ;
> : TODO  2 . ;
> : FIXME TODO ;
> : FIXME TODO ;
> : HELP1 FIXME ;
> : HELP2 FIXME ;
>
> That has the identically-named words preserved in the order
> they were defined, which is what you just stated.  Clearly,
> this doesn't and wouldn't ever work correctly.

Yes, but you're trying to reference them before they've been compiled at 
all. Nobody ever said that would work.

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]

#33992

On Fri, 17 Oct 2014 20:39:51 -0400, Elizabeth D. Rather  
<erather@forth.com> wrote:
> On 10/17/14 2:30 PM, Rod Pemberton wrote:
>> On Fri, 17 Oct 2014 04:58:20 -0400, Andrew Haley
>> <andrew29@littlepinkcloud.invalid> wrote:
>>> Elizabeth D. Rather <erather@forth.com> wrote:
>>>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>>>> <erather@forth.com> wrote:

>>>>>> The requirement (from Forth 2000X) is "When searching a word list  
>>>>>> for
>>>>>> a definition name, the system shall search each word list from its
>>>>>> last definition to its first." There is no restriction on how the
>>>>>> dictionary is organized or searched, providing that the most recent
>>>>>> definition of a word will be found in preference to any prior
>>>>>> definition that may exist in the current search order.
>>>>>
>>>>> Unfortunately, requiring that the most recent definition of a word
>>>>> to be
>>>>> found requires that the order of *all* other words be preserved in  
>>>>> time
>>>>> order they were defined.
>>>>
>>>> That is correct. However, 40 years of use has found this not in the
>>>> least "unfortunate" but rather an asset that most users depend upon.
>>>
>>> Actually not: it only requires that identically-named words be
>>> preserved in the order they were defined.  Otherwise, hashed
>>> dictionaries could not work.
>>>
>>
>> Are you saying it's valid to change this defining order?
>>
>> : TODO 1 . ;
>> : FIXME TODO ;
>> : HELP1 FIXME ;
>> : TODO  2 . ;
>> : FIXME TODO ;
>> : HELP2 FIXME ;
>>
>> E.g., to this order?
>>
>> : TODO 1 . ;
>> : TODO  2 . ;
>> : FIXME TODO ;
>> : FIXME TODO ;
>> : HELP1 FIXME ;
>> : HELP2 FIXME ;
>>
>> That has the identically-named words preserved in the order
>> they were defined, which is what you just stated.  Clearly,
>> this doesn't and wouldn't ever work correctly.
>
> Yes, but you're trying to reference them before they've been
> compiled at all. Nobody ever said that would work.

The entire point was that they must be compiled in a certain order
to preserve their relationships.  Are you saying that _after_
the words have been compiled, then the dictionary is reorganized
and/or sorted?  What's the point in that?  Each definition
consumes space.  Sorting wastes time.  The best option would
be to leave them where they are in the linked-list and provide
an additional layer of indexing.  Of course, there needs to
be a point in time when that operation is cost-effective.
You're not going to do that over and over again or continuously.
So, you'd do it for the system dictionary, but not for user apps.


Rod Pemberton

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

#34005

On 10/17/14 3:33 PM, Rod Pemberton wrote:
> On Fri, 17 Oct 2014 20:39:51 -0400, Elizabeth D. Rather
> <erather@forth.com> wrote:
>> On 10/17/14 2:30 PM, Rod Pemberton wrote:
>>> On Fri, 17 Oct 2014 04:58:20 -0400, Andrew Haley
>>> <andrew29@littlepinkcloud.invalid> wrote:
>>>> Elizabeth D. Rather <erather@forth.com> wrote:
>>>>> On 10/16/14 11:55 AM, Rod Pemberton wrote:
>>>>>> On Sun, 12 Oct 2014 14:33:37 -0400, Elizabeth D. Rather
>>>>>> <erather@forth.com> wrote:
>
>>>>>>> The requirement (from Forth 2000X) is "When searching a word list
>>>>>>> for
>>>>>>> a definition name, the system shall search each word list from its
>>>>>>> last definition to its first." There is no restriction on how the
>>>>>>> dictionary is organized or searched, providing that the most recent
>>>>>>> definition of a word will be found in preference to any prior
>>>>>>> definition that may exist in the current search order.
>>>>>>
>>>>>> Unfortunately, requiring that the most recent definition of a word
>>>>>> to be
>>>>>> found requires that the order of *all* other words be preserved in
>>>>>> time
>>>>>> order they were defined.
>>>>>
>>>>> That is correct. However, 40 years of use has found this not in the
>>>>> least "unfortunate" but rather an asset that most users depend upon.
>>>>
>>>> Actually not: it only requires that identically-named words be
>>>> preserved in the order they were defined.  Otherwise, hashed
>>>> dictionaries could not work.
>>>>
>>>
>>> Are you saying it's valid to change this defining order?
>>>
>>> : TODO 1 . ;
>>> : FIXME TODO ;
>>> : HELP1 FIXME ;
>>> : TODO  2 . ;
>>> : FIXME TODO ;
>>> : HELP2 FIXME ;
>>>
>>> E.g., to this order?
>>>
>>> : TODO 1 . ;
>>> : TODO  2 . ;
>>> : FIXME TODO ;
>>> : FIXME TODO ;
>>> : HELP1 FIXME ;
>>> : HELP2 FIXME ;
>>>
>>> That has the identically-named words preserved in the order
>>> they were defined, which is what you just stated.  Clearly,
>>> this doesn't and wouldn't ever work correctly.
>>
>> Yes, but you're trying to reference them before they've been
>> compiled at all. Nobody ever said that would work.
>
> The entire point was that they must be compiled in a certain order
> to preserve their relationships.  Are you saying that _after_
> the words have been compiled, then the dictionary is reorganized
> and/or sorted?  What's the point in that?n

There is none. AFAIK no one has suggested such a thing.

> Each definition
> consumes space.  Sorting wastes time.  The best option would
> be to leave them where they are in the linked-list and provide
> an additional layer of indexing.  Of course, there needs to
> be a point in time when that operation is cost-effective.
> You're not going to do that over and over again or continuously.
> So, you'd do it for the system dictionary, but not for user apps.

I do not think the OP had any idea of sorting existing definitions. I 
think he was proposing to maintain definitions in a B-tree structure on 
disk from the time they were created. I still don't think disk is 
appropriate, but he didn't mean what you seem to think he meant.

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]

#34006

Elizabeth D. Rather wrote:
> There is none. AFAIK no one has suggested such a thing.

I've killfiled Rod a long time ago, just because of this sort of argument. 
He proves that you can misunderstand and misrepresent everything.  I hate it 
when the killfile filter sometimes doesn't work, and I have to see his 
nonsense.  And I hate it when someone responds to him, and I have to read 
his nonsense, too.  Please don't.  Just killfile him, he's an idiot at 
"feels like enlightenment" level.

You know why some Buddhists say one path to enlightenment is ingorance?  
Dunning-Kruger effect: The confidence level is highest when you are a 
complete idiot, decreases when you start gaining knowledge, and then, when 
you reach mastership, increases again, to reach another high at the real 
enlightenment.  However, real enlightenment is hard, so there's the fake 
enlightenment on the other side of the Dunning-Kruger valley, the "ignorance 
is bliss"-style "enlightenment".  The difference is: When you are really 
enlightened, you know everything, and all things you know are true, 
including your self-assessment, which means you know that you are enlighted.  
On the other side, you know nothing, everything you think of is wrong, 
including your self-assessment, which means you think you are enlighted.

Confucius says "only the idiots and the wise people never change".  So 
there's no point in arguing with either side: The idiot is always wrong, and 
will never change (there's no way to convince him), and the wise man is 
always right, and won't change either.  Fortunately, wise men are much rarer 
than idiots, in fact, the 100% sage doesn't exist.  But the 100% idiot is 
commonplace.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#33979

Back in 2002 +/- I implemented a Graphical Programing system called VNOS. Heirarchical tree of Views (much like a file system but all in the GUI). Scripts an be attached to anything in the system, and one of the languages I implemented was FORTH. I chose to implemented the dictionary structure as a parallel tree, where the code inside any View saw only the dictionary composed of its parents up to the root. i.e. the system is scoped. Given our system in production could have hundreds of thousands of words, this turned out to be a very efficient system. I also added in local variables and words, which allowed for little "bubble universes" of code invisible to child dictionaries. No time for etails right now (I have to leave for work) but I'd be happy to share when I have time iff there is any flame-free interest. It's an Existence Proof that the dictionary does _not_ have to follow precisely those rules and still be a functioning system with high utility, without sacrificing what makes FORTH so great. Genesis was I noticedmost of the definitions closer to the tail of the linked list were noise as far as any current definition goes. So I exploited locality and traditional scoping paradigms.

 David

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

#33960

On Sun, 12 Oct 2014 05:46:05 -0400, <mfanyikazi@gmail.com> wrote:

> [...]
> ummmm come to think of it , this would be a kick-ass way to develop a  
> highly domain independent AI engine ...
> [...]

An AI engine?  Hey, Mentifex is that you? ...


Rod Pemberton

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

#33999

On Saturday, October 11, 2014 11:06:42 AM UTC-7, Elizabeth D. Rather wrote:
> There have been many approaches to dictionary linking. Common strategies 
> include multiple linked lists, with a hash algorithm applied to the name 
> to select the list. Wordlists can be implemented simply by adding an 
> offset to the hash. In the 90's, FORTH, Inc. did some research and 
> determined that 16 lists was optimum (32 did not yield a measurable 
> advantage).

In SwiftForth-v2 I read the source-code for SwiftForth's implementation of a hash-table for the dictionary. Humorously, there is a comment in there that says the hash-table would be more efficient if the size were a prime number. True enough! Apparently however, whoever wrote the comment didn't have the authority to fix the problem --- so this Forth Inc. employee just left a helpful comment there, hoping that someday somebody with enough authority to fix bugs would see the comment and fix the bug. But nobody did --- so SwiftForth got sent out to the customers such as myself, and we get to see the comment and wonder at why the the bug never got fixed.

Quite a "strategy" they have at Forth Inc. --- all of the employees just brown-nose Elizabeth Rather, and they sweep the problems under the rug.

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

#33845

mfanyikazi@gmail.com wrote:
> I must admit that I am not the first person to ask this or even think
> about it but could someone tell me why there hasn't been any serious work
> done in trying to store the dictionary using an alternative structure
> other than linked lists? I know Chuck Moore has used a bit of hash tables
> in his flavours of the language but is that the end of it?

Well, hashes are used a lot, but on-disk storage seems to be quite stupid.  
The dictionary has to live in RAM anyways, since it's mostly code that 
executes.  From a slow disk?  Seems like a pretty stupid idea.

And as the only order in the dictionary that matters is the one of defining 
time (later means is found if there's a collission), sorting is not 
necessary.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

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

#33858

On Saturday, October 11, 2014 11:39:03 PM UTC+3, Bernd Paysan wrote:
> mfanyikazi@gmail.com wrote:
> 
> > I must admit that I am not the first person to ask this or even think
> 
> > about it but could someone tell me why there hasn't been any serious work
> 
> > done in trying to store the dictionary using an alternative structure
> 
> > other than linked lists? I know Chuck Moore has used a bit of hash tables
> 
> > in his flavours of the language but is that the end of it?
> 
> 
> 
> Well, hashes are used a lot, but on-disk storage seems to be quite stupid.  
> 
> The dictionary has to live in RAM anyways, since it's mostly code that 
> 
> executes.  From a slow disk?  Seems like a pretty stupid idea.

Efficient caching would sufficiently solve this drama! Caching of Code that is mostly used ... using a semantic network to aggregate other types of data ... it would be a really sweet system .... just think about it ... no more FORTH blocks , a fast indexing feature , AI utility ... etc 

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

#33864

On 10/11/14 11:50 PM, mfanyikazi@gmail.com wrote:
> On Saturday, October 11, 2014 11:39:03 PM UTC+3, Bernd Paysan wrote:
...
>> Well, hashes are used a lot, but on-disk storage seems to be quite stupid.
>> The dictionary has to live in RAM anyways, since it's mostly code that
>> executes.  From a slow disk?  Seems like a pretty stupid idea.
>
> Efficient caching would sufficiently solve this drama! Caching of Code that is mostly used ... using a semantic network to aggregate other types of data ... it would be a really sweet system .... just think about it ... no more FORTH blocks , a fast indexing feature , AI utility ... etc

Bernd makes a good point. Disk is generally used when there is 
insufficient memory. Given that one of Forth's most significant features 
is small memory footprint, going to disk or slower memory seems 
counter-productive. If there is no point in using disk at all, the added 
complexity of a caching algorithm isn't relevant.

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]

#33846

On Saturday, October 11, 2014 8:52:51 AM UTC-7, mfany...@gmail.com wrote:
> Ideally , the forth dictionary is a linked list of data , a nice conventional way to store data , but what if you need to store more than just a linked list of forth words , then stuff begins to get interesting , recently I have been working on several projects where I needed to apply some kick-ass ADT stuff to sort and index a large array and ummm I just though that some of the ideas that I was working with would properly organise forth and make it super optimal.
> 
> I must admit that I am not the first person to ask this or even think about it but could someone tell me why there hasn't been any serious work done in trying to store the dictionary using an alternative structure other than linked lists? I know Chuck Moore has used a bit of hash tables in his flavours of the language but is that the end of it?
> 
> Anyone else think that this is a good idea?

See my SYMTAB.4TH in the novice package.
http://www.forth.org/novice.html

What my symtab does, is move the more commonly used words (DUP etc.) toward the root, and the less commonly used words (BYE etc.) toward the leaves. Symtab has the same memory usage as a hash-table (assuming that the hash table is rebuilt when it gets more than half full). The advantage of symtab over a hash-table is that it doesn't "stop the world" to do a rebuild, but it just grows smoothly.

The disadvantage of symtab is the same as the disadvantage of a hash-table --- MARKER (or FORGET) is problematic to implement because there is no inherent chronological ordering to the definitions as there is in a linked-list. You can store an CHRONO number with each header that indicates their chronological order, but doing so uses up a lot of memory. All in all, ye olde linked-list is the most efficient memory-wise. On a processor that does data-caching, memory-efficiency pretty much translates into speed-efficiency, so a linked list isn't all that bad of a solution. I do think my symtab is better than a hash-table though, and both are better than a linked-list in terms of look-up speed with a large dictionary despite using more memory.

As an historical note, I came up with symtab for ANS-Forth in 2009 (it was ported from an old IBM370 assembly-language program of mine). A faggot/troll named Passaniti repeatedly said that it "sucks," and Elizabeth Rather enthusiastically agreed, denouncing me as "homophobic" because I objected to this filthy language on C.L.F. --- she has never apologized for this, and I will never forgive her until she does --- may she burn in Hell!

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web