improwizacje metatematyczne

JavaScript jako język funkcyjny

2009-11-04T11:53:00.000-08:00

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++

2009-09-07T04:25:00.000-07:00

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++

2009-07-24T07:32:00.000-07:00

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

2009-06-06T18:00:00.000-07:00

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

2009-05-28T12:04:00.000-07:00

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

2009-05-28T04:21:00.000-07:00

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

2009-03-17T09:55:00.000-07:00

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

2009-03-06T11:52:00.000-08:00

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.

Durczok, Lis, Kaczyński, Niesiołowski i nasze emocje

2009-02-17T07:41:00.000-08:00

Pan Kamil Durczok stał się dla nas źródłem wesołości, pozwalając się sfilmować przy pracy. Nie przebił moim zdaniem Tomasza Lisa, który uraczył nas jakiś czas temu jeszcze dłuższym potokiem błota wylewanego na współpracowników. Nie dziwi mnie to ani nie gorszy, wolę co prawda ludzi kulturalnych, ale pogodziłem się z tym, że takich jest mało na świeczniku. Ale przecież pan Kamil uważa się za kogoś wyrastającego ponad poziom przeciętny, nie chciał stawać w szranki o nagrodę medialną razem z Kasią Cichopek - kimże ona jest przy nim ! Bez urazy ...

Wczoraj mogliśmy obejrzeć Tomasza Lisa w rozmowie na temat pana Czumy, a potem na innym kanale telewizyjnym pana Pospieszalskiego w dyskusji o eutanazji. I tu i tam widziałem gotujące się emocje (pogardę i wściekłość u Niesiołowskiego, gniew u Kaczyńskiego, pogardę i wściekłość u pana profesora bioetyka, którego nazwiska nie zapamiętałem - przepraszam). W ogóle wszędzie pełno obrażania, dokuczliwych złośliwości i jadu. Lis stale wyciąga jakieś stare nagrania z Kaczyńskim, aby ludziom pokazać, jak agresywne są Kaczory. Nie udała mu się jednak prowokacja, kiedy gościł Kaczyńskiego u siebie - chociaż zaprezentował mu filmik z Marcinkiewiczem, nie usłyszał nic poza zapewnieniami o dobrej woli. Prezes Kaczyński zmienił front i hamuje agresję, choć pewnie mu ciężko. Za to tydzień później, Lis razem z nowym gościem wspólnie szydzili z nieobecnego prezesa bez umiaru. Uśmiechali się pogardliwie pod nosem wymieniając porozumiewawcze spojrzenia wspominając jego wpadki i litując nad jego poziomem.

U Pospieszalskiego goście byli spokojni i opanowani, oprócz pana Profesora, którego nazwiska nie pamiętam - wojującego ateisty, który bardzo się sam zdenerwował z tego powodu, że połowa ludzkości wierzy w duszę. Odniosłem wrażenie, że złościł się po prostu dlatego, że nie okazano mu należnego respektu - pani redaktor, z którą rozmawiał, ośmieliła się go krytykować. Upomniał ją, że winna mu szacunek, jako, że jest PROFESOREM. Pani redaktor też była mocno zdenerwowana.

Wszystko to nastraja mnie dość smutno - światem nie rządzi wcale rozum, wbrew temu, co się nam wmawia. Rządzą nimi EMOCJE wywoływane przez media - czytaj - MANIPULACJA. Na szczęście chyba nie zawsze skuteczna - drugie na szczęście - zdecentralizowana ... Kto wywoła odpowiednie emocje w odpowiednim kontekscie, przeciąga wyborcę (czytelnika? konsumenta?) na swoją stronę. Ludzie tacy jak Lis próbują to robić zawodowo, politycy - też, ale mam nadzieję, że przynajmniej ci, którym wierzę, robią to dla słusznych celów.

Skrzynka z narzędziami

2009-02-16T12:06:00.000-08:00

Podczas pracy z plikami tekstowymi często powstaje potrzeba przeprowadzenia prostej operacji w rodzaju sortowania, zmiany kolejności, sumowania itp. Zwykle odruchem jest pisanie jednolinijkowca w AWK-u albo innym ulubionym języku. Niesłusznie. Czasem lepiej jest otworzyć skrzynkę z narzędziami i poszukać gotowca. W Unix-ie mamy mnóstwo małych gotowych programów. Zdarzyło mi się napisać program, który robił to, co shuf i inny, który wykonywał operację paste. Niepotrzebnie. Poniżej wymieniam kilka z tych narzędzi.

csplit:podział pliku na podstawie zawartości
cut:wybranie kolumn
join:połączenie plików wg wspólnej kolumny
paste:sklejenie plików kolumnami
shuf:mieszanie kolejności linii w pliku
split:podział pliku na równe kawałki
tac:wypisanie pliku liniami od tyłu
tr:zamiana znaków
uniq:wybranie linii powtarzających się

Warto zapoznać się z nimi - mają bogaty repertuar różnych opcji - na przykład program split może zliczać linie, albo znaki. Program paste może skleić pliki pionowo lub poziomo. Program shuf może mieszać linie, ale może też potasować swoje argumenty. I tak dalej. Skrzynka narzędziowa jest pełna !

Jednolinijkowce w AWK-u

2009-02-16T11:39:00.000-08:00

AWK jest językiem programowania nadającym się wybitnie do tworzenia jednolinijkowców. "Jednolinijkowiec" to skrypt napisany ad-hoc, bez edytora, od razu w linii komend. Często mieści się w jednej linii - stąd nazwa.

Pracując nad analizą techniczną kursów walut używam często awk-a i bash-a jako narzędzi szybkiego prototypowania i błyskawicznych kalkulacji.

Przykład: w pliku A.txt mam dane w postaci tekstowej, każda linijka zawiera jedną liczbę - wartość kursu w danym punkcie. Chcę obliczyć średnią wykładniczą z dziesięciu okresów.

Za pomocą jednolinijkowca w AWK-u robię to tak:

awk '{s=0.1*$1+0.9*s; print s}' A.txt

Po przeczytaniu tego artykułu też będziesz to umieć.

Przykład innego typu: Chcę z pliku B.txt wybrać co dziesiątą linię:

awk '{n++; if(n>=10) {print; n=0}}' B.txt

Przykład trzeci - powiedzmy, że w pliku C.txt mam dwie kolumny z wartościami liczbowymi. Chcę obliczyć średnią wartość liczb w obu kolumnach. Posługuję się więc jednolinijkowcem, który tworzę w locie:

awk '{p+=$1; x+=$2; n++} END {print p/n, x/n}' C.txt

I tak dalej, wszysto szybko, łatwo i bezbłędnie.

AWK jest genialnie dostosowany do takich celów - ma kilka konstrukcji składniowych, kilka funkcji i kilka reguł, które trzeba poznać, podręcznik mieści się w jednym manualu systemowym, a możliwości są ogromne. Nie ma obiektów, klas, wyjątków ani modułów, ale robi to, co potrzebne. Aby sobie to uzmysłowić, wystarczy zrozumieć, jak działa AWK.

DZIAŁANIE AWK-a

Program w AWK-u to lista reguł. Każda reguła to wzorzec i akcja. Program czyta dane rekord po rekordzie, znajduje pierwszy wzorzec, który może być dopasowany do rekordu i wykonuje skojarzoną z nim akcję. Rekord dzieli się na pola, oznaczane w akcjach i wzorcach symbolami $1, $2, $3 itd.

Przykład:

awk '$1>1 {n++} END {print n}'

awk - to komenda - nazwa programu awk '$1>1 {n++} END {print n}' - to program w AWK-u, składa się z dwóch reguł: $1>1 {n++} - wzorzec $1>1 oznacza rekordy, w których wartość numeryczna pierwszego pola jest większa niż 1, akcja {n++} oznacza inkrementację zmiennej n END {print n} - wzorzec END to sztuczny wzorzec, nie dopasowywany do żadnego rekordu, skojarzona z nim akcja wykonywana jest na zakończenie programu. W tym wypadku wypisuje liczbę n.

Powyższy program liczy linie, w których pierwsza kolumna zawiera liczbę większą od 1, a następnie wypisuje wynik.

Akcje ujęte są w nawiasy {}, warunki to wyrażenia relacyjne lub specjalne symbole BEGIN lub END.

Inny przykład - pomnożenie wszystkich liczb zawartych w pliku:

awk 'BEGIN {x=1} {x*=$1} END {print x}'

Aby zmusić program do zainicjowania zmiennej jedynką został tu użyty wzorzec BEGIN. Tyle informacji wystarczy, aby rozpocząć eksperymentowanie.

Sztuka bezkontekstowa i sztuka algorytmiczna

2009-01-25T05:32:00.000-08:00

Natknąłem się przypadkowo na interesujący program graficzny - Context Free - narzędzie służące do tworzenia algorytmicznej grafiki.

Używa się go w niestandardowy sposób, mianowicie nie rysuje się nic na ekranie, ani na kartce - zamiast tego zadaniem artysty jest stworzenie opisu grafiki w specjalnym języku programowania. Pomysł ten jest krewniakiem idei muzyki algorytmicznej, o której pisałem przy okazji omawiania csound'a . Przypomniałem sobie o swoich starych eksperymentach z tworzeniem algorytmicznej grafiki bezpośrednio w języku C: oto wizerunek "tęczowej planety" i fragment kodu programu, który go narysował. Dość złożony obraz powstaje w wyniku działania tak prostej funkcji !

#define tfi(x) (0.5*(x+1))

float calc_color( float x, float y, int rgb )
{
        float d, K;

        d = (x-0.4) * (y-0.3) - 0.04;

        if ( d < 0 ) 
                K = 0;
        else if ( d < 0.03 ) {
                K = 1 - (0.03 - d)/0.03;
        }
        else
                K = 1;

        switch ( rgb ) {
                case 0:
                        return K * tfi(sin( 41 * x*y ));
                case 1:
                        return K * tfi(cos( 13 * x ));
                default:
                        return K * tfi(cos( 28 * y ));
        }
}

Więc czy da się przewidywać kursy walut na forexie ?

2009-01-12T10:43:00.000-08:00

Dane historyczne są dostępne w sieci, wyposażmy się więc w jakieś narzędzie (dla mnie najwygodniejszy jest bash i awk, ale równie dobrze może być to Excel) i popróbujmy prostych eksperymentów. Badając dane pary EURCHF z ostatnich kilku lat (moje dane były pobrane z rosyjskiego portalu forexite, próbkowane z rozdzielczością minutową) widzimy, że każdy ruch w jedną stronę poprzedza ruch w przeciwną stronę - ta obserwacja jest słuszna z dość dużym prawdopodobieństwem ! Prawdopodobieństwo to wynosi około 62 % dla danych minutowych. Dla danych próbkowanych 2 razy rzadziej analogiczna wielkość to 59 % Ogólnie rzecz biorąc, im dłuższe okresy badamy, tym ta korelacja (albo ściślej rzecz ujmując - antykorelacja) jest słabsza. Przybliżone wielkości prawdopodobieństwa "odbicia" dla pary EURCHF w zależności od długości ruchu przedstawia zestawienie:

 1    0.622234
 2    0.595226
 5    0.570834
10    0.557971
20    0.543762
60    0.538403

