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