inheritance: is circle an ellipse?
Jan. 24th, 2011 11:46 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
juan_gandhiIt's a known puzzle from the depths of object-oriented teaching: is Circle a subclass or Ellipse. From school we know it is; but as we read in books, for programmers, it is not. How come? Oh, "Liskov principle". They use Liskov principle to scare kids.
Actually we know that a circle is an ellipse with both axes being the same length.
But in programming, an ellipse is something different. It is at least stretchable. And it is also moveable. Somehow it is not rotatable, but we can skip it for simplicity.
An ellipse in programming is (almost) always horizontal; it can be moved (by changing coordinates of its center) and it can be stretched/compressed by changing its height and width. Sure a stretchable ellipse is neither an ellipse nor a circle, not even a stretchable circle. A stretchable circle stretches equally in all directions.
That's it, no? Questions? Objections?
Actually we know that a circle is an ellipse with both axes being the same length.
But in programming, an ellipse is something different. It is at least stretchable. And it is also moveable. Somehow it is not rotatable, but we can skip it for simplicity.
An ellipse in programming is (almost) always horizontal; it can be moved (by changing coordinates of its center) and it can be stretched/compressed by changing its height and width. Sure a stretchable ellipse is neither an ellipse nor a circle, not even a stretchable circle. A stretchable circle stretches equally in all directions.
That's it, no? Questions? Objections?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-01-24 08:07 pm (UTC)BTW, when I was a kid, I was being scared by sqare-rectangle example, not circle-ellipse.
"pessimist is a well-informed optimist"
Date: 2011-01-24 08:27 pm (UTC)no subject
Date: 2011-01-24 08:23 pm (UTC)Liskov principle corresponds to contravariance.
no subject
Date: 2011-01-24 09:48 pm (UTC)no subject
Date: 2011-01-24 10:05 pm (UTC)These people also claim that they are very "categorical", even extending Curry-Howard isomorphism to cartesian closed categories (http://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence#Curry.E2.80.93Howard.E2.80.93Lambek_correspondence).
This does not mean that they are right, but this is smth to keep in mind... (I tended to dislike contravariance when I was thinking about functional programming in the 1990-s, in particular, because I thought it was a bad idea to mimic object inheritance, and because of other reasons [one is that this results in "non-extensionality" [multiple points representing the same function from A to B in the models], but I did not like categorical models in software either back then. So, basically, if you come up with a viewpoint which would be categorical, but would decouple these things [proper inheritance and contravariance], it would be something different from mainstream [and might be better, but you would have to argue explicitly against the mainstream viewpoint here].)
no subject
Date: 2011-01-24 10:56 pm (UTC)I do not see the importance of substitutability, but is not it true that some functors are contravariant?
no subject
Date: 2011-01-25 01:33 am (UTC)sure; it's just that if one wants a system where subtypes are subsets, and functions are extensional ( (f, g: A -> B, and for all x from A, f(x) = g(x)) implies f = g), then this one cannot be contravariant (assuming that I have not made a mistake when "proving" that).
> I do not see the importance of substitutability
I think it is quite essential in justifying rules for various mainstream systems of types lambda calculus (e.g. parametric polymorphism of ML and similar systems); although it really becomes explicit, when one enriches a system like that with subtypes.
So here is a logical fork, which depends on whether one likes this class of type systems. If one likes these type systems, then it probably matters that this class of type systems comes from people who think that substitutability is quite key here (although it still does not mean that one has to agree with them, but their arguments should be considered).
Alternatively, one could decide that one does not like this class of type systems, and that inference rules should be different (like I was thinking in the 90-s; now I don't have a firm opinion). Then it's quite likely that substitutability would not be involved.
no subject
Date: 2011-01-25 06:58 am (UTC)After refreshing it in my memory, the canonical way to think about it in the mainstream school of thought is as follows. One considers a universal set D of all untyped lambda-terms (or of their equivalence classes). Types are just some subsets of D. When a lambda-term belongs to the subset X, we say that this term is of type X. Subtypes are subsets. A term f is said to be of type A->B, if whenever term x is of type A, term f(x) is of type B. Here we have contravariance and substitutability, and they are the same thing (easy to see), but we don't have extensionality (because the terms can be equivalent on the inputs from A, but can behave quite differently, when the inputs are outside of A).
Also, the resulting type systems are quite horrible (IMO) in two ways. On one hand, they are strongly normalizable, and lambda-terms without normal form are never typable, so the recursion and Turing-completeness have to be added by ad-hoc methods. On another hand, the inference is usually too strong, so, for example, one can write a pathological sequence of well-typed programs in ML, such that the size of their types is exponential of the size of the program as a directed acyclic graph (and doubly exponential as a linear output) and hence the compiling time is also exponential. And this "compiler bug" is built-in as a design feature right in the heart of ML and languages with the similar type systems (it does not really occur in practice, one has to work to create this pathology, but it's an ugly property of the type system and of the language).
no subject
Date: 2011-01-24 08:45 pm (UTC)В одной онтологии ont1:Круг и ont1:Эллипс могут быть отдельными классами, элементы которых частично пересекаются. В другой классы ont2:Круг и ont2:Эллипс не пересекаются - "если Круг, то уже не Эллипс". В третьей ont3:Круг явно описывается как подкласс ont3:Эллипс.
Разные определения эллипсов это разные классы, нельзя заявлять об их идентичности. Но тройка классов ont1:Круг, ont2:Круг и ont3:Круг содержит одни и те же элементы. Как и классы ont1:Эллипс и ont3:Эллипс содержат те же элементы, что объединение классов ont2:Эллипс и ont2:Круг.
Далее смотрим: про эллипсы нигде не указано, что они могут или не могут двигаться. Но даже подвижность и неподвижность могут рассматриваться и как возможности, и как ограничения. Тогда появляются, например, ont4:НеподвижныйЭллипс (пересечение классов ont4:Эллипс и ont4:НеподвижныйПримитив) или ont5:ПодвижныйЭллипс (пересечение классов ont5:Эллипс и ont5:ПодвижныйПримитив).
При переходе к архитектуре ПО выбор между ont4 и ont5 начинает сильно зависеть от используемых средств (языков программирования, etc). А верхняя онтология "что есть Примитив" (как онтология, API или описание формата данных) тоже может быть задана извне, где-то в требованиях по interoperability продукта.
А дальше - с чем удобнее работатьь в коде. Из первых трёх онтологий я бы выбрал ont1. :)
no subject
Date: 2011-01-24 09:05 pm (UTC)We do, but in schools they teach 'constant' circles and ellipses (functional style :-), so say, objects with quite limited interfaces. For which Liskov's works pretty well.
> sure a stretchable ellipse is neither an ellipse nor a circle
Stretchable ellipse is an ellipse. Why not?
> A stretchable circle stretches equally in all directions.
It may stretch unequally, but then it changes its type, if we are smart enough to implement consistently such a magic.
Bottom line: how would I design stuff like that? No idea. One approach is to abandon type system and use dynamic languages. If we want to have static type system... I have no idea whether such a thing has been designed already. Luca Cardelli might have wrote something about it. And... nobody said a perfect object-oriented type system is possible for design. OOP is not exactly about the real world, it is not promised to always work and always solve our problems, especially in compile time.
no subject
Date: 2011-01-24 09:52 pm (UTC)no subject
Date: 2011-01-24 09:59 pm (UTC)Anyway, why stretchable ellipse is not an ellipse... it depends on the axiom of choice actually. If it holds, it is; if we do not assume the AC, it is not. Stretchable ellipse is an equivalence class.
no subject
Date: 2011-01-25 03:21 am (UTC)How comes? In what way?
no subject
Date: 2011-01-25 03:58 am (UTC)I can give you an example when this is not the case.
Imagine a curve in space that projects (vertically) on an ellipse. This curve loops twice, in space. So for every point on ellipse there are two points projecting onto it. If we limit ourselves with continuous mappings only, we cannot split this projection.
no subject
Date: 2011-01-24 09:18 pm (UTC)Вот у окружности есть центр (две координаты) и радиус (положительное число); у эллипса центр, две полуоси и (при большой удаче) угол наклона. Ага, значит, варьируя центр (две координаты) и радиус, можно из окружности получить другие окружности; варьируя центр, две полуоси и (при большой удаче) угол наклона, можно получить другие эллипсы, которые иногда вырождаются в окружности, которые можно опять превратить в эллипсы (а те, настоящие окружности, нельзя).
То есть для окружностей одни законы преобразования, для эллипсов другие, и удивительное дело — те и другие хорошо соответствуют внутреннему представлению данных. С чего бы это?
Ну, если мы пишем MS Paint, это нормально. Но в Paint эллипс и окружность не обязаны быть подтипами ни друг друга, ни чего-то третьего (разве что абстрактного типа Shape). Там это просто не нужно.
Настоящие геометрические программы (не Paint) часто применяют настоящие геометрические преобразования. Я знаю, я это десять лет программировал за кусок хлеба с маслом. Например, преобразование подобия, при которых эллипсы, не являющиеся окружностями, никогда ими и не становятся. Или, например, произвольные аффинные преобразования, при которых окружности свободно переходят в эллипсы, и тогда отдельная сущность для окружностей просто не нужна.
Настоящие геометрические программы производят и другие геометрически осмысленные действия — пересекают кривые и поверхности и прочее. Вот при такой работе с геометрией полезно выделить общие свойства у эллипса и окружности (это частные случаи, то есть подтипы, квадратичной кривой). Но у геометрических кривых никакой мутабельности, то есть объектно-ориентированного «поведения», нет. Никто там не растягивается и не сжимается.
Как-то так.
no subject
Date: 2011-01-24 09:51 pm (UTC)Смешно, что в математике об этом и не рассуждают, всё понятно, а как начинают программировать, так мысли из башки вылетают, и начинается демагогия.
no subject
Date: 2011-01-24 09:51 pm (UTC)A circle cannot be a subclass, because eclipse can have radii of different lengths, but circles cannot.
An elipse cannot be a subclass, because circles know their radius, but elipses cannot (they do not even have such a concept).
no subject
Date: 2011-01-24 09:54 pm (UTC)extends- does it mean you extend something or limit something? Do you think red circles form a subclass of circles? How about visible circles?What can an ellipse do that circle cannot, tell me. Define a circle as an ellipse with two equal axes, and that's it.
no subject
Date: 2011-01-25 03:03 am (UTC)So if you had color-blind circles, then "colored circles" is a subclass (i.e. -- it adds an ability of a circle to know its color). Now, if your "colored circles" could never change color, then you could also make "red circles" a subclass of "colored circles", since you would not be removing any abilities. But if your "colored circles" could change colors before, then "red circles" is not a subclass.
Same analysis about "visible circles".
> "What can an ellipse do that circle cannot"?
If an ellipse object cannot change its shape (cannot change the radii independently, for example, via setters), then, indeed, a circle is a fine subclass of "ellipse". If ellipse radii were mutables, however, you would be taking away that ability, which is not allowed.
no subject
Date: 2011-01-24 10:57 pm (UTC)Looks like this whole idea of designing class hierarchies is not very useful, other than as far as refactoring goes. With the addition of the "you ain't gonna need it" principle, that means that if you can make the code clearer/more compact, then use the inheritance, otherwise don't bother.
Also, I find myself using inheritance not at the design stage, but at the refactoring stage. Code it up first, extract superclasses later if that makes sense.
So, to me this question is more of a "how many angels can dance on the head of a pin?" thing.
no subject
Date: 2011-01-25 01:56 am (UTC)Yeah, something like that.
Interesting. This implies "exploratory" programming. Does it mean if we had a solution beforehand we would not need inheritance? (Apparently, of classes, not interfaces?)
no subject
Date: 2011-01-25 03:28 am (UTC)Most inheritance attempts die when asked "can X have more than one Y". Can a car have more than one steering wheel? Well, yeah, why not. It would be a weird car, but it is quite possible. So, car is not a subclass of steering wheel.
There are, of course, other tests, but this one weeds off the vast majority of inheritance candidates.
no subject
Date: 2011-01-25 03:20 am (UTC)Thus, blindly transferring mathematical concepts to programming can create a lot of confusion.
Immutable circle is an immutable ellipse, and LSP here holds just fine. Mutable circle may or may not be a mutable ellipse, depending on the nature of allowed mutations. E.g. movable circle is a movable ellipse, but stretchable circle is not a stretchable ellipse, because a circle cannot be stretched the way an ellipse can be.
So, yes, you a right. The culprit is stretchability, as a particular case of mutability. This destroys the IS-A relationship between immutable objects.
no subject
Date: 2011-01-25 03:49 am (UTC)no subject
Date: 2011-01-25 05:05 am (UTC)For me "class of ellipses" is either the set of all ellipses, or something akin to typeof(Ellipse) or Ellipse.class. Of course, this is distinct from the class of circles.
no subject
Date: 2011-01-25 05:11 am (UTC)no subject
Date: 2011-01-25 07:58 am (UTC)On what morphisms? A mathematical circle is not the same as the Circle type/class/whatever you defined in a program.
no subject
Date: 2011-01-25 04:11 am (UTC)no subject
Date: 2011-01-25 05:20 am (UTC)Путаница примерно как если бы мы не могли различить вещественное число и множество вещественных чисел.
Откуда мы вообще знаем, что слово "эллипс" означает нечто эллиптическое? Это нигде не написано. Давайте заменим слово "эллипс" на слово "полигастроном", и будем рассуждать, чем отличается полигастроном от моногастронома... при этом полигастроном содержит четыре переменные, а моногастроном - две.
no subject
Date: 2011-01-25 07:12 am (UTC)no subject
Date: 2011-01-25 07:13 am (UTC)no subject
Date: 2011-01-25 05:54 pm (UTC)no subject
Date: 2011-01-25 09:26 pm (UTC)Но вопросы стоят более серьёзные; напишу отдельным постом.
no subject
Date: 2011-01-25 09:57 pm (UTC)Это одно и тоже.
Ну так и с эллипсами та же ситуация. Если сделать мутабельные числа, то можно ли умножить 3 на 1 + i?
no subject
Date: 2011-01-25 11:05 pm (UTC)no subject
Date: 2011-01-25 11:12 pm (UTC)no subject
Date: 2011-01-25 11:22 pm (UTC)MyReal x(2);
MyComplex y(1,1);
x.setValue(10);
x.multiplyBy(y);
no subject
Date: 2011-01-26 12:07 am (UTC)no subject
Date: 2011-01-26 01:18 am (UTC)Можно было бы спокойно эллипсы и окружности таскать by value, и конвертировать, если надо — как округляется double при приведении к int, например. Но всё упирается в производительность, память и старые вредные привычки вроде «на питоне я могу таскать туда-сюда целые массивы, а на плюсах всё должно быть оптимально!»
Мне так кажется. Но надо ещё подумать.
:-)
Date: 2011-01-25 08:01 am (UTC)movable и stretchable
Date: 2011-01-25 11:48 am (UTC)no subject
Date: 2011-01-25 01:07 pm (UTC)no subject
Date: 2011-01-25 11:06 pm (UTC)no subject
Date: 2011-01-27 02:30 pm (UTC)Описать интерфейс класса можно терминальной коалгеброй или изящнее, терминальной диалгеброй.
В таком понимании, вполне очевидно, что от класса "окружность" есть мономорфизм в "эллипс".
Правильно выше сказали - "долой классы, да здравствуют интерфейсы", с ними-то всё ясно.
no subject
Date: 2011-01-27 04:50 pm (UTC)