Teymour Aldridge

Random thoughts on entities that (usually) exist.

global money dispatch

This is semi-regular series of articles about the Global Financial System published by Credit Suisse. As might be expected, it often expresses opinions that are advantageous to Credit Suisse.

All these URLs are also available in the Wayback Machine.

bio 2021 question 1

Part A

This problem can be solved simply using a recursive algorithm:

function is_pat(string: String) -> bool
    if string.len() == 1 then
        return True
    else
        is_pat = False
        for i=0 to string.len() - 2 do
            let (first_half, second_half) = string.split_at(i)
            if NOT min(first_half) > max(second_half) then
                return False
            endif
            if is_pat(reversed(first_half)) AND is_pat(reversed(second_half)) then
                is_pat = True
                break
            endif
        endfor
        return is_pat
endfunction

It is a good idea to check that this algorithm is fast enough by testing some down pats that are twelve letters long.

Part B

This question is easily solved once you have solved 1A by generating all the permutations of ABCD and checking which ones are pats (you can even do this by hand).

Part C

This question is a bit more involved (I would argue that it is harder than question 1.A) and requires some combinatorics.

The trick to thinking about this question is to generalise – it's much easier to think about a down pat in the abstract than it is to thinking about different specific down pats and try to draw conclusions about the number of permutations.

First we can simplify the problem – we know that the down pat will be in the form B___A (this is because B comes one letter after A in the alphabet, so it is not possible to put a letter after A because this letter would be after B in the alphabet, and thus not all the characters in the left string would be higher in the alphabet than B). So we can split B___A into ___B and A. For ___B we know that the letter before B will be after B in the alphabet (C or higher) this means that we can only split ___B into ___ and B (because if we had CB, when we reverse this we get BC, and B is not higher than C in the alphabet, so this is not a down pat – the argument can be extended for other letters and greater splits).

We can conclude that we have 24 letters, and we would like to see how many different ways we can arrange them that are also valid down pats. We could think about individual permutations, and whether or not these are valid down pats – this is really messy though!

There is a better way; we can consider the structure of every down pat simultaneously. Let's think about a 24 letter (valid – this is the crucial assumption; one way that we can define a pat is that for a pat of n letters, we can split it n-1 times in total, before we have just single letters – i.e. we have a binary tree with n-1 nodes with children) down pat – we can split it in 23 different places.

You might find these diagrams useful as a visual aid:

A visualisation of how the down-pat "BCA" can be decomposed

  • 3 letters, 3-1 nodes with children

A visualisation of how the down-pat "BDCA" can be decomposed

  • 4 letters, 4-1 nodes with children

So we could have splits in the form (1, 23), (2, 22), (3, 23), ..., (23, 1) (where each number represents the length of the pat). How does this help us? Well, it means the number of ways this "tree" (think about it – every down pat has two "children" and all of those childen have either two children or no children) can be arranged is:

arrangements(1) * arrangements(23) + arrangements(2) * arrangements(22) + arrangements(3) * arrangemenents(23) + ... + arrangements(23) * arrangements(1).

Hopefully this is looking quite solvable now! But why is this true? Well, let's think about the first case, where we place one node on the right of the tree, and one node on the left of the tree (see my diagram below).

Diagram showing a binary tree with one node with value 24, connceted to two child nodes, one node with value 23 and the other with value 1

The number of ways that we can rearrange this tree is the number of ways that we can rearrange a tree with one node (i.e. one) times the number of ways that we can rearrange a tree with twenty-three nodes (it's not immediately obvious how we do this, but note that we can break this problem down recursively in the same way that we did with the 24 letter one). Why? Because for every possible arrangement of the left node, we can have every other arrangement of the right node (in this case, that's one). I've emphasised some of the words there because hopefully they help to make it obvious where this program comes from:

total_options = 0
// for every arrangement of the left node
for i=1 to arrangements(left_node) do
    // we have every arrangement of the right node
    for i=1 to arrangements(right_node) do
        // and this is a distinct arrangement of the whole tree
        total_options += 1
    endfor
endfor

Note that this is equivalent to arrangements(left_node) * arrangements(right_node).

So overall, we have an algorithm that looks a bit like

function arrangements(nodes: nat) -> nat
    // this is our basis case
    if nodes == 1 then
        return 1
    endif

  // we reduce the other cases in terms of the basis case
    total = 0
    for i=1 to nodes - 1 do
        total += arrangements(i) * arrangements(nodes - i)
    endfor
    return total
endfunction

This takes into account all the ways we can build distinct trees.

We are starting with 24 nodes, so the value we want is arrangements(24) (this equals 343059613650). Unfortunately, this function above (although very simple) is too slow as-is. It can easily be sped up using dynamic programming; see a possible solution that runs which I wrote.

The key is never to compute the same value twice – we just save the output value of the function into (for example) a hashtable (aka hashmap, aka dictionary).

A really easy way to do this in Python is to use the built-in cache decorator (cache documentation) – note that this seems to only exist in Python 3.10 (so you may need to replace cache with lru_cache):

from functools import cache

@cache
def arrangements(nodes: int) -> int:
    if nodes == 1:
        return 1
    total = 0
    for i in range(1, nodes):
        total += arrangements(i) * arrangements(nodes - i)
    return total

print(arrangements(24))

Using very statistically dubious measurement techniques, I measured the time taken for each approach:

  • With cacheing: 0.0001087188720703125s
  • Without cacheing: you know, my machine is still trying to work this out. We'll just say a lot. I think this a great illustration of just how effective dynamic programming can be. Update: it took 24854.752412080765s (ouch) which is about 7 hours!

An aside

It is sometimes joked that

There are two hard problems in computer science – naming things, cache invalidation [working out when to remove things from a cache] and off by one errors.

And not completely without merit – cacheing can be hard. Although it is not the case for our function, sometimes we might have too many values to store in our cache. In this case, we could use an LRU cache.

LRU stands for "least recently used" and is an eviction strategy (i.e. if our cache is too big, we have to remove an element, which element do you choose?) for cacheing. A cache stores values that have previously been computed – however, sometimes (not in this case) it turns out that there are too many values (relative to the amount of memory we have). One way of removing values is to store when each value was last used, and remove the value that was (you guessed it) least recently used.

For example, if our cache could only support five values, and we already have five values in it:

value | last_used
arrangements(1) = 1  | 4
arrangements(2) = 1  | 3
arrangements(3) = 2  | 2
arrangements(4) = 5  | 1
arrangements(5) = 14 | 0

Then we would select the value with the greatest last_used value (i.e. arrangements(1)) and remove it from the cache, instead inserting the new value that we wanted to insert. This can be useful if you find that you use this method and run out of memory. For this function, though, it is not needed (at least given the size of our input) and we can just use an "unbounded" (i.e. there is no maximum number of items) cache.

unification (sort-of in rust)

I've recently been ~~attempting~~ failing to write a compiler in Rust (I keep getting stuck on name resolution for modules, and scopes/namespaces – if you have any good resources, please do point me to them!) One part of this that I did (eventually) manage to get working was type inference. I've written up a tutorial-esque thing (you know, the "what I wish I'd known" thing), and I hope that it will be of use to someone.

The basic problem of type inference is this: we don't want to make the programmer write out all the types, so we "infer" the ones that are (too the human mind) 'obvious'. For example, in the following program not all the type annotations are necessary.

function f(x: int) -> int {
    return x * x;
}

let y: int = 12;
let x: int = f(y);

We could definitely remove the type annotation from the y (because we can work out that y must be an integer due to the fact that we assign the literal 12 to it)!

function f(x: int) -> int {
    return x * x;
}

let y = 12;
let x: int = f(y);

For this specific program, we can also remove the annotation from the x (we can work it out, because we worked out that y is an integer, and we know that when we multiply an integer by another integer we get an integer.

function f(x: int) -> int {
    return x * x;
}

let y = 12;
let x = f(y);

We can do a similar thing for the function f. Because we only ever pass integers into it, we can remove the int annotation. Whether this is actually desirable is questionable (bidirectional type checking, for example, explicitly keeps type annotations for functions).

function f(x) -> int {
    return x * x;
}

let y = 12;
let x = f(y);

And we can also remove the return value (because return int*int implies int as the return type).

function f(x) {
    return x * x
}

let y = 12;
let x = f(y);

So, in essence, type inference is about getting from:

function f(x) {
    return x * x
}

let y = 12;
let x = f(y);

to

function f(x: int) -> int {
    return x * x;
}

let y: int = 12;
let x: int = f(y);

Of course, this is not (in my mind) an easy problem to solve! My instinct was to use a tree representing the program state and traverse it, infering the types as we go. It turns out that this is definitely possible, but there's a much simpler way (in my opinion) to do this – we separating out finding "constraints" and solving them. A "constraint" means – reason why something needs to be a type. For example, every time we removed a type in getting from the typed to the untyped program, we were effectively dealing with a constraint. A sufficient constraint set for the types above, might look something like this:

y = Int
x (the variable) = f (the return type of f)
x (from f(x)) = y
x (from f(x)) = f (the return type of f)

But how do we distinguish between the different names in use – x from f(x) doesn't equal x the variable, after all? I'm actually not sure, but the ~~approach~~ guess I took was something like this – assuming you've constructed your syntax tree not dissimiliarly to that of the Rust compiler (see this page of the rustc-dev-guide for details) and every identifier (and expression, function return, etc ) has a unique tag (e.g. a usize) we can use these as the constraints. Once I've worked out how to handle name resolution, I'll write up my findings in the hope that they can be of help to somebody else.

Once we have the constraint set, it's not too hard to solve it. We write a unification algorithm, such as the one below (I hope it's correct :D).

