Nazwa techniki wnioskowania argumentów typu parametru typu?

9

Konfiguracja: Załóżmy, że mamy typ o nazwie, Iteratorktóry ma parametr typu Element:

interface Iterator<Element> {}

Następnie mamy interfejs, Iterablektóry ma jedną metodę, która zwróci Iterator.

// T has an upper bound of Iterator
interface Iterable<T: Iterator> {
    getIterator(): T
}

Problem z Iteratorbyciem ogólnym jest taki, że musimy dostarczyć mu argumenty typu.

Jednym ze sposobów rozwiązania tego jest „wywnioskowanie” typu iteratora. Poniższy pseudo-kod wyraża koncepcję, że istnieje zmienna typu, Elementktóra ma być argumentem typu Iterator:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

A potem używamy go w taki sposób:

class Vec<Element> implements Iterable<VecIterator<Element>> {/*...*/}

Ta definicja Iterablenie używa Elementnigdzie indziej w swojej definicji, ale mój prawdziwy przypadek użycia tak. Niektóre funkcje, które używają, Iterablemuszą również mieć możliwość ograniczenia swoich parametrów do akceptacji Iterables, które zwracają tylko niektóre rodzaje iteratorów, takich jak iterator dwukierunkowy, dlatego zwrócony iterator jest parametryzowany zamiast tylko typu elementu.


Pytania:

  • Czy istnieje ustalona nazwa dla tych wywnioskowanych zmiennych typu? Co z techniką jako całością? Brak znajomości konkretnej nomenklatury utrudnił wyszukiwanie tego przykładów na wolności lub poznanie funkcji specyficznych dla języka.
  • Nie wszystkie języki z generycznymi mają tę technikę; czy istnieją nazwy podobnych technik w tych językach?
Levi Morrison
źródło
1
Czy możesz pokazać kod, który się nie kompiluje, który chcesz skompilować? Myślę, że dzięki temu pytanie będzie jaśniejsze.
Sweeper
1
Możesz także wybrać jeden język (lub powiedzieć, jakiego języka używasz i co oznacza składnia). To oczywiście nie jest na przykład C #. W Internecie dostępnych jest wiele informacji na temat „wnioskowania o typie”, ale nie jestem pewien, czy dotyczy to tutaj.
5
Wdrażam generyczne w jednym języku, nie próbując skompilować kodu w żadnym języku. To także pytanie dotyczące nazewnictwa i projektu. Dlatego jest nieco agnostyczny. Bez znajomości terminów trudno jest znaleźć przykłady i dokumentację w istniejących językach. Z pewnością nie jest to wyjątkowy problem?
Levi Morrison,

Odpowiedzi:

2

Nie wiem, czy istnieje konkretny termin na ten problem, ale istnieją trzy ogólne klasy rozwiązań:

  • unikaj konkretnych rodzajów na korzyść dynamicznej wysyłki
  • zezwalaj na parametry typu symbol zastępczy w ograniczeniach typu
  • unikaj parametrów typu, używając powiązanych typów / rodzin typów

I oczywiście domyślne rozwiązanie: wciąż przeliteruj wszystkie te parametry.

Unikaj konkretnych rodzajów.

Zdefiniowałeś Iterableinterfejs jako:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

Daje to użytkownikom interfejsu maksymalną moc, ponieważ otrzymują dokładnie konkretny typ Titeratora. Pozwala to również kompilatorowi na zastosowanie większej liczby optymalizacji, takich jak wstawianie.

Jeśli jednak Iterator<E>jest to interfejs dynamicznie wywoływany, znajomość konkretnego typu nie jest konieczna. Jest to np. Rozwiązanie, którego używa Java. Interfejs byłby wówczas zapisany jako:

interface Iterable<Element> {
    getIterator(): Iterator<Element>
}

Interesującą odmianą tego jest impl Traitskładnia Rust, która pozwala zadeklarować funkcję za pomocą abstrakcyjnego typu zwracanego, ale wiedząc, że konkretny typ będzie znany w witrynie wywołania (umożliwiając w ten sposób optymalizację). Zachowuje się podobnie do parametru typu niejawnego.

Zezwalaj na parametry typu symbolu zastępczego.

IterableInterfejs nie musi wiedzieć o rodzaju elementu, więc może to być możliwe, aby napisać to jako:

interface Iterable<T: Iterator<_>> {
    getIterator(): T
}

Gdzie T: Iterator<_>wyraża ograniczenie „T jest dowolnym iteratorem, niezależnie od typu elementu”. Bardziej rygorystycznie, możemy to wyrazić w następujący sposób: „istnieje jakiś typ, Elementwięc Tjest to Iterator<Element>”, bez konieczności poznawania konkretnego typu Element. Oznacza to, że wyrażenie typu Iterator<_>nie opisuje rzeczywistego typu i może być użyte jedynie jako ograniczenie typu.

Użyj rodzin typów / powiązanych typów.

Np. W C ++ typ może mieć członków typu. Jest to powszechnie stosowane w całej standardowej bibliotece, np std::vector::value_type. To tak naprawdę nie rozwiązuje problemu parametru typu we wszystkich scenariuszach, ale ponieważ typ może odnosić się do innych typów, pojedynczy parametr typu może opisywać całą rodzinę powiązanych typów.

Zdefiniujmy:

interface Iterator {
  type ElementType
  fn next(): ElementType
}

interface Iterable {
  type IteratorType: Iterator
  fn getIterator(): IteratorType
}

Następnie:

class Vec<Element> implement Iterable {
  type IteratorType = VecIterator<Element>
  fn getIterator(): IteratorType { ... }
}

class VecIterator<T> implements Iterator {
  type ElementType = T
  fn next(): ElementType { ... }
}

Wygląda to bardzo elastycznie, ale należy pamiętać, że może to utrudnić wyrażenie ograniczeń typu. Np. Jak napisano Iterable, nie wymusza żadnego typu elementu iteratora i interface Iterator<T>zamiast tego możemy chcieć zadeklarować . A teraz masz do czynienia z dość złożonym rachunkiem typu. Bardzo łatwo jest przypadkowo sprawić, że taki typ systemu jest nierozstrzygalny (a może już jest?).

Zauważ, że skojarzone typy mogą być bardzo wygodne jako domyślne dla parametrów typu. Np. Zakładając, że Iterableinterfejs potrzebuje osobnego parametru typu dla typu elementu, który zwykle, ale nie zawsze jest taki sam jak typ elementu iteratora, i że mamy parametry typu zastępczego, można by powiedzieć:

interface Iterable<T: Iterator<_>, Element = T::Element> {
  ...
}

Jest to jednak tylko funkcja ergonomii języka i nie czyni języka mocniejszym.


Systemy typów są trudne, więc dobrze jest spojrzeć na to, co działa i nie działa w innych językach.

Np. Zastanów się nad rozdziałem Zaawansowane cechy w Rust Book, który omawia powiązane typy. Należy jednak pamiętać, że niektóre punkty na rzecz powiązanych typów zamiast generycznych mają zastosowanie tylko tam, ponieważ język nie zawiera podtytułów, a każda cecha może zostać zaimplementowana maksymalnie raz dla każdego typu. Tj. Rust nie są interfejsami podobnymi do Javy.

Inne interesujące systemy typów obejmują Haskell z różnymi rozszerzeniami językowymi. Moduły / funktory OCaml są stosunkowo prostą wersją rodzin typów, bez bezpośredniego łączenia ich z obiektami lub sparametryzowanymi typami. Java jest godna uwagi ze względu na ograniczenia w swoim systemie typów, np. Generyczne z usuwaniem typów i brak generycznych względem typów wartości. C # jest bardzo podobny do Javy, ale udaje mu się uniknąć większości z tych ograniczeń, kosztem zwiększonej złożoności implementacji. Scala próbuje zintegrować generyczne style w stylu C # z typami klas Haskell na platformie Java. Zwodniczo proste szablony C ++ są dobrze zbadane, ale w przeciwieństwie do większości implementacji generycznych.

Warto również przyjrzeć się standardowym bibliotekom tych języków (zwłaszcza standardowym kolekcjom bibliotek, takim jak listy lub tabele skrótów), aby zobaczyć, które wzorce są często używane. Np. C ++ ma złożony system różnych możliwości iteracji, a Scala koduje funkcje dokładnego zbierania jako cechy. Standardowe interfejsy biblioteczne Java są czasami niesłyszalne, Iterator#remove()ale mogą wykorzystywać klasy zagnieżdżone jako rodzaj powiązanego typu (np Map.Entry.).

amon
źródło