Tutorial

One Function, Many Ranks

Let's run programs with Tensors.
Quick warm-up: what is 1 + 1?

2. But are those even Tensors?

Yes, 1 has type Tensor[int][[]].
Try this next: Tensor([1]) + Tensor([1]).

Hmm... if we break them into smaller tensors, then at the matching position, we have 1 + 1 again--a problem we've already solved.

Great instinct. Indeed, we add the matching positions.

Then it is Tensor([2]), right?
Likewise, Tensor([1, 2, 3]) + Tensor([5, 7, 9]) gives Tensor([6, 9, 12]).

What about Tensor([[1, 2, 3], [3, 2, 1]]) + Tensor([5, 7, 9])?

Wait, their types are different: Tensor[int][[2, 3]] and Tensor[int][[3]].
Can we add Tensors with different types?

For this one, yes. A Tensor[int][[2, 3]] contains two Tensor[int][[3]]s.
So we run + twice. Each still adds matching positions.

Right.
First: Tensor([1, 2, 3]) + Tensor([5, 7, 9]).
Second: Tensor([3, 2, 1]) + Tensor([5, 7, 9]).
Then we combine the results as Tensor([[6, 9, 12], [8, 9, 10]])?

What is the result type?

The result is Tensor[int][[2, 3]], the same as the larger input shape.
It's a nice trick to split the larger Tensor!

The trick is called rank polymorphism.

An intimidating name!

It's actually warmer and fuzzier than it looks. Here, rank is just the length of the shape.
Tensor[int][[3]] has rank 1, and Tensor[int][[2, 3]] has rank 2.

Then 42 has type Tensor[int][[]], so rank 0?

Yes.
When we design a function, we define its expected types for inputs and result.
Rank polymorphism lets us apply that function to higher-rank inputs when they are compatible, and it wraps the result type accordingly.

So one function works across different input ranks.
Is + a function?

+ is a function. Just like
5 has type Tensor[int][[]],
+ has type (x: Tensor[int][[]], y: Tensor[int][[]]) -> Tensor[int][[]].

This function type suggests three things:
+ expects two inputs, x and y.
x is Tensor[int][[]], and so is y.
The result is also a Tensor[int][[]].

Now imagine applying + with 1 as x and 1 as y.

1 is Tensor[int][[]], so both inputs match exactly.
Therefore 1 + 1 has result type Tensor[int][[]], which is the type of 2.

Next: Tensor([[1, 2, 3], [3, 2, 1]]) + Tensor([5, 7, 9]). In the earlier exercise, we virtually ran the program and found Tensor[int][[2, 3]] by looking at the result value.
Now we derive the result type, without running the program.
Let's start by validating the inputs.

Here, x has type Tensor[int][[2, 3]] and y has type Tensor[int][[3]].
Neither exactly matches the expected Tensor[int][[]].
But they must be compatible, since we added them just now!

We need a rule for the compatibility between List[int]s.

Let's see it!

Two List[int]s are compatible, if we line them up from the right and find a suffix in the longer one that matches the shorter.* The remaining part in the longer list is called the prefix.
Find the suffix and prefix for x and y.

For x, compare [2, 3] with []: suffix [], prefix [2, 3].
For y, compare [3] with []: suffix [], prefix [3].
That means: each given input is compatible with its expected type!

Great. Next, validate compatibility between the two prefixes.

Does compatibility also work on prefixes?

Yes. Compatibility applies to List[int]s. Prefixes are List[int]s too.

So we compare [2, 3] with [3].
The suffix is [3] and the prefix is [2].
That means the prefixes from the inputs are also compatible.

Good progress! So far:
for each input, the given type is compatible with the expected type;
the two prefixes from the inputs are compatible with one another.
So Tensor[int][[2, 3]] and Tensor[int][[3]] are valid inputs for x and y in +.

Nice. What's our next step?

Now we wrap the result type. Under rank polymorphism, we repeatedly apply + to generate many Tensor[int][[]]s.
The number of repetitions depends on the longer prefix.

Got it. The longer prefix is [2, 3], so we wrap Tensor[int][[]] with [2, 3]. That makes Tensor[Tensor[int][[]]][[2, 3]], which simplifies to Tensor[int][[2, 3]].
Exactly the same as running the program!

Great work!
Try a few failing examples too: cases where a given type is incompatible with an expected type, or where the prefixes are incompatible.
It helps to internalize this trick.

Will do.

Let's recap rank polymorphism:
for each input, validate compatibility between the given and expected types, find the prefixes;
validate compatibility between those prefixes;
wrap the result type with the longer prefix.
This process applies to all functions.

Are there other functions besides +?

Yes, you can define as many as you need. We'll cover that in the next chapter.
Time for a break!

Okay, ciao!

* We match the ints in two List[int]s in matching positions, from the right end. Two ints match, if they are identical, or if either of them is 1.