/// Unify a set of constraints (i.e. solve them, if that is possible)
fn unify(set: HashSet<Constraint>, mut solved: TyEnv) -> Result<TyEnv, TyCheckError> {
    if set.is_empty() {
        return Ok(solved);
    }

    let mut iter = set.into_iter();

    let next = if let Some(next) = iter.next() {
        next
    } else {
        return Ok(solved);
    };

    let u = match next {
        Constraint::IdToTy { id, ty } => Some(Substitution::ConcreteForX(ty, id)),
        Constraint::IdToId { id, to } => {
            if id != to {
                Some(Substitution::XforY(id, to))
            } else {
                None
            }
        }
        Constraint::TyToTy { ty, to } => {
            if ty != to {
                return Err(TyCheckError::TypeMismatch);
            } else {
                None
            }
        }
    };

    if let Some(u) = u {
        // add the substitution to the list of substitutions
        solved.feed_substitution(u);

        // apply the newly generated substitution to the rest of the set
        let new_set: HashSet<Constraint> = iter
            .map(|constraint| match (u, constraint) {
                // wherever we see y, replace with x
                (Substitution::XforY(x, y), Constraint::IdToTy { id, ty }) => Constraint::IdToTy {
                    id: if id == y { x } else { id },
                    ty,
                },
                // wherever we see y, replace with x
                (Substitution::XforY(x, y), Constraint::IdToId { id, to }) => Constraint::IdToId {
                    id: if id == y { x } else { id },
                    to: if to == y { x } else { to },
                },
                (Substitution::ConcreteForX(sub_with, x), Constraint::IdToTy { id, ty }) => {
                    if id == x {
                        Constraint::TyToTy {
                            ty: sub_with,
                            to: ty,
                        }
                    } else {
                        Constraint::IdToTy { id, ty }
                    }
                }
                (Substitution::ConcreteForX(sub_with, x), Constraint::IdToId { id, to }) => {
                    if id == x {
                        Constraint::IdToTy {
                            id: to,
                            ty: sub_with,
                        }
                    } else if to == x {
                        Constraint::IdToTy { id, ty: sub_with }
                    } else {
                        Constraint::IdToId { id, to }
                    }
                }
                // these substitutions cannot be applied to the constraint set
                (Substitution::XforY(_, _), constraint)
                | (Substitution::ConcreteForX(_, _), constraint) => constraint,
            })
            .collect();

        unify(new_set, solved)
    } else {
        unify(iter.collect(), solved)
    }
}

Solving these constraints shouldn't be too tricky. What we do is:

  1. remove the first item from the constraint set (if the set is empty, then return the results)
  2. generate a substitution for this. There are a couple of cases:
    • if we have a constraint variable=type we substitute the variable with the type
    • if we have a constraint variableY=variableX we substitute variableY for variableX
    • if we have a constraint type=type we check if the two types are equal – if they are, then we generate no substitution – if they are not the same, then there is a type error in the program, and we abort
  3. we use this substitution to work out the value of the type – for this maintain a map containing all the variables and the values they correspond to
    • if we are applying the substitution "variable=type" then insert variable -> type into the solutions map
    • if we are applying the substitution replace variableY with variableX then insert variableY->variableX into the map
  4. we apply this substitution to the rest of the set, and then call unify recursively (with the new data)

Applying this to

y = Int
x (the variable) = f (the return type of f)
x (from f(x)) = y
x (from f(x)) = f (the return type of f)

would run something like this.

  1. Substitute y=Int in the rest of the set, and add y->Int to our solutions.
solutions = {
    y -> int
}
constraints = {
    x (the variable) = f (the return type of f)
    x (from f(x)) = Int
    x (from f(x)) = f (the return type of f)
}
  1. substitute x (the variable) with f (the return type of f)
solutions = {
    y -> int
    x (the variable) -> f (the return type of f)
}
constraints = {
    x (from f(x)) = Int
    x (from f(x)) = f (the return type of f)
}
  1. substitute x(from f(x)) = Int
solutions = {
    y -> int
    x (the variable) -> f (the return type of f)
    x (from f(x)) = Int
}
constraints = {
    Int = f (the return type of f)
}
  1. substitute f (the return type of x) = Int
solutions = {
    y -> int
    x (the variable) -> f (the return type of f)
    x (from f(x)) = Int
  f (the return type of f) = Int
}
constraints = {
}
  1. done!

