DEV Community: Sean Williams

A cool programming-based game

Sean Williams — Tue, 02 Aug 2022 23:27:56 +0000

The game is called Bitburner, and I have no affiliation with it. I just think it's cool.

You mostly play the game through a terminal, which allows you to create files and run JavaScript programs. It contains a JavaScript interpreter, but also allows you to run scripts natively. (I think this is done similarly to "bookmarklets.") Native scripts mainly have the drawback of being able to hang the game, so you have to be diligent about explicit sleeping in long loops.

Anyway, the game provides an API that allows you to take game actions (otherwise you write straight JavaScript, so you have its control flow and collections and the like), and as you get further in you get access to more APIs that let you automate more and more things.

It seems to me like a fun way of working on your programming skills.

Meditations on concurrency

Sean Williams — Tue, 26 Jul 2022 23:01:58 +0000

My business is auto repair, which has been a bit of a journey from computer science. On the other hand, auto repair is a surprisingly software-reliant field. I don't just mean this in the sense that cars have more computational elements in them, though that's an issue too.

Many business could be run with just paper, though it would be burdensome. Auto repair has a few special problems, though.

First, job times are standardized. Nearly every job that could be done to nearly every car has a benchmark time it should take a competent technician to complete. This means, if your shop is legitimate, the price of a job should be: the book time for the job * the shop's labor rate + the cost of parts required to do the job * (1 + the shop's parts markup) + nominal overhead.

Second, every car is different, often in bizarre ways. In the old days there were big service manuals for every year for every make and model—these still exist, but in practice they've been displaced by software. Even if you can figure out how to do a job on your own, you often need specs—how much to torque down a bolt, how much fluid to add, that sort of stuff.

Third, if you're good enough to do electrical diagnosis and repair, you need wiring diagrams.

Yes, auto repair preexists computers, but cars were a lot simpler in those days. Not surprisingly, the currently available software for running an auto repair shop—isn't great. Our biggest problem is one of concurrency: Our current software can be run in a client/server mode over a local network. When a work order is up on one computer, other computers are fully locked out.

This has led to me thinking a lot about how concurrency should be handled in this situation, since I'll soon start writing our own shop management software.

Race conditions

The principal issue is what we call "race conditions." Imagine you have a shared variable x, initially 0, and five threads all run x++. What happens? It's tricky because the definition of x++ looks more like this:

load x into register1
add 1 to register1
store register1 into x

The final value of x could be anything between 1 and 5, depending on how instructions interleave. For example, just looking at two threads, you could have:

thread 1: load x [r = 0]
thread 1: add 1 [r = 1]
thread 1: store x [x = 1]
thread 2: load x [r = 1]
thread 2: add 1 [r = 2]
thread 2: store x [x = 2]

In this case, x is 2. The instructions could also play out like this:

thread 1: load x [r = 0]
thread 2: load x [r = 0]
thread 1: add 1 [r = 1]
thread 2: add 1 [r = 1]
thread 1: store x [x = 1]
thread 2: store x [x = 1]

In this case, x is 1.

This opens up into a whole lot of other stuff: mutual exclusion (mutex) locks, semaphores, transactions... You introduce special processor instructions, like "atomic check and set," which can do

if(x == 0) {
  x = 1;
  return true;
}
else {
  return false;
}

in a single cycle. This lets you start doing stuff like,

int lock = 0;

void foo() {
  while(!atomic_check_and_set(lock)) {
    sleep(100);
  }
  // Do some stuff, knowing that other threads won't interfere
  lock = 0;
}

This requires a lot of diligence to get right; it's very easy to hang your program by improperly handling locks. This is also why focus has shifted to "safer" things like promises and work queues.

There's one other problem with locking that's worth mentioning. Locking should have some level of granularity, where there are different locks for different data. What if a thread needs three locks? More importantly, what if multiple threads need overlapping subsets of locks? One thing you absolutely should not do is:

int lock1 = lock2 = lock3 = 0;

void foo() {
  while(!atomic_check_and_set(lock1)) sleep(100);
  while(!atomic_check_and_set(lock2)) sleep(100);
  while(!atomic_check_and_set(lock3)) sleep(100);
  // do stuff
  lock1 = lock2 = lock3 = 0;
}

If there's another function that looks like this:

void bar() {
  while(!atomic_check_and_set(lock3)) sleep(100);
  while(!atomic_check_and_set(lock2)) sleep(100);
  while(!atomic_check_and_set(lock1)) sleep(100);
  // do stuff
  lock1 = lock2 = lock3 = 0;
}

you can run into a situation where a thread executing foo takes lock1, while a thread executing bar takes lock3. One of them will then take lock2, but at this point both threads will hang indefinitely.

Time scales

The issue exposed by our shop management software is the problem of time scales. Holding a lock for 200 ms is fine in smaller-scale environments. Holding a lock for eight hours will piss people off. This is the difference between "batch processing" speeds, versus user interface speeds.

The obvious lesson is that you should avoid holding locks while waiting for user input. Among other things, you don't know if the user is even at the computer!

The above discussion about locks is apparently nowadays called "pessimistic concurrency control." The alternative that gets suggested is "optimistic concurrency control," in which you allow concurrent memory access to proceed but roll back or merge in case of conflicts.

This approach makes sense in situations with very high utilization. At the smaller scale, especially a smaller scale where the users are auto mechanics, I think it's a bad idea to drag in merge semantics. I mean, programmers themselves already have significant heartburn with Git merge—subjecting auto mechanics to merging sounds inhuman.

Live updates

I decided to approach this problem, not as a programmer, but as a normal person. Nearly everything in computing is some sort of metaphor for real life: there's a reason the base of most graphical operating systems is called a "desktop," and that "files" are stored in "folders." Even the older term "directory" is—well, for the youngsters out there, you used to use directories to look up phone numbers.

The main reason for this is, you ought to try and make computing intuitive. That means having a handle on intuition: what will people find intuitive? Conflict merging in the real world is incredibly tedious, and made up of judgment calls and "who has final authority?"

What about the more basic question: what are real-world situations in which we have concurrent access to a shared medium? I realized, that happens all the time, it's so common that it's nearly invisible. Namely, having a conversation. People manage conversations not through complicated technical rules, but through—for lack of better words—courtesy and willpower. You and I talk at the same time. Do I stop speaking, do you? If we both stop, who starts talking? If we both keep talking, who blinks first?

For the purposes of concurrent access, these questions don't need to be answered—it suffices that people manage conversations, and we call that management "social convention." This made me realize, smaller-scale concurrent access can be handled with live updates, like Google Docs.

That is, commit changes as they're made, and have those changes immediately reflected to other users. Yes, users can create race conditions, but this isn't a technical problem—it's a social problem. Users will instinctively see the possibility of race conditions (without knowing that term) because they'll see what other users are working on. Prosocial users will avoid conflicting changes; antisocial users can be disciplined.

There are some algorithmic problems with doing this well, and I'll post about them later. You still need to do three-way merging, for example, and you need to keep the text input cursor in a reasonable place. But this solution does bring locking back to the batch processing timescale, in a way that ought to be intuitive to normal people.

This is a work in progress, of course, but I think it's interesting enough to be worth posting about.

What is a computer?

Sean Williams — Tue, 12 Jul 2022 21:39:48 +0000

At the close of the 19th Century, it was thought that math and science were about to be "solved," and all that remained was cleaning up some of the details. The famous mathematician David Hilbert posed what he considered the last big questions. One of them was called the Entscheidungsproblem, meaning Decision Problem. The question was:

Given a set of axioms in first-order logic, can you create a mechanical process for deciding whether a particular proposition is true?

The first step in solving this problem was to figure out what constitutes a mechanical process for solving logic problems. Two great mathematicians came to the fore: Alonzo Church and Alan Turing. Church came up with a mathematically oriented process, called lambda calculus, and Turing came up with a mechanically oriented process, the Universal Turing Machine.

Both mathematicians proved that, for the problem-solving processes they devised, the answer to the Decision Problem is "no." They got to this answer through another, better known problem:

Given an algorithm and a set of inputs, can you prove whether the algorithm will fall into an infinite loop?

What they actually proved is that the answer to this question, the Halting Problem, is "no." The undecidability of the Decision Problem is an extension of the undecidability of the Halting Problem.

Indeed, this is one way of defining computers: a computer is a machine for which the Halting Problem is undecidable.

The limits of analysis

One of the more eye-opening things for me, as a computer science student, came from the required graduate-level theory course. We looked at proofs about the behavior of computer programs. Proofs generally work by substituting things for equivalent things, to change the form of some logical statement into a form you're happier with.

When it comes to computer programs, this breaks down once you have a loop. What's the value of a loop? Sometimes you can work this out; sometimes you can prove that a loop "reduces its problem space" with each iteration until you collapse down to a particular value. OpenMP, a sort of extension library for C/C++, allows you to automatically parallelize loops that take on certain "canonical forms." The strange programming language Idris automatically detects certain recursive patterns that are guaranteed to produce a value.

But for the most part, the value of a loop is unknowable. After all, outside certain special cases, you can't prove whether a loop will take on any value at all. Computer scientists have a special name for this: bottom, indicated by the symbol ⊥. ⊥ is the value of a "divergent computation," or, one for which we don't know if it'll ever actually produce a value. (⊥ is also the value of exceptions.)

The most obvious consequence of this is quite simple: a computer program cannot robustly write another computer program. In order to write a robust program-writing-program, you need to understand what the inputs and outputs of each piece of the program will be—just as normal programming is about understanding the flow of input and output.

If we try to model a computer program, which is the first step in writing a program to write programs, most of the inputs and outputs will be ⊥, and you can't analyze ⊥. After all, ⊥ isn't any particular value; there's no equivalent thing you can substitute into the proof. It's a sort of logical black hole, an immovable logical object.

The other obvious consequence of this is that we are nothing like computers. The Halting Problem presents some obstacles to programming, or rather to testing, but we can look at looping code and figure out what it's supposed to do. We also have problem solving intuitions that let us sort out when the loop isn't doing what it's supposed to, and bring it more into line. I don't know what problem solving intuition is, but I know for a fact that it isn't computation.

What about compiler optimization? The truth is, compiler optimization starts by breaking your code down into "basic blocks," which are runs of code that contain no branching. No ifs, no loops, no function calls. Basic blocks can be robustly analyzed, but they're also not Turing complete.

This is also the reason that the dream of "programming for business managers" has never worked out (despite decades of trying). Once your needs exceed the walled garden of curated functionality you can mix and match in a reasonably safe way, you're back to normal programming.

What a computer isn't

Another dream that hasn't panned out very well is declarative programming. Prolog is a language that purports to allow you to answer questions in propositional logic. Of course, computing began with the fact that you can't do that.

Indeed, Prolog programs are highly sensitive to the order in which statements are presented. This is because Prolog programs are still dynamical processes: there's still an evaluation system that does recursive descent to determine the truth of the logic you present it.

This gets to the most important point of what computers aren't: they are not logic machines. They contain integrated circuits that are designed from logical principles, but that no more makes them logic machines than the presence of silicon makes a beach a computer.

Similarly, the standard engineering tool for complex math used to be the slide rule. A slide rule is based on a more fundamental principle of what addition is: if you walk forward 6 feet, then you walk forward 3 feet, you've walked forward 6 + 3 = 9 feet. Is walking forward the essence of arithmetic?

Physically, a slide rule is just one bar that's allowed to slide between two other bars. You do addition by sliding the inner rule such that its 0 mark lines up with the left operand on the outer rule, going forward on the inner rule a distance equal to the right operand, and reading the value at the same place on the outer bar. This acts like doing addition with a tape measure: to do 6 + 3, start from a wall and measure out 6 feet and mark the position. Measure an additional 3 feet from your mark, and mark that position. Now measure the distance from the wall to the second mark.

Slide rules do another trick, though. Knowing that log(a * b) = log(a) + log(b), you can logarithmically scale the tick marks and thereby add log(a) to log(b). Look up the position of log(a) + log(b) on the same logarithmic scale, and the result is a * b.

Does this mean that arithmetic is the essence of tape measures and slide rules—that a couple of sticks with notches on them "do" math? In a certain sense the answer is "yes," but accepting that answer also forces math to come down from the mountaintops and linger with us commoners.

In terms of Plato's cave, though, the answer is obviously "no." Adding some transistors doesn't make computers any more of "mathematical entities" or "pure abstracta" than tape measures.

What computers are

A friend of mine has the best, but also most obtuse, characterization of computers: he says they're instruments for which we control the output. With most instruments, a voltmeter for example, the output is some sort of fact of the world. Also, instruments are calibrated to react to the world in certain predictable ways, but it's the world that determines how far the needle moves.

Computers are a strange situation in which we condition the input and control the output. In my experience, this means computers only have two fundamental uses: accounting and control.

Accounting is a situation where we've created a system for ourselves, and we've set up the rules about how inputs should be conditioned (debits = credits) and what the outputs should look like (e.g., profit and loss statement). If the output were a fact of the world, it would be unnecessary to use a computer. This shows us another fact of computing: a bug is when the computer produces the wrong output.

This is the most fundamental problem with artificial intelligence, by the way. One thing that's very clear about AI research is, it has no interest in relinquishing control over the output—after all, AI is joined at the hip with "model validation." But then again, there isn't really such a thing as a computer for which the programmers don't control the output. This is, in my opinion, a rather meager view of "intelligence."

Control is a situation where you want to drive some real-world process according to rules you've set up. Cruise control is meant to keep your car's speed in a range around some set point, and it does that by adjusting the throttle. We still control the output in this situation, but the output is not the car's speed—it's how open the throttle is. Controlling speed is the goal, but it isn't what the program does.

Anyway, most computer programs you and I write are reskinned accounting systems. Video games are accounting systems, just with much fancier user interfaces. Even large scientific simulations are no different: almost all of the actual work in simulation design goes into having it produce correct output. If this sounds anathema to your understanding of the scientific method, then I'm sorry to be the bearer of bad news.

You should, though, feel better about the fact that it's provably impossible for you to optimize yourself out of the job, at least in the aggregate.

How to Do Away with Floating Points

Sean Williams — Fri, 08 Jul 2022 01:29:46 +0000

Don't get me wrong, floating points are good for a lot of things, but their inaccuracy is well known. The basic issue is that floating points are based on a m*2^p approach. If p is negative you get fractions, since for example 2^-1 = 0.5, 2^-2 = 0.25, and so on.

The reason you can get funky behavior with floats is because the denominator must always be a power of two, so denominators that aren't powers of two are approximated. This is why you can compute something that should be 0.3, but end up with 0.29999999999999.

I took some accounting classes after I pivoted into business, and got madder and madder about having to round my own fractions when using a REPL as a calculator. Eventually I sat down and wrote a precise fractional calculator. Which is harder than it seems.

As a brief reminder, a rational number is a pair of integers p ÷ q, for example, ½. Integers are also rationals, with q = 1. They're called rationals because they express a ratio, if you were wondering.

Floating-point is technically a rational number format, but it's often used to approximate real numbers. Real numbers include those that can't be represented as a fraction of integers, like π and sqrt(2).

To finalize the intuition about why floating-point "drift" occurs, consider that decimal is also a rational number system. However, decimal only allows a finite representation of rational numbers for which the prime factorization of the denominator only contains 2 and 5.

Explicit Rationals

Another approach to rational numbers is to store them as a pair of integers. I'll quickly lay out the algorithms for doing this:

Prime Factorizing: x

factors = []
limit = floor(sqrt(x))
for d in 2 to limit:
  while x > 0 and x % d = 0:
    factors.append(d)
    x = x / d
  if x == 0:
    break

Putting into Lowest Terms: p / q

Compute the prime factors of p and q. For each factor f present in both, divide both p and q by f. Alternatively, divide p and q by the product of their common factors.

Addition: p1/q1 + p2/q2

Compute the prime factors of q1 and q2, call them f1 and f2. For each factor f in f1 that isn't also in f2, multiply p2 and q2 by f. For each factor f in f2 that isn't also in f1, multiply p1 and q1 by f.

This has the effect of setting q1 = q2. The result is (p1 + p2) / q1, but for housekeeping purposes you should put this into lowest terms.

Subtraction: p1/q1 - p2/q2

Multiply p2 by -1, then apply the addition algorithm.

Multiplication: (p1/q1) * (p2/q2)

This is much easier, it's just (p1 * p2) / (q1 * q2), put into lowest terms.

Division: (p1/q1) / (p2/q2)

This is equal to (p1/q1) * (q2/p2).

Find a library for the above

You can probably find a library that implements all of this, but it's worth spelling it out so you can see what working with rationals is like. For example, Rust has a num_rational crate.

Parsing a rational

If you have a decimal number, say 0.25, this is equivalent to 25/100, which reduces to 1/4. (factors of 25: 5, 5; factors of 100: 2, 2, 5, 5; common factors: 5, 5 = 25; 25 / 25 = 1; 100 / 25 = 4.) So for example, you can get the numerator by removing the dot and parsing it as an integer, and if there are d digits after the dot, the denominator is 10^d.

Displaying a rational

This is the hardest part by far, and the real reason behind this post. The trivial way of displaying a rational is as p.to_str_radix(10) + "/" + q.to_str_radix(10). If q is 1, the number is an integer so really you should only display p.to_str_radix(10).

What about decimal expansion? In theory there are two cases: finite and infinite. Infinite expansions are periodic, for example, 1/3 = 0.(3), and 1/6 = 0.1(6). In practice, there's a third case: periodic expansions can be very, very long, and displaying thousands of digits for a correct expansion isn't very helpful.

Figuring out whether you're in a finite or infinite case is easy: a rational with a finite expansion for decimal output is one where the prime factors of q contains only 2 and 5. In that case, we can work out the expansion using long division (here I'm calling the terms of the rational n and d, for numerator and denominator):

fn unsafe_bigint(x: i32) -> BigInt {
    x.to_bigint().unwrap()
}

fn long_divide_finite(n: BigInt, d: &BigInt) -> String {
    let zero = Zero::zero();
    let ten = unsafe_bigint(10);
    let mut n = n;
    let mut result = String::new();
    loop {
        if n == zero {
            return result;
        }
        let (q, r) = n.div_rem(&d);
        result.push(digit_to_char(&q));
        n = r * &ten;
    }
}

Though it may be strange to see it written out like this, you learned this algorithm in like third or fourth grade.

Now, infinite expansions are trickier. An infinite decimal expansion consists of two parts: a fixed prefix, and an infinitely repeated periodic section. For example, in 1/3, the prefix is empty, and the periodic section is just 3. In 1/7, the prefix is empty, and the periodic section is 142875. In 1/6, the prefix is 1, and the periodic section is 6.

It turns out, there's a formula of sorts for calculating the length of the prefix, which we'll call s, and the length of the periodic section, which we'll call t. The formula is: 10^s is congruent to 10^(s + t) (mod d). Another way of writing this is, we need to find the values of s and t that satisfy: (10^s - 10^(s + t)) mod d = 0.

Because of the third case, we need to figure out the largest s + t we're willing to accept. You don't have to do this, and you can just write a loop of the form,

for s in 0..infinity:
  for t in 1..s:
    if (10^s - 10^(s + t)) mod d == 0:
      return (s, t)

It can just take a long time, and give you an unsatisfying result. My way looks like this:

static MAX_EXPANSION: usize = 50;

fn prefix_and_period(d: &BigInt) -> Option<(usize, usize)> {
    let zero = Zero::zero();
    let ten = unsafe_bigint(10);
    let mut s_pow: BigInt = One::one();
    for s in 0..MAX_EXPANSION {
        let mut t_pow: BigInt = unsafe_bigint(10);
        for t in 1..(MAX_EXPANSION + 1 - s) {
            if (&s_pow - &s_pow * &t_pow).mod_floor(&d) == zero {
                return Some((s, t));
            }
            t_pow = t_pow * &ten;
        }
        s_pow = s_pow * &ten;
    }
    None
}

If this returns Some, then we have a feasible infinite expansion, and we again do long division: after reaching the decimal place, expand out s times, then insert a '(', then expand out t times, then insert a ')', and we're done.

fn long_divide_infinite(n: BigInt, d: &BigInt, s: usize, t: usize) -> String {
    let ten = unsafe_bigint(10);
    let mut n = n;
    let mut s = s;
    let mut t = t;
    let mut result = String::new();
    if s == 0 {
        result.push('(');
    }
    loop {
        if t == 0 {
            result.push(')');
            return result;
        } else {
            let (q, r) = n.div_rem(&d);
            result.push(digit_to_char(&q));
            n = r * &ten;
            if s == 0 {
                t = t - 1;
            } else if s == 1 {
                result.push('(');
                s = 0;
            } else {
                s = s - 1;
            }
        }
    }
}

For a very long expansion, we just expand it out MAX_EXPANSION times and add a "..." to the end, so we know this was a truncated expansion:

fn long_divide_infinite_trunc(n: BigInt, d: &BigInt) -> String {
    let ten = unsafe_bigint(10);
    let mut n = n;
    let mut result = String::new();
    for _ in 0..MAX_EXPANSION {
        let (q, r) = n.div_rem(&d);
        result.push(digit_to_char(&q));
        n = r * &ten;
    }
    result + "..."
}

The functions above only expanded the fractional portion of a number—the part that comes after the decimal point. The case breakdown looks like this:

fn show_rational(x: &BigRational) -> String {
    let one = One::one();
    let ten = unsafe_bigint(10);
    let a = x.abs();
    let n = a.numer();
    let d = a.denom();
    let negative = x < &a;
    let mut result = String::new();
    if negative {
        result.push('-');
    }
    result = result + &n.to_str_radix(10);
    if d == &one {
        return result;
    }
    let (ipart, fpart) = n.div_rem(d);
    result.push('/');
    result = result + &d.to_str_radix(10);
    if is_finite(&d) {
        result = result + " = ";
        if negative {
            result.push('-');
        }
        result = result + &ipart.to_str_radix(10);
        result.push('.');
        return result + &long_divide_finite(&fpart * &ten, &d);
    } else {
        match prefix_and_period(&d) {
            Some((s, t)) => {
                result = result + " = ";
                if negative {
                    result.push('-');
                }
                result = result + &ipart.to_str_radix(10);
                result.push('.');
                return result + &long_divide_infinite(&fpart * &ten, &d, s, t);
            }
            None => {
                result = result + " \u{2248} ";
                if negative {
                    result.push('-');
                }
                result = result + &ipart.to_str_radix(10);
                result.push('.');
                return result + &long_divide_infinite_trunc(&fpart * &ten, &d);
            }
        }
    }
}

The Unicode \u2248 is ≈, again to make sure we know this is only approximate. But this gives us the results we'd hope for...

5
5/2 = 2.5
5/3 = 1.(6)
5/6 = 0.8(3)
5/7 = 0.(714285)
5/1003 ≈ 0.00498504486540378863409770687936191425722831505483...

Now just make a simple REPL, and you can do your accounting homework in peace, knowing your numbers will always be accurate.

The Strange Art of Code Reuse, Part 3

Sean Williams — Tue, 05 Jul 2022 23:41:20 +0000

The first two parts of this series talked about dynamic typing, then object-oriented programming. Along the way, I tried to get across some notions of what polymorphism is. When you have a function take an argument of some type, there are two issues: first, what operations can be done with that type, and second, what are the semantics of that type?

The semantics of primitive types have been ingrained in us since elementary school. Integers are for counting, rational numbers are for ratios, booleans are for logic, and strings are for reading and writing. Once you start structuring data, you need to come up with your own semantics: vec3 is a position in a three-dimensional vector space, array is an ordered list of things, Person is information about a person in the real world.

I dislike dynamic typing because it has sloppy semantics, and you can even see that at the primitive level. JavaScript coerces all numbers to double, which degrades its use for counting. This also means that you don't know off hand whether a number in JavaScript is for counting or for ratios.

Object-oriented programming encodes semantics, particularly for structured data, into a sort of data taxonomy. If your data don't rigidly conform to your taxonomy, then you either have to refactor, or you have to hack. Interfaces ease the restrictiveness of class hierarchies, but in my experience this fact isn't appreciated as much as it should be. Even then, interfaces have the problem that you can't generally tack them onto classes you bring in from the outside (i.e., from an API).

This brings us to Haskell, the ivory tower of programming languages. It's not the tallest tower out there, but that doesn't make it any less ivory.

`eat :: ∀t, t ∈ Edible: t → IO ()`

For lack of a better term, I'll be referring to the Haskell-style type system as category programming. At first blush, category programming is focused on interfaces, though they're called typeclasses. The caveat is that interfaces can be implemented on existing types, including primitive types. For example, the Haskell analog of ToString is a typeclass called Show, defined as follows:

class Show t where
    show :: t -> String

While the syntax may be unfamiliar, you probably already know everything going on here. t is a generic type parameter, much like std::vector<'t> in C++ or List<'t> in C#. Like interfaces, the typeclass Show defines one or more function "templates," so all we specify here is a signature. :: is a type annotation, and -> indicates a function.

So Show is a typeclass containing one function, show, which takes a value of type t and returns a String. We can then add types to a typeclass with instance. For example,

-- Define a Vec2 type, which just contains two doubles
-- Don't stress the syntax right now
data Vec2 = Vec2 Double Double

instance Show Vec2 where
    show (Vec2 a b) = "(" ++ show a ++ ", " ++ show b ++ ")"

The basic Haskell library already implements Show on many types, including Double—much like how Dotnet defines ToString on double. Let's dive into the original example problem, of making a generic function to add elements to a collection:

{-# LANGUAGE FlexibleInstances, MultiParamTypeClasses #-}
import Data.Set as Set

class AddToCollection c e where
   add_to_collection :: e -> c e -> c e

instance AddToCollection [] t where
    add_to_collection e c = e : c

instance Ord t => AddToCollection Set t where
    add_to_collection e c = Set.insert e c

Okay so there's a lot going on here. Let's agree to ignore FlexibleInstances and MultiParamTypeClasses and focus on the meat. First and foremost, we had no difficulty putting basic API types into this class, which is great. But what's going on with these type signatures?

Let's start from a more basic point, which is "currying." In ML-style languages (including Haskell and F#), you don't surround arguments to function calls in parentheses. Instead, functions have "free variables," and applying a value to a function "closes" one of them. So Set.insert is a function with two free variables, t -> Set t -> Set t. We apply a value e to it, which closes it to Set t -> Set t, then we apply a value c to it, which closes it all the way to just Set t.

This same logic applies to types. Dotnet Generic.List is a type function, while Generic.List<int> is a type. Generic.List has a free type parameter; passing it the type int gives us a concrete type. Dotnet requires you to surround type arguments in angle-brackets, while Haskell allows type arguments to be curried.

So let's look at

class AddToCollection c e where
   add_to_collection :: e -> c e -> c e

again. c is a type function, and e is a concrete type. The add_to_collection function takes an element (of type e), and a collection (of type c e). At this point, this isn't very different from a C# function taking arguments of type int and List<int>. The difference is, to my knowledge, C# doesn't let you define interfaces with type functions as generics.

And what about this:

instance Ord t => AddToCollection Set t where
    add_to_collection e c = Set.insert e c

The default Data.Set is tree-based, and operations on sorted trees require the elements of the tree to be comparable, with > and <. Since Haskell was made by mathematicians, the class of types that define less-than and greater-than is called ordinal, meaning, they can be ordered. Ord t is a type constraint: we say that t must be ordinal.

This also lets us take a glimpse at the formality behind all of this. The reason we need the Ord t constraint is because of the type of Set.insert:

insert :: Ord t => t -> Set t -> Set t

The add_to_collection function, as defined for Set t, applies the Set.insert function to e and c. Set.insert requires that its first argument be of an ordinal type, and that its second argument be a Set of ordinal types. This requirement gets re-imposed on our function, add_to_collection.

Now, what exactly is t? Let's again compare it to something more familiar: what is an integer, or maybe, what is a 32-bit integer? The answer to that is, it's a whole number between -2,147,483,648 and 2,147,483,647. So int32 isn't a particular value, but it's a range of values. Better said, int32 is a set, and a value of type int32 is a member of that set.

t is similar: t is the set of all possible types. Ord t => narrows this down, where t is any type in the set Ord. Remember, Ord is a typeclass, and types can be added to a typeclass with instance. Many types are in there by default (including Int and Char), and we can add any other types we want.

Earlier we defined a type of two-dimensional vectors. As it stands, this doesn't work:

data Vec2 = Vec2 Double Double

vec2set = add_to_collection (Vec2 5 2) Set.empty
-- error: No instance for (Ord Vec2) arising from a use of 'add_to_collection'

Okay, so we need Vec2 to provide an instance of Ord...

instance Ord Vec2 where
    compare (Vec2 a1 b1) (Vec2 a2 b2) =
        if a1 == a2 then compare b1 b2 else compare a1 a2
-- error: No instance for (Eq Vec2) arising from the superclasses of an instance declaration

It turns out, classes can require other classes, and Ord requires Eq, which defines equality. Okay, so...

instance Eq Vec2 where
    (Vec2 a1 b1) == (Vec2 a2 b2) = a1 == a2 && b1 == b2

And now we're good, we can now have a Set of Vec2 since we've satisfied all the requirements (including the earlier definition of Show, which is required to pass something to print):

main :: IO ()
main = print (add_to_collection (Vec2 5 2) Set.empty)
-- output: fromList [(5.0, 2.0)]

This probably shows you why Haskell has the reputation it does: To explain object-oriented programming, I just gestured at the idea of taxonomy and your intuition did the rest of the work. To really explain category programming, we had to get knee-deep in theory. The plus side is, this is a system of such staggering flexibility that, as long as you keep your distance from the Entscheidungsproblem, you can do nearly anything you want.

I'm going to close out on one cool feature that you kind of need this level of complexity to tackle. I mentioned way back at the beginning that dictionaries are weird. If you have a dictionary that contains an entry "a": 5 and you add "a": 3, what's the correct thing to do? As usual this depends on your dictionary's semantics, but often the best thing to do is to set "a" to 8.

But let's think big: what I'm really talking about is having insertion semantics that are specific to the type of the dictionary's values. The dictionary type in Haskell is called Map, and as in Dotnet's Generic.Dictionary, it has two type parameters. Because of this, let's sidestep an even more obscure issue called "higher-kinded polymorphism" and define a new typeclass:

class AddToMap k v where
    add_to_map :: k -> v -> Map k v -> Map k v

Map defines a function insertWith: we pass it a function, and if a key is already present in the Map, it combines the old and new values using that function; otherwise it inserts the value. We can use it to create instances of AddToMap that are specialized to particular value types:

instance Ord k => AddToMap k String where
    add_to_map k v c = Map.insertWith (++) k v c

instance Ord k => AddToMap k Int where
    add_to_map k v c = Map.insertWith (+) k v c

++ is string/list concatenation, while + has the usual meaning. So if we have a Map of Strings, overwriting an existing key instead concatenates, while if we have a Map of Ints, overwriting an existing key instead adds:

main :: IO ()
main = do
    print (add_to_map "a" (5::Int) (add_to_map "a" 3 Map.empty))
    print (add_to_map "message" "hello" (add_to_map "message" " world" Map.empty))

-- output:
-- fromList [("a",8)]
-- fromList [("message","hello world")]

Conclusion

There's no question that category polymorphism is the most powerful of the type systems considered here. This doesn't mean I think everyone should use Haskell, or that you should try to convince your company to switch to Haskell, or anything like that. The point of this series was to be informative, not persuasive. Indeed, in practice, there are enormous drawbacks to using Haskell, but understanding Haskell can teach you a lot about computer science.

That is the one thing I'll definitively say about all this: I don't care whether you use Haskell, but you should absolutely learn it. I mean, I hardly ever use it, but the knowledge I gained from learning it is indispensable.

This is also the core reason that Rust is my current favorite language: Rust's traits are very similar to Haskell's typeclasses, but I think Rust has better handling of other stuff, particularly mutable state. Also Rust is incredibly fast.

Now all it needs is a good GUI library...

In any case, if you made it through all this, I hope you gained a deeper appreciation for polymorphism, and the three-way trade-off between code reusability, semantic stability, and language complexity.

The Strange Art of Code Reuse, Part 2

Sean Williams — Sun, 03 Jul 2022 20:05:04 +0000

Fundamentally, the problem of code reuse is this: when you have structured data—collections, structs, objects, discriminated unions, whatever—and you have a function that takes structured data as an argument, which structured types are allowed?

Part one, besides talking about what this looks like in dynamic typing, also revealed some of the intuition behind this question. It really comes down to what your function is going to do with your data. Part three will formalize this idea—it turns out that you can pose this as a logic problem, which was demonstrated way back in 1969—but we're not quite there yet.

In dynamic typing, "what you can do with an object" really comes down to "what methods are defined on that object." Dynamically typed languages are generally based on the idea that objects are dictionaries. A "length" method on an object is just something like,

obj.length = function() { ... }

though doing this correctly requires using a constructor to do a lexical closure on the object self-reference, as in,

function make_obj() {
    obj = { ... };
    obj.length() = { obj.something_or_other };
    return obj;
}

These languages then allow you to do dictionary lookup with "dot notation," where obj.length() is equivalent to obj["length"]().

Anyway, my criticism of this approach is that two methods having the same name does not imply they have the same semantics. It's worth throwing in an important caveat, though: computers are not semantic machines. The only thing you can do to improve programming is to have more disciplined programmers, but language design has a role to play in instilling or "normalizing" discipline. So really my problem with dynamically typed languages is that they encourage sloppiness.

Anyway, we're done with dynamic typing. Now that we're into static typing, it's time to talk about the most popular form of code reuse.

Hot Dogs and Other Sandwiches

While the base requirement for code reuse is that we have a shared set of operations we can do with our function arguments, what we really want is shared semantics. In a sense, this is a philosophical problem. The most popular answer, both in CS and out in the world generally, is taxonomy.

Taxonomy is where you create conceptual parent-child relationships between categories. Scientists have created elaborate taxonomies for all sorts of things in the natural world: the kingdom-phylum-class-order-family-genus-species categorization of life, for example, or the Berzelian classification system for minerals.

Of course, I'm talking about object-oriented programming. The core feature of OOP is inheritance, which says that a class is a more specialized version of another class. If you have parent class A and child class B, then B must provide an implementation of all properties and methods on A—and it can provide some more methods and properties if it wants to. Of course, if A is a concrete class, B starts out with default implementations for everything on A, namely, the implementations provided on A.

Because of this, if a function expects an argument of type A, then it can also take an argument of type B. Taking a type A argument means that you'll only be able to access properties and methods specified on A, which as I said, B must also provide by virtue of being a child.

The example problem in the first part is in one sense easy to solve in OOP, but in the real world usually ends up requiring some bizarre hacks.

abstract class Collection<'t> {
    public abstract void Add('t);
}

public class List<'t> : Collection<'t> {
    // implementation details

    public void Add(element) {
        // implementation details
    }
}

public class Set<'t> : Collection<'t> {
    // implementation details

    public void Add(element) {
        // implementation details
    }
}

Now a function can take a Collection, and it's guaranteed that you can Add an element to it. If you pass a List, it'll put it on the end; if you pass a Set, it'll add it if it isn't already present. Under the hood this is called "dynamic dispatch." Objects have tables of function pointers to their specific methods, so method invocation involves looking up the correct function pointer in the actual object being operated on and calling that.

How do we do dictionaries? Probably the most sensible answer is to create a helper class:

public class KeyValuePair<'k,'v> {
    private 'k _key;
    private 'v _value;

    public KeyValuePair('k key, 'v value) {
        _key = key;
        _value = value;
    }

    public 'k Key {
        get { return _key; }
    }
    private 'v Value {
        get { return _value; }
    }
}

public class Dictionary<'k,'v> : Collection<KeyValuePair<'k,'v>> {
    // implementation details
}

So far so good, but there's a big problem still. Let's consider Windows Presentation Foundation, one of Microsoft's many application libraries. There's a class for text boxes, System.Windows.Controls.TextBox, and there's a lightweight rich text label, System.Windows.Controls.TextBlock. TextBox is a Control, since it's used to provide input, while TextBlock is not.

Both classes have a property for controlling word wrapping, TextWrapping. Even though both classes have the same property of the same type (System.Windows.TextWrapping, an enumeration of word wrapping styles), it isn't derived from a base class. The parent of TextBlock is FrameworkElement, which covers anything that can be laid out and rendered, so it would be inappropriate for it to define TextWrapping—that would put a spurious property on all sorts of classes, most of which don't have any text at all!

Instead, the two classes independently define their own TextWrapping property. This means that, at first blush, it's impossible to write a function SetTextWrapping that works on both TextBox and TextBlock.

The obvious solution to this problem is allowed in C++, and disallowed in basically every object-oriented language since:

abstract class TextElement {
    private System.Windows.TextWrapping _wrap_mode;
    // other implementation details
}

public class TextBlock : FrameworkElement, TextElement {
    // implementation details
}

This is called multiple inheritance, and it's verboten because it's complicated. The best demonstration of the problem is called "diamond inheritance":

#include <iostream>

class A {
  public:
    virtual void foo();
};

class B: public A {
  public:
    B() { }
    void foo() {
        std::cout << "Called foo on B" << std::endl;
    }
};

class C: public A {
  public:
    C() { }
    void foo() {
        std::cout << "Called foo on C" << std::endl;
    }
};

class D: public B, public C {
  public:
    D() { }
};

int main() {
    D* d = new D();
    d->foo();
    return 0;
}

What does this program print? Nowadays you get this compiler error:

member 'foo' found in multiple base classes of different types

but most languages just don't allow multiple inheritance in the first place. Back when compilers allowed this, I honestly can't remember what it would have printed. Indeed, embedding multiple inheritance into a GUI library would be a maintainability disaster.

Interfaces allow multiple implementation, which is fine because interfaces don't provide any implementations themselves. This means the interface inheritance scheme will never create ambiguities: interface implementations will only ever be inherited through the single-inheritance class hierarchy.

So why aren't there interfaces for these orphaned properties in WPF? I don't have an answer. Maybe some Microsoft engineer out there could answer it, but I don't imagine I'd find the answer very satisfying.

This also gets us back around to the problem of a generic add-to-collection function. Arguably the biggest weakness of object-oriented programming, as it's done today, is that interfaces have to be implemented as part of the class definition. So what if we wanted to allow, say, Dotnet's System.Collections.Generic.List<'t> into our scheme?

We can't go back and edit Dotnet's definition of List<'t>, so the only real answer is inheritance. This means that our Collection<'t> class has to become an interface. Now if someone takes our code and wants to extend the functionality further, they have to go through the same trouble: define their functionality as an interface, and inherit our List<'t> to tack on their interface implementation.

To summarize object-oriented programming, then...

We do get some semantic discipline, since it pushes programmers to think taxonomically. We have reasonable assurance that Collection.Add has consistent meaning, since a sane person isn't going to stick a non-collection class in the Collection interface. It also makes the intentions of our arguments clearer, for the same reasons: type names, at the very least, clue programmers in to our intended semantics.

The problem, and this is why the fictional Carnap had so much trouble classifying sandwiches and hot dogs, is that the world is not taxonomical. Any taxonomy is inherently inadequate, which does two things to class hierarchies: first, they get bloated, and second, you end up having to hack around their limitations. So we get deranged stuff like the "composition pattern," and needless inheritance, and "extension methods," and the like.

In the next and final episode I'll talk about Haskell. I'm no theory zealot, and I don't think type classes are the end all and be all, but I do think they're a huge step up from all of this.

The Strange Art of Code Reuse, Part 1

Sean Williams — Fri, 01 Jul 2022 17:26:15 +0000

When I try to explain programming to a non-programmer, I go to an old standby: how do you make a sandwich? Sometimes they'll ask the first most important question: what kind of sandwich? I'll say something like, "that's a very good question, but for now, pick one."

After all, you don't want to do too much too quickly. More to the point, you don't want to immediately muddy the waters with the most important ontological question, is a hot dog a sandwich? At some point, though, you move on from primitive types and enter the wild world of polymorphism—or maybe you never learned a (mostly) monomorphic language like C or FORTRAN.

Anyway, the art of code reuse is defining what's common about heterogeneous data. The end goal is answering the question, in what situations can these data stand in for those data—or to be more concrete, what's required for this type to be a valid parameter to this function? Having functions that can operate on a wide range of types is called polymorphism, "having many shapes."

As a starting point, C has very little support for polymorphism, though clever programmers can hack it in using macros—which is the real reason it's called C++. But even basic C still has a dash of hard-coded polymorphism in the form of +, -, *, /, and the like. The compiler does some work to cast arithmetic operands into the same type, and then emits assembly based on that type.

This also helps illustrate what polymorphism really is: + is well-defined for all primitive numeric types, and importantly, it has the same semantics for all primitive numeric types. Conversely, the (hardware) implementation of floating-point addition is vastly different and more complicated than integer addition. This is basically where polymorphism starts from, though: a situation where you have an operation with substantially similar semantics over a wide range of types, but in which the implementations are all over the place.

The big question is, how do we define "substantially similar semantics?" There are basically three standard answers, and you're likely familiar with at least one of them.

Let's consider an artificial but illustrative problem: how could we write a function that, given two collections, joins them together? The meaning of "join" is specific to each collection type, so we would concatenate lists and union sets. Dictionaries are more complicated, and will be a crack in the door to much more advanced topics in static typing.

If It Quacks

Dynamic typing is used in languages like JavaScript, Python, and Lua. Most interpreted languages are dynamically typed, which has its own technical reasons. The style of dynamic typing you typically run into is also sometimes called "duck typing," as in, "if it quacks like a duck, waddles like a duck, and floats like a duck, it's close enough to being a duck for our purposes."

First and foremost, primitive data in these languages are still typed. In my experience, these languages nowadays tend to have all numbers be doubles, and all chars be strings, but a primitive is still a number, a string, or possibly a boolean. They often use implicit coercion, meaning that "hello " + 5 will convert 5 to "5" to produce "hello 5".

Structured data are, conceptually, dictionaries. They may or may not support lists/arrays—if they don't, then lists are dictionaries with indexes as keys.

In terms of joining collections, let's look at JavaScript. It basically has two collection types: Arrays and Objects (which are dictionaries). Our function might look like this, though there are other possible implementations...

function join(a, b) {
    if(a.constructor === Array && b.constructor === Array) {
        return a.concat(b);
    }
    if(a.constructor === Object && (b.constructor === Array || b.constructor === Object)) {
        return Object.assign({}, a, b);
    }
    return null;
}

Maybe there's a better implementation, I'm not really a JavaScript guy, but it gets at the core of duck typed polymorphism: enumerating types.

The other rider in this apocalypse is looking for the presence of dictionary keys. After all, objects are dictionaries, which means methods are functions keyed off their name (sometimes with additional magic to get a self-reference). For example, let's say we want to be able to add an element onto either an Array or an Object. We might do this:

function make_addable_array(a) {
    a.add = function(x) { a[a.length] = x; };
    return a;
}

// e.g., arr = make_addable_array([1, 2, 3]);
// arr.add(4);
// - [1, 2, 3, 4]

function make_addable_object(o) {
    o.add = function(x) {
        idx = 0;
        for(k in o) {
            if(Number(k) >= idx) {
                idx = Number(k) + 1;
            }
        }
        o[idx] = x;
    };
    return o;
}

// e.g., obj = make_addable_object({"hello": "world", 1: 5});
// obj.add(3);
// - {"hello": "world", 1: 5, 2: 3}

We could now write a trivial function to add an element onto a collection created this way:

function add_element(collection, element) {
    if(collection.add) {
        collection.add(element);
    }
    else {
        console.log("invalid collection passed to add_element");
    }
}

We're actually making a tragically strong assumption in the definition of add_element: that an object having a key/member named add means the same thing for all collections that are passed to add_element. This is the big tradeoff with dynamic typing, though: you give up semantic guarantees in exchange for simpler syntax. Not a tradeoff I like, which is why I personally avoid dynamically typed languages.

Anyway, this is a lot of trouble! Will other styles of polymorphism be any easier? This post is already getting too long, so I'll pick it up next time with a study of the taxonomy of sandwiches.

Generating hashed passwords for PostgreSQL

Sean Williams — Tue, 28 Jun 2022 20:25:30 +0000

This is a quickie, but can be incredibly useful. For the background, in case you don't know, it's a very very bad idea to store passwords. The first change is storing the hash of a password. A hash is just a function that's given some bytes and deterministically produces some other bytes, but it's very hard to go the other way. That is, if you have password_hash = hash(password) (where password is just the user's plaintext password), you can't easily derive password from password_hash.

Because of this, you only need to store password hashes. A user sends a password, you hash it, and see if the hashes match. For a good hashing algorithm, the probability of two passwords producing the same hash is minuscule. If your database is broken into, attackers will only get the hashes, not the passwords.

This gave rise to "rainbow table attacks," in which you precompute hashes for a lot of common passwords for common hashing functions. If you get a dump of password hashes, you see if any of the hashes are present in the rainbow table. For any hashes that show up, now you've got their password.

The defense against this is called "salting." You generate a random string, called the salt, and you compute salted_hash = hash(password + salt) (plus being string/array concatenation). You then store salt and salted_hash, so you can repeat the calculation when a user goes to log in. It's fine if the salts are leaked, because again the only thing we're actually defending against here is rainbow tables: an attacker can't precompute the hash of common passwords concatenated with all possible salts.

Anyway, Postgres lets you provide a salted, hashed password when creating a user. The issue with providing a hashed password to someone else's system is that you need to follow exactly the same steps they do: this whole song and dance is about being able to reproduce the same hashes from the same passwords. Being a little bit wrong on the hash you provide will make logins fail.

I did way too much digging to figure out how to reproduce the Postgres password hashing algorithm (particularly digging through the Postgres and Npgsql sources), so hopefully this'll save someone from the same trouble:

let password_hash (password: string) =
    let normalized = System.Text.Encoding.UTF8.GetBytes(password.Normalize(System.Text.NormalizationForm.FormKC))
    let salt_len = 16
    let default_iterations = 4096

    let salt = System.Security.Cryptography.RandomNumberGenerator.GetBytes(salt_len)
    let mutable salt1 = Array.create (salt.Length + 4) 0uy

    let hmac = new System.Security.Cryptography.HMACSHA256(normalized)
    System.Buffer.BlockCopy(salt, 0, salt1, 0, salt.Length)
    salt1[salt1.Length - 1] <- 1uy

    let mutable hi = hmac.ComputeHash(salt1)
    let mutable u1 = hi

    for _ in 1 .. default_iterations - 1 do
        let u2 = hmac.ComputeHash(u1)
        for i in 0 .. hi.Length - 1 do
            hi[i] <- hi[i] ^^^ u2[i]
        u1 <- u2

    let client_key = (new System.Security.Cryptography.HMACSHA256(hi)).ComputeHash(System.Text.Encoding.UTF8.GetBytes("Client Key"))
    let stored_key = (System.Security.Cryptography.SHA256.Create()).ComputeHash(client_key)
    let server_key = (new System.Security.Cryptography.HMACSHA256(hi)).ComputeHash(System.Text.Encoding.UTF8.GetBytes("Server Key"))

    let builder = new System.Text.StringBuilder()
    builder.Append("'SCRAM-SHA-256$").Append(default_iterations.ToString()).Append(":").Append(System.Convert.ToBase64String(salt)).Append("$")
        .Append(System.Convert.ToBase64String(stored_key)).Append(":").Append(System.Convert.ToBase64String(server_key)).Append("'").ToString()

Then, within a CREATE ROLE query, you just use,

"ENCRYPTED PASSWORD " + password_hash password

Picking colors in WPF

Sean Williams — Mon, 27 Jun 2022 22:24:30 +0000

Since I've been working in WPF a lot, it's jumped out at me how many features are conspicuously missing. The feature I'll talk about today is color picking. I'll start with the final dialog box, since I'll be referring to it later:

Computer color is a three-dimensional space, not least because there are three colors of filters in your monitor. The simpler color space is the colors of those filters—red, green, and blue—but it's also the hardest to work with. For normal use, we typically use a different three-dimensional space, of hue, saturation, and value.

Hue is your position on the rainbow, so values of hue go through red-orange-yellow-green-blue-violet. Saturation is the "whiteness" of your color, and value is the "blackness." When picking HSV colors, the standard is to have a two-dimensional selector (a rectangle) and a one-dimensional selector (a line). I followed Gimp's example, with saturation and value as the 2D selection, and hue as the 1D. Refer to the above image to see what I mean: you pick a hue in the small box on the right, then the big box on the left shows you all possible saturation-value combinations for that hue.

The first thing we need, then, is functions to convert between RGB and HSV colors:

let inline hsv_to_rgb h s v =
    let i = int (h * 6.) % 6
    let f = h * 6. - System.Math.Floor(h * 6.)

    let v = v * 255.
    let p = byte (v * (1. - s))
    let q = byte (v * (1. - f * s))
    let t = byte (v * (1. - (1. - f) * s))
    let v = byte v

    if (i = 0) then (v, t, p)
    else if (i = 1) then (q, v, p)
    else if (i = 2) then (p, v, t)
    else if (i = 3) then (p, q, v)
    else if (i = 4) then (t, p, v)
    else (v, p, q)

let inline rgb_to_hsv r g b =
    let v = max r <| max g b
    let delta = float (v - (min r <| min g b))

    let s = if v = 0uy then 0. else delta / (float v)

    let h =
        if s = 0. then 0.
        else
            if r = v then (float g - float b) / delta
            else if g = v then 2. + (float b - float r) / delta
            else 4. + (float r - float g) / delta
    let h = if h < 0. then h + 6. else h
    (h / 6., s, (float v) / 255.)

Here, HSV is three floats in the range [0, 1], while RGB is three bytes (so the range is [0, 255]). Hue gets scaled out to six, for the three primary (red, green, blue) and three secondary (yellow, cyan, magenta) colors, but to me it makes more sense for everything to be in the same range outside these functions.

Now we get into WPF weirdness. As far as I can tell, Brushes are really not configurable. While there is a LinearGradientBrush, the linear gradient is in RGB space. The only real answer I could find to make a hue spectrum is to make an image. You could make this by hand if you want, and Gimp or Photoshop will probably help you out, but we can also just do this in code.

let hue_gradient =
    let bitmap = new System.Windows.Media.Imaging.WriteableBitmap(1, 360, 96., 96., System.Windows.Media.PixelFormats.Pbgra32, null)
    let colors = [|
            for i in 0u .. 359u ->
                let y = 359u - i
                let i = y / 60u
                let h = ((y % 60u) * 255u) / 60u

                if i = 0u then
                    (h <<< 8) ||| (255u <<< 16) ||| (255u <<< 24)
                else if i = 1u then
                    (255u <<< 8) ||| ((255u - h) <<< 16) ||| (255u <<< 24)
                else if i = 2u then
                    h ||| (255u <<< 8) ||| (255u <<< 24)
                else if i = 3u then
                    255u ||| ((255u - h) <<< 8) ||| (255u <<< 24)
                else if i = 4u then
                    255u ||| (h <<< 16) ||| (255u <<< 24)
                else
                    (255u - h) ||| (255u <<< 16) ||| (255u <<< 24)
        |]
    bitmap.WritePixels(System.Windows.Int32Rect(0, 0, 1, 360), colors, 4, 0, 0)
    bitmap.Freeze()
    new System.Windows.Media.ImageBrush(bitmap)

There's a lot of things to say about this function. The image this produces is 1 pixel wide and 360 pixels tall. This is just following the convention that hue is a circle, and there are 360° in a circle, but you could make it bigger if you need more color resolution.

The calculations here are really just an integer-only reformulation of hsv_to_rgb above, except that saturation and value are always 1. The other big thing here is, this writes out one pixel at a time: the type of colors is uint32[]. In F#, ||| is the bitwise-or operator, and <<< is the bitshift-left operator.

This brings us to the issue that most computers eat eggs from the little end: "A little-endian system, in contrast, stores the least-significant byte at the smallest address" (from Wikipedia). Least significant means highest value, hence the pixel ordering in memory is in fact ARGB, for a pixel format called BGRA. Meaning, if a color byte is not shifted, that's the blue channel, then an 8-bit shift is green, 16 bits is red, and 24 bits is alpha.

hue_gradient is an ImageBrush, so it can be used as the Fill of a rectangle. We still need a callback, but that'll only make sense in the context of saturation and value.

This is where things get a bit mathematical. The box for saturation and value needs to be updated whenever a new hue is selected, but generating a new image on every mouse move event wouldn't be great. It turns out, we can do this entirely with alpha blending.

The way RGBA transparency works is quite simple:

blended_color =
    foreground_alpha * foreground_color +
        (1 - foreground_alpha) * background_color

Looking back at the HSV to RGB conversion, we had,

let v = v * 255.
let p = byte (v * (1. - s))
let q = byte (v * (1. - f * s))
let t = byte (v * (1. - (1. - f) * s))
let v = byte v

p, q, and t are used to set color channels: q and t for secondary channels, and p is for an "unused" channel. For example, in the case where we're moving from red to yellow, the RGB color is (v, t, p): v, pure value, sets the amount of red, while "leftover" hue (f) is combined with saturation and value to set yellow, while just saturation and value set blue.

The more important point here is, this looks a lot like the equation for alpha blending. I worked this all out numerically, so I don't have a full derivation here (exercise for the reader?), but it turns out you can make a saturation-value selector by overlaying three Brushes on top of each other, from bottom to top:

A SolidColorBrush, which contains an HSV color of the form (H, 1, 1)—we'll call this the color_background_brush
A LinearGradientBrush, which goes horizontally from the RGBA color (255, 255, 255, 255) to (255, 255, 255, 0)—that is, opaque white to transparent white
A LinearGradientBrush, which goes vertically from the RGBA color (0, 0, 0, 0) to (0, 0, 0, 255)—that is, transparent black to opaque black, also note the alpha values are reversed here since in WPF going down is an increase in y, in other words, we want this brush to be opaque at the bottom

When a new color is selected, we just have to update the SolidColorBrush to the new hue, and the whole SV color space is updated automatically. Or if that's too mystical for you, it gets updated by fragment composition in the rendering pipeline.

Now all that's left is a couple events:

    let mutable (h, s, v) = (0., 1., 1.)
    let mutable (r, g, b) = hsv_to_rgb h s v

    let hue_bar_drag _ (args: System.Windows.Input.MouseEventArgs) =
        if args.LeftButton = System.Windows.Input.MouseButtonState.Pressed then
            h <- 1. - args.GetPosition(hue_bar).Y / (float color_box_height)
            let (r', g', b') = hsv_to_rgb h 1. 1.
            color_background_brush.Color <- System.Windows.Media.Color.FromRgb(r', g', b')
            let (r', g', b') = hsv_to_rgb h s v
            r <- r'
            g <- g'
            b <- b'
            color_preview_brush.Color <- System.Windows.Media.Color.FromRgb(r, g, b)
    hue_bar.MouseLeftButtonDown.AddHandler(hue_bar_drag)
    hue_bar.MouseMove.AddHandler(hue_bar_drag)

    let sv_bar_drag _ (args: System.Windows.Input.MouseEventArgs) =
        if args.LeftButton = System.Windows.Input.MouseButtonState.Pressed then
            s <- args.GetPosition(value_mask).X / (float color_box_height)
            v <- 1. - args.GetPosition(value_mask).Y / (float color_box_height)
            let (r', g', b') = hsv_to_rgb h s v
            r <- r'
            g <- g'
            b <- b'
            color_preview_brush.Color <- System.Windows.Media.Color.FromRgb(r, g, b)
    value_mask.MouseLeftButtonDown.AddHandler(sv_bar_drag)
    value_mask.MouseMove.AddHandler(sv_bar_drag)

color_box_height, of course, is just the size (in pixels) of the hue and saturation-value selection boxes. I've got it set to 256 in the above image.

After this you just have to configure the UI as you'd like it: color_preview_brush is a SolidColorBrush applied to the rectangle along the bottom, which displays the currently selected color. You'll need to use a Grid to properly overlay color_background_brush (or rather, a Rectangle with that as its Fill) with the saturation and value masks. You could also add a few Lines or Circles to show the positions of the selected color if you're so inclined. But you know, I'm not going to tell you how to make your dialog boxes. Finally, the constantly-updated (r, g, b) values are the return.

Anyway, that's how you can make a color picker dialog. I mean sure you could download a library for it, but isn't it more interesting figuring out how they work?