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á.

Kontrola pravopisu pomocí dynamického programování

Zajímalo vás někdy, jak se implementuje kontrola pravopisu v textových editorech? Nemyslím teď kontrolu překlepů na základě seznamu slovních tvarů (to je velice jednoduché), ale upozorňování na chyby ve skladbě (např. shoda přísudku s podmětem apod.). Tento příspěvěk začíná seriál, který je úvodem do kontroly pravopisu (převážně češtiny) a zároveň do dynamického programování.

Nejprve si vymezme, co bude náš kód kontrolovat. Zaměříme se pouze na skladbu v rámci jedné věty. To znamená, že hrubky jako "děti zpívali" nebo "kdyby jste věděli" by měl odhalit, ale chyby plynoucí z mezivětného kontextu, např. "Máme dvě děti. Včera byli nemocné" neodhalí, protože zpracovává věty jednu po druhé, bez ohledu na text, který kontrolované větě předchází.

Projděme si teď několik typů chyb, na které se kontrola zaměří. Nejjednodušší na odhalení jsou chyby rozpoznatelné pomocí lexikonu. Pokud například někdo napíše "narozdíl", což je neexistující slovo, je jednoduché chybu odhalit bez analýzy skladby. Problém může nastat u příslovečných spřežek, u nichž je možná i víceslovná varianta, často s odlišným významem, například "nahoru" vs. "na horu". V tomto případě případnou chybu neodhalíme, protože je algoritmicky těžké (i když ne nemožné) zjistit, co uživatel zamýšlel.

Na pomezí tvarosloví a skladby je podmiňovací způsob. V případě hrubky "kdyby jste" jde sice o dvě slova, ale chyba je snadno odhalitelná, protože tato dvě slova jsou vždy vedle sebe. Je také zajímavé (a možná proto se to tak plete), že ve slovenštině je výraz "keby ste" jediný správný, tam bychom ale zase mohli chtít odhalovat barbarismy typu "kebyže som".

U většiny chyb je nutné vzít v potaz větnou skladbu, a ani potom nelze vždy jednoznačně rozhodnout, jde-li o pravopisnou chybu. Například věta "Jan prodal jeho telefon" je správně, pokud Jan prodal telefon někoho jiného. Což je docela dobře možné, proto ji nelze bez hlubší analýzy opravit na "Jan prodal svůj telefon."

U shody přísudku s podmětem je situace poměrně jednoduchá, až na pár okrajových případů. Z pohledu skladby je správně "koně ržáli" i "koně ržály", ačkoliv sémanticky je správně s vysokou pravděpodobností první možnost, neboť nářadí v tělocvičně nebo šachové figurky v reálném světě ržát nebudou. Naopak "šachové koně se ztratili" je jednoznačně špatně. Podobné nuance se vyskytují naštěstí jen u mála slov (například také "roboti byli"/"roboty byly").

Zvláštní kategorií jsou přechodníky, které se používají tak málo, že mnozí pravidla jejich skloňování neznají. Tyto slovesné tvary se shodují v rodě a čísle s podmětem, jejž modifikují, píšeme tedy "učitel mi dal pětku soucitu nemaje", ale "učitelka mi dala pětku soucitu nemajíc". V množném čísle pak "učitelé mi dali pětky soucitu nemajíce". Ještě méně známé jsou některé tvary přechodníků minulých: "děti přišedše ze školy si začaly hrát," "sestra přišedši ze školy si začala hrát" a podobně. Z hlediska kontroly jde ale stále pouze o kontrolu shody s podmětem, tedy to samé, co beztak chceme pro minulý čas.

Pokud bychom chtěli opustit spisovnou češtinu a kontrolovat i některé hovorové konstrukce, první na ráně bude příklonné -s. Jedná se o jeho pozici ve větě, tedy rozdíl mezi "kdes byla" a "kde bylas" (to druhé je silně nářeční), především ale o psaní bez apostrofu. Je až nepochopitelné, jak někdo může napsat "že's byl". V angličtině se takovémuto směšnému použití apostrofu říká greengrocer's apostrophe, Němci mají výstižnější Deppenapostroph (=apostrof blbců). Ve spisovném jazyce se příklonné -s vyskytuje u zvratných sloves: "kdyby ses vrátil", "kdyby sis koupil."

Po tomto krátkém přehledu pravopisných chyb, které chceme odhalit, bude v dalším díle konečně následovat kód, který pomocí dynamického programování ukáže, jak rozpoznat skladbu věty a v ní případné chyby.