To find something from the solution set, I wrote a small algorithm something like:

  1. find the item in the map – return None if it could not be found
  2. if the item corresponds to a concrete type (e.g. Int) then return Some(Int)
  3. otherwise recursively search for the item that is pointed to by the one we just found

further reading

against the term "critical ai"

The term "AI" is one of those words so well-worn by corporate marketing departments that all the meaning has been worn out of it. When it is used today it is to describe things which certainly do not match its original meaning (machines which could think, or at least demonstrate signs of intelligence); they are not machines which can think - they are machines which can crudely, repeatedly, and quickly crunch large amounts of data and find millions (or more) conditional probabilities from which it makes new predictions about what is likely to happen in the future. Effective? Yes. Thinking? No.

It's not exactly a co-incidence that this has happened; I don't have numbers on this to hand but I'm certain that the product labelled as an "AI-powered car saving lives" sells better than the "mathematical mystery tour of conditional probabilities in a box on wheels responsible for not killing you;" the "AI-enhanced camera" is probably more popular than the "over-exposed camera that will mash up your photos in otherwise interesting ways;" perhaps in more sinister fashion, the "AI-powered border safe-keeping technology" is more palatable to most than "a bunch of cameras and barbed wire intended to keep refugees out."

"AI" has become an anodyne term that does more to obscure than it does to illuminate and explain. This should probably be the first observation that any "critical AI" scholar makes – at least some consideration of what the term means, where it came from, and what it is used for. Blindly accepting the term "AI" as given, and using it as the basis for analysis of modern data processing and storage systems, benefits those who use the term to obscure what they are doing, or (worse) as euphemism for the horrible consequences that their software systems can bear.

As such, the notion of the "critical AI" scholar feels like an oxymoron. Describing mass data collection and processing as "AI" is problematic if you want to carry out "critical" analysis; if machine systems are "intelligent" then this suggests that their output should not be subjected to the same level of scrutiny as we would subject other industrial systems to (such as planes, chemical refineries, nuclear reactors, etc); if we repackage what people presently consider ethically repulsive as something new by suggesting that that we are on the frontier of some brave new world brought into being by technology – which is usually not true (even if the current techniques are new, what they do is in effect what computer systems have always been intended to do – process large volumes of information in order to derive usable output) – then that is effectively a form of deception; conflating data processing with the term "AI" used to mean, and has now been renamed "GAI" (general artificial intelligence) is fundamentally not a critical analysis, because it has neglected the fact that language has meaning and shapes how we think!

In its present usage, the term AI conflates different ideas and elides meaning. It carries unspoken assumptions. Surely the purpose of scholarship should be to make things clearer and to improve our understanding. Accepting the term "AI" without considering the ramifications of doing this is antithetical to this.

cognitive complexity and failures of computer programs

One of the most frequently overlooked performance metrics is the cognitive complexity of a codebase. If engineers experience high friction when trying to change a codebase, all efforts to make the code faster will be dramatically hindered. A codebase that is a joy for engineers to work with is a codebase that will see the most long-term optimizations. Codebases that burn people out will not see long-term success unless they receive tons of funding to replace people who flee the project after short periods of activity. Organizational instability is a high-quality predictive metric for the bugginess of a codebase.

https://sled.rs/perf.html

testing macros with side-effects using `trybuild`

Note: this is probably only of interest if you write (or want to write) Rust procedural macros.

I was recently writing a test for a procedural macro which looked like this:

#[test]
fn test_classes_to_file() {
    let t = trybuild::TestCases::new();
    t.pass("tests/write_file/pass.rs");
    let file = read_to_string(&format!(
        "{}/styles.css",
        std::env::var("CARGO_MANIFEST_DIR").unwrap()
    ))
    .unwrap();
    assert!(file.contains("{font-size:24px;font-family:sans-serif;}"));
}

It compiles a file which invokes a procedural macro. The procedural macro in question will write some data (some auto-generated CSS) into a file, and I wanted to make sure that it writes the correct CSS into the file. Unfortunately, in its current state the test fails (but not because the macro is performing incorrrectly!)

The way in which trybuild runs tests means that tests are added and then run when TestCases is dropped. I might question this API design were it not for the fact that most macros are just simple(ish) mappings of code from "A" to "B." That is a good way to write macros!!!

Anyway, in this case, the trick is to ensure that TestCases is dropped before checking that the file has been written to.

#[test]
fn test_classes_to_file() {
    let t = trybuild::TestCases::new();
    t.pass("tests/write_file/pass.rs");
        std::mem::drop(t);
    let file = read_to_string(&format!(
        "{}/styles.css",
        std::env::var("CARGO_MANIFEST_DIR").unwrap()
    ))
    .unwrap();
    assert!(file.contains("{font-size:24px;font-family:sans-serif;}"));
}