Widzimy, że dla długich okresów badana wielkość upodabnia się do danych losowych, dla których oczywiście prawdopodobieństwo to wynosi 50 %. Podobieństwo dotyczy oczywiście tylko tego jednego aspektu, należy pamiętać, że nasz eksperyment jest zbyt prosty, żeby w ogólności rozstrzygnąć o charakterze badanego procesu. Czy można jednak jakoś wykorzystać te zależności ? Okazuje się, że nie, że to za mało. Średnia względna wielkość ruchu ceny w zależności od wielkości kroku w badanych okresach wygląda tak:

 1      0.000158347
 2      0.000164155
 5      0.00024643
10      0.000328186
20      0.000444261
60      0.000738944

Zakładając, że broker zabiera nam 1 pips prowizji w postaci spread'u, co stanowi około 0.000066 wartości pozycji, mamy następujący średni profit na tak zaprognozowanej transakcji:

 1     -2.72892e-05
 2     -3.47364e-05
 5     -3.10888e-05
10     -2.79495e-05
20     -2.71165e-05
60     -9.24467e-06

Profit jest ujemny dla każdego z badanych przedziałów, co więcej, widać, że w zakresie małych ruchów jest prawie stały, spread równoważy prawie zysk związany z przewidywalnością ruchu, a więc można uznać, że jest to przewidywalność NIEZNACZĄCA, niwelowana przez prowizje. Nie powinniśmy jednak się poddawać ! Wykryty przez nas autentyczny fakt, polegający na MOŻLIWOŚCI przewidywania ruchów cen, którą można EKSPERYMENTALNIE UDOWODNIĆ powinien nas zachęcić do dalszych samodzielnych badań. W kolejnych odcinkach postaram się opisać, do czego ja doszedłem, w jaki sposób, a także jak używałem awk'a i jednolinijkowców do super ekstremalnie szybkiego programowania i obliczania różnych statystyk i prawdopodobieństw.

Handel walutami - czy trendy istnieją

2009-01-02T11:03:00.000-08:00

Od paru lat, na skutek upowszechnienia internetowych platform transakcyjnych, handel walutami na rynku międzynarodowym dostępny jest dla każdego, kto jest podłączony do sieci. FOREX zyskuje coraz większą popularność w kręgach domorosłych spekulantów ze względu na niskie koszty transakcji (rzędu 0.01 % !) i dostępne wysokie lewary (nawet do 200 x ). Każdy, kto chce rozpocząć przygodę z forexem powinien jednak najpierw zapoznać się ze specyfiką tego rynku, w przeciwnym razie szybko straci wszystkie zainwestowane środki. W tym artykule chcę pokazać, jak złudne są nasze przekonania co do natury kursów walut. Obalę mit o wyraźnych trendach , które rzekomo widoczne są gołym okiem na wykresach kursów. Poniżej przedstawiam wykres notowania pary EUR/USD na przestrzeni kilku lat: Końcowe załamanie to objaw obecnego kryzysu funansowego, który przerwał wyraźny trend rosnący Euro w stosunku do dolara amerykańskiego. Każdy widzi ten trend, a ja teraz pokażę, że to złudzenie. W tym celu wygeneruję sztuczne dane i pokażę ich wykresy. Poniżej przedstawiam pięć zestawów danych całkowicie losowych. Program generujący startuje z jedynki i losowo mnoży ją lub dzieli przez tę samą wartość (krok) równą 1.001. Skrypt, który wygenerował te dane wygląda tak:

awk 'BEGIN { x=1; p=1.001; 
     for (i=0; i<27783; i++) { 
        if (rand() < 0.5) x *= p; else x /= p; print x }
     }'

