Struct inheritence and lenses

[LeifAndersen]

At the moment, lenses do not seem to compose well with structs that extend other structs. Consider:

#lang racket

(require lens)

(struct/lens foo (a) #:transparent)
(struct bar foo (b) #:transparent)
(define-struct-lenses bar)

(define x (bar 1 20))
(lens-set foo-a-lens x 42) ; (foo 42)

In this example, the resulting lens is a foo, specifically (foo 42), I would like it to still be a bar, in this case (bar 20 42).

I because define-struct-lenses does not try to walk a struct's inheritance chain, I cannot just use bar-a-lens.

Now, I know this is not always possible to do, such as if you don't have an impersonator that does not have access to the struct and if you also do not have access to the struct's fields itself. But if you have access to it, having it walk up the chain and make lenses for it would be very helpful.

[LeifAndersen]

It is also worth noting that it may be reasonable to require the user to explicitly pass it into define-struct-lenses, since you cannot guarantee that you have access to the relevant super class. Similar to how struct-copy works.

[LeifAndersen]

(Although the user would also have to manually enter the fields too, which could get cumbersome. You could only require it for the fields they want lenses for, but at that point they basically did just make their own lens, so hmmph...)

[AlexKnauth]

The correct point of control for most of this is in @lexi-lambda's struct-update package. There should be an issue for handling inheritance on that.

[AlexKnauth]

There is now an issue for this on that repository https://github.com/lexi-lambda/struct-update/issues/1

[lexi-lambda]

IMO, struct inheritance is not well supported in Racket, which makes doing stuff like this basically impossible in a way that satisfies the lens laws. I would recommend not using struct inheritance if you are using lenses. Hopefully we can get a better struct system in Racket 2.

[jackfirth]

Perhaps define-struct-lenses should throw an error when used on a struct that has a parent?

[lexi-lambda]

That wouldn’t even address the problem in general, since you could define a substruct of that struct, and it would exhibit the same slicing problem, so you’d have to put stronger contracts on the lenses themselves. I’m not actually sure what that contract would look like, though, since I don’t know how you could detect a struct but not its subtypes.

[jackfirth]

Right, but right now there's simply no mention of inheritance at all in the lens docs rather than any sort of indication that it should be avoided. Signaling the problems inheritance brings up in docs and syntax errors would be useful communication.

[LeifAndersen]

Ya, this makes me really think that the best option is to either require the user have the correct impersonator (which is super easy to do in struct/lens, but harder to do in define-struct-lenses), or have the user specify the super struct and its fields if they don't have the correct impersonator.

To make the API simpler to understand, it seems like the right thing to do here would just have struct/lens take care of it, and ave define-struct-lenses require you to specify them manually in its syntax.

Its not ideal, and it's also problematic because struct/lens is not really compressible, but it's the best I got at the moment. Thoughts?

[lexi-lambda]

Having a sufficiently powerful impersonator isn’t enough to have the right behavior here because it’s still impossible to dynamically determine the actual type of a struct and perform a non-slicing copy. Consider the following structs:

(struct a (foo))
(struct b a (bar))
(struct c a (baz))

Imagine you have a list of a?s, but of different subtypes:

(define as
  (list (a 1) (b 1 2) (c 1 2)))

Quite reasonably, you might want to use a lens to map over every struct in the list and increment its foo value by one, producing the following result:

(list (a 2) (b 2 2) (c 2 2))

However, this is impossible, unless you manually specify predicates and updaters for every possible type, then do a lookup to see which subtype it is for each element, turning an O(n) operation into an O(n * m) operation, where m is the number of subtypes in play. The boilerplate would be pretty inhibitive, too, imo.

I think noting that lenses don’t work well with struct subtyping in the documentation (and giving some examples about what can happen) is the best approach, unless I’m overlooking something major.

[LeifAndersen]

Yes, but what I was proposing was NOT to dynamically determine the struct's type. (Which is still doable, but requires you to register the struct and you essentially just recreate your own virtual function table, but it certainly wouldn't need to take O(n*m) time, although that is admittedly the naive way. As an example, a better way would be to use your virtual function table a struct-info to grab the type of the struct, and then just use a dict to return the relevant lens. This could be done in O(n) time, but I digress...)

I am not proposing the lens library try to imitate dynamic dispatch, I'm suggesting that you create a lens so that you can actually update fields defined in a super struct. Such as in my initial example:

(struct/lens foo (a) #:transparent)
(struct bar foo (b) #:transparent)
(define-struct-lenses bar)

I should have a way to get bar-a-lens when I either have a strong enough inspector or specify the fields manually, without having to manually make a new lens for each field, which is doable, but creates significantly more boilerplate than the boilerplate of just specifying fields.

[lexi-lambda]

Ah, I see. Since that wouldn’t work with heterogenous lists, though, what exactly would be the point of using subtyping here, though? I just feel a little wary about the confusion this could cause, since it seems pretty unintuitive to me that you’d break Liskov here.

If you do go this route, consider at least attaching a custom contract that prevents using subtypes with struct lenses that provides an explanatory error message? Something like this:

(struct/lens foo (a) #:transparent)
(struct bar foo (b) #:transparent)

> (lens-set foo-a-lens (bar 'a 'b) 'c)
foo-a-lens: contract violation
  expected: foo?, without subtypes
  given: (bar 'a 'b), which is a subtype of foo
  note: lenses do not work well with struct subtyping due to the design of Racket’s
        struct system; see the documentation for lens/data/struct for more information

[AlexKnauth]

I don't agree that error messages for using subtypes would be good. If B is a subtype of A then the A operations should work without error on B things. The confusion comes from you expecting something with the type A -> A to also have the type B -> B if B inherits from A, which is not true.

A -> A

Does not mean

∀ (X) where (X <: A)
  X -> X

But the type A -> A does imply its supertypes, including

B -> A

(Edit: This means a bar-foo-a-lens would be needed as a separate lens from foo-a-lens, and that foo-a-lens would keep the same behavior it currently has, loosing the information from the subtypes. It also means the heterogeneous list example would convert every element to a foo, unless it used a lens with some sort of dynamic lookup.)

[LeifAndersen]

Ah, I see. Since that wouldn’t work with heterogeneous lists, though, what exactly would be the point of using subtyping here, though?

So that I can do your above example with a homogeneous list for starters.

I just feel a little wary about the confusion this could cause, since it seems pretty unintuitive to me that you’d break Liskov here.

Ya, I completely agree. For what it's worth, I feel like it's the Racket struct system that breaks this, not lenses.

If you do go this route, consider at least attaching a custom contract that prevents using subtypes with struct lenses that provides an explanatory error message? Something like this:

Yup, I also completely agree with this example.

[lexi-lambda]

@AlexKnauth I disagree, because the current behavior violates the lens laws: (lens-transform foo-a-lens x identity) can potentially return a value that is not equal? to x.

[AlexKnauth]

It violates it if equality of foos is defined as equal?. However if you define foo=? as

(define (foo=? x y)
  (and (equal? (foo-a x) (foo-a x))
       (equal? (foo-b x) (foo-b x))
       ...))

Then this does not violate the lens laws. However, I can see that this definition of equality is very weird when sub-structing is involved.

[AlexKnauth]

Is there a way to declare structs as final? That's what this weirdness makes me want.

[LeifAndersen]

At the moment, no, not that I can think of anyway. I mean, if you make a struct that extends another struct, you must at least have access to the super struct's constructor.

[lexi-lambda]

As far as I know, no, not directly (otherwise I would be using it!). Any struct type can be used as a supertype with make-struct-type, so if the struct type is exposed to a user, it can be subtyped.

Of course, the way struct and define-struct work is a little bit different, since they rely on the transformer binding to expand to the necessary make-struct-type call. If you use the #:omit-define-syntaxes option and do not expose struct:id, that would probably have the effect of disallowing subtyping, but of course that would break lots of other things (including match expanders and this very package’s struct-related forms).

Maybe we’re going about this the wrong way, though—would it be possible to create a primitive in Racket itself that can do the necessary copy properly? That could solve a lot of existing problems, including struct-copy’s many levels of brokenness, such as racket/racket#1399.

[LeifAndersen]

@lexi-lambda Heh, lol, that's a great bug. It's like the SO post I made recently. I feel like rename transformers cause a lot of confusion when mixed with other macros for this exact reason.

[jackfirth]

Would it even be possible to add "final" structs to the Racket runtime? That's my ideal preferred solution to this problem but I suspect the way structs are internally represented is not amenable to that approach.

[LeifAndersen]

Kind of, but not really...

The problem is that anyone with a powerful enough impersonator can grab your struct type. And, as @lexi-lambda said, they can then make their own.

All functions that allow you to create an impersonator always make it as a sub or sibling impersonator to the current-impersonator. So, doing this you can kind of do it to a first approximation. But your whole program could really be running in a sandbox in a larger environment (like how DrRacket runs code), and in that case it can still extend your struct. If you want to disregard that use case, then yes, a final should be possible.

[lexi-lambda]

@LeifAndersen I’m not sure that it’s an issue with renaming, specifically, but more an issue with how the information structs provide is insufficient for a lot of practical use-cases (both the static information and the runtime capabilities). The missing information forces struct-copy to be unhygienic when really it has no business doing anything hygiene bending at all given what it does.

Fixing the static information is hard but not intractable, but fixing the dynamic model is probably a lot harder, since structs are very low-level primitives. At that point it might be easier to create a separate struct2 form that implements an entirely new struct system on top of the old one. Obviously, in either case, maintaining backwards compatibility is where the real difficulty comes from.

[LeifAndersen]

Actually, I think its possible, but you're not going to like it @jackfirth (and @lexi-lambda )

Create your struct type, and never ever ever give anyone access to your struct outside of a closure. Then, only really the compiler (and any unsafe libraries) can really get to your structs and thus get the struct-type.

[LeifAndersen]

@lexi-lambda Yup, I agree on both accounts.

(Hence why I said, woops, other way, on your issue....)

[lexi-lambda]

Create your struct type, and never ever ever give anyone access to your struct outside of a closure.

Yeah, this is effectively what I mentioned a little bit earlier by using #:omit-define-syntaxes and not exporting the struct type. You can do that more easily by using make-struct-type directly and not exposing the struct-type? result, but at that point you’d have to reimplement some things so that match and other forms (again, including struct-lens and friends) still work. It’s possible, though, since make-struct-info and prop:struct-info exist.

[LeifAndersen]

Yup, exactly. :) Well, :(, but at least we're on the same page.

[LeifAndersen]

And ya, the more I think about this, the more I think we just need to make struct2. :(

[LeifAndersen]

On the other hand, I have to admit that it's pretty cool that Racket is powerful enough for us to make struct2, but I fear it will be much slower. :(

[AlexKnauth]

With https://github.com/lexi-lambda/struct-update/pull/3, this is what I'm planning to do. For these structs:

(struct foo (a b c))
(struct sub (c a t))

The form (define-struct-lenses foo) would generate foo-a-lens, foo-b-lens, and foo-c-lens, and they would convert subs to foos when setting.

However the form (define-struct-lenses sub) would generate sub-foo-a-lens, sub-foo-b-lens, and sub-foo-c-lens, in addition to the normal sub-c-lens, sub-a-lens, and sub-t-lens. The sub-foo-a-lens etc. ones would take only subs (not foos) and preserve the sub information. However information from other structs that inherit from sub will still be lost.

[AlexKnauth]

@lexi-lambda Would it make sense to share some more of this code with the struct updaters?

Specifically, the names of the "sub-pieces" to update, as identifiers at compile time. Something that given sub above, would return a list containing the identifiers sub-foo-a, sub-foo-b, sub-foo-c, sub-c, sub-a, and sub-t. The struct-update code could append -set and -update to these, and the lens code could append -lens to them. Does it make sense to factor this shared code out? Would this notion possibly be useful anywhere else, or would it be specific to just these two packages?

[AlexKnauth]

@lexi-lambda The common code could be included in a syntax class like this:

  (define-syntax-class struct-id/sub-pieces
    #:attributes [all-fields-visible? constructor-id [accessor-id 1] [sub-piece 1]]
    [pattern (~and struct :struct-id)
      #:with [sub-piece ...]
             (for/list ([(accessor-id index) (in-indexed (in-list (@ accessor-id)))])
               (cond
                 [(< index (@ num-supertype-fields))
                  (format-id #'struct "~a-~a" #'struct accessor-id #:source #'struct #:props #'struct)]
                 [else
                  accessor-id]))])

The main thing that this gets rid of is the need for the condition in the struct-id/set+update syntax class.