+ + + An Inheritance Detox + + + + + +

+ +

An Inheritance Detox

+ +

+ I once pointed out to someone, who was learning Rust, that Rust doesn't have inheritance. He's a + software engineering major at RIT¹, 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. +

+ +

+ 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. +
- Allen Holub
+

+ +

The Problem of Inheritance

+ +

+ 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. +

+ +

+ 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. +

+ +

+ 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: +

+ +

+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++);
+	}
+}
+

+ +

+ Say, for the sake of argument, that when you implemented the Queue, the + ArrayList only had two methods: get and add. Later, somebody + decides to add a clear method. What happens if someone calls queue.clear()? + Your start field won't be updated to reflect the new length. So you'll very quickly run + into a bug. +

+ +

+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
+

+ +

+ Ok, so let's say, for the sake of argument, that you realize what happened and update + Queue quickly. +

+ +

+public class Queue<E> extends ArrayList<E> {
+	// ... *snip* ...
+
+	@override
+	public void clear() {
+		this.start = 0;
+		super.clear();
+	}
+}
+

+ +

That's one problem solved. But what happens when someone adds removeRange?

+ +

+public class Queue<E> extends ArrayList<E> {
+	// ... *snip* ...
+
+	@override
+	public void removeRange(int from, int to) {
+		// ???
+	}
+}
+

+ +

+ So a better way of doing this would be to have Queue contain an ArrayList, + rather than being an ArrayList. +

+ +

+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++);
+	}
+}
+

+ +

Note that this is actually very easy to write in Rust.

+ +

+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)
+	}
+}
+

+ +

+ In Allen Holub's article, + Why extends is evil, he gives another example of a problem where optimizing a + base Stack 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. +

+ +

+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)
+	}
+}
+

+ +

That was a long piece of code. But I hope that the point is clear.

+ +

Replacing Inheritance

+ +

So if we can't use inheritance, what can we use. Rust provides a few mechanisms for composition:

structs (the equivalent of final class in Java)
traits (like interfaces in Java)
enums (Java has no equivalent. Java enums aren't the same.)

+ +

Let's show a few examples of common object-oriented patterns in Rust.

+ +

Factory Methods

+ +

+ It's worth noting that I'm getting these patterns from oodesign.com. + For copyright reasons, I will link to their implementation. +

+ +

+ 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. +

+ +

+type Factory<P: Product> = fn() -> 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. +

+ +

+trait ProductFactory {
+	fn create_product(&mut self) -> Box<dyn Product>;
+}
+

+ +

The Java version is even simpler:

+ +

+interface ProductFactory {
+	Product createProduct();
+}
+

+ +

Shapes

+ +

+ 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 oodesign.com. + Notice that calling setWidth on a square doesn't make very much sense. Here's what I + would do in Rust: +

+ +

+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
+	}
+}
+

+ +

Interpreter

+ +

+ 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 + interpreter pattern. 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. +

+ +

+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),
+		}
+	}
+}
+

+ +

+ Let's say, for the sake of argument, that you want the set of expressions to be extendable. That can + be done too. +

+ +

+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)
+	}
+}
+

+ +

But that is far more verbose.

+ +

Observer

+ +

+ 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 + oodesign.com, but I'll use composition. +

+ +

+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();
+	}
+}
+

+ +

+ 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. +

+ +

First, we'll need an Observer trait. That's easy.

+ +

+trait Observer {
+	fn update(&mut self);
+}
+

+ +

+ "Show me your data, and your functions will be obvious", so let's go ahead and make the + Observable struct. The problem is that we need to be able to mix and match different + types that all implement Observable. We'll need a dyn Observable, but + trait objects aren't sized, and thus can't be put into a Vec directly. We can't use + Arc because Observer::update requires a mutable reference. We'll use + Box. +

+ +

+struct Observable {
+	observers: Vec<Box<dyn Observer>>,
+}
+

+ +

+ You might be wondering why Observer::update needs a mutable reference. What if we want + to have multiple references to the observer? The answer to the first question is that some + Observers will need to mutate after an update. The answer to the second question is that + it won't be difficult to wrap your existing Observer inside of an Arc + before attaching it to the Observable. Yeah, Box<Arc<Observer>> + isn't ideal, but it's better than forcing the Observables to all have interior mutability. +

+ +

+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()
+	}
+}
+

+ +

Alternatively, we could update our API to allow both immutable and mutable observers.

+ +

+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>>,
+}
+

+ +

+ 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 observers but not mutable_observers, since a Box + needs to be a unique reference. But, we could use a raw pointer. +

+ +

+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
+	}
+}
+

+ +

+ 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. +

+ +

+ I suppose we've jumped the gun a bit on implementing detach, so now let's implement the + rest of Observable. +

+ +

+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();
+		}
+	}
+}
+

+ +

+ Now all that's left is the StatefulObserver. In the Java implementation, I used an + Object 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. +

+ +

+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();
+	}
+}
+

+ +

And now we're done. Here's the full code for the curious:

+ +

+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();
+	}
+}
+

+ +

Conclusion

+ +

+ 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. +

+ +

+ + + + diff --git a/src/blog/best-tool-for-the-job.kuht b/src/blog/best-tool-for-the-job.kuht new file mode 100755 index 0000000..ad89290 --- /dev/null +++ b/src/blog/best-tool-for-the-job.kuht @@ -0,0 +1,685 @@ + + + + The Best Tool for the Job + + + + + +

+ +

The Best Tool for the Job

+ +

+ I often see programmers saying that programming languages are tools, and that instead of arguing over + what the best language is, we should just pick the right tool for the job. I think this is a sensible + philosophy, but I've never seen it used in a sensible way. One time I was talking to someone who told + me that the Software Engineering program at RIT exclusively uses the Java programming language. When + I pointed out how weird this was, he said, "Languages are tools, and you should just use the right + tool for the job"¹. If Java is a hammer in this + analogy, then why is this major not teaching you how to use a screwdriver? +

+ +

+ There are other times when the philosphy is used in sort of the right way, but to promote a language + that doesn't fit at all. I keep seeing Go being recommended for web development, for example. That is + the intended purpose of the language, but I don't recommend it due to the strange way it handles + errors². +

+ +

+ To be clear, I don't hate this way of thinking. I approve of it. In fact, I find the suggestion that + we should just use the same language for everything even worse. But I wish more thought went into the + idea. In this article, I want to propose the actual ideal language for each task. Surely, this will + end all debates related to the choice of programming language. If you currently in the middle of such + a debate, link this article to your co-workers³, and + give yourselves the rest of the day off. +

+ +

My Biases

+ +

+ Just like everybody else, I have my own preferences for language design, which might not align with + yours. I still think my recommendations are correct, but I'll make some premises clear here, so that + if you want to adapt my work for your preferences, you may do so. +

+ +

+ I hate dynamic typing. The time it takes me to ensure type safety is far less than the time it + takes me to debug type errors, find the documentation that tells me what types I can pass into + a function, figure out what methods I can call on a given type, or even what type a given value + is supposed to be. Ensuring type safety doesn't take that much time anyway, as long as your + language has type inference. Most of the languages I recommend here have type inference. +
+ On that note, the language should try to prevent me from making runtime errors. No language can + fully prevent logic errors, but you shoud note that most, if not all, of the languages I + recommend have some sort of null safety, albeit not always by default. +
+ Similarly to the last two points, borrow checking provides many benefits (including + deadlock prevention) which I believe are worth the + hassle. I don't recommend a borrow checker all of the time, but it is a pretty common occurrence. +
+ I don't like object-oriented programming. I don't have a problem with classes. But when a + language forces me to put all of my behavior inside of a class, I get annoyed. I also recommend + against using inheritance. I can put up with languages like C#, but it's not an ideal situation. +

+ +

+ Something else that I think is worth pointing out is that I will be focusing more on the language + features than the ecosystem. In a more practical discussion, you should probably be thinking about + this. But I think the language features are more interesting, and it's not hard to imagine a good + ecosystem being developed for any of these languages. Sometimes, a language feature means it might + be easier to develop an ecosystem designed for a specific task. +

+ +

Systems or Embedded Programming

+ +

+ You'll need Assembly. There's no getting around that. The question is, what language do you use to + call your Assembly utilities? Given that most programming languages need a runtime, and that the + runtime does not exist until you write it, you have a limited set of options: +

+ +

More Assembly: Yuck. Do I need to explain this one?
C: + An oldie. Not quite a goodie. I think we can do better than 30 years of tech debt. +
C++: + Not much better than C. Linus Torvalds would actually prefer C. There's a lot of language bloat, + and creating a custom standard library for C++ is much harder than for C. +
Rust: + Not exactly made for kernel development. The Linux kernel can use it now, but they modified some + of the standard library features in order to make it work. +
Zig: This language isn't even 1.0 yet.

+ +

+ I recommend Rust. Most of the errors in many projects are due to memory safety issues. + + Android has solved this problem by using more memory safe languages. + Windows and Linux are also starting to introduce Rust into their codebases for the same reason. +

+ +

+ I also mentioned having to write a runtime for C and C++. That's not necessary for Rust. Rust has, in + addition to the standard library, a core library. The core library does not require an operating + system, and has some very convenient utilities, + including UTF-16. + And even without the standard library, you can use the built-in alloc crate to use utilities that require + memory allocation. You'll just need to bring your own memory allocator. +

+ +

+ I'm not done yet. Rust has async/await. Rust's implementation of async/await does not rely upon the + existence of an operating system. You can create your own async runtime, and then use async/await + inside of your kernel! If that does not sell you, nothing will. +

+ +

Parsers and Compilers

+ +

+ Now you have an operating system. Maybe you already have a shell and some command-line utilities. But + you now you need a way to compile programs on your new system. You don't necessarily want to write + everything in Rust. But you'll need to write a compiler for that to work. What language do you do it + in? I have a couple ideas for a good parser language. I'll make the case for both. +

+ +

Rust

+ +

+ There's one particular reason why I like Rust here: enums. Rust enums are discriminant unions, which + can make it much easier to create a token type, and an abstract syntax tree. Here's an example of + some types I'd make when creating a basic Lisp interpreter: +

+ +

+enum TokenType {
+	LeftParenthesis,
+	RightParenthesis,
+
+	LiteralNumber(f64),
+	LiteralString(Arc<str>),
+	Symbol(Arc<str>),
+}
+

+ +

And here's what the abstract syntax tree could look like:

+ +

+enum ExpressionType {
+	LiteralNumber(f64),
+	LiteralString(Arc<str>),
+	Symbol(Arc<str>),
+
+	SExpression(Arc<[ExpressionType]>),
+}
+

+ +

+ It gets more complicated than that when you're doing error reporting, but you can at least understand + how this makes things easier. I also recommend you take a look at the + Icon programming language. + You won't be using it, but it is a very useful framework for tokenizing. I wrote a Rust + implementation of some of Icon's standard library, in the form of a library called + snob. I still use it, and I recommend giving it a try. +

+ +

+ I don't think Rust is the perfect language for this task though. You may have noticed all of my + Arcs in that code snippet. Constantly copying a Box or a Vec + will get expensive very quickly. But this interface isn't the greatest. Constantly copying an + Arc isn't great either. In fact, the D programming language found that typical + generational garbage collection is faster than implementing garbage collection using + Arc⁴. Another problem is that Rust uses + more memory than a garbage collected language would. Rust monomorphizes generic functions for more + speed. But this bloats the binary size and uses a lot of memory. I can't find it now, but I remember + seeing a GitHub issue stating that rustc couldn't be compiled on a Raspberry Pi, because compiling it + requires too much memory. +

+ +

+ So I would recommend a garbage collected language, but the problem is that I can't find a language + that has Rust-style enums and garbage collection⁵. C# + could do this once they figure out discriminated unions. + But I don't hold much hope for that right now. +

+ +

Dart

+ +

+ Now I'll admit that I've never attempted to write a parser in Dart before. I'm only thinking about it + now. Dart doesn't have Rust-style enums. But it tried. Dart has sealed classes, and if you run a + switch statement on a sealed class, then it will require an exhaustive match. Here, I'll duplicate + the Token data structure I showed in Rust: +

+ +

+sealed class Token {}
+
+class LeftParenthesis extends Token {}
+
+class RightParenthesis extends Token {}
+
+class LiteralNumber extends Token {
+	final double value;
+
+	const LiteralNumber(this.value);
+}
+
+class LiteralString extends Token {
+	final String value;
+
+	const LiteralString(this.value);
+}
+
+class Symbol extends Token {
+	final String name;
+
+	const Symbol(this.name);
+}
+

+ +

+ Notice how that was far more verbose than the Rust implementation. And I didn't even create an + abstract syntax tree. We're also using inheritance, so we'll have to be careful about how we modify + the base class. But there is one benefit. Something I did not show in the Rust implementation is the + information about where the data is stored in the original source code. Adding that to the Rust + implementation can be done using another struct. +

+ +

+struct Token {
+	token_type: TokenType,
+	start: usize,
+	end: usize,
+	file: Arc<Path>,
+}
+

+ +

+ Then any token we create has to be wrapped in this new structure. But in Dart, we can do it by + modifying the base class +

+ +

+sealed class Token {
+	final int start;
+	final int end;
+	final File file;
+
+	const Token({required this.start, required this.end, required this.file});
+}
+

+ +

+ But then we'll also have to modify the constructors on the child classes to have the same + information. So you might still want to use composition here. But this would cut down on the of times + you have to write something like token.token_type. +

+ +

Dart seems promising. I'll try writing a parser in it sometime.

+ +

Scripts

+ +

+ So now you can create a parser. But a parser for what language? Say you need a scripting language for + some simple tasks. What can you use? +

+ +

+ Bash is ok, if the only thing you need to do is run some simple commands. But most scripts will end + up being more complicated than that. If your bash script needs a variable, then you shouldn't use + Bash. +

+ +

+ Here we have a different set of priorities. This code shouldn't take too long to write. In many cases + it will be thrown away immediately. We should still make it easy to read, just in case. But we might + not need it for very long. +

+ +

+ Python was designed to be a middle-ground between Bash and C. It's painfully slow, + but our scripts shouldn't take too long to run anyway. The syntax is kinda annoying, but not annoying + enough that I would consider writing a new language to replace it. There are some conveniences + like default parameters that I honestly wish Rust had, but that one in particular was implemented + with some stupid mutability rules. There's no interfaces, only inheritance. + Exceptions are bad. After getting used + to the borrow checker, I don't appreciate the with blocks. So much of the standard library + is deprecated. Python is certainly not the perfect language. +

+ +

+ But it does come with some interesting ideas. Gradual typing was probably the right decision for a + language like this. And I can't complain, because the type system comes with null safety. The idea of + having big integers by default is also really clever. And the large set of builtins is both a + blessing and a curse. It's a good idea for scripting, but not when half of the builtins are + deprecated. The package manager installs everything globally, which is not a great idea, but nothing + else really makes sense for a scripting language. Most scripts don't need their own directory and + node_modules. +

+ +

+ That said, there's more that could be done. I don't like whitespace as syntax, but maybe we could + agree on automatic-semicolon-insertion as a middle ground. A derive-like syntax seems especially + important for a language trying to cut down on developer time. This could even be done with macros. + Speaking of which, I'd like to see interfaces, and Rust's enums. Dart has some nice ideas too, like + the this.x parameter in constructors, as well as named constructors and factories. Hell, + use 1-based-indexing and use a numerical tower as the default number type, or at least use a decimal + type. Python is used mostly by novices, so we might as well make it easier for them. +

+ +

+ At this point, I've essentially proposed my own programming language. To be clear, I don't hate + Python enough to actually make this. I'm just dreaming here. +

+ +

Game Development

+ +

+ Now you want to have some fun, so why not make a video game? What language can we use for that? +

+ +

+ There are several constraints that game engines have that other programs do not. For example, we + really do not want any stuttering, so a garbage collector is out of the question, unless you decide + to manually run the garbage collector on every single frame. However, performance is another + important goal for a video game, so we probably want to avoid that too. That means + Rust is our only option. +

+ +

+ The problem there is that the ecosystem for Rust game development + isn't very ripe. There is the work-in-progress + Bevy game engine, but I honestly don't like the way you query + for components in it. So you'll be making your own game engine. Given that this is Rust, we will + still use an entity-component system. But the queries will be much simpler: +

+ +

+let mut player_sprite = cx.sprites.get("player")?;
+let player_collider = cx.colliders.get("player")?;
+player_sprite.set_position(player_collider.position());
+

+ +

+ It would be really cool if the engine supported hot reloading scripts, but Rust doesn't have that. + We could make it work by compiling the scripts to WebAssembly and reloading them when the file + changes. But this would introduce undefined behavior if the old script's state doesn't match what the + new script is expecting (i.e. a struct definition changed). To resolve this, we will require that + scripts not store any state. Instead, the memory of the script will be cleared every frame. Any + information we need to keep will be stored in the engine code. +

+ +

+fn run(state: ScriptState) {
+	let mut velocity: i32 = state.get("player_velocity").parse();
+	velocity += 1;
+	state.store("player_velocity", velocity);
+}
+

+ +

+ Now, something magical has just happened. We are clearing all state every single frame. All + heap-allocated memory, as far as this script is concerned, is static. This will be the new + memory-allocation strategy. We can use a bump allocator as the allocator. And that means we won't + need a garbage collector (because we're clearing memory every frame), or a borrow checker + (because all heap memory is static). It wouldn't be too hard to adapt an existing garbage-collected + language to use this strategy, so we could just pick one that can theoretically be compiled to + WebAssembly, and make a compiler that doesn't insert a garbage collector. That could include C#, + Dart, Kotlin, or Swift. But we could also make a custom language suited to this task. This could + make it even faster than Rust, because bump allocators are so fast. +

+ +

+ In fact, I don't think the perfect language for game development exists yet. I want something easy to + embed, like Lua, but statically typed⁶. If we could + block the use of the file system or network, then we could ensure that mods don't contain any + viruses. But the language server would need some way to know what libraries are being imported, and + what they contain. +

+ +

Another useful idea is a property declaration. Here's an analogy:

+ +

+// this is determined at compile-time, and not modifiable at runtime
+const PLAYER_SPEED: usize = 5;
+
+// this can be mutated (not in Rust, but in other languages), but an initial value must be given
+static PLAYER_SPEED: usize = 5;
+
+// this is a value inserted by the game engine
+property PLAYER_SPEED: usize;
+

+ +

+ The engine would need to parse the script to determine what properties exist, give the developer a + slider that they can use to change it, and then insert that value into the script. Technically, this + would probably just be syntactic sugar for calling a function. But you wouldn't have to worry about + typos in the property name. +

+ +

+ I'm sure are other features that I think could be useful as well, but this proves the point that a + language specific to game scripting could be useful. +

+ +

Backend Web

+ +

+ Now you have a video game. Maybe this game has online features. In that case, you'll need a web + server to handle communication between players. Once again, we need to pick a language to write it + in. Let's take a look at the usual suspects. +

+ +

Rust (or Swift)

+ +

+ Rust is great because of the exceptional error handling. If all errors are handled using the + Result type, and errors are sent to the client using the Result type, + then you guarantee no cryptic 500 errors, except in the case of a panic. Swift also has a Result + type, so most of what I say here should apply to Swift as well (although I'm not familiar enough + with Swift to tell you when this advice might not apply). +

+ +

+ A point to Rust specifically is the performance and lack of a garbage collector. In most languages, + when the garbage collector starts, the entire program stops. But Rust doesn't have this problem, so + you can send responses at the speed of the network. Another point to Rust is the fearless + concurrency. No data races ever, and bad race conditions should be rare as well. Multithreading is + important to a server, so this is a good thing to have. The ecosystem is also able to provide things + that no other language can. Serde makes JSON and XML + serialization/deserialization a piece of cake. Take a look at SQLx. + Not only can Rust get rid of memory and race errors, it also gets rid of SQL errors. +

+ +

+ AWS supports Lambda functions written in Rust, and even gives you a discount if you do so, since it + runs faster. If you don't like cold boots, then you can always use an actual server application. + There are a few backend web frameworks written in Rust, such as axum, + which everyone seems to love despite the fact that it isn't finished yet. I use + actix-web. It's slightly faster than axum, and it's both + stable and production-ready. +

+ +

Dart

+ +

+ Let's start with what Dart doesn't have. It doesn't have anything as nice as serde or SQLx because it + doesn't have macros. It also doesn't have a Result type. AWS Lambda support for Dart is + also lacking. So all in all, I recommend Rust over Dart. But I wanted to mention + Dart because of the interesting strategy it uses to avoid data races. +

+ +

+ Dart doesn't allow you to share memory between threads. Each thread is its own Instance + with its own heap. But the Instances can communicate with each other over channels. So + there are no data races, just like Rust. +

+ +

+ Now, Dart does have a garbage collector. It's always going to be slightly slower than Rust under + load. But since all of the threads have a separate heap, the garbage collector does not need to stop + your application from running. It only stops one thread. And the garbage collector can be programmed + to run early if a thread has no tasks waiting for it. So in practice, you might never experience a + GC pause. +

+ +

+ There are a number of Dart backend frameworks. I haven't personally tried any of them, and many of + them are deprecated, but I think it's worth checking out if you really want to avoid garbage + collection. Some of them have built-in ORMs and I've seen at least one with built-in OAuth2. +

+ +

WebAssembly

+ +

+ In case you didn't guess, we're going down the same path I followed in my game development ideas. +

+ +

+ The framework itself should be written in Rust, but we can do better for the route code. I really + like the idea of serverless, but cold starts are a problem for me. But take a look at Fermyon's + spin. It uses WebAssembly to get the best of both worlds. + Just like serverless functions, they don't need to be loaded up all of the time. But because + WebAssembly is already heavily sandboxed, they don't need to create a virtual machine to contain your + code. Which makes the cold starts fast. So fast that they've decided to just cold start every single + time. With the help of WASI, Spin can support other languages, such as Go, Python, JavaScript, C#, + and Ruby. +

+ +

+ So you might see where this is going. Again, we can use a bump allocator to avoid garbage collection + and borrow checking. I think spin uses a custom implementation of WASI in order to keep everything + sandboxed, so we could do that too. But, again, custom compilers would be needed, so we could forego + WASI and use a more stable interface that we invent. +

+ +

+ I also think that a new language to support this system could be helpful. We'll need Rust macros, + Rust enums, and a Result type. Although, the macros would probably be implemented in the + embedding, in order to make it more powerful. We'll also want a multithreading system similar to the + one in Dart. Of course this new language would need async/await. Ideally, it would also have a core + library separate from the main one. Ideally, it would also be impossible to panic, but that seems + impossible. +

+ +

+ There's something else we can do now that we're running everything inside of a WebAssembly framework. + Spin provides its own key/value store. The neat thing about this is that we don't necessarily need a + network request to access this store. It's stored locally on the machine. So we can do fast DB access + by creating our own database, and embedding it directly into the framework. I think Spin had this + idea with the built-in SQLite database, but + + SQLite doesn't work well in some cases + . + The key/value store Spin provides is also limited to about 1000 tuples, if I understand correctly. + So I would prefer something with a built-in wide column DB, that doesn't require a network connection + to access. Maybe also a relational database, but those are harder to create from scratch (speaking + from experience). +

+ +

+ I'm not actually convinced that WebAssembly is the best possible thing here either. WebAssembly is a + stack-based bytecode, which is typically slower than one based on registers. This is a good idea for + WebAssembly, because it's on the web, and stack-based bytecode is much smaller than register-based. + So you'll be able to download the code more quickly. But a server doesn't have this requirement. The + bytecode will need to be uploaded to the server, but the size doesn't matter too much after that. So + I could imagine a new bytecode being invented here that takes advantage of registers. It could even + be AOT-compiled once it reaches the server. The same idea applies to games as well. The only benefit + to a smaller bytecode would be a smaller download size, but performance is probably more important + there. +

+ +

Frontend Web

+ +

+ Any language you choose here is going to either compile into JavaScript or WebAssembly. WebAssembly + can be a problem for many languages, since you need glue code to make the language's runtime work + in a browser, which is often the same size as a JavaScript framework. If there were a language that + had a runtime more directly based on JavaScript, designed specifically for frontend WebAssembly, that + could work⁷. But until that happens, I'm going to + recommend avoiding this approach. +

+ +

+ That leaves your options to JavaScript, and languages that compile to JavaScript. This shouldn't be + a surprise to anyone, but TypeScript is your best bet here. I don't think it's + perfect. It takes some of the flaws of JavaScript for itself. But it does make many of them more + bearable. It doesn't cause the JavaScript to get much larger. You get built in lowering to older + versions of JavaScript. And you inherit the whole JavaScript ecosystem. +

+ +

+ Alright, here's the part where I propose a better language. First of all, we shouldn't be inheriting + JavaScript's syntax. If we have to compile to JavaScript from another language, why not compile from + a good one? So things like === don't need to be there. We should also get rid of + undefined. +

+ +

+ Now, one problem I've noticed in most JavaScript frameworks is the difficulty in figuring out which + variables have been updated. Svelte tried to solve this by using the equal sign as a marker that a + variable needs to be updated. But what if I use array.push(5)? Now I need to enter a + hacky array = array to make the change visible. So we'll want some way of detecting + which methods mutate a value. +

+ +

+ Rust, as you may know, has that. Methods that mutate the value take &mut self. How would + we implement this system in Rust? +

+ +

+struct Signal<T> {
+	value: T,
+}
+
+struct SignalGuard<'a, T> {
+	signal: &'a mut Signal<T>,
+}
+
+impl<'a, T> Drop for SignalGuard<'a, T> {
+	fn drop(&mut self) {
+		mark_as_updated(self.signal);
+	}
+}
+

