Provide more specific error messages for invalid arguments to a method call

[Quantumplation]

Imagine a function defined like so

fn my_func(a: Int, b: String, c: EscrowDatum, d: Redeemer, e: List<Int>, f: List<String>) { ... }

fn spend(_1, _2, _3) -> Bool {
  my_func(1, EscrowDatum { }, PoolDatum { }, FactoryDatum { }, ["X", "Y"], [1,2]);
}

Currently, this would be reported as some simple form of "the arguments to this function are incorrect" or "the wrong number of arguments have been specified".

However, in code review with a human, you might explain the errors this way:

Function parameter b is missing.
Expected something of type Redeemer for the third argument (d), but got PoolDatum instead.
The provided FactoryDatum is extra, and doesn't satisfy any of the parameters.
The parameters e (List) and f (List) are likely in the wrong order.

This may seem difficult, as it involves inferring a lot of user intent; and to some extent, solving this exactly would be impossible.

However, it turns out it's possible to get fairly good results by applying a few heuristics. This was implemented in the Rust compiler a year or so back, (first here)[https://github.com/rust-lang/rust/pull/71827] then (merged)[https://github.com/rust-lang/rust/pull/92364] later.

I propose porting the algorithm in the PRs above to Aiken. I'm happy to do this work (and actually already started on this 😅), but I figured I'd open a discussion to track that work.

Here's a brief outline of the algorithm:

It works very similarly to the Levenshtein edit distance, if the types involved were "letters" in a word: what is the smallest sequence of edits you'd need to make to this "word" for them to "match".

So, we build a boolean matrix: Each column is one of the arguments provided to the function, and each row is one of the inputs to the function.

We compute whether each argument provided could satisfy one of the other inputs, if they were reordered.

• An argument that can satisfy no inputs is "extra"
• An input that can be satisfied by no arguments is "missing"
• etc.

We iteratively identify these cases, emit the appropriate heuristic, and then remove the column/row until the matrix is empty.

There's some extra nuance to be careful about (test the diagonal first, so that the happy path is fast, be careful about unifying types so we don't mess up other type-checking, etc.

Here's as far as I've gotten so far: when type-checking functions, we print out a little compatibility matrix for debugging purposes:

[Quantumplation]

Absolutely floored at the amazing coincidence of this discussion being #314 lmao