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:

• <konstrukcja>,
• $::=$,
• słowo kluczowe,
• $\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ń

Parser nie mógł rozpoznać (nieznana funkcja „\begin{matrix}”): {\displaystyle \begin{matrix} \mbox{<jednostka kompilacji>} ::= & \mbox{<wyrażenie>} | \dots\\ \mbox{<wyrażenie>} :== & \kwd{(} \bnf{wyrażenie} \kwd{)} | \{ \bnf{wyrażenie} \}^+ |\&nbsp;&&\bnf{operator unarny} \bnf{wyrażenie} |\&nbsp;&&\bnf{wyrażenie} \bnf{operator binarny} \bnf{wyrażenie} |\&nbsp;&&\bnf{identyfikator} | \bnf{stała całkowita} |\&nbsp;&&\bnf{stała zmiennopozycyjna} | \bnf{stała napisowa} | \dots\\ \bnf{operator unarny} \prod \kwd{-} | \kwd{not} | \dots\\ \bnf{operator binarny} \prod \kwd{+} | \kwd{+.} | \kwd{-} | \kwd{-.} | \kwd{*} | \kwd{*.} | \kwd{/} | \kwd{/.} | \kwd{mod} | \kwd{||} | \kwd{&&} |\&nbsp;&&\kwd{=} | \kwd{<} | \kwd{<=} | \kwd{>} | \kwd{>=} | \kwd{^} | \dots \end{bnfdef}% 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? }