Re: [Lightning] automata, minimal perfect hash functions, and gnu lightning

[Ludovic Courtès]

Hi,

(and best wishes!)

"Johnicholas Hines" <address@hidden> writes:

> A finite automaton could read a string and return a bin. Building such
> a finite automaton would be a deterministic way to make minimal
> perfect hash functions. If you can build the automaton fast and also
> run the automaton on input fast, you might be able to use minimal
> perfect hash functions in more dynamic situations than just reserved
> words for programming languages.

Funny, I've had such a project in mind for some time!  ;-)

I think lightning would be appropriate, providing a more dynamic
alternative to gperf, as you mentioned.  It could be very valuable to
run-time systems of dynamic programming languages like Scheme, Python,
etc., which currently use hash tables to store symbols of global
variables.  Those hash tables are typically only populated at
initialization time; as they are populated, they are enlarged in order
to optimize lookup time.  Those systems could use heuristics to
determine when to switch from a regular hash table to a
lightning-compiled automaton.

I'm sure there are other applications that could benefit from this.  Let
us know about the evolution of your project!

Thanks,
Ludovic.