Jednym z większych feature’ów w Great# mają być typy wyższych rodzajów - z angielskiego Higher Kinded Types (HKT). Poniżej przedstawiam co to i jak wyglądają różne podejścia do ich implementacji.
Możemy podzielić typy na trzy kategorie:
- typy konkretne
- typy pierwszego rzędu
- typy wyższych rzędów
Typy konkretne są konkretne np. int. Kolejne dwie kategorie to typy wyższych rodzajów. Rodzaj jest dla typów mniej więcej tym co funkcja dla wartości.
Weźmy pod lupę typ List<T>. Jak widzimy może być on sparametryzowany innym typem. Co więcej, musi on być sparametryzowany typem konkretnym. Jeśli rodzaj typu konkretnego to * to rodzaj typu List<T> to * -> *. Czyli niejako funkcja, która przyjmuje typ i zwraca konretny typ np. List<string>.
W .NET typy generyczne podpadają właśnie pod kategorię typów pierwszego rzędu, czyli parametryzowanych typami konkretnymi. Istnieje dyskusja na Githubie o tym czy i jak wprowadzić HKT, ale szybko go nie dostaniemy.
Teraz robi się ciekawiej. Typy wyższych rzędów to takie, które mogą być parametryzowane innymi typami, ale niekoniecznie konkretnymi.
Najlepiej ilustruje się to na przykładzie transformatorów monad. Transformatory monad to takie “wrappery” na monady, które je w pewien sposób wzbogacają.
Przypomnijmy sobie monadę Result oraz monadę State. Moja monada stanu była już połączona z monadą Result na sztywno. Chcielibyśmy zaimplementować generyczną monadę. Tak wyglądać będzie deklaracja jej typu w Great#:
union StateT<S, M, A> where M : Monad<M> = StateT of (S -> M<(A,S)>)
Jak widzimy StateT (T od transformer) ma trzy parametry - stan, wewnętrzna monada, zwracana wartość.
Jeśli chciałbym opisać jego rodzaj notacją gwiazdek to byłoby to
* -> (* -> *) -> * -> *
S M A
Przydatność transformatorów monad zasługuje na osobny post, tutaj chciałem tylko zilustrować że istnieje potrzeba na typy wyższych rzędów, które nie mają bezpośredniego wsparcia w .NETcie.
Próby rozwiązania problemu
Spotkałem się dwiema działającymi próbami rozwiązania tego problemu w F#.
W FSharpPlus mamy do czynienia z podejściem
type StateT<'s,'``monad<'t * 's>``>
Gdzie typ StateT ma dwa parametry, z czego drugi ma być konkretną monadą o typie 't * 's. Żeby dobrze to działało to dzieje się dużo inlineowania i magii ze strony kompilatora F#. Jednak sporym problemem jest to, że implementacja StateT wycieka do użytkownika.
Jeśli kompilator odmówi współpracy to trzeba będzie podać mu typ np:
let x : StateT<int, Option<string * int>> = monad { return "abc" }
Jeśli użytkownik nie wie jak zbudowane jest StateT to nie będzie umiał podać poprawnie tego typu. W Great# moim celem jest aby można było napisać
let x : StateT<int, Option, string> = do return "abc"
To pierwsze podejście można określić jako sprytne wykorzystanie kompilatora.
Drugim podejściem jest biblioteka Higher, która, korzystając z artykułu dla podobnego podejścia w języku OCaml, pozwala na zbudowanie hierarchi klasowej opartej o zdefiniowany system typów korzystający z App<'ConstrType, 'ArgumentType>. Wprowadzone jest tam dużo magii, po to aby wykorzystać istniejący typechecker do zatwierdzania użycia typów wyższych rodzajów. Jeśli chcesz więcej się o tym dowiedzieć to polecam tę serię blogpostów.
Moje rozwiązanie
Na tę chwilę stworzyłem prototyp tego jak wyglądałby generowany C#, pozwalający na korzystanie z HKT. Opiera się on na idei, że typy generyczne w .NET mogą być konkretyzowane przy pomocy object. Gdyby nie to, to kod w C# tak jak w FSharpPlus wyciekałby szczegółami implementacji.
Ponieważ kod użytkownika będzie przechodzić type checking po stronie kompilatora Great#, to kompilator C# nie musi się tym za bardzo przejmować.
Omówię teraz dogłębnie to co udało mi się stworzyć.
Great#
Zacznijmy od pełnego kodu w Great#
module Great.Monads
union StateT<S, M, A> where M : Monad<M> = StateT of (S -> M<(A,S)>)
with
public static Run(StateT(f), s) => f(s)
public static Return(x) => StateT <| (s) => do return (x,s)
public static Bind(m, f) =>
StateT <| (s) => do
let (r, s') <- Run(m, s)
Run(f(r), s')
public static Fail(x) => StateT <| (s) => do fail x
public static Lift(m) => StateT <| (s) => do
let x <- m
return (x,s)
// StateT<S, M> is a Monad
// StateT<S> is a MonadTransformer
Dwa słowa wyjaśnienia, żeby było czytelnie. Monad<M> to statyczny interfejs, który wygląda mniej więcej tak:
static interface Monad<T where T<U>>
Return : a -> T<a>
Bind : T<a> -> (a -> T<b>) -> T<b>
Fail : a -> T<b>
Deklaracja funkcji z => oznacza, że jej ciało to pojedyńcze wyrażenie. Notacja do zaczerpnięta z Haskella to uproszczenie korzystania z monad (podobne do wyrażeń komputacyjnych w F#).
Teraz przejdziemy do tej cięższej części, czyli co dostajemy po stronie C#
namespace Great.Monads
{
public class StateT<S, M, A>
{
public Func<S, M> Value { get; }
public StateT(Func<S, M> value) {
Value = value;
}
Zaczniemy od tego jak będzie wyglądać nasz typ monadyczny. Mamy funkcję ze stanu w monadę. Nie możemy określić parametrów M, bo C# na to nie pozwala - nie można aplikować parametrów do generycznych typów.
Pierwszą statyczną metodą jest Run
public static M Run(StateT<S, M, A> monad, S state)
{
return monad.Value.Invoke(state);
}
I teraz robi się najciekawiej! Zadeklarujmy sobie trzy pola zawierające odwołania do funkcji monadycznych z typu M
private static Func<object, M> returnM;
private static Func<M, Func<object, M>, M> bindM;
private static Func<object, M> failM;
Dzięki temu możemy dość łatwo przepisać kolejne metody, które będą tych funkcji monadycznych używać.
public static StateT<S, M, B> Return<B>(B x)
{
return new StateT<S,M,B>((s) =>
returnM(new Tuple<B, S>(x, s)));
}
public static StateT<S, M, B> Bind<B>(StateT<S, M, A> monad, Func<A,StateT<S, M, B>> f)
{
Func<object, M> binder = (o) => {
var t = (Tuple<A,S>) o;
return StateT<S, M, B>.Run(f(t.Item1), t.Item2);
};
return new StateT<S, M, B>((s) =>
bindM(StateT<S, M, A>.Run(monad, s), binder));
}
public static StateT<S, M, A> Fail<B>(B x)
{
return new StateT<S, M, A>((s) =>
failM(x));
}
public static StateT<S, M, A> Lift(M monad)
{
Func<S, Func<object, M>> binder =
(s) => (x) => returnM(new Tuple<object, S>(x, s));
return new StateT<S, M, A>((s) =>
bindM(monad, binder(s)));
}
Cała magia opiera się na tym jak teraz dostać te delegaty. Moje początkowe rozwiązanie korzystało z refleksji, a dokładniej MethodInfo.Invoke(...). Okazuje się, że ze względu na dodatkowe sprawdzanie typów podczas tej inwokacji jest to jakieś 60 razy wolniejsze niż wywoływanie delegatu.
Żeby móc uzyskać delegat, to jednym ze sposobów jest wyemitowanie ILu w postaci dynamicznej metody. Polecam przeczytać artykuł Why is reflection slow Matta Warrena, żeby dokładniej poznać temat.
W moim przypadku stworzyłem pomocniczą metodę
private static TDelegate EmitDelegate<TDelegate, TTarget>
(string name) where TDelegate : class
{
var methodInfo = typeof(M)
.GetMethod(name, BindingFlags.Static | BindingFlags.Public)
.MakeGenericMethod(new[]{typeof(object)});
var delegateTypes = typeof(TDelegate).GetGenericArguments();
var delegateReturn = delegateTypes[delegateTypes.Length - 1];
var delegateParams = new Type[delegateTypes.Length - 1];
Array.Copy(delegateTypes, delegateParams, delegateParams.Length);
var dyn = new DynamicMethod(
name + "M",
delegateReturn,
delegateParams,
typeof(StateT<S,M,A>).Module);
var il = dyn.GetILGenerator();
if (delegateParams.Length >= 1)
il.Emit(OpCodes.Ldarg_0);
if (delegateParams.Length >= 2)
il.Emit(OpCodes.Ldarg_1);
il.Emit(OpCodes.Call, methodInfo);
il.Emit(OpCodes.Ret);
return dyn.CreateDelegate(typeof(TDelegate)) as TDelegate;
}
Która tworzy dynamiczną metodę, wypisze do środka IL, który działa tak, że woła metodę podaną w MethodInfo, a następnie zwraca jej wynik. Na koniec dostajemy do niej delegat, którego możemy bezpośrednio używać.
Taka metoda zaistnieje w bibliotece standardowej Great#, tylko zostanie odpowiednio ulepszona - walidacja typów + więcej opcji.
Użycie jej jest mega proste
returnM = EmitDelegate<Func<object, M>, M>("Return");
bindM = EmitDelegate<Func<M, Func<object, M>, M>, M>("Bind");
failM = EmitDelegate<Func<object, M>, M>("Fail");
Na koniec stworzyłem jeszcze monadę Identity, żeby przetestować działanie. Cały kod z tego eksperymentu jest dostępny na moim GitHubie.
W C# ta definicja dla x z wcześniej wygląda w moim eksperymencie tak:
var x = StateT<int, Identity<object>, string>.Return("abc");
Czytelność i przejrzystość
Generowany przeze mnie kod w C# nie musi być w 100% czytelny, w końcu jest generowany - ma działać. Jednak ponieważ Great# nie będzie szybko miał debuggera, a C# ma bardzo dobry - to zależy mi na tym aby generowany kod był dość dobrej jakości i odzwieciedlał Great# w jakichś 80%.
Co sądzisz o moim podejściu? Zachęcam do komentowania!