27783 to liczba punktów pierwotnego wykresu - chcę uzyskać dane tej samej długości. Oto, co uzyskuję: Wygenerowany wykres również zawiera wyraźny trend . Jedyne wyjaśnienie tego faktu to przypadek, albo złudzenie. Wygenerujmy więc kolejne cztery przebiegi czasowe i obejrzyjmy: Oprócz być może pierwszego z powyższych czterech sztucznie wygenerowanych wykresów, wszystkie posiadają odcniki wyraźnego trendu . Tłumaczy się to tym, że umysł ludzki cechuje skłonność do dopatrywania się porządku nawet tam, gdzie go wcale nie ma. Czy więc dane finansowe , takie jak notowania FOREXU czy giełdy, są nieprzewidywalnymi ciągami losowymi ? Czy więc cała analiza techniczna jest równoważna próbom znalezienia systemu wygrywania w totolotka ? Nawiasem mówiąc są tacy, którzy wierzą w systemy totolotka i nawet tacy, którzy je sprzedają ! W środowiskach akademickich do niedawna panowało przekonanie o efektywności rynków i co za tym idzie o niemożliwości przewidywania kursów. Od ostatnich kilku (czy też kilkunastu) lat pojawiają się jednak prace (znajdziemy je względnie łatwo używając http://scholar.google.com ) dostarczające solidnych argumentów zwolennikom analizy technicznej. Jedno jest pewne : dzisiejszy trader nie obejdzie się bez komputera, podstawowej umiejętności programowania i podstawowej znajomości statystyki matematycznej. O swoich dokonaniach na polu handlu FOREXOWEGO - o próbach znalezienia solidnych teoretycznych podstaw do praktycznego zarabiania pieniędzy - postaram się napisać w kolejnych postach.

Post Scriptum i PostScript

2008-10-01T11:44:00.000-07:00

Mój dobry znajomy opublikował niedawno nowe narzędzie do generowania PostScriptu. Jest to proceduralny język programowania o składni zbliżonej do C, tłumaczony bezpośrednio na PostScript - nazywa się Post Scriptum. Angielskie słowo "postscript" znaczy to samo, co łacińskie (czy też międzynarodowe) - "post scriptum". Aby zrozumieć możliwe zastosowania Post Scriptum, należy po pierwsze wiedzieć jak działa i czym jest PostScript. Potocznie traktowany jako format plików graficznych, w rzeczywistości PostScript jest językiem programowania wysokiego poziomu, stworzonym jako język opisu strony (page description language), ale będącym pełnym językiem programowania. PostScript jest idealny do generowania maszynowego, niezbyt jednak nadaje się do użycia ręcznego. Problemem jest przede wszystkim składnia języka, oparta na odwrotnej notacji polskiej (Reverse Polish notation) pozbawiona nawiasów. Predestynuje ona PostScript do generowania automatycznego, ale praktycznie uniemożliwia żywemu programiście szybkie czytanie złożonego kodu. Oto przykład: Wyrażenie w Post Scriptum, zrozumiałe dla każdego programisty:

if (x[1] > 2*y) 
    x[1]=y-1; 
else 
    x[1] += 1;

zapisane w PostScripcie wygląda na przykład tak:

x 1 get 2 y mul gt{
   x 1 y 1 sub put
}
{
   x 1 x 1 get 1 add put
} ifelse

Na tym poziomie da się to jeszcze czytać przy odrobinie wprawy, ale już widzimy różnicę - musimy się trochę skupić. W bardziej złożonych programach wyszukanie błędu jest mozolne i naprawdę można tego uniknąć używając Post Scriptum. Taka beznawiasowa składnia nazywana jest postfiksową - tak nazywa się zapis, w którym argumenty stoją przed operatorami - stąd chyba zresztą wzięła się nazwa PostScriptu. Autor Post Scriptum celnie zauważył, że składnia ta jest jedynym elementem języka, który powstrzymuje programistów od masowego bezpośredniego używania PostScriptu. Pozostałe elementy języka, takie jak zarządzanie pamięcią, system typów, czy wreszczie rozbudowany system graficzny, stanowiący clue PostScriptu, są wygodne, przemyślane i dopracowane - można powiedzieć, że aż chciałoby się ich używać, gdyby nie ten język ... Wniosek był jeden: trzeba stworzyć język, który będzie miał klasyczną składnię, a tłumaczony będzie na PostScript. Tak powstało Post Scriptum. Podobnie powstał język C - w wyniku znużenia zawiłościami kodu assemblerowego. Ale można w C zakodować prawie wszystko to, co w asemblerze. Podobnie w naszym nowym języku - program w Post Scriptum może być funkcjonalnie równoważny dowolnemu programowi w PostScripcie. Nowy język posiada klasyczne konstrukcje sterujące: pętle, instrukcje "if", funkcje. Obsługuje typy danych PostScriptu: słowniki (odpowiedniki paskalowych rekordów, struktur C, czy PHP-owych hashów), stringi i oczywiście liczby stało- i zmiennoprzecinkowe. Operatory PostScriptu udokumentowane bardzo dokładnie w "PostScript Language Reference Manual" firmy Adobe) są wywoływane bezpośrednio jak każda inna funkcja, dzięki czemu Post Scriptum daje dostęp do całej graficznej maszynerii PostScriptu. Możliwe jest też włączanie kodu napisanego w PostScripcie bezpośrednio do programu w Post Scriptum. Na etapie kompilacji można dołączać fragmenty kodu (klasyczna dyrektywa "include") jak i gotowe fragmenty PostScriptu (dyrektywa "import"). Autor poprzedził pracę nad tym językiem poszukiwaniami gotowego rozwiązania tego typu i - o dziwo - nie znalazł. W dalszych planach, o ile mi wiadomo, jest wsparcie dla kontroli typów (obecnie język jest polimorficzny, jak PostScript), kontrola prototypów funkcji i inne feature'y wspierające szybkie tworzenie i debugowanie kodu. Życzę autorowi dalszego zapału i zachęcam wszystkich do odwiedzenia strony "Post Scriptum".

Najprostsze pliki graficzne

2008-06-19T01:25:00.001-07:00

Trzy formaty plików graficznych: PPM, PGM i PBM (portable pixmap, portable graymap, portable bitmap) wspólnie określane popularnie jako "portable anymap" stanowią w zamyśle autorów "wspólny mianownik" formatów graficznych, format prosty i oczywisty, pozwalający na wymianę danych graficznych pomiędzy systemami i programami. Format zdefiniowany w latach 80-tych i używany do dziś.

Wszystkie trzy oparte są na wspólnej zasadzie: plik zawiera nagłówek z koniecznymi danymi (rozmar, typ) i prostokątną macierz pixeli. Pixel określa kolor w postaci składowych RGB (dla pixmap PPM), stopień szarości (dla greymap) lub jednobitową wartość biało-czarną (dla bitmap). Format zdefiniowano w wariancie binarnym i tekstowym. W przyrodzie występują z rozszerzeniem .ppm, .pbm i .pgm, ale także .pnm (Portable aNyMap).

Dalszym rozwinięciem tego formatu jest PAM, występujący tylko w formie binarnej, pozwalający na dalsze rozszerzenia, kanał alfa itp.

W Twoim Unixie znajdziesz mnóstwo programów - narzędzi zawierających w nazwie ciąg znaków ppm, pnm, pgm itp. Oto rezultat komendy "apropos pnm" na komputerze, na którym piszę ten artykuł (pierwszy fragment) :

anytopnm (1)         - attempt to convert an unknown type of image file to a portable anymap
bmptopnm (1)         - convert a BMP file into a portable anymap
calibrate_ppa (8)    - pnm2ppa calibration tool
fiascotopnm (1)      - Convert compressed FIASCO image to PGM, or PPM
fitstopnm (1)        - convert a FITS file into a portable anymap
gemtopnm (1)         - convert a GEM .img file into a portable anymap
giftopnm (1)         - convert a GIF file into a portable anymap
jpegtopnm (1)        - convert JPEG/JFIF file to portable pixmap or graymap
palmtopnm (1)        - convert a Palm pixmap into a portable anymap
pamdeinterlace (1)   - remove ever other row from a PAM/PNM image
pamfile (1)          - describe a Netpbm (PAM or PNM) file
pamstretch (1)       - scale up a PNM or PAM image by interpolating
between pixels
pamstretch-gen (1)   - use pamstretch and pnmscale to scale by non-integer values
pngtopnm (1)         - convert a Portable Network Graphics file into portable anymap
pnm2ppa (1)          - convert portable anymap (PNM) images to HP's
PPA printer format.
pnmalias (1)         - antialias a portable anyumap.
pnmarith (1)         - perform arithmetic on two portable anymaps
pnmcat (1)           - concatenate portable anymaps
pnmcolormap (1)      - create quantization color map for a portable anymap
pnmcomp (1)          - composite (overlay) two portable anymap files together
pnmconvol (1)        - general MxN convolution on a portable anymap
pnmcrop (1)          - crop a portable anymap
pnmcut (1)           - cut a rectangle out of a portable anymap
pnmdepth (1)         - change the maxval in a portable anymap
pnmenlarge (1)       - read a portable anymap and enlarge it N times
pnmfile (1)          - describe a portable anymap
pnmflip (1)          - perform one or more flip operations on a portable anymap
pnmgamma (1)         - perform gamma correction on a portable anymap
pnmhisteq (1)        - histogram equalise a portable anymap
pnmhistmap (1)       - draw a histogram for a PGM or PPM file
pnmindex (1)         - build a visual index of a bunch of anymaps
pnminterp (1)        - scale up a PNM or PAM image by interpolating between pixels
pnminterp-gen (1)    - use pamstretch and pnmscale to scale by non-integer values
pnminvert (1)        - invert a portable anymap
pnmmargin (1)        - add a border to a portable anymap
pnmmontage (1)       - create a montage of portable anymaps
pnmnlfilt (1)        - non-linear filters: smooth, alpha trim mean, optimal estimation smoothing, edge enhancement.

.......

Biorąc pod uwagę, że każdy taki plik można zamienić na postać tekstową, którą łatwo przetwarzać przy użyciu narzędzi typu awk/perl/bash/sed, mamy w ręce pełną bibliotekę graficzną ...

Nagroda Wolframa przyznana pół roku temu

2008-06-17T07:44:00.001-07:00

Wszedłem niedawno przypadkowo na strony Wolframa - nagroda Wolframa, 25000 dolarów, została przyznana w zeszłym roku: Maszyna jest uniwersalna ! Młody anglik rozwikłał problem, gdyż uważał go za niezłą zagadkę. Początkowo sądził, że maszyna, o której mowa w treści problemu, jest zbyt prosta. Sądził, że zdoła pokazać jej nieuniwersalność. Gdy jednak przyjrzał jej się bliżej, ujrzał złożoność, która dała podłoże do zbudowania maszyny uniwersalnej. Można mu pozazdrościć, zwłaszcza, że po przekartkowaniu dowodu ma się wrażenie, że jest on w zasięgu możliwości zrozumienia, a więc i skonstruowania, matematyka-amatora. Wolfram pisze, że nagroda ta jest miłym sposobem wydania dwudziestu pięciu tysięcy ... Wolfram sądzi, że wszystko jest obliczeniami ...

OOA/OOD i Air Traffic Control

2008-06-16T08:09:00.001-07:00

Metoda obiektowa projektowania i analizy software'u ma w opinii zwolenników wprowadzić dyscyplinę i porządek do procesu tworzenia oprogramowania. W rzeczywistości wydaje się być jednak za mało ścisła. W klasycznych książkach Coada i Yourdona i na wykładach w uczelniach technicznych, które opierają się na tej obiektowej tradycji proponuje się poszukiwanie klas i obiektów w fizycznej rzeczywistości i odwzorowanie ich w projekcie. Zawsze mnie to dziwiło, jakim cudem struktura rzeczywistości ma się tak prosto przenieść na strukturę programu. Ma to sens, owszem, ale tylko w symulacji komputerowej. Należy zawsze pamiętać o tym, że obiekty w programie to odwzorowanie naszej wiedzy, a nie stanu rzeczywistego obiektu. I tak, na przykład, w programie używanym w aptece, owszem, mamy obiekt klasy "pacjent" a także "lekarstwo", ale nie będzie metody "pacjent.zażyj( lekarstwo )", bo to tylko w rzeczywistości pacjenci zażywają lekarstwa. W komputerze nie.

W książce Coada i Yourdona autorzy posługują się przykładem wziętym z życia: systemem kontroli ruchu powietrznego. Pełno tam tras, radarów i samolotów. Kiedy to czytałem, nie wiedziałem, dlaczego akurat te radary są takie ważne. Potem, parę lat później, przypadkowo natrafiłem na klasyczną unixową grę tekstową atc. Był to prosty symulator konsoli radaru kontrolera ruchu powietrznego. Na ekranie powyżej widzimy, jak to działa. Właśnie w mój obszar wleciały dwa samoloty: b7 i A7. A7 zmierza w stronę wyjścia E1, a b7 w stronę E4 (widzimy ten "plan lotu" w tabelce po prawej). Oba znajdują się na wysokości 7 tys. stóp (oznacza to siódemka w symbolu samolotu). Należy, wydając odpowiednie komendy dotyczące kierunku ruchu i wysokości lotu doprowadzić wszystkie samoloty do ich przeznaczenia i nie dopuścić do zderzenia. Po kilkunastu minutach konsola radaru zawiera kilka lub kilkanaście samolotów, a człowiek jest znużony z powodu ciągłego napięcia. Ponieważ sterowanie wyimaginowanymi samolotami jest bardzo zajmujące, postarałem się o zdobycie bardziej rozbudowanych, graficznych programów, w końcu zacząłem używać darmowego symulatora firmy Xavius. Prawdę mówiąc ze wszystkich gier komputerowych, jakie miałem w życiu poznać (cóż poznałem ich niewiele w porównaniu z moimi kolegami) ten rodzaj wciągnął mnie najbardziej. I siedząc godzinami w najwyższym napięciu nad sektorem powietrznym Chicago lub Los Angeles powoli uzyskiwałem wgląd w hierarchię klas Coada i Yourdona dotyczącą dziedziny ruchu powietrznego. Jedno jest pewne: aby zobaczyć te klasy, trzeba choć trochę poznać tematykę, której dotyczy dany projekt. Prymitywna gra atc(6) okazała się bardzo zbliżona w charakterze do tych złożonych. Najwidoczniej jej autor wykonał kawał dobrej analizy obiektowej ...

Milion dolarów nagrody

2008-06-09T08:48:00.001-07:00

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

Widzenie barwne i Unix

2008-06-05T09:51:00.001-07:00

Widzenie barwne człowieka oparte jest na trzech różnych typach komórek światłoczułych, czułych odpowiednio na światło czerwone, zielone i niebieskie, dlatego każde wrażenie barwne może być wywołane za pomocą bodźców trójkolorowych wymieszanych w odpowiednich proporcjach. Kolor żółty widzimy, gdy pobudzimy oko mieszaniną barwy zielonej i czerwonej, ale identyczny kolor spostrzegamy gdy pobudzimy oko monochromatycznym światłem żółtym. Nie ma tu analogii do słyszenia dźwięków: człowiek odróżnia wielodźwięki od dźwięków prostych, ponadto nie jest wrażliwy na wysokość dźwięku, a raczej na ich różnicę.

Znalazłem gdzieś w sieci obrazek mający przedstawiać widmo światła białego:

Postanowiłem zbadać, jak został skonstruowany z trzech barw
składowych. Tęcza powinna składać się z barw prostych o zmieniającej się płynnie długości. Grafika komputerowa to - wiadomo - mieszanina trzech barw prostych o różnym natężeniu w różnych punktach - coś całkiem innego niż oryginalny pierwowzór. Gdyby istniała istota zdolna do widzenia absolutnego barw, bez trudu rozpoznałaby oszustwo. Ja potrzebowałem do tego kilku narzędzi uniksowych.

Po pierwsze rozkompresowałem obrazek przy użyciu djpeg:

$ djpeg pasek.jpg > pasek.ppm

Następnie przekonwertowałem plik na format tekstowego ppm'a, aby łatwiej mi było go dalej przetwarzać:

$ pnmnoraw pasek.ppm > pasek.txt

Szybki rzut oka do pliku:

$ head pasek.txt
P3
600 66
255
254 0 0
254 0 0
254 0 0  
254 0 0  
253 1 0

....

Mamy 600 pikseli szerokości.

Teraz zamieniam trochę porządek, żeby mieć jeden piksel w jednym wierszu:

$ awk '{
>         S="";
>         for (i=1; i<=NF; i++) {
>                 S=S" "$i;
>                 if (i % 3 == 0) {
>                         print S;
>                         S="";
>                 }
>         }
> }' pasek.txt > pasek.x

$ head pasek.x
254 0 0
254 0 0
254 0 0
254 0 0

....
Dobrze idzie, teraz wezmę jeden rządek i narysuję wykres nasycenia trzech barw:

 
$ head -n 600 pasek.x > pasek3
$ gnuplot
gnuplot> plot 'pasek3' using 1 with lines, 'pasek3' using 2 with
lines, 'pasek3' using 3 with lines

Pięknie, widać, co zrobił autor tego rysunku: wygenerował go automatycznie używając kawałków liniowych funkcji !

Jeszcze tylko wykonałem zrzut ekranu i zamieniłem go na jpg, żeby umieścić wykres w blogu:

 
$ xwd
$ xwdtopnm pasek.xwd > pasek3.ppm
xwdtopnm: writing PPM file
$ cjpeg pasek3.ppm > wykres1.jpg

Gotowe.
Ciekawe, jakbym to zrobił w Windowsach ...

Ciekawostką jest fakt, że gnuplot do oznaczania kolejnych linii używa kolorów właśnie w kolejności
czerwony, zielony, niebieski.
Inną ciekawostką jest czerwony składnik po prawej stronie widma -
tam, gdzie mamy mocny fiolet.

Phoenix cd

2008-06-05T07:31:00.000-07:00

Wczoraj lądownik Phoenix przestał odbierać sygnały z orbitera "Odyseja", który do tej pory służył jako przekaźnik sygnału na odcinku Ziemia - Mars. Powodem było nieoczekiwane wejście orbitera w tryb bezpieczny. W trybie tym przestają działać mniej istotne funkcje, a do takich projektanci zaliczyli komunikację z lądownikiem. Nie wiadomo dlaczego przekaźnik wszedł w tryb bezpieczny, ale spodziewamy się, że wyjdzie z niego za parę dni. W takiej sytuacji Phoenix wykonuje rozkazy, które otrzymał uprzednio, w danym momencie oznacza to, że będzie kontynuował robienie zdjęć w celu skompletowania 360-stopniowej pełnokolorowej panoramy wysokiej rozdzielczości. Jeśli będziemy mieli trochę szczęścia, zobaczymy może na horyzoncie majaczące niewyraźnie sylwetki marsjańskich osiedli ... Tymczasem naukowcy rozważają użycie jako przekaźnika MRO (Mars Reconnaissance Orbiter) który jest także przystosowany do tego celu i był już w ten sposób używany, ale miał ostatnio problemy z radiem. W próbkach pyłu marsjańskiego, które Phoenix zdążył już pobrać za pomocą swojej kopareczki, widać jakąś białą substancję, na razie nie wiadomo, co to. Spekuluje się, że to lód, albo sól. Na Marsie znajduje się w tej chwili ponad osiem ton sprzętu wysłanego przez ludzi. Najlepiej sprawują się amerykańskie łaziki, które działają już nieprzerwanie kilka lat, choć były obliczone na miesiące. Inne państwa też wysłały tam kosmiczne roboty , ale wszystkie zagraniczne rozbiły się lub zepsuły ... Amerykanie rządzą na Marsie.

