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
lexi-lambda/struct-update#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.