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 ?

szablony w C++

Mechanizm szablonów w C++ umożliwia deklarowanie klas i funkcji sparametryzowanych typami lub wartościami. Klasa w C++ wprowadza przestrzeń nazw, w której można deklarować obiekty statyczne - daje to możliwość używania szablonów do deklarowania innych obiektów języka, nie tylko klas i funkcji - bezpośrednio nie byłoby to możliwe. Nie można na przykład zdefiniować szablonu tablicy, o tak:

template <class T>
T table[100];

Ale można uzyskać pożądany efekt w taki prosty sposób:

template <class T>
class t {
        public:
        static T table[100];
};

template <class T>
T t<T>::table[ 100 ];

Podobnie można postąpić z innymi kontrukcjami: Np. wyliczenie:

template <int N>
class t {
        public:
                enum en {
                        START=N,
                        STOP
                };
};

Szablonów można użyć do wielu nieoczywistych sztuczek. Oto jak można sprawdzić, czy dwa wyrażenia są tego samego typu:

template <class T>
bool same_type(const T&, const T&) {
        return true;
}

template <class T1, class T2>
bool same_type(const T1&, const T2&) {
        return false;
}

int main()
{
        std::cout << same_type(1, 2) << '\n';
        std::cout << same_type(1, 2.1) << '\n';
}

Kompilator oczywiście całkowicie optymalizuje taką funkcję - zamienia ją na stałą.

Unifikacja termów w C++

Jeden z moich znajomych napisał ostatnio zestaw klas w języku C++, która dzięki zastosowaniu operatora () do konstrukcji termów i operatora == do unifikacji pozwala programować w stylu Prologu w języku C++. Do obejrzenia tu: http://symbolism.110mb.com

Ci, którzy programują w Prologu, wiedzą, co to jest term. Term, to wyrażenie składające się ze stałych, zmiennych i wyrażeń typu f(x1, x2, ... ) gdzie f jest nazwą funktora (symbolem) a x1, x2, ... też są termami. Jeśli oznaczymy zmienne nazwami zaczynającymi się od dużych liter (X, Y, Z itp) a stałe innymi nazwami , liczbami itp, term może wyglądać tak:

f
ala( f, f(X, Y, 10), X)
ala( 0 )

i tak dalej. W skrócie mówiąc - unifikacja termów, to takie dopasowanie wartości zmiennych (wartości zmiennych też mają być termami) aby dwa unifikowane termy uzyskały tę samą wartość. Unifikacja może się nie udać, zmienne nie są wtedy zmieniane (mówi się też - ukonkretnione) Jeśli oznaczymy symbolem == operację unifikacji, możemy napisać:

f( X, 1 ) == f( 2, Y )                   
-> zmienna X zyskuje wartość 2, Y wartość 1

f( X, g( Y, 0 ), Y ) == f( 1, Z, g( 2 )) 
-> zmienna X zyskuje wartość 1, Y wartość g(2) a Z wartość g(g(2), 0)

f( X, g( 1 )) == f( 0, 2 )   -> unifikacja zawodzi, zmienne pozostają wolne.

Spread, lewar i pipsy na rynku Forex

Wszyscy co prawda wiedzą, co oznaczają pipsy, lewar i tym podobne pojęcia, ale może nie wszyscy potrafią wyciągać odpowiednie wnioski z tej wiedzy. Tymczasem na wyniki strategii stosowanej na rynku forex wpływa równocześnie wiele czynników: rozmiar pozycji (pipsy), stosowany lewar, skuteczność (prawdopodobieństwo) i oczywiście spread (koszty stałe transakcji).

Ponieważ jest to wpływ równoczesny, sytuacja jest złożona, mimo, że w istocie chodzi tu o matematykę na szkolnym poziomie.

Musisz koniecznie wiedzieć, co dokładnie dzieje się gdy wykonujesz traksakcję o danych parametrach. Wyobraź sobie, że dysponujesz kwotą 100 $, wchodzisz na rynek z lewarem 10, przy spreadzie 4 pipsy (umawiamy się dla celów tych rozważań, że 10 pipsów = 1 promil) ustawiasz poziom 'take profit' na wysokości 30 pipsów i po kilku godzinach zgarniasz kasę. Pytanie - ile ? Jeśli to rozumiesz i umiesz wyliczyć, to dobrze, ale spójrz niżej, zobacz, czy czegoś nie pomijasz.

Przy lewarze 10 handlujesz w rzeczywistości 1000 $, przy spreadzie 0.0004 i TP=0.003 zarabiasz 0.0026 * 1000 = 2.60 $, co daje czynnik 0.026 profitu. W razie straty przy SL=-0.003 tracisz 0.0034 * 1000 = 3.40 $ ponieważ spread działa zawsze na niekorzyść gracza. Dlatego zysk i strata nie są symetryczne, mimo, że ustawiliśmy poziomy TP i SL w równych odległościach.

Wyobraźmy sobie hipotetyczną metodologię, która dla danej pary umożliwia prognozowanie ruchy kursu o 50 pipsów. Jej skuteczność niech wynosi 70 %. Oto jak wygląda wartość porfela gracza, który wykonuje 20 transakcji stosując opartą o taką prognozę strategię przy spreadzie 4 pipsy, trafiając "take profit" 14 razy: W zależności od zastosowanego lewara gracz zarabia aż do 170 %, ale widać jasno, że LEWARA NIE MOŻNA BEZKARNIE ZWIĘKSZAĆ w nieskończoność: w pewnym momencie następuje nasycenie profitu ! Dla lewara 120 obserwujemy już stratę. Lewar wpływa bardziej na wahania, a mniej na wynik końcowy.

Odpowiedzialność za taki fatalny stan rzeczy ponosi spread (czyli broker, który zgarnia całą kasę zachłannego gracza, podobnie jak krupier w kasynie). Oto jak wygląda zależność zarobku w naszej hipotetycznej sytuacji od zastosowanego lewara przy różnych spreadach: Słabsze strategie są jeszcze bardziej podatne na te efekty i wręcz nie działają na dużych spreadach, mimo, że nie stosujemy lewara.

Co jeszcze warto wiedzieć ?

Występujące w przyrodzie spready nieprzypadkowo mają taką wielkość, że działające strategie musiałyby mieć dzielność rzędu 65% lub większą - dla wielkości pozycji przekraczającej około dziesięciokrotnie wartość spreadu. To jest maksymalny poziom trafności, jaki można osiągnąć stosując znane metody (włączając w to sieci neuronowe, algorytmy genetyczne, filtry bayesowskie i inne metody - określane jako standardowe, choć nie są one proste).

Istnieje jeszcze jedna pułapka na chciwych graczy: "margin call". O tym też trzeba pamiętać. Można po prostu stracić wszystko za jednym zamachem, jeśli przedobrzymy z lewarem.

Tak więc rację ma Oanda, twierdząc, że dla tradera to właśnie niskie spready są istotne, a nie duże lewary. W warunkach bojowych lewar większy od 10 to lichwiarska pułapka ! Na stronach Oandy dokładnie opisane są te sprawy, ten broker stara się uczciwie informować o podstawowych regułach gry.

Paradoks skuteczności lekarstw

W jednym ze starych numerów Delty opisany był następujący paradoks:

Zbadano skuteczność dwóch lekarstw A i B. Okazało się, że wśród kobiet wyższą skuteczność miało A, natomiast w całej populacji wygrywało B. Nie byłoby to dziwne, gdyby nie fakt, że wśród mężczyzn również lepszym było lekarstwo A. Jak to możliwe ? Otóż badanie przeprowadzono w następujący sposób - zgłaszającemu się pacjentowi aplikowano losowo A lub B, po czym notowano wynik terapii.

Wyniki badania były następujące:

Badano 32 mężczyzn, 25 mężczyznom podano lek A, z czego 10 wyleczono. 7 mężczyzn leczono lekiem B, z czego 2 wyleczono. Skuteczność leków wynosiła więc wśród mężczyzn 40% dla A i 29% dla B.

Zbadano 25 kobiet, na 11 leczonych lekiem A wyleczono 9, pozostałe 14 leczono podając lek B, wyleczono 11. Skuteczność leku dla kobiet wyniosła więc 82% dla A i 79% dla B. Widać, że kobiety łatwiej się leczyło, ale wśród pacjentów obu płci lepszy był lek A.

Tymczasem po zsumowaniu liczb widzimy, że skuteczność A w całej grupie wynosi 53%, a B 62% ! Co ma więc zrobić lekarz, do którego przychodzi pacjent ? Zbadać jego płeć i przepisać A niezależnie od wyniku tego badania, czy nie badać i przepisać B ?

Istnieje wiele układów liczb tworzących taką sytuację. Podobne zadanie (tylko z innymi "didaskaliami") pojawiło się w konkursie Eulera, o którym już wcześniej tu pisałem.

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