Algoritmus pro inferenci typových parametrů

Jednou z hlavních výhod jazyků jako C++(17+), Rust, Swift či Go je, že mají silnou typovou kontrolu v době překladu, a přitom není nutné typy explicitně uvádět nejen u proměnných (tam je algoritmus jednoduchý), ale často ani u typových parametrů.

Pokud máme například všeobecně známou funkci map s typovými parametry T a U

func MapSlice[T, U any](s []T, f func(T) U) []U {
	r := make([]U, len(s))
	for i, x := range s {
		r[i] = f(x)
	}
	return r
}

můžeme jednoduše napsat

s := []int{1, 2, 3}
r := MapSlice(s, func(x int) float32 { return float32(x) + .1 })

přičemž parametry T a U si překladač odvodí sám, aniž bychom museli psát MapSlice[int,float32]. V případě typových parametrů je algoritmus přímočarý, neboť je založený na unifikaci termů (složených hodnot). Typovou charakteristiku funkce MapSlice lze deklarativně zapsat jako MapSlice(params(T, U), signature(slice(T), f(T,U), U)), zavolání pak bude call(MapSlice, args(slice(int), f(int,float32), float32)), stačí tedy prostě unifikovat termy signature(...) a args(...). Některé jazyky jdou ještě dále a dovolují zapsat lambda funkci bez explicitních typů jako (x) { return x + .1; }, takže překladač odvodí nejdříve typy lambda funkce a následně volání. To už je skoro matematický zápis λx . x+.1.

Typy v signatuře mohou být i hlouběji, například v tomto případě (definice FlattenSlice by měla být zřejmá):

func FlatMapSlice[T, U any](s []T, f func(T) []U) []U {
	return FlattenSlice(MapSlice(s, f))
}

Při zavolání

r := FlatMapSlice(s, func(x int) []float32 {
	return []float32{float32(x) - .1, float32(x) + .1}
})

se rovněž automaticky odvodí typy pomocí vnořené unifikace.

Použitý formální zápis je pro názornost vyššího řádu (s vnořenými strukturami), nejjednodušší algoritmus pro unifikaci vyžaduje struktury rozepsané do prvního řádu, v kterémžto případě zůstává ale výpočetní složitost i formální síla stejná.