Duck typing i inferencja

24 Lipca 2018

Spędziłem cały dzień, a może nawet więcej, myśląc o tym jak rozwiązać problem dostarczenia jak najbardziej generycznego rozwiązania inferencji typów w Great#. Poniżej omawiam sytuację oraz plusy i minusy kilku rozwiązań.

Problem

Inferencja typów jest bardzo fajna i porządana. Ale tak w sumie, to dla niefunkcyjnych typów jest trudna do ogarnięcia. Jeśli mamy operatory działające na liczbach to wnioskujemy, że zmienna jest liczbą. Jeśli mamy pattern matching to po wzorcach jesteśmy zazwyczaj w stanie określić typ zmiennej. Ale w ogólnym przypadku programowania obiektowego?

let f(x) => x.Name

Jaki typ ma x?

Przede wszystkim chciałbym zdefiniować w moim systemie typów coś takiego

x : 'T where 'T : (Name : 'a)
=>
f : 'T -> 'a where 'T : (Name : 'a)

W ogólności dopuszczałbym

'T where
    nullable 'T
    struct 'T
    comparable 'T
    equatable 'T
    'T : StaticInterface
    'T : Interface
    'T : Class
    'T : (new : ... -> 'T)
    'T<'U>    // <- 'T jest generyczne,
              // parametryzowane conajmniej jednym typem,
              // który możemy dalej ograniczać
    'T : (static operator (>=>) : 'a -> 'b)
    'T : (Method : int -> int)
    'T : (static Method : int -> int)
    'T : (Property : int)
    'T : (static Property : int)

Więc na ten moment znamy ograniczenia typu 'T. Nadchodzi kolejny krok - wywołanie funkcji f.

W szczególności poniższe rozwiązania nie biorą pod uwagę funkcji inline, których te obostrzenia nie dotyczą. Jeśli funkcja jest inline to możemy na chama podstawić konkretny typ w miejscu wywołania, jeśli wcześniej przeszedł type checking.

Pomysł 0 - value restriction

Jeśli kod nie będzie generyczny, to nie ma problemu. Przy pierwszym użyciu unifikujemy typ x z typem wartości przekazanej do funkcji.

Minus: nie jest generyczne. Jeden z głównych bólów głowy programistów. Plus: proste do ogarnięcia?

Pomysł 1 - wrappery

Pierwsze co mi przyszło do głowy to, żeby utworzyć interfejs dla tego typu, a następnie zrobić klasę, która będzie ten interfejs implementować i wywoływać odpowiednie funkcje na oryginalnym obiekcie. To się ładnie nazywa wzorzec projektowy Adapter (lub Decorator).

Żeby nie tworzyć tysiąca klas, wystarczy po jednym adapterze per klasa przez nas używana. Za to tworzymy interfejs per funkcja i adapter te wszystkie interfejsy implementuje.

Minus: dużo nowych klas i interfejsów.

Plus: funkcje mogą być użyte przez kogoś kto podepnie się pod naszą binarkę z C# i ma jasny interfejs do użycia.

Pomysł 2 - templating jak w C++

Dla każdego wywołania funkcji tworzymy jej klona podstawiając właściwe typy.

Minus: bardzo dużo powtórzonego kodu. Podpinający się z C# nie może użyć funkcji z innym typem, który nie został przez nas użyty.

Plus: niemal tak szybkie jak funkcje inline.

Pomysł 3 - dynamic

Używamy słowa kluczowego dynamic, przez co kompilator C# nie narzeka, a my i tak dostarczamy mu dobre typy i w runtimie będzie generowana konkretna sprametryzowana metoda.

Minus: koszt dynamicznego bindowania. Podpinający się z C# musi znać wymagany interfejs. Plus: mamy jeden egzemplarz metody.

Notka: moim celem jest napisanie kompilatora Great# -> C#, aby można było dołączać do niego pliki napisane w C#

Moje rozwiązanie

Nie ma jednego dobrego sposobu, więc wymyśliłem połączenie powyższych.

Najprosztszym sposobem na pozbycie się bólu głowy (to zrobiono w Scali i Nemerle) jest wymuszenie podawania typów argumentów. W Great# jest to opcjonalne, ale zalecane jeśli chcemy mieć 100% kontroli nad typami argumentów.

Gdy w deklaracji parametru x nie ma żadnych informacji, będziemy trzymali się “standardowych zasad inferencji”:

  • Jeśli przekazujemy do funkcji strukturę, to duplikujemy ją i parametryzujemy. Inaczej musielibyśmy boxować nasz obiekt, a to kosztuje.
  • Jeśli mamy do czynienia z metodą i nazwy metod parametru wyglądają na nazwy naszych metod prywatnych to z dużym prawdopodobieństwem to jest oczekwiany typ, więc robimy value restiction na siebie.
  • Jeśli aplikujemy funkcję do obiektu, który implementuje interfejs, zgodny z naszymi wymaganiami, to używamy tego interfejsu.
  • W przeciwnym wypadku uznajemy, że ten kod nie ma być generyczny i robimy value restriction na pierwszej klasie, którą do tej funkcji aplikujemy.

Ale czasem będziemy chcieli, żeby nasz kod był wyjątkowo generyczny. Wtedy użyjemy specjalnego zapisu

let f(x : ?) => x.Name
  • Zachowanie odnośnie struktur jest jak wyżej ze względu na wydajność.
  • Dla typów referencyjnych będzie jedna definicja, gdzie parametr x jest deklarowany jako dynamic.

W przypadku metod statycznych będziemy generowali wywołanie przez refleksję

let do(x : ? 'T) where 'T : (static Do : unit -> unit) =
    'T.Do()

=>

public void do(dynamic x) {
    x.GetType().GetMethod("Do", BindingFlags.Static).Invoke(null, null);
}

Przy czym, żeby powyższe dobrze działało, to x nie może być nullem.

W sumie czemu by nie zrobić z tego generyka?

let do<'T>  where 'T : (static Do : unit -> unit) =
    'T.Do()

=>

public void do<T>() {
    typeof(T).GetMethod("Do", BindingFlags.Static).Invoke(null, null);
}

Na ten moment wymyśliłem takie rozwiązanie, aczkolwiek widzę tu i ówdzie jeszcze problemy. W momencie kiedy zabiorę się za implementację to na pewno jeszcze jakieś smaczki się pojawią. Jeśli widzisz tu jakieś problemy, bądź znasz inne rozwiązania tego problemu, to zachęcam do komentowania!

P.S. W internecie ludzie piszą, że ogólnie system unifikacji Hindleya-Milnera, na którego podstawie będę robił inferencję, nie nadaje się do OOP, szczególnie kiedy mamy metody o tej samej nazwie z różnymi wersjami argumentów (overloading), stworzenie dobrego systemu typów będzie na pewno trudne.