niedziela, 18 grudnia 2016

Sprawność ITSilnika

Za wikipedią : https://pl.wikipedia.org/wiki/Sprawno%C5%9B%C4%87

Sprawność – skalarna bezwymiarowa wielkość fizyczna określająca w jakim stopniu urządzenie, organizm lub proces przekształca energię występującą w jednej postaci w energię w innej postaci, stosunek wartości wielkości wydawanej przez układ do wartości tej samej wielkości dostarczanej do tego samego układ.

Mamy na przykład sprawność silnika cieplnego, do tego z technikum pamiętam, że generator prądu też miał sprawność, a no i w zasadzie wszystko co zamienia jeden rodzaj energii na inny ma sprawność. Zamiana energii programisty w implementację ficzerów też ma swoją sprawność. Zerkniemy trochę na tę sprawność. Trochę na serio ale bardziej nie na poważnie. Bo tak na poważnie to się nie da.

mała uwaga

Jeśli pojawia się słowo "sprawność" to najpierw ostrzeżenie. Niestety branża IT przepełniona jest masą folkloru i samozwańczych metodyk wytwarzania końcowego produktu co owocowało tym, że "sprawność pracy" w przeszłości była określana na podstawie chybionych porównań pomiędzy skrajnie różnymi formami pracy. I tak ludzie, którzy nie za bardzo znali się na wytwarzaniu oprogramowania ale regularnie prasowali swoje koszule określili, że miernikiem sprawności pracy jest ilość wytwarzanych linijek kodu bo przecież jak produkujemy śrubki to im więcej normy ktoś wyrobi to chyba lepiej tak?

To co mam nadzieję zobaczymy poniżej powinno nas przekonać, że jest odwrotnie. Im mniej linii kodu tym lepiej. (z założeniem odpowiedniej czytelności co też trudno zdefiniować bo czasem brak czytelności kodu to nie właściwość kodu ale właściwość niesatysfakcjonującego poziomu wiedzy osoby ten kod czytającej ) . A w zasadzie jak ktoś ma ten współczynnik ujemny czyli np -100 oznacza usunięcie 100 lii kodu i uzyska oczekiwany efekt - to ten ktoś powinien dostać kurde bonus. Każda linia kodu to potencjalne bugi a tu linie kodu poznikały a ficzery są! W zasadzie jeśli programista jest w stanie przyjść do pracy i zrobić ficzera zgodnie z założeniami jakości kodu w 30 minut to powinien iść do domu bo każda minuta obecności programisty przy komputerze zwiększa prawdopodobieństwo pojawienia się bugów.

Na koniec obligatoryjne wspomnienie klasyki : https://en.wikipedia.org/wiki/The_Mythical_Man-Month by przypomnieć, że już od 40 lat niektórzy śmieją się z tworzenia programowania przy pomocy "metodyki ludzkiej fali", o i teraz można przejść do rzeczy prostszych czyli języków programowania.

Sprawność programowania

Jest taki dowcip, że programowanie to konwersja kawy do linii kodu (taki śmieszny śmieszny dowcip). Można to uogólnić na wymianę energii psycho-fizycznej programisty w uporządkowany zestaw cybernetycznych operacji na abstrakcyjnych formach informacji, które to można dla uproszczenia nazwać "ficzerami produktu, które przynoszą hajs".

I tak np. dla uproszczenia rozważmy formę zminimalizowaną tych ficzerów - niech "ficzer" na początku będzie reprezentowany przez minimalną logikę inkrementująca inta. Mamy tu przykład Javy 7 i Javy 8 także zostajemy w mainstreamie.

//Java7
Function<Integer,Integer> inkrementuj7=new Function<Integer, Integer>() {
    @Override
    public Integer apply(Integer integer) {
        return integer+1;
    }
};

//Java8
Function<Integer,Integer> inkrementuj8 = i -> i+1;
W pierwszym przypadku potrzeba więcej ruchów palcami, spalenia większej ilości kalorii i większej aktywności pomiędzy neuronami by wyprodukować rezultat dokładnie taki sam jak jedno-linijkowiec poniżej.

Teraz zerknijmy na bardziej rozbudowany przykład - funkcja map, która robi podobne manipulacje jak analogiczna metoda na Stream'ach - zmienia każdy z elementów według podanej funkcji prostej 'f' -> stąd zagnieżdżone wewnętrzne Function w typie.

Function<List<Integer>,Function<Function<Integer,Integer>,List<Integer>>> map = input -> f -> ...; 

Typ jest dosyć zakręcony a to w zasadzie jedna z najprostszych sygnatur funkcji wyższego rzędu jakie można spotkać. Zobaczmy co możemy uzyskać po wprowadzeniu łatwiejszej notacji typów. Tym razem scala :

val mapFull: Function[List[Integer],Function[Function[Int,Int],List[Integer]]] = input => f => ???
    
val map : List[Integer] => (Int=>Int) => List[Integer] = input => f => ???
Chociaż na początku wydaje się, że różnica to tylko kilka centymetrów to jednak z punktu widzenia programisty różnica w poświęconej energii na kodowanie/dekodowanie typu rozszerzonego jest odczuwalna. Przynajmniej ja ja odczułem. Może drogi czytelniku/czytelniczko przeprowadzić swój własny eksperyment i spróbować popisać samemu/samej te typy.

Ciekawą rzeczą jest tutaj także koszt dekompresji rozwiązania do mózgu programisty i subiektywna ocena tego kosztu wynikająca czasem z braku odpowiedniego doświadczenia. Na przykład :

map(List(1,2,3))(e=>e+1)
map(List(1,2,3))(_+1)
Ten podkreślnik .W scali możemy zastosować taki "plejsholder" zamiast powtarzać wystąpienie argumentu. Dla mnie osobiście jest to trochę czytelniejsze (to z podkreślnikiem) natomiast pamiętam na początku, że nie zawsze było dlatego potrzebny jest pewien czas ekspozycji na dane rozwiązanie by subiektywnie było zakwalifikowane do indywidualnego worka "(według mnie) obiektywnie czytelne"

Dane

Podobnie jak z operacjami na informacjach tak samo można podejść do kosztów energetycznych tworzenia samych informacji. Jaki wqysiłek mierzony w ruchach palcami (a przypomnijmy, że jakieś tam zapalenie nadgarstków to zawodowa choroba programistów) należy ponieść by zdefiniować dane?

Java
class User{
    private Long id;
    private String name;

    public User(Long id, String name) {
        this.id = id;
        this.name = name;
    }

    public Long getId() {
        return id;
    }

    public String getName() {
        return name;
    }
}
Kotlin i Scala
//Kotlin zwykła klasa
class User(val id:Int,val name:String)

//Kotlin klasa z equalsami,hashcodami i innymi takimi
data class User(val id:Int,val name:String)

//scala zwykła klasa
class User(val id:Int,val name:String)

//scala - klasa z całym dobrodziejstwem inwetnarza hasz kody,equalsy i pattern matching
case class User(id:Int,name:String)

Oczywiści w 2016 roku nie trzeba każdej literki pisać z osobna bo IDE dużo samo pogeneruje jednakże już w trakcie analizy - nawet mając do czynienia ze znajomymi wzorcami gettery/gettery/gettery - trzeba to gdzieś w pamięci operacyjnej zmagazynować i chyba wtedy zdaje się sód albo jakiś inny pierwiastek jest używany do zmiany potencjału na aksonach (końcówki neuronów) i później jakieś odpadki wyładowań elektrycznych, które po tych wymianach danych pozostały pomiędzy neuronami, muszą być w trakcie snu usunięte.

W javie jest jeszcze ten Lombok. Nie znam produktu jako takiego ale skoro ludzie chcą go używać to strzelam, że ilość mechanicznego kodu, który inaczej musieliby napisać ręcznie jest dla nich bolesna. Coś tam słyszałem, że w Javie 10 może jakas lepsza składnia będzie. Jak będzie to będzie.

Bonus : bezpieczne granice

Ponieważ pojawiła się Scala to być może pojawią sie opinie, że trudny język, że tak dalej i tak dalej... Generalnie o ile przy przejmowaniu kodu z dalekich krain trzeba mieć się na baczności o tyle samemu kontrolując granice można naprawdę traktować scalę jak wygodniejszą jave. I chociaż w środowisku scalowym często sformułowanie "używać scalę jako lepszą javę" często jest używane trochę z negatywnym zabarwieniem, że ktoś niby nie stosuje/rozumie technik niedostępnych w javie (wolne monady 147 poziomu) - o tyle jeśli ktoś zdecyduje się przejść z javy do scali to to jednak od czegoś trzeba zacząć. Można zacząć od prostych rzeczy zgodnie z powiedzeniem "lepszy rydz niż nic".

Pomimo, że scala kojarzy się (przynajmniej mnie) z popularyzacją podejścia funkcyjnego to - być może nie jest wiedza powszechna - ale ale Scala jest bardziej obiektowa niż Java. Bo jak to większość czytanek wspomina - w Javie wszystko jest obiektem.... no może poza klasą która ma same metody statyczne,... no i może poza int... i w sumie też nie long. No i boolean to też nie obiekt.

Weźmy taki standardowy przykład z abstrakcją za interfejsem i fabryką implementacji realizujących tę abstrakcję - możemy to strzelić w scali w kilku linijkach

trait Abstraction{
  def abstractProcess(s:String):String
}

class ConcreteImplementationDupa extends Abstraction{
  override def abstractProcess(s: String): String = s+"dupa"
}

object SurpriseFactoryPattern{
  def create():Abstraction = new ConcreteImplementationDupa
}

I co najważniejsze - jeśli będziemy trzymać się koncepcji, które dla javy 8 nie są czymś obcym to pod spodem dostaniem byte code, który też nie powinien zawierać niespodzianek. I tak trait z abstrakcyjnymi metodami kończy jako zwykły interfejs

public interface jug.lodz.workshops.Abstraction {
  public abstract java.lang.String abstractProcess(java.lang.String);
}

A klasa to zwykła klasa
public class jug.lodz.workshops.ConcreteImplementationDupa implements jug.lodz.workshops.Abstraction {
  public java.lang.String abstractProcess(java.lang.String);
  public jug.lodz.workshops.ConcreteImplementationDupa();
}

Fabryka jako, że stanowi koncept dla javy8 obcy czyli singleton na poziomie języka - jest odwzorowany przy pomocy dwóch klas SurpriseFactoryPattern.class i SurpriseFactoryPattern$.class - czyli jedna jedyna instancja i dostęp do tejże instancji poprzez statyczne metody - w javie jako javie inaczej chyba się nie da

Również jesli chodzi o sygnatury funkcji process kompilacji jest przewidywalny i a na poziomie kodu mamy bardzo czytelne aliasy typów funkcji :

  val map: List[String] => (String=>String) => List[String] = input => f => input.map(f)
Są one przez kompilator zamieniane w znajome dla javy8 SAM type
public static scala.Function1<scala.collection.immutable.List<java.lang.String>,
 scala.Function1<scala.Function1<java.lang.String, java.lang.String>,
 scala.collection.immutable.List<java.lang.String>>> map();

Zakończenie

Na zajęciach z polskiego zawsze była taka teoria, że artykuł ma początek, środek i zakończenie. Gdzie zakończenie to wstęp tylko innymi słowami. Zamiast się tutaj produkować przeczytajcie sobie raz jeszcze wstęp ale co drugie słowo to wyjdzie coś oryginalnego z tym samym przesłaniem i tyle na dzisiaj starczy.

poniedziałek, 21 listopada 2016

Bezpieczny numerek

Wyobrażenie

Za każdym razem gdy spróbujemy wyjść poza najbardziej mainstreamowy język programowania na ziemi musi pojawić się pytanie ale po co. W Javie jest wszystko, frameworki, serwery, narzędzia, są obiekty - a wszystko jest obiektem to chyba jest wszystko?

W tym momencie pojawi się teza. Teza może wynikać z teorii lub obserwacji i ta tutaj wynika właśnie z szeregu obserwacji. Obserwacji, że w 2016 - czyli dwa lata po tym jak Java oficjalnie dostała w podarunku lambdy - wielu programistów javy z kilkuletnim doświadczeniem , a których miale okazję obserwować, miało pewien kłopot w operowaniu tymi "strzałkami". I nie jest to dyskusja typu "bo ja umiem a wy nie" ale raczej czy możne pewne zjawiska ubiec aby być lepiej przygotowanym gdy już nastąpią.

I tak na przykład jeśli planowałbym ogarniać strzałki od pierwszego dnia ich wprowadzenia - czyli któryś tam marzec 2014 - wtedy nie mogę ograniczyć się jedynie do javy bo nie nauczę się mechanizmu, który w tym języku jeszcze przed ta datą nie istnieje... (podobnie w 2004 gdy wyszła java5 z generykami świat javy musiał zaznajomić się z teorią, która wcześniej w nim nie istniała czyli nie możesz przygotować się do rozwoju javy ograniczając się jedynie do javy!)

I tak na przykład widziałem jak doświadczeni programiści C# szybciej łapali Scalę aniżeli ci doświadczeni w Javie7lubmniej. Być może nawet w marcu 2014 taki "uśredniony" programista C# lepiej odnalazłby się w Javie8 aniżeli jego javowy odpowiednik. Do tego kolejną zaleta poszerzenia pola widzenia jest to, że znajomość realizacji tego samego mechanizmu w dwóch lub więcej językach ułatwia zrozumienie abstrakcji, która za tym mechanizmem stoi.

No ale co było to było a za chwilę Java8 będzie miała trzecią rocznicę, lambdy - podobnie jak wcześniej generyki - z roku na rok będą stawać się integralną częścią języka, lada chwila ma być wydana książka "Functional Programming in Java" i istnieją już także wygodne biblioteki "lambdowe" jak Javaslang. W Javie 9 i 10 są zapowiadane pewne udogodnienia (Project_Valhalla) ale na horyzoncie nie widać kolejnej wielkiej rewolucji.

Ale czy na pewno...? (tak z akcentem na 'NA PEwno', i do tego przydałby się jakiś podkład muzyczny - może jakiś wczesny scooter?)

Idzie nowe

The Essence of Dependent Object Types - to tytuł pracy - takiej naukowej - na którą można natrafić o tu --> http://dotty.epfl.ch/#why-dotty a "TU" to strona platformy dotty, która (chyba) ma zdefiniować jak będzie wyglądała Scala 3.0. Jeśli wierzyć autorom mamy do czynienia z zupełnie nowym potężnym podejściem do typów w językach prorgamowania. Niestety z dokumentu za wiele nie rozumiem a samo dotty jest work in progress.

Ale gdy tak siedzę nieco zagubiony nagle, tak znienacka wyłania się język, który w kwestii edukacji może być dla "Typów Zależnych" tym samym czym Haskell dla "Programowania Funkcyjnego " - mowa o Idris. Co ciekawe ten język jest w istocie napisany "na" Haskellu i ma bardzo podobną składnię także w tym przypadku dla mających jakieś pojęcie o Haskellu łatwiej jest zacząć. Tyle gadaniny - zerknijmy trochę pod pokrywkę.

Typ Typu

Cały bajer z typami zależnymi polega na tym, że typ może mieć typ, który może mieć typ itd. Nie będę tutaj grał fachury bo sam hoduje sobie neurony by ogarnąć ten temat ale nawet na najprostszych przykładach widać jak obiecujący jest to mechanizm.

Pierwsza rzecz do której musimy się przyzwyczaić to ta rekurencyjna koncepcja pojęcia typu. Jeśli znowu wrócimy do Javy to przed javą 5 lista to była sucha konstrukcja. Od javy 1.5 możemy już np. mówić, że Lista ma typ String czyli :

List<String>
A teraz... jeśli to pójdzie dalej to ta lista stringów też może mieć typ - dokładnie tak - typ typu - np. List typu String o typie długość cztery
List<String><4>
Oczywiście w Javie nie ma czegoś takiego ale czas na Idris gdzie taka sytuacja to stan naturalny :
fourElements : Vect 4 String
fourElements = ["pierwszy","drugi","trzeci","czwarty"]
Gdybym się pomylił i dał inną ilość elementów to to się nawet nie skompiluje!
fourElements = ["pierwszy","drugi","trzeci"]

No i teraz pierwsze miejsce gdzie ta konstrukcja może sie przydać. Zerknijmy na poznaną już Java8 metoda Stream.map , zmieniająca każdy element według instrukcji podanej w postaci funkcji a->b. W takim javowym pseudokodzie to będzie coś takiego :

List<B> result= List<A>.stream.map(fab).collect(toList);
Problem polega na tym, że mając zabezpieczenie tylko tymi typami a->b bardzo łatwo popełnić błąd. Co gdy zawsze będę zwracać pustą listę? I tak się skompiluje. Podobnie jak analogiczny przykład z Idris z użyciem typu List, która nie ma zależnego typu długości
customStandardMap : (a->b) -> List a -> List b
customStandardMap f [] = []
customStandardMap f (x :: xs) = []
Natomiast gdy przerzucimy się na typ Vect, którego typ ma swój typ dostaniemy taką oto sygnaturę :
customMap : (a -> b ) -> Vect n a -> Vect n b
n to długość kolekcji i przy tak zapisanej funkcji nie ma wyjścia, kolekcja zwracana musi mieć taką samą długość jak ta podana!
-- this will not compile!!!
customMap f [] = []
customMap f (x :: xs) = []

Czas na numerek

Teraz coś z zupełnie innej beczki. Czy można wartość dowolnej liczby naturalnej (jedne, milion,pierdzyliard) zaprezentować przy pomocy jedynie dwóch typów?

Jeśli ktoś spróbował w życiu Scali wie, że tam Lista to nie tyle "kolekcja N elementów" ale po prostu : "element z przodu i (być może) reszta listy". Lista tam jest tzw. typem algebraicznym czyli ściśle ograniczoną rodziną możliwych typów z jasno zdefiniowanymi nań operacjami. A w praktyce Lista to albo ... "Lista" albo "Koniec listy" co pozwala nam wygodnie używać tej konstrukcji rekurencyjnie

safeListIteration: List Integer -> String
safeListIteration [] = ""
safeListIteration (x :: xs) = show x ++":"++ safeListIteration xs

No i teraz jeśli zadziałało dla listy to możemy sobie wyobrazić Kolejne liczby naturalne jako taką listę z końcem ogonka na zerze. I w ten oto sposób dostaniemy bardzo bliźniaczy kod

safeNumberIteration : Nat -> String
safeNumberIteration Z = ""
safeNumberIteration (S k) = show k ++":"++ safeNumberIteration k

Jest to trochę taki mindfuck - dowolna liczba naturalna to : albo zero albo następca innej liczby naturalnej. No i teraz jak tę definicję scalimy z typami zależnymi dostajemy kolejne możliwości zabezpieczenia poprawności programu na etapie kompilacji.

append : String -> Vect n String -> Vect (S n) String
append x [] = [x]
append x xs = x :: xs

Czyli jeśli dodamy element do kolekcji to nie ma ku**a innego wyjścia jak tylko musimy otrzymać kolekcję gdzie długość to kolejna liczba naturalna względem długości kolekcji pierwotnej (być może trzeba to zdanie przeczytać sobie raz jeszcze)

Program zabezpieczony

A teraz taka sytuacja. Jak w Javie byśmy się zabezpieczyli przed np. podaniem indexu przekraczającego długość kolekcji? Albo jak się zabezpieczyć przed podaniem 369 w miejsce gdzie jest spodziewany dzień miesiąca? A jak już się zastanawiasz i widzisz te ify sprawdzające poprawność wartości w rantajmie - to kolejne pytanie - jak to zrobić w trakcie kompilacji?

Weźmy na to ten kalendarz i tylko trzy pierwsze miesiące by było mniej pisania

nToMonth : Fin 3 ->  Month
nToMonth i = case finToInteger i of
                  0 => January
                  1 => February
                  2 => March

Ok co ja pacze? Co to jets ten Fin 3? Otóż jest to zabezpieczenie na poziomie typów - czyli i kompilacji, takie że tam jako argument tejże metody otrzymamy wartość skończoną z zakresu 0-2. Jeszcze raz - TYPÓW - T-Y-P-Ó-W - Typów - types - типы. Jeśli to się skompiluje to znaczy, że działa! Jeszcze raz - jak to się skompiluje to znaczy, ze działa!

No ok ale skąd ten Fin się ma wziąć?. Trzeba pomyśleć o tym w szerszym kontekście. Ta funkcja jest taka czysto biznesowa a funkcja "sito" odpowiedzialna za komunikację z nieprzewidywalnym światem zewnętrznym będzie gdzieś indziej.

firstQuarterMonth : Integer -> Maybe Month
firstQuarterMonth i = case integerToFin i 3 of
                           Nothing => Nothing
                           Just n => Just (nToMonth n)

I teraz ładnie ogarniamy każdą możliwą kombinację wejścia czyli nasz program jako program działa zawsze poprawnie, pomimo iż w trakcie kompilacji nie wiemy co przyjdzie w runtime.

*poligon> firstQuarterMonth 0
Just January : Maybe Month
*poligon> firstQuarterMonth 1
Just February : Maybe Month
*poligon> firstQuarterMonth 2
Just March : Maybe Month
*poligon> firstQuarterMonth 3
Nothing : Maybe Month

Czaisz o co chodzi? Poprawność programu wynika z tego, że zwraca zdefiniowaną odpowiedź na każda możliwa kombinacje wejściową!

Ale czy na pewno?

Oczywiście, że nie bo użyłem tam hamskiego brute forca, żeby na siłę zamienić Fin z powrotem w integer, którego użyłem później w pattern matchingu. Dlaczego tak zrobiłem? Wynika to z prostej przyczyny : inaczej nie umiem. Nauka jest w trakcie trwania i na pewno za kilka miesięcy spojrzę na swój kod w Idris z dzisiaj i być może się porzygam ale to co fajnego wyszło w tym przykładzie, to że tak naprawdę to język zauważył, że odpierdalam a nie ja sam. Idris jest w stanie przeanalizować typy od początku do końca i sprawdzić czy funkcja jest całkowita czyli nei wystąpi jakaś nieprzewidziana kombinacja parametrów wejściowych, która zrobi nam kuku.
*poligon> :total firstQuarterMonth 
Main.firstQuarterMonth is possibly not total due to:
Main.nToMonth, which is possibly not total due to:
Main.case block in nToMonth at poligon.idr:59:19, which is not total as there are missing cases  

Linia 59 to jest dokładnie ta linia z tym brute forcem. Żeby być w stanie zrobić taką analizę programu to jest siła!!! Jeśli to nie wywróci świata IT do góry nogami w przeciągu następnej dekady...



środa, 2 listopada 2016

Wrażenia po Code retreat 2016 którego nie było

W tym roku data Global Day of Code Retreat niestety pokryła się z Mobilizacją dlatego my jako JUG Lodz tegoż wydarzenia nie organizowaliśmy nic mi nie wiadomo by ktoś inny podjął się tego zadania także w Łodzi ćwiczenia tej jesieni chyba się nie odbyły. Cóż - Zobaczymy czy daty za rok dopasują. Ale pomimo braku połączenia video z Koluszkami Górnymi czy innymi miastami wokół globu (oraz brakiem standardowego browara po zajęciach) można samemu przeprowadzić ćwiczenie i wyciągnąć jakąś naukę ze zdarzenia, które się technicznie nie odbyło.

Zasadniczo główną przeszkodą na drodze nauki jesteśmy my sami wyposażeni w bogatą kolekcję błędów poznawczych jak chociażby efekt aureoli, którą sami sobie nakładamy gdy myślimy, że doskonała znajomość jiry i kilkuletnie doświadczenie w odpalaniu tomcata automatycznie oznacza, że ogólnie "umiemy IT bardzo dobrze". "Pisanie kodu, o możliwie niskiej złożoności w wymiarze czasu i przestrzeni" to umiejętność niezależna od znajomości adnotacji w springu, doświadczeniu w konfiguracji mavena czy latach doświadczenia w przekonywaniu, że ten rysunek z 5 kwadratami to kompletny projekt systemu. Także jako umiejętność niezależną należy ją ćwiczyć niezależnie.
Więcej o takich sprawach produkowałem się rok temu : CodeRetreat 2015 i nauka są obrazki z cyklem Kolba (nie mylić z uderzeniem kolbą w skroń, która to może przynieść efekt odwrotny do zamierzonego) jest i teoria atrybucji także można sobie poczytać.

Ograniczenia i przyzwyczajenia

Im dłużej pracujemy w pewien sposób tym bardziej ten sposób dopracowaliśmy do "lokalnej perfekcji" nawet jeśli to jedynie mało wydajne "maksimum lokalne" produktywności. Gdy próbujemy wyjść ze starego sposobu to opuszczamy to maksimum lokalne i nawet jeśli za rogiem czai się potężna "górka efektywności" (ku*wa chyba pójdę w kołczing) to w pierwszym momencie i tak będzie nam szło gorzej.

Stąd też pomysł aby nałożyć sztuczne ograniczenia w trakcie pisania programu, tak abyśmy byli zmuszeni wyjść poza znane nam mechanizmy (ej naprawdę nazwać to "poza cyfrową strefe komfortu", kupić trochę pączków i jeździć po Polsce ze szkoleniami). Oczywiście ograniczenia musza być dobrane w sposób sensowny aby kierować nas w dobra stronę - a skąd wiemy, która jest dobra? CodeRetreat ma pewne gotowe schematy sesji, które czerpią inspirację z doświadczenia ludzie mających ogromne doświadczenie praktyczne. A Skąd wiadomo, że oni mają dobre doświadczenie praktyczne? Tego nie wiadomo nigdy ale taką wskazówką jest podejście tych ludzi do tematu nauki, kiedy to twierdzą iż rozumieją, że w trakcie edukacji trzeba cały czas powracać do etapu początkującego (taka skromność edukacyjna).

Mainstreamowy CodeRetreat jest raczej nakierowany na Javę i dobre praktyki programowania obiektowego - czy można to podejście wykorzystać do nauki programowania funkcyjnego? Może ograniczenie "tylko funkcje", "żadnych przypisań", "nie zmieniaj stanu", "żadnych efektów ubocznych"? No w sumie z myślą o takiej sesji, zostało przygotowane specjalne narzędzie edukacyjne - nazywa się onoHaskell...

Kod

Znam (niestety) wiele opinii i podejść do Haskella - "tego się nie używa to po co się uczyć". A może języka warto się nauczyć dla ... samej nauki? (chociaż tutaj pewnie fani Haskella powiedzą, że w praktyce tu czy tam się go używa). W Haskellu programowaniu funkcyjne jest "natywne" i przez to nauka tego podejścia idzie tam naturalnie i duzo łatwiej niż w Scali czy Javie. No jak na przykład w książce "Functional Programming in Java" jest cały rozdział o tym jak w Javie zasymulować tail recursion, które w Haskellu (a nawet w Scali) po prostu "jest" - to istnieje duże prawdopodobieństwo, że standardowy programista Javy zawróci z tej ścieżki traktując funkcje w Java8 jako taki kosmetyczny dodatek do kolekcji. (to trochę tka jakby naukę programowania zaczynać od lutowania rezystorów do płytki - "Lekcja 3 - nakładamy kalafonię")

Zasady gry Game Of Life, którą to implementuje się na code retreat - opisane są tutaj : https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life. Jak jest tyle a tyle komórek a nasza jest żywa to przezywa albo umiera. I podobnie gdy jest martwa. Czyli dosyć ciekawy zestaw wymagań gdzie występuje stan zarówno wewnątrz komórki jak i poza nią.

No to spróbujmy Haskella i zobaczmy najciekawsze fragmenty, które udało się wygenerować. Na początek w naszym kodzie - komórka. Gra życie polega na ewolucji komórek w kolejnych pokoleniach. Często ludzie słysząc, że komórka ma dwa stany myślą boolean. A Komórka to Komórka. Więc prezentujmy Komórkę jako komórkę.

data Cell = Live | Dead deriving (Show,Eq)
Kolejna rzecz, która jest jasno zdefiniowana w wymaganiach gry to zasady ewolucji komórki w zależności od sąsiadów. Widzimy więc, że komórka jest mocno zależna od stanu zewnętrznego. Trzeba jakoś przekazać tę informację i zazwyczaj tutaj pojawia się jakiś if no bo jest kilka warunków ewolucji komórki. Okazuje się, że mając mechanizmy niespotykane w Javie można te zasady w sposób bardzo czytelny napisać bez użycia ifa - oto mamy pattern matching
next :: Cell -> Int -> Cell
next Dead 3 = Live
next Dead _ = Dead
next Live 2 = Live
next Live 3 = Live
next Live _ = Dead
Następnie przechodzimy do definicji planszy. Generalnie pisząc raz za razem game of life dochodzimy do momentu gdzie w zasadzie liczą się tylko miejsca z żywymi komórkami i możemy łatwo zasymulować nieskończoną przestrzeń przy pomocy mapy. Nie musimy także tworzyć osobnego typu na współrzędne gdyż haskella dostarcza nam wygodne aliasy. W tym przypadku zastosowanie aliasu pomaga łatwo dołożyć na przykład trzeci wymiar gdyż współrzędne działają jedynie jako "klucz" i kawałki kodu świadome ilości wymiarów są ograniczone i łatwe do ogarnięcia.
type Coordinates = (Int,Int)
type Board = M.Map Coordinates Cell

initial:: [Coordinates]
initial = [(0,0),(0,1),(1,1),(2,1)]

initialBoard ::M.Map Coordinates Cell
initialBoard = M.fromList $ map (\c->(c,Live)) initial

Tu macz comprehenszyn

W jaki sposób znaleźć współrzędne wszystkich sąsiadów? Szukamy iloczynu kartezjańskiego sasiadów w osi x z sąsiadami w osi y. W Javie można to zrobić dwoma zagnieżdżonymi forami - no chyba, że akurat jest ograniczenie "bez zagnieżdżeń" - wtedy robi się na przykład klasy Range, Surroundings i jakiś Carthesian (Function,Service co tam chceta). A w Haskellu ?
neighbours:: Coordinates -> [Coordinates]
neighbours (x,y) = [(xn,yn) |xn <- [x-1..x+1],yn<-[y-1..y+1], (xn,yn)/=(x,y) ]
No proszę tylko jedna linijka! Ale to oszukiwanie bo tam są poukrywane monady... W każdym razie podobnie możemy policzyć żywych sąsiadów
liveNeighbours :: Coordinates -> Board -> Int
liveNeighbours c board = sum [1 | coord <- neighbours c,M.member coord board]
Ponieważ zyskujemy tutaj dodatkowy wymiar kompozycji pod nazwą currying czyli innymi słowy możemy niezależnie zaaplikować Board i Coordinate, więc powstaje pytanie czy obecna kolejność jest właściwa : Coordinates -> Board -> Int czy może powinno być na odwrót czyli Board-> Coordinates -> Int? O tym, że problem nie jest banalny starłem się napisać tutaj : http://pawelwlodarski.blogspot.com/2016/03/o-rany-odwrotna-kolejnosc-danych.html natomiast w tymże ćwiczeniu odpowiedzi nie znam. W tej formie w jakiej jest kod kolejność wydaje się nie mieć znaczenia bo funkcja i tak ani nie weźmie udziału w kompozycji ani nie będzie niezależnie aplikować argumentów.

Końcówka

Końcówkę umieszczam w zasadzie tylko aby za rok zrobić porównanie. Generalnie metody wydają się krótkie ale jest to złudne gdyż te kilka linijek w Javie7 zajęłoby linijek kilkadziesiąt. Logika jest dosyć "skompaktowana" i wymaga od umysłu programisty odpowiedniej mocy obliczeniowej na rozpakowanie.

potentialCells :: [Coordinates] -> [Coordinates]
potentialCells cs = [(xn,yn) | c<-cs,(xn,yn)<-neighbours c, xn>=0 , yn>=0]

nextStep :: Board -> Board
nextStep board =M.filter ( == Live) $  M.fromList $ map mapCell newCells
  where
    newCells = potentialCells $ M.keys board
    mapCell cord =(cord, next (M.findWithDefault Dead cord board) (liveNeighbours cord board))

Odpalenie też w sumie wykorzysta kilka ciekawych mechanizmów :
map (map fst  . Data.Map.toList) $ take 5 $  iterate nextStep initialBoard
    -- [[(0,0),(0,1),(1,1),(2,1)],[(0,0),(0,1),(1,1),(1,2)],[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)],
[(0,0),(0,2),(1,0),(1,2),(2,1)],[(1,0),(1,2),(2,1)]]
W wyniku dostajemy kolejne fazy gry i chyba są nawet poprawne - niestety jeszcze nie ogarnąłem tematu testów jednostkowych w Haskellu także dowód jest empiryczny. Podejście było dosyć restrykcyjne z punktu widzenia Obiektówki bo nie mamy żadnego zmiennego stanu. Natomiast widać cały czas pewne oznaki takiego trochę proceduralnego programowania gdzie kawałki kodu niejako nie komponują się a jedynie następują jeden po drugim.
Także by zabawy było więcej, czas dorzucić jakieś ograniczenia w ramach już istniejących ograniczeń.

Ograniczenia

Pojawiają się pewne rzeczy, które potencjalnie nadają się na ograniczenia
  • maks jeden $ w linii - generalnie każdy kolejny '$' można traktować jako kolejną linie kodu tyle że... w poziomie.
  • brak zagnieżdzonych nawiasów "))" - kolejny sposób na wywołanie instrukcji w instrukcji
  • brak where,let i list comprehension - tak by nie zamykać logiki w lokalnych aliasach
Kod zaczyna się podobnie, w sensie operacje na komórkach sa jasno określone przy pomocy pattern matchingu. Ciekawie zaczyna robić się przy określaniu współrzędnych. Na początek prosty jednowymiarowy generator sąsiadów z uwzględnieniem krawędzi planszy co być może jest niepotrzebne bo przecież poruszamy się po planszy nieskończonej.
surrounding :: Int -> [Int]
surrounding i = filter (>=0) [i-1,i,i+1]
I teraz zaczyna się robić naprawdę ciekawie bo aby zdefiniować współrzędne sąsiadów potrzebne jest połączenie "każdy-z-każdym". Tyle, że bez comprehension i zagnieżdżonych funkcji. Jak to zrobić?
wchodzimy na hoogle (https://www.haskell.org/hoogle/) i szukamy czegoś co połączy nam dwie listy w listę tupli, które są u nas współrzędnymi. [a]->[a]->[(a,a)]. Znajdujemy funkcję zip i jakieś inne funkcje specjalizowane. Ponieważ mamy REPLa (od wersji 9 w końcu ma być repl w Javie!) możemy sobie szybko zrobić test
zip [1,2] [3,4]
 >> [(1,3),(2,4)]
To nie to o co nam chodziło. Spróbujmy poszerzyć poszukiwania. Może znajdziemy coś co łączy dwie listy dając nam do dyspozycji mechanizm połączenia ich w wygodny dla nas sposób (a->b->c)->[a]->[b]->[c] . I tu pojawi się coś ciekawego na miejscu drugim :
  1. zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
  2. liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
Applicative w tej sygnaturze to w wolnym tłumaczeniu "Klasa Typu", która znowu w wolnym wytłumaczenia trochę po javowemu mówi, że przekazany typ musi spełniać określony interfejs. Czy lista go spełnia?
:info []
data [] a = [] | a : [a]  -- Defined in ‘GHC.Types’
instance Eq a => Eq [a] -- Defined in ‘GHC.Classes’
instance Monad [] -- Defined in ‘GHC.Base’
instance Functor [] -- Defined in ‘GHC.Base’
instance Ord a => Ord [a] -- Defined in ‘GHC.Classes’
instance Read a => Read [a] -- Defined in ‘GHC.Read’
instance Show a => Show [a] -- Defined in ‘GHC.Show’
instance Applicative [] -- Defined in ‘GHC.Base’      `` <- spełnia!spełnia! ojjjj spełnia!
...
Ale skąd weźmiemy funkcję? To jest dosyć ciekawa perspektywa poznawcza. Struktura z która pracujemy w zasadzie... jest funkcją
:t (,)
>> (,) :: a -> b -> (a, b)
i eksperyment :
Control.Applicative.liftA2 (,) [1,2] [3,4]
>> [(1,3),(1,4),(2,3),(2,4)]
Control.Applicative.liftA2 (,) [0,1,2] [1,2]
>> [(0,1),(0,2),(1,1),(1,2),(2,1),(2,2)]

Ćwiczenie można kontynuować bez wnikania w to co to jest faktycznie to Applicative. Temat jest gruby i w dużym skrócie można napisać, że Applicative umożliwia zastosowanie prostej funkcji a->b->c czyli u nas a->b->(a,b) na poziomie złozonychefektów. Tylko jakich efektów i w jakim sensie złożonych? Czego efektem jest lista? Jeśli założymy, że funkcja może mieć tylko jeden wynik to zwrócenie listy, która jest "wieloma wynikami", oznacza brak determinizmu. No bo jeśli mamy funkcję MONETA->STRONA i wyniku dostajemy [ORZEL,RESZKA] to po dwóch wywołaniach mamy [ORZEL,RESZKA] i [ORZEL,RESZKA] i łącząc ze sobą dwa niedeterministyczne wyniki otrzymujemy wszystkie możliwe kombinacje - co też zobaczyliśmy na przykładzie szukanie sąsiadów.

I to w zasadzie tyle.
Tyle?!? Ale przecież nieskończone!!!
Nie musi być skończone a nawet nie powinno dlatego sesje na code retreat trwają 45 minut i nie zakładają, że ktoś skończy. I aby nie przywiązywać się do jednego rozwiązania kasujemy kod po sesji i to też własnie robię.

Podsumowanie

W ferworze implementacji wyszło mi coś takiego map (\(coord,cell)->(coord,next cell)) na co haskell-ide zareagowała "po co się meczysz z czymś takim zamiast użyć Control.Arrow.second"

:t Control.Arrow.second 
Control.Arrow.second :: Arrow a => a b c -> a (d, b) (d, c)
Jak już myślałem, że zaczynam ogarniać te monady to teraz zerkłem se na to i : "Arrows, like monads, express computations that happen within a context. However, they are a more general abstraction than monads, and thus allow for contexts beyond what the Monad class makes possible". Także ten tego... nauka nie kończy się nigdy...

poniedziałek, 3 października 2016

Na tej pętli nie zawiśniesz

To jest taki trochę ciąg dalszy poprzedniego odcinka Kompozycja Funkcyjna w języku w którym lista dziedziczy po funkcji, który to odcinek był inspirowany dokumentem Why Functional Programming Matters.

O ile poprzednia część była o prostej kompozycji i funkcjach wyższego rzędu o tyle dalsza część wchodzi w zupełnie nowy wymiar komponowania programów dodając kontrolę nad wymiarem czasu. No bo to jest trochę taki mindfuck kiedy do tego "co jest" jako konstrukcja kodu dodajemy wymiar "kiedy i czym to jest" - wymiar który również można parametryzować. Ale najpierw ogólnie o kompozycja na rysunku.

Kompozycja jest tak naprawdę udana kiedy bierzemy dwie części i łączymy je bez dodatkowego "klejo-kodu"

A tak mniej abstrakcyjnie. Na poniższym rysunku nakrętka doskonale komponuje się z butelką i tworzy nową funkcjonalność "zamknięta butelka".

Następnie spróbujmy uzyskać zamkniętą butelkę poprzez kompozycje butelki i mapy Jury Krakowsko-Częstochowskiej (Część północna).

Pomimo iż, dobry konsultant może się wykłócić, że tak otrzymany produkt spełnia wymagania user story "as a Stefan I want to zabrać ze sobą za sklep 1 litr bimbru so that straż miejska mnie nie spisze " i wszelkie "rozlania płynu" wynikają z błędnego użycia interfejsu przez użytkownika - to jednak my - inżynierowie - wiemy w głębi duszy, że kompozycja jest nieudana

Bardzo często w takich przypadkach wywala się masę hajsu na jakiś zewnętrzny frejmłork obiecujący mimo wszystko przymocowanie mapy do butelki w sposób trwały za 100 trylionów rubli per sprint

(Odkręcanie zrobi się później w ramach utrzymania - a w przyszłości bez kleju już się nie obędzie także "vendor lock in")

Czas

No i teraz ten mindfuck. Generalnie kawałki kodu widzimy tu i teraz i myśląc o kompozycji myślimy o "kompozycji tu i teraz" w "formie zdefiniowanej tu i teraz". Idąc jeden poziom abstrakcji wyżej można wyobrazić sobie kompozycję w kontekście czasu - "skomponuj jeden fragment kodu, który kiedyś będzie działał i dopiero wtedy będzie wiadomo jak wygląda - z drugim kawałkiem kodu, który też w pewnym momencie czasu będzie pasował do kompozycji".

Mi zbudowanie intuicji wokół tej koncepcji zajęło dużo czasu i zauważyłem, że atakowanie tego tematu z różnych kierunków buduje ciekawe perspektywy pojęciowe, które pomagają zbudować swoiste "przyczółki zrozumienia". Także od ostrej abstrakcji przejdźmy teraz do zwykłych konkretów.

Pętla

Jest sobie taka zwykła pętla.

var i = 0
while(i < 100){
    println(i)
    i=i+1
}

Co można zrobić z taką zwykłą pętlą? Rozwiązuje ona doskonale pewien niszowy problem pod tytułem "wypisz 100 liczb na konsolę" ale średnio komponuje się z czymkolwiek. Na początek może spróbujmy dokodować możliwość kompozycji ze zwykłą liczbą całkowitą.

def kompozycja(limit:Int)={
   var i = 0
   while(i < limit){
      println(i)
      i=i+1
    }
  }

kompozycja(10)

Możemy iść dalej i dorobić gwint do wkręcania czynności jaka ma być wykonana wewnątrz pętli. (Kto był w technikum ten wie jak fajnie się gwintuje gwintownikiem ręcznym przez 5 godzin). I teraz można to zrobić o tak :

trait BusinessGwintownikStrategy{
  def dziaaaaaaaaałaj(input:Int):Unit
}


object WypisywaczProfessionalStrategy extends BusinessGwintownikStrategy{
  override def dziaaaaaaaaałaj(input: Int): Unit = println(s"STRATEGY $input")
}

def kompozycja(limit:Int,strategy : BusinessGwintownikStrategy)={
  var i = 0
  while(i < limit){
    strategy.dziaaaaaaaaałaj(i)
    i=i+1
  }
}

kompozycja(10,WypisywaczProfessionalStrategy)

Tylko na ch*j? W tej całej strategi nie ma nawet jakiegokolwiek stanu także po co się męczyć z jakimś pseudo obiektowym rękodziełem kiedy mamy uniwersalny standard śrubek w formie A=>B? (Chociaż UMLe zawsze można za dodatkowy hajs ojebać. No i do tego fajnie wyglądają w powerpointach)

I to jest dosyć istotny moment, że nawet go wyboldowałem. Bo teraz tak. Jak macie np. kompa to on ma interfejs USB. I są pendraivy na USB, klawiatury na USB, lampki na USB i podobno nawet takie "urządzenia peryferyjne" dla zdalnych par (if you know what i mean). Mamy do czynienia z ogólnoświatowym standardem dzięki czemu lampka na usb wyprodukowana w Chinach komponuje się z komputerem wyprodukowanym na tajwanie.

Gdyby każdy wyprodukowany komp dorzucał swój interfejs "Strategia" to nie byłaby to "Strategia" tylko "Tragedia". Dlatego warto użyć universalnego portu w postaci funkcji , która jest zdefiniowana w bibliotece standardowej i jest U-N-I-V-E-R-S-A-L-N-A (później jak ktoś bardzo chce może sobie ograniczyć dostęp ze względu na typy - dajemy wybór)

val wypisywacz : Int => Unit = i => println(s"FUNKCYJA $i" )
    
def kompozycja(limit:Int,strategy : Int => Unit)={
  var i = 0
  while(i < limit){
    strategy(i)
    i=i+1
  }
}

kompozycja(10,wypisywacz)

Gdzie ten czas?

No dobra to nadszedł czas na "czas". W tej chwili mamy dwa sposoby kompozycji (INT, INT => UNIT) z tymże w takiej formie musimy materializować je w czasie w tym samym momencie (tak wiem, że w scali można robić częściową aplikację parametrów w zwykłych metodach bo w scali można "wszystko" ale dla wygody wyprowadzanego wywodu nie mąćmy).

Aby odseparować te dwie rzeczy w czasie wykorzystajmy mechanizm wspomniany w pierwszej części "Why Functional Programming Matters" czyli Currying.

def kompozycja(limit:Int)(strategy : Int => Unit):Unit={
  var i = 0
  while(i < limit){
    strategy(i)
    i=i+1
  }
}

val kompozycjaWToku: (Int => Unit) => Unit = kompozycja(10) _
println("cos sobie wypisze dla zabicia czasu")
kompozycjaWToku(wypisywacz)

Ba! możemy pójść nawet o krok dalej i nie wykonywać programu w tym samym czasie co ustalenie ostatniej kompozycji.

//Metoda zwraca teraz typ () => Unit - nowy alias 'Program'
type Program = () => Unit
def kompozycja(limit:Int)(strategy : Int => Unit):Program=()=>{
  var i = 0
  while(i < limit){
    strategy(i)
    i=i+1
  }
}

val kompozycjaWToku: (Int => Unit) => Program = kompozycja(10) _
println("kompozycja w trakcie...")
val blueprint: Program =kompozycjaWToku(wypisywacz)
println("Jakiś czas później...")
blueprint()

Iteracja

Analogicznie do funkcji, która określa "co robić" możemy dodać dodatkową kompozycję "jak iterować."

val coDrugi: Int => Int = _ + 2

type Program = () => Unit
def kompozycja(iterator:Int=>Int)(strategy : Int => Unit)(limit:Int):Program=()=>{
  var i = 0
  while(i < limit){
    strategy(i)
    i=iterator(i)
  }
}

val iterujCoDrugi: (Int => Unit) => (Int) => Program = kompozycja(coDrugi) _
val wypisuj: Int => Program =iterujCoDrugi(wypisywacz)
val doDziesieciu : Program= wypisuj(10)
println("Jakiś czas później...")
doDziesieciu()

Nie ma róży bez kolców. To co źle tutaj działa to połączenie sposobu generowania elementów z licznikiem pętli. Na pytanie "po co byśmy chcieli to robić" odpowiemy kolejnym przykładem z artykułu Why Functional Programming matters a mianowicie iteracyjnym algorytmem na obliczenia pierwiastka kwadratowego

Czyli generalnie chciałbym aby pętla sobie chodziła - nawet i w nieskończoność - a ja niezależnie od niej co iterację chcę generować kolejne stadium rozwiązania.

Pętla tylko koncepcyjna

Można wytwarzać kolejne przybliżenia rozwiązania naszą pętlą ale zaczyna powstawać coś strasznego - metoda z tysiącem parametrów. A do tego utrudnione jest użycie zwykłych funkcji bo one w scali nie mogą mieć generyków

val wypisywacz : Int => Unit = i => println(s"FUNKCYJA $i")
val coDrugi: Int => Int = _ + 2

    
val nextRoot : Double=>Double=>Double = n => ai => (ai+n/ai)/2
def generycznyWypisywacz[A] :A=>Unit =e => println(s"e : $e")

type Program = () => Unit
def kompozycja[A](start:A)(iterator:A=>A)(strategy : A => Unit)(limit:Int):Program=()=>{
  var i = 0
  var e=start
  while(i < limit){
    strategy(e)
    e=iterator(e)
    i=i+1
  }
}

//kompozycja(0.0)(nextRoot(2))(wypisywacz)(10)  // zwykly wypisywacz nie dziala
val program=kompozycja(1.0)(nextRoot(2))(generycznyWypisywacz)(10)

program()

Ale co gorsza po odpaleniu programu nie mamy żadnego wpływu na wynik naszej operacji. Zwróć uwagę na kilka ostatnich elementów. :

e : 1.0
e : 1.5
e : 1.4166666666666665
e : 1.4142156862745097
e : 1.4142135623746899
e : 1.414213562373095
e : 1.414213562373095
e : 1.414213562373095
e : 1.414213562373095
e : 1.414213562373095

I teraz fajnie, że robimy sobie takie wstrzykiwanie zależności i parametrów ale my wcale nie potrzebowaliśmy 10 elementów bo z tego co widać 5 by wystarczyło. Ale to jest informacja, która będzie dostępna dopiero w trakcie wykonania. Czyli chociaż nasze budowanie programu jest takie trochę lazy to nijak nie umiemy tego wykorzystać w trakcie odpalania programu.

Oczywiście moglibyśmy dodać kolejny parametr w postaci funkcji A=>Boolean, który by określał warunek w pętli while ale specjalnie już trochę przekombinowałem. Nosz kurde mamy 4 parametry w metodzie - zaraz się z tego zrobi WinAPI.

Aby rozwiązać ten problem musimy totalnie zanihilować fizyczną reprezentację pętli i zachować ją jedynie w formie "koncepcji", która będzie materializowana w miarę potrzeb w trakcie wykonywania się programu.

Leniwość i Materializacja

Tutaj trochę robi się obiektowo bo tworzymy klase - ale to case klasa czyli taka klasa-dana ale nie jak w piosence oj dana dana tylko dana jako dana... w każdym razie "koncepcyjna pętla, która można iterować bez końca" wygląda tak

case class Loop[A](e:A,next:()=>Loop[A])

def petlaKoncepcyjna[A](start:A)(iterator:A=>A): Loop[A] = {
    val e2=iterator(start)
    Loop(e2,()=>petlaKoncepcyjna(e2)(iterator))
}

val Loop(e,next)=petlaKoncepcyjna(1.0)(nextRoot(2))
val Loop(e2,next2) = next()
val Loop(e3,next3) = next2()
val Loop(e4,next4) = next3()

println(s"elements : $e,$e2,$e3,$e4")
I wynik :
elements : 1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899

Nie ma co się na razie przerażać tym, że jedziemy po niej ręcznie. Co się robi na pałę da się zautomatyzować (dlatego większość programistów CRUDa kiedyś straci prace - just saying)

Co można zrobić dalej? Udajmy się po inspirację do języka czysto funkcyjnego...

Bez Klas

Haskellowo - amatorska implementacja tego co do tej pory zrobiliśmy wygląda mniej więcej tak :

data Loop a = Loop a (Loop a)

petlaKoncepcyjna :: a -> (a->a) -> Loop a
petlaKoncepcyjna start iter = Loop e (petlaKoncepcyjna e iter)
  where e = iter start

root :: Double -> Double ->Double
root n ai = (ai+n/ai)/2

element (Loop a _) = a
loop (Loop _ next) = next

Co daje nam ponownie możliwość manualnej iteracji po pętli.

*Learn> let s1=petlaKoncepcyjna 1.0 (root 2)
*Learn> element s1
1.5
*Learn> let s2= loop s1
*Learn> element s2
1.4166666666666665
*Learn> let s3= loop s2
*Learn> let s4= loop s3
*Learn> let s5= loop s4
*Learn> map element [s1,s2,s3,s4,s5]
[1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899,1.414213562373095]

Tyle, że nie ma co wyważać otwartych drzwi bo w Haskellu mamy już na to gotowca

> :t iterate
iterate :: (a -> a) -> a -> [a]

To będzie szło w nieskończoność dlatego mamy specjalny operator do określenia ile elementów nam potrzeba - w ten sposób uniezależniliśmy się od wewnętrznej iteracji po pętli

> take 10 $ iterate (root 2) 1.0
[1.0,1.5,1.4166666666666665,1.4142156862745097,1.4142135623746899,
1.414213562373095,1.414213562373095,1.414213562373095,1.414213562373095,1.414213562373095]
*Learn> :t take
take :: Int -> [a] -> [a]

Co więcej uniezależniliśmy się od sposobu określania "końca pętli"

> :t takeWhile 
takeWhile :: (a -> Bool) -> [a] -> [a]
*Learn> takeWhile (<10) $ iterate (+1) 1
[1,2,3,4,5,6,7,8,9]

Ok do szczęścia brakuje nam już tylko jednej rzeczy. Na razie operujemy na pojedynczym elemencie a na przykład chcielibyśmy określić by pętla się skończyła gdy elementy przestaną się zmieniać - a do tego musimy jakoś je ze sobą porównywać.

> let epsilon e (a,b) = abs (b-a) < e 
*Learn> epsilon 0.1 (2,1)
False
*Learn> epsilon 0.1 (2,2.01)
True

Czas na kolejny mindfuck - ponieważ nasza pętla jets teraz koncepcją wiec nie ma problemu by ja skomponować ...samą ze sobą. I do tego też jest sprzęt.

> :t zip
zip :: [a] -> [b] -> [(a, b)]

W zasadzie wszystkie części gotowe - to wio!

Learn> let squareRootSeq=iterate (root 2) 1.0
*Learn> head $ dropWhile (not . (epsilon 0.01)) $ zip squareRootSeq (tail  squareRootSeq)
(1.4166666666666665,1.4142156862745097)
*Learn> snd $ head $ dropWhile (not . (epsilon 0.01)) $ zip squareRootSeq (tail  squareRootSeq)
1.4142156862745097

Pierwsza uwaga dla hejterów, którzy będą płakać że tam się za dużo dzieje - ludzie... to jest REPL, w programie możecie sobie przy pomocy "where" albo "let .. in" porobić aliasy/zmienne i będzie czytelnie.

No a druga sprawa - rozwiązaliśmy problem iteracyjny bez użycia kleju komponując jedynie ze sobą poszczególne komponenty. Według autora wspominanego od czasu do czasu dokumenty "Why Functional Programming matters" taką klasyczną pętelką w jakichś kobolach wyglądało by tak :

W Javie po imperatywnemu na podstawie znalezionego w necie przykładu mamy cos takiego :

public class SqrtNewtonMethod {
    public static void main(String[] args) {
        double c = Double.parseDouble(args[0]);

        double epsilon = 1e-15;    // relative error tolerance
        double t = c;              // estimate of the square root of c

        // repeatedly apply Newton update step until desired precision is achieved
        while (Math.abs(t - c/t) > epsilon*t) {
            t = (c/t + t) / 2.0;
        }
        // print out the estimate of the square root of c
        System.out.println(t);
    }
}

Tyle, że te kawałki kodu to znowu monolityczna pętla tak jak ta z początku co rozwiązywała jeden niszowy problem!!!

Inny Problem

Aby pokazać siłę mechanizmu, którym dysponujemy pykniemy inny ciekawy problem - ciąg Fibonacciego. Każdy student wie, że są dwa rozwiązania : czytelne rekurencyjne, które wypierdala stos i drugie - nieczytelne iteracyjne z tymczasowym akumulatorem.

A tu proszę! Pojawia się trzecie, czytelne i bezpieczne dla stosu. Najpierw określamy minimum logiki specyficznej dla naszego problemu.

let fibStep (a1,a2) = (a2,a1+a2)

I KOMPOZYCJA!

> map fst $ take 20 $ iterate fibStep (0,1)
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181]

Oczywiście to jest czytelne jak się język choć trochę zna. No bo bez sensu mówić, że jest "nieczytelne" jak się języka nie zna. To tak jakby Stefan pod budką powiedział, że język Duński jest niezrozumiały bo Stefan go nie zna. Bo według Stefana to jest cecha języka Duńskiego, ze Stefan go nie rozumie a nie cecha samego Stefana.

W każdym razie może to dobry czas na rzucenie flary i przekierowanie nienawiści w inna stronę poprzez zacytowanie jak Diekstra krytykuje w 2001 "Budget Council of The University of Texas." za to, że zamienili na studiach Haskella na Jave o pod tym linkiem

I z klasami

Generalnie cały wywód z pętla w Scali wyprowadzał taką ułomna implementację Strumienia, który już jest w bibliotece standardowej zoptymalizowany i gotowy do użycia.

    //iterate podobnie jak w HAskellu
    Stream.iterate(1.0)(nextRoot(2)).take(5).toList
    //List(1.0, 1.5, 1.4166666666666665, 1.4142156862745097, 1.4142135623746899)

    val rootTwo: Stream[Double] =Stream.iterate(1.0)(nextRoot(2))

    //zip dwóch streamów
    rootTwo.zip(rootTwo.tail).take(5)


    //fibonacci
    val fibStep: ((Int,Int)) => (Int,Int) = { case (a1,a2) => (a2,a1+a2) }

    Stream.iterate((0,1))(fibStep).take(20).map(_._2).toList
    //List(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765)

Nawet w Javie

Otóż tak - można to zrobić nawet w Javie! (z domieszką javaslang)

private List<Integer> fibonacci(int limit){
        Tuple2<Integer, Integer> seed = Tuple.of(0, 1);

        UnaryOperator<Tuple2<Integer,Integer>> step=
                t->Tuple.of(t._2,t._1+t._2);

        return Stream.iterate(seed, step)
                .limit(limit)
                .map(t -> t._1)
                .collect(Collectors.toList());
 }

Także to już nie jest kwestia, który język lepszy-gorszy ale raczej krytyka pewnego sposobu myślenia. I to w sumie ciekawie nawiązuje do wstępu. Otóż okazuje się, iż kompozycja w Javie również ma charakter czaso-przestrzenny. Do 2014 są kompozycyjne wieki ciemne a później odrodzenie...

Praktyka

Teoria teorią ale bez ćwiczeń mięśnie nie rosną. Dlatego spróbojemy warsztat na podstawie artykułu "Why Functional Programming Matters" : "Functional Programming Matters" w Scali,Haskellu i Javie8 .

Plan jest taki by robić w Scali i Javie8 ćwiczenia inspirowane artykułem a później dla porównania i perspektywy edukacyjnej zobaczyć jak to będzie wyglądało w Haskellu. 13 października w czwartek o 17:30. Także zapraszam.

Mobilizacja

Konferencja Mobilization już 22 października. Bilety można kupować tutaj --> o tutaj



środa, 14 września 2016

Załamanie czasoprzestrzeni na styku paradygmatów - currying spotyka dziedziczenie

Inspiracją dla tego wpisu jest kilka pierwszych stron niezwykle ciekawego artykułu, który pojawił się w 1990 roku a tytuł jego: Why Functional Programming Matters. Jest to tez praca bardzo praktyczna bo wyśmiewa popularne podejście w dyskusjach, że "X jest lepsze bo nie można w nim robić Y" - "Programowanie funkcyjne jest lepsze bo nie ma przypisań" itd.

It is a logical impossibility to make a language more powerful by omitting features, no matter how bad they may be

Autor natomiast odwołuje się do bardzo ogólnych zasad tworzenia kodu, który dzięki odpowiedniej modularyzacji umożliwia łatwe komponowanie nowych konstrukcji z tychże modułów. Jest to rodzaj kleju, który zlepia kawałki kodu tak, że łatwo tworzyć nowe programy bez rozlewania własnego kleju w postaci dziesiątek pozagnieżdzanych ifów, które drutują dwa moduły ze sobą.

I w zasadzie cały dokument pokazuje na przykładach jak funkcje wyższego rzędu oraz "przetwarzanie leniwe" znacznie ułatwiają kompozycję kawałków kodu bez wspomnianego zewnętrznego kleju. Nie ma sensu tutaj powtarzać wszystkie bo dokument jest dostępny na necie i ma 20coś stron. Dlatego skupimy się na jednej ciekawostce. Co się dzieje gdy spróbujemy przemycić trochę obiektowości Scali do przykładów, które prezentują podejście czysto funkcyjne? Otóż dzieje się ciekawie.

Currying i foldr - dwa bratanki

Albo się zna foldr i nie trzeba tłumaczyć jak to działa albo się nie zna i trzeba doczytać - ale nie tutaj tylko trzeba podążać za strzałką ---> http://perugini.cps.udayton.edu/teaching/books/PL/www/lecture_notes/currying.html . Rysunek jest tez pożyczony z tej strony także może ktoś szybko wizualnie ogarnie.

jak już foldr ogarnięty to najpierw zerkniemy na Haskella bo wspomniany we wstępnie dokument opisuje przykłady w haskellu. Chyba. Bo to jest pismo z 1990 a wtedy z komputerów to były chyba tylko te rosyjskie jajeczka na rynku dostępne.

W każdym razie w samym foldr jedzie się od prawej (dlatego foldr ight) i zwija listę według przepisu podanego w funkcji dwuelementowej.

foldr (\x y->x+y) 0 [1,2,3,4,5]
--15

I własnie na tym polega bajer bo nie ma czegoś jak "funkcja dwuargumentowa". W każdym razie nie ma w Haskellu i chyba w takim czysto funkcyjnym programowaniu też nie ma. Nie jest to jakaś wielka strata bo łatwo można ten sam efekt uzyskać zwracając funkcję jednoelementową, która przyjmie drugi argument. To podejście zagościło już w tytule tej sekcji i nazywa się : currying (i też do doczytania)

I napisane w ten sposób dodawanie będzie wyglądać tak :

add :: Int->Int->Int
add a b = a + b

I nie jest to już tylko "taka ciekawostka" ale zastosowanie tego mechanizmu umożliwia nam zupełnie nowa formę kompozycji dwóch kawałków kodu! No bo zoba :

-- dla wszystkich "Foldable"
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
--i prosciej dla listy
foldr :: (a -> b -> b) -> b -> [a] -> b

To jest sygnatura "foldr" ze standardowej biblioteki Haskella. I cały bajer polega na tej funkcji "dwuargumentowej" , która jest typu a->b->b a zwijana tablica jest typu [a] w związku z tym mogę sobie dowolnie komponować funkcje, które działają na elementach tablicy a->a. W praktyce oznacza to zajebistą, wręcz epicką kompozycję kawałeczków kodu bo mając :

timesTwo :: Int -> Int
timesTwo x = 2 * x

addOne :: Int -> Int
addOne x = x + 1

toString :: Int -> String
toString i = show i

joinString :: String->String->String
joinString s1 s2 = s1 ++ "~" ++s2

Można teraz przetwarzać dowolnie elementy przed zwinięciem :

*Learn> foldr joinString "END" [1,2,3,4,5] 

<interactive>:38:25:
    No instance for (Num String) arising from the literal ‘1’
    ...
-- i szybko naprawiamy konwersją do string
*Learn> foldr (joinString . toString  ) "END" [1,2,3,4,5] 
"1~2~3~4~5~END"

-- a dalej jak tylko typy się zgadzają można łączyć i w lewo i w prawo

*Learn> foldr (joinString . toString . addOne  ) "END" [1,2,3,4,5] 
"2~3~4~5~6~END"
*Learn> foldr (joinString . toString . addOne . timesTwo  ) "END" [1,2,3,4,5] 
"3~5~7~9~11~END"
*Learn> foldr (joinString . toString .  timesTwo  ) "END" [1,2,3,4,5] 
"2~4~6~8~10~END"
*Learn> foldr (joinString . toString .  timesTwo . addOne ) "END" [1,2,3,4,5] 
"4~6~8~10~12~END"

Z foldLeft czy po haskellowemu foldl tak łatwo się chyba nie da bo tam zwijanie idzie od drugiej strony b->a->b

Funkcyjnie ale trochę niefunkcyjnie

A jak to wyjdzie w Scali? Też jest foldRight i jak przystało na język, który ma "wszystko", foldRight jest funkcją wyższego rzędu "na obiekcie". Jest ona funkcją wyższego rzędu, która przyjmują funkcja, która nie jest funkcją bo ma dwa parametry i zaczyna się robić ciekawie.

scala> :t List(1,2,3).foldRight("End") _
((Int, String) => String) => String

W scali Funkcja dwuargumentowa to oczywiście nic innego jak instancja klasy Function2 czyli funkcja jest obiektem i faktycznie jest bardzo hybrydowo. Problem z Function2 jest taki, że tego nie da się łatwo skomponować z inną funkcją bo "andThen" i "compose" są jedynie na Function1, która jak na funkcje przystało jest klasą.

Mamy jednakże do dyspozycji pewien most bo Function2 dostarcza nam metody na obiekcie funkcji (w końcu programowanie funkcyjne) do zmiany wersji dwuargumentowej w "currying" , "skuringowaną" funkcję jednoelementową (czy jak to tam nazwać)

 /** Creates a curried version of this function.
   *
   *  @return   a function `f` such that `f(x1)(x2) == apply(x1, x2)`
   */
  @annotation.unspecialized def curried: T1 => T2 => R = {
    (x1: T1) => (x2: T2) => apply(x1, x2)
  }

I dzięki temu możemy powrócić do świata jedno-argumentowych funkcji dzięki czemu kompozycja znów działa

val joinString:(String,String)=>String=(s1,s2)=>s1+"~"+s2
val asString:Int=>String= _.toString

//joinString compose toString  -- to nie pomalujesz to je Function2

joinString.curried  //String => (String => String) = <function1>

val convertAndJoin=joinString.curried compose asString //Int => (String => String) = <function1>

I prawie jest fajnie ale niestety foldRight w Scali wygląda tak : def foldRight[B](z: B)(op: (A, B) => B): B - czyli znowu trzeba wrócić od wersji jedno-argumentowej do dwuargumentowej. I żeby zachować spójność to tym razem dla odmiany mamy funkcję w "companion object" Function.uncurried

//List(1,2,3,4,5).foldRight("END")(convertAndJoin)  //tez sie nie kompiluje bo jednoelementowa


List(1,2,3,4,5).foldRight("END")(Function.uncurried(convertAndJoin)) 
//res1: String = 1~2~3~4~5~END

No i z odrobiną dodatkowego kleju (ale kleju już gotowego w bibliotece standardowej) możemy uzyskać podobną kompozycję jak ta omawiana we wspomnianym na początku dokumencie

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose addOne))
//res2: String = 2~3~4~5~6~END

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose addOne compose timesTwo))
//res3: String = 3~5~7~9~11~END

List(1,2,3,4,5).foldRight("END")(uncurried(convertAndJoin compose timesTwo compose addOne))
//res4: String = 4~6~8~10~12~END

Czyli w sumie spoko, trzeba trochę konwersji porobić ale da się ładnie funkcje w foldzie komponować tak? Taki chu... znaczy taka ciekawostka... teraz taka ciekawostka będzie... bo zobaczymy co się dzieje gdy następuje kolizja paradygmatów.

Taka ciekawostka

Ciekawie zaczyna się dziać kiedy dorzuci my do równania tzw. "typy wyższego rzędu" czyli np Listę.

val append:Int=>List[Int]=>List[Int]= i => l=> i ::l

Cały czas spelnia to warunek dla foldr a->b->b gdzie a::Int a b::List[Int] . No czyli tylko trzeba trzasnąć uncurring i działamy tak? To byłoby zbyt proste ponieważ w wyniku wcale nie otrzymamy funkcji dwuargumentowej

Function.uncurried(append)
//res5: (Int, List[Int], Int) => Int = <function3>

Czyżby jakiś BUG? Nie Nie, nic z tych rzeczy - to jak najbardziej FICZER!!! Otóż jak na dobry hybrydowy język przystało scala ma dziedziczenie - a szczególnie w przypadku List oj mamy dużo tego dziedziczenia... I tak List[A] rozszerza Seq[A] , które rozszerza PartialFunction[Int,A] co ostatecznie rozszerza Int=>A

No i ostatecznie List[Int] jest typu Int=>Int czyli nasza funkcja o sygnaturze Int=>List[Int]=>List[Int] może być przekazana tam gdzie spodziewany jest typ Int=>List[Int]=>Int=>Int

Do tego dodajmy kolejny obiektowy super mechanizm do zaciemniania co się naprawdę dzieje zwany "method overloading" i już mamy rozwiązanie tajemnicy

 /** Uncurrying for functions of arity 2. This transforms a unary function
   *  returning another unary function into a function of arity 2.
   */
  def uncurried[a1, a2, b](f: a1 => a2 => b): (a1, a2) => b = {
    (x1, x2) => f(x1)(x2)
  }

  /** Uncurrying for functions of arity 3.
   */
  def uncurried[a1, a2, a3, b](f: a1 => a2 => a3 => b): (a1, a2, a3) => b = {
    (x1, x2, x3) => f(x1)(x2)(x3)
  }

Były takie zasady overloadingu na certyfikat SCJP i zdaje się, że wybierana była bardziej specjalizowana metoda - no cóż sytuacja gdzie jeden typ będący częścią typu funkcji rozszerza kolejną funkcje wydaje zajebistym tematem na kolejne super praktyczne zadania na rozmowie kwalifikacyjnej (zaraz po klasycznym left-joinie i "jak zbudowana jest hashmapa") : #HurraHurraFPplusOOP

Wspomniany efekt dosyć fajnie opisany jest tutaj w tymże wątku : Jakiś wątek na forum z 2015

Największe gunwo

Największe gówno jakie widziałem w scali wygląda niepozornie bardzo :

List(1,2,2,3).toSet()
Ale co tutaj jest dziwnego? "toSet()" na liście pewnie wyrzuci powtarzające się elementy i skończmy z Set(1,2,3). Otóż nie bo wynik tej operacji to... false. Otóż toSet() na liście zwróci false -hmmm czy ta metoda nie powinna nazywać się "isSet()" ? kurwa. Nie w tym rzecz bo tam są tak naprawdę dwie metody.

//co się dzieje
val set: Set[Any] =List(1,2,2,3).toSet
set.apply(())
set.apply ()
set apply ()
set()
//teraz zastap set wyrazeniem
List(1,2,2,3).toSet.apply(())
List(1,2,2,3).toSet.apply ()
List(1,2,2,3).toSet apply ()
List(1,2,2,3).toSet ()
List(1,2,2,3).toSet()

Dokładne wytłumaczenie jest w scala-puzzlersie : http://scalapuzzlers.com/#pzzlr-040 . To jest zło. Była kiedyś taka gra "Świątynia pierwotnego zła" - to była gra gdzie magiem i druidką walczyło się własnie z takimi konstrukcjami kodu.