Programowanie funkcyjne/Podstawy

Wstęp

W każdym języku programowania mamy trzy rodzaje konstrukcji językowych:

• podstawowe symbole (typy, wartości, operacje, relacje, itp.) --- pochodzące z dziedziny algorytmicznej,
• sposoby konstrukcji --- czyli jak z prostszych całości budować bardziej skomplikowane,
• sposoby abstrakcji --- czyli jak złożone konstrukcje mogą być nazwane i dalej wykorzystywane tak, jak podstawowe elementy.

Nasza dziedzina algorytmiczna zawiera m.in.:

• typy: bool, int, float, char, string,
• stałe: logiczne (true i false), całkowite (np.: 0, 1, -2), rzeczywiste (np.: 2.3, -3.4, 4.5e-7), znakowe (np.: 'a'), napisy (np. "ala ma kota").
• procedury: +, -, *, /, mod, +., -., *., /., ||, &&, not, $=$, $\le$, $\ge$, $<$, $>$, $<>$, ^.

Powtórka: rozróżnienie symboli od ich interpretacji.

BNF

Gramatyka bezkontekstowa jako sposób opisu związku między zapisem, a drzewem rozbioru gramatycznego. Opisując składnię języka będziemy się posługiwać notacją BNF (rozszerzenie gramatyk bezkontekstowych), ale bez przesadnego formalizmu. Opis notacji:

• ,
• $::=$,
• ,
• $\dots |\dots$,
• $[\dots ]$,
• $\{\dots {\}}^{*}$,
• $\{\dots {\}}^{+}$,
• $\{\dots \}$.

Tego formalizmu będziemy używać do opisu składni.

Przyrostowy tryb pracy

Kompilator Ocamla działa w sposób inkrementacyjny, tzn. działa w cyklu powtarzając następujące czynności:

• wczytuje fragment programu,
• kompiluje go, dołączając do już skompilowanych fragmentów,
• wykonuje wprowadzony fragment.

Taki fragment programu będziemy nazywać jednostką kompilacji. Wykonanie jednostki kompilacji może zarówno powodować obliczenia wartości, jak i definiowanie nowych pojęć. Każda jednostka kompilacji musi być w Ocamlu zakończona przez ;;. Ponieważ kompilator nie musi generować całego kodu od razu, dlatego też taki tryb pracy nazywamy przyrostowym.

<program> ::= { <jednostka kompilacji> ;; }*

Wyrażenia

Najprostsza jednostka kompilacji i podstawowa konstrukcja programistyczna, to wyrażenie. Wyrażenia budujemy w standardowy sposób za pomocą stałych, procedur i nawiasów. Jedynym odstępstwem jest to, że argumenty procedur nie muszą być objęte nawiasami i pooddzielane przecinkami. Operacje, które standardowo zapisujemy infiksowo (np. operacje arytmetyczne) mają również postać infiksową. Rozróżniamy operacje arytmetyczne na liczbach całkowitych i rzeczywistych --- te ostatnie mają dodaną kropkę.

486;;
- : int = 486
137 + 349;;
- : int = 486
18 * 27;;
- : int = 486
1000 - 514;;
- : int = 486
1*2*3*4*5*6 - (7*8*9 - 3*12) / (3*4 - 2*5);;
- : int = 486
5832.0 /. 12.0;; 
- : float = 486.
"ala" ^ " ma " ^ "kota";;
- : string = "ala ma kota"
   

Wszystko, czego potrzeba do budowy wyrażeń, to:

• stałe (liczbowe, napisy, lub nazwy stałych),
• zastosowanie procedury do argumentów,
• nawiasów.

Zauważmy, że procedury i ich argumenty są tu traktowane na równi --- takie symbole jak + czy * to po prostu nazwy stałych, których wartościami są procedury wbudowane w język programowania, a 123, 486.5, czy "ala" to stałe.

Składnia wyrażeń

<jednostka kompilacji>    ::= <wyrażenie> | ...
<wyrażenie>               ::= ( <wyrażenie> ) | { <wyrażenie> }+ |
                              <operator unarny> <wyrażenie>  |
                              <wyrażenie> <operator binarny> <wyrażenie> |
                              <identyfikator> | <stała całkowita> |
                              <stała zmiennopozycyjna> | <stała napisowa> | ...
<operator unarny >        ::= - | not | ...
<operator binarny>        ::= + | +. | - | -. | * | *. | / | /. |  
                              mod | || | && | = | < | <= | > | >= | ^ | ...

Zastosowania procedur wiążą najsilniej, operatory unarne słabiej, a operatory binarne najsłabiej, przy czym zachowana jest tradycyjna kolejność wiązania operacji arytmetycznych.

Uwaga

Powyższa gramatyka nie jest jednoznaczna. Nie będziemy aż tak formalni. W rezultacie, nie każde wyrażenie kompilator jest w stanie poprawnie zinterpretować. W razie potrzeby należy dodać nawiasy określające jednoznacznie sposób wyprowadzenia.

Jak poprzednie przykłady wyprowadzają się w powyższej gramatyce?

Obliczanie wartości wyrażeń

Efektem "działania" wyrażenia jest jego wartość. Wyrażenie możemy sobie przedstawić jako drzewo wyprowadzenie - w liściach mamy stałe, a węzły wewnętrzne to procedury. Nawiasy wraz z priorytetami operatorów wyznaczają kształt takiego drzewa. Wszystkie nazwane stałe są przechowywane w tzw. środowisku. Przyporządkowuje ono nazwom ich wartości. Jeśli w wyrażeniu występują nazwy stałych, to ich wartości są pobierane ze środowiska. Wyliczenie wartości wyrażenia możemy sobie wyobrazić jako udekorowanie drzewa wyprowadzenia wartościami, od liści do korzenia. Wartość w korzeniu to wynik. Zilustrować na przykładzie.

Definicje stałych

Kolejną podstawową jednostką kompilacji jest definicja stałej.

<jednostka kompilacji> ::= <definicja> | ...
<definicja>            ::= let <identyfikator> = <wyrażenie> | ...

Definicja stałej nie da się wyrazić jako procedura, ponieważ zmienia środowisko. Dlatego też let jest nazywane formą specjalną. "Obliczenie" definicji wykonywane jest następująco:

• oblicz wartość wyrażenia tworzącego definicję,
• wstaw do środowiska identyfikator i przyporządkuj mu wartość obliczonego wyrażenia.

Jeżeli symbol jest już w środowisku, to można przysłonić go i nadać symbolowi nowe znaczenie.

Uwaga

To jest uproszczony model, który w miarę potrzeb będziemy zmieniać.

Przykład [Przysłanianie symbolu]

let a = 4;;
val a : int = 4
let b = 5 * a;;
val b : int = 20
let pi = 3.14;;
val pi : float = 3.14
pi *. 4.0 *. 4.0;;
val - : float = 50.24
let a = "ala";;
val a : string = "ala"

Możliwe jest też równoczesne definiowanie wielu stałych.

<definicja> ::= let <identyfikator> = <wyrażenie>
                { and <identyfikator> = <wyrażenie> }^*
   

Przykład [Równoczesne definiowanie wielu stałych]

let a = 4 and b = 5;;
val a : int = 4
val b : int = 5
let a = a + b and b = a * b;;
val a : int = 9
val b : int = 20

Definicje procedur

Mamy tylko trzy podstawowe konstrukcje językowe:

• użycie wartości zdefiniowanej w środowisku (nie ważne liczby, czy procedury),
• zastosowanie funkcji do argumentów (np. obliczenie mnożenia),
• definiowanie nowych wartości.

Jak wcześniej wspomnieliśmy, procedury są równie dobrymi wartościami, jak wszystkie inne. Wynika stąd, że:

• można definiować nazwane procedury,
• procedura może być wartością wyrażenia,
• procedury mogą być argumentami i wynikami procedur (o tem potem).

Definicje nazwanych procedur mają następującą postać:

<definicja> ::= let <identyfikator> <identyfikator> + = <wyrażenie>

Pierwszy z identyfikatorów to nazwa definiowanej procedury, a reszta, to jej parametry formalne. Wyrażenie zaś to treść procedury. Przypomnijmy, że argumenty nie są otaczane nawiasami, ani oddzielane przecinkami.

Przykład [Definicje nazwanych procedur]

let square x = x *. x;; 
let pow r = pi *. (square r);;
pow 4.0;;
- : float = 50.24  

let twice x = 2 * x;;
twice (twice 3);;
- : int = 12  

let mocium s = "mocium panie, " ^ s;;
mocium (mocium "me wezwanie");;
- : string = "mocium panie, mocium panie, me wezwanie"

Możemy też tworzyć procedury bez nazwy - $\lambda$-abstrakcja.

<wyrażenie> ::= function <identyfikator> -> <wyrażenie>

Wartością takiego wyrażenia jest jednoargumentowa procedura bez nazwy. Forma specjalna let jest tak naprawdę lukrem syntaktycznympokrywającym wyrażenie function i definicję stałej. Oto alternatywna definicja procedur z poprzedniego przykładu.

Przykład [Alternatywne definicje procedur]

let square = function x -> x *. x;;
let pow = function r -> pi *. (square r);;
let twice = function x -> 2 * x;;

W momencie, gdy zastosujemy procedurę do jej argumentów, jej wartość jest obliczana w następujący sposób:

• obliczana jest procedura, którą należy zastosować i jej argumenty,
• obliczane jest wyrażenie stanowiące treść procedury, w środowisku, w którym była definiowana procedura, rozszerzonym (chwilowo) o przyporządkowanie argumentom formalnym wartości odpowiadających im argumentów,
• wartość tak obliczonego wyrażenia jest wartością zastosowania procedury do argumentów.

Procedury mogą być rekurencyjne.Musimy to jednak jawnie określić dodając słówko rec:

<definicja> ::= let rec <identyfikator><identyfikator> + => <wyrażenie> 

Taka definicja procedury nie jest już lukrem syntaktycznym, gdyż procedury będące wynikiem wyrażeń function nie mogąbyć rekurencyjne. Dodanie słówka rec powoduje, że definiowana procedurajest obecna w środowisku, w którym później będzie obliczana jej treść. Podobnie jak w przypadku definicji innych wartości, możemy równocześnie definiować kilka procedur, używając and.Jest to przydatne, gdy piszemy procedury wzajemnie rekurencyjne.

Uwaga

Procedury nie są funkcjami matematycznymi --- mogą być nieokreślone, np. dzielenie przez 0, lub ich obliczanie może się zapętlać.

Definicje lokalne

Jeśli chcemy zdefiniować jakąś wartość lokalnie, używamy następującej postaci wyrażenia:

<wyrażenie> ::= <definicja> in <wyrażenie>

Zakres definicji jest ograniczony do wyrażenia po in.

Przykład [Definicje lokalne]

let pow x =
  let pi = 3.14
  and s = x *. x
  in pi *. s;;
pow 4.0;;
- : float = 50.24  

let pitagoras x y =
  let square x = x * x
  in
    square x + square y;;
pitagoras 3 4;;    
- : int = 25

Wartości logiczne i wyrażenia warunkowe.

Wartości typu bool to wartości logiczne: true i false. Wyrażenie warunkowe mają postać:

<wyrażenie> ::= if <wyrażenie> then <wyrażenie> else <wyrażenie>

Wartością pierwszego wyrażenia powinna być wartość logiczna, a pozostałe dwa wyrażenia muszą być tego samego (lub uzgadnialnego, ale o tym na razie cicho sza!) typu.

let abs x =
  if x < 0 then -x else x;;          
  
if x = 0.0 then "błąd: x = 0.0" else 1 /. x;;
error ...   

let rec silnia n = 
  if n < 2 then 1 else n * silnia (n - 1);;
silnia 7 / silnia 5;;
- : int = 42   

let rec fib n = 
  if n < 2 then n else fib (n - 1) + fib (n - 2);;
fib 10 - fib 7;;
- : int = 42
       

Obliczanie wyrażenia if jest w pewnym sensie leniwe --- obliczane jest tylko to, co niezbędne. Jeżeli warunek jest prawdziwy, to nie jest obliczany ostatni człon, a jeśli jest fałszywy, to nie jest obliczany drugi człon. If-then-else jest formą specjalną, nie można go zdefiniowaćjako procedury.

Operatory logiczne && i ||, to odpowiedniokoniunkcja i alternatywa. Są to również formy specjalne, a nie procedury. Są one równoważne odpowiednim wyrażeniom warunkowym:

x && y $\equiv$ if x then y else false
x || y $\equiv$ if x then true else y

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu