Re: Soliciting criticism of memoize function

[Roberto Ierusalimschy <roberto@...>]

>  > Basically weak tables are always a bit tricky and semi-weak tables are  
>  > doubly so. Essentially weakness means that some of the keys and values  
>  > won't be marked via the table and hence may get collected, but that  
>  > word "some" is important to understand.
> 
> Yes.  I don't understand.  I have never understood.  It's one place
> where I think both the reference manual and PIL fall down, because the
> explanation is with respect to a model that's not written down anywhere.
> I have long wanted a formal semantics of some fragment of Lua, and the
> semantics of garbage collection is right up there with things that
> I would like to see formalized.

We may define a predicate SA ("strongly accessible") inductively:

- the main thread is SA;

- all values refered by local variables of a SA thread are SA;

- the environment of a SA thread is SA;

- bla-bla-bla (for closures, registry, etc.)

- if a table is SA and it does not have weak keys, then all its keys
are SA;

- if a table is SA and it does not have weak values, then all its values
are SA;

- only values proven SA by the previous rules are SA.

Then GC goes like this:

- any value that is not SA is eventually collected;

- once a value is collected, any entry in any table with that value
as a key or as a value is removed from the table.

(If you want finalizers the model is more complex, but not too much.)

-- Roberto