Programowanie funkcyjne/Procedury wyższych rzędów

Wstęp

Wcześniej zaznaczyliśmy, że procedury są w funkcyjnych językach programowania obywatelami pierwszej kategorii, czyli są równie dobrymi wartościami jak wszystkie inne. W szczególności procedury mogą być argumentami procedur lub ich wynikami. Argumenty proceduralne występują również w imperatywnych językach programowania (np. w standardzie Pascala). Natomiast to, że procedury mogą być wynikami procedur jest czymś charakterystycznym dla języków funkcyjnych. w tym wykładzie zajmiemy się procedurami wyższych rzędów, tzn. procedurami przetwarzającymi procedury.

Uwaga

To, że w językach imperatywnych procedury mogą być przekazywane jako argumenty, a nie mogą być wynikami wynika ze sposobu kompilacji programów imperatywnych. Czytelników, którzy znają techniki kompilacji prosimy o przypomnienie sobie, w jaki sposób przekazywane są argumenty proceduralne i porównanie tego z modelem obliczeń przedstawionym w kolejnym wykładzie.

Typy proceduralne i polimorfizm

Przyjrzyjmy się kilku prostym przykładom procedur wyższych rzędów.

let p f = function x -> f x + f (2 * x);;
val p : (int -> int) -> int -> int = <fun>

Argumentem procedury p jest procedura f, natomiast jej wynikiem jest procedura będąca wartością $\lambda$-abstrakcji. Zwróćmy uwagę na typ procedury p. Możemy go przeczytać jako (int -> int) -> (int -> int). Zarówno argument f, jak i wynik p są procedurami typu int -> int.

let twice f = function x -> f (f x);;
val twice : ('a -> 'a) -> 'a -> 'a = <fun>

twice (function x -> x * (x+1)) 2;;
- : int = 42          

twice (function s -> "mocium panie, " ^ s) "me wezwanie";;
- : string = "mocium panie, mocium panie, me wezwanie"

Argumentem procedury twice jest procedura f, natomiast jej wynikiem jest złożenie f z samą sobą. Zwróćmy uwagę na typ procedury twice. Typ tej procedury czytam jako: ('a -> 'a) -> ('a -> 'a). Kompilator jest w stanie wywnioskować, że f jest procedurą i że typ jej argumentu musi być taki sam, jak typ jej wyniku (inaczej nie możnaby jej złożyć samej ze sobą). Natomiast nie wie jaki to jest typ. Tak naprawdę, może to być dowolny typ.

Mamy tu do czynienia z polimorfizmem -- ta sama procedura może być wielu typów. Oznaczenie 'a jest tzw. zmienną typową. Jeśli w typie występują zmienne typowe, to taki typ jest schematem opisującym wiele typów. Do takiego typu-schematu pasuje każdy taki typ, który możemy z niego uzyskać, podstawiając (równocześnie) za zmienne typowe dowolne typy. Przy tym, za różne zmienne typowe możemy podstawiać różne typy, ale za wszystkie wystąpienia tej samej zmiennej typowej musimy podstawiać te same typy. Na przykład, podstawiając za 'a typ int, uzyskujemy z typu ('a -> 'a) -> ('a -> 'a) typ (int -> int) -> (int -> int). Natomiast podstawiając za 'a typ 'a -> 'a, uzyskujemy typ (('a -> 'a) -> ('a -> 'a)) -> (('a -> 'a) -> ('a -> 'a)).

Uwaga

Mechanizm podstawiania typów za zmienne typowe jest dokładnie taki sam, jak podstawianie termów, za zmienne w termach.

Składanie procedur możemy zdeiniować następująco:

let compose f g = function x -> f (g x);;
val compose : ('a -> 'b) -> ('c -> 'a) -> 'c -> 'b = <fun>

Zwrócmy uwagę, że mamy tu aż trzy zmienne typowe. Mamy tu następujące zależności między typami składowych:

• wynik g i argument f muszą być tego samego typu,
• argument g i argument wyniku są tego samego typu,
• wynik f i wynik wyniku compose są tego samego typu.

Procedurę twice możemy teraz zdefiniować w następujący sposób:

let twice f = compose f f;;
val twice : ('a -> 'a) -> 'a -> 'a = <fun>

Możemy też zdefiniować wielokrotne składanie funkcji:

let id x = x;;
val id : 'a -> 'a = <fun>

let rec iterate n f =
  if n = 0 then id else compose (iterate (n-1) f) f;;