+ +

+ We won't be able to replicate this in TypeScript because TypeScript doesn't have a borrow checker, + and thus cannot detect when a value needs to be dropped. That's the problem that the garbage + collector is meant to solve. So how about we add a borrow checker to TypeScript? +

+ +

+ Yes, I'm actually proposing taking a language which does not have or need a borrow checker, and + adding a borrow checker to it. The borrow checker just makes so many problems easier. For instance, + we said that we needed a language that compiles to WebAssembly but is more closely related to + JavaScript. If we have a borrow checker, and plan the language properly, this language could even + compile to WebAssembly, making it faster than JavaScript. +

+ +

+ I've been working on a web framework for a bit now, and I think this would be a useful feature. I + think I'll try it someday. +

+ +

Conclusion

+ +

+ I didn't mention desktop or mobile apps, but the answer there would be incredibly simple: Dart. Dart + was designed with that specifically in mind, and went through extensive user testing to ensure that + it could be useful for that task. I wouldn't even have any suggestions for what to add to it + (other than Rust enums and macros). Other languages try to have more general purposes, but if a + language is built with a specific goal in mind, it will be good for that task. Python was designed + with scripts in mind, and I recommended it, even though I hate dynamically typed languages. Rust was + designed as a competitor to C++, and it does indeed replace C++ in many use-cases. Icon is a language + that barely exists, and yet I still gave it a shoutout in the parser section. +

+ +

+ The idea of languages being tools is a good one. But I don't think enough thought goes into it. Make + a language with a task in mind. It will be a great one. +

+ +

+ + + + diff --git a/src/blog/color-spaces.kuht b/src/blog/color-spaces.kuht new file mode 100644 index 0000000..ee668b5 --- /dev/null +++ b/src/blog/color-spaces.kuht @@ -0,0 +1,130 @@ + + + + Color Spaces + + + + +

Color Spaces

+ +

+ Colors are more interesting than you might think. I want to share a bit of + information on colors so that you can pick better ones. +

+ +

RGB

+ +

+ Most programmers should already be familiar with RGB. When you have a hex code + like #e395fa, that's an RGB value. Displays are made of pixels + which can simultaneously display red, green, and blue lights. The hex code + tells us how much of each color to use, using a two-digit hexadecimal number. + This format is common because it maps directly to what is displayed on the + screen, so most other color spaces need to be converted to RGB eventually. +

+ +

HSL

+ +

+ RGB, despite its necessity, is pretty hard to intuitively understand. I gave + the example of #e395fa earlier, but it's difficult to imagine what that color + actually looks like (it's lavender-ish). HSL is a 1-1 mapping of RGB, meaning + that each HSL value maps to a different RGB value. And it's in a form that is + pretty intutive. H stands for hue, and is measured in degrees. It points to a + specific color on the color wheel. 0° is red, 180° is turquoise, 270° is + purple, and so on. S stands for saturation, which refers to the strength of the + color. Lower saturations mean that the color will be less colorful, and look + more gray-ish. L stands for lightness. Whiter colors will have higher + lightness, and blacker colors will have lower lightness. +

+ +

LAB

+ +The problem with HSL is that is is not perceptually uniform. According to HSL, all of these colors are the same lightness. + + The HSL color space at 60% lightness. Some parts are clearly lighter than others

The HSL color space at 60% lightness. Some parts are clearly lighter than others

+ +

+ LAB, otherwise known as CIELAB, was designed by the International Commission + of Illumination to be more perceptually uniform. L, once again, stands for + lightness, and is on a scale of zero to one. A and B don't stand for anything, + don't have any bounds, and can in fact be negative. A is the spectrum between + red and green, and B is the spectrum between blue and yellow. +

+ +

+ LAB still isn't perfect. The most notable problem is known as hue shift. As the + color gets lighter, the color starts somehow shifting towards purple. +

+ +

Demonstration of the hue shift described above

+ +

+ But all is saved, because one day Björn Ottosson said, "let there be OKLAB". + OKLAB was first described in a blog post he made. It's called OKLAB, because + he thought it was just okay¹. + Clearly he was wrong, because it didn't take long for OKLAB to become widely + available in Photoshop, web browsers, and game engines. It's not perfect, and + it's not even always better than CIELAB², + but it's good enough to beat everything else that's out there. +

+ +

OKLCH

+ +

+ I don't think you need me to tell you that LAB is hard to visualize. Just guess + what oklab(0.78 0.12 -0.11) is. So, OKLCH came in. It's very + similar to HSL. H and L still stand for hue and lightness, respectively. C + stands for chroma, which is technically different from saturation, but similar + enough that I just think of them as the same thing. +

+ +

+ One big difference between OKLCH and HSL is that OKLCH doesn't recognize every + color as being valid. Some colors are simply impossible. Try imagining a green + that's as dark as black, but still clearly green. And there are colors which + exist but cannot be displayed by your monitor, like the brightness of the sun. + OKLCH doesn't attempt to represent them. You can clamp them down to a color + from the sRGB color space if you wish, but there are colors in OKLCH that + cannot be displayed by your monitor, or any monitor for that matter. +

+ +

+ I think it's better this way. Some designers may decide to clamp the color into + sRGB anyway, but it's good to at least know that the selected color value + doesn't quite match reality. And on the bright side, it might become slightly + easier to support HDR displays. +

+ +

+ If you want to play around with OKLCH, there's a convenient URL for + oklch.com. I recommend giving it a try, + and thinking about it the next time you need a set of colors for your project. +

+ +

+ + + + + Comments at the End + + + + + +

+ +

Comments at the End

+ +

+ I'm about to say something which many of you will find comically stupid. I imagine a reaction of both + cringe and shock. Worse, I don't think my rationale is convincing on its own. But I want you to hear + me out, give it a try one day, and maybe I will convince you. If you go through this process and are + not convinced of the benefits, that's fine. As long as you consider it, I will be happy. +

+ +

+ This year, I made a new year's resolution: don't write comments until the end, preferably right + before you make the pull request. It's fine to make todo comments, and if you think you might forget + to document something later, it's okay to write it immediately. But at the end, you should go through + your code and write comments. +

+ +

+ As is typically recommended, your comments should not explain what your code does. Your code should + explain what your code does. Instead, the comments should explain why you did what you did, and why + you did it in that particular way. Basically, imagine you're showing a co-worker your code, and + explaining what you did. Your comments should reflect everything that you would normally say. Code + that is very simple won't need comments at all. More complicated logic will. +

+ +

+ The first benefit to this is that you will be in "writing mode" instead of "coding mode". You'll + discover many points where you need a comment, that you never thought about before. Your comments + will also be very in-depth. I said before that comments should reflect what you would tell someone + when explaining your code. If your comments are this detailed, then you'll never have to explain + anything. This might not work very well if you hate writing. I obviously enjoy it (when I'm not + being graded). I don't know if this benefit will be as big for others. +

+ +

+ The bigger benefit, in my opinion, is that it might give you an opportunity to improve your code. I + have another rule, which says, "no apology comments". If you find yourself saying, "Sorry for not + making this better", then you should just fix the problem. Note that you are allowed to say "I didn't + do it this different way because that would be worse". If your solution is the best solution you can + think of, then you should use that solution. But when there's a better alternative, you + should choose the better alternative. As I'm writing comments, I often catch myself in the middle of + writing an apology comment. Then I go fix the problem. That means the commenting phase of my code is + also a minor refactoring phase. +

+ +

+ One person has criticized my commenting style, saying that it takes too long to read, and should be + more concise. I think there is a middle ground here, that I haven't achieved yet. In the future, I + might try doing a second pass over my comments to shorten them if I can. I'll just have to hope that + over time, I learn how to make my comments concise from the start. This person has also recommended + that I read Steven Pinker's The Sense of Style. I have a copy of it, but unfortunately I + enjoy writing more than I enjoy reading. +

+ +

+ I'm sure some people are still unconvinced, which is reasonable. So I'll provide, below, a sample of + code where I did this by accident, which convinced me to turn this into a habit. If you like what you + see, then I suggest you give my idea a try. This is a C library that allows the + CheckerBoard UI to use my + Ampere Checkers AI. +

+ +

+// File: ampere_cb.c
+// Description: Provides a bridge between Ampere and CheckerBoard
+// Author: Mica White (they/them) <botahamec@outlook.com>
+// License: CC0 1.0
+
+// -------------------------- IMPORTS ------------------------------------
+
+#include <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <windows.h>
+
+#include "ampere.h"
+#include "cb_interface.h"
+
+
+// --------------------------- MACROS -------------------------------------
+
+// The engine should never search to a depth greater than 40
+// This number is somewhat arbitrary. I just doubled the length of the
+// shortest possible checkers game
+#define MAX_DEPTH 40
+#define MEGABYTE (1024*1024)
+// I don't think anybody will ever miss a single megabyte of RAM.
+// For computers more powerful than a Raspberry Pi Zero, I recommend
+// increasing this to eight megabytes.
+#define DEFAULT_HASH_SIZE MEGABYTE
+
+// These are the lengths of buffers which are given to us by CheckerBoard
+#define INFO_STR_LEN 255
+#define COMMAND_LEN 256
+#define CMD_REPLY_LEN 256
+#define NAME_LEN 250
+
+// I'm not actually sure when I should start calling this 0.2
+// I'm still planning on making breaking changes, so I won't call it 1.0
+#define ENGINE_NAME "Ampere 0.1"
+#define ENGINE_ABOUT \
+"\
+Ampere version 0.1\n\
+A fast and smart Checkers engine\n\
+Implements: transposition table, aspiration windows, iterative deepening\n\
+Defecits: simple evaluation function, no quiescence search\n\
+Copyright Mica White\n\
+"
+
+
+// -------------------------- STATICS ------------------------------------
+
+/// The engine itself
+// I ended up leaking this. I don't think it'll ever be possible for two
+// threads to access the transposition table at the same time, but it's
+// probably better safe than sorry. I don't actually know when this would
+// be collected anyway.
+ampere_engine_t ampere_engine = NULL;
+/// A collection of C functions which the engine may call
+// This needs to be static because it must outlive `ampere_engine`
+struct frontend frontend;
+/// The size to set the transposition table to. This can only be modified
+/// before the engine is constructed, not after.
+int hash_size = DEFAULT_HASH_SIZE;
+/// This is a buffer that CheckerBoard provides to display to the user.
+// This is static because it needs to be accessed by the `give_info` function.
+char* info_str;
+
+
+// --------------------- FRONTEND CALLBACKS -------------------------------
+// These are functions which are passed into the engine on certain events,
+// such as logging debug information, displaying evaluation progress, and
+// determining the best move. The only useful one for our purpose is
+// the `give_info` function, which is called occasionally by the engine
+// during its evaluation to give progress reports.
+
+/// The name says it all
+// This is used for both `debug` and `best_move`. We don't do anything
+// with debug information because CheckerBoard gives us no way to
+// display it. We don't need to do anything with `best_move` because
+// our evaluation runs synchronously, and the evaluation function already
+// returns the best move.
+void do_nothing(void* x) {}
+
+/// Displays information about the in-progress evaluation to the user
+void give_info(ampere_evalinfo_t info) {
+	char move_str[6] = "None"; // If no move was found, default to "None"
+	ampere_move_t move = ampere_evalinfo_bestmove(info);
+	if (move != NULL) {
+		ampere_move_string(move, move_str);
+	}
+
+	float eval = ampere_eval_tofloat(ampere_evalinfo_evaluation(info));
+	int depth = ampere_evalinfo_depth(info);
+	unsigned long long int nodes_per_sec = ampere_evalinfo_nodespersec(info);
+
+	sprintf_s(
+		info_str, INFO_STR_LEN,
+		"Move: %s; Eval: %f; Depth: %d; NPS: %llu",
+		move_str, eval, depth, nodes_per_sec
+	);
+}
+
+
+// ---------------------- HELPER FUNCTIONS --------------------------------
+
+/// Converts a CheckerBoard piece to an Ampere piece.
+/// This results in undefined behavior for: null pointers,
+/// `i` or `j` >= 8, or `index` >= 32,
+void square_convert(
+	Board8x8 board,
+	int i,
+	int j,
+	uint32_t* pieces,
+	uint32_t* colors,
+	uint32_t* kings,
+	int index
+) {
+	int value = board[i][j];
+	uint32_t piece_mask = 1 << index;
+
+	if (value == CB_FREE) {
+		return;
+	}
+	else {
+		*pieces |= piece_mask;
+	}
+
+	if (value & CB_BLACK) {
+		*colors |= piece_mask;
+	}
+
+	if (value & CB_KING) {
+		*kings |= piece_mask;
+	}
+}
+
+/// Converts an Ampere piece to a CheckerBoard piece.
+/// This results in undefined behavior for a null board or `index` >= 32
+int get_cb_piece(ampere_board_t amp_board, int index) {
+	int piece = 0;
+
+	if (!ampere_board_has_piece_at(amp_board, index)) {
+		return CB_FREE;
+	}
+
+	if (ampere_board_color_at(amp_board, index) == DARK) {
+		piece |= CB_BLACK;
+	}
+	else {
+		piece |= CB_WHITE;
+	}
+
+	if (ampere_board_king_at(amp_board, index)) {
+		piece |= CB_KING;
+	}
+	else {
+		piece |= CB_MAN;
+	}
+
+	return piece;
+}
+
+/// Converts an ampere square index to a CheckerBoard square coordinate.
+/// This is undefined behavior for `amp_square` >= 32
+struct coor get_cb_square(int amp_square) {
+	struct coor coordinates;
+
+	switch (amp_square) {
+	case 0:
+	case 6:
+	case 12:
+	case 18:
+		coordinates.y = 0;
+		break;
+	case 1:
+	case 7:
+	case 13:
+	case 19:
+		coordinates.y = 1;
+		break;
+	case 8:
+	case 14:
+	case 20:
+	case 26:
+		coordinates.y = 2;
+		break;
+	case 9:
+	case 15:
+	case 21:
+	case 27:
+		coordinates.y = 3;
+		break;
+	case 16:
+	case 22:
+	case 28:
+	case 2:
+		coordinates.y = 4;
+		break;
+	case 17:
+	case 23:
+	case 29:
+	case 3:
+		coordinates.y = 5;
+		break;
+	case 24:
+	case 30:
+	case 4:
+	case 10:
+		coordinates.y = 6;
+		break;
+	case 25:
+	case 31:
+	case 5:
+	case 11:
+		coordinates.y = 7;
+		break;
+	default:
+		// this is undefined behavior
+		break;
+	}
+
+	switch (amp_square) {
+	case 18:
+	case 26:
+	case 2:
+	case 10:
+		coordinates.x = 0;
+		break;
+	case 19:
+	case 27:
+	case 3:
+	case 11:
+		coordinates.x = 1;
+		break;
+	case 12:
+	case 20:
+	case 28:
+	case 4:
+		coordinates.x = 2;
+		break;
+	case 13:
+	case 21:
+	case 29:
+	case 5:
+		coordinates.x = 3;
+		break;
+	case 6:
+	case 14:
+	case 22:
+	case 30:
+		coordinates.x = 4;
+		break;
+	case 7:
+	case 15:
+	case 23:
+	case 31:
+		coordinates.x = 5;
+		break;
+	case 0:
+	case 8:
+	case 16:
+	case 24:
+		coordinates.x = 6;
+		break;
+	case 1:
+	case 9:
+	case 17:
+	case 25:
+		coordinates.x = 7;
+		break;
+	default:
+		// this is undefined behavior
+		break;
+	}
+
+	return coordinates;
+}
+
+/// Converts a CheckerBoard board to an Ampere board.
+/// This is undefined behavior for a null `board`, or invalid `turn`.
+/// It is the caller's responsibility to free the return value using the
+/// `ampere_board_destroy` function. Otherwise this results in a memory leak.
+ampere_board_t cb_board_to_ampere_board(Board8x8 board, int turn) {
+	uint32_t pieces = 0l;
+	uint32_t colors = 0l;
+	uint32_t kings = 0l;
+	enum color ampere_turn = DARK;
+
+	square_convert(board, 0, 0, &pieces, &colors, &kings, 18);
+	square_convert(board, 2, 0, &pieces, &colors, &kings, 12);
+	square_convert(board, 4, 0, &pieces, &colors, &kings, 6);
+	square_convert(board, 6, 0, &pieces, &colors, &kings, 0);
+	square_convert(board, 1, 1, &pieces, &colors, &kings, 19);
+	square_convert(board, 3, 1, &pieces, &colors, &kings, 13);
+	square_convert(board, 5, 1, &pieces, &colors, &kings, 7);
+	square_convert(board, 7, 1, &pieces, &colors, &kings, 1);
+	square_convert(board, 0, 2, &pieces, &colors, &kings, 26);
+	square_convert(board, 2, 2, &pieces, &colors, &kings, 20);
+	square_convert(board, 4, 2, &pieces, &colors, &kings, 14);
+	square_convert(board, 6, 2, &pieces, &colors, &kings, 8);
+	square_convert(board, 1, 3, &pieces, &colors, &kings, 27);
+	square_convert(board, 3, 3, &pieces, &colors, &kings, 21);
+	square_convert(board, 5, 3, &pieces, &colors, &kings, 15);
+	square_convert(board, 7, 3, &pieces, &colors, &kings, 9);
+	square_convert(board, 0, 4, &pieces, &colors, &kings, 2);
+	square_convert(board, 2, 4, &pieces, &colors, &kings, 28);
+	square_convert(board, 4, 4, &pieces, &colors, &kings, 22);
+	square_convert(board, 6, 4, &pieces, &colors, &kings, 16);
+	square_convert(board, 1, 5, &pieces, &colors, &kings, 3);
+	square_convert(board, 3, 5, &pieces, &colors, &kings, 29);
+	square_convert(board, 5, 5, &pieces, &colors, &kings, 23);
+	square_convert(board, 7, 5, &pieces, &colors, &kings, 17);
+	square_convert(board, 0, 6, &pieces, &colors, &kings, 10);
+	square_convert(board, 2, 6, &pieces, &colors, &kings, 4);
+	square_convert(board, 4, 6, &pieces, &colors, &kings, 30);
+	square_convert(board, 6, 6, &pieces, &colors, &kings, 24);
+	square_convert(board, 1, 7, &pieces, &colors, &kings, 11);
+	square_convert(board, 3, 7, &pieces, &colors, &kings, 5);
+	square_convert(board, 5, 7, &pieces, &colors, &kings, 31);
+	square_convert(board, 7, 7, &pieces, &colors, &kings, 25);
+
+	if (turn == CB_WHITE) {
+		ampere_turn = LIGHT;
+	}
+
+	return ampere_board_new(pieces, colors, kings, ampere_turn);
+}
+
+/// Converts an Ampere board to a CheckerBoard board.
+/// This is undefined behavior if `dest` or `src` are null.
+void set_cb_board(Board8x8 dest, ampere_board_t src) {
+	dest[0][0] = get_cb_piece(src, 18);
+	dest[2][0] = get_cb_piece(src, 12);
+	dest[4][0] = get_cb_piece(src, 6);
+	dest[6][0] = get_cb_piece(src, 0);
+	dest[1][1] = get_cb_piece(src, 19);
+	dest[3][1] = get_cb_piece(src, 13);
+	dest[5][1] = get_cb_piece(src, 7);
+	dest[7][1] = get_cb_piece(src, 1);
+	dest[0][2] = get_cb_piece(src, 26);
+	dest[2][2] = get_cb_piece(src, 20);
+	dest[4][2] = get_cb_piece(src, 14);
+	dest[6][2] = get_cb_piece(src, 8);
+	dest[1][3] = get_cb_piece(src, 27);
+	dest[3][3] = get_cb_piece(src, 21);
+	dest[5][3] = get_cb_piece(src, 15);
+	dest[7][3] = get_cb_piece(src, 9);
+	dest[0][4] = get_cb_piece(src, 2);
+	dest[2][4] = get_cb_piece(src, 28);
+	dest[4][4] = get_cb_piece(src, 22);
+	dest[6][4] = get_cb_piece(src, 16);
+	dest[1][5] = get_cb_piece(src, 3);
+	dest[3][5] = get_cb_piece(src, 29);
+	dest[5][5] = get_cb_piece(src, 23);
+	dest[7][5] = get_cb_piece(src, 17);
+	dest[0][6] = get_cb_piece(src, 10);
+	dest[2][6] = get_cb_piece(src, 4);
+	dest[4][6] = get_cb_piece(src, 30);
+	dest[6][6] = get_cb_piece(src, 24);
+	dest[1][7] = get_cb_piece(src, 11);
+	dest[3][7] = get_cb_piece(src, 5);
+	dest[5][7] = get_cb_piece(src, 31);
+	dest[7][7] = get_cb_piece(src, 25);
+}
+
+
+// --------------------- LIBRARY FUNCTIONS -------------------------------
+
+/// Returns the name of the engine
+// This shouldn't be necessary since we also implemented the "name" command,
+// but this function is very easy to implement, so why not just do it?
+int enginename(char reply[NAME_LEN]) {
+	sprintf_s(reply, NAME_LEN, ENGINE_NAME);
+	return 1;
+}
+
+/// Responds to an engine command. The following commands are implemented:
+/// * name
+/// * about
+/// * help
+/// * set hashsize (only valid before getmove is called)
+/// * get hashsize
+/// * get protocolversion
+/// * get gametype
+int enginecommand(char str[COMMAND_LEN], char reply[CMD_REPLY_LEN]) {
+	// answers to the command sent by CheckerBoard.
+	char command[COMMAND_LEN] = "", param1[COMMAND_LEN] = "", param2[COMMAND_LEN] = "";
+	sscanf_s(str, "%s %s %s", command, COMMAND_LEN, param1, COMMAND_LEN, param2, COMMAND_LEN);
+
+	//by default, return "I don't understand this"
+	sprintf_s(reply, CMD_REPLY_LEN, "?");
+
+	if (strncmp(command, "name", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, ENGINE_NAME);
+		return 1;
+	}
+
+	if (strncmp(command, "about", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, ENGINE_ABOUT);
+		return 1;
+	}
+
+	if (strncmp(command, "help", COMMAND_LEN) == 0) {
+		sprintf_s(reply, CMD_REPLY_LEN, "amperehelp.html");
+		return 1;
+	}
+
+	if (strncmp(command, "set", COMMAND_LEN) == 0) {
+		if (strncmp(param1, "hashsize", COMMAND_LEN) == 0) {
+			if (ampere_engine == NULL) {
+				hash_size = strtol(param2, NULL, 10) * MEGABYTE;
+				return 1;
+			}
+			else {
+				// we can't change the size of the transposition table after
+				// the engine is initialized
+				return 0;
+			}
+		}
+
+		if (strncmp(param1, "book", COMMAND_LEN) == 0) {
+			return 0;
+		}
+	}
+
+	if (strncmp(command, "get", COMMAND_LEN) == 0) {
+		if (strncmp(param1, "hashsize", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "%d", hash_size / MEGABYTE);
+			return 1;
+		}
+
+		if (strncmp(param1, "book", COMMAND_LEN) == 0) {
+			// theoretically, the correct value is `CB_BOOK_NONE`, but
+			// CheckerBoard will assume that means:
+			//     "the book hasn't been loaded yet"
+			// when we actually mean:
+			//     "Ampere doesn't support opening books"
+			return 0;
+		}
+
+		if (strncmp(param1, "protocolversion", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "2");
+			return 1;
+		}
+
+		if (strncmp(param1, "gametype", COMMAND_LEN) == 0) {
+			sprintf_s(reply, CMD_REPLY_LEN, "%d", GT_ENGLISH);
+			return 1;
+		}
+	}
+
+	return 0;
+}
+
+/// Asks the engine to make a move
+int WINAPI getmove(
+	Board8x8 board,
+	int color,
+	double maxtime,
+	char str[INFO_STR_LEN],
+	int* playnow,
+	int info,
+	int moreinfo,
+	struct CBmove* move
+) {
+	// this will be modified on every call, just in case CheckerBoard decides
+	// to reallocate it later
+	info_str = str;
+
+	if (ampere_engine == NULL) {
+		// initialize the frontend
+		frontend.debug = (void (*)(char*)) do_nothing;
+		frontend.info = give_info;
+		frontend.report_bestmove = do_nothing;
+
+		// initialize the engine with the frontend and table size
+		ampere_engine = ampere_new_engine(hash_size, &frontend);
+	}
+
+	int current_turn = DARK;
+	if (color == CB_WHITE) {
+		current_turn = LIGHT;
+	}
+
+	// set up Ampere's clock
+	int increment_info = (info >> 2) & 3;
+	ampere_clock_t clock;
+	if (increment_info != 0) {
+		int inc_factor = 1;
+		if (increment_info == 2) {
+			inc_factor = 10;
+		}
+		else if (increment_info == 3) {
+			inc_factor = 100;
+		}
+
+		int time_remaining = ((moreinfo >> 16) & 0xffff) * inc_factor;
+		int increment = (moreinfo & 0xffff) * inc_factor;
+		clock = ampere_clock_incremental(time_remaining, time_remaining, increment, increment, 0, 0);
+	}
+	else {
+		int time = floor(maxtime * 1000.0);
+		clock = ampere_clock_timepermove(time);
+	}
+
+	ampere_board_t amp_board = cb_board_to_ampere_board(board, color);
+	ampere_set_position(ampere_engine, amp_board);  // the board might change between calls
+
+	struct eval_result result = ampere_evaluate(ampere_engine, (bool*)playnow, 0, MAX_DEPTH, clock);
+	ampere_move_t best = result.best_move;
+	ampere_eval_t evaluation = result.evaluation;
+
+	// we calculate the result at the beginning, in case we need to return early
+	int eval = CB_UNKNOWN;
+	if (ampere_eval_is_force_win(evaluation)) {
+		eval = CB_WIN;
+	}
+	else if (ampere_eval_is_force_loss(evaluation)) {
+		eval = CB_LOSS;
+	}
+
+	// the move will be null if there are no legal moves...
+	// which means we lost, ergo we could've returned when we got the eval
+	// i don't really wanna change it now
+	if (best == NULL) {
+		return eval;
+	}
+
+	// I don't think this is actually necessary. CheckerBoard is usually able
+	// to figure this out automatically for American Checkers. I didn't learn
+	// that until after I wrote all this code, so I'll leave it in case it
+	// prevents a bug later.
+	move->jumps = 0;
+	move->from = get_cb_square(ampere_move_start(best));
+	move->oldpiece = get_cb_piece(amp_board, ampere_move_start(best));
+	if (ampere_move_is_jump(best)) {
+		move->del[move->jumps] = get_cb_square(ampere_move_jump_position(best));
+		move->delpiece[move->jumps] = get_cb_piece(amp_board, ampere_move_jump_position(best));
+		move->jumps = 1;
+	}
+
+	// we figure out the new board position, in case we need to double jump
+	ampere_play_move(ampere_engine, best);
+	ampere_board_destroy(amp_board);
+	amp_board = ampere_current_position(ampere_engine);
+
+	// Ampere and CheckerBoard don't align in their definition of a move
+	// In Ampere, a move is a single slide or jump. But in CheckerBoard,
+	// double jumps are considered to be one move. This is a very sensible
+	// decision. But Ampere is very fast partially because it can optimize
+	// the move struct down to a single byte. So in order for it to work with
+	// CheckerBoard, we need to go down the line and return any extra jumps
+	while (*ampere_board_turn(amp_board) == current_turn) {
+		move->path[move->jumps] = get_cb_square(ampere_move_end(best));
+
+		// the move should be in the transposition table, so it's ok to set the depth to 1
+		result = ampere_evaluate(ampere_engine, (bool*)playnow, 0, 1, 0);
+		ampere_move_destroy(best);
+		best = result.best_move;
+		if (best == NULL) {
+			return eval;
+		}
+
+		if (ampere_move_is_jump(best)) {
+			move->del[move->jumps] = get_cb_square(ampere_move_jump_position(best));
+			move->delpiece[move->jumps] =
+				get_cb_piece(amp_board, ampere_move_jump_position(best));
+			move->jumps += 1;
+		}
+
+		ampere_play_move(ampere_engine, best);
+		ampere_board_destroy(amp_board);
+		amp_board = ampere_current_position(ampere_engine);
+	}
+
+	move->to = get_cb_square(ampere_move_end(best));
+	move->newpiece = get_cb_piece(amp_board, ampere_move_end(best));
+
+	// this is the part that CheckerBoard actually relies upon to figure out what move was played
+	set_cb_board(board, amp_board);
+
+	ampere_move_destroy(best);
+	ampere_eval_destroy(evaluation);
+	ampere_board_destroy(amp_board);
+	return eval;
+}
+

+ +

+ diff --git a/src/blog/datetime.kuht b/src/blog/datetime.kuht new file mode 100644 index 0000000..38bceff --- /dev/null +++ b/src/blog/datetime.kuht @@ -0,0 +1,518 @@ + + + + Comparing Date Types Across Languages + + + + +

+ +

Comparing Date Types Across Languages

+ +

+Every language uses a different API to represent types. To put it mildly, some +of them are better than others. This post will compare the best and worst APIs, +for both informative and entertainment purposes. +

+ +

C

+ +

+C has multiple ways of representing time, depending on which version you use, +and what operating system you have. I'm not going to bother to look at the +Win32 +or POSIX +APIs. Instead I'll focus on plain, simple <time.h>. +

+ +

+C89 has the `time` function, which returns a +time_t. +The specification doesn't say what the type looks like, but it's usually an +integer counting the number of seconds since the UNIX +epoch¹. +

+ +

+On its own, this isn't very useful. How would you get information like the +current year, or the current hour? Luckily, C also provides the +gmtime +and localtime +functions, which convert the time_t into a +tm. +

+ +

+struct tm {
+	int tm_sec; // seconds after the minute [0, 61?]
+	int tm_min; // minutes after the hour [0, 59]
+	int tm_hour; // hours since midnight [0, 23]
+	int tm_mday; // day of the month [1, 31]
+	int tm_mon; // months since January [0, 11]
+	int tm_year; // years since 1900
+	int tm_wday; // days since Sunday [0, 6]
+	int tm_yday; // days since January 1st [0, 365]
+	// positive is Daylight Savings Time is in effect,
+	// zero if not, negative if unknown
+	int tm_isdst;
+};
+

+ +

+There was a mistake in the initial specification where you were allowed to have +62 seconds in a minute. They remembered that leap +seconds² exist, but forgot +about inclusive ranges. This was fixed in C11. +

+ +

+There's also no way to represent either just the date or just the time. If you +want to do either of those things, you'll either have to set some arbitrary day, +or define your own structure. +

+ +

+There's also no time zone information whatsoever here. There's the two +functions to create a tm for the local timezone and UTC, but it's +impossible to tell, just by looking at this structure, which of the two +functions were used to create it. They did, however, include the Daylight +Savings Time information as a nullable boolean. +

+ +

+Overall, I'm not a big fan of this. +

+ +

JavaScript

+ +

+JavaScript's date-time class is called Date, +despite also holding information about time. It was copied almost directly from +Java's Date +class, which was almost entirely obsoleted by JDK 1.1 with the +Calendar +type, for good reason. +

+ +

+Let's start with the constructor. Here it is, according to MDN: +

+ +

+new Date()
+new Date(value)
+new Date(dateString)
+new Date(dateObject)
+
+new Date(year, monthIndex)
+new Date(year, monthIndex, day)
+new Date(year, monthIndex, day, hours)
+new Date(year, monthIndex, day, hours, minutes)
+new Date(year, monthIndex, day, hours, minutes, seconds)
+new Date(year, monthIndex, day, hours, minutes, seconds, milliseconds)
+
+Date()
+

+ +

+Note that calling `Date()` without the new keyword is equivalent +to new Date().toString(). I wonder how many bugs have been caused +by accidentally passing a string into the constructor instead of a number. +

+ +

+If you pass a year in the range of [0, 99], the year will be +translated into the 20th century. You might think, "Oh, is that because the +Date class doesn't support dates from that long ago?" No. This +class supports flawless millisecond precision between the years from +271,822 BCE to 175,760 CE, but cannot construct an object for 67 CE without a +workaround. +

+ +

+You might also wonder why MDN uses the term, monthIndex instead +of just, you know, month. Well, every other field looks natural. +For example, January 1st uses 1 for the day. But in the case of +month, 1 represents February, and 0 represents +January. So anyone who naively writes the following will have a bug. +

+ +

+`${date.getMonth()}/${day.getDay()}/${day.getFullYear()}`
+

+ +

+And now I've just opened another can of worms. What is that +getFullYear method? JavaScript does have a getYear +method, but it's deprecated. It returns the year, minus 1900. The year 2025 +will be returned as 125. The year 1812 is returned as -88. +

+ +

+You may be wondering if that constructor with the year, month, day, hours, +minutes, seconds and milliseconds has the ability to select a timezone. It does +not. In fact, Date contains no timezone information whatsoever in +the object itself. It will always be local time. If you want UTC, you can use +new Date(Date.UTC(year, monthIndex, day, hours, minutes, seconds, milliseconds)). +

+ +

+Because of all of these problems, many JavaScript users decide to ignore the +built-in Date API entirely, and use a library like +moment, which will usually add at least 18 +KB to your site's download size, which is bigger than +some web frameworks. +

+ +

+More recently, we've been granted the Temporal API, but it's not available in +all browsers yet, and the specification is still a draft. I won't get into the +specifics right now in case some of this information becomes out of date. But +there will probably be multiple classes, including Duration, +Instant, PlainDate, and ZonedDateTime. +These types will support nanosecond precision, and the ZonedDateTime +should support proper timezones like "Asia/Shanghai". +

+ +

C#

+ +

+This is the language that inspired me to write this blog post. +

+ +

+In the first versions of .NET, there were two structures related to date and +time: DateTime, +and DateTimeOffset. +These structures, unlike the ones we've seen so far, are pretty well named. +DateTime includes a date and a time. If you need a timezone, +DateTimeOffset includes the date, time, and timezone offset. More +on that later. +

+ +

+There is also a DayOfWeek enum. Perfect! This is probably the best +way of representing days of the week³. +

+ +

+Let's look at some constructors: +

+ +

+DateTime(int year, int month, int day);
+DateTime(int year, int month, int day, int hour, int minute, int second);
+DateTime(int year, int month, int day, int hour, int minute, int second, int millisecond);
+DateTime(int year, int month, int day, int hour, int minute, int second, int millisecond, DateTimeKind kind);
+

+ +

+Not too bad, but I've omitted some overloads for brevity. Since the language is +statically typed, there's no way to accidentally pass in a string, and there's +no overload for a string. Instead you would use the static method, +DateTime.Parse(string). +

+ +

+Now you might wonder what that +DateTimeKind +is. Remember how I said that you use DateTimeOffset for timezones? +That's not true. DateTime can also use a timezone, but I don't +think anyone uses it this way. Let's look at the DateTimeKind enum. + +

+enum DateTimeKind {
+	Unspecified,
+	Utc,
+	Local
+}
+

+ +

+Hmm. So it can represent timezones, but only the local timezone and UTC. That's +annoying. What if my users are in a different timezone than the server? Tough +luck. +

+ +

+Or no? There's the DateTimeOffset struct. Let's just use that! +Except, as you might have suspected, it is insufficient. The constructors for +DateTimeOffset are similar to the constructors for +DateTime, except for no DateTimeKind, and in their +place is a +TimeSpan +struct. +

+ +

+DateTimeOffset(DateTime dateTime, TimeSpan offset);
+DateTimeOffset(int year, int month, int day, int hours, int minutes, int seconds, TimeSpan offset);
+

+ +

+That TimeSpan doesn't seem like a very good timezone, and indeed +it is not. You can't specify a timezone like "America/New_York". Instead, you +specify `UTC-6`. When New York goes into daylight savings time, then you also +need to update the offset⁴. +

+ +

+Now we're getting back into the problems with JavaScript's Date +class. There's no timezone information whatsoever, and the timezone information +that we can provide is worse than useless. I'm told that most people who have +to work with time in C# use an external library, but this wasn't the case at the +company I worked at. At least in this case, your users aren't forced to +download the library⁵. +

+ +

+You may have noticed that, unlike with DateTime, there's no way to +create a DateTimeOffset without specifying the time. There's also +no way to create a DateTime without specifying a date. You could +argue that this is a good thing, since a date time should include both +a date and a time. But for a long time, there was no +alternative. +

+ +

+You might look through the documentation and get excited, because of the +Date property, which presumably returns a new structure I hadn't +mentioned yet which only contains the date information. Unfortunately, this +property is completely useless. It returns the same DateTime, but +with the time set to midnight. There's also a TimeOfDay property +which returns a TimeSpan representing the time that has elapsed +since midnight. +

+ +

+Fortunately, in .NET 6, we got the +DateOnly +and +TimeOnly +structs. These do exactly what you think they would do. +

+ +

+DateOnly(int year, int month, int day);
+TimeOnly(int hour);
+TimeOnly(int hour, int minute);
+TimeOnly(int hour, int minute, int second);
+TimeOnly(int hour, int minute, int second, int millisecond);
+TimeOnly(int hour, int minute, int second, int millisecond, int microsecond);
+

+ +

+There is a caveat here, though. The DateTime.Date property still +doesn't return a DateOnly. A part of me hoped that after these +types were introduced, a breaking change to the language could be made to +replace the completely useless property. Alas, we are stuck with that. +

+ +

Rust

+ +

+Of course, I have to talk about Rust. What does Rust do? Let's look at the +time module. It includes three types worth caring about: +Duration, +Instant, and +SystemTIme. +The behavior of Duration should be obvious, but you may wonder +what Instant and SystemTime are. Let's start with +SystemTime. +

+ +

+pub struct SystemTime(/* private fields */);
+
+impl SystemTime {
+	const UNIX_EPOCH: SystemTime;
+	
+	fn now() -> SystemTime;
+	fn duration_since(&self, earlier: Self) -> Result<Duration>;
+	fn elapsed() -> Result<Duration>;
+	fn checked_add(&self, duration: Duration) -> Option<Self>;
+	fn checked_sub(&self, duration: Duration) -> Option<Self>;
+}
+

+ +

+And that's it! What? You were expecting more? This is every method implemented +on SystemTime outside of traits. No formatting, no figuring out +the current year, just that. +

+ +

+Ok, surely Instant must be more useful, right? Nope. It's actually +the same as SystemTime, except it is monotonically +increasing⁶. What is this? +

+ +

+The Rust standard library is small, on purpose. They don't include features +unless the developers are confident in both the API and its utility. The other +languages in this post should make it obvious that this is a difficult feature +to make a good API for. So it's better to not include dates and times in the +standard library, and just let external libraries handle that. +

+ +

+On the other hand, many low-level system APIs do require some time information. +For example, the Metadata struct contains the time when a file was +last modified. So, there needs to be an Instant struct, but it is +very small, and mostly just a wrapper around the values used by the system +calls. +

+ +

+That being said, I do want to talk about a Rust library that I personally like. +My favorite is chrono. +I mostly just want to talk about the +DateTime +type. Needless to say, it has much more functionality than the +SystemTime type, so I won't go over all of it. But I do want to +show the declaration. +

+ +

+struct DateTime<Tz: TimeZone> {
+	datetime: NaiveDateTime,
+	offset: Tz::Offset.
+}
+

+ +

+That's different. You might correctly guess that +NaiveDateTime +is just a date and a time with no timezone information. But what's that +TimeZone trait? +

+ +

+trait TimeZone: Sized + Clone {
+	type Offset: Offset;
+	
+	fn from_offset(offset: &Self::Offset) -> Self;
+	fn offset_from_local_date(&self, local: &NaiveDate) -> MappedLocalTime<Self::Offset>;
+	fn offset_from_local_datetime(&self, local: &NaiveDateTime) -> MappedLocalTime<Self::Offset>;
+	fn offset_from_utc_date(&self, utc: &NaiveDate) -> Self::Offset;
+	fn offset_from_utc_datetime(&self, utc: &NaiveDateTime) -> Self::Offset;
+}
+
+trait Offset: Sized + Clone + Debug {
+	fn fix(&self) -> FixedOffset;
+}
+
+enum MappedLocalTime<T> {
+	Single(T),
+	Ambiguous(T, T),
+	None,
+}
+

+ +

+This is far more complex than the timezone representation in C#. We do see the +Offset +trait in there, but there's more to it than that. The TimeZone +trait includes several methods for getting the offset from UTC for a given date +and time. So, we can have different offsets at different dates. Finally, we can +transparently handle daylight savings time for timezones other than the local +timezone! And since the timezone is a generic type, we can easily infer from +the types what the timezone is going to be, rather than having to look at how +the object was constructed. +

+ +

+The chrono crate by default includes three timezones: +FixedOffset, +Local, +and Utc. +This is already as good as what we were provided in C#. But remember that +TimeZone is a trait that we can implement ourselves. I recommend +importing the chrono-tz +crate, which includes every time zone under the sun. There's also a generic +Tz +enum, which can represent any timezone if you need it. The implementors of the +trait need not be empty structs. +

+ +

+This is, by far, the best implementation of a time API I've seen anywhere. I'm +sure there are libraries for other languages which do the same thing, and I +recommend trying them out. +

+ +

+The downside to chrono is that, at time of writing, it's +unmaintained. Hopefully a new maintainer will take it over some day soon. For +now, jiff is the +most popular maintained time crate for Rust. It takes heavy inspiration from +JavaScript's new Temporal API that we talked about earlier. It's no chrono, +but it gets the job done, and they're approaching a 1.0 release. +

+ +

Conclusion

+ +

+My conclusion is my own opinion. You may have one that differs from mine. But +here's what I like to see: +

+ +

Handline of timezones
The timezones cannot be plain offsets from UTC
Even better: have an implementable `TimeZone` interface that records the timezone information in the type
Enums for days of the week and months are great
When passing in numbers as months, use 1 for January
Higher resolution is better

+ +

+Hopefully this will inspire you to either go out and see what other time +libraries are out there, or make one yourself. +

+ +

+ + + + diff --git a/src/blog/how-happylock-works.kuht b/src/blog/how-happylock-works.kuht new file mode 100755 index 0000000..c1cf631 --- /dev/null +++ b/src/blog/how-happylock-works.kuht @@ -0,0 +1,767 @@ + + + + How HappyLock Works + + + + + +

+ +

How HappyLock Works

+ +

+ Recently, I released version 0.3 of my HappyLock crate + on crates.io. In this blog post, I wanted to explain what I changed, and why it works. +

+ +

Background

+ +

+ There are four conditions necessary for a deadlock to occur. You only need to prevent one of them + in order to prevent all deadlocks: +

+ +

Mutual exclusion
Non-preemptive allocation
Circular wait
Partial allocation

+ +

Let's go through each one, and see what we can do.

+ +

Mutual exclusion

+ +

+ This doesn't make all that much sense to prevent. We could provide some sort of + Readonly<T> type, but Rust already has &T and + Arc<T>. So this wouldn't be very useful. +

+ +

Non-preemptive allocation

+ +

+ Preventing this would mean that the language can decide to take away your access to a piece of + data at any time. Not only would this be incredibly difficult to pull off, it would also just + annoying for the programmer to deal with. Something like this would need to happen: +

+ +

+let mutex = Mutex::new(5);
+let mut_ref = &mutex;
+let th = thread::spawn(|| {
+	let number = mut_ref.lock();
+	*number = 6;
+});
+
+let number = mut_ref.lock();
+th.join(); // preempts the lock on mut_ref
+println!("{}", number); // oops, we can't use number anymore
+

+ +

+ We could have some sort of LockCell type, which releases the lock immediately after + performing some action, but there are often times where you need to make sure nothing else can + mutate the value for a section of code. So this won't always work. +

+ +

Circular wait

+ +

+ From what I can tell, most attempts to prevent deadlock go through this route. The idea is what + every lock must be acquired in the same order. So if you lock l1 and then + l2 on one thread, then you can't do it in the opposite order on the other thread. + This is an interesting approach, but there's no way to enforce it in the language. Some people + have resorted to using macros for this, such as in the recently published + deadlocker crate (which is a very confusing name). + But an attempt to make this happen at compile-time won't be dynamic enough for the general case. +

+ +

Keep an eye on this one, because we will make use of it later.

+ +

Partial allocation

+ +

+ This is the hero we've been waiting for. To prevent this, we need to enforce total allocation. So if + you want to lock a new mutex, you must first release the locks you've already acquired, and then + acquire a new set of locks. Preventing this is possible in Rust, and less possible in languages that + don't have a borrow checker. Let me explain how we'll use the borrow checker. +

+ +

Exploration

+ +

+ Say we were making mutexes for an operating system. How would we enforce total allocation? We could + simply give an error if someone acquires a new set of locks without releasing the already acquired + locks. It'd also mean we'd have to check for an error every time we acquire a new set of locks. +

+ +

+mutex_t m1 = new_mutex();
+mutex_t m2 = new_mutex();
+
+mutex_t mutices[] = { m1, m2 };
+if (lock_mutexes(mutices, 2)) {
+	// oh noes!
+}
+
+// now we can use the data
+

+ +

But we're not C. We have technology! And our technology is the borrow checker.

+ +

Borrow Checker Rules

+ +

For those of you who don't know, here's a quick rundown of the borrow checker rules:

+ +

A value may not be moved while references to it exist.
Only one mutable reference to a value may exist at a time.
A mutable reference and immutable references, must not exist at the same time.

+ +

As a quick example of these rules:

+ +

+let s = String::new("Hello, world!");
+let r1 = &s;
+let r2 = &s; // this is allowed because these references aren't mutable
+let mr = &mut s; // illegal: rule #3
+drop(s); // also illegal: rule #1
+println!("{r1} {r2}");
+

+ +

A Naive implementation

+ +

+ So here's the plan: We'll make a new type called ThreadKey. This type cannot be + cloned, copied, sent to another thread, or mutably referenced from another thread. The Rust type + system is able to enforce all of those things. +

+ +

+// no traits are derived, especially not Clone or Copy
+pub struct ThreadKey {
+	phantom: PhantomData<*const ()>, // !Send and !Sync
+}
+

+ +

+ Then, we can require that when locking a mutex (or a read-write lock), a ThreadKey, + or a &mut ThreadKey, must be given. +

+ +

+pub fn lock<'s, 'k: 's, Key: Keyable>(&'s self, key: Key) -> MutexGuard<'_, 'k, T, Key, R>
+

+ +

+ Wow! That's a lot of lifetimes and generics. We'll worry about those later. For now, let's show + how this works. +

+ +

+use happylock::{ThreadKey, Mutex};
+
+fn main() {
+	// each thread can only have one thread key
+	// the call to unwrap panics if this thread already got its key
+	// ThreadKey is not Send, Sync, Copy, or Clone
+	let key = ThreadKey::get().unwrap();
+
+	let mutex = Mutex::new(10);
+
+	// locking a mutex requires either the ThreadKey or a &mut ThreadKey
+	let mut guard = mutex.lock(key);
+
+	// we no longer have the thread key, so we can't lock anything else anymore
+
+	println!("{}", *guard);
+}
+

+ +

+ I recently learned that I wasn't the only person who thought of this. Over a year ago, Adrian + Taylor posted on Medium, + + Can the Rust type system prevent deadlocks?. + I was completely unaware of this when I published the crate, despite my search for other + implementations of the idea. He also worked on getting inner mutexes to work, which is currently + impossible in HappyLock. He didn't attempt to do something more obvious though, which is locking + more than one mutex at a time. He also never considered the possibility of using a + & mut MutexPermissionToken to make the code more ergonomic. +

+ +

Speaking of which, how do we lock more than one mutex at a time?

+ +

Lock Collections

+ +

+ It's actually quite simply, we just lock a collection of things. We can have a type, called + LockCollection, which takes a collection of locks, and locks them all at the same time. + Then, it'll return a LockGuard for the collection. +

+ +

+ There are different collections we could try to lock, including Vec<T>, + (A, B), and (Vec<A>, Vec<B>), so this'll have to be generic. To + enable this, we'll create a trait called Lockable. +

+ +

This isn't the current implementation in HappyLock, but here's a proof-of-concept:

+ +

+unsafe trait Lockable {
+	type Guard<'a>;
+
+	unsafe fn lock<'a>(&self) -> Self::Guard<'a>;
+
+	unsafe fn try_lock<'a>(&self) -> Option<Self::Guard<'a>>;
+}
+

+ +

Then, we just need to implement on every collection that could hold a lock.

+ +

+use happylock::{ThreadKey, Mutex, LockCollection};
+
+fn main() {
+	let key = ThreadKey::get().unwrap();
+	let mutex1 = Mutex::new(5);
+	let mutex2 = Mutex::new(String::new());
+	let collection = LockCollection::new((mutex1, mutex2));
+	let guard = collection.lock(key);
+	*guard.1 = format!("{}{}", *guard.1, guard.0);
+	*guard.0 += 1;
+}
+

+ +

That seems to work pretty well.

+ +

Duplicate Locks

+ +

Let's try something:

+ +

+use happylock::{ThreadKey, Mutex, LockCollection};
+
+fn main() {
+	let key = ThreadKey::get().unwrap();
+	let mutex1 = Mutex::new(5);
+	// oh no. this will deadlock us
+	let collection = LockCollection::new((&mutex1, &mutex1));
+	let guard = collection.lock(key);
+}
+

+ +

+ The problem is that we passed the same lock in twice. That'll be a problem if we require it to be + locked twice. The good news is, this code doesn't compile, because LockCollection::new + actually requires a different trait that I haven't mentioned. +

+ +

+// not implemented for &impl Lockable
+// ergo: the values within are guaranteed to be unique
+unsafe trait OwnedLockable: Lockable {}
+

+ +

+ Let me elaborate on this. If the value is owned, then there's no way to pass it twice into the same + collection. The same is true for mutable references. So we can safely lock an owned lock without + checking for duplicates. +

+ +

+ But sometimes, it's useful to lock a referenced mutex. For these, we'll need a runtime check for + duplicates. So we'll need to add another method to our Lockable trait. +

+ +

+unsafe trait Lockable {
+	// ... snip ...
+
+	fn get_ptrs(&self) -> Vec<usize>;
+}
+

+ +

+ Then we can check for duplicate pointers within a collection. My first implementation of that check + was a brute-force O(n²) check. When I posted about this on Reddit, people were quick to point out + that this could be made O(nlogn) by sorting the pointers, then checking if the same pointer appeared + twice in a row. +

+ +

+fn contains_duplicates<L: Lockable>(data: L) -> bool {
+	let mut pointers = data.get_ptrs();
+	pointers.sort_unstable();
+	pointers.windows(2).any(|w| w[0] == w[1])
+}
+

+ +

Of course, you could make this an O(n) check by using a HashSet too.

+ +

Now we need a new constructor for LockCollection.

+ +

+impl<L: Lockable> LockCollection<L> {
+	pub fn try_new(data: L) -> Option<Self> {
+		let ptrs = data.get_ptrs();
+		if contains_duplicates(&ptrs) {
+			return None;
+		}
+
+		Some(Self { data })
+	}
+}
+

+ +

The Actual Implementation

+ +

+ Although we have now successfully prevented deadlocks, + livelocking can still be an issue. +

+ +

+ The first implementation of LockCollection would try to lock everything in order. If + one of the locks blocked, then it would release everything it had and try again. It would keep + retrying until it successfully locked everything in a row. This resulted in a lot of wasted work. It + also made the LockCollection start to resemble a spinlock. This also made the + collection prone to livelocking. +

+ +

+ Imagine this scenario with two threads trying to lock a set of mutexes, but in a different order: +

+ +

Thread 1 locks mutex 1
Thread 2 locks mutex 2
Thread 1 tries to lock mutex 2 and fails
Thread 2 tries to lock mutex 1 and fails
Thread 1 releases mutex 1
Thread 2 releases mutex 2
Repeat

+ +

+ In practice, this loop would probably end eventually, but it'd be nice if we could prevent it + altogether. You could avoid this by locking everything in the same order. But if we could do that, + then we would've prevented cyclic wait from before, which would have avoided this whole problem. +

+ +

Cyclic wait

+ +

+ Remember when I said we would make use of cyclic wait later? This is where we'll do this. If you + recall from earlier, we already sorted the mutex pointers by their memory address. What if we locked + them in that order? This was suggested by many people on Reddit, but it took a while to work out + exactly how to do this. I can't sort a tuple. So we'll need to lock them in a different order than + the one they're returned in. This will require a large change to the existing Lockable + trait. Let's see what we can do. +

+ +

+unsafe trait Lock {
+	unsafe fn lock(&self);
+	unsafe fn try_lock(&self) -> bool;
+	unsafe fn unlock(&self);
+}
+
+unsafe trait Lockable {
+	type Guard<'g>;
+	fn get_locks<'a>(&'a self, &mut Vec<&'a dyn Lock>);
+	unsafe fn guard<'g>(&'g self) -> Self::Guard<'g>;
+}
+

+ +

+ Lock is implemented on Mutex and RwLock. Lockable + is implemented on the same types as before. These traits are even more unsafe than they were before, + now that they can obtain a guard without locking it first. So, we'll just need to be very careful. +

+ +

Now let's try making our new LockCollection

+ +

+struct LockCollection<L> {
+	data: L,
+	locks: Vec<&'self.data dyn Lock>
+	// wait, this is a self-referential struct
+}
+

+ +

+ Ooh, boy. This is gonna be a problem. We could box the data, but sometimes we don't want to pay the + price of memory allocation. We could try using a reference, but then we have an extra lifetime to + deal with. It's also sometimes useful to have an owned lock collection. How are we going to do this + without creating four lock collection types that do mostly the same thing? +

+ +

We'll just create four Lock Collection Types that do mostly the same thing

+ +

+ I'll cover each of the four types, but if you're looking for a sensible default, there's a type alias + so that LockCollection points to BoxedLockCollection. It's slower and + doesn't allow you to mutate the underlying collection (yet), but it works for most use cases. +

+ +

+ I'm pretty sure when this gets posted to Reddit, someone will tell me I could've avoided this + somehow. +

+ +

`RefLockCollection`

+ +

+pub struct RefLockCollection<'a, L> {
+	data: &'a L,
+	locks: Vec<&'a dyn RawLock>,
+}
+

+ +

+ It needs to sort the locks by address. Yes, that applies even if the collection is owned. Otherwise + the locks could be acquired in a different order. We're no longer releasing the locks when we can't + acquire them all at once, so they need to be acquired in exactly that order. But it avoids one memory + allocation. +

+ +

`BoxedLockCollection`

+ +

+pub struct BoxedLockCollection<L> {
+	data: *const UnsafeCell<L>,
+	locks: Vec<&'static dyn RawLock>,
+}
+

+ +

+ This is similar to RefLockCollection, but it allocates more memory. You may notice that + there's no Box in this structure, despite the name. That's because Box + needs to be a unique pointer. But because of the references in locks, it's not unique. + It's const because of the existing references to the collection, meaning mutating the + underlying collection would cause undefined behavior, especially if it means the locks move (such + as when a Vec reallocates). It's a raw pointer, because deallocating the data requires + a mutable pointer, and creating a mutable pointer from an immutable reference is undefined behavior. + The UnsafeCell is used for a similar reason. +

+ +

+ This is actually the reason why this release is titled 0.3 and not 0.2. I released 0.2 and found + these soundness bugs, so I had to make a fix. This was a breaking change, because you can't mutate + the underlying collection anymore. +

+ +

`OwnedLockCollection`

+ +

+pub struct OwnedLockCollection<L> {
+	data: L,
+}
+

+ +

+ Since both RefLockCollection and BoxedLockCollection require sorting the + locks, it'd be nice if we could sometimes avoid that for owned lock collections. If a set of locks is + in an OwnedLockCollection, then it really cannot be used anywhere else. That means as + long as references to a OwnedLockCollection always lock in the same order, then it'll + never deadlock. That's the only order these particular locks can be locked in. So, we don't bother + sorting and just lock them in the order they appear in for the collection. +

+ +

`RetryingLockCollection`

+ +

+ This is the collection that was used in Happylock 0.1. This does the releasing of all of the locks + thing. The upside of this collection is that it can contain references, and still not sort the + pointers. Duplicates are checked for by using a HashSet. Because of the lack of sorting, + it can be fast in the following case, from the docs: +

+ +

+ [...] when the first lock in the collection is always the first in any + collection, and the other locks in the collection are always locked after + that first lock is acquired. This means that as soon as it is locked, there + will be no need to unlock it later on subsequent lock attempts, because + they will always succeed. +

+ +

RwLocks

+ +

+ It doesn't take a genius to realize that my lock collection API is not friendly to read-write locks. + In HappyLock 0.1, I had ReadLock and WriteLock wrappers for + RwLock to allow reads in collections. +

+ +

+struct ReadLock<'a, T(&'a RwLock<T>);
+struct WriteLock<'a, T(&'a RwLock<T>);
+

+ +

+ This worked fine at the time, but I quickly realized that this would not work for an + OwnedLockCollection. To solve this problem, I made more changes to the + Lockable API. +

+ +

+unsafe trait Lock {
+	// ...
+	unsafe fn read(&self);
+	unsafe fn try_read(&self) -> bool;
+	unsafe fn unlock_read(&self);
+}
+
+unsafe trait Lockable {
+	// ...
+	type ReadGuard<'g>;
+	unsafe fn read_guard<'g>(&'g self) -> Self::ReadGuard<'g>
+}
+
+// A NEW TRAIT
+unsafe trait Sharable: Lockable {}
+

+ +

+ The Sharable trait is implemented on collections that only contain readable locks. + All of the lock collection types then have functions for when their locks are all sharable. That + allows us to grant read-access in OwnedLockCollections. +

+ +

After I was done with that, I updated the documentation and published the new version.

+ +

Performance

+ +

+ ThreadKey is a zero-cost abstraction. It takes zero space at runtime. The only code is + checking to see if the key has already been acquired for a thread. That is a static, + lazily-initialized, thread local, boolean check and update, so it's fairly fast. +

+ +

+ I used lock_api as backends for the Mutex and RwLock types. + By default, this library acts as a thin wrapper around parking_lot, so it will be + roughly the same speed as parking_lot. There's an optional feature that can be enabled + to use spin as well, and you can import your own raw locks if you wish. The standard + library locks cannot be used, because it's impossible to implement the lock_api traits + on them. If someone adds a Mutex::force_unlock function to the standard library, then I + can add that support, and I'll even make it the default. For now, we have to deal with the larger + binary size that's given by parking_lot. +

+ +

+ The only place where performance could be an issue is in the lock collection types. The performance + qualities of each type have already been discussed. But to summarize, only the + OwnedLockCollection is zero-cost. Both RefLockCollection and + BoxedLockCollection allocate memory and sort the lock pointers, and sometimes they'll + even need to check for duplicates within the pointers. All of this work is done when the collection + is created though, so at least you don't need to worry about it after that. On the other hand, the + RetryingLockCollection, when locking, will waste time unlocking and relocking unless the + following condition is met: +

+ +

+ [...] when the first lock in the collection is always the first in any collection, and the other + locks in the collection are always locked after that first lock is acquired. +

+ +

RetryingLockCollection also checks for duplicates using a HashSet.

+ +

In summary, it's pretty fast, but choose the correct lock collection constructor carefully.

+ +

Future Work

+ +

+ This is summarized on the GitHub repo, but I'll try to go into more depth on my plans for the future + of this library. +

+ +

Poisoning

+ +

+ Personally, I'm not a big fan of mutex poisoning, but I can see why someone would want to use it. I + plan on adding it to Happylock soon, by having a Poisonable wrapper around + Lock types. And if I implement Lock on the lock collection types, then + it'll even be able to wrap those, which might be useful. +

+ +

OS Locks

+ +

+ I originally thought of this as being a must-have for the next version of HappyLock, but after trying + it for a bit, I decided to hold off on it. As I mentioned before, there is a binary size cost to + using parking_lot. We could save memory by using the locks that are built into the + operating system, which is what the standard library does. It would be very convenient if I could + just use the standard library as a backend for HappyLock. +

+ +

+ Unfortunately, there's a reason why the standard library's locks do not implement + lock_api's traits. There's just no way to unlock one of those mutexes without holding + onto the guard. If we were to put the guard inside of the mutex, and then drop it when unlocking, + that would make it impossible to share the lock across threads, since the guard isn't + Send. +

+ +

+ There are raw mutexes used in the underlying implementation of the standard library, but those aren't + public. I've tried simply copying the part of the standard library that implements those traits, but + it relies on too much of the rest of the standard library. I don't want importing HappyLock to + require recompiling the entire standard library. +

+ +

+ The next feasible solution, in my opinion, would be to make a new crate that uses the operating + system mutexes, and implements lock_api traits on them. I've already started doing this, + and it seems very possible. But don't expect it to properly support every platform that the standard + library supports. +

+ +

Compile-Time Duplicate Checks

+ +

+ The only way to make duplicate checks free is to run them at compile-time. I doubt I'd be able to + implement this using procedural macros (feel free to prove me wrong). But, as + pacak keeps reminding me, it might be possible using const + functions with a Bloom filter. I don't know + if const Rust is robust enough for this to be implemented yet, but I do want to give it a try. It + wouldn't work for lock collections which require sorting, but it might work for + RetryingLockCollection. +

+ +

Expanding Cyclic Wait

+ +

+ One other thing I'd like to explore is if there's anything more that can be done with cyclic wait. + I could imagine LockCollection<Vec<L>> where L: OwnedLockable having some + lock_next method, or maybe an iterator type that would allow you to only lock the first + few items as they are needed, rather than locking the entire collection at once. I'm not sure how + useful this would be though. I'm sure there are other ideas that I'm not thinking of too. +

+ +

A `LockCell` type

+ +

+ If you've seen the Cell type in Rust, then you know that it's a good zero-cost + abstraction that provides safe interior mutability. The downsides are that it cannot be shared + between threads and its limited API. But I think it would be neat to add some of its methods as + convenience methods for Mutex and RwLock, i.e: + Mutex::lock_swap. This would not remove the need for a ThreadKey, since + then you'd be able to call lock_swap on a thread that's already locked the mutex. +

+ +

+ However, if we had methods like Mutex::try_swap, then there'd be no need. The mutex + wouldn't be able to block the current thread, and because the lock is released so quickly, it + wouldn't block any other threads either. No blocking, means no deadlock. I think the same would be + true for try_clone and try_take, but they're scarier since the + Clone and Default traits could try to lock the same mutex, resulting in a + deadlock. I don't know if it would be possible to access the ThreadKey safely in these + methods though. Either way, all of these methods would be fallible, so it's not going to be a + perfect solution. +

+ +

+ But we could introduce a LockCell type, which would be the same as Cell, + but it safely implements Sync by using a mutex or rwlock internally. This would not + require ThreadKey at all, as long as all of the implemented methods don't lock the + LockCell a second time, which is probably impossible. +

+ +

+ It is a little surprising that a type like this doesn't already exist in the standard library. That + might be because it would make race conditions very easy to trigger. Imagine checking to see if two + LockCell values were equal for an if-block, but once you get inside the if-block, + they're no longer equal. I'll have to think more about this. +

+ +

+let a: LockCell<i32>;
+let b: LockCell<i32>;
+
+if a == b {
+	// a and b are no longer equal
+}
+

+ +

Readonly Lock Collections

+ +

+ I originally had a different idea of what to do with the Sharable trait. We could avoid + checking for duplicates in a lock collection if we knew that the only thing we would do with them is + read. At the time, I thought that reading twice on the same thread will never cause a deadlock. + However, that's not true on every platform, because of contention. Luckily, the lock_api + developers thought ahead by designing a RawRwLockRecursive trait, which I can extend by + creating a Recursive subtrait of Lockable. +

+ +

+ That's cool, but I don't really want to add three more lock collection types for this feature. So + maybe this could be a wrapper around the existing lock collection types, i.e. + Readonly<RetryingLockCollection<L>>. I'd need to implement a + LockCollection trait that would have an associated unsafe constructor for creating the + collection without checking for duplicates. Then, creating that retrying lock collection would be + free (but locking it can still sometimes be expensive). +

+ +

+ This doesn't only apply to RwLock. If there was a ReentrantMutex type, then + we could implement Recursive on that, and use that in a readonly lock collection as well. + For those of you who don't know, a ReentrantMutex can be locked several times on the same + thread, but not while it's being locked by a different thread. However, the guard can only access the + data immutably, because multiple mutable references to data on the same thread is still undefined + behavior. It's mostly intended for wrapping Cell or RefCell. Unfortunately, + lock_api doesn't have a trait for recursive mutexes. Instead it provides a struct + wrapper for RawMutex, called RawReentrantMutex. This is despite the fact + that Unix's pthread API already supports recursive mutexes. I might be able to sway the + lock_api developers to support this. +

+ +

No Standard Library

+ +

+ Doing this without the standard library would be very interesting. But currently, the + Lockable interface requires a Vec of pointers, so it might not be feasible. + The thread keys are stored in a thread local storage too, but I'll probably come up with some + UnsafeKey system to deal with that eventually, in order to support async runtimes. +

+ +

Other Types from the Standard Library

+ +

+ It would be fun to add OnceLock or LazyLock, but I don't think it's + necessary. I don't think anybody has ever accidentally deadlocked using those interfaces, if at all. + In the past I've also considered Condvar and Barrier, but that's trickier. + They're kind of the opposite of a mutex, so tricks that work for avoiding deadlocks here won't work + on them. I've also never used either of those types before, so I'm probably not the best person to + figure that out. +

+ +

Conclusion

+ +

+ This has been a very long nerd snipe. But I think this idea could become incredibly useful, which is + why I keep pushing for it. It'd be even better if it was a part of the standard libary to begin with, + but I'm aware that's not possible anymore. +

+ +

+ The fact that this is possible makes me appreciate the borrow checker even more. People often think + of it as a limitation (myself included), but it solves so many problems that I'm surprised more + languages don't adopt it. Not only does it solve memory corruption, but also resource leaks, and now + deadlocks. You spend more time specifying your code, but less time debugging it. +

+ +

+ There's still work that needs to be done (I haven't even begun async runtime support yet), but I hope + that as this library becomes more developed, there will be more projects which are immune this error. +

+ +

+ diff --git a/src/blog/linking.kuht b/src/blog/linking.kuht new file mode 100644 index 0000000..f994765 --- /dev/null +++ b/src/blog/linking.kuht @@ -0,0 +1,245 @@ + + + + What Other Distros Can Learn from NixOS + + + + +

What Other Distros Can Learn from NixOS

+ +

+ As a warning, this blog post contains the ramblings of an Arch user who + barely knows what a flatpak is and has like, three of them on their system. + Their background is in web deployment pipelines and they're trying to apply + their personal beliefs to Linux distributions, like an idiot, without even + making a proof-of-concept. Reader discretion is advised. +

+ +

+ One debate that often comes up is static versus dynamic linking. Most Linux + distributions try to manage dependencies by dynamically linking them. This can + be good, because if a previous version of a library contains a bug, then it's + easy to distribute the bug fix and have it apply to all applications + simultaneously. The downside is that if a newer version of a library contains + a bug, or a backwards-incompatible change, then that will apply to all + installed applications. Dynamic linking is a double-edged sword that makes it + both easier to fix bugs and easier to create new ones. +

+ +

+ But NixOS offers strict control over both the release and use of libraries, + which allows applications to get both the ease of rollout that comes with + dynamic linking, and the control that comes from static linking. +

+ +

Background

+ +

+ When an application is installed on NixOS, it is not put in the + /bin folder. In fact, this folder is almost entirely empty. + Instead, it goes to /nix/store, in a directory with an + unreadable hash. Then, when you boot the system, the files for your system + applications are symlinked into /run/current-system/sw, which is + in the PATH, so these applications can run in your terminal. +

+ +

+ But that's only system applications. For libraries, the application sets its + own LD_LIBRARY_PATH variable. This tells the dynamic linker + where to fetch the required libraries from. This isn't exactly what the file + looks like, but you can imagine it looking something like this: +

+ +

+#!/path/to/bash
+LD_LIBRARY_PATH="$LD_LIBRARY_PATH:/nix/store/naioghuraopjfi4738-libgit2-2.23"
+export LD_LIBRARY_PATH
+exec -a git "$@"
+

+ +

+ The benefit of this system is that you can multiple versions of the same + library installed on your system, and different applications can depend on + different versions, depending on what they need. +

+ +

+ I want to note that there's nothing special about NixOS that would make this + impossible on other systems. Flatpak already allows applications to bundle + their own versions of libraries, and Snap has a similar system. So I think + other distros can still benefit from this system. +

+ +

Testing

+ +

+ Before I go into the benefits of the system described above, I'll touch on + something that distros can do already, but that specifying dependency + versions might make easier. +

+ +

+ Before you can even update the repository, you'll have to test the library. + Hopefully, the maintainer of the library has already done this for you, by + creating a suite of unit tests that they ran before creating the release. I + suppose it wouldn't hurt to double check. +

+ +

+ The more interesting test you'll need to run is similar to what + crater does for the Rust + ecosystem. Whenever a change is made to the language, Rust runs crater to + determine if the change would cause a breaking change for any packages on + crates.io. It's a very brute-force way to test for new bugs. +

+ +

+ In order for this to work, not only does the library need a unit test suite, + but so does every application that depends on that library. You'll build + every single dependent against the newer version of the library, and then + test all of them to see if anything breaks. +

+ +

+ Inevitably, some applications will fail under a new version of a library. + This doesn't necessarily need to be because of a problem in the library + itself, but it could be due to a transient failure in the application. In + such a scenario, the application's dependency would be updated to say + 3.13 instead of 3, so it doesn't block other + applications from using the newer version. +

+ +

+ It would also be beneficial to store somewhere in the package which version + of each dependency an application was last tested with. Then, if you want to + be extra safe, you can delay upgrading the dependency until you know that a + test has been run on the latest dependencies. +

+ +

Beta Channel

+ +

+ The delayed release of packages is what separates Arch Linux from Manajaro. + Some users are more interested in being on the bleeding edge than others. I + don't see any reason why two separate package repositories are needed for + this. We can allow users to opt-in to the bleeding edge for specific packages + faster. These people can submit bug reports before the new features make + their way to regular users. +

+ +

+ NixOS has this in the form of the unstable channel. Users can + opt-in to using the unstable channel to get an experience more similar to a + rolling release distro. And judging from some Reddit threads, there are + people using the unstable channel regularly. This makes sense to me, since + not everyone who uses Nix is there for stability. Some people just like + having a central config file. NixOS also lets people go one step further and + use unstable for specific packages, but leave the rest of their + entire system stable. +

+ +

+ Other distros do have this. Most commonly this comes in the form of an LTS + variant of the distro, which most users are expected to stay on. The non-LTS + variant is often treated as a beta. +

+ +

Rollout

+ +

+ The rest of the ideas presented in this post are ideas that can be done as + long as you have a way to pin dependency versions, but they're not done by + NixOS. How important these are is debatable, since NixOS already tests their + stable channels before releasing them. +

+ +

+ Not every package is of equal importance. A change to a library affecting + pacman is far more critical to a library that only affects GIMP. But thanks + to the system we have here, it doesn't need to affect every package at the + same time. We can rollout a library change to less important packages first + before we apply it to every library. +

+ +

+ To give an example of how this would work, let's say a new library version + releases, and it affects both pacman and GIMP. For this to work, we'd need to + assign a priority level to every package. Pacman would probably be a level 2 + package, meaning it's very important. There should only be a few level 1 + packages. GIMP would be level 4, so not very important. As a level 4 package, + GIMP would be one of the first packages to use the new version of the + library. After a couple days, pacman would also start using the new library. +

+ +

Rollback

+ +

+ So with all that in mind, what happens when a library actually is bad? Well, + marking the library version as bad is luckily pretty simple. We just update + the version resolver to say that if a package asks for version + 3, don't use 3.14. Prefer 3.13 + instead. Pacman already caches older versions of packages, so you might not + even need to re-install 3.13. +

+ +

+ Of course, rolling backwards isn't always safe. Some newer packaages might + already be using features of 3.14 that don't exist in + 3.13. To partially resolve this, we can run the test suite + against each package before downgrading to 3.13. Hopefully + everything will pass, but if a particular package does not, then we can set + that package specifically to require a minimum of 3.14. We can + also mark this downstream package as bad, and prevent new installations of it + until a patch is made. +

+ +

Distribution

+ +

+ There's one thing here that we can't control: the distribution. Meaning, we + don't know when the user is going to run an upgrade. Unlike in Windows land + or web land, we don't run the upgrade automatically. Some systems will at + least automatically check for updates and notify the user when there is one, + but there's usually no distinction between critical bug fixes and feature + updates. +

+ +

+ I would recommend having a daemon that at least automatically downgrades in + the case of bad library versions. Since we can cache older versions of the + library, this wouldn't require too much network activity. And we can always + give the user an option to disable it. +

+ +

+ NixOS actually does support full automatic upgrades in the background. Some + NixOS users report that because NixOS is so stable, they feel comfortable to + just letting everything update in the background without intervention. The + NixOS wiki provides this example on how to do so. +

+ +

+system.autoUpgrade = {
+  enable = true;
+  flags = [
+    "--print-build-logs"
+  ];
+  dates = "02:00";
+  randomizedDelaySec = "45min";
+  allowReboot = false;  # Set to true if you want automatic reboots
+};
+

+ +

Conclusion

+ +

+ I don't want to say none of these solutions come with caveats. NixOS has + trouble running arbitrary executables because of how it goes about + accomplishing its goals. The way things are set up on NixOS can sometimes be + confusing to newcomers, and I understand why a Linux distro wouldn't want to + copy everything from NixOS. But I think even a best-effort attempt at some of + the ideas that NixOS provides could provide major benefits for stability. + It's just about choosing the right compromises. +

diff --git a/src/blog/named-optional-args.kuht b/src/blog/named-optional-args.kuht new file mode 100644 index 0000000..7d36972 --- /dev/null +++ b/src/blog/named-optional-args.kuht @@ -0,0 +1,1701 @@ + + + + Named and Optional Arguments are Awesome + + + + + +

+ +

Named and Optional Arguments are Awesome

+ +

+ Whenever someone asks what my least favorite part of Rust is, my answer is + always the same: it doesn't have named or optional arguments. +

+ +

+ I have a small list of programming languages I tolerate: Rust, C#, TypeScript, + Dart, Python. Of those languages, Rust is the hardest to get named arguments + out of. I'm going to start this post by going over the other languages and how + they've achieved named arguments. Then, we'll look at Rust, the problems that + have resulted from not having named arguments, and proposals for how Rust + could get them in the future. +

+ +

How Other Languages Handle Named Parameters

+ +

Dart

+ +

+ Dart is designed specifically for graphical user interfaces. GUI components + tend to have lots of optional parameters, so Dart tried very hard to get them + right. And I think it does the best job out of any language we're going to + talk about today. +

+ +

+ First, let's look at a normal function, just to familiarize ourselves with the + language: +

+ +

+Widget Text(String text) {
+	// ...
+}
+

+ +

+ That's pretty normal as far as languages go. You can probably guess what it + does, even if you don't know Dart. Dart was basically designed in a lab to be + easy for programmers to learn. +

+ +

+ Now, let's add a named parameter to set the size of the text, and default it to + 16 pixels: +

+ +

+Widget Text(String text, {int fontSize = 16}) { /* ... */ }
+
+// usage:
+Text("Hello, world!", fontSize: 24)
+

+ +

+ Named parameters are wrapped in curly braces. This makes them look similar to + a map. Named parameters can also be defaulted to null, or even required. +

+ +

+Widget Text({
+	int fontSize = 16,
+	Color? color,
+	required String text,
+});
+

+ +

+ Dart also supports optional positional arguments by wrapping the parameter in + square brackets. +

+ +

+// From the Dart documentation
+String say(String from, String msg, [String device = 'carrier pigeon']) {
+  var result = '$from says $msg with a $device';
+  return result;
+}
+
+assert(say('Bob', 'Howdy') == 'Bob says Howdy with a carrier pigeon');
+assert(say('Bob', 'Howdy', 'smoke signal') == 'Bob says Howdy with a smoke signal');
+

+ +

C#

+ +

+ C#'s handling of named parameters is also pretty good. In fact, any parameter can be + named. +

+ +

+void ExampleMethod(string foo, string bar)
+{
+	Console.WriteLine($"{foo} {bar}")
+}
+
+ExampleMethod(bar: "Hello", foo: "world");
+

+ +

+ And any parameter can have a default value, as long as they're specified after + the required parameters. +

+ +

+void ExampleMethod(string foo, string bar = "world")
+{
+	Console.WriteLine($"{foo} {bar}")
+}
+
+ExampleMethod("Howdy");
+

+ +And that's all there is to it. I like the simplicity of it. + +

TypeScript

+ +

+ TypeScript's handling of named parameters is not very good, in my opinion. + But optional positional parameters aren't named, and they work pretty well, so + let's start with that. +

+ +

+function example(required: string, optional?: string = "world"): string {
+	return `${required} ${optional}`;
+}
+
+example("Hello") === "Hello world";
+example("Hello", "TypeScript") === "Hello TypeScript";
+

+ +

+ That seems fine to me. If you don't specify the default value, then it gets + set to undefined. The problem is that there isn't a good built-in + syntax for named parameters, so we have to use other TypeScript features to + hack it in. +

+ +

+function example(
+	required: string,
+	{
+		requiredNamed,
+		namedOptional = "world"
+	}: { requiredNamed: string, namedOptional?: string }
+): string {
+	return `${required} ${requiredNamed} ${namedOptional}`;
+}
+
+example("Hello", { requiredNamed: "beautiful" });
+

+ +

+ Here, we're taking advantage of both anonymous types and destructuring. The + second parameter of the function has an anonymous object type, which contains + two fields: requiredNamed and namedOptional. Then + we destructure this parameter so we can use the fields in the function. +

+ +

+ The most annoying part of this is that we have to define the field names + twice. Once for the type, and once for the function parameters. This is + unnecessary verbosity that any good language should try to avoid. The function + call is also more verbose than necessary, because of the curly braces. +

+ +

+ Unfortunately, this syntax is used all of the time in React. Components are + typically a function that takes one argument, which is an object. So when you + define a component, you have to do this constantly. +

+ +

Rust

+ +

+ Some people have tried to do named parameters in Rust. This generally doesn't + work very well. The most common approach is to define a struct for the + function, and then have it implement the Default trait, so that + we can end the struct initializer with ..Default::default(). +

+ +

+struct ExampleParams {
+	foo: String,
+	bar: String,
+}
+
+impl Default for ExampleParams {
+	fn default() -> Self {
+		Self {
+			foo: "Hello".into(),
+			bar: "Hello".into(),
+		}
+	}
+}
+
+fn example(Example { foo, bar }) -> String {
+	format!("{foo} {bar}")
+}
+
+assert_eq!(
+	example(Example { foo: "Hello".into(), ..Default::default() }),
+	"Hello world".to_string()
+);
+

+ +

+ I complained before about how verbose TypeScript's version is, but this is + even worse, because the types are not anonymous. And worse, if your default + values are not the default of the types (e.g. empty string for String), + then you need to write a whole function to set the default values. It also + only works if every single parameter has a default value. If only some of the + parameters have default values, then you need an even more verbose solution. +

+ +

Why Rust Needs Optional Parameters

+ +

+ The standard library doesn't tend to follow the above pattern (for good reason, + in my opinion). But there are still several cases where the standard library + probably would have benefitted from it. +

+ +

Take some of the factories of HashMap, for example.

+ +

+impl<K, V> HashMap<K, V, RandomState> {
+	pub fn new() -> HashMap<K, V, RandomState>;
+	pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>;
+}
+
+impl<K, V, A: Allocator> HashMap<K, V, RandomState, A> {
+	pub fn new_in(alloc: A) -> Self;
+	pub fn with_capacity_in(capacity: usize, alloc: A) -> Self;
+}
+
+impl<K, V, S> HashMap<K, V, S> {
+	pub const fn with_hasher(hash_builder: S) -> HashMap<K, V, S>;
+	pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S>;
+}
+
+impl<K, V, S, A: Allocator> HashMap<K, V, S, A> {
+	pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self;
+	pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self;
+}
+

+ +

+ With just three optional parameters, we need eight functions to represent all + of the overloads. Each one of them needs to have their own name, since Rust + doesn't actually have overloads. And the programmer and/or code reviewer must + either memorize or look up the order of the parameters when one of the more + complex factories are used. +

+ +

+ Another problem that comes up is the fact that, when the parameters are + unnamed, it can be easier to make mistakes. Consider the following print + function. +

+ +

+fn print(text: &str, bold: bool, italics: bool, underline: bool);
+

+ +

+ It's easy to mix up the parameters here because they don't have names. If I + forget that the italics parameter is third and not second, then I + can end up accidentally bolding my text instead. +

+ +

+ Some functions just have lots of parameters as well. Imagine if I added color, + underline color, background color, blinking text, hidden text, circled text, + and fast blinking text above. Nobody wants to pass in 14 arguments to a + function, of which several will have sensible defaults. And I don't see much + reason to name a new struct if it's only going to be used for the one function. +

+ +

Proposals for Named Arguments

+ +

+ First I'm going to describe some proposals that I've seen for improving named + arguments in Rust, that I don't like. Then I'll reveal what my preferred + solution is. +

+ +

Default Field Values

+ +

+ This feature is already available in Nightly Rust. And the syn + create even recently added support for it. The idea is to make implementing + the Default trait easier by adding special syntax for it. It's + not proposed that this will solve named arguments by itself, but might be part + of a larger solution. +

+ +

+#[derive(Default)]
+struct Pet {
+	name: Option<String>, // impl Default for Pet will use Default::default() for name
+	age: i128 = 42, // impl Default for Pet will use the literal 42 for age
+}
+
+// Pet { name: Some(""), age: 42 }
+let _ = Pet { name: Some(String::new()), .. };
+// Compilation error: `name` needs to be specified
+let _ = Pet { .. };
+// Pet { name: None, age: 42 }
+let _ = Pet::default();
+

+ +

+ I don't actually have a problem with the proposal itself. I even created my + own library to implement a polyfill for it + (feluments). It seems perfect for + structs. But it doesn't help very much for functions. +

+ +

Structural Records

+ +

+ The RFC for default field values mentions a closed RFC for structural records. + They can be thought of as anonymous structs or tuples with named fields. +

+ +

+fn do_stuff_with(color: { red: u8, green: u8, blue: u8 }) { // More ergonomic!
+	some_stuff(color.red); // *And* readable! :)
+	...
+	other_stuff(color.green);
+	...
+	yet_more_stuff(color.blue);
+}
+
+do_stuff_with({ red: 255, green: 127, blue: 63 });
+

+ +

+ The RFC notes that this emulates named arguments, although it does not emulate + optional arguments. It wasn't a major motivation. The major motivation was to + get the convenience of tuples with the readability of structs. +

+ +

+ Let's say for the sake of argument that this RFC succeeded. What would the + syntax of our "Hello, world" examples look like here? Let's assume default + field values are also merged, and they work with structural records. +

+ +

+fn example(
+	required: String,
+	{requiredNamed, namedOptional}: {
+		requiredNamed: Option<String>,
+		namedOptional: String = "world".into()
+	}
+): String {
+	format!("{required} {requiredNamed} {namedOptional}")
+}
+
+example("Hello", { requiredNamed: "beautiful", .. });
+

+ +

+ Wow, that looks familiar. In fact it's the same syntax that TypeScript uses, + with all the problems that come with it. You need to specify the parameter + names twice. +

+ +

Structural records also come with many other challenges:

+ What happens with records that have only one field? { x } can be + interpreted as either a block expression that returns x, or a + structural record expression: { x: x, }. To fix the ambiguity, + the RFC proposed requiring an extra comma: { x, }, like what + tuples do. But this requires making the Rust parser much more complicated, + to do several tokens of lookahead. +
+ It's impossible to implement any traits on these. The RFC proposed magically + implementing several traits. And unlike for tuples, we can't just define some + generic trait implementations, because there can be so much variation in the + field names. +
+ A newcomer to the language may mistake this syntax for a Python dictionary + or Dart's map type. +

+ +

+ Interestingly, TypeScript actually has named tuple fields. But they only exist + at the type declaration. You can't use the field names to access the fields. +

+ +

+type NewLocation = [lat: number, long: number]
+
+const newLocations: NewLocation[] = [
+    [52.3702, 4.8952],
+    [53.3498, -6.2603]
+]
+
+const firstLat = newLocations[0][0]
+const firstLong = newLocations[0][1]
+

+ +

+ Rust's language team decided that although something resembling this feature + seems useful, it would be very hard to implement and not worth the effort. +

+ +

Copy C#

+ +

+ If we're already agreeing on a syntax for optional fields in structs, why not + just copy that over to functions? First, we can allow the arguments to be + specified in any order, as long as they are named, and no out-of-order + positional arguments are following a named argument. +

+ +

+print_order_details(order_num: 31, product_name: "Red Mug", seller_name: "Gift Shop");
+print_order_details(seller_name: "Gift Shop", product_name: "Red Mug", order_num: 31);
+print_order_details("Gift Shop", 31, product_name: "Red Mug");
+print_order_details(seller_name: "Gift Shop", 31, product_name: "Red Mug");
+
+// this would cause an error
+print_order_details(product_name: "Red Mug", 31, "Gift Shop");
+

+ +

+ Then, we could define default values, and allow parameters with default values + to be unspecified. +

+ +

+fn print_order_details(product_name: &str, order_num: 31, seller_name: &str = "Gift Shop");
+
+print_order_details("Red Mug", 31);
+

+ +

+ Unlike for the default field values proposal, we can't use a .. + at the end here, because it is also a valid expression. +

+ +

+ The biggest problem with this idea is that it makes parameter names part of + the public API of the function, without functions opting into it. There was + previously an objection on the grounds of it conflicting with the proposed + type ascription feature. But the RFC for it has since been deleted, so I don't + think we need to worry about that anymore. +

+ +

Public Arguments

+ +

+ As far as I know, a formal RFC was never made for this, but a pre-RFC was + posted to the Rust Internals Forum several years ago, and it's the most + thorough proposal for named arguments that I know of. I'll avoid copy-pasting + the entire RFC here, but I'll give a high level overview. +

+ +

Here's an example of a function with named arguments from the RFC:

+ +

+pub struct Database;
+pub struct RegistrationError;
+
+pub fn register(
+	pub name: String,
+	pub surname: String,
+	to db: Database
+) -> Result<(), RegistrationError> {
+	/* ... */
+}
+
+register(name: "Alexis".into(), surname: "Poliorcetics".into(), to: my_db);
+

+ +

+ In the case of to db, the name of the argument is to, + but it's referred to as db within the body of the function. For + the other two parameters, the pub keyword is used to say that + that both the name of the argument when calling the function, and the name of + the parameter in the function body, are the same. +

+ +

+ The RFC goes into way more detail, proposing function overloads, using named + arguments with the Fn trait, exposing names from patterns, method + overloads, and explaining the documentation aspect. +

+ +

Here are the criticisms I saw in the comments:

+ Unordered named arguments was ruled out. I don't like the justification + RustyFrog gave for this, but it seems easy to support with this model. +
+ Default parameter values also weren't proposed, even though it's the main + reason for wanting named parameters +
+ Despite not proposing default parameter values, the pre-RFC did propose + overloads, which are very difficult to implement in Rust, and they're not as + useful as optional arguments. It's not proposing type-based overloads, which + is a bit better, but still. +
It's a very big RFC, which might make it difficult to get it approved.
+ There are some syntax ambiguities, like fn foo(name (a, b): name), + which is currently valid syntax. There was also a proposed type acription + feature that it conflicted with, but as I said before, that RFC has since + been removed. +
+ Using pub might be confusing, given how it's used currently. I + don't think I mind that personally, because its effect is to make the name of + the parameter part of a function's public API. But I get how that's a bit + weird. +
+ The proposal for changing the Fn trait seemed underbaked. The + Fn(f32, f32) -> String trait gets desugared to + Fn<(f32, f32), Output = String>, but it's not clear what the + desugaring for named parameters should look like. +
+ Despite explaining the usage for Fn implementations, the fn + type was not mentioned at all. +
+ The pre-RFC was not clear about if named parameters were required to be used + by name, or if having the correct position was technically sufficient. +
+ The handling of extern functions with named arguments is fairly complicated + to the point where it would probably be better to not handle them. +

+ +

+ My understanding is that the author got busy and didn't address these concerns, + but I think the pre-RFC serves as a good starting point. +

+ +

Struct-style function calls

+ +

+ This idea was proposed back in 2016 by nixpulvis. I've also seen it floating + around in some other places. +

+ +

+// 1. Tuple style method call (current functions).
+fn foo(a: u32) {}
+foo(2);
+
+// 2. Struct style method call.
+fn foo { a: u32 }
+foo { a: 2 };
+// SomeType { a: 1 } -> SomeType
+// SomeFunc { a: 1 } -> Codomain
+// generally_lowercase { a: 1 } -> Codomain
+
+// 3. Together.
+fn foo(a: u32) { a: u32 } {}
+foo(1) { a: 2 };
+

+ +

+ I personally don't like it because it makes struct constructions and function + calls look too similar. I also have no idea how the compiler would parse this. + But then again, most languages use new Foo() syntax for + constructors, so maybe somebody will like it. +

+ +

Copy Dart

+ +

+ Another proposal that's come up, including from myself, is to copy the Dart + syntax, like so: +

+ +

+fn foo({ foo: &str = "Hello", bar: &str = "World" }) -> String {
+	format!("{foo} {bar}")
+}
+

+ +

+ To me, this looks too much like existing pattern syntax. But I do like that it + doesn't require an extra keyword on each argument. +

+ +

Edition Separation

+ +

+ Some people have proposed solving the backwards-compatibility problem by only + allowing named arguments to be used with functions that were written in a + future edition of Rust. To me, this feels like too large of a breaking change + to be worth considering. +

+ +

Dot Prefixes

+ +

+ An RFC was opened in 2020 proposing using a dot prefix to distinguish between + named and unnamed variables. It was not merged, because the RFC was a very + incremental step that didn't explain the future plans for how the named + arguments would work. Here's an example from the PR: +

+ +

+fn split(string: &str, .at: char, .limit: usize, .case_sensitive: bool) {}
+
+split("hello world", .at = ' ', .limit = 2, .case_sensitive = true);
+

+ +

+ The dot was chosen because it's only one character, (as opposed to four + characters, with the pub keyword plus a space). But I honestly + don't think it's intuitive enough. The dot is also reminds the user of struct + fields, which is a completely unrelated concept. +

+ +

My Proposal

+ +

+ After reading all of these proposals, I feel that all of the pieces exist for + a complete named arguments proposal that lack any of the downsides. I get the + impression that some people are going to be opposed to the concept no matter + what, but I tried to address as many counter-arguments for named arguments as + possible in this post. The rest of this post will be a pre-RFC that think + will satisfy as many people as possible. I'll monitor the comments anywhere + this gets posted to see if there are any major criticisms. I can't guarantee + that I'll actually make an RFC, but permission is granted to create an RFC if + I don't. I think it's been a while since named argument were last seriously + proposed, so I think now is a good time for a new proposal. +

+ +

Summary

+ +

+ Add named and optional arguments to functions. Functions can have both + positional and named arguments. In function calls, named arguments may be + referred to by name, to increase readability and maintainability. Named + arguments may also have default values, avoiding the need to specify them in + the function call. +

+ +

Motivation

+ +

Improve safety and readability

+ +

+ Misremembering which parameter is at which position is a major source of bugs + in many languages, including Rust. Take the function from the standard + library: hard_link. +

+ +

+pub fn hard_link<P: AsRef<Path>, Q: AsRef<Path>>(
+	original: P,
+	link: Q,
+) -> Result<()>
+

+ +

+ Both parameters accept the same types, so there's no way to know which one is + which without looking at the documentation. The consequence of misremembering + is a runtime error or a bug. +

+ +

+ With named parameters, it is easy to see what is happening at the call-site. + This also makes the resulting code more readable. +

+ +

+hard_link(original: "a.txt", link: "b.txt")?;
+

+ +

The effect is more pronounced for functions which have more parameters.

+ +

+// Without named arguments: what are these numbers?
+solar_elevation(1787517098.0, 38.897957, -77.036560)
+
+// With named arguments, it's obvious
+solar_elevation(timestamp: 1787517098.0, latitude: 38.897957, longitude: -77.036560);
+

+ +

+ A similar effect is possible in Rust today, by creating a new struct and + having that be the function's only parameter. But it's very verbose to create, + so in practice, few libraries take advantage of it. Importantly, the standard + library rarely uses this pattern. +

+ +

Boilerplate reduction

+ +

+ Many functions have reasonable defaults that should be passed into many of + their parameters, but because all positional arguments are required, all of + the parameters must be specified. Passing None into every + parameter comes with readability issues. +

+ +

+repository.checkout_index(None, None)?;
+

+ +

+ Passing a struct into the parameters does give us names, but still requires + us to specify None for the optional values. Sometimes this + boilerplate can be reduced by adding ..Default::default() to the + end of the constructor, Default cannot be implemented if any of + the fields are not optional. Implementing Default is also a lot + of boilerplate if it cannot be implemented simply by using the derive macro. + Some of these problems can be addressed by + RFC 3681, but it + still requires a new struct to be defined specifically for one function. +

+ +

+let instance = Instance::new(InstanceDescriptor {
+	backends: Backends::default(),
+	flags: InstanceFlags::default(),
+	memory_budget_thresholds: MemoryBudgetThresholds::default(),
+	backend_options: BackendOptions::default(),
+	display: None,
+});
+

+ +

+ To help reduce the boilerplate of calling such a function, many libraries + implement builder types that don't require every value to be specified. This + comes at the cost of even more boilerplate to create the builder, which + becomes part of the library's public API. There are crates, such as + bon to make declaring a builder + for a struct easier, but it still requires a struct be declared for a single + function. Libraries don't always use these crates either, as doing so + increases compile times. The Command struct uses 60 SLOCs (and + many more lines of documentation) to allow us to do this: +

+ +

+Command::new("printenv")
+	.stdin(Stdio::null())
+	.stdout(Stdio::inherit())
+	.env_clear()
+	.envs(&filtered_env)
+	.spawn()
+	.expect("printenv failed to start");
+

+ +

If we had named arguments, the following function would be easy to define:

+ +

+spawn(
+	command: "printenv",
+	stdin: Stdio::null(),
+	stdout: Stdio::inherit(),
+	env_clear: true,
+	envs: &filtered_env
+).expect("printenv failed to start");
+

+ Bon also provides utilities for emulating named arguments in functions, but + calling such a function involves some boilerplate as well. +

+ +

+// Example from the bon README
+
+#[builder]
+fn greet(name: &str, level: Option<u32>) -> String {
+	let level = level.unwrap_or(0);
+
+	format!("Hello {name}! Your level is {level}")
+}
+
+// This could be shortened to greet(name: "Bon", level: 24)
+let greeting = greet()
+	.name("Bon")
+	.level(24)
+	.call();
+
+assert_eq!(greeting, "Hello Bon! Your level is 24");
+

+ +

+ In practice, the added complexity means that these patterns are only ever used + in public APIs, so private functions have no worthwhile workaround to improve + readability. +

+ +

Extensibility without breaking changes

+ +

+ Currently, adding a new parameter to an existing function is a breaking + change. If you want to add a new field to a struct, your existing factory must + implement a reasonable default value, and a new function must be created to + enable the new functionality. +

+ +

+ This leads to some APIs having many functions which do similar things, but + with different parameters. For example, HashMap from the standard + library has the following factories. +

+ +

+impl<K, V> HashMap<K, V, RandomState> {
+	pub fn new() -> HashMap<K, V, RandomState>;
+	pub fn with_capacity(capacity: usize) -> HashMap<K, V, RandomState>;
+}
+
+impl<K, V, A: Allocator> HashMap<K, V, RandomState, A> {
+	pub fn new_in(alloc: A) -> Self;
+	pub fn with_capacity_in(capacity: usize, alloc: A) -> Self;
+}
+
+impl<K, V, S> HashMap<K, V, S> {
+	pub const fn with_hasher(hash_builder: S) -> HashMap<K, V, S>;
+	pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> HashMap<K, V, S>;
+}
+
+impl<K, V, S, A: Allocator> HashMap<K, V, S, A> {
+	pub fn with_hasher_in(hash_builder: S, alloc: A) -> Self;
+	pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self;
+}
+

+ +

+ All of these functions are shown in the documentation, polluting the API. The + number of functions is exponential with respect to the number of parameters. + If we ignore the differences in generic parameters (a possible solution to + which is discussed in the "Future possibilities" section), then we could + imagine having a single function. +

+ +

+pub fn new(
+	pub capacity: usize = 0,
+	pub alloc: A = Global,
+	pub hasher: S = RandomState,
+);
+

+ +

+ If we wanted to some day add a fill parameter, we'd be able to + add it to this existing function without it being a breaking change, and + without doubling the number of factories for HashMap. +

+ +

Guide-level explanation

+ +

+ Parameters may be named or unnamed. By default, all parameters to a function + are unnamed, and cannot be referred to by name. We can create a named + parameter by adding the pub keyword before its name. +

+ +

+fn print_labeled_measurement(pub value: i32, pub unit_label: char) {
+	println!("The measurement is: {value}{unit_label}");
+}
+
+fn main() {
+	print_labeled_measurement(5, 'h');
+}
+

+ +

+ At first, this may not seem very different from unnamed parameters. But when + a parameter is named, we may use its name when calling the function. This + makes it easier to tell, at a glance, what the values being passed into the + function are meant to do. +

+ +

+print_labeled_measurement(value: 5, unit_label: 'h');
+

+ +

+ When parameters are named, they may also be re-ordered, so you don't need to + remember the position of each one. +

+ +

+print_labeled_measurement(unit_label: 'h', value: 5);
+

+ +

+ There are some caveats to the ordering. A function may contain both named and + unnamed parameters. But if it does, all named arguments must be specified + after the positional arguments, both in the function declaration and in the + function body. +

+ +

+// unit_label is named, value is not
+fn print_labeled_measurement(value: i32, pub unit_label: char) {
+	println!("The measurement is: {value}{unit_label}");
+}
+
+// forbidden: all named parameters must be after all unnamed parameters
+fn _print_labeled_measurement(pub value: i32, unit_label: char) {
+	// ...
+}
+
+fn main() {
+	// forbidden: the parameter that 'h' is being passed into must be named
+	print_labeled_measurement(value: 5, 'h');
+	// forbidden
+	print_labeled_measurement(unit_label: 'h', 5);
+}
+

+ +

+ Named parameters may also have default values. This means that the caller does + not need to specify the argument value when calling the function. The default + value is using automatically. +

+ +

+fn print_labeled_measurement(pub value: i32, pub unit_label: char = 'm') {
+	println!("The measurement is: {value}{unit_label}");
+}
+
+fn main() {
+	// unit_label is unspecified and is defaulted to 'm'
+	print_labeled_measurement(5)
+}
+

+ +

+ Named parameters cannot be used if the parameter does not have a name and is + defined as a pattern instead. For example, the following is not valid. +

+ +

+fn print_coordinates(pub &(x, y): &(i32, i32)) {
+	// ...
+}
+

+ +

+ However, a name can be given to this parameter by using an @ + binding. +

+ +

+fn print_coordinates(pub point @ &(x, y): &(i32, i32)) {
+	// ...
+}
+

+ +

+ Traits may also choose to use named parameters, in which case the + implementation must use the same name. However, trait function parameters + cannot have default values. +

+ +

+trait Trait {
+	fn f(pub a: i32, pub b: i32);
+}
+
+impl Trait for () {
+	// This is okay, because the parameter names match
+	// unused parameter warnings can be ignored using @
+	fn f(pub a: i32, pub b @ _: i32) {}
+}
+
+impl Trait for i32 {
+	// invalid: the second argument is named `b` in the definition
+	fn f(pub a: i32, pub c: i32) {}
+}
+
+impl Trait for bool {
+	// invalid: `b` is not public
+	fn f(pub a: i32, b: i32) {}
+}
+
+impl Trait for X {
+	// invalid: trait methods cannot have default parameter values
+	fn f(pub a: i32, pub b: i32 = 0) {}
+}
+

+ +

+ Because the parameter names are optional, function pointers may be created for + functions with named parameters. However, the name will not be accessible on + the function pointer, and default values cannot be used. This also applies for + the Fn* family of traits. +

+ +

+fn foo(pub a: i32, pub b: i32) {}
+
+let f: fn(i32, i32) = foo;
+
+f(4, 2);       // ok
+f(a: 4, b: 2); // ERROR! `f` can't be called with named arguments
+
+fn higher_order(f: Fn(i32, i32)) {
+	f(4, 2);        // ok
+	f(a: 4, b: 2);  // ERROR! `f` can't be called with named arguments
+}
+higher_order(foo);       // ok
+higher_order(|_, _| {}); // ok
+

+ +

Reference-level explanation

+ +

Grammar

+ +

+ The only needed change to support public parameters in function declarations + is to function parameters. First, we add the pub keyword, which + must be followed by an identifier pattern. Such a pattern may also include a + default value. +

+ +

+FunctionParamPattern = PatternNoTopAlt ":" ( Type | "..." )
+                     | "pub" IdentifierPattern ":" ( Type | "..." ) ( "=" Expr )?
+

+ +

+ For function calls, the syntax is slightly more complicated to parse, but only + affects CallParams. +

+ +

+CallParam  = Expression ( ":" Expression )?
+CallParams = CallParam ( "," CallParam )* ","?
+

+ +

+ This is slightly more complicated to parse, because an identifier is also a + valid expression. To solve this, we'll just parse an entire expression, and + then check to see if there's a colon following it. The compiler can later + give an error if the argument name is anything other than an identifier. +

+ +

Static semantics

+ +

Function parameters

+ +

+ Given a FunctionParamPattern where the default is specified, i.e.: +

+ +

+FunctionParamPattern = "pub" pat:IdentifierPattern ":" ( ty:Type | "..." ) ( "=" expr:Expr )
+

+ +

similar rules to the rules for default field values apply. Namely,

+ If the function is const, then the expression, expr + must be a constant expression. +
The expression expr must coerce to the type ty
+ Generic parameters of the current items are accessible. +
```
+fn foo<const A: usize>(bar: usize = A) {}
+
```
+
+ Default const expressions are not evaluated at definition time, only during + instantiation. This means that the following will not fail to compile: +
```
+fn foo(a: usize = panic!(), b: usize = 42) {}
+
+foo(a: 0);
+
```
+
+ The function's generic parameters are properly propagated, meaning the following is possible: +
```
+fn foo<T>(bar: Vec<T> = Vec::new()) {}
+
+foo::<T>();
+
```
+
+ When lints check attributes such as #[allow(lint_name)] are + placed on a FunctionParam, it also applies to the expression, + expr. +
+ Unused parameter names will not emit a warning if they are bound to a + different pattern using @. The bound pattern may still emit a + warning +

+ +

+ For public parameters in general, all public parameters must be strictly after + all non-public parameters. +

+ +

Function calls

+ +

+ The semantics of function calls change significantly. In general, all named + arguments must be specified after all positional arguments. For positional + arguments, all existing semantics apply. +

+ +

In the case of the following production of a named argument:

+CallParam  = name:Expression ":" value:Expression
+

the following rules apply

The expression, name must be a plain identifier.
+ The identifier, name must be the name of a public parameter of + the function. +
+ The expression, value must coerce the the type of the + aforementioned public parameter. +

+ +

Trait declarations

+ +

+ For trait declarations all the same rules apply from function declarations. In + addition: +

Trait methods cannot have default parameter values.

+ +

Trait implementations

+ +

+ The semantics of trait implementations vary slightly from the semantics for + trait declarations. +

+ Any parameter which was declared public on the trait declaration must also + be public in the trait implementation. +
Public parameters must have the same name that their declaration has.

+ +

Drawbacks

+ +

Added complexity

+ +

+ The language would be slightly more complex as a result of this feature. But + this proposal is fairly minimal as far as named arguments proposals go. The + syntax for named arguments resembles the syntax for struct fields, and the + default value syntax is pretty similar to the syntax proposed for default + field values. +

+ +

+ One concern that can come up in named argument proposals is the problem of it + only applying to new functions, which makes it hard to remember which + libraries. This proposal can be backported to the standard library, making the + language feel more consistent. +

+ +

Named arguments aren't mandatory

+ +

+ The fact that names are optional could be seen as a compromise on the safety + benefits. Some people may lazily choose to leave them out, in which case, no + safety benefit is provided. +

+ +

+ However, the fact that they aren't mandatory allows more library authors to + use them without worrying about breaking changes. Some authors may also be + more inclined to support named arguments if they felt confident that it would + not increase the verbosity of calling the function. +

+ +

+ This drawback does present a potential bug. If the names are removed during a + refactor, then they may be in the wrong position after the refactor, causing + a bug. +

+ +

+// before refactor
+coordinates(y: 45.6, x: 6784.0);
+
+// after refactor: incorrect order
+coordinates(y, x);
+

+ +

Remedy: Add a clippy lint

+ +

+ A clippy lint can be used to enforce the use of named arguments when possible. +

+ +

Remedy: Require named arguments in a future edition

+ +

+ Although it may be a large breaking change, future editions could likely + require the use of named parameters, if it were deemed desirable to do so. +

+ +

Limiting type ascription

+ +

+ Many older proposals for named arguments noted that the syntax chosen here: + name: value conflicts with the proposed type ascription feature. + However, since then, the RFC for type ascription has been removed. And another + type ascription RFC was rejected, partially on the basis of it potentially + conflicting with named arguments. So this is not likely to be a concern + anymore. +

+ +

Rationale and alternatives

+ +

Why make named arguments opt-in?

+ +

+ Although many languages, such as Kotlin and C#, allow any argument to be + named, this is not practical for Rust. Changing an argument is currently not + a breaking change, but would become one as soon as named arguments are + introduced. The solution is to allow authors to decide if their argument names + are an implementation detail or not. +

+ +

The `pub` keyword

+ +

+ Using the pub keyword may seem like a strange choice, given the + semantics. But it has essentially the effect of making the parameter name + public, so this is defensible. Other visibility modifiers are not proposed by + this RFC, because it's hard to imagine a situation where a public function + would want to allow named arguments internally, but not externally. +

+ +

+ Other modifiers have been proposed. One could imagine adding an ext + keyword to define named parameters. A previous RFC proposed using dots, but + this was deemed to be too reminiscent of field access. Other symbols, such as + @ may be more acceptable. Another proposed idea is to copy Swift + syntax and use two identifiers. +

+ +

+fn foo(bar bar: &str) {}
+

+ +

+ Re-typing the same parameter name twice is verbose and usually unnecessary. + It's also unnecessary since syntax exists for rebinding a variable already. +

+ +

+ Dart wraps named arguments in curly braces. This has the benefit of not + requiring the pub keyword to be specified multiple times. However, + in the context of Rust, this looks like a destructuring pattern, which isn't + semantically correct. +

+ +

+// In Dart
+void enableFlags({bool? bold, bool? hidden})
+enableFlags(bold: true)
+
+// Similar idea, in Rust
+fn enable_flags({ bold: Option<bool> = None, hidden: Option<bool> = None })
+enable_flags(bold: Some(true))
+

+ +

+ Another proposal is to make function calls with named arguments look more like + struct constructions by using curly braces instead of parentheses. This seems + like it could be very confusing and make the distinction between the two + features unclear. +

+ +

+fn foo (a: u32) { b: u32 } {}
+foo(1) { b: 2 };
+

+ +

Colon vs equal sign

+ +

+ Some have proposed using an equal sign (=) instead of a colon + (:). This would make the syntax more closely resemble assignment, + which is semantically true. It also would not possibly conflict with type + ascription. +

+ +

+ The colon syntax was chosen for this RFC to be more consistent with struct + initializers. +

+ +

Argument re-ordering

+ +

+ Some proposals for named arguments have omitted re-ordering of arguments for + simplicity. For the sake of thoroughness, this RFC proposes allowing arguments + to be re-ordered. A possible alternative would be to require arguments to + still be in the original order. The drawback would be unnecessary friction + when the user sorts the arguments out of order. +

+ +

+ Some languages allow for more flexible re-ordering than this RFC proposes. C# + allows named arguments to appear before unnamed arguments, as long as the + arguments are still in order. This RFC omits this feature, in order to make + named arguments seem less confusing to users. The reordering proposed here + still allows for more flexible argument-reordering in the future. +

+ +

No default values in traits

+ +

+ This RFC currently prohibits traits from making use of default parameter + values. This is because it's unclear if default values for trait parameters + should be defined at the trait definition or the trait implementation. It + would likely be more predictable if default values could be defined by the + implementation. But it's hard to imagine how a default value would allow the + trait to be dyn-compatible. If the default values were defined at the trait + definition, then they could stay dyn-compatible. +

+ +

On const contexts

+ +

+ In the default field values RFC, it was decided that default values for + structs must be const. The reasoning is that functions with side-effects may + be confusing for the compiler and for users. However, these justifications + don't apply to functions, because non-const functions don't carry an + expectation of being cheap or consistent. It is possible to always require + default values to be const, but there's seemingly no strong reason to do so. +

+ +

+ However, it would be confusing if default parameters could be non-const in + const functions, which is why they are required to be const in that case. +

+ +

Named arguments aren't mandatory

+ +

See the section above in "Drawbacks".

+ +

Alternative: Do nothing

+ +

+ The "Motivation" section explains thoroughly how the current state is very + verbose, to the point where existing alternatives, such a struct parameters + and builders are often not used. The existence of these patterns is evidence + that users want some way to emulate named arguments. The fact that these + alternatives are not used in private APIs is evidence that the status quo is + annoyingly verbose. +

+ +

Alternative: Structural Records

+ +

+ It has been proposed many times that structural records, alongside default + field values, could emulate named parameters. This is a pattern that is often + used in languages like TypeScript. The syntax for declaring such a function + would look like this. +

+ +

+fn foo({ a, b, c }: { a: f64, b: f64, c: f64 }) {}
+

+ +

There are several criticisms I have of this pattern:

+ It cannot be backported to older functions without causing a breaking change, + so the standard library could not use it. +
+ Every identifier in this declaration needs to be typed twice. It might be + possible to introduce syntactic sugar for this, but not such syntax has been + proposed. +
+ Structural records have had a proposed RFC in the past, but was rejected, + mainly due to the complexity of implementing it. +

+ +

+ Structural records could serve as a temporary compromise for named arguments, + if they are ever implemented. I'm not currently convinced that they ever will + be implemented. If the compromise solution is harder to implement than the + real solution, then we might as well just use the real solution. +

+ +

Alternative: Struct name inference

+ +

+ One proposal to make named arguments easier is to allow the name of a struct + to be inferred when it is constructed. This would make the call sites of + functions using struct parameters to look mostly simple. +

+ +

+foo(_ { a: 1, b: "2", c: [] });
+

+ +

+ However, this still requires the function to support this function explicitly, + by defining a struct to be passed in. It also still cannot be backported to + existing functions. The only benefit this provides over the status quo is to + avoid typing the name of the struct at the call site, which is not the main + criticism of this pattern. It would still be unlikely for private functions to + use this pattern. +

+ +

Alternative: Implementing `Fn` traits

+ +

+ I've seen this come up a couple of times, but I think most of the people + suggesting this are doing so as a joke. Implementing Fn would + be a more verbose form of the method overload feature that some other + languages have. Overloads are difficult and controversial to implement in + Rust, so it's unlikely this pattern would be adopted. +

+ +

Prior art

+ +

+ Several previous attempts at named arguments, both in Rust and in other + languages, have been described throughout this RFC. +

+ +

+ A previous RFC for named arguments exists for Rust. It was rejected mainly + because it did not describe what the future of named arguments would look like + with optional arguments. This RFC attempts to address as many future uses of + named arguments as possible in order to give a full picture. +

+ A pre-RFC was proposed by forum user Azerupi, but no RFC seemed to come as a + result of it. Several complications were pointed out by commenters. This RFC + attempts to address syntactic ambiguity, the type system, and opt-in naming. +

+ Another pre-RFC proposed using a more Swift-style syntax, which was avoided in + this RFC. The pre-RFC also proposed overloading but not default arguments. + Arguably the latter is more important than the former. +

+ As was mentioned before, bon offers a procedural macro for creating builders + from functions. The existence of this feature shows that there is a desire for + named arguments, that would be better handled as a language feature. +

+ +

+ Other lanaguages with named arguments have also been discussed. The feature + proposed here is similar to named arguments from C# or Kotlin, with the + difference being that thhe named arguments are opt-in. The syntaxes used by + Dart and Swift have also been discussed. Dart uses the following syntax, which + looks closer to destructuring than named arguments. +

+ +

+void enableFlags({bool? bold, bool? hidden})
+enableFlags(bold: true)
+

+ +

+ Swift makes all arguments named by default, allowing authors to opt-out by + using an underscore before the variable name. This is impossible to port to + Rust without making a breaking change to the language. Various proposals have + tried to use slightly different syntaxes, but many of them present syntactic + ambiguities. +

+ +

Unresolved questions

+ +

Should we require named arguments to be given in position order?
Is pub the best keyword, or should a different keyword be used?
Should default values be required to always be const?

+ +

Future possibilities

+ +

Default parameter values for trait methods

+ +

+ Trait methods were forbidden from having default values due to the question of + if the default value should be on the trait declaration or the trait + implementation. Having it be on the implementation would be consistent with + how associated types and constants work. But this would make it hard for such + a trait to be dyn-compatible. +

+ +

+ One solution would be to only allow default values to be used in non-dyn + contexts. +

+ +

+trait Foo {
+	fn bar(&self, baz: i32 = 0);
+}
+
+impl Foo for i32 {
+	fn bar(&self, baz: i32 = i32::MAX) {}
+}
+
+fn do_bar<T: Foo>(x: &T) {
+	x.bar(); // baz doesn't need to be specified, since we're using generics
+}
+
+fn do_bar_2(x: &dyn T) {
+	x.bar(); // ERROR: baz must be specified when using a method on a dyn object
+}
+

+ +

Extending traits

+ +

+ Theoretically, there's nothing preventing the following, as long as a default + parameter value is provided: +

+ +

+impl<T> Default for Vec<T> {
+	fn default(capacity: usize = 0) -> Self {
+		Self::with_capacity(capacity)
+	}
+}
+

+ +

+ Although, in addition to making the behavior of the default + function inconsistent, this is even harder to resolve in a dyn + context. The likely remedy would be to forbid Vec from being + converted into a dyn Default, which would make introducing the + named parameter a breaking change. +

+ +

Requiring named arguments in a future edition

+ +

+ Allowing named arguments to be optional is necessary in order to backport them + into existing functions without creating breaking changes. This comes with + some compromises, as has been described in the "Drawbacks" section. However, + the way this RFC is drafted makes it possible to require named arguments in a + future edition of Rust. Specifying a named argument would not give a warning + in either the previous edition or the new edition. +

+ +

+ Doing this too early would likely hurt adoption of named arguments, as + backporting them into existing functions would become a breaking API change. + This would also increase the verbosity of calling functions which make use of + named parameters, hurting adoption further. +

+ +

More flexible re-ordering

+ +

+ As mentioned before, re-ordering of named arguments is allowed by this RFC, + in a limited way. The limitations are kept in order to keep the rules easy to + explain and reason about. However, some languages allow arguments to be + re-ordered more flexibly, and this would be possible to do in the future. +

+ +

+ C#'s main rule is that out-of-order named arguments cannot be followed by + positional arguments. +

+ +

+print_order_details(order_num: 31, product_name: "Red Mug", seller_name: "Gift Shop");
+print_order_details(seller_name: "Gift Shop", product_name: "Red Mug", order_num: 31);
+print_order_details("Gift Shop", 31, product_name: "Red Mug");
+print_order_details(seller_name: "Gift Shop", 31, product_name: "Red Mug");
+
+// this would cause an error
+print_order_details(product_name: "Red Mug", 31, "Gift Shop");
+

+ +

Defaults Affect Inference

+ +

+ In 2022, Gankra proposed using default parameter values as part of inference + for generic type parameters. We could imagine something like this. +

+ +

+fn default_hasher() -> RandomState { ... }
+
+impl <K, V, S: BuildHasher> HashMap<K, V, S> {
+    fn new(hasher: S = RandomState::default()) { ... }
+}
+
+// uses S=RandomState
+let map = HashMap::new();
+

+ +

+ The downside of this particular approach, as Gankra pointed out, is that this + would only allow the argument to be omitted if the type of S is + RandomState. Although, that's already true with the current set + of HashMap factories, unless you use default which + doesn't have any parameters at all. +

+ +

Generic const

+ +

+ In the case of Vec, adding an optional capacity + parameter is not possible with this iteration of the RFC, because + Vec::new is a const function, and allocating memory + cannot be done at compile-time. This is a very difficult problem to solve, + and it's possible that it never will. However, if keyword generics are added + to the language, it may be possible to do something like this: +

+ +

+const<C> trait Capacity: Copy {
+	const<C> fn allocate<T>(self) -> Option<Box<[MaybeUninit<T>]>>;
+
+	const fn as_usize(self) -> usize;
+}
+
+const impl Capacity for () {
+	const fn allocate<T>(self) -> Option<Box<[MabyUninit<T>]>> {
+		None
+	}
+
+	const fn as_usize(self) -> usize {
+		0
+	}
+}
+
+impl Capacity for usize {
+	fn allocate<T>(self) -> Option<Box<[MaybeUninit<T>]>> {
+		Some(Box::default())
+	}
+
+	const fn as_usize(self) -> usize {
+		self
+	}
+}
+
+const<C> impl<T, Cap: const<C> Capacity> Vec<T> {
+	pub const<C> fn new(capacity: Cap = ()) -> Self {
+		Self {
+			len: 0,
+			capacity: capacity.as_usize(),
+			buffer: capacity.allocate(),
+		}
+	}
+}
+

+ +

+ If no argument value is provided, then the function would be + const. But when a usize is provided, then it would + no longer be const. +

+ +

+ diff --git a/src/blog/quality-quantity.kuht b/src/blog/quality-quantity.kuht new file mode 100644 index 0000000..e3ddf99 --- /dev/null +++ b/src/blog/quality-quantity.kuht @@ -0,0 +1,98 @@ + + + + More Features Don't Make Software Better + + + + +

+ +

More Features Don't Make Software Better

+ +

+ Forgive the clickbaity title. It's not entirely true, but it is accurate to + the spirit of what I'm describing. I have frustration when explaining this to + people, and I've struggled to articulate it well until now. +

+ +

+ If your software has 100 features, but all of them suck, then I have no reason + to use your product. But if your software has even one feature that feels very + well considered, thought-out, and cared for, I now have a reason to use your + product. +

+ +

+ A similar principle applies when applying for jobs. If you send out 100 job + applications that all suck, then every single one of them is going to be + rejected. You can't scam someone into giving you a job. I spent two weeks + refining my resume, and only sent it to two companies. Both companies also got + cover letters from me. I got an offer from the second job I applied + for¹. +

+ +

+ My code editor of choice is helix. It doesn't have a lot of features. In fact, + it doesn't even support extensions yet². + But I keep coming back to it because the mental model it asks me to adopt is + very simple compared to something like Vim, and much more efficient than VS + Code. I select text, and then perform an action. The other things I need out + of a code editor are just good enough to get by. There is a built-in file + explorer and ripgrep tool. I've tried LazyVim in the past, and even though it + had more features, I couldn't shake the feeling that none of them were + designed to work nicely with each other. So despite how much functionality + there was, I didn't feel good about using any of it. +

+ +

+ Sonic Frontiers, after releasing, had three updates to the game that were + released for free. There were a lot of interesting ideas in those updates. + They did try to address some of the issues players had with the game, such as + the lack of momentum when jumping. But there were other ideas that I found + questionable. Action chain challenges are cool, but would it really improve + how players perceive the game if it were there at launch? None of the updates + improved the art direction, or addressed the gratuitous pop-in, or made the + existing Cyberspace stages feel less like copies of older levels. The final + update came with a new campaign at the end of the game with multiple playable + characters. The lack of multiple playable characters is a long-standing + complaint in the Sonic community, but the gameplay for these characters was so + difficult to control (with the exception of Amy) that I would rather have not + played as them at all. +

+ +

+ I don't think it should be acceptable to excuse having lots of bugs because + you also have a lot of features. It would make sense that more features would + induce more bugs, but that's still worse for the end-user. I'd rather have + software that doesn't do much, but also doesn't annoy me with problems while + it does very little. Those annoyances will cause some users to find other + options, even if those other options may not do everything your software does. +

+ +

+ All of this is my opinion. I won't claim that everyone else feels the same + way, or that following this approach will make you more money in the long run. + But personally, I prefer a piece of software that has one feature I really + like, to a piece of software that has 100 features that I only tolerate. +

+ +

+ + + diff --git a/src/blog/try-catch-in-rust.kuht b/src/blog/try-catch-in-rust.kuht new file mode 100755 index 0000000..63734cd --- /dev/null +++ b/src/blog/try-catch-in-rust.kuht @@ -0,0 +1,553 @@ + + + + How to Introduce try-catch to Rust + + + + + +

+ +

How to Introduce try-catch to Rust

+ +

+ As a disclaimer, this isn't my personal proposal or anything. But I took a look at the RFC for try + blocks in Rust, and I thought it was interesting how it it left the door open for catch blocks in the + future. I thought it would be an interesting idea to share. But in order to talk about this, we have + to work our way forwards. +

+ +

Above the Iceberg: Rust enums

+ +

+ Many of you readers will already understand this much, but if you've never worked with Rust before, + I'll have to introduce the enum system. Rust's enums can carry values on particular variants. They're + pretty much just tagged or discriminated unions. +

+ +

+pub enum JsonValue {
+	Null,
+	Boolean(bool),
+	Number(f64),
+	String(String),
+	Array(Vec<JsonValue>),
+	Object(Vec<(String, JsonValue)>),
+}
+

+ +

+ There are a few ways we can get the inner value. We can use a match expression, which is a bit like + switch in other languages. +

+ +

+fn to_json(value: JsonValue) -> String {
+	match value {
+		JsonValue::Null => "null".to_string(),
+		JsonValue::Boolean(b) => b.to_string(),
+		JsonValue::Number(n) => n.to_string(),
+		JsonValue::String(s) => format!("\"{s}\""),
+		JsonValue::Array(a) => {
+			let mut builder = String::from("[ ");
+			for element in a {
+				builder.push_str(&to_json(element));
+				builder.push_str(", ");
+			}
+			builder.push(']');
+			builder
+		}
+		JsonValue::Object(o) => {
+			let mut builder = String::from("{ ");
+			for (key, value) in o {
+				builder.push_str(&format!("\"{key}\": {}", to_json(value)));
+				builder.push_str(", ");
+			}
+			builder.push('}');
+			builder
+		}
+	}
+}
+

+ +

We can use if let to match on only one particular variant.

+ +

+fn unwrap_number(value: JsonValue) -> f64 {
+	if let JsonValue::Number(n) = value {
+		n
+	} else {
+		panic!("The passed value was not a number");
+	}
+}
+

+ +

+ More recently, we got let else, which lets us assert that it is one particular variant, or quit early. +

+ +

+fn unwrap_number(value: JsonValue) -> f64 {
+	let JsonValue::Number(number) = value else {
+		panic!("The passed value was not a number");
+	}
+
+	number
+}
+

+ +

But importantly, there's no way to get the inner value without first checking for the variant.

+ +

In the Beginning: The `Result` type

+ +

+ Rust doesn't have exceptions. The panic macro, shown earlier, causes an immediate end to + the program (in most cases). For catchable errors, we use the Result type, which is + included in Rust's core library. +

+ +

+pub enum Result<T, E> {
+	Ok(T),
+	Err(E),
+}
+

+ +

+ The Result type has two generic types: T, which is the type that was + expected to be returned; and E, which is the type that will be returned instead if an + error occurred. For example, we could define a parse_number function like this: +

+ +

+fn parse_to_f64(s: &str) -> Result<f64, ParseFloatError>
+

+ +

+ If the passed string is a number, then this function will return a 64-bit float. Otherwise, it will + return a ParseFloatError, which is an error describing a failure to parse the number. + We can use the result of this function like so: +

+ +

+fn foo() {
+	let number = match parse_to_f64("3.14159") {
+		Ok(number) => number,
+		Err(e) => panic!("{e}"),
+	};
+
+	println!("{number}");
+}
+

+ +

+ The Result type has a convenient helper method to do this, called unwrap. + If the result is Ok, then the inner value will be returned. Otherwise, the program will + panic. +

+ +

+fn foo() {
+	let number = parse_to_f64("3.14159").unwrap();
+	println!("{number}");
+}
+

+ +

But typically, you'd want to just throw the error again.

+ +

+fn foo() -> Result<(), ParseFloatError> {
+	let number = match parse_to_f64("3.14159") {
+		Ok(number) => number,
+		Err(e) => return Err(e),
+	};
+
+	println!("{number}");
+}
+

+ +

Introduced Later: The `?` operator

+ +

+ As you might imagine, using that match expression over and over again to propogate errors will + quickly become tedious. The original solution was to use the try macro to do it for you. +

+ +

+fn foo() -> Result<(), ParseFloatError> {
+	let number = try!(parse_to_f64("3.14159"));
+	println!("{number}");
+}
+

+ +

+ But the 2018 edition of Rust introduced some syntactic sugar to make this even easier. It can be used + to propogate an error in any function which returns a similar Result. +

+ +

+fn foo() -> Result<(), ParseFloatError> {
+	let number = parse_to_f64("3.14159")?;
+	println!("{number}");
+}
+

+ +

It can even convert between errors, if possible.

+ +

+enum JsonError {
+	ParseNumber(ParseFloatError),
+	Other(String),
+}
+
+impl From<ParseFloatError> for JsonError {
+	fn from(value: ParseFloatError) -> Self {
+		Self::ParseNumber(value)
+	}
+}
+
+fn foo() -> Result<(), JsonError> {
+	// automatically converts the ParseFloatError to a JsonError
+	let number = parse_to_f64("3.14159")?;
+	println!("{number}");
+}
+

+ +

It also works on the Option type, which is also included in Rust.

+ +

+fn foo() -> Option<i32> {
+	let array = [1, 2, 3, 4];
+	let x = array.get(4)?; // get the element at index 4, which doesn't exist in the array
+	Some(x)
+}
+

+ +

+ And some of you may be surprised to learn that it also works on ControlFlow and some + Poll types. +

+ +

+ This isn't stable yet, but there's also a proposal to allow the use of the ? operator on + custom types. This would be done using a few new traits: Residual, + FromResidual, and Try. A residual is a type that can be returned from using + a ?. The FromResidual trait is implemented on types that can be created + from residuals (for example, using ? to get a + Result<Infallible, JsonError>, then converting that to a + Result<(), JsonError>). The Try trait is implemented when a + FromResidual type can also have the ? operator applied to it. These traits + are already available in nightly Rust. As an exercise for the Dallas Rust User Group, we created + our own Result type, and + used these traits to make the ? operator work with it. +

+ +

In Nightly: Try Blocks

+ +

+ Today, try is a reserved keyword. So to use the try! macro in newer + editions of Rust, you'll need to use the raw-literal syntax. +

+ +

+fn foo() -> Result<(), ParseFloatError> {
+	let number = r#try!(parse_to_f64("3.14159"));
+	println!("{number}");
+}
+

+ +

+ What's the keyword being used for? It's for the try-block feature, which is currently only available + in nightly. The idea for this was made at roughly the same time as the ? operator, to + catch anything that was propogated with it. However, only the ? got merged. +

+ +

+let x: Result<_, _> = try { foo()?.bar()?.baz()? };
+

+ +

This way, you can catch an error without having to create a whole new function.

+ +

The Future: Catch blocks

+ +

+ From what I understand, the original idea was to not reserve try as a keyword. Instead, + the keyword was going to be catch. That idea was dropped, presumably because it would + break with the convention created by every other programming language. But this also leaves the door + open to introduce catch blocks later. +

+ +

+ I haven't found any proposed RFCs for what catch blocks might look like. I think most people don't + want to think about this until try is finished. But people have noted that we have the + option of adding catch later, and the rough syntax isn't too hard to figure out. +

+ +

+let x: Result<f64, _> = try {
+	//...
+} catch error {
+	panic!("Unexpected error: {:?}", error);
+}
+

+ +

We could pattern match on the expression too.

+ +

+let x: f64 = try {
+	//...
+} catch JsonError::ParseNumber(error) {
+	panic!("Failed to parse float: {:?}", error);
+} catch JsonError::Other(error) {
+	panic!("An unexpected error occurred: {:?}", error);
+}
+

+ +

We'd also have to allow try-catch on Option.

+ +

+let array = [1, 2, 3, 4];
+let x = try {
+	array.get(4)?;
+} catch {  // note that there's no reason for a variable to be created here
+           // this would probably desugar to `catch _`
+           // that desugaring would allow this syntax to also be used with Result
+	panic!("wait, what am i doing with my life?");
+}
+

+ +

+ Creating this API would probably also mean we'd have to think about adding a Catch + trait, so that it could be allowed on custom types. Modeling this is difficult, but can be done. +

+ +

+pub trait Catch: Try {
+	type Error;
+
+	fn error(residual: Self::Residual) -> Self::Error;
+}
+
+impl<T, E> for Result<T, E> {
+	type Error = E;
+
+	fn error(residual: Self::Residual) -> Self::Error {
+		let Err(error) = self;
+		error
+	}
+}
+
+impl<T> for Option<T> {
+	type Error = ();
+
+	fn error(residual: Self::Residual) -> Self::Error {
+		()
+	}
+}
+

+ +

In case you're wondering about the desugaring:

+ +

+let x: f64 = match try { /* ... */ }.branch() {
+	ControlFlow::Continue(output) => output,
+	ControlFlow::Break(residual) => match Result::error(residual) {
+		JsonError::ParseNumber(error) => panic!("Failed to parse float: {:?}", error),
+		JsonError::Other(error) => panic!("An unexpected error occurred: {:?}", error),
+	}
+}
+

+ +

+ Does that mean that finally could be added in the future too? Perhaps. I've never been a + big fan of finally blocks. But we can do it. If you're familiar with the +scopeguard crate, then it shouldn't seem too difficult. +

+ +

+let x: f64 = try {
+	//...
+} catch JsonError::ParseNumber(error) {
+	panic!("Failed to parse float: {:?}", error);
+} catch JsonError::Other(error) {
+	panic!("An unexpected error occurred: {:?}", error);
+} finally {
+	println!("finally! we're done!");
+}
+
+// desugars to...
+
+let x: f64 = {
+	defer! {
+		println!("finally! we're done!");
+	}
+
+	match try { /* ... */ }.branch() {
+		ControlFlow::Continue(output) => output,
+		ControlFlow::Break(residual) => match Result::error(residual) {
+			JsonError::ParseNumber(error) => panic!("Failed to parse float: {:?}", error),
+			JsonError::Other(error) => panic!("An unexpected error occurred: {:?}", error),
+		}
+	}
+}
+

+ +

Yeet! We can go even further

+ +

+ Now that we have most of the syntax from languages that have exceptions, let's go even further. + We could consider adding the throw e keyword as syntactic sugar for + return Err(e). +

+ +

+let x: f64 = try {
+	throw JsonError::Other("oh no, an error!".to_string());
+} catch JsonError::ParseNumber(error) {
+	panic!("Failed to parse float: {:?}", error);
+} catch JsonError::Other(error) {
+	panic!("An unexpected error occurred: {:?}", error);
+} finally {
+	println!("finally! we're done!");
+}
+

+ +

+ This isn't available in nightly, because throw isn't yet a keyword in Rust. Worse, we + can't add it as a keyword until everybody agrees on what keyword to use. Some languages, such + Python, use raise instead. +

+ +

+ This problem is known as bikeshedding. People can't agree on what color to paint the bikeshed, so the + bikeshed never gets built. Everybody agrees that having the bikeshed is important, regardless of what + color it is. A common solution to this is to pick an option nobody would ever want. This lets everyone + know that we're not actually going to use that color, so we can and will change it later. This + happened. +

+ +

+#![feature(yeet_expr)]
+
+fn throw_error() -> Result<Infallible, JsonError> {
+	do yeet JsonError::Other("an error has been yeeted");
+}
+

+ +

+ Yep, yeet is the chosen keyword. The do needs to be there because + yeet is not a reserved word, but do is, despite it not being used for + anything. +

+ +

+ The way this works under the hood, is do yeet e desugars to Yeet(e). + Then a couple of FromResidual implementations allow the Yeet type to be + used for error propogation. +

+ +

+impl<T> FromResidual<Yeet<()>> for Option<T> {
+	fn from_residual(_: Yeet<()>) -> Option<T> {
+		None
+	}
+}
+
+impl<T, E, F: From<E>> FromResidual<Yeet<E>> for Result<T, F> {
+	fn from_residual(error: Yeet<E>) -> Result<T, F> {
+		Err(error.0.into())
+	}
+}
+

+ +

+ Now that we've been using yeet for so long, there are some people who want this to be + the new keyword. There was even a proposal to reserve yeet for Rust 2021. It was rejected. +

+ +

Now in Reverse? What?

+ +

+ I had to share this because Rust does not have exceptions. The idea that we could introduce an + exception-like syntax for a language which doesn't have them is amazing to me. +

+ +

This got me thinking, could we introduce Result to a language that doesn't have it?

+ +

Imagine the following C# code, where using try, but without a catch, returns a Result.

+ +

+// I used a wildcard for the error type because C# can throw one of multiple exceptions here
+Result<decimal, _> = try {
+	yield demical.Parse("3.14159");
+}
+

+ +

+ This would be easier in languages where block expressions exist. If a language were to pursue this, + I'd prefer they call the type Except or Exceptional instead of + Result. +

+ +

Conclusion

+ +

+ The main I reason I wrote this post was because, when I proposed a new scripting language in an + earlier blog post, I wanted to talk about how + try/catch would be implemented in it. But I figured that was way too off-topic for that post. So I + wanted to discuss it here. +

+ +

+ My scripting language would have unchecked exceptions, with the option to catch errors and put them + inside of an Exceptional type. +

+ +

+function throws() {
+	throw "oh no"
+}
+
+throws()  // this crashes the script
+

+ +

Wrapping an expression in a try block yields an Except type.

+ +

+function throws() {
+	fail with "oh no"
+}
+
+let x: Except<any, any> = try {
+	throws()  // this doesn't crash
+}
+

+ +

I think it's feasible to use a postfix ! as syntactic sugar for this

+ +

+function throws() {
+	fail with "oh no"
+}
+
+let x: Except<any, any> = throws()!
+

+ +

Then with catch or .catch, the error can be handled

+ +

+function throws() {
+	fail with "oh no"
+}
+
+let x: Except<any, any> = throws()!.catch error {
+	print("an error occurred")
+	exit()
+}
+

+ +

I like this idea. I'm glad I could share it with you.

+ +

+ diff --git a/src/blog/unwind-safety-happylock.kuht b/src/blog/unwind-safety-happylock.kuht new file mode 100755 index 0000000..61c36c8 --- /dev/null +++ b/src/blog/unwind-safety-happylock.kuht @@ -0,0 +1,555 @@ + + + + Poisoning, Unwind Safety, Exception Safety, and More in HappyLock + + + + + +

+ +

Poisoning, Unwind Safety, Exception Safety, and More in HappyLock

+ +

+ I'm proud to announce that HappyLock 0.4 has been released. I thought that I should focus on + poisoning because I thought, at the time, that it would be simple. I was very wrong. Poisoning + exposed a whack-a-mole of challenges to solve, which I will illustrate here. +

+ +

A Refresher on HappyLock

+ +

+ I recommend reading the full article on HappyLock. I've been told it's a very good read. But I'll + briefly explain the idea here. Those of you who have already read the full post can skip ahead to + the new stuff. +

+ +

+ HappyLock uses the Rust borrow checker to make deadlocks impossible at compile-time. This is done by + having a ThreadKey which is not Send, Copy, or + Clone. But it is now Sync. Only one ThreadKey can exist + on each thread at a time. In order to lock anything, you must pass either a ThreadKey + or a &mut ThreadKey into the lock function. This means that in order to + lock anything new, you must first release any resources you have already acquired, preventing partial + allocation. +

+ +

+fn main() {
+	// This panics if the ThreadKey has already been acquired for this thread
+	let mut key = ThreadKey::get().unwrap();
+
+	let mutex1 = Mutex::new(42);
+	let mutex2 = Mutex::new(76);
+
+	thread::spawn(|| {
+		// You're allowed to have more than one ThreadKey, but not on the same thread
+		let key = ThreadKey::get().unwrap();
+
+		let guard = mutex.lock(&mut key); // Note the key. Nothing else can use it now
+		*guard = 24;
+		drop(guard); // Now we can use the ThreadKey again
+
+		let guard = mutex2.lock(&mut key);
+		*guard = 67;
+	}).join().unwrap();
+
+	let guard = mutex.lock(&mut key);
+	assert_eq!(guard, 24);
+	// the guard is implicitly dropped here
+	let guard = mutex.lock(&mut key);
+	assert_eq!(guard, 67);
+}
+

+ +

+ If you want to lock multiple mutexes at the same time, you can use a LockCollection, + which will ensure that all locks are acquired at the same time, so there's no possibility of deadlock. + By default, this works by sorting all of the locks by their memory address, preventing circular wait, + but there are other ways to do this with different performance qualities. +

+ +

+fn main() {
+	let key = ThreadKey::get().unwrap();
+	let collection = LockCollection::new((Mutex::new(42), Mutex::new("foo")));
+	let guard = collection.lock(key);
+	assert_eq!(guard.0, 42);
+	assert_eq!(guard.1, "foo");
+}
+

+ +

+ Lots of things can be used in a LockCollection, which have the Lockable trait. + There's also the RawLock trait, which is implemented for Mutex and + RwLock. +

+ + +

What is Unwind Safety

+ +

+ Unwind safety has nothing to do with the conventional notion of safety in Rust. And although + object-safety has recently been rebranded to dyn-compatible, unwind safety cannot be. The notion + of unwind safety is actually the entire reasoning why poisoning exists. Imagine the following + incredibly contrived scenario. +

+ +

+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&mut self) {
+		catch_unwind(|| {
+			for _ in 0..5 {
+				self.0 += 1;
+			}
+		});
+	}
+}
+

+ +

+ The variant that is supposed to be held here is that a MultipleOfFive is always + divisible by five. But what happens if debug assertions are enabled, and our value is 125? +

+ +

+125 + 1 = 126
+126 + 1 = 127
+127 + 1 ??? integer overflow! panic!
+

+ +

+ But, we caught that panic, so now the value will always be 127, even though 127 is not divisible + by five. This doesn't result in undefined behavior. It's just very bizarre. This is the purpose + of the UnwindSafe trait. It asserts that unwinding won't result in unexpected behavior + for the type. In fact, the code from before doesn't compile. +

+ +

+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&mut self) {
+		catch_unwind(|| {
+			for _ in 0..5 {
+				self.0 += 1; // compile error: mutable references are not unwind-safe
+			}
+		});
+	}
+}
+

+ +

+ But again, this cannot be used to prevent undefined behavior. To make this point clear, there + is a wrappper type in the standard library that actually lets us work around unwind-safety. We + can just use AssertUnwindSafe, which is completely safe to construct. +

+ +

+struct MultipleOfFive(i8);
+
+impl MultipleOfFive {
+	fn increment(&mut self) {
+		let this = AssertUnwindSafe(self);
+		catch_unwind(move || {
+			for _ in 0..5 {
+				(*this).0 += 1;
+			}
+		});
+	}
+}
+

+ +

+ So that begs the question: if mutable references are not unwind safe, why is Mutex + unwind safe? That's because of poisoning. Any time when a panic is caught while a + MutexGuard is in scope, the mutex gets poisoned. Any future calls to lock + on that mutex will return a PoisonError. Then, it becomes the responsibility of the + caller to decide how to handle that error. Most people don't care and just `unwrap` the result. + Most people seem to think that providing poisoning by default in the standard library was a mistake. + Several locking crates, like parking lot and spin, don't include poisoning at all. There's even some + work being done to provide non-poisoning variations of the locking primitive in the standard library. + For HappyLock, I want to provide as many of the standard library's features as possible, so I worked + out an alternative approach where you can get poisoning, but not by default. +

+ +

How to Poison a Mutex

+ +

+ I decided to implement poisoning in the simplest way I could think of. HappyLock is already + filled with wrappers, so why not use one here too? Put simply, the implementation looks like + this: +

+ +

+struct Poisonable<L: RawLock + Lockable> { /* ... */ }
+
+impl Poisonable<L> {
+	// this is way over-simplified but you probably get the point
+	pub fn lock(&self) -> PoisonGuard<L::Guard>;
+}
+

+ +

+ Unlike with LockCollection, Poisonable requires that L be + a RawLock. That's because Poisonable can't decide on its own how to deal + with multiple locks without deadlocking. That's the purpose of LockCollection. But, + RawLock already has a lock method, so it's easy to just call that to + lock whatever we need. +

+ +

+ At the same time, it would be nice if we could put a LockCollection inside of a + Poisonable. So, LockCollection now implements RawLock, + so you can create a Poisonable<LockCollection<Vec<Mutex<String>>>> + and not unwrap every single mutex. +

+ +

+ There's another method that the standard library's Mutex has that is much harder to + implement: get_mut. This is already implemented on HappyLock's Mutex. It + also exists on the lock collections, but instead of getting mutable references to the data being + locked, it actually returns the collection. For example, + LockCollection<Vec<Mutex<i32>>>::get_mut returns a + &mut Vec<Mutex<i32>>. Doing the same thing on a Poisonable would + require calling get_mut twice where the standard library only requires it to be called + once. +

+ +

+ So, I've made a couple more traits: LockableGetMut and LockableIntoInner +

+ +

+trait LockableGetMut {
+	type Inner<'a>;
+
+	fn get_mut(&mut self) -> Self::Inner<'_>;
+}
+
+trait LockableIntoInner {
+	type Inner;
+
+	fn into_inner(self) -> Self::Inner;
+}
+

+ +

+ You might wonder, why not just have the same Inner type on both traits, and then we can + have get_mut return &mut Self::Inner. But consider the case of a tuple. + In order to have a method like get_mut, we have to create a new tuple with a different + type that has no mutexes. But we can't return a mutable reference to a tuple we just created! But, + we can implement the function quite simply with this system. +

+ +

+impl<A: LockableGetMut, B: LockableGetMut> LockableGetMut for (A, B) {
+	type Inner<'a> = (A::Inner<'a>, B::Inner<'a>);
+
+	fn get_mut(&mut self) -> Self::Inner<'_> {
+		(self.0.get_mut(), self.1.get_mut())
+	}
+}
+

+ +

+ For consistency, lock collections now also use this functionality, and the previous into_inner + method is now called into_child. This is a breaking change, but there are other breaking + changes that we'll also need to make here, as we'll soon see. +

+ +

The Exception Safety of HappyLock

+ +

+ Exception safety is a less optional form of unwind safety. The Rustonomicon actually refers to + unwind-safety as "maximal exception safety". But even if we don't always guarantee that safe code + will have the correct behavior, we need to at least make sure that our types are exception-safe + to the point where unwinding does not cause potential unwind safety. Here's an example of how this + could be violated. +

+ +

+impl<T: Clone> Vec<T> {
+	fn push(&mut self, x: &T) {
+		self.reserve(1);
+		unsafe {
+			self.set_len(self.len() + 1);
+			self.ptr().add(1).write(x.clone());
+		}
+	}
+}
+

+ +

+ The problem is that clone can panic, because you can implement it however you want. + If it panics, then the length will be incorrect forever. This is something that you'll always need + to be careful about in unsafe code. Now, look at this function in HappyLock. +

+ +

+impl<L: OwnedLockable> OwnedLockCollection<L> {
+	pub fn lock<'g, 'key, Key: Keyable + 'key>(
+		&'g self,
+		key: Key,
+	) -> LockGuard<'key, L::Guard<'g>, Key> {
+		let locks = get_locks(&self.data);
+		for lock in locks {
+			// safety: we have the thread key, and these locks happen in a
+			//         predetermined order
+			unsafe { lock.lock() };
+		}
+
+		let guard = unsafe { self.data.guard() };
+		LockGuard {
+			guard,
+			key,
+			_phantom: PhantomData,
+		}
+	}
+}
+

+ +

+ As we can see, it is considered undefined behavior in HappyLock to cause a deadlock. Now, what + would happen if we had a collection of three locks, and the second one panicked. The first mutex + would never unlock, and then we could call it again, causing a deadlock, like this. +

+ +

+fn main() {
+	let collection = OwnedLockCollection::new((
+		Mutex::new(1),
+		Mutex::new(2),
+		Mutex::new(3)
+	));
+
+	catch_unwind(|| {
+		let key = ThreadKey::get().unwrap();
+		collection.lock();
+		// We'll say for the sake of argument that our second mutex panics here
+		// The first mutex was never unlocked
+	});
+
+	// The ThreadKey was still dropped, so we can re-acquire it.
+	let key = ThreadKey::get().unwrap();
+
+	// But wait, the first mutex is still locked by this thread.
+	collection.lock(); // DEADLOCK!!!
+}
+

+ +

+ Note that this only becomes a problem if, somehow, parking_lot panics when calling the + lock function. This would be considered a bug, but since you can use whatever + RawMutex you want with HappyLock, I can't guarantee that this will never happen. + This could be solved by just requiring a specific underlying API to be used, but I'm not ready + to impose that restriction (yet). Somebody at RustConf suggested using a fancy guard insertion + strategy so that the mutexes will automatically unlock on panic. That might work, but I have + a simpler solution. +

+ +

+ We can use the scopeguard library to automatically run code when unwinding. What + we'll need to do is keep track of which locks have been locked so far, and then, if we start + unwinding, unlock them. +

+ +

+ Now, if you use the scopeguard crate, this will actually result in a stack overflow, + depending on how rigourously you check for this. It won't check to make sure that the panic was + caused by your function, so it will keep calling itself, and you'll get a stack overflow. So I + made my own utility to check that the unwinding was caused by a specific piece of code +

+ +

+fn handle_unwind<R, F: FnOnce -> R, G: FnOnce()>(try_fn: F, catch: G) -> R {
+	let try_fn = AssertUnwindSafe(try_fn);
+	catch_unwind(try_fn).unwrap_or_else(|e| {
+		catch();
+		resume_unwind(e)
+	})
+}
+

+ +

Then we can use it to unlock on failure, like so

+ +

+unsafe fn ordered_lock(locks: &[&dyn RawLock]) {
+	let locked = Cell::new(0);
+
+	handle_unwind(
+		|| {
+			for lock in locks {
+				lock.raw_lock();
+				locked.set(locked.get() + 1);
+			}
+		},
+		|| attempt_to_recover_locks_from_panic(&locked[0..locked.get()]),
+	)
+}
+
+unsafe fn attempt_to_recover_locks_from_panic(locked: &[&dyn RawLock]) {
+	handle_unwind(
+		|| locked.for_each(|lock| lock.raw_unlock()),
+		|| locked.for_each(|l| l.poison()),
+	)
+}
+

+ +

+ Ok, so I lied when I said there's no poisoning by default. It's not documented anywhere, but yeah. + If the unlock function panics, when we're kinda screwed, so all RawLocks now have to + be poisonable. This is a different kind of poisoning, which causes all future calls to the mutex to + panic, similar to the poisoning of Once. It's not exposed in the signatures for any of + the functions. I don't want you to ever have to think about this kind of poisoning. I emphasize, + this should never happen. If it does, then the RawMutex probably contains a bug that + already needs to be fixed. +

+ +

+ The lock that panicked is poisoned, regardless of whether it was locked or not. That's because I have + zero clue whether or not it actually locked. I would hope that if the lock function + panics, it didn't lock, but I don't know that for sure. I also don't have a good way to check, without + excluding support for certain mutexes in the future. Someone might suggest using the result of + try_lock to check if it's locked or not, and then unlock it in either case. That person + might be surprised to learn that, in C, it is undefined behavior to call try_lock on + a mutex that is already acquired by the calling thread. So there's not much I can do other than panic + here. +

+ +

Miscellaneous Changes

+ +

+ The try_lock function now returns a Result instead of an Option. + This is something I've been thinking about for a while now, and the fact that Poisonable + now exists makes an even more compelling argument for using Result. If something + is already locked, then you can have the key back without having to call ThreadKey::get. +

+ +

+ I've kinda shown this already in some of the examples, but the RawLock trait methods have + been renamed. For example, RawLock::lock is now RawLock::raw_lock. +

+ +

+ Some of the reading APIs have been moved from Lockable to Sharable. The reason + they were in Lockable before was because I had an idea where you could mix sharables + with non-sharables in a lock collection, and then calling read would just get an exclusive + lock if there was no shared lock available for an entry. Eventually I decided this was a bad idea, but + I still had the read_guard method in Lockable. So now it's moved to + Sharable. +

+ +

+ I mentioned this already in the introduction to HappyLock, but ThreadKey is now + Sync. This is possible for the same reason that the nightly Exclusive + type is Sync. A &ThreadKey is completely useless, so no undefined + behavior can be caused because of it. This also allows guards which hold a key (i.e. MutexGuard) + to be Sync. They still can't be send because, among other things, dropping a + ThreadKey on the wrong thread can lead to having multiple ThreadKeys + on the same thread, making deadlock possible. The Rust standard library also doesn't implement + Send on its guard types, so I think this is acceptable. +

+ +

+ I'm now using cargo-diet before I publish HappyLock, so examples are no longer included when you + download it. +

+ +

+ The ThreadKey now uses a Cell<bool> instead of an AtomicBool + when deciding if you can get a key or not. It's a thread-local variable, so there was no + synchronization needed in order to access the value. +

+ +

+ Speaking of which, I've removed the thread-local crate as a dependency and learned + enough to just use the standard library's thread_local macro. It's more efficient + anyway. Also, now that LazyCell is in the standard library, I've dropped the + once_cell dependency. But this does increase the MSRV substantially. +

+ +

+ The guard and ref types now implement more traits like Eq, Ord and + Hash. This would be a breaking change in the standard library, but this is already + a breaking change here. +

+ +

+ I've been using cargo-mutants to help me write better unit tests. This helped me + catch one bug before it was even released. Although, I did still find a bug, so it's not perfect. + HappyLock is in this weird state where it's being used and I'm scared of obvious bugs, but it's + not used enough to the point where obvious bugs are immediately found and fixed. I should + probably start using tarpaulin as well. +

+ +

The Future

+ +

+ I'm still deciding what my next course of action will be for this crate. I should write more tests + for it before I do another big release. The documentation examples could definitely be improved. Some + of my plans for the future have changed. I still would like to try copying the standard library + lock implementations at some point. I no longer think compile-time duplicate checks are possible + due to the lack of const trait methods in Rust. LockCell and ReadOnlyLockCollection are still just + ideas in the back of my mind. But I have acquired a few new ideas since last year. +

+ +

Once

+ +

+ It is definitely possible to make a deadlock-free Once, by having call_once + require a ThreadKey. I tried somehow fitting it into a LockCollection, but + I don't think that's practical, and I don't know why you would ever want more than a single + Once at a time. Although, I can see a point to using a Mutex inside of a + call_once, so I can also provide a way to pass in a RawLock + Lockable with it. +

+ +

+ I'm still not sure if I want to include Condvar. It is useful but I don't think I would + be able to prevent it from deadlocking. I'll keep it in mind though. +

+ +

Async

+ +

+ During my time at RustConf, I realized that the biggest barrier to HappyLock adoption is probably + the inability to use it with async Rust. The problem is that you can have multiple tasks running on + the same thread, so ThreadKey::get() will return None very often. But a + good solution to this would be to have TaskKeys instead, which would only be useful + on the async mutexes. But this is something that the async runtime would need to be able to provide. + But if the spawn function gave you a TaskKey, then there would be no need + to even call a get function for it. The biggest problem here would be that you can't use + a blocking lock, because if it's already locked in a task that runs on the same thread, then this + would cause a deadlock. +

+ +

Expanding Cyclic Wait

+ +

+ A reddit comment gave me an idea on how to pursue this. I don't think I'll go into too much detail + right now, but it would involve a IntoLockIterator trait, several new types, adding + a &ThreadKey to all of the ref guard types, and quite a bit of type-state analysis. + I'll probably talk about this over at the Miami Rust User Group, so join us online if you're + interested. I think we can turn HappyLock from a library that primarily prevents partial allocation + and prevents cyclic wait as an optimization, to a library that is used to prevent cyclic wait + and uses remnants of total allocation to prevent you from screwing up. +

+ +

+ + + + diff --git a/src/index.kuht b/src/index.kuht new file mode 100755 index 0000000..c0a3929 --- /dev/null +++ b/src/index.kuht @@ -0,0 +1,33 @@ + + + + Botahamec's Website + + + +

Botahamec

+ +

+ Hi. This is a website I threw together quickly so that I could write my blog post. It's not + much right now. But you should read my blog posts anyway. +

+ +

Projects

HappyLock (Deadlock-free mutexes)
git-autosave (Autosave for Git)
Exun (Expected and unexpected error handling)
Snob (Snobol-inspired string parsing)

+ +

Blog

+ -- cgit v1.3.1

An Inheritance Detox

The Problem of Inheritance

Replacing Inheritance

Factory Methods

Shapes

Interpreter

Observer

Conclusion

The Best Tool for the Job

My Biases

Systems or Embedded Programming

Parsers and Compilers

Rust

Dart

Scripts

Game Development

Backend Web

Rust (or Swift)

Dart

WebAssembly

Frontend Web

Conclusion

Color Spaces

RGB

HSL

LAB

OKLCH

Comments at the End

Comparing Date Types Across Languages

C

JavaScript

C#

Rust

Conclusion

How HappyLock Works

Background

Mutual exclusion

Non-preemptive allocation

Circular wait

Partial allocation

Exploration

Borrow Checker Rules

A Naive implementation

Lock Collections

Duplicate Locks

The Actual Implementation

Cyclic wait

We'll just create four Lock Collection Types that do mostly the same thing

RefLockCollection

BoxedLockCollection

OwnedLockCollection

RetryingLockCollection

RwLocks

Performance

Future Work

Poisoning

OS Locks

Compile-Time Duplicate Checks

Expanding Cyclic Wait

A LockCell type

Readonly Lock Collections

No Standard Library

Other Types from the Standard Library

Conclusion

What Other Distros Can Learn from NixOS

Background

Testing

Beta Channel

Rollout

Rollback

Distribution

Conclusion

Named and Optional Arguments are Awesome

How Other Languages Handle Named Parameters

Dart

C#

TypeScript

Rust

Why Rust Needs Optional Parameters

Proposals for Named Arguments

`RefLockCollection`

`BoxedLockCollection`

`OwnedLockCollection`

`RetryingLockCollection`

A `LockCell` type

The `pub` keyword

Alternative: Implementing `Fn` traits

In the Beginning: The `Result` type

Introduced Later: The `?` operator