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:

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:

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ć: \begin{bnfdef} <definicja> ::=let} \bnf{identyfikator} <identyfikator^+ \kwd{=><wyrażenie> \end{bnfdef}% 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.

\paragraph{Przykład:} \begin{code} 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" \end{code}

Możemy też tworzyć procedury bez nazwy --- $\lambda$-abstrakcja. \begin{bnfdef} <wyrażenie> ::=\kwd{function} \bnf{identyfikator} -> <wyrażenie>\end{bnfdef}% 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: \begin{code} let square = function x -> x *. x;; let pow = function r -> pi *. (square r);; let twice = function x -> 2 * x;; \end{code}

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:\begin{bnfdef} <definicja> ::=\kwd{let} rec <identyfikator><identyfikator}^+ \kwd{=><wyrażenie> \end{bnfdef}% 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ć.

Laboratoria i ćwiczenia

Laboratoria i ćwiczenia do wykładu