środa, 1 października 2008

Post Scriptum i PostScript

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

czwartek, 19 czerwca 2008

Najprostsze pliki graficzne

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

wtorek, 17 czerwca 2008

Nagroda Wolframa przyznana pół roku temu

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

poniedziałek, 16 czerwca 2008

OOA/OOD i Air Traffic Control

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

poniedziałek, 9 czerwca 2008

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

czwartek, 5 czerwca 2008

Widzenie barwne i Unix

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

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.

wtorek, 3 czerwca 2008

Phoenix

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