First commit

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&lt;E> extends ArrayList&lt;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&lt;Integer> queue = new Queue&lt;>();
+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&lt;E> extends ArrayList&lt;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&lt;E> extends ArrayList&lt;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&lt;E> {
+	private int start;
+	private ArrayList&lt;E> list;
+
+	public Queue() {
+		this.start = 0;
+		this.list = new ArrayList&lt;>();
+	}
+
+	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&lt;T> {
+	start: int,
+	list: Vec&lt;T>,
+}
+
+impl&lt;T> Queue&lt;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&lt;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&lt;T> {
+	fn push(&mut self, item: T);
+	fn pop(&mut self) -> T;
+	fn push_many(&mut self, items: &[T]);
+}
+
+pub struct SimpleStack&lt;T> {
+	stack_pointer: Option&lt;usize>,
+	stack: Box&lt;[T]>
+}
+
+impl&lt;T> Stack&lt;T> for SimpleStack&lt;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&lt;T> {
+	stack: SimpleStack&lt;T>,
+	high_water_mark: usize,
+	current_size: usize,
+}
+
+impl&lt;T> Stack&lt;T> for SimpleStack&lt;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&lt;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&lt;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&lt;str>),
+	Or(Arc&lt;Expression>, Arc&lt;Expression>),
+	And(Arc&lt;Expression>, Arc&lt;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&lt;str>,
+}
+
+impl TerminalExpression {
+	pub fn new(literal: Arc&lt;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&lt;Expression>,
+	expression2: Arc&lt;Expression>,
+}
+
+impl OrExpression {
+	pub fn new(expression1: Arc&lt;Expression>, expression2: Arc&lt;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&lt;Expression>,
+	expression2: Arc&lt;Expression>,
+}
+
+impl AndExpression {
+	pub fn new(expression1: Arc&lt;Expression>, expression2: Arc&lt;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&lt;Observer> observers;
+
+	public Observable() {
+		this.observers = new ArrayList&lt;>();
+	}
+
+	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&lt;Box&lt;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&lt;Arc&lt;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&lt;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&lt;Arc&lt;dyn Observer>>,
+	mutable_observers: Vec&lt;Box&lt;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&lt;()> {
+		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&lt;dyn Observer>) {
+		self.observers.push(observer);
+	}
+
+
+	pub fn attach_mutable(&mut self, observer: Box&lt;dyn MutableObserver>) {
+		self.mutable_observers.push(observer);
+	}
+
+	pub fn detach(&mut self, observer: *const ()) -> Option&lt;()> {
+		// ... 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&lt;T> {
+	state: T,
+	observable: Observable,
+}
+
+impl&lt;T> StatefulObservable&lt;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&lt;dyn Observer>) {
+		self.observable.attach(observer)
+	}
+
+	pub fn attach_mutable(&mut self, observer: Box&lt;dyn MutableObserver>) {
+		self.observable.attach_mutable(observer)
+	}
+
+	pub fn detach(&mut self, observer: *const ()) -> Option&lt;()> {
+		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&lt;Arc&lt;dyn Observer>>,
+	mutable_observers: Vec&lt;Box&lt;dyn MutableObserver>>,
+}
+
+impl Observable {
+	pub const fn new() -> Self {
+		Self {
+			observers: Vec::new(),
+			mutable_observers: Vec::new(),
+		}
+	}
+
+	pub fn attach(&mut self, observer: Arc&lt;dyn Observer>) {
+		self.observers.push(observer);
+	}
+
+
+	pub fn attach_mutable(&mut self, observer: Box&lt;dyn MutableObserver>) {
+		self.mutable_observers.push(observer);
+	}
+
+	pub fn detach(&mut self, observer: *const ()) -> Option&lt;()> {
+		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&lt;T> {
+	state: T,
+	observable: Observable,
+}
+
+impl&lt;T> StatefulObservable&lt;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&lt;dyn Observer>) {
+		self.observable.attach(observer)
+	}
+
+	pub fn attach_mutable(&mut self, observer: Box&lt;dyn MutableObserver>) {
+		self.observable.attach_mutable(observer)
+	}
+
+	pub fn detach(&mut self, observer: *const ()) -> Option&lt;()> {
+		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>