JavaScript, język znany powszechnie jako wbudowana maszyna skryptowa przeglądarek webowych, jest kompletnie niedoceniany jako język programowania. Tymczasem jest to zgrabny i mały, ale bardzo elastyczny język dynamiczny. Obsługuje funkcje jako obiekty pierwszej klasy, domknięcia (closures) i funkcje anonimowe. To sprawia, że jest pełnoprawnym członkiem rodziny języków funkcyjnych, a ponieważ jego składnia jest prosta i zbliżona do C, posiada wielką siłę wyrazu, niektórzy zgodzą się nawet, że większą niż języki obiektowe oparte na klasach.
Sam język ani standardowa biblioteka nie posiada wielu udogodnień, ale moc wyrazu JavaScript (może należałoby pisać ECMAScript, ale w dalszym ciągu pozwolę sobie konsekwentnie używać tej pierwszej nazwy) jest tak duża, że potrzebne mechanizmy łatwo definiujemy.
Jako pierwszy przykład rozpatrzę iteratory. Chcemy stworzyć obiekt pozwalający na łatwe indeksowanie tablic, a w przyszłości będący wzorem dla ogólniejszych mechanizmów (wykorzystam go poniżek opisując implementację teoriomnogościowych zbiorów). Nasz iterator to funkcja, która po utworzeniu ustawia się na początku sekwencji, każde jej wywołanie generuje kolejny element, a gdy sekwencja się skończy, zwraca obiekt niezdefiniowany:
function iterator( arr ) { var index = 0; return function() { if ( index >= arr.length ) return undefined; return arr[ index++ ]; } }
Funkcja "iterator" jest konstruktorem iteratora, zamyka tablicę "arr" i zmienną "index" w domknięciu i tworzy funkcję używającą tych obiektów. Rezultatem wywołania funkcji "iterator" jest właśnie iterator. Jego pierwsze wywołanie zwraca pierwszy element tablicy, kolejne wywołania zwracają kolejne elementy. Na przykład:
var it = iterator( [1,2,3,4] ); for ( x=it(); x != undefined; x=it() ) { print( x ); }
Taki kod wypisze zawartość tablicy.
Tak skonstruowany iterator jest obiektem-funkcją. Widzimy, że definicja nasza była zwięzła i przejrzysta, dzięki domknięciom i funkcjom pierwszej klasy.
Biblioteki języków obiektowych zawierają definicje różnorakich kolekcji, list, kolejek, wektorów, map itp. Postanowiłem skonstruować na próbę zestaw funkcji i obiektów JavaScript odzwierciedlających podstawowy rachunek aksjomatycznej teorii mnogości. Użytkownicy Javy czy STL z pewnością nie będą pytać o celowość definiowania tak ogólnych mechanizmów.
Nasze zbiory mogą zawierać dowolne elementy (w końcu po to JavaScript jest językiem o słabej typizacji, żeby z tego faktu korzystać). Dla każdego z nich musi istnieć sposób (funkcja? metoda?) na określenie przynależności dowolnego obiektu. Poza tym chcemy mieć możliwość wykonywania takich podstawowych operacji jak dodawanie, selekcja podzbioru (wybór elementów spełniających podany predykat), tworzenie zbioru potęgowego. Siła programowania funkcyjnego polega na tym, że używając kilku prostych pojęć budujemy bardziej złożone, robiąc to prawie tak, jak definiuje się je w matematyce.
Załóżmy na początek, że zbiór jest reprezentowany przez funkcję przynależności. Wywołana z dowolnym argumentem powinna zwrócić wartość logiczną zdania "argument należy do tego zbioru". Używając tej konwencji definiujemy łatwo:
1) zbiór pusty:
function empty() { return false }
2) sumę zbiorów:
function sum( a, b ) { return function( x ) { return a( x ) || b( x ); } }
Tutaj już użyliśmy domknięcia, na razie sprawa jest prosta i piękna.
3) podzbiór elementów spełniających predykat P:
function subset( a, P ) { return function( x ) { return a( x ) && P( x ); } }
Tu widzimy, że reprezentacja zbioru jest tożsama z predykatem, a operacja "subset" z częścią wspólną.
Problem pojawia się w momencie, gdy próbujemy utworzyć zbiór potęgowy. Zbiór potęgowy danego zbioru X jest to zbiór wszystkich podzbiorów zbioru X. Zbiór jest podzbiorem innego, gdy zawiera się w nim. Zatem funkcja przynależności to zawieranie, a zatem:
4) zbiór potęgowy:
function power( a ) { return function ( x ) { return includes( a, x ); } }
Co jednak oznacza stwierdzenie, że zbiór a zawiera zbiór x ? Oznacza to, że ich część wspólna jest równa x !
5) zawieranie:
function includes( a, x ) { return equals( subset( a, x ), x ); }
A co oznacza równość zbiorów ? Aby zdefiniować ten predykat musimy albo posłużyć się zawieraniem, co spowoduje nieskończoną rekursję, albo wyliczyć wszystkie elementy. Rozszerzamy więc reprezentację zbiorów o funkcję zwracającą iterator. Pozwoli to wyliczyć wszystkie elementy i sprawdzić ich przynależność. Nasz zbiór jest więc dwójką składającą się z funkcji "contains" - będącej odpowiednikiem funkcji przynależności - i funkcji "iterator" zwracającej iterator ustawiony na pierwszy element zbioru, gwarantujący jednokrotne wyliczenie każdego elementu.
Teraz zbiór pusty wygląda tak:
1a) Zbiór pusty:
var empty = { contains:function() {return false}, iterator:function() {return function(){return undefined}} }
2a) Suma jest nieco bardziej skomplikowana:
function sum(a, b) { return { contains:function( x ) {return a.contains(x) || b.contains(x)}, iterator:function() { var i1 = a.iterator(); var i2 = b.iterator(); return function() { var x = i1(); if ( x == undefined ) { while (true) { var next = i2(); if ( next == undefined ) return undefined; if ( a.contains(next) ) continue; return next; } } else { return x; } } } } }
Komplikacja bierze się z konieczności zagwarantowania braku powtórzeń w iteratorze. Iterator sumy domyka dwa iteratory składników, wyczerpuje pierwszy, a potem używa drugiego sprawdzając, czy zwrócony element nie był już wyliczony wcześniej.
3a) podzbiór elementów spełniających predykat P:
function subset( a, p ) { return { contains:function ( x ) { return a.contains( x ) && p( x ); }, iterator:function () { var it = a.iterator(); return function() { var x; while ( true ) { x = it(); if ( x == undefined ) return undefined; if ( p( x ) ) return x; } } } }; }
I wreszcie sprawca zamieszania, zbiór potęgowy:
4a) Zbiór potęgowy:
function power( a ) { return { contains:function( x ) { return includes( x, a ); }, iterator:function() { var div = divide( a ); if ( div.head == undefined ) return singleton( empty ).iterator(); var tail_pow = power( div.tail ); var tail_pow_iterator1 = tail_pow.iterator(); var tail_pow_iterator2 = tail_pow.iterator(); return function() { var x; x = tail_pow_iterator1(); if ( x != undefined ) return x; x = tail_pow_iterator2(); if ( x == undefined ) return undefined; return sum( singleton( div.head ), x ); } } } }
Pełne źródła tych procedur można pobrać tu: sets.txt, tam też znajdują się pomocnicze procedury "includes" i "divide". Ta druga posłużyła do wydzielenia jednego elementu i reszty - z dowolnego zbioru. Dzięki temu zbiór potęgowy mógł zostać zdefiniowany rekursywnie.
A teraz proszę popatrzeć, jak to ładnie działa:
Oto wynik działania programu testowego:
Zbior 4 - elementowy:
{1, 2, 3, 4}
Jego zbiór potęgowy:
{{}, {4}, {3}, {3, 4}, {2}, {2, 4}, {2, 3}, {2, 3, 4}, {1}, {1, 4}, {1, 3}, {1, 3, 4}, {1, 2}, {1, 2, 4}, {1, 2, 3}, {1, 2, 3, 4}}
Zbiór podzbiorów właściwych:
{{4}, {3}, {3, 4}, {2}, {2, 4}, {2, 3}, {2, 3, 4}, {1}, {1, 4}, {1, 3}, {1, 3, 4}, {1, 2}, {1, 2, 4}, {1, 2, 3}}
Albo:
{{4}, {3}, {3, 4}, {2}, {2, 4}, {2, 3}, {2, 3, 4}, {1}, {1, 4}, {1, 3}, {1, 3, 4}, {1, 2}, {1, 2, 4}, {1, 2, 3}}
Czy zbiór jest jednoelementowy ?
{} : false
{1} : true
{1, {}} : false
Istnienie elementu o podanej wlasnosci:
{1, 2, 3, 4} , 3: true
{1, 2, 3, 4} , 100: false
Kwantyfikator ogólny:
Czy zbior jest dwuelementowy ?
{} : false
{1} : false
{{}, {1}} : true
{1, 2, 3, 4} : false
Warto zwrócić uwagę na sposób definiowania kwantyfikatorów - funkcje anonimowe (w notacji lambdapodobnej) dają możliwość nazywania zmiennych związanych pod kwantyfikatorem, więc da się tego używać bez wielkiego wysiłku. Porównawszy to z kodem, który trzebaby napisać w C++ używając <functional> widzimy moc wyrazu JavaScript.
I kto dalej twierdzi, że JavaScript to język do robienia animowanych buttonów w internecie ? No kto ?
