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ń

XXX
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.