Phoenix

2008-06-03T08:40:00.000-07:00

Kolejny amerykański robot wylądował na Marsie. Ta misja różni się od poprzednich - użyto statycznego lądownika, a nie autonomicznego łazika-włóczęgi. Wynika to z celów misji, trzeba będzie wiercić, potrzeba dużo sprzętu. Naukowcy chcą poszukać wody. Chodzi o to, że woda będzie bardzo potrzebna ludziom, gdy tam się znajdą, a także o to, że wciąż wierzymy, że życie w kosmosie rozwija się w wodzie. Owszem, woda ma bardzo wiele właściwości sprzyjających życiu, jakie znamy, ale czy nie jesteśmy zbyt antropocentryczni w naszym rozumieniu życia w ogóle ? ...

Pluton

2007-07-23T14:28:00.001-07:00

Na początku XX wieku Gustav Holst napisał "Planety", suitę koncertową o wyraźnie astrologicznym programie, która zyskała sobie dużą popularność i wielu miłośników. Autor muzycznej rubryki w Uranii nazwał je pozycją obowiązkową dla astronoma-melomana. Podobno John Wiliams zapytany, czy wzorował się na "Marsie" Holsta pisząc muzykę do "Star Wars" miał odpowiedzieć, że nie wzorował się, ale jest dumny z takiego przypuszczenia ...

W 1930 roku odkryto kolejną planetę - Pluton - ale Holst nie dopisał kolejnej części, choć był do tego nakłaniamy. Kilku innych kompozytorów to zrobiło, ale historia w pewnym sensie przyznała Holstowi rację - w 2006 roku Międzynarodowa Unia Astronomiczna, chcąc uporządkować nazewnictwo orzekła, że Pluton jest tylko "planetą karłowatą".

nagroda Wolframa

2007-07-20T13:42:00.000-07:00

W maju 2007 Stephen Wolfram ufundował nagrodę w wysokości 25000 $ dla osoby, która będzie w stanie rozsztrzygnąć problem, czy pewna prosta maszyna Turinga o dwóch stanach i trójsymbolowym alfabecie jest uniwersalna. Dla tych, którzy potrzebują pieniędzy, opisuję dalej pojęcia potrzebne do zdefiniowania problemu - są dość proste. Poniżej rzeczona maszyna zapisana graficznymi symbolami Wolframa:

Maszyna Turinga jest abstrakcyjnym modelem obliczeń stworzonym dla celów teoretycznych przez Alana Turinga w 1936 roku. Składa się ona z nieskończenie długiej taśmy podzielonej na komórki, głowicy pisząco-czytającej, wskaźnika stanu, który może wskazywać jeden z kilku stanów, oraz tabelki reguł. Maszyna pracuje wg ścisłego przepisu, przy czym jej praca podzielona jest na kolejno następujące po sobie kroki. W każdym kroku maszyna czyta symbol z komórki znajdującej się właśnie w polu widzenia głowicy, w tabelce odszukuje regułę na podstawie aktualnego stanu i przeczytanego symbolu i wykonuje określoną w tej regule akcję. Akcją może być zapisanie nowego symbolu i przesunięcie głowicy o jedną komórkę w lewo lub w prawo.

Oczywiście istnieje wiele maszyn Turinga: różnią się liczbą stanów, alfabetem symboli i zawartością tabeli reguł. Co jest jednak najciekawsze, co udowodnił Alan Turing, możliwe jest stworzenie Maszyny Uniwersalnej, która potrafi symulować każdą inną maszynę Turinga, zapisaną w odpowiedni sposób symbolicznie na jej taśmie. Taka uniwersalna maszyna została wielokrotnie jawnie zapisana, jest to względnie proste zadanie. Można także udowodnić, że wszelkie mechaniczne obliczenia da się zrealizować za pomocą maszyny Turinga - jest to więc mocne narzędzie badawcze - jeżeli udowodnimy, że jakiś system obliczeniowy jest zdolny symulować Uniwersalną Maszynę Turinga, możemy mieć pewność, że potrafi on wykonać wszystkie obliczenia, które potrafimy formalnie zapisać - tak, jak komputer.

Do dziś nie wiadomo, jaka najmniejsza maszyna Turinga może być maszyną uniwersalną. Wolfram znalazł dwustanową maszynę o alfabecie pięcioznakowym, ale nie uduwodnił, że jest najmniejsza wśród Maszyn Uniwersalnych. Co więcej, znalazł lepszą kandydatkę, ale nie potrafi rozstrzygnąć, czy jest Uniwersalna. I stąd nagroda - każdy może zgarnąć tę pulę !

Dobrymi kandydatami do nagrody mogą być na przykład autorzy i entuzjaści ezoterycznych języków programowania - często posługują się tym aparatem pojęciowym, aby wykazać, że ich języki są "Turing-kompletne". Chcąc przystąpić do konkursu, warto przejrzeć New Kind Of Science, ale także prace hobbystów - polecam ich wiki. Jeżeli ktoś dziwi się "po co to wszystko", niech pomyśli o tych pieniądzach ;-) Albo niech pomyśli o Johnie von Neumannie, który w wyniku tego typu teoretycznych rozważań wpadł na pomysł budowy maszyny liczącej, czyli komputera, którego zapewne właśnie używamy - ja - pisząc te słowa - Ty - czytając je.

konkursy programistyczne

2007-07-15T04:44:00.000-07:00

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.

lazy K

2007-07-09T14:10:00.000-07:00

Unlambda opiera się na rachunku kombinatorów SKI, który jest rachunkiem lambda pozbawionym zmiennych - stąd nazwa. Dodatkowo autor dołożył kilka nadmiarowych mechanizmów, w tym "call with current continuation", znane niektórym z Guile. Zrobił to celowo, na złość, zresztą przyznaje się do tego, chciał jeszcze bardziej zaciemnić obraz tego, co robi program w jego języku. Warto przejrzeć jego artykuł na ten temat. Konstrukacja ta robi czary-mary ze stanem obliczeń, w sposób dużo bardziej tajemniczy niż setjmp(3) z C albo throw/catch z C++. Inaczej autor "lazy K" - ten uprościł wszystko maksymalnie i zostawił tylko operatory ("kombinatory") S, K, I. Zresztą i tak był rozrzutny - przecież I może być wyrażone jako (S K K) - zobacz tu. Ale Chris Baker był jeszcze bardziej radykalny i stworzył język, który ma tylko dwa symbole i nadal jest kompletny. Czemu to służy ? Tylko teoretycznym badaniom. Albo artystycznej zabawie - dla niektórych język programowania też jest dziełem sztuki .......

SODA constructor

2007-07-06T15:04:00.000-07:00

Tak wygląda skonstruowany w aplecie SODA stwór robakopodobny, który umie chodzić ! Składa się ze sprężynek (to te czarne krechy) poruszających się w rytm fal nerwowych, których częstotliwość i fazę można ustawiać w ww aplecie wg uznania. Stworki takie mogą pełzać, dreptać, kiwać się i nawet można urządzać ich wyścigi. A fizyka całości jest bardzo prosta: sprężynki, grawitacja i tarcie. Całość w przestrzeni dwuwymiarowej. Trójwymiarowa wersja konstruktora nie jest już tak łatwa w użyciu, ale za to efekty są niesamowite - te wszystkie ośmiornice i kosmiczne potwory są jak prawdziwe !

TargetWriter

2007-07-06T10:40:00.000-07:00

Jak napisać generator tekstu oparty na szablonach ? Nie trzeba go pisać - istnieje i jest bardzo znany, to BASH. Wystarczy napisać kilka funkcji i korzystając z mechanizmów basha można generować dowolny tekst. Tak powstał WriteTarget, generator oparty na bashu. A tak wygląda próbka kodu:

# the template hello.tpl:
cat <<END_OF_FILE
<html>
<head>
     <title> $(target MAIN_TITLE) </title>

</head>
<body>
     <h1> $(target MAIN_TITLE) <h1>
     $(target TEXT)

</body>
</html>  
END_OF_FILE 

# the text file:
. ./hello.tpl

write MAIN_TITLE  H E L L O
write TEXT Hello world !

unlambda

2007-07-06T10:25:00.000-07:00

Język programowania, który nie posiada pętli, instrukcji warunkowej, zmiennych, nie posiada właściwie nic, tylko jednoargumentowe funkcje. Funkcja przyjmuje jeden argument, jednoargumentową funkcję i zwraca także jednoargumentową funkcję. To nie LISP, to UNLAMBDA. Funkcja stała - zwraca zawsze to samo. Funkcja "przeźroczysta", albo identycznościowa - zwraca zawsze swój argument. I konstruktor - funkcja, która pozwala tworzyć kolejne .... To wystarcza, aby pisać kompletne w sensie maszyny Turinga programy. A tak wygląda program w tym języku:

```s``s``sii`ki
  `k.*``s``s`ks
 ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
  `k``s`ksk

Czytać się tego nie da ....

csound

2007-07-06T09:54:00.000-07:00

Czym assembler dla programisty, tym dla muzyka komputerowego jest csound. Jest to program wywodzący się ze starej unixowej tradycji końca ubiegłego wieku, więc trudny w użyciu, ale baaaaardzo potężny. Jak Povray w grafice 3D, csound służy do off-line'owego renderowania utworu. Może jednak także służyć jako real-time'owy syntezator - podłączamy go wtedy do naszego kontrolera MIDI i gramy. A tak wygląda kawałek utworu napisany w języku csound'a:

t 0 90

i100 0 205 .05 1.5 1.7
i101 0 205 .2 2.1 2 .25
i102 0 205 .3 2 2.2 .15 .175
i103 0 205

Dur Root Amp Shape Pat Acc Env Filter Pan Wet
;1 2 3 4 5 6 7 8 9 10 11 12
i1 0 4 6.04 15000 2 100 81 50 56 20 1
i1 + . . . . 101 . . . . .
i1 + . 5.04 . . 100 . . . . .
i1 + . . . . 101 . . . . .
i1 + . 6.04 . 2 100 . . . . .
i1 + . . . . 101 . . . . .
i1 + . 5.04 . . 100 . . . . .

A tak wygląda opis instrumentów w tym języku (orchestra file) :

instr 3
kpan      =         p6
i1        =         p5*3

k1        oscil     i1, 1/p3, 10             ; ADSR
a2        oscil     k1, p4, 11               ; SINE

       outs      a2*kpan,a2*(1-kpan)

garvbsig  =         garvbsig+(a2*.1)

       endin

To oczywiście tylko próbka - prawdziwy program jest o wiele dłuższy ... Jeśli chcesz posłuchać, co może powstać z takich matrixowych cyferek, posłuchaj np. tu.