Thoughts and tempering expectations on redefining structs

Internals & Design
1

TLDR: musings on how redefining structs cannot be as convenient as we’d like, nothing really important so feel free to ignore this thread

Overoptimistic expectations

We enjoy the interactivity and incremental code modifications that a dynamic language offers, and Julia’s multimethods achieve a particular kind of intermodule composability, if we sensibly avoid type piracy. But while we can add or replace methods in a function and invalidate its callers to adjust, we cannot change anything within a struct definition. There have been other discussions about this “missing feature”, and they generally expect an analog to method invalidation: change the struct, and the callers adjust accordingly. After all, it’s a dynamic language, you can redefine classes in Python, so why not structs in Julia?

It’s much more complicated than method invalidation

If we expect an analog to method invalidation, then we should compare structs and functions more carefully. First we should recognize that they’re not distinct concepts. A function has a singleton subtype of Function, a const name, and no fields. Like a function, a type constructor is a multimethod and also causes invalidations of callers. However, unlike independent methods, a struct’s parameters, supertype, fields, and inner constructors are rooted in the type and are usable by any method. It’s not possible to make multiple versions of these like multimethods, so a struct block necessarily attempts to reassign the const name of the type. Currently, it’s not possible to replace a struct like that, but it’s also not possible (or even desired) to replace a function, either. When we write function blocks for an existing function, we do not reassign that const name, we just add or replace one of multiple methods.

But let’s assume that we’re trying to make replacement of structs possible. You can invalidate a caller foo() = MyType(1, "a"), and that does happen already. However, types don’t just show up in calls. A big one is argument annotations, like bar(::MyType) = 0. If the annotated types would be replaced, these methods would be essentially replaced, and the method dispatch tree would be modified. Commenters feel free to correct me, but this could be tracked with some version of backedges, though I expect much more overhead as I believe type annotations outnumber function calls. Bear in mind, automatic inheritance adjustment does not occur in Python: the obsoleted class remains in superclass lists, so subclasses must be reevaluated (though it’s easy to find them).

The thornier issue is existing instances in the global scope, whether of the obsoleted type or from a function call that relied on the obsoleted type on some level. Tracking and reevaluating these can become very expensive (const ohgodwhy = takes5minutes(args...)). Unlike recompilation of invalidated methods, reevaluation of expressions cannot be lazy and incremental much because different orders of evaluations can result in wildly different behavior.

Reevaluation causes artifacts, replacing instances is questionable

The straightforward way to replace a struct is to restart the REPL and evaluate everything from scratch, which can take an undesirably long time to load necessary dependencies and recompile methods. However, redefinitions alone cannot replicate the behavior of a full restart, and this is true even for method redefinitions e.g. baz() = 1; a = baz(); baz() = 2; a # still 1. That raises the possibility of using automatic reevaluation to have the active code fully adapt; baz() = 2 triggers an implicit a = baz(). Problem is if we replaced the call signature, then past code would throw MethodErrors if reevaluated automatically after redefinition. In most cases, there won’t be a sensible way to 1-to-1 replace a call signature in source code, that must be done manually, and only after that is reevaluation possibly useful. This can get much more complicated than global instances, with cross-module influences and conditional evaluation of methods.

Even assuming the call signature is not changed, one suggestion (that I also have made) has been to only reevaluate in the module the struct belongs to, the idea being it’s isolated, but modules are rarely fully isolated from one another. Other modules will also need to be reevaluated to adjust behavior, and it’s not as “simple” as tracking functions extended on the type and modules importing such functions or the type. For an example, let’s say my working module uses custom units types in a method to compute the speed of light const c = computec(), which gets exported very liberally. Then I change the types to different units, which the value of c adjusts to. However, none of the modules that imported c imported my types, so they happily use the obsolete value. You might then suggest to track all modules that import anything from my working module, but that doesn’t cover modules that import different values, like a light-year, computed from c outside my working module. If we play it safe and reevaluate in order every module our working module can reach via imports, it could easily save very little time. If we extended any function in Base on the redefined type, which is imported in every module except baremodules, we might as well restart the REPL to save on tracking overhead.

Let’s assume that it’s just unfeasible to find and evaluate a subset of past code that both replicates a restart and saves a lot of time, and we choose the latter: just replace the type, its global instances, and the live methods using them; every other necessary change, like methods that call the type constructor, must be done manually. Then we have to also decide if that retroactivity is the sort of dynamic feature we want. Take method redefinitions again baz() = 1; a = baz(); baz() = 2; b = baz(); (a, b); we expect to see that change in (1,2). (FYI avoid method redefinitions in source code, those are unnecessary and break incremental compilation.)

Strategies and package highlights

This doesn’t mean we need to restart the REPL every time. Replacing a struct only becomes a big reevaluation problem if you had built many methods and modules on top of it.

  1. When you are still experimenting, you can make throwaway structs and test a few interface methods on them, and try to reach a decision on the structure and supertyping before extending the functionality.
  2. If you carefully make a supertype interface and make many methods rely on that supertype instead, a new subtype struct and its interface methods can smoothly integrate into the supertype’s methods (this doesn’t handle global instances though).
  3. If you haven’t exported the type or extended other modules’ functions with it, you can replace the whole module without affecting other modules at all. Julia v1.9 makes this smoother by letting you change the module you interact with in the REPL. Packages don’t have to be reloaded, just reimported. Other modules’ functions extended with obsolete types should not get in the way if you never use the obsolete type again, it’s just that those obsolete methods will show up in reflection, which can be confusing.

People only desired redefinable structs for experimenting, so it’s reasonable to keep the experiments small and isolated so the widespread changes are feasible without restarting everything. There are a couple packages for this context; bear in mind that neither package does retroactive reevaluation.

  1. RedefStructs.jl is not kept up to date with Julia, but the macro @redef renames a struct block to make a hidden struct assigned to a non-const global name you provided. It’s a bit more convenient version of throwaway structs.

  2. ProtoStructs.jl is a bit more updated, and the macro @proto changes a struct block to a different struct parameterized by and containing the fields as a NamedTuple or Dict{Symbol,Any}, depending on if the struct was immutable or mutable. Another @proto block just changes the active parameter of the type constructor. Unlike RedefStructs.jl, this strategy does not accommodate supertyping, and it appears the type parameters must be entirely inferable from field values.

4 Likes
2

Great writeup, thank you!

If you happen to have some examples for this, I would be glad if you put those in an issue on the repository :slight_smile:

2 Likes
3

AFAIK there is nothing that conceptually prevents redefining structs, it’s just that the issue involves reworking the internals of Julia that only a few people know how to do, and they currently do not have the bandwidth for this. The latest proposal is

While not being able to redefine structs is irksome, it does not prevent Julia from being usable, so the developers can take their time addressing this in a way that meshes well with other features.

1 Like
4

I think redefining structs is in a different category, most likely in the bucket “we don’t want to go there.” The compiler is allowed to make all sorts of decisions during codegen conditioned on the assumption that types are const, and there’s no equivalent of backedges documenting consequences of those decisions. Unless those get added, we can’t accurately perform invalidations if types change their definitions. And adding all those backedges would likely bloat the system enormously. That’s a pretty huge cost to pay for a little extra developer convenience.

Given that recent versions of Julia allow you to replace Main with a new module, there’s a decent workaround that could stand a bit more usage (and perhaps tools to make it easier). But I’ve not played with that much myself.

13 Likes
5

I am aware that this was the approach in #22721, and it turned out to be expensive, but does this apply to the more recent world-age based approach linked above?

Of course this depends on the cost of the solution, but arguably the convenience is not trivial. We have learned to work around this, but solving this would make exploratory coding much more convenient.

2 Likes
6

So the issue with this is that there isnt a concept of world age for objects/types, what is the behaviour if I have an array of the struct that was redefined, should it be invalid to use or should it behave as the old type, are you allowed to make a copy etc.

3 Likes
7

I am aware that this was the approach in #22721 , and it turned out to be expensive, but does this apply to the more recent world-age based approach linked above?

Hmm, I’d forgotten about that PR (I should have clicked, sorry). The storage requirements are more minimal, although not zero because the number of forward edges might be substantial in some code. The walk of all compiled code would take a while, but it might be less time than, say, building a large package.

what is the behaviour if I have an array of the struct that was redefined, should it be invalid to use or should it behave as the old type, are you allowed to make a copy etc.

Handling existing data is a thorny problem. There’s no plausible way to automatically migrate over to the new type. You might still have old compiled code apply to old data, and it would be easy to inadvertently forget to recreate something and get misleading results. I’m not saying it’s not solvable, but replacing Main conveniently clears your data as well as your bindings.

3 Likes
8

I could live with the following heuristic:

  1. If field names match, try to convert their contents,
  2. Otherwise wrap fields in a type dedicated for this purpuse, in a NamedTuple, with some metadata.
1 Like
9

I meant a couple things. @proto struct X <: Number end won’t incorporate the supertype as intended; looking at the @macroexpand, you get struct X{NT <: NamedTuple} and a (X() where Number) method that prints a warning. It is pretty doable to bake the supertype into the struct, but the other problem is a second @proto struct X <: Real end cannot possibly change the supertype, which makes incorporating a supertype a liability. This is a “downside” but I think it’s worth it to have a clearly named parametric type, compared to RedefStructs’ non-const aliasing of gensymed hidden structs, and it is fine for early experimental stages of development.

10

I’m still not well-versed on world age, so a lot of #40399 goes over my head. However, it seems like it’s about adjusting methods specifically, but I could be very wrong.

That’s good, I should’ve mentioned that in the essay where I talked about replacing modules. Still, good to do this before that type gets exported to other modules or used to extend other modules’ functions.

I don’t see how this is related to what tim.holy was saying. Maybe I’m misinterpreting the conversation, I thought this was about global variables. For example, what to do with ant::Insect = Insect(3.4, 1.2); ant2::Insect = foo(ant); getants(::Insect) = (ant, ant2); @replace struct Insect mass::Float64 end.

I can imagine getants’ type annotation changing automatically, but as I said in the essay, automatically changing existing data like ant::Insect isn’t dynamic, it’s retroactive. It’s also ambiguous in that example which input/field is intended to be kept, so an automatic change isn’t possible. Another way an automatic change isn’t possible is if the type constructors (Insect) or other methods (foo) haven’t been adapted to the struct definition yet. In the case where you planned to change some methods along with the struct, would you even want automatic changes to kick in right after the struct redefinition? These issues aren’t particular to Julia, redefining classes in Python can’t do retroactive changes for the same reasons.

Even if we mark ant::Insect as temporarily undefined and ant2::Insect as its dependent (order matters!), things get messy when we try to run and recompile getants(::Insect):

  1. If we go full retroactive, the type annotation adjusts to the new type but the ant::Insect is undefined. We run getants(Insect(1.1)) to recompile it for the new type, but it errors because we don’t have an ant value.

  2. If we accept that all global instances must be manually replaced and thus keep their old type, then running getants(Insect(1.1)) would run and compile to return the old type if we forgot to replace ant::Insect. It’s even worse because the types have the same name so best case scenario they are printed with their world ages and we’re squinting at numbers.

This example would be even worse if it had been const ant instead, which is expected to never change so the data gets incorporated into the compiled code, instead of a reference to the global scope. Or if I had involved side effects and program state in foo.

11

Yes, this is a valid point.

Perhaps the API to redefine a struct should also involve a method for converting existing structures. Otherwise, it is indeed a nightmare: even if heuristics are allowed to simple cases (eg changing the field types to something convert can deal with), even trivial modifications could leave global variables in a state that could lead to subtle errors with a lot of time wasted.

One approach I can imagine is “version” old types with eg the world age, or a counter that maps to that. So when

struct Foo # 1
   value::Int
end

is redefined to

struct Foo # 2
    x::Float64
end

then previous instances of Foo (1) remain available, along with methods that dispatch on them etc, so that each type is tied to a world age. The user, of course, would not care about this in most cases, as the symbol would automatically map to the latest. But other types could be around as long as they are needed.

(No doubt this proposal has a lot of corner cases I haven’t thought of)

3 Likes
12

I’m not exactly sure whether you mean to retroactively replace existing instances or to make copies in a new world age. I lean toward the latter because it could accommodate a dynamic language. A simple example would be redefining the struct in a loop and pushing an instance to a vector per iteration; in a dynamic language, the vector’s elements would have different types (this is doable in Python).

Making copies and isolating their behavior from the obsolete world is difficult though. Unlike invalidated methods, types take up spots in the type hierarchy and affect method dispatch. If we also try to consider redefining abstract types, this gets even more complicated. A true isolation would have to duplicate the type tree and all the functions that are affected by the changes. Given 1-to-1 conversions of existing global instances from the obsolete type to the new type and the type constructor calls in functions, this could result in a program copy that doesn’t suffer from artifacts of reevaluation order. I just don’t think 1-to-1 conversions between different structs could exist or be desired in practice, so manually changing the type constructor calls or writing out new methods for an additional type in the source code would probably be far less buggy. I mean, we don’t have 1-to-1 conversions for when we change a method’s intended signature, and that’s a far simpler case.

13

I’m clearly not qualified to judge the complexity of the changes needed to support it. But just from a developer perspective, I don’t think I can agree in a general sense.

I think being unable to revise struct is fundamentally breaking from the almost-perfect interactive/dynamic story for Julia development. I would almost go as far as to say it’s qualitatively the same pain you encounter in C++/C, where you have to recompile every time (they have partial recompile too!)

I’m not saying this should be a high priority, but just that as long as we can’t do it, we’re definitively in a different tier than Lisp/Python in terms of actual dynamic/interactive developer experience.

5 Likes
14

I can’t speak for Lisp, but someone should because change-class and update-instance-for-redefined-class look interesting, like a way to adjust instances without reevaluating past code and running into the issues of evaluation order and side effects. I also wonder about how instances are implemented to allow this, and whether there is an automatic adjustment of multimethod argument annotations or call sites.

I can say you’re wrong about Python. A key detail is that Python doesn’t have const variables, so that’s why it’s possible to “redefine” a class. However, “redefine” there does not mean backedges or forward edges are involved. It’s just creating a new class and assigning it to the existing name. Every other class that subtyped the obsolete class will not change, every existing instance will not change its type. Instantiation calls do adapt to the new class because the name cannot be const, but in practice, the call sites need to be edited because the call signature almost always changes.

We can do the same in Julia with non-const global variables, and indeed RedefStructs.jl did that.

julia> struct Foo1 end
julia> Foo::DataType = Foo1;
julia> bar() = Foo();
julia> bar()
Foo1()
julia> struct Foo2 end
julia> Foo = Foo2;
julia> bar()
Foo2()

Conceivably, a macro could change the way the type is printed and represented so that we could write blocks that act like a non-const struct. If someone does this, I only request that the printing for obsolete structs be changed to have numbering like the above or something because multiple distinct classes sharing the same name in Python is a nightmare, so nobody actually tries to redefine classes, they usually just add or change methods. Changing __init__ does make a class have a malleable structure, but it’s not really done because as I mentioned before, you need to edit all the call sites. I also don’t think we should have struct instances emulate dictionary-backed class instances, the inefficiency would be horrible.

15

That’s pretty much what I proposed above.

IMO const in Julia should be relaxed from “you promise that this will not change, otherwise dire consquences follow” to “if this changes, a bunch of stuff needs to be recompiled”. Technically this is already possible with

_my_constant() = 42

instead of

const MY_CONSTANT = 42

it just has different access syntax.

1 Like
16

_my_constant is an implicitly const name, but that’s really just splitting hairs because methods can be redefined. The real issue is that those are not actually equivalent; the method body is run every call. _my_constant() = [42] would not be equivalent to const MY_CONSTANT = [42]. _my_constant() = rand((4,2)) would not be equivalent to const MY_CONSTANT = rand((4,2)). Your case is only equivalent because every call returns the same immutable value.

17

First, there is nothing to “run” here, the function just returns a value.

Second, for this particular method, the compiler will just inline it. Eg

julia> _my_constant() = 42
_my_constant (generic function with 1 method)

julia> foo(x) = x + _my_constant()
foo (generic function with 1 method)

julia> @code_llvm foo(10)
;  @ REPL[81]:1 within `foo`
define i64 @julia_foo_8728(i64 signext %0) #0 {
top:
; ┌ @ int.jl:87 within `+`
   %1 = add i64 %0, 42
; └
  ret i64 %1
}

The semantics is not that different from constants. Except that backedges take care of redefinition.

The point is that consts might as well be modifiable (at a cost). It is a choice. structs are “constant” too, but that is something that could change without fundamental upheavals of the language semantics (and of course a lot of work on the part of developers).

18

Semantically, the function constructs and returns a value, 42. The compiler optimizes by making a deterministic immutable value at compile time and inlining it in other methods. It can’t do that for _my_constant() = [42] or _my_constant() = rand((4,2)).

19

You can do that with one level of indirection though, eg

_MY_CONSTANT1 = [42]
_my_constant() = _MY_CONSTANT1

and then each time you want to modify it, you just make a different constant.

Regretfully, Julia does not have anything equivalent to CL:LOAD-TIME-VALUE; that would get rid of the indirection.

20

Isn’t this just making the point that if you want a global variable that can change its instance, you can’t make it const?

1 Like