val iterate : int -> ('a -> 'a) -> 'a -> 'a = <fun>

Czy istnieją procedury wieloargumentowe?

Typy proceduralne są postaci argument -> wynik. Ponieważ zarówno argument, jak i wynik może być typu proceduralnego, więc typ może zawierać więcej "strzałek". Zastanówmy się nad typem procedur wieloargumentowych. Rozważmy następujące dwie definicje:

let plus (x, y) = x + y;;
val plus : int * int -> int = <fun>

let plus x y = x + y;;
val plus : int -> int -> int = <fun>      

Pierwsza procedura ma jeden argument, który jest parą liczb całkowitych. Druga procedura ma dwa argumenty bedące liczbami całkowitymi. Jej typ można jednak zinterpretować tak: int -> (int -> int). Można ją więc traktować jak procedurę jednoargumentową, której wynikiem jest procedura jednoargumentowa, której wynikiem jest suma. Inaczej mówiąc, procedura ta bierze argumenty na raty. Przedstawiona powyżej definicja jest równoważna następującej, lepiej oddającej możliwość brania argumentów po jednym:

let plus = function x -> function y -> x + y;;
val plus : int -> int -> int = <fun>

Można więc powiedzieć, że istnieją wyłącznie procedury jednoargumentowe, a procedury wieloargumentowe są tak naprawdę procedurami wyższego rzędu. Taki sposób patrzenia na procedury wieloargumentowe może być wygodny. Jeśli kolejność argumentów jest odpowiednio dobrana, to możemy czasem podawać tylko część z nich, otrzymując w wyniku potrzebną procedurę.

let plus x y = x + y;;
val plus : int -> int -> int = <fun>      

let inc = plus 1;;
val inc : int -> int = <fun>

Obie przedstawione formy przekazywania argumentów są sobie równoważne. Dowodem na to są poniższe dwie procedury przekształcające jedną w postać w drugą i odwrotnie. Jakiego typu są te procedury?

let curry f = function x -> function y -> f (x, y);;
let uncurry f = function (x, y) -> f x y;;

Standardową postacią podawania argumentów procedury jest "curry". Tak więc przedstawione przykłady można zdefiniować i tak:

let twice f x = f (f x);;
let compose f g x = f (g x);;
let curry f x y = f (x, y);;
let uncurry f (x, y) = f x y;;

Przykład: Sumy częściowe szeregów

Przykład - szereg (kolejnych liczb naturalnych, kwadratów, $\frac{1}{(4i-3)(4i-1)}$ zbieżny do $\frac{\pi }{8}$. Istota szeregu jako funkcja wyższego rzędu, sumowane elementy jako funkcje liczb całkowitych. Procedura sumująca $n$ pierwszych elementów danego szeregu (podać specyfikację sum):

let rec szereg f n = 
  if n = 0 then 0.0 else f n + szereg f (n-1);;
  
let szereg_pi_8 n = 
  szereg 
    (function i ->
      1. /. ((4. *. float i -. 3.) *. (4. *. float i -. 1.)))
    n;;
  
let pi = 8. *. szereg_pi_8 1000;;
     

Procedura szereg może służyć do obliczania sumczęściowych dowolnych szeregów.

Przykład: Różniczkowanie funkcji

Zdefiniujmy najpierw różniczkę:

let rozniczka f x dx = (f (x +. dx) -. f x) /. dx;;
     

Wówczas pochodną możemy przybliżyć następująco:

let pochodna f x = rozniczka f x epsilon;;
     

Zwróćmy uwagę, że pochodna jest procedurą jednoargumentową i wynikiem (pochodna f) jest funkcja będąca pochodną f.

Metoda Newtona

Zakładamy, że dana funkcja jest różniczkowalna. Pomijamy kwestie stopu i dzielenia przez 0. Metoda Newtona, nazywana też metodą stycznych, polega na przybliżaniu zera funkcji w następujący sposób: w punkcie będącym aktualnym przybliżeniem rysujemy styczną do wykresu funkcji i kolejnym przybliżeniem jest punkt przecięcia stycznej z osią X.

Zauważmy, że jeżeli naszym przybliżeniem zera jest $x$, to styczna do wykresu funkcji przecina oś X w punkcie $x-\frac{(fx)}{(f^{\prime }x)}$.

Jest to przykład algorytmu polegającego na iteracyjnym przybliżaniu wyniku. Spróbujmy sformułować najpierw ogólny schemat takiego postępowania iteracyjnego:

let rec iteruj poczatek popraw czy_dobre wynik =
  if czy_dobre poczatek then 
    wynik poczatek
  else
    iteruj (popraw poczatek) popraw czy_dobre wynik;;
     

Zastosujmy teraz ten schemat do zaimplementowania metody stycznych Newtona. Zauważmy, że jeżeli naszym przybliżeniem zera jest $x$, to styczna do wykresu funkcji przecina oś X w punkcie $x-\frac{(fx)}{(f^{\prime }x)}$.

let id x = x;;
let newton f x = 
  let p = pochodna f
  in 
    let czy_dobre x = abs (f x) < epsilon
    and popraw x = x -. (f x) /. (p x)
    in
      iteruj x popraw czy_dobre id;;
     

Zwróćmy uwagę na to, że procedura popraw-newton jest lokalna i ma dostęp do funkcji f. Pozostało nam jeszcze napisanie procedury pochodna. Metoda Newtona liczenia pierwiastków kwadratowych to szczególny przypadek metody Newtona znajdowania zer, dla funkcji $f(x)=x^2-a$. Funkcja ta ma zera w punktach $\pm \sqrt{a}$. Ponadto $f^{\prime }(x)=2x$, czyli nasz algorytm przekształca przybliżenie $x$ w

$x-\frac{f(x)}{f^{\prime }(x)}=x-\frac{x^2-a}{2x}=\frac{2x^2-x^2+a}{2x}=\frac{x^2+a}{2x}=\frac{x+\frac{a}{x}}{2}$

Zaczynając w punkcie 1 przybliżamy $\sqrt{a}$.

let sqrt a = 
  let f x = a -. square x
  in newton f 1.;;

Punkty stałe funkcji

Punkt stały funkcji $f$, to taki $x$, że $f(x)=x$. W przypadku niektórych funkcji (i określonych $x$-ów) ciąg $x,f(x),f^2(x),f^3(x),\dots$ jest zbieżny do pewnego punktu stałego $f$. Możemy zaimplementować tę metodę:

let punkt_staly f x = 
  let blisko x = abs (x -. f x) < epsilon
  in
    iteruj x f blisko f;;
     

Przykładową funkcją, której punkt stały można znaleźć tą metodą jest $\cos (x)$.

punkt_staly cos 1.0;;
0.73908\dots      

Proszę to sprawdzić na jakimś nudnym wykładzie --- wystarczy ciągle stukać w klawisz $\cos$.

Obliczanie punktów stałych moglibyśmy zastosować do obliczania pierwiastków --- punkt stały funkcji $y\to \frac{x}{y}$ to $\sqrt{x}$. Jednak obliczenie:

punkt_staly (function y ->  x /. y) 1.0;;
     

nie jest zbieżne: $1\to \frac{x}{1}=x\to \frac{x}{x}=1\to \dots$

W takich przypadkach czasami pomaga "wytłumienie" oscylacji takiego ciągu przez jego uśrednienie.

let usrednienie f = 
  function x -> average x (f x);;
  
let sqrt x = 
  punkt_staly (usrednienie (function y -> x /. y)) 1.0;;
     

W ten sposób uzyskujemy po raz kolejny metodę pierwiastkowania Newtona.

Zastosowania procedur wyższych rzędów

Procedury wyższych rzędów to jeden z tych elementów języka, który jest czysto funkcyjny. W językach imperatywnych procedury mogą być parametrami procedur, lecz nie wynikami. W przypadku języków funkcyjnych mamy pełną swobodę.

Zastosowania procedur wyższych rzędów można podzielić na dwie grupy:

• Pewne pojęcia matematyczne, zwłaszcza te dotyczące funkcji, w naturalny sposób przekładają się na procedury wyższych rzędów, np.: sumy częściowe szeregów, składanie funkcji, różniczkowanie funkcji itp.
• Procedury są jeszcze jednym typem danych. Przyjmując takie podejście, procedury przetwarzające takie dane będą procedurami wyższych rzędów.
• Procedury wyższych rzędów są również narzędziem abstrakcji. Jeżeli ten sam fragment kodu pojawia się w kilku miejscach, to naturalnym jest wyłonienie go w postaci (zwykłej) procedury.
• Jeżeli ten sam schemat kodu pojawia się w wielu miejscach, ale różni się wypełniającymi go fragmentami, to schemat ten możemy ująć w postaci procedury wyższego rzędu, a fragmenty do wypełnienia staną się parametrami proceduralnymi. Przykładem może być tu procedura iteruj.

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu