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

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

ciforth model

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

Contents

  ciforth model albert@spenarnc.xs4all.nl - 2026-04-16 15:38 +0200
    Re: ciforth model dxf <dxforth@gmail.com> - 2026-04-17 11:44 +1000
      Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-17 07:29 +0000
        Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-17 12:10 +0200
          Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-18 10:26 +0000
            Re: ciforth model peter <peter.noreply@tin.it> - 2026-04-18 18:11 +0200
            Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-18 20:57 +0200
              Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-04-19 11:08 +0000
                Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-20 13:39 +0200
            Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-21 10:28 +0200
              Re: ciforth model minforth <minforth@gmx.net> - 2026-05-22 12:04 +0200
              Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-05-23 18:12 +0000
                Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-23 23:09 +0200
                Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-24 10:07 +0200
                  Re: ciforth model anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2026-05-25 13:34 +0000
                    Re: ciforth model peter <peter.noreply@tin.it> - 2026-05-27 10:42 +0200
        Re: ciforth model Hans Bezemer <the.beez.speaks@gmail.com> - 2026-04-21 19:39 +0200
        Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-22 22:48 +0200
          Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-24 10:38 -0700
            Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-25 11:54 +0200
              Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-25 13:22 -0700
                Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-26 14:05 +0200
        hashing for Forth dictionaries and address books (was Re: ciforth model) Kragen Javier Sitaker <kragen@canonical.org> - 2026-09-01 15:09 -0300
    Re: ciforth model Paul Rubin <no.email@nospam.invalid> - 2026-04-17 00:27 -0700
      Re: ciforth model albert@spenarnc.xs4all.nl - 2026-04-17 12:13 +0200

Page 2 of 2 — ← Prev page 1 [2]

#134973

albert@spenarnc.xs4all.nl writes:
> If you have a conflict, you rename the new offending definition,
> as you do now. 

How do you know when there is a conflict?  We're talking about a hash
collision, right?  Are we supposed to guarantee that the hash function
won't change between interpreter versions and that sort of thing?

"As you do now": well, no; I've never used a Forth that faced this
issue.  All the ones I've used have stored the entire name instead of
hashing.  I thought (or at least hoped) that the different lossy
compression schemes from the early days were historical artifacts due to
the very small machines of the era.  By the time of the Commodore 64,
those tricks were not needed.

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

#134985

In article <87bjf64wpe.fsf@nightsong.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>albert@spenarnc.xs4all.nl writes:
>> If you have a conflict, you rename the new offending definition,
>> as you do now.
>
>How do you know when there is a conflict?  We're talking about a hash
>collision, right?  Are we supposed to guarantee that the hash function
>won't change between interpreter versions and that sort of thing?
You know there is a conflict because the message:
    : aapx1 ; ISN'T UNIQUE  \ because there was aapy1
You donot want a hash conflict, as the hash replaces the name.

>
>"As you do now": well, no; I've never used a Forth that faced this
Yes you do encounter name collisions. See below.
>issue.  All the ones I've used have stored the entire name instead of
>hashing.  I thought (or at least hoped) that the different lossy
>compression schemes from the early days were historical artifacts due to
>the very small machines of the era.  By the time of the Commodore 64,
>those tricks were not needed.

You defined a constant SIZE, and then discovered that
the name was used in another part of the program. You then
redefine it with THINGO-SIZE or some such.
This doesn't change a bit if you use 3+last names. Collusion are
more probable, but the first FIG-Forth were usable.

If you have a SIZE and then you define size, you have a conflict
caused by case-insensitivity. You redefine the second size.
    : SIZE ; ISN'T UNIQUE  \ because there was size

How is this different?

Groetjes Albert
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

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

#135509 — hashing for Forth dictionaries and address books (was Re: ciforth model)

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
> Looking at the traditional length+3 chars and
> albert@spenarnc.xs4all.nl's 3 first and last, at least one pair of
> words in Forth-94 conflicts
> (...)
>
> Another option would be to store a hash value that is computed using
> all characters in the name.  If a good hash function is used, (...)
> The disadvantage of this approach is that WORDS or SEE cannot even
> show the little about the name that Chuck Moore's approaches or
> albert@spenarnc.xs4all.nl's approach shows.

I think I have some relevant, though highly eccentric, experience here.
Bear with me.

For a number of years, I used a hash table for a address book
handwritten with pen on paper.  This may sound impossible, so I'll
include some explanation here that isn't relevant to the Forth
dictionary use case.  I used linked-list chaining between entries
appended to a chronologically ordered numbered array:

    105. 153 Angela Lark  +54 11 4844 3938  Tronador 371, Buenos Aires
    106.     Erik Stauffer  +1 415 310 0531  737 Allston, Berkeley CA
    107. ...

The pen-on-paper medium has the WORM characteristic: you cannot really
erase ink from the paper, so I represented the linked-list pointers as
next-entry numbers, terminating the list with an empty space.  This
makes it possible to append to the list without erasing anything.

The heads of the chains (the number of the first entry in a chain) were
held in a fixed-size table addressed by the hash value of the address
book entry.

Hash function choice was constrained by what I could easily evaluate in
my head.  After evaluating a few different hash functions, I settled on
the “flavors” of the first and third letters of the person’s given name,
where the “flavor” of a letter is its ordinal position in the alphabet,
divided by 2, rounded up.  So “a” and “b” are flavor 1, “c” and “d” are
flavor 2, etc.  (I forget what I did for one- and two-letter names.)

This gave a 13×13 hash table that fit easily on one page of the
notebook, beginning more or less as follows:

        ab cd ef gh ...
    ab      7
    cd  12   
    ef         5
    gh 105
     ⋮

So, for example, to look up “Angela”, you would start at entry 105
(from the “A” and “g”), and if that wasn’t the right Angela, but there
was a next-pointer of 153, you would check entry 153.

With 169 hash chains and under 200 people in my address book, lookup
seemed a little faster than with an alphabetized list, but the real
benefit was that insertion of new entries was possible without leaving a
great deal of blank space.

The first and third letter worked better than the first two letters
because they were less correlated.

If you wanted to maximize the human-interpretable information of the
32-bit hash value of a Forth identifier, maybe the solution is to
transcode the name lossily into 5-bit Baudot-Murray code and take, like
old Fortran linkers, the first six characters of the name.  This gives
you Forth’s traditional case-smashing behavior; it costs you an extra
FIGS shift when you use punctuation or digits, and there are some ASCII
punctuation characters you’d have to map to something else on input,
such as `?` or `/`.  Maybe map the specially important characters `<`
and `>` to `=(` and `=)`.

So, for example, `s>f` might be 00101 11011 11110 10010 11111 01101,
using up all 30 of the character bits.  But `words` is just 10011 11000
01010 01001 00101 and can be padded out with nulls.  A `words` or `see`
could render both of those without truncation, as too with any
purely-alphabetic word of up to 6 letters.

...but it might be worthwhile to skip characters at some point, or store
the last character instead of the sixth, in cases where truncation is
needed.

Kragen

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

#134927

albert@spenarnc.xs4all.nl writes:
> However we could squeeze for 16 bits, without logically affecting the model.

These days for such a constrained target, it's probably best to tether
from a bigger machine.

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

#134930

In article <87ecke59nq.fsf@nightsong.com>,
Paul Rubin  <no.email@nospam.invalid> wrote:
>albert@spenarnc.xs4all.nl writes:
>> However we could squeeze for 16 bits, without logically affecting the model.
>
>These days for such a constrained target, it's probably best to tether
>from a bigger machine.

What was the argument about? See my answer to Anton Ertl.

Groetjes Albert
-- 
The Chinese government is satisfied with its military superiority over USA.
The next 5 year plan has as primary goal to advance life expectancy
over 80 years, like Western Europe.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web