Metody Bezpiecznego Programowania

Programowanie Funkcyjne

Prowadzący (1)

mgr inż. Konrad Siek <imię.nazwisko@cs.put.edu.pl>

Walcz z entropią! Umieszczaj [MBP] jako prefiks tytułu mejla!

Zaliczenie

Warunki konieczne do otrzymania zaliczenia bloku FP:

• Obecność na zajęciach.
• Wykonanie zadań sprawdzających.
• Wykonanie indywidualnego projektu zaliczeniowego.

Zagadnienia z bloku FP są uwzględnione w kolokwium zaliczeniowym/egzaminie.

Repozytorium

• Kod źródłowy zadań: https://dsg.cs.put.poznan.pl/gitlab
• Osobny projekt w grupie MBP2014. Zadania w podkatalogach.
• Wykładowca dostaje dostęp z uprawnieniami Developer (cel: nanoszenie uwag).

Pytania?

Programowanie Funkcyjne

Motywacja i definicja

PB by Evan Amos

(c) Fir0002/Flagstaffotos

#!/bin/bash

$ cat > crew.csv
Name,                Rank,             Position,                  Post
James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

# MAGIC!

JAMES T. KIRK, CAPTAIN
SPOCK, COMMANDER
LEONARD MCCOY, LT. COMMANDER
MONTGOMERY SCOTT, LT. COMMANDER
NYOTA UHURA, LIEUTENANT
HIKARU SULU, LIEUTENANT
PAVEL CHEKOV, ENSIGN

$ cat > crew.csv
Name,                Rank,             Position,                  Post
James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

$ <crew.csv tail -n +2

James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

$ cat > crew.csv
Name,                Rank,             Position,                  Post
James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

$ <crew.csv tail -n +2 | cut -f 2,1 -d,

James T. Kirk,       Captain
Spock,               Commander
Leonard McCoy,       Lt. Commander
Montgomery Scott,    Lt. Commander
Nyota Uhura,         Lieutenant
Hikaru Sulu,         Lieutenant
Pavel Chekov,        Ensign

$ cat > crew.csv
Name,                Rank,             Position,                  Post
James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

$ <crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:]

JAMES T. KIRK,    CAPTAIN
SPOCK,            COMMANDER
LEONARD MCCOY,    LT. COMMANDER
MONTGOMERY SCOTT, LT. COMMANDER
NYOTA UHURA,      LIEUTENANT
HIKARU SULU,      LIEUTENANT
PAVEL CHEKOV,     ENSIGN

$ cat > crew.csv
Name,                Rank,             Position,                  Post
James T. Kirk,       Captain,          Commanding Officer,        USS Enterprise
Spock,               Commander,        Science Officer,           USS Enterprise
Leonard McCoy,       Lt. Commander,    Chief Medical Officer,     USS Enterprise
Montgomery Scott,    Lt. Commander,    Chief Engineer,            USS Enterprise
Nyota Uhura,         Lieutenant,       Communications Officer,    USS Enterprise
Hikaru Sulu,         Lieutenant,       Helmsman,                  USS Enterprise
Pavel Chekov,        Ensign,           Navigator,                 USS Enterprise

$ <crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

JAMES T. KIRK, CAPTAIN
SPOCK, COMMANDER
LEONARD MCCOY, LT. COMMANDER
MONTGOMERY SCOTT, LT. COMMANDER
NYOTA UHURA, LIEUTENANT
HIKARU SULU, LIEUTENANT
PAVEL CHEKOV, ENSIGN

Co w tym takiego ciekawego?

• naturalne podejście
• kompozycyjność
• bezpieczeństwo

(za darmo!)

naturalne podejście

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

vs

first_line=true
while IFS='' read -r line
do

    if $first_line
    then
        first_line=false
        continue
    fi

    IFS=, read -ra fields <<< "$line"
    echo ${fields[0]^^}, ${fields[1]^^}

done <crew.csv

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• używanie gotowych komend

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• używanie gotowych komend
• łączenie małych komend w dużą funkcjonalność

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• używanie gotowych komend
• łączenie małych komend w dużą funkcjonalność
• łatwe debugowanie/testowanie

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• używanie gotowych komend
• łączenie małych komend w dużą funkcjonalność
• łatwe debugowanie/testowanie
• przejrzystość referencyjna

kompozycyjność (composability)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• używanie gotowych komend
• łączenie małych komend w dużą funkcjonalność
• łatwe debugowanie/testowanie
• przejrzystość referencyjna
• łatwa rozbudowa

sed 's/^ //g' | sed 's/LIEUTENANT/LT./g' | sed 's/COMMANDER/CMDR./g'

<crew.csv tail -n +2 | tr -s ' ' | cut -f 2,1 -d, | tr [:lower:] [:upper:] | sed 's/^ //g' \
| sed 's/^ //g' | sed 's/LIEUTENANT/LT./g' | sed 's/COMMANDER/CMDR./g'

bezpieczeństwo (safety)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

bezpieczeństwo (safety)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• izolacja (isolation)
• spójność (consistency)

bezpieczeństwo (safety)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• izolacja (isolation)
• spójność (consistency)
• atomowość (atomicity) ... tak jakby

bezpieczeństwo (safety)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• izolacja (isolation)
• spójność (consistency)
• atomowość (atomicity) ... tak jakby

Współbieżne wykonanie:

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g' &
<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g' &
<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g' &

Jakie założenia robimy, żeby mieć komponowalność, przejżystość referencyjną i bezpieczeństwo?

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

Jakie założenia robimy, żeby mieć komponowalność, przejżystość referencyjną i bezpieczeństwo?

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• modularność (modularity)

Jakie założenia robimy, żeby mieć komponowalność, przejżystość referencyjną i bezpieczeństwo?

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

• modularność (modularity)
• bezstanowość (statelessness)
• brak efektów ubocznych (no side effects)

memosed vs bezstanowość

memosed_args=
memosed_content_hash=
memosed_processed_content=

memosed () {
    content=`cat <&0`
    content_hash=`echo "$content" | md5sum`

    if [ "$memosed_content_hash" -eq "$content_hash" ]
    then
        echo "$memosed_processed_content"

    else
        memosed_content_hash="$content_hash"
        memosed_processed_content=`echo "$content" | sed $@`
        echo "$memosed_processed_content"
    fi
}

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | memosed 's/^ *//g' &
<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | memosed 's/^ *//g' &
<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | memosed 's/^ *//g' &
<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | memosed 's/^ *//g' &

ettail vs efekty uboczne

ettail () {
    echo 'Somebody is using ettail!' | mutt -s '[MBP] Oh, happy day! :D' 'konrad.siek@cs.put.edu.pl'
    tail $@ <&0
}

# run always
<crew.csv ettail -n +2 | tee tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'
<crew.csv ettail -n +2 | tee tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

# run sometimes
<crew.csv ettail -n +2 | tee tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'
<tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

# sadness :c
<preprepared_tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'
<preprepared_tmp.csv | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

Wszystko albo nic!

magic () {
    ettail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | memosed 's/^ *//g'
}

something_else () {
    # ...
    <crew.rst magic
    # ...
}

Funkcje (matematyczne)

Funkcje (matematyczne)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

tail: Int × String → String = ...

cut: Int Set × Char × String → String = ...

tr: Char Set × Char Set × String → String = ...

squeeze: Char × String → String = ...

sed: Regex × String → String = ...

crew: String = ...

Funkcje (matematyczne)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

tail: Int × String → String = ...

cut: Int Set × Char × String → String = ...

tr: Char Set × Char Set × String → String = ...

squeeze: Char × String → String = ...

sed: Regex × String → String = ...

crew: String = ...

tail(2, crew)

Funkcje (matematyczne)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

tail: Int × String → String = ...

cut: Int Set × Char × String → String = ...

tr: Char Set × Char Set × String → String = ...

squeeze: Char × String → String = ...

sed: Regex × String → String = ...

crew: String = ...

cut({2,1}, ",", tail(2, crew))

Funkcje (matematyczne)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

tail: Int × String → String = ...

cut: Int Set × Char × String → String = ...

tr: Char Set × Char Set × String → String = ...

squeeze: Char × String → String = ...

sed: Regex × String → String = ...

crew: String = ...

tr({A..Z}, {a..z}, cut({2,1}, ",", tail(2, crew)))

Funkcje (matematyczne)

<crew.csv tail -n +2 | cut -f 2,1 -d, | tr [:lower:] [:upper:] | tr -s ' ' | sed 's/^ *//g'

tail: Int × String → String = ...

cut: Int Set × Char × String → String = ...

tr: Char Set × Char Set × String → String = ...

squeeze: Char × String → String = ...

sed: Regex × String → String = ...

crew: String = ...

sed(s/^ *//g, squeeze(" ", tr({A..Z}, {a..z}, cut({2,1}, ",", tail(2, crew)))))

Ograniczenia funkcji

• deterministyczne
• bezstanowe/niezmienne
• bez efektów ubocznych
• deklaratywne
• przejżyste referencyjnie
• (czyste, pure)

Zalety funkcji

• komponowalne (+)
• bezpieczne (+)
• zwięzłe

Programowanie funkcyjne

Paradygmat programowania za pomocą funkcji (matematycznych)

Rozwiązywanie problemów w sposób funkcyjny

Mam zbiór S który zawiera liczby całkowite. Chce mieć zbiór T który będzie miał te same liczby całkowite, ale powiększone o jeden.

Rozwiązywanie problemów w sposób funkcyjny

Mam zbiór S który zawiera liczby całkowite. Chce mieć zbiór T który będzie miał te same liczby całkowite, ale powiększone o jeden.

• Jak to rozwiązać imperatywnie (aka "normalnie")?

Rozwiązywanie problemów w sposób funkcyjny

Mam zbiór S który zawiera liczby całkowite. Chce mieć zbiór T który będzie miał te same liczby całkowite, ale powiększone o jeden.

• Jak to rozwiązać imperatywnie (aka "normalnie")?
• Jak to rozpisać jako funkcje matematyczne?

Rozwiązywanie problemów w sposób funkcyjny

Mam zbiór S który zawiera liczby całkowite. Chce mieć zbiór T który będzie miał te same liczby całkowite, ale powiększone o jeden.

• Jak to rozwiązać imperatywnie (aka "normalnie")?
• Jak to rozpisać jako funkcje matematyczne?
• Jak zaimplementować kwantyfikator?

Skomplikowane?

Można programować funkcyjnie (prawie) w dowolnym języku, ale języki funkcyjne mają mechanizmy które ułatwiają takie programowanie.

Języki funkcyjne:

• Scala
• Ocaml
• F#
• Haskel
• Erlang
• Lisp
• Clojure

Języki z elementami funkcyjnymi:

• Python
• Groovy
• Ruby
• Javascript

Na pewno wszystko się da zaimplementować?

Twierdzenie Church'a-Turing'a.

Na pewno wszystko się da zaimplementować?

Twierdzenie Church'a-Turing'a.

Monady.

Zalety

Zalety programowania funkcyjnego:

• Zwięzłość - rozwiązania prostych problemów przeniesione do kompilatora; każda linia programu jest:

  • tańsza do wytworzenia
  • tańsza w utrzymaniu

• Programowanie współbieżne:

  • Determinizm
  • Bezpieczeństwo wątków (thread safety)
  • Mniej problemów współbieżnych

• Testowanie jednostkowe -- brak efektów ubocznych
• Dowodzenie poprawności
• Optymalizacja kompilatora
• Geek cred

Zalety

Maybe functional programming isn't the answer... or maybe functional programming can't magically protect you from using poor abstractions and writing bad code.

Michael Shaw. Game development in Scala.

Wady programowania funkcyjnego:

• Wydajność.
• Wymagania pamięciowe.
• Inny sposób myślenia o problemach -- przestrzeń, nie czas.

Ankieta

Materiały

Książki:

• Joshua Suereth D. Scala in Depth. (dostępna w BT)
• Martin Odersky, Lex Spoon, Bill Venners. Programming in Scala. (dostępna online)
• Michel Schinz, Philipp Haller. Scala Tutorial for Java programmers. (dostępna online)
• Harold Abelson, Gerald Jay Sussman, Julie Sussman. Structure and Interpretation of Computer Programs (dostępna online)

Materiały

Wideo:

• Kelsey Innis. Learning Functional Programming without Growing a Neckbeard. SF Scala 2012.
• Neal Ford. Functional Thinking. OSCON 2013.
• Martin Odersky. Working Hard to Keep It Simple. OSCON Java 2011.
• Martin Odersky. Scala -- the Simple Parts. SF Scala 2014.
• Venkat Subramaniam. Why Scala?
• Philip Wadler. Faith, Evolution, and Programming Languages: from Haskell to Java. Tech Mesh 2012.
• Rúnar Bjarnason. Functional Programming is Terrible. NEScala 2014.
• Robert C Martin. Functional Programming; What? Why? When? NDC2014.
• Rich Hickey. The Values of Values. JaxConf 2012.
• John Hughes and Mary Sheeran. Why Functional Programming Matters. Code Mesh 2015.

Materiały

Inne:

• Functional Programming For The Rest of Us
• EPFL. Functional Programming Principles in Scala (Coursera).
• University of Washington. Programming Languages (Coursera).
• Michael Shaw. Game development in Scala.
• Steve Yegge. Execution in the Kingdom of Nouns.