Surjection, automated generation

helmwo at web.de

Re: Surjection, automated generation

Julian V. Noble

Re: Surjection, automated generation

Albert van der Horst

From:	helmwo at web.de
Subject:	Surjection, automated generation
Date:	19 Jan 2005 07:12:09 -0800

Hi at all!

I currently want to write a program that generates FORTH source for a
specific problem:

1) I have a possible input space I[] of K unique elements. The input
space is fixed for the problems I want to solve.
2) The elements are encoded as words with an alphabete A%
3) A word from I[] should be transformed to a numerical representation
N, where N is unique for each of the K possible words and the function
that transformes such a word to an N should be easy to implement in
FORTH.
4) N should be in the best case inside the range 1..K
5) It should be fast.

4) and 5) are the problem. I think this is something like a "perfect
hash generator" - there exists gperf. I wonder now if something like
this exists for FORTH?

Bis dann,
Helmar
helmwo@web.de

From:	Julian V. Noble
Subject:	Re: Surjection, automated generation
Date:	Fri, 21 Jan 2005 13:40:23 -0500

helmwo@web.de wrote:
>
> Hi at all!
>
> I currently want to write a program that generates FORTH source for a
> specific problem:
>
> 1) I have a possible input space I[] of K unique elements. The input
> space is fixed for the problems I want to solve.
> 2) The elements are encoded as words with an alphabete A%
> 3) A word from I[] should be transformed to a numerical representation
> N, where N is unique for each of the K possible words and the function
> that transformes such a word to an N should be easy to implement in
> FORTH.
> 4) N should be in the best case inside the range 1..K
> 5) It should be fast.
>
> 4) and 5) are the problem. I think this is something like a "perfect
> hash generator" - there exists gperf. I wonder now if something like
> this exists for FORTH?
>
> Bis dann,
> Helmar
> helmwo@web.de

Have you consulted Knuth's book? Soundex might help. You might also try
one of the hashing schemes with chaining (rather than linking) for collision
avoidance. They can be very fast. The one I have used requires two primes > K
and differing by 2, that is, p1 > K, p2 = p1 + 2. It is a little wasteful
of space, but these days space is far cheaper than time. ;-)

I think I found this algorithm in Kruse's book "Data Structures and Program
Design" (but it might have been an article in BYTE or PC TECH MAGAZINE).
I employed it in my one-and-only commercial piece of software around 1986/7
so that's when the article would have appeared (if it is NOT in Kruse).
The program is written in QuickBasic, but (as usual) I didn't put in enough
comments so I am finding it a bit hard to read, despite having named the
subroutines and functions telegraphically and having kept them short.
(Forth was having a major influence on my programming style even then!)

If you want the Basic program I can probably dig it out, but the algorithm
is fairly standard so it might be easier to look it up in a text.

--
Julian V. Noble
Professor Emeritus of Physics
jvn@lessspamformother.virginia.edu
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"As democracy is perfected, the office of president represents, more and
more closely, the inner soul of the people. On some great and glorious
day the plain folks of the land will reach their heart's desire at last
and the White House will be adorned by a downright moron."

--- H. L. Mencken (1880 - 1956)

From:	Albert van der Horst
Subject:	Re: Surjection, automated generation
Date:	22 Jan 2005 14:39:03 GMT

In article <41F14C97.7596469B@virginia.edu>,
Julian V. Noble wrote:
>
>Have you consulted Knuth's book? Soundex might help. You might also try
>one of the hashing schemes with chaining (rather than linking) for collision

Do you mean where you have a large table, maybe 1/5 filled at most?
If you have a collision (1 in 5^2 at most) you take the next
empty slot?
I was thinking to employ that for vocabulary lookup in Forth,
because my reverse engineering assembler generates an awfull
lot of labels.
Has anyone used this for Forth dictionary lookup?
Are there any known disadvantage over having a linked list per bucket?

>avoidance. They can be very fast. The one I have used requires two primes > K
>and differing by 2, that is, p1 > K, p2 = p1 + 2. It is a little wasteful
>of space, but these days space is far cheaper than time. ;-)
>
>I think I found this algorithm in Kruse's book "Data Structures and Program
>Design" (but it might have been an article in BYTE or PC TECH MAGAZINE).

What I describe above, is in Knuth TOAP. If it is not the same,
it may be a viable alternative, and it is a source readily found.

>I employed it in my one-and-only commercial piece of software around 1986/7
>so that's when the article would have appeared (if it is NOT in Kruse).
>The program is written in QuickBasic, but (as usual) I didn't put in enough
>comments so I am finding it a bit hard to read, despite having named the
>subroutines and functions telegraphically and having kept them short.
>(Forth was having a major influence on my programming style even then!)
>
>If you want the Basic program I can probably dig it out, but the algorithm
>is fairly standard so it might be easier to look it up in a text.

Why not put it up your website? At least it is an annoyance for the
companies that try to patent everything.

If someone has the following brilliant code an his/her website
( addr1 addr2 -- flag)
\ Return a flag whether addr1 and addr2 point not to the same variable
: IsNot = 0= ;

it could serve as "prior art" to dismiss a to-be Microsoft patent.

(The reason they are using IsNot and not just plain Is, is to thwart
claims of prior art. A sane person would define Is, and invert where
appropriate. Yes. It is *that* bad.)
Of course nobody has, so the patent may be just granted.

>--
>Julian V. Noble

Groetjes Albert

--
--
Albert van der Horst,Oranjestr 8,3511 RA UTRECHT,THE NETHERLANDS
One man-hour to invent,
One man-week to implement,
One lawyer-year to patent.