jesseschalken

Interfaces and Sum Types

The way different programming languages implement the mapping of runtime polymorphic values to code both at the source level and in the language implementation is a defining characteristic. There are two opposite approaches that languages facilitate to varying degrees:

1. Interfaces / Traits / Abstract Classes / Inheritance / Method Overriding (from here on, just "Interfaces")
2. Sum Types / Algebraic Data Types / Tagged Unions / Pattern Matching (from here on, just "Sum Types")

Example

You have two types: A, containing a string, and B, containing an int, and two operations: x and y.

jesseschalken

• ⚪ = uninitialized memory
• 🔵 = value 1
• 🟢 = value 2

	name	operator	note
⚪ → 🔵	construction	A()	constructor may require parameters constructor may have multiple overloads
🔵 → ⚪	destruction	~A()

jesseschalken

import { ClientReadableStream } from "grpc-web";
import { Observable } from "rxjs";

export function grpcToRx<T>(f: () => ClientReadableStream<T>): Observable<T> {
  return new Observable<T>(subscriber => {
    const stream = f();
    stream.on("error", e => subscriber.error(e));
    stream.on("end", () => subscriber.complete());
    stream.on("data", x => subscriber.next(x));
    return () => stream.cancel();

jesseschalken

fun Iterable<Boolean>.toBrailleString(): String =
  chunked(8) {
    fun p(i: Int, j: Int) =
      if (i < it.size && it[i]) 1 shl j else 0

    '\u2800' +
        p(0, 0) + p(1, 1) + p(2, 2) + p(3, 6) +
        p(4, 3) + p(5, 4) + p(6, 5) + p(7, 7)
  }.toCharArray().concatToString()

jesseschalken

T.also(block: (T) -> Unit): T
T.apply(block: T.() -> Unit): T
T.let(block: (T) -> R): R
T.run(block: T.() -> R): R

jesseschalken

export interface HashImpl<T> {
  hash?(value: T): unknown;
  equals(a: T, b: T): boolean;
}

export class AssociationList<K, V> implements Map<K, V> {
  private inner: {readonly key: K; value: V}[] = [];

  constructor(
    private readonly impl: HashImpl<K>,

jesseschalken

C	C++
T* owning a single object	T
T* borrowing a single object	T&
T* owning a single object, nullable	std::optional<T>
T* owning a single object, polymorphic	std::unique_ptr<T>
T* owning an array (dynamic size)	std::vector<T>
T[N] owning an array (static size)	std::array

jesseschalken

export class CircularBuffer<T> implements Iterable<T> {
  private start: number = 0;
  private _length: number = 0;
  private array: T[] = [];
  grow(size: number) {
    if (size > this.array.length) {
      size = Math.max(size, this.array.length * 1.5);
      const array = new Array<T>(size | 0);
      for (const x of this) {
        array.push(x);

jesseschalken

Random database IDs

I'm inferring this based on vague statements on the internet and a reading of how B-trees work.

Databases and file systems use B-tree indexes to implement key-value maps (indexes for a database table). Since it's a search tree and not a hash table, it is inherently ordered.

Cache locality

When inserting sequentially increasing values into a B-tree, you always hit the rightmost leaf node (sorting left to right), since that's where a value that is higher than all the existing values must be inserted. When the leaf is full, it is split in two and the parent node is updated to have an extra child. Since the parent may also already be full, it may need to be split, and so on. When the root node is full, it needs to be split, creating a new root and increasing the height of the tree by 1 level.

jesseschalken

<?php

function utf8_ord(string $s, int $i = 0): int {
  $b0 = 0b00000000;
  $b1 = 0b10000000;
  $b2 = 0b11000000;
  $b3 = 0b11100000;
  $b4 = 0b11110000;
  $b5 = 0b11111000;