JavaScript jako język funkcyjny

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 ?

Gdzie czytać o najnowszych osiągnięciach nauki

Gdzieś w początkach swojej przygody z internetem zetknąłem się z programem surfraw, a w przykładowych skryptach z adresem xxx.lanl.gov. Myślałem, że xxx wskazuje na pornografię, ale okazało się, że nie - krzywdziłem autorów. Jest to stary (ale do dziś działający) adres arXiv - wielkiego archiwum preprintów naukowych będącego kopalnią wiedzy o współczesnych naukach ścisłych. Archiwum to jest miejscem gdzie naukowcy z takich dziedzin jak matematyka, fizyka, informatyka, astronomia publikują swoje prace zanim zostaną one wydrukowane na papierze. Niedawno natknąłem się na "The physics arXive blog", którego autor codziennie omawia w sposób dostępny dla zainteresowanych laików jeden wybrany temat z archiwum. Oto zagadnienia, które podejmował ostatnio:

"Pierwszy dowód splątania w fotosyntezie"
"Jak używać pulsarów w nawigacji międzygwiezndej"
"Termodynamiczny limit rozmiaru mózgu"
"Odsłonienie sekretów ludzkiego chodu"
"Gdzie załamuje się zasada równoważności"
...

Wszystkie tematy ciekawie opisane, z kolorowymi ilustracjami i z aktualnymi odnośnikami do oryginalnych prac z arXiv.

Nowy freshmeat

"Świeże mięsko" jeszcze bardziej się odświeżyło - mamy nowy freshmeat 3.0. Nestety niedokończony ... W starej postaci używałem takich funkcji jak wyszukiwanie wg kategorii - teraz nie mam hierarchii kategorii, mam za to modną w Web 2.0 chmurę tagów ... czy to jest lepsze ? Na pewno nie, czekam na resztę.

Miałem też możliwość podglądania statystyk projektu - liczbę odwiedzin, ściągnięć, współczynnik żywotności, to wszystko co pozwala szybko ocenić i wstępnie zakwalifikować nieznany program. Mogłem też sortować wyniki wyszukiwania wg tych czynników - często to robiłem. Zamiast tego jest jakiś mikroskopijny wykres, nie wiadomo czego - stworzony przy użyciu google charts API, skądinąd przyjemnego. Ale statystyki mają wkrótce być - ponoć ulepszone.

Co gorsza, po zalogowaniu się nie potrafię znaleźć statystyk moich projektów - czy one gdzieś są ? W FAQ znalazłem sugestię, że "trzeba było testować wersję beta" - wszyscy testowali i nikt nie zgłaszał takich to a takich potrzeb. Hmmm ... Owszem, dostałem jakieś zaproszenie, ale nie chciało mi się. Mam jednak nadzieję, że używane przeze mnie funkcje będą tu nadal.

Poza tym nie ma nigdzie możliwości sciągnięcia całości bazy danych w formie XML - a była ! Podobno (tak piszą) jest możliwość pobrania rekordu projektu w JSon'ie - ale jak to zrobić ? Tego nie napisali.

Z ostatniej chwili - pojawiło się wiele komentarzy - ludzie pytają o wiele spraw, w tym np o XML - poczekajmy, co się z tym dalej będzie działo ... Jak ktoś tam napisał: "koniec końców - nie jest tak źle" ...

Obrazek "inline" w HTML

Warto czasem pamiętać o różnych dziwnych sztuczkach. Na przykład o wstawianiu grafiki bezpośrednio w tekście HTML. Poniższy obrazek jest tu bezpośrednio wklejony w żródle HTML:

Aby to zrobić, trzeba użyć schematu "data" zdefiniowanego w RFC 2397. Ponieważ schemat ten obsługuje kodowanie base64, można wstawić dowolną grafikę.

Można także wstawić zagnieżdżoną stronę HTML, tym razem już bez kodowania base64, ale Internet Explorer odmówi renderowania elementu "data" z "nawigowalną treścią" - chodzi o względy bezpieczeństwa - filtry zabezpieczające różnorakie aplikacje internetowe przed atakiem typu cross-side scripting prawdopodobnie nie rozpoznałyby javascriptu zagnieżdżonego w elemencie zakodowanym w "data". A jak spreparować taki obrazek ? Po prostu użyć polecenia "base64" dostępnego w uniksie, a także w bibliotekach różnych języków ...

Używając tego mechanizmu Jeff Epler zaimplementował w JavaScript funkcje służące do generowania obrazków w locie po stronie klienta.

Milion dolarów nagrody

Kolejna ciekawa okazja zdobycia dużych pieniędzy w drodze konkursu to Netflix Prize. Tym razem chodzi o sztuczną inteligencję, algorytmy uczące i data-mining. Firma Netflix, największy online'owy serwis z filmami DVD oferuje tak wielką nagrodę za opracowanie algorytmu rozpoznawania upodobań użytkowników, który pobiłby algorytmy dotychczas stosowane w ich serwisie. Suma jest tak duża, a zadanie tak prosto sformułowane, że warto zapoznać się z zasadami tego konkursu.

Wyobraźmy sobie bazę danych obejmującą filmy i preferencje użytkowników. Każdy użytkownik ocenia niektóre filmy w pewnej skali, my dysponujemy ocenami, a naszym zadaniem jest przewidzieć ocenę, której brak w bazie. Jeśli trudno sobie wyobrazić, jak się to robi, wystarczy sobie uświadomić, że istnieją grupy użytkowników o podobnych gustach (np. mężczyźni inaczej oceniają pewne filmy niż kobiety) a także zbiory podobnych filmów (gatunki, rodzaje, filmy danego reżysera). W rzeczywistości efektywne algorytmy tego typu opierają się na badaniu struktury zbioru ocen, a nie na explicite podanych atrybutach, ale w przypadku nagrody Netflix dysponujemy pewnym ograniczonym zbiorem danych dodatkowych (tytuły, daty) i jak najbardziej można z nich korzystać.

Jeśli ktoś zdecyduje się zmierzyć z problemem, powinien pobrać dane testowe z internetu i rozpocząć eksperymenty. Co ciekawe, można zapoznać się z wynikami pośrednimi, ponieważ regulamin konkursu jest tak skonstruowany, że zachęca do ich publikowania (po prostu ufundowano nagrody pośrednie).

konkursy programistyczne

W sieci można wiele konkursów programistycznych, w tym mniej lub bardziej ambitne konkursy matematyczne. Jeden z ciekawszych , to konkurs Ala Zimmermana, który nie tylko funduje kilkusetdolarowe nagrody, ale także zapewnia rozrywkę umysłową i rywalizację na wysokim poziomie. Zadania, które proponuje to różnego rodzaju problemy optymalizacyjne, czy kombinatoryczne, często wymagające napisania sprytnego programu i poświęcenia wiele dni procesora na obliczenia. Uczestnicy wysyłają swoje rozwiązania (wyniki obliczeń, nie programy), a na stronie konkursu można śledzić swoją pozycję w rankingu, W pewnej chwili konkurs dobiega końca i najlepszy zgarnia kasę. Jeśli ktoś interesuje się matematyką, zwłaszcza dziedzinami takimi jak teoria liczb albo matematyka dyskretna, polecam "Project Euler". W tym konkursie nie ma nagrody pieniężnej, ale za to zadania są częściej publikowane i chyba łatwiejsze. Tu po wysłaniu rozwiązania za pomocą formularza (podobnie jak w konkursie Zimmermanna wysyłamy tylko odpowiedź, nie program) od razu uaktualniana jest lista z rankingiem i widzimy, w jakim miejscu peletonu się znajdujemy. W obu tych konkursach nie ma żadnych warunków co do używanych narzędzi, liczy się tylko rozwiązanie problemu.