InstallValue is broken for (at least) Types

[markuspf]

Currently GAP handles forward declarations and installations of values for global variables as follows:

• A call to DeclareGlobalVariable registers a global variable name and installs a dummy value ToBeDefined for it
• A later call to InstallValue copies the new value over the dummy object using CLONE_OBJ

Now the following is possible:

gap> cache := [];
gap> makeval := function()
          local v;
          v := rec( canary := "hello" );
          Add(cache, v);
          return v;
end;;
gap> DeclareGlobalVariable("Cheese");
gap> InstallValue(Cheese, makeval());
gap> Cheese;
rec( canary := "hello" )
gap> cache;
[ rec( canary := "hello" ) ]
gap> Cheese.canary := "world";
"world"
gap> cache;
[ rec( canary := "hello" ) ]

This is roughly how the NEW_TYPE cache works, which means at the very least we must not install values for types this way.

I couldn't come up with a better solution for the DeclareGlobalVariable. InstallValue yet, and we might have to forbid InstallValue (or rather CLONE_OBJ) for all kinds of objects.

Maybe @stevelinton @fingolfin or @ChrisJefferson have a bright idea.

[ChrisJefferson]

We could try duplicating the logic of InstallFlushableValue, and make InstallValue do:

CLONE_OBJ(obj, DEEP_COPY_OBJ(value)), so at least the original value it not effected. Does that break anything?

[ChrisJefferson]

Stepping back a minute, what would we like InstallValue to do? Would we like it to be more like Cheese := makeval()?

[stevelinton]

What we want is, I think, impossible. We want to find every reference to the "ToBeDefined" placeholder anywhere in the workspace and replace it by a reference to the exact object we are trying to install as its value.

Since that's too hard, we change the object which is the ToBeDefined placeholder into a clone of the object we are trying to install. Mostly that's OK, but there is a problem when the identity of the value we are installing matters, which it does for a few things like types (because we maintain the invariant that equal types are identical.

[fingolfin]

So here is a (nasty) way how we could perhaps resolve this: We add a new TNUM T_PLACEHOLDER (better name TBD). When we DeclareGlobalVariable, then we create a new instance of that type, and use it as placeholder object (instead of "ToBeDefined"). In it, we store the name resp. gvar id of the declared global var.

Now we go on in one of several ways:

1. As soon as a gvar gets installed, we iterate over the whole workspaces (yay), searching for all places its T_PLACEHOLDER occurs, and substitute it with the newly installed value.
2. Or, instead, whenever we access such a placeholder object "anywhere", we check whether a value has been installed for the gvar. If that is the case, we immediately return the actual value. Moreover, if this was inside a plist, precord, etc. we substitute the placeholder with the real object, to avoid the overhead next time around.

Both approach are quite problematic and ugly. The first may be difficult to achieve in HPC-GAP (we can't really walk over all objects there, can we? And then there is a locking issue... we'd essentially have to "stop the world" for this). The second approach is problematic regarding the word "anywhere": we'd have to potentially change a lot of code, or else modify some very low level functions to make those checks, adding lots of overhead everywhere; and that just to support a rather obscure feature.

That leaves variant 3: My bet is that almost all code using DeclareGlobalVariable and InstallValue only does so to avoid syntax errors when using those globals in function bodies. At the point any of those functions actually are executed, there is always an installed value; since the coded function body encode the gvar number, and not a pointer to the installed value, they don't notice.

In other words, my guess here is that almost none of the placeholders escape, and thus the big problem we are trying to fix is almost a non-problem. Indeed, other than assigning the placeholder to another variable, there is precious little one can do with them, right? So, we could just make that a rule, and then enforce it, by changing GAP to forbid use of T_PLACEHOLDER object for basically anything; trying to assign or otherwise evaluate such an object would trigger an error. Indeed, we could implement that right away, then start GAP to see if and where that error is triggered. If I am right, then it won't be, or only for variable assignment. If it is only for assignment to global variables, then we could fix the problem by adding a check to InstallValue: It would simply iterate over all globals, and check if any references the same placeholder, and if so, update that global variable, too. That is much less problematic than iterating over the whole workspace.

And even if we determine that I am wrong, then at least we'll know a concrete example where I am wrong, and can continue discussing based on that. (I still hope this would be rare, and could be removed by refactoring the code).

[ChrisJefferson]

I think tidying this up would be nice.

Another possibility would be to just leave the variable unbound, and come up with some way of stopping the error message (although, I can't immediately think of a better way of doing that than something similar to what you describe)

[ChrisJefferson]

Although, that would require InstallValue gaining some magic to cope with the name not being defined.

[fingolfin]

@ChrisJefferson yeah, that sounds like a nice approach, except that we'd have to turn InstallValue into a compiler special, like IsBound and Unbind, which is not so nice ... :/

Anyway: Right now, a declared but not installed variable still ...

• ... is bound, as in IsBound(x) returns true,
• ... can be assigned to other variables
• ... is read-only, i.e. the name is blocked otherwise.
  That is:

gap> DeclareGlobalVariable("declaredVar");
gap> declaredVar;
<< declaredVar to be defined>>
gap> IsBound(declaredVar);
true
gap> x:=declaredVar;
<< foobar to be defined>>
gap> declaredVar:=1;
Error, Variable: 'declaredVar' is read only
not in any function at *stdin*:4
you can 'return;' after making it writable
brk>

When we change this, we need to be a bit careful about not breaking things silently (it is OK to break things, it should just be guaranteed that this results in an immediate error, and not some code which silently changes its behavior).

So, one approach would be to do what I suggested, and declare a special "placeholder" type. That sounds like quite some work and deeper changes to the kernel

The approach suggested by @ChrisJefferson, if I understand it right, would be to, say, keep a list of global variables which are unbound but for which we suppress the "unbound variable" syntax warning. That still sounds like something that requires kernel changes, but much more localized (yay!). Indeed, we could do this: First, we immediately reserve the gvar id for that variable; then, we add it to a list / bitlist (T_BLIST) / OBJ_SET / whatever. Then, in the place that triggers the syntax warning, we ignore any gvar id in that list. Also, once a value gets installed, we can delete it from that list (however, that's not strictly necessary).

This approach should work as long as no code does the equivalent of x:=declaredVar; in my above example. And of course there is the problem that we'd have to somehow stop GAP from evaluating the first argument to InstallValue... urhm

[olexandr-konovalov]

I suggest to re-assign this to a future milestone (4.9.1 or even 4.10.0).

[fingolfin]

Re-assigned to 4.10.0. This would be a major change, so certainly nothing for a minor bugfix release

[fingolfin]

Also: My idea for resolving this unfortunately was way too naive and does not work. So this still needs more work.

I thought some more about the idea @ChrisJefferson sketched (i.e. simply not binding the variable upon declaration; instead adding it to a list which then is used to suppress the warnings; and finally a gross but probably simple hack to the interpreter to accept such declared variables as first argument to InstallValue and InstallFlushableValue (but nothing else). (Note that this gross hack would not be necessary if InstallValue et all accepted a string as first argument; we may want to allow that as part of a long-time migration strategy, perhaps even for GAP 4.9, and then try to get all package authors to use that new format).

However, even with that, I worry about problems with flushable variables, as there we cannot avoid redefining a previously bound variable...

[fingolfin]

Actually, the way I read the documentation for InstallValue and InstallFlushableValue resp. InstallFlushableValueFromFunction, nothing in it indicates that CLONE_OBJ is used. It says this:

InstallValue assigns the value value to the global variable gvar. InstallFlushableValue does the same but additionally provides that each call of FlushCaches (79.18-18) will assign a structural copy of value to gvar.
InstallFlushableValueFromFunction instead assigns the result of func to gvar (func is re-evaluated for each invocation of FlushCaches (79.18-18)

InstallValue does not work if value is an "immediate object", i.e., an internally represented small integer or finite field element. It also fails for booleans. Furthermore, InstallFlushableValue works only if value is a list or a
record. (Note that InstallFlushableValue makes sense only for mutable global variables.)

i.e., I would not be able to deduce from this that the following example would behave the way it does:

gap> DeclareGlobalVariable("foobar");
gap> x := foobar;
<< foobar to be defined>>
gap> IsIdenticalObj(x, foobar);
true
gap> InstallValue(foobar, rec());
gap> IsIdenticalObj(x, foobar);
true  # <--- and here a miracle happens...
gap> x;
rec(  )

This suggests a very simple solution to this mess:

1. Change InstallValue and its siblings to also accept the name of the global var as first argument (this requires some trickery to distinguish inside InstallValue to distinguish between InstallValue("foobar", ...) on the one hand, and InstallValue(foobar, ...) with foobar = "someString" on the other hand; e.g. by checking that the string really is the name of a declared global variable etc.); much easier would be to simply provide a new function InstallNamedValue or InstallValueByName or so. In either case, the implementation would simply call MakeReadWriteGlobal + BindGlobal + MakeReadOnlyGlobal.

2. Change all library code and packages to use the new calling convention resp. new function.

3. Once everything is deprecated, remove the old implementation using CLONE_OBJ.

Of course if we are more ambitious, we could also do something completely different, and introduce a syntax extension which allows changing the usual call by sharing semantics used by GAP (following the notation on Wikipedia) to "call by reference". That's something I know how to implement (essentially, it needs a notion of lvalues, which is something I thought about long and hard for my feature request #40, which I am still interested in). To illustrate with an example, with pseudo syntax inspired from C++:

gap> f := function(&a, b)  a:=b; end;; # a is passed by-reference
gap> g := function(a, b)  a:=b; end;; # is passed by-sharing, as usual
gap> x:=4;;
gap> g(x, 5);  # g has no side effect, nothing happens
gap> x;  # x is unchanged
4
gap> f(x, 5); # x is passed by-reference to f ...
gap> x; # ... hence it is modified by the assignment in f
5

With this, InstallValue can be trivial rewritten to work without CLONE_OBJ.

Anyway, this is a much more difficult and ambitious solution, and certainly not without controversy (e.g. it is not easily visible for a given function call whether any of the arguments to the function are passed by-sharing or by-reference), so despite personally liking the idea of introducing call-by-reference support, I think in this case the much simple approach I described first is preferable.

[fingolfin]

Removing the milestone. Nobody is working on this right now; it only makes sense to set a milestone if we have a clear plan how to solve a given issue, resp. volunteers who promise to take care of it in a given time frame.

[fingolfin]

My current plan is to eliminate as many uses of InstallValue as possible from the GAP library and packages. Ideally all, but more realistically just "most". Then hopefully the remaining ones will install only "plain" values like lists, strings or records. We can then change InstallValue to only allow install such plain values, and only if the existing value is of the same "plain" type. Dealing with those then can always be done safely.