diff options
Diffstat (limited to 'src/blog/an-inheritance-detox.kuht')
| -rwxr-xr-x | src/blog/an-inheritance-detox.kuht | 853 |
1 files changed, 853 insertions, 0 deletions
diff --git a/src/blog/an-inheritance-detox.kuht b/src/blog/an-inheritance-detox.kuht new file mode 100755 index 0000000..200380f --- /dev/null +++ b/src/blog/an-inheritance-detox.kuht @@ -0,0 +1,853 @@ +<import "base.kuht" as "base" /> + +<head> + <title>An Inheritance Detox</title> + <meta name="description" content="I once pointed out to someone, who was learning Rust, that Rust doesn't have inheritance. Even people who like object-oriented programming don't like inheritance, so this is how I explained why and what you should do instead." /> +</head> + +<body> + +<article> + +<h1>An Inheritance Detox</h1> + +<p> + I once pointed out to someone, who was learning Rust, that Rust doesn't have inheritance. He's a + software engineering major at RIT<a id="af-1" href="#footnote-1"><sup>1</sup></a>, so this was a + shock to him. I eventually told him I would need to give him an object-oriented programming detox. + But as I was researching, I learned that even people who like object-oriented programming don't + defend inheritance anymore. Inheritance was the problem he was dealing with, so I decided to just + focus on that. This post is a blog-translation of the presentation I eventually gave to the Buffalo + Rust User Group. +</p> + +<blockquote> + I once attended a Java user group meeting where James Gosling (Java's inventor) was the featured + speaker. During the memorable Q&A session, someone asked him: "If you could do Java over again, + what would you change?" "I'd leave out classes", he replied. After the laughter died down, he + explained that the real problem wasn't classes per se, but rather implementation inheritance + (the extends relationship). Interface inheritance (the implements relationship) is preferable. You + should avoid implementation inheritance whenever possible. + <p><a href="https://www.infoworld.com/article/2160788/why-extends-is-evil.html">- Allen Holub</a></p> +</blockquote> + +<h2>The Problem of Inheritance</h2> + +<p> + For starters, anything you can do with inheritance, you can also do with composition. I'll give some + examples of that later. That, on its own, should enough to make you skeptical of inheritance, but + I'll keep going. +</p> + +<p> + One problem is that inheritance leads to unnecessary coupling. Allowing the child class to modify the + base class, and vice-versa, are going to result in more testing on your part. If you ever change the + base class, not only do you need to retest that base class, but also anything that inherits from that + base class. +</p> + +<p> + Another problem is known as the fragile-base class problem. To illustrate it, here's an example of + some code that would be difficult to write in Rust: +</p> + +<pre> +public class Queue<E> extends ArrayList<E> { + private int start; + + public Queue() { + this.start = 0; + } + + public void enqueue(E element) { + this.add(element); + } + + public E dequeue() { + return this.get(this.start++); + } +} +</pre> + +<p> + Say, for the sake of argument, that when you implemented the <code>Queue</code>, the + <code>ArrayList</code> only had two methods: <code>get</code> and <code>add</code>. Later, somebody + decides to add a <code>clear</code> method. What happens if someone calls <code>queue.clear()</code>? + Your <code>start</code> field won't be updated to reflect the new length. So you'll very quickly run + into a bug. +</p> + +<pre> +Queue<Integer> queue = new Queue<>(); +queue.enqueue(5); +queue.enqueue(6); +int x = queue.dequeue(); +// pretty normal so far + +queue.clear(); // oh no +int y = queue.dequeue(); // oh no no no no +</pre> + +<p> + Ok, so let's say, for the sake of argument, that you realize what happened and update + <code>Queue</code> quickly. +</p> + +<pre> +public class Queue<E> extends ArrayList<E> { + // ... *snip* ... + + @override + public void clear() { + this.start = 0; + super.clear(); + } +} +</pre> + +<p>That's one problem solved. But what happens when someone adds <code>removeRange</code>?</p> + +<pre> +public class Queue<E> extends ArrayList<E> { + // ... *snip* ... + + @override + public void removeRange(int from, int to) { + // ??? + } +} +</pre> + +<p> + So a better way of doing this would be to have <code>Queue</code> contain an <code>ArrayList</code>, + rather than being an <code>ArrayList</code>. +</p> + +<pre> +public class Queue<E> { + private int start; + private ArrayList<E> list; + + public Queue() { + this.start = 0; + this.list = new ArrayList<>(); + } + + public void enqueue(E element) { + this.list.add(element); + } + + public E dequeue() { + return this.list.get(this.start++); + } +} +</pre> + +<p>Note that this is actually very easy to write in Rust.</p> + +<pre> +pub struct Queue<T> { + start: int, + list: Vec<T>, +} + +impl<T> Queue<T> { + pub const fn new() -> Self { + Self { + start: 0, + list: Vec::new(), + } + } + + pub fn enqueue(&mut self, item: T) { + self.list.push(item); + } + + pub fn dequeue(&mut self) -> Option<T> { + let idx = self.start; + self.start += 1; + self.list.get(idx) + } +} +</pre> + +<p> + In Allen Holub's article, <a href="https://www.infoworld.com/article/2160788/why-extends-is-evil.html"> + Why <code>extends</code> is evil</a>, he gives another example of a problem where optimizing a + base <code>Stack</code> class causes a problem if the child classes depend on a method being called. + I won't copy and past his article, but I wanted to show that he recommended using an interface in + that case. And the interface he wrote translates very nicely to Rust. +</p> + +<pre> +pub trait Stack<T> { + fn push(&mut self, item: T); + fn pop(&mut self) -> T; + fn push_many(&mut self, items: &[T]); +} + +pub struct SimpleStack<T> { + stack_pointer: Option<usize>, + stack: Box<[T]> +} + +impl<T> Stack<T> for SimpleStack<T> { + fn push(&mut self, item: T) { + self.stack_pointer += 1; + self.stack[self.stack_pointer] = item; + } + + fn pop(&mut self) -> T { + let item = self.stack[self.stack_pointer]; + self.stack_pointer -= 1; + item + } + + fn push_many(&mut self, items: &[T]) { + // Notice that this doesn't call push. If this were a base class for + // MonitorableStack, it might incorrectly assume that this will call push. + + let start = self.stack_pointer + 1; + let end = self.stack_pointer + 1 + items.len(); + self.stack[start..end].clone_from_slice(items); + self.stack_pointer += items.len(); + } +} + +pub struct MonitorableStack<T> { + stack: SimpleStack<T>, + high_water_mark: usize, + current_size: usize, +} + +impl<T> Stack<T> for SimpleStack<T> { + fn push(&mut self, item: T) { + self.current_size += 1; + if self.current_size > self.high_water_mark { + high_water_mark = self.current_size; + } + + self.stack.push(item) + } + + fn pop(&mut self) -> T { + self.current_size -= 1; + self.stack.pop() + } + + fn push_many(&mut self, items: &[T]) { + if self.current_size + items.len() > self.high_water_mark { + self.high_water_mark = self.current_size + items.len(); + } + + // We cannot assume that our call function will be pushed, because + // that'd be impossible. We're in charge of our own destiny here. + self.stack.push_many(items) + } +} +</pre> + +<p>That was a long piece of code. But I hope that the point is clear.</p> + +<h2>Replacing Inheritance</h2> + +<p>So if we can't use inheritance, what can we use. Rust provides a few mechanisms for composition:</p> +<ul> + <li>structs (the equivalent of final class in Java)</li> + <li>traits (like interfaces in Java)</li> + <li>enums (Java has no equivalent. Java enums aren't the same.)</li> +</ul> + +<p>Let's show a few examples of common object-oriented patterns in Rust.</p> + +<h3>Factory Methods</h3> + +<p> + It's worth noting that I'm getting these patterns from <a href="https://www.oodesign.com">oodesign.com</a>. + For copyright reasons, I will link to <a href="https://www.oodesign.com/factory-method-pattern">their implementation</a>. +</p> + +<p> + Their example is actually hilarious to me, because we can replace it with a type alias, if you're ok + with monomorphization, and the fact that Rust doesn't actually care about type bounds on type alises + at the moment. +</p> + +<pre> +type Factory<P: Product> = fn() -> P; +</pre> + +<p> + The typical use-case I've seen for factories in the past is when creating the product relies on some + other state. Another case is when we can't specify the underlying type and only know that it's a + product. We can do bose of those as well. +</p> + +<pre> +trait ProductFactory { + fn create_product(&mut self) -> Box<dyn Product>; +} +</pre> + +<p>The Java version is even simpler:</p> + +<pre> +interface ProductFactory { + Product createProduct(); +} +</pre> + +<h3>Shapes</h3> + +<p> + This is a very common example of inheritance, but I think it's accidentally an example of why you + shouldn't use it. There's an example on <a href="https://www.oodesign.com/prototype-pattern">oodesign.com</a>. + Notice that calling <code>setWidth</code> on a square doesn't make very much sense. Here's what I + would do in Rust: +</p> + +<pre> +trait Shape { + fn width(&self) -> f32; + + fn height(&self) -> f32; + + fn area(&self) -> f32; + + // no need for set_width and set_height here +} + +struct Rectangle { + width: f32, + height: f32, +} + +impl Rectangle { + fn set_height(&mut self, height: f32) { + self.height = height; + } + + fn set_width(&mut self, width: f32) { + self.width = width; + } +} + +impl Shape for Rectangle { + fn width(&self) -> f32 { + self.width + } + + fn height(&self) -> f32 { + self.height + } + + fn area(&self) -> f32 { + self.width * self.height + } +} + +struct Square { + size: f32, +} + +impl Square { + fn set_size(&mut self, size: f32) { + self.size = size; + } +} + +impl Shape for Square { + fn width(&self) -> f32 { + self.size + } + + fn height(&self) -> f32 { + self.size + } + + fn area(&self) -> f32 { + self.size * self.size + } +} +</pre> + +<h3>Interpreter</h3> + +<p> + I was planning on using the Command pattern here, but after another look I noticed that the provided + example didn't even use inheritance. So instead we'll use the + <a href="https://www.oodesign.com/interpreter-pattern">interpreter pattern</a>. This pattern is + amazing for Rust, because of enums. If you don't want user code to extend the set of possible + commands, then this is really simple. +</p> + +<pre> +pub enum Expression { + Literal(Arc<str>), + Or(Arc<Expression>, Arc<Expression>), + And(Arc<Expression>, Arc<Expression>) +} + +impl Expression { + fn interpret(&self, tokens: &[Token]) -> bool { + match self { + Self::Literal(test) => for token in tokens { + if token.value() == test { + return true; + } + + false + }, + Self::Or(expr1, expr2) => expr1.interpret(tokens) || expr2.interpret(tokens), + Self::And(expr1, expr2) => expr1.interpret(tokens) && expr2.interpret(tokens), + } + } +} +</pre> + +<p> + Let's say, for the sake of argument, that you want the set of expressions to be extendable. That can + be done too. +</p> + +<pre> +pub trait Expression { + fn interpret(&self, tokens: &[Token]) -> bool; +} + +pub struct TerminalExpression { + literal: Arc<str>, +} + +impl TerminalExpression { + pub fn new(literal: Arc<str>) -> Self { + Self { literal } + } +} + +impl Expression for TerminalExpression { + fn interpret(&self, tokens: &[Token]) -> bool { + for token in tokens { + if token.value() == self.literal { + return true; + } + } + + false + } +} + +pub struct OrExpression { + expression1: Arc<Expression>, + expression2: Arc<Expression>, +} + +impl OrExpression { + pub fn new(expression1: Arc<Expression>, expression2: Arc<Expression>) -> Self { + Self { + expression1, + expression2 + } + } +} + +impl Expression for OrExpression { + fn interpret(&self, tokens: &[Token]) -> bool { + self.expression1.interpret(tokens) || self.expression2.interpret(tokens) + } +} + +pub struct AndExpression { + expression1: Arc<Expression>, + expression2: Arc<Expression>, +} + +impl AndExpression { + pub fn new(expression1: Arc<Expression>, expression2: Arc<Expression>) -> Self { + Self { + expression1, + expression2 + } + } +} + +impl Expression for AndExpression { + fn interpret(&self, tokens: &[Token]) -> bool { + self.expression1.interpret(tokens) && self.expression2.interpret(tokens) + } +} +</pre> + +<p>But that is far more verbose.</p> + +<h3>Observer</h3> + +<p> + In case someone is now accusing me of picking examples that work too easily in Rust, the Observer + pattern is actually quite difficult. So before I show this one, I want to give a sneak peak into what + this pattern looks like in Java. The inheritance version is provided on + <a href="https://www.oodesign.com/observer-pattern">oodesign.com</a>, but I'll use composition. +</p> + +<pre> +interface Observer { + void update(); +} + +class Observable { + private ArrayList<Observer> observers; + + public Observable() { + this.observers = new ArrayList<>(); + } + + public void attach(Observer observer) { + this.observers.add(observer); + } + + public void detach(Observer observer) { + this.observers.remove(observer); + } + + public String notify(String newState) { + for (Observer observer in this.observers) { + observer.update(); + } + } +} + +class StatefulObservable { + private Object state; + private Observable observable; + + public StatefulObservable(Object initialState) { + this.state = initialState; + this.observable = new Observable(); + } + + public void attach(Observer observer) { + this.observable.attach(observer); + } + + public void detach(Observer observer) { + this.observable.detach(observer); + } + + public Object getState() { + return this.state; + } + + public setState(Object newState) { + this.state = newState; + this.observable.notify(); + } +} +</pre> + +<p> + I wanted this here because I wanted to point out that the tricky part of this pattern is Rust's + borrow checker, and not composition. So now we'll walk step by step through making this work in Rust. +</p> + +<p>First, we'll need an <code>Observer</code> trait. That's easy.</p> + +<pre> +trait Observer { + fn update(&mut self); +} +</pre> + +<p> + "Show me your data, and your functions will be obvious", so let's go ahead and make the + <code>Observable</code> struct. The problem is that we need to be able to mix and match different + types that all implement <code>Observable</code>. We'll need a <code>dyn Observable</code>, but + trait objects aren't sized, and thus can't be put into a <code>Vec</code> directly. We can't use + <code>Arc</code> because <code>Observer::update</code> requires a mutable reference. We'll use + <code>Box</code>. +</p> + +<pre> +struct Observable { + observers: Vec<Box<dyn Observer>>, +} +</pre> + +<p> + You might be wondering why <code>Observer::update</code> needs a mutable reference. What if we want + to have multiple references to the observer? The answer to the first question is that some + <code>Observer</code>s will need to mutate after an update. The answer to the second question is that + it won't be difficult to wrap your existing <code>Observer</code> inside of an <code>Arc</code> + before attaching it to the <code>Observable</code>. Yeah, <code>Box<Arc<Observer>></code> + isn't ideal, but it's better than forcing the Observables to all have interior mutability. +</p> + +<pre> +use super::ImmutableObserver; // we want multiple references to this + +#[derive(Debug, Clone)] +pub struct AliasableObserver(Arc<ImmutableObserver>); + +impl Observer for AliasableObserver { + fn update(&mut self) { + self.0.update() + } +} +</pre> + +<p>Alternatively, we could update our API to allow both immutable and mutable observers.</p> + +<pre> +pub trait Observer { + fn update(&self); +} + +pub trait MutableObserver { + fn update(&mut self); +} + +pub struct Observable { + observers: Vec<Arc<dyn Observer>>, + mutable_observers: Vec<Box<dyn MutableObserver>>, +} +</pre> + +<p> + I actually like this idea, so let's go with this. But this raises another concern. In Java, we could + detach observers by passing in a reference and comparing the pointer addresses. This is still + possible with <code>observers</code> but not <code>mutable_observers</code>, since a <code>Box</code> + needs to be a unique reference. But, we could use a raw pointer. +</p> + +<pre> +impl Observable { + pub fn detach(&mut self, observer: *const ()) -> Option<()> { + for i in 0..self.observers.len() { + if std::ptr::addr_eq(&self.observers[i], observer) { + self.observers.remove(i); + return Some(()); + } + } + + for i in 0..self.mutable_observers.len() { + if std::ptr::addr_eq(&self.mutable_observers[i], observer) { + self.mutable_observers.remove(i); + return Some(()); + } + } + + None + } +} +</pre> + +<p> + Dealing with raw pointers is annoying, but it works. Alternatively, we could put an ID on each + attached observer, and remove using an ID, but that sounds even worse. Plus, we'd have to deal with a + sparse index. I don't want that. +</p> + +<p> + I suppose we've jumped the gun a bit on implementing <code>detach</code>, so now let's implement the + rest of <code>Observable</code>. +</p> + +<pre> +impl Observable { + pub const fn new() -> Self { + Self { + observers: Vec::new(), + mutable_observers: Vec::new(), + } + } + + pub fn attach(&mut self, observer: Arc<dyn Observer>) { + self.observers.push(observer); + } + + + pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) { + self.mutable_observers.push(observer); + } + + pub fn detach(&mut self, observer: *const ()) -> Option<()> { + // ... already did this ... + } + + pub fn notify(&mut self) { + for observer in &self.observers { + observer.update(); + } + + for observer in &mut self.mutable_observers { + observer.update(); + } + } +} +</pre> + +<p> + Now all that's left is the <code>StatefulObserver</code>. In the Java implementation, I used an + <code>Object</code> as the state, but that's not very useful in Rust (or in general). So instead + I'll use a generic type here. The implementation is pretty simple, so I'll write that out too. +</p> + +<pre> +pub struct StatefulObservable<T> { + state: T, + observable: Observable, +} + +impl<T> StatefulObservable<T> { + pub const fn new(initial_state: T) -> Self { + Self { + state: initial_state, + observable: Observable::new(), + } + } + + pub fn state(&self) -> &T { + &self.state + } + + pub fn attach(&mut self, observer: Arc<dyn Observer>) { + self.observable.attach(observer) + } + + pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) { + self.observable.attach_mutable(observer) + } + + pub fn detach(&mut self, observer: *const ()) -> Option<()> { + self.observable.detach(observer) + } + + pub fn set_state(&mut self, new_state: T) { + self.state = new_state; + self.observable.notify(); + } +} +</pre> + +<p>And now we're done. Here's the full code for the curious:</p> + +<pre> +use std::sync::Arc; + +pub trait Observer { + fn update(&self); +} + +pub trait MutableObserver { + fn update(&mut self); +} + +pub struct Observable { + observers: Vec<Arc<dyn Observer>>, + mutable_observers: Vec<Box<dyn MutableObserver>>, +} + +impl Observable { + pub const fn new() -> Self { + Self { + observers: Vec::new(), + mutable_observers: Vec::new(), + } + } + + pub fn attach(&mut self, observer: Arc<dyn Observer>) { + self.observers.push(observer); + } + + + pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) { + self.mutable_observers.push(observer); + } + + pub fn detach(&mut self, observer: *const ()) -> Option<()> { + for i in 0..self.observers.len() { + if std::ptr::addr_eq(&self.observers[i], observer) { + self.observers.remove(i); + return Some(()); + } + } + + for i in 0..self.mutable_observers.len() { + if std::ptr::addr_eq(&self.mutable_observers[i], observer) { + self.mutable_observers.remove(i); + return Some(()); + } + } + + None + } + + pub fn notify(&mut self) { + for observer in &self.observers { + observer.update(); + } + + for observer in &mut self.mutable_observers { + observer.update(); + } + } +} + +pub struct StatefulObservable<T> { + state: T, + observable: Observable, +} + +impl<T> StatefulObservable<T> { + pub const fn new(initial_state: T) -> Self { + Self { + state: initial_state, + observable: Observable::new(), + } + } + + pub fn state(&self) -> &T { + &self.state + } + + pub fn attach(&mut self, observer: Arc<dyn Observer>) { + self.observable.attach(observer) + } + + pub fn attach_mutable(&mut self, observer: Box<dyn MutableObserver>) { + self.observable.attach_mutable(observer) + } + + pub fn detach(&mut self, observer: *const ()) -> Option<()> { + self.observable.detach(observer) + } + + pub fn set_state(&mut self, new_state: T) { + self.state = new_state; + self.observable.notify(); + } +} +</pre> + +<h2>Conclusion</h2> + +<p> + Anything you can do with inheritance, you can also do with composition. Composition will make your + code easier to modify in the future, without creating weird semantics or bugs. Use composition, + wherever possible. +</p> + +</article> + +<hr/> + +<footer> + <ol> + <li id="footnote-1"> + I'm not quite sure what software engineering majors do at RIT. I imagine them all sitting + around a table, and saying words like "agile" and "scrum" with no context. I took Computer + Science. <a class="return" href="#af-1">return</a> + </li> + </ol> +</footer> + +</body> |