Wyrażanie ograniczeń przez system typów - przykłady

Cześć

Czytając między innymi to forum, spotykam się ze stwierdzeniami dotyczącymi języków funkcyjnych/z dobrymi systemami typów (wybaczcie, nie wiem o czym mówię), że lepiej pozwalają wyrażać ograniczenia, które normalnie są sprawdzanie w runtime, dzięki czemu kompilator pozwala wyłapywać więcej błędów. Np. takie języki jak Haskell czy Scala. Niestety nie wiem jak ugryźć ten temat i nie za bardzo potrafię znaleźć przykłady, które uzmysłowiłyby mi jak to wygląda i zachęciły do nauki tych języków. Czy mogę prosić o jakieś przykłady, bądź przynajmniej wskazanie kierunku?

Interesuje mnie to głównie w kontekście aplikacji biznesowych. Na co dzień jestem dotnetowcem ;)

Dla mnie najważniejsze aspekty to:
a) niemutowalność, która to jest defaultowa w językach funkcyjnych.
W javie też możesz używać typówów niemutowalnych, ale kompilator Ci w tym nie pomaga. Np. nie wie, że nigdzie nie podstawiasza wyniku (bo zakłada, że może robisz jakisside effekt).
Np. java nie ostrzeże Cie, jak zrobisz bigDecimal.add(otherDecimal) i nie podstawisz do wyniku.
b) wyrażenia, zamiast zdań.
if, while, switch itp. są w jezykach funkcyjnych wyrażeniami czyli nie da się zapomnieć, że coś trzeba zrobić w else.

c) bogatszy type system. Pozwala wprowadzic więcej abstrakcji (fold, monady itp),
Dzięki temu już w typie widać np. jakie są efekty uboczne i jakie ograniczenia.

Bogactwo na szybko:-)
https://stackoverflow.com/questions/26440436/how-does-scalas-type-system-compare-to-javas

Dodatkowo fp języki w wiekszości są bardzo type friendly. Czyli wprowadzanie dodatkowych typów jest tanie i nie boli. Pomocne są wszelkiego rodzaju type aliasy, konwersje itp.
Np. w javie raczej zapiszesz class Person { int age; }, a w funkcyjnym prędzej class Person { Age age;} (bo mniej boli). Przy czym poczatkowo Age to może być alias na unsigned int, który potem np. będzie dostawał dodatkowe ograniczenia.

TLDR: programować dość funkcyjnie można też w javie. To robię, to też pomaga, ale mam dużo więcej boiler plate, musze borykać się z toną i tak nie fuknkcyjnego kodu (biblioteki), a do tego kompilator mi nie pomaga.

Może tu zacznij: https://www.manning.com/books/type-driven-development-with-idris :)

Czytając między innymi to forum, spotykam się ze stwierdzeniami dotyczącymi języków funkcyjnych/z dobrymi systemami typów (wybaczcie, nie wiem o czym mówię), że lepiej pozwalają wyrażać ograniczenia, które normalnie są sprawdzanie w runtime, dzięki czemu kompilator pozwala wyłapywać więcej błędów.

Generalnie kompilator jest w stanie sprawdzać ograniczenia w czasie kompilacji dzięki statycznym typom. Im bardziej masz rozbudowany system typów, tym więcej jesteś w stanie wprowadzić tych ograniczeń. Bogatszy system typów pozwala na wprowadzanie bezpiecznych abstrakcji, które nie byłby bezpieczne przy uboższym systemie typów.

Konkretne przykłady:

1. Buildery, które sprawdzają reguły za pomocą systemu typów, a więc końcowa metoda .build() się nie wywala w czasie wykonania:
   https://japgolly.blogspot.com/2018/07/enforcing-rules-at-compile-time-example.html
   http://jim-mcbeath.blogspot.com/2009/09/type-safe-builder-in-scala-part-4.html

2. Ad-hoc polymorphism za pomocą implicitów/ typeclasses
   Jeśli nasza metoda M wymaga od parametru określonych funkcjonalności to mamy następujące rozwiązania:

• zaimplementować odpowiedni interfejs we wszystkich klasach, które wrzucamy do naszej metody M - czyli np chcemy porównywać elementy, więc wymagamy interfejsu Comparable i parametry muszą implementować Comparable - wada jest taka, że musimy mieć możliwość zmiany tych klas oraz możemy zaimplementować nową funkcjonalność na tylko jeden sposób jednocześnie
• zrobić gdzieś statyczną metodę, która sprawdza typ elementów i na podstawie tego porównuje, czyli robimy drabinkę ifów z instanceofami i obsługujemy mały wycinek klas - wada jest taka, że kompilator teraz w ogóle nie sprawdza czy typy da się porównać (dowiadujemy się dopiero gdy program wchodzi w drabinkę ifów), a ponadto statyczna metoda może być tylko jedna, a więc nie można np wybrać sobie komparatora
• dodać tą funkcjonalność do osobnej klasy B i wymagać podawania instancji klasy B razem z instancją klasy A - czyli np dla parametru klasy X podajemy instancję Comparator<X> - wadą jest to, że trzeba ten komparator explicite wszędzie przekazywać
• zrobić podobnie jak wyżej, ale uczynić parametr B implicit - Scala umożliwia tworzenie parametrów implicit, które kompilator sam wstawia w odpowiednie miejsce, a więc można stworzyć Comparatora, sprawić by był widoczny lokalnie i nie musieć go wprost podawać

W tym przypadku ten parametr typu B to w rzeczywistości typeclass. Dzięki temu, że implementację typeclassy dla typu A robi się poza typem A można dodawać operacje do typów nad którymi nie mamy kontroli (tak jak przy implementowaniu interfejsu Comparator dla np klasy z której nie da się dziedziczyć). Typeclassy mogą zastąpić klasyczne dziedziczenie i tak np jest w Ruście, Haskellu, itp Scala oferuje zarówno dziedziczenie jak i typeclassy. Ponadto w Scali można mieć wiele implementacji tej samej typeclassy dla jednego typu - można sterować ich widocznością za pomocą importów albo można je podawać explicite.

1. Path dependent types + abstract types
   Mogę zrobić następującą klasę:

abstract class Klasa {
  type T
  def producer: T
  def consumer(item: T): Unit
}

oraz np 2 implementacje:

class IntKlasa extends Klasa {
  override type T = Int
  def producer = 5
  def consumer(item: Int) = println(8 + item)
}
class StringKlasa extends Klasa {
  override type T = String
  def producer = "ala"
  def consumer(item: String) = println(item + " ma kota")
}

Następnie mogę zrobić kolekcję takich implementacji oraz metodę, która bez rzutowań i z precyzyjnym typowaniem korzysta z producera i consumera:

val klasy = Seq(new IntKlasa, new StringKlasa)
klasy.foreach { klasa =>
  var item = klasa.producer // typ: klasa.T
  // item = "bob" // nie skompiluje się, bo typ klasa.T nie redukuje się do String
  klasa.consumer(item)
  // klasa.consumer(8.0) // nie skompiluje się, bo typ klasa.T nie redukuje się do Double
}

Pisałem na szybko, więc pewnie trochę zamotałem, w szczególności jeśli chodzi o typeclasses.

Kilka przykładów ze świata Scali, które często są używane w pracy na codzień, a jednocześnie są całkiem ciekawe:

• NonEmptyList/NonEmptySet itd.
  Kolekcje, które zawierają ograniczenia że nie mogą być puste. Niby nic wielkiego, a czasami potrafią znacznie uprościć kod

• Type class'y
  Abstrakcyjna definicja możliwych do wykonywania operacji, zazwyczaj z prawami których muszą przestrzegać. Definicja jest per typ. System typów zapewnia, że konkretny typ musi mieć instancję w danym scopie. Dość prostym przykładem może być Show (https://typelevel.org/cats/typeclasses/show.html), który zapewnia, że dla danego typu jest zdefiniowana metoda konwertująca jego obiekty na poprawne stringi (coś a'la type safe toString) Do tego dochodzi np. type class derivation.

• Możliwość kompozycji
  Pozwala na definiowanie małych, łatwych do testowania klocków z których budujesz większą całość. Dość ciekawym przykładem mogą być na przykład Lens'y - http://julien-truffaut.github.io/Monocle/optics/lens.html

• Przekazywanie poprzez sygnaturę co dana funkcja może zrobić
  Chyba największy kop do produktywności jak już przywykniesz do tego. W pewnym momencie implementacje tracą na znaczeniu, a patrzysz jedynie na sygnaturę metody i jesteś w stanie pisać poprawne kawałki kodu (oczywiście nie zawsze jest to prawdą ;))

• Refined types
  Możliwość nałożenia ograniczeń na typy. Jeśli wiesz, że dany typ będzie przyjmować tylko liczby całkowite pozytywne, to zamiast go modelować jako Int możesz nałożyć na niego ograniczenie, że ma przyjmować tylko pozytywne wartości (https://github.com/fthomas/refined). W ten sposób właśnie wyeliminowałeś połowę wartości, które z założenia są błędne.

• Phantom builder
  Ot całkiem ciekawy pomysł na to, aby wykorzystać zarówno wzorzec builder jak i pomoc kompilatora. Zapewnia, że program wywali się na poziomie kompilacji jeśli builder zostanie użyty w niepoprawny sposób (np. zapomniałeś wywołać jednej metody)

*Shapeless
Kopalnia ciekawostek co można robić przy pomocy Scali (https://github.com/milessabin/shapeless), a jednocześnie jak wydłużyć czas kompilacji, żeby mieć możliwość pójścia na spotkanie, wrócenia z niego i jeszcze kawkę sobie zrobisz :)

@Wibowit: a jak to wpływa na kompilację? W Scali (jeszcze) nie programowałem, ale słyszałem że te różne dodatki powodują że ten proces jest mega powolny. Czy widać aż tak dużą różnice?

Przyrostowa kompilacja jest na tyle szybka, że nie jest w praktyce problemem. W projekcie, przy którym pracuję typowo 1-5 sekund. A nie przeszliśmy jeszcze na 2.12, która podobno jest 1,5x-2x szybsza.

Natomiast czas kompilacji projektu od zera, zimnym kompilatorem (zimny JVM) faktycznie jest niemiłosiernie długi.

Co do systemu typów, co nam się przydaje :

• Refined types w połączeniu z value types: mamy mnóstwo identyfikatorów, które w bazie są przechowywane jako UUID, ale w kodzie mamy konkretne typy, więc nie da się omyłkowo użyć złego typu identyfikatora. Taki kod jest też czytelniejszy.
• Type classes - bardzo wygodna sprawa gdy trzeba obiekty niepowiazanych ze sobą klas konwertować / serializowac w jakiś specyficzny sposób - np. do Json albo do postaci binarnej. Zwłaszcza jak te same rzeczy trzeba konwertować do kilku różnych formatów. I zwłaszcza jak nad częścią tych klas nie mamy kontroli w sensie możliwości dodawania nowych metod. Type classes > polimorfizm OOP.
• Makrami w powiązaniu z type-classes to już można cuda robić - np. możesz mieć zagnieżdzony czysty CQL w Stringu, a kompilator sprawdzi jego poprawność syntaktyczną i nawet semantyczną (np. istnienie kolumn oraz zgodność ich typów).
• W paru miejscach przydały się typy zależne. Np. masz w kodzie jakiś obiekt biznesowy klasy X, a do niego chcesz inny typ XDTO zawierający tylko wybrane informacje. I teraz masz miejsce w kodzie, gdzie musisz znać obydwa (albo z X zrobić XDTO lub na odwrót) ale chcesz żeby ten kod był abstrakcyjny i działał dla wielu takich par typów np. (X, XDTO) (Y, YDTO) itd. i jeszcze aby typ DTO automatycznie wywnioskował z podanego argumentu. Natomiast stanowczo nie chcesz aby ktoś przekazał niekompatybilne (X, YDTO).
• No i na końcu jest całe mnóstwo mechanizmów, których nie używamy wprost, ale są użyte w bibliotekach i dzięki którym te biblioteki są łatwe w użyciu i rozszerzalne. Np. dzięki typów wyższych rzędów można mieć abstrakcyjny kod biblioteczny działajacy z różnymi typami kolekcji i dodać nowe własne typy kolekcji później, bez modyfikacji istniejącego kodu.
• Wiele drobiazgów takich jak np. jeśli masz typy A, B i C, i jest zdefiniowany dla nich porządek (Ordering), to kompilator potrafi wywnioskować porządek dla trójek (A, B, C). Małe, ale jednak cieszy. Zwłaszcza że nie jest to zahardkodowane w języku, a mechanizm dostępny dla każdego twórcy biblioteki.

Szybkość kompilacji w Scali zależy w dużej mierze od stosowanych konstrukcji. O ile w takiej Javie szybkość kompilacji jest z grubsza proporcjonalna do ilości kodu źródłowego o tyle w Scali pewne konstrukcje wymagają od kompilatora większego nakładu pracy, a inne mniejszego. Najłatwiej zabić wydajność (w kolejności od najpopularniejszego sposobu do najmniej popularnego):

• importując dużą ilość implicitów (często przesadnie, np robiąc import scalaz._, import scalaz.Scalaz._ czyli importując całego scalaz naraz) i częste korzystanie z nich. Same implicity mogą być hierarchiczne, tzn kompilator szukając argumentu implicit może wykorzystać wynik metody, która sama ma kolejne parametry implicit (głębokość rekurencji zależy tylko od fantazji twórców).
• mieszając wielokrotnie duże ilości skomplikowanych traitów naraz. Tutaj klasycznym przykładem jest cake pattern, czyli niesławna metoda na wstrzykiwanie zależności. Przy niefortunnym użyciu może wydłużyć czas kompilacji o rząd wielkości (dobra wiadomość jest taka, że cake pattern jest powszechnie uznawany za antywzorzec).
• stosując często makra, bo te gryzą się z kompilacją przyrostową - tutaj nie jestem dokładnie pewien w jakim stopniu, bo z makr jakoś dużo nie korzystam (no chyba, że chodzi o scalatest, który ma trochę makr, ale one są proste)

Kompilacja typowego kodu obiektowo-funkcyjnego przebiega w całkiem OK tempie. W takim kodzie implicity są zwykle proste i jest ich niedużo. Narzut na mieszanie traitów można łatwo zminimalizować, np w przypadku testów można stworzyć klasę abstrakcyjną z wmieszanymi traitami ( http://www.scalatest.org/user_guide/defining_base_classes ) - dziedziczenie po takiej klasie jest znacznie szybsze (w sensie prędkości kompilacji, ale także rozmiar jest mniejszy) niż wmieszanie traitów z osobna za każdym. Z drugiej strony w scalaz/ cats/ shapeless/ etc jest mnóstwo hierarchicznych implicitów, ale te biblioteki są raczej dla entuzjastów kombinowania, taki trochę wyższy poziom. Jeśli ktoś wchodzi w scalaz/ cats/ shapeless/ etc słabo znając Scalę to może dostać szoku.

Podobna nierównomierność prędkości kompilacji co w Scali istnieje też np w C++. Metaprogramowanie może znacząco wydłużyć kompilację kodu C++ - kompilator po drodze będzie instancjonował masę szablonów, liczył stałe, szukał dopasowań, itd Oczywiście nie każdy piszący w C++ zajmuje się często metaprogramowaniem, ale tak samo nie każdy piszący w Scali szaleje z implicitami. Zarówno w Scali jak i w C++ zanim użyje się zaawansowanych technik (czy bibliotek wykorzystujących te techniki) trzeba się zastanowić czy zalety przewyższają wady.

stosując często makra, bo te gryzą się z kompilacją przyrostową - tutaj nie jestem dokładnie pewien w jakim stopniu, bo z makr jakoś dużo nie korzystam (no chyba, że chodzi o scalatest, który ma trochę makr, ale one są proste)

Używałem makr i bardzo wiele zależy od tego co te makra robią. Istnieją konstrukcje, które wywołane wewnątrz makra potrafią niemalże zabić kompilator. Np. ewaluacja wartości drzew za pomocą c.eval. Kiedyś nie wiedząc tego tak zrobiłem makro, które wykonywało się 500 ms, mimo że nie robiło nic specjalnego :D Po pozbyciu się evali, czas wykonania tego samego makra spadł do poniżej 1 ms. Podobnie porównywanie skomplikowanych typów ani wyszukiwanie implicitów tanie nie jest.

Ogólnie jeżeli nie robi się czegoś głupiego, to makra nie są takie strasznie drogie.
Mam taki test, gdzie jest ok. 50 zapytań CQL analizowanych naprawdę rozbudowanymi makrami (parsing CQL, type-checking wg reguł Cassandry + wyszukanie serializatorów / deserializatorów zdefiniowanych jako implicit) i type-checking całej tej klasy nie przekracza 0,5 sekundy.

Bardzo dziękuję wszystkim za odpowiedzi.
Muszę przyznać, że z wymienionych przykładów wiele jest dla mnie na ten moment dość abstrakcyjnych. Najbardziej natomiast zafascynowały mnie makra w Scali i możliwość parsowania nimi zapytań na etapie kompilacji.
Myślałem, że C# ze swoim Expression jest genialny w porównaniu do opartych na stringach rozwiązań z innych języków, ale Scala to jednak całkiem nowy poziom :)
Myślę, że będzie to element, który zachęci mnie do poznania tego języka i przy okazji przetestowania także innych pojęć.