Posts Tagged ‘Lisp’

Dlaczego Lisp?

Sunday, August 1st, 2010

Wielokrotnie byłem pytany, dlaczego interesuję się Lispem, co mnie skłoniło do jego nauki i “co w nim jest takiego fajnego”. W tym tekście chcę odpowiedzieć na te pytania i wyjaśnić, czego szukam w tym języku i jak jego nauka wpłynęła na mnie do tej pory.

Historia zaczęła się rok temu, gdy aktywnie prokrastynując celem ucieczki od projektu, który został mi “na wrzesień”, trafiłem na interesujący post na devBlogach – “Niebezpieczne Java-Szkoły”. Sam artykuł, którego lekturę gorąco polecam, wspomina o Lispie w kilku miejscach, ale jedna wzmianka okazała się decydująca. “Beating the Averages” Paula Grahama.

Tak, słyszałem wcześniej o Lispie. To ten język, w którym nawiasy tworzą większość kodu. Wygląda jak mleko z powrzucanymi obciętymi paznokciami. To najdziwniejszy język, w jakim można pisać kod, zaraz po BF i Whitespace. Tego typu opinie. A tu nagle pewien człowiek twierdzi w porywającym eseju, że Lisp jest najpotężniejszym językiem programowania dostępnym obecnie. I przedstawia argumenty. To przykuwa uwagę.

Blub programmer
Jedną z najważniejszych myśli eseju Paula Grahama jest to, że języki programowania różnią się w mocy. Myślę, że intuicyjnie zdawałem sobie z tego sprawę od jakiegoś czasu, ale nigdy nie myślałem o tym świadomie. Właściwie, muszę się do czegoś przyznać. Do tego momentu, zgodnie z terminologią eseju, byłem typowym “Blub programmerem” (jeżeli Czytelniku jeszcze nie przeczytałeś tego eseju, to gorąco zachęcam do lektury). Mój ulubiony język programowania (tak się złożyło, że był nim C++) jest najlepszy. Wszystko co jest na niższym poziomie to niepotrzebne męczenie się. Wszystko, co jest na wyższym poziomie (zwłaszcza Java, za którą nie przepadałem) i tak można zaimplementować w C++. Właściwie cały mój świat programistyczny skupiał się wokół C++, Javy (która jak dla mnie jest bloatware’m), C# i PHP. Programowanie funkcyjne? Nie słyszałem nigdy o czymś takim.

Wielkie obietnice

Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot.

Powyższy cytat, przytoczony przez Paula a pochodzący z “How To Become A Hacker” Erica Stevena Raymonda, był intrygujący. Przeczytałem więc inne eseje – w tym “Revenge of the Nerds”, “What Made Lisp Different”. Na innej stronie znalazłem też “The Nature of Lisp”. Wszystko to przyswojone “na raz” robi mętlik w głowie, ale pewne trendy zaczynały stawać się widoczne.

Widziałem trochę kłótni, dysput i artykułów na temat wyższości jednych języków nad drugimi (C++ vs. Delphi i C++ vs. Java były moimi ulubionymi sporami). Zwykle fani danego języka twierdzą, że jest on lepszy od języka przeciwników. Ale nigdy wcześniej nie widziałem, żeby ktoś twierdził, że ich język jest najlepszy, najpotężniejszy, że Bóg stworzył za jego pomocą wszechświat. Tylko Lisp odważył się zająć miejsce ponad wszystkimi. Zwykła arogancja? A może uzasadniona*?

W dużym skrócie, najważniejsze argumenty stawiane przez zwolenników Lispu to:

  • Język ten jest unikatowy w swojej możliwości wyrażania myśli przez programistę. Dzięki umiejętności przepisywania własnego kodu źródłowego w czasie kompilacji można zmieniać sam język w taki sposób, żeby dopasowywał się do rozwiązywanego problemu. Programując w Lispie człowiek używa najpotężniejszego języka programowania dostępnego obecnie.
  • Sam proces poznawania i zrozumienia Lispu czyni człowieka lepszym programistą, niezależnie od języka jakiego przyjdzie mu później używać (ten argument zdaje się też pasować do teoretycznych, matematycznych stron informatyki; biorąc pod uwagę pochodzenie Lispu, może to nie jest zbieg okoliczności).
  • Kolejne języki programowania powstające obecnie stopniowo zdążają do Lispu, implementując różne cechy, które w tym ostatnim były dostępne od wielu lat. Nauka Lispu jest więc strategicznie najlepszą opcją, bo język ten zawiera wszystkie ważne elementy semantyczne innych języków, a wciąż ma cechy, których nikt inny nie powielił (np. makra).

To wszystko brzmiało dla mnie bardzo intrygująco – zwłaszcza, że nie chciałem (i dalej nie chcę) skończyć jako klepacz biznesowego kodu w Javie. Bardzo zaciekawiony postanowiłem więc nauczyć się Lispu i sprawdzić doświadczalnie, czy te wszystkie zapewnienia jego zwolenników są uzasadnione.

Eksperyment
Przez ostatni rok uczyłem się Lispu w wolnych chwilach (czasem nawet spychając ‘przyziemne sprawy uczelni’ na dalszy plan). Chociaż póki co zdążyłem napisać w nim jedynie małą grę i kilka drobnych narzędzi, to mogę dziś powiedzieć, że odniosłem wiele korzyści, często nie związanych stricte z naturą języka Lisp.

  • Odkryłem, że tam daleko, poza C++, Javą i C# jest cały wielki świat programowania. Że programowanie zorientowane obiektowo nie jest receptą na wszystko (świadomie bądź nie, ale wcześniej w to wierzyłem); są inne paradygmaty programowania, które w wielu miejscach są bardziej odpowiednie.
  • Poznałem programowanie funkcyjne. Chociaż Lisp nie jest językiem funkcyjnym (jest wieloparadygmatowy), to wiele wzorców pisania kodu – związanych z pracą na listach i drzewach oraz funkcjach wyższego rzędu i wyrażeniach lambda – stanowi podstawę funkcyjnego tworzenia oprogramowania (która to jest tematem na zupełnie osobny wpis). Gdyby nie Lisp, najprawdopodobniej w ogóle nie zainteresowałbym się Erlangiem, i nie pisałbym w nim dziś oprogramowania.
  • Zrozumiałem, że C++ w programowaniu zorientowanym obiektowo nie mówi ostatniego słowa. Common Lisp tak na prawdę pokazał mi, że model obiektowy może być zrobiony wokół zupełnie innych założeń, być większy i bogatszy.
  • Nabrałem wstrętu do pisania rzeczy, które powinien pisać za mnie komputer. Jak powiedział Olin Shivers, “I object to doing things that computers can do.” Przykładowo, wśród programistów C/C++ (a także innych języków, np. Erlanga) znana jest niechęć do używania makr preprocesora. W wielu przypadkach jest ona uzasadniona, jednak dzięki “Lispowemu sposobowi myślenia” zacząłem traktować preprocesor jako przydatne narzędzie generowania kodu w czasie kompilacji.

Nauka Lispu miała też potężny efekt uboczny:

  • Zacząłem dostrzegać wpływy Lispu wszędzie. Tak, wiem – niektórych to denerwuje. Odruchowe zwracanie uwagi, że “XYZ zgapiło to z Lispu!”. Te skojarzenia nie są jednak nieuzasadnione. Dobrze oddaje to “10-ta zasada programowania Greenspuna”:

    Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

    Na to, jak ten sposób myślenia udziela się programistom Lispu, samokrytycznie zwrócił uwagę Slobodan Blazeski w artykule o Haskelu:

    (…) The reasons vary but it probably has something with lispers’ being spoiled brats. They’re damn hard to impress. You show them the cool feature that your favourite language has and they either already have it, have something better or they’ve already seen it and decided it’s not such a good idea as you might think.

A droga długa jest; nie wiadomo, czy ma kres…
W dalszym ciągu intrygują mnie możliwości Lispu, których jeszcze w ogóle nie poznałem. W szczególności makra i metaprogramowanie. Chciałbym też dokładniej sprawdzić, czy Lisp jest faktycznie tak wygodnym narzędziem do pisania eksperymentalnych aplikacji jak pisał Paul Graham**. Przede mną jeszcze daleka droga. W dalszym ciągu nie umiem używać makr ani rewelacyjnego systemu wyjątków w Common Lisp. W szczególności, jeżeli chodzi o lekturę, to chciałbym skończyć SICP, a następnie przeczytać “On Lisp”, “Let Over Lambda” i “Art of Metaobject Protocol”. Do dnia dzisiejszego Lisp dał mi jednak bardzo dużo, i nie żałuję, że zacząłem się go uczyć. Dzięki niemu wyszedłem z “zastoju” informatycznego i odkryłem wiele nowych dziedzin i rozwiązań, o których wcześniej nawet mi się nie śniło.

(przypisy)
* – Podobnie do mnie czuł się pewien człowiek, którego Paul Graham cytuje na swojej stronie

“I have heard more than one LISP advocate state such subjective comments as, “LISP is the most powerful and elegant programming language in the world” and expect such comments to be taken as objective truth. I have never heard a Java, C++, C, Perl, or Python advocate make the same claim about their own language of choice.”

- A guy on Slashdot. What theory fits this data?

** – W czasach, gdy Paul pisał swój esej, języki takie jak Python, Perl czy Ruby nie były powszechnie używane w taki sposób jak dzisiaj; obecna ilość i rozmiar projektów powstających w językach dynamicznie typowanych wysokiego poziomu, posiadających REPL jest argumentem za tym, że miał rację.

Funktory – traktowanie obiektów jak funkcje w Common Lisp

Monday, June 14th, 2010

Funktorem nazywamy obiekt, który może być wywoływany jak funkcja. Często chcemy też, by wywołanie takiego funktora przypominało składnią wywołanie normalnej funkcji w danym języku programowania.

W niektórych językach (np. w C++, o czym niedawno pisałem) funktorów używa się do naprawienia braku naturalnego wsparcia dla funkcji first-class. Jednak Common Lisp takie wsparcie ma, więc zasadnicze pytanie brzmi: po co nam funktory w języku, w którym funkcja jest takim samym typem danych jak każdy inny?

Zadajmy sobie inne pytanie – co robimy z funktorami?

  1. Przekazujemy je do funkcji wyższego rzędu, takich jak map czy reduce.
  2. Ponieważ są to obiekty, możemy trzymać w nich dodatkowe informacje lub umożliwiać wykonywanie na nich dodatkowych operacji.

Wyobraźmy sobie, że piszemy bibliotekę do obliczania minimum zadanej funkcji matematycznej*. Niektóre metody potrzebują jedynie znać wartości naszej funkcji w kilku punktach. Inne potrzebują także pochodnych lub gradientu. Chcielibyśmy takie informacje trzymać “razem” z naszą funkcją, móc uzyskać do nich dostęp w razie potrzeby (na tym etapie nie zastanawiamy się nad sposobem ich wyliczenia czy przechowywania). Nasza matematyczna funkcja powinna więc być obiektem. Z drugiej strony, chcemy mieć możliwość użycia jej jak normalnej funkcji w języku programowania – choćby po to, by nie mnożyć dziwnej składni tylko dlatego, że chcemy “na boku” przechowywać dodatkowe informacje. W C++ przeładowalibyśmy operator() – spełniając w ten sposób wymagania 1) i 2) naszego funktora.

Deklaracja i użycie wyglądałyby na przykład tak:

class MathFunction
{
//...
public:
    MathFunction FirstDerivative(); //funkcja zwracajaca nam pierwsza pochodna
    double operator() (double x); //funkcja zwracajaca nam wartosc w punkcie
};

//uzycie
MathFunction funkcja;
double wynik = funkcja(100.0);
std::for_each(dane.begin(), dane.end(), funkcja);

Powiedzmy raz jeszcze, co chcemy uzyskać w Lispie – chcielibyśmy mieć obiekt funkcja, który dałoby się wywołać jak funkcję, pisząc: (funcall funkcja 100)**, oraz przekazać do funkcji wyższego rzędu, np.: (map 'list funkcja dane), ale równocześnie chcemy uzyskiwać z niego pewne informacje, np. (first-derivative funkcja).

Rozwiązaniem jest użycie Metaobject Protocol do zmiany typu klasy z standard-class na funcallable-standard-class. Przykładowo (w Clozure Common Lisp***):

(defclass math-function ()
  () ; tutaj mozemy umieszczac sloty, czyli zmienne skladowe
  (:metaclass ccl:funcallable-standard-class))

Definiujemy również metodę zwracającą pierwszą pochodną:

(defgeneric first-derivative ()
  (:documentation "Returns analytical first derivative of a function."))

(defmethod first-derivative ((f math-function))
  (...)) ; kod metody pomijam

Od teraz obiekty klasy math-object są “funcallable” – mogą być przekazane do funcall, co oznacza, że mogą być argumentami funkcji wyższego rzędu. Spełniamy tym samym wymagania 1) i 2) naszego funktora.

Pozostaje tylko pytanie, jaki kod wykona “wywołanie” naszego obiektu? Kod ten możemy ustawić za pomocą set-funcallable-instance-function. Wygodnie jest zrobić to w konstruktorze. W Lispie, konstruktor klasy tworzymy dodając metodę after o nazwie initialize-instance.

(defmethod initialize-instance :after ((f math-function) &key code)
  (set-funcallable-instance-function f code))

Dodaliśmy parametr kluczowy code, który pozwala nam tworzyć obiekty w następujący sposób:

; stworzony obiekt zapisujemy do zmiennej square
(setq square (make-instance 'math-function :code (lambda (x) (* x x))))

; uzycie:
(funcall square 3)
;wynik: 9

Jeżeli chcemy, aby nasz funktor był widziany jak funkcja globalna i używany ze składnią normalnego wywołania funkcji, możemy napisać:

(setf (fdefinition 'square) square)

; ponizszy kod teraz bedzie dzialal:
(square 3)
; wynik: 9

Wydaje się, że konieczność zaprzęgania Metaobject Protocol sprawia, iż stworzenie funktora jest czymś skomplikowanym w stosunku do np. C++. Należy jednak pamiętać, funktory w Lispie zwykle nie są potrzebne – same funkcje są first-class i można je przekazywać oraz zwracać jak każdy inny typ. Konieczność łączenia z funkcjami dodatkowych danych i operacji jest – wydaje mi się – czymś rzadkim. I nawet nie jestem pewien, czy nie znalazłaby się lepsza abstrakcja dla tego problemu.

Przypisy
* – problem nie jest wcale taki błahy ani wzięty z powietrza – w tym semestrze miałem na studiach cały przedmiot poświęcony znajdywaniu minimum funkcji na różne, niekiedy dość dziwne sposoby.
** – składnia (funcall funkcja argumenty) jest naturalnym sposobem wywoływania funkcji przekazanej w zmiennej w Common Lisp. Język ten, w przeciwieństwie do Scheme, pozwala funkcjom i zmiennym nosić te same nazwy – dlatego nie możemy napisać po prostu (przekazana-funkcja argumenty) (tak jak zrobilibyśmy w Scheme), gdyż Lisp będzie szukał symbolu przekazana-funkcja w przestrzeni nazw funkcji.
*** – jest trochę zamieszania z Metaobject Protocol w różnych implementacjach Common Lispu. Sam symbol funcallable-standard-class znajduje się w pakiecie specyficznym dla danej implementacji. Dla Clozure Common Lisp jest to pakiet CCL (tak jak w przykładzie), w SBCL prawdopodobnie SB-MOP. Powstał projekt Closer mający na celu ujednolicenie Metaobject Protocol pomiędzy różnymi implementacjami Common Lispu, ale nie miałem okazji jeszcze z niego korzystać.

Cloze Call – postmortem

Thursday, May 13th, 2010

Cloze Call

W końcu mój ostatni projekt – Cloze Call – doczekał się wpisu na blogu. Po sporej ilości zabaw udało mi się znaleźć popełniony błąd i ostatecznie przygotować binarkę pod Windows’a.

Po szczegóły, screeny, źródła i download – zapraszam na stronę projektu!

Postmortem

Jedną z sugestii na 2010LGDC było, by każdy na koniec napisał postmortem swojej gry. Poniżej zamieszczam tekst w oryginale (wzbogacony jedynie o linki i bez poprawiania błędów) – dla tych, którzy nie boją się czytać długiego tekstu po angielsku :) .

Hi,

This is a postmortem for my 2010LGDC entry, called “Cloze-Call”. It derives its name from Clozure Common Lisp, in which it was written (more on that topic in Section 2). It is also a reference to a phrase, “close call”, which means achieving something or escaping by a narrow margin, which corresponds to the ball maneuvering between planets.

The game itself is a very simple “Gravity Pong”. Your goal as a player is to shoot a ball into a hole. The ball must not collide with any of the planets that are on screen. To make things more fun, all planets attract the ball by means of gravity force.

1. What did I learn?
Common Lisp, first of all. It is my first real project in Lisp. I started learning this language in summer 2009, but (thanks to university) I didn’t have much time to write some real programs.

Using ASDF – at least a little bit.

That my old design concept for Game State Manager code (which I used for years in at least three other languages) has flaws to get ????

2. What went right?
Setting up the environment. I am working on 32-bit Windows 7. Even though I had to try out SBCL (which crashed on SDL examples), CLISP (too slow), ECL (also too slow) and SBCL on Ubuntu before ending up with well-working lispbuilsder-sdl and Clozure Common Lisp, I am surprised that the installation and setting up process wasn’t that complicated and things actually worked first-time. I spent two days before the Challenge on setting up SDL and working environment.

Graphic Design. This project confirmed what I actually learned recently – it is important to sacrifice some time and get decent-looking graphics / media for your product (be it a game, or anything else) and make it look nice. I’d be very unhappy if this game had circles and squares instead of those pictures, which I found on OpenGameArt.org.

Fixed-step physics. I am using and promoting fixed time step approach to simulation in computer games, and it’s the first time I really saw how good it is. During first physics test I had a fixed initial velocity vector for the ball, and I could see how it always travels the same path and lands in the same place.

The game. It isn’t finished, but it is playable and has most of the game mechanics implemented. I had to cut down on features as I was running out of time, but I shipped.

3. What went wrong?
Transparency in SDL – I made some little voodoo and made planets use alpha channel, but the same trick didn’t worked for any other image. I’m still confused why it’s not working, and this phenomena is responsible for ugly Victory/Defeat screens.

Watching movies – I’d have at least few more hours to work on my game if I haven’t found myself some stuff that I really, really wanted to watch.

Bad naming conventions. I heard it’s hard to give names to vector-math library functions. I done it wrong, and had to look for a bug for almost an hour. My vector math library that I wrote for this game had two kinds of functions – some were returning a new vector with the result of an operation, and some modified their arguments. In particular, I had (negative-vector) which returned a new vector representing inversed input parameter. The complimentary function was (negate-vector), which just negated its parameter. I used the latter instead of the former in physics code, and spent almost an hour trying to discover why graphics was flickering.

6 days instead of 7. If I were more careful and wrote 2010-04-01 23:59GMT+1 instead of 2010-04-01 00:00GMT+1, I’d have one more day to work. I found my mistake about a day after signing up and decided not to change my initial declaration.

4. What’s lispy about my entry?
It is in Lisp :) . It is not that common to see a game in Lisp :) .

Few lambdas and high-order functions here and there. I think that my code is more like C++ with Lisp-syntax. But I guess, as for a first Lisp project, it’s not that bad.

5. What interesting algorithms or designs did I use?
My good, old Game State Manager abstraction that I use everywhere. It simplified managing different game screens. Apart from that, I guess everything else is typical stuff you’ll find in any computer game.

At first I wasn’t sure if I want to take part in the Contest. I have lot of stuff to do at university (and other places as well), I don’t know that much Common Lisp, ect. etd. But, I thought, it would be a good occasion to actually learn much Lisp in short time, and write another game. I decided to sacrifice some university lectures and now I’m happy I did it. I’d like to thank David O’Toole for inviting me to #lispgames and encouraging me to take part in the Challenge. And I’d like to thank all of you #lispgames guys for support and nice time wasted (I should have been coding, not chatting :P ) on IRC :) .

Elementarne automaty komórkowe

Sunday, May 9th, 2010

Niedawno odkryłem dostępną darmowo w sieci książkę Stephena Wolframa (tego od programu Mathematica i wyszukiwarki Wolfram|Alpha) – “A New Kind of Science”. Czytelnikom, którzy widzieli jego ostatnie wystąpienie na TED nie trzeba mówić o jego ciekawych poglądach na przyszłość współczesnej nauki oraz o tym, jak duże znaczenie przywiązuje do szukania złożonych zachowań w rzeczach prostych.

Przed lekturą drugiego rozdziału wspomnianej książki postanowiłem napisać sobie prosty, dwustanowy, jednowymiarowy automat komórkowy i wygenerować opisywane przez Wolframa obrazy. Implementacja zajęła piątkowe popołudnie i wieczór, a w rezultacie powstał program symulujący automat komórkowy z dowolną trójelementową regułą oraz renderujący obrazy.

(Galeria automatów komórkowych)

Poniżej chciałbym zaprezentować kilka najciekawszych przykładów tego, co potrafi stworzyć tak prosty automat komórkowy. Nieco dalej wyjaśnię, na czym polega numeracja reguł. Na samym końcu chciałbym też opowiedzieć o programie, który napisałem.

Reguła 30

Reguła 30

Ulubiona reguła S. Wolframa, szeroko omówiona w jego książce. Z prawej strony tworzy się wzór nie mający żadnej widocznej struktury. Sekwencja kolorów bezpośrednio pod punktem startowym jest podobno losowa według wielu testów sprawdzających generatory liczb losowych – sam Wolfram użył reguły 30 jako generatora liczb losowych w programie Mathematica.

Reguła 18

Reguła 18

Pierwsze pojawienie się trójkąta Sierpińskiego. Wiele reguł produkuje różnej postaci trójkąty Sierpińskiego. W całej galerii naliczyłem 24 wystąpienia tego wzoru: 18, 22, 26, 60, 82, 90, 102, 105, 126, 129, 146, 150, 151, 153, 154, 161, 165, 167, 181, 182, 183, 195, 210, 218.

Reguła 151

Reguła 151

Reguła ta jest bardzo ciekawą wariacją wokół trójkąta Sierpińskiego. Powstaje z samych brzegów automatu – to krawędzie są źródłem wzoru, który przy górnej granicy przypomina wspomniany fraktal. Bardzo interesujący jest też wynik “interferencji” zbiegających się wzorców.

Reguła 124

Reguła 124

Prawa krawędź tego wzoru pokazuje powtarzającą się sekwencję trójkątów. Na środku jednak pojawia się bardzo ciekawa struktura, która sprawia wrażenie zupełnie chaotycznej.

Reguła 225

Reguła 225

Ciekawy, chaotyczny wzór powstaje z punktu początkowego. Tutaj jednak, podobnie jak przy regule 151, najciekawsze rzeczy tworzy sama krawędź.

Numeracja Wolframa
Numeracja reguł, zaproponowana przez Wolframa w A New Kind of Science, jest bardzo prosta. Automat, na którym pracujemy oblicza stan nowej komórki z trzech innych – z tej bezpośrednio nad sobą, oraz z lewego i prawego sąsiada komórki nad sobą. Wystarczy zaobserwować, że mając do dyspozycji trzy komórki, z których każda może przyjąć dwa stany (zapalona albo zgaszona), uzyskujemy 8 możliwych układów. Dla każdego takiego układu definiujemy zasadę – czy nowa komórka ma zostać zgaszona, czy zapalona. Łącząc takie zasady dla wszystkich ośmiu stanów uzyskujemy jedną regułę opisującą wszystkie możliwe sytuacje spotkane w omawianym automacie komórkowym.

Łączenie zasad w numer reguły jest oparte o operacje bitowe. Jeżeli potraktujemy trójki komórek jako liczby binarne, gdzie stan ‘zapalona’ oznacza 1, a stan ‘zgaszona’ oznacza 0, uzyskujemy naturalną numerację od 0 do 7. I teraz jeżeli zasada oparta o daną trójkę mówi, ze nowa komórka ma być zapalona, to ustawiamy bit odpowiadający ‘numerowi’ trójki komórek na 1, a jeżeli nowa komórka ma być zgaszona – to na 0. Uzyskany numer zasady jest liczbą ośmiobitową, a więc z zakresu od 0 do 255.

Numeracja Wolframa - objaśnienie

Jeżeli sam opis był zbyt zagmatwany, to mam nadzieję, że powyższe zdjęcie wyjaśniło sprawę ;) .

Symulator automatu komórkowego
(Pobierz symulator)
Sam symulator to prosty program w Common Lispie, który pisałem przez piątkowy wieczór. Trzon designu stanowiły schematy narysowane kredą na betonie przed pizzerią oraz kod rozpisany na pudełku od pizzy :) . Program ten umie przeprowadzać symulacje dla jednowymiarowego, dwustanowego automatu komórkowego o dowolnej szerokości na podstawie reguł sprawdzających trzy sąsiadujące ze sobą komórki.

Screen z symulatora automatów komórkowych.

Główny program wypisuje swoje wyniki w postaci tekstowej, jednak dopisałem też nakładkę, która umie generować obrazy i zapisywać je do plików. Korzysta ona ze znanej programistom gier biblioteki SDL za pośrednictwem bindingów lispbuilder-sdl.

Krawędzie i warunki początkowe
Jest jedna ważna rzecz, o której na tym etapie trzeba wspomnieć. Jak w każdym automacie komórkowym, tak i w tym pojawia się problem krawędzi, czyli tego, jaką wartość ma przyjąć lewy sąsiad pierwszej komórki oraz prawy sąsiad ostatniej. W przypadku mojej implementacji, komórki ‘z poza planszy’ przyjmują domyślnie stan ‘zgaszony’, pusty.

Uważny czytelnik zauważy, że wygenerowane przeze mnie obrazki różnią się miejscami od przykładów z książki Wolframa – wynika to z tego, że symulacja odbywała się na automacie o szerokości 800, gdzie bardzo szybko dochodziła do głosu obecność krawędzi. Zdjęcia zamieszczone w A New Kind of Science są wolne od wpływu krawędzi – najprawdopodobniej ‘krawędź’ jest gdzieś bardzo daleko :) .

Wszystkie obrazki zostały wygenerowane przy tych samych warunkach początkowych, jakie stosował Stephen Wolfram w A New Kind of Science – startujemy ze wszystkimi komórkami zgaszonymi, i zapalamy jedną dokładnie na środku.

Symulator – pobieranie i użycie
Pobierz symulator (źródła).
Przykład użycia (za pomocą specjalnych funkcji do prostego testowania):

(load (compile-file "ca1d.lisp"))

;; wyswietlenie w konsoli 17 iteracji (16 + stan poczatkowy)
;; automatu dlugosci 16 zgodnie z regula 30
(test-wolfram-rule 16 30 16)

;; zakladam, ze lispbuilder-sdl jest juz zaladowany
(load (compile-file "ca1d-gfx.lisp"))

;; wyswietlenie graficznie 600 iteracji (ze stanem poczatkowym wlacznie)
;; automatu dlugosci 800 zgodnie z regula 30
(test-rule-800x600 30)

;; j.w., ale celem wygenerowania samego obrazka:
(test-rule-800x600 30 t)

CLOS jedynym słusznym systemem obiektowym? ;)

Tuesday, May 4th, 2010

“o ile w ciągu zeszłego (2005) roku nic się nie zmieniło to ANSI Common Lisp jest jedynym językiem obiektowym spełniającym wymagania organizacji ‘Object Managment Group’ (tej od CORBY i UML-a). “

Szymon

Lisp, domknięcia i Pokemony

Saturday, May 1st, 2010

Ostatnio na Warsztacie pojawił się problem PoKeMoNizacji tekstu. Przykładowe rozwiązanie tego problemu w Common Lispie można zawrzeć w następujących funkcjach:

(defun get-pokemonizer ()
  (let ((upkemonize nil))
    (lambda (letter)
      (setf upkemonize (not upkemonize))
      (if upkemonize
          (char-upcase letter)
          (char-downcase letter)))))

(defun pokemonize-string (string-to-pokemonize)
  (map 'string (get-pokemonizer) string-to-pokemonize))

Problem pokemonizacji tekstu sam w sobie nie jest wart poświęcania mu miejsca, ale chciałbym wykorzystać tę okazję by pokazać kilka ciekawych rzeczy w Common Lispie.

Zacznijmy od końca. Funkcja

(defun pokemonize-string (string-to-pokemonize)
  (map 'string (get-pokemonizer) string-to-pokemonize))

mogłaby w C++ być napisana jako:

#include <algorithm>

std::string pokemonize_string(std::string input)
{
    std::string outStr(input);
    std::transform(input.begin(), input.end(), outStr.begin(), pokemonize_letter);
    return outStr;
}

std::transform z C++ i map z Common Lispu to przykłady tak zwanych funkcji wyższego rzędu*. Jak nietrudno się domyśleć, zadaniem użytych przez nas funkcji jest przejście przez cały napis znak po znaku i zastosowanie na każdym elemencie funkcji przekazanej jako parametr. Zauważmy, że nie napisaliśmy tutaj żadnej iteracji, żadnej pętli for – myślimy w kategoriach “przejścia funkcją po napisie”. Taki przeskok myślowy jest bardzo cenny; w C++ zalecane jest (mniej błędów się robi) używanie algorytmów z biblioteki STL, które umieją w różny sposób stosować przekazane funkcje na elementach pojemników (polecam przeglądnąć nagłówek <algorithm>).

Skoro mamy już trzon naszego rozwiązania, warto pomyśleć nad samą funkcją pokemonizującą. Według oryginalnej definicji problemu funkcja ma sprawiać, że wynikowy tekst będzie miał co drugą literę wielką. Przyjmijmy automatycznie, że pozostałe litery mają być małe. W naszym rozwiązaniu funkcja pokemonizująca musi więc zmieniać swoje zachowanie w kolejnych wywołaniach – powinna zamieniać litery raz na małe, a raz na duże. Musimy więc w funkcji ukryć stan. Dla przypomnienia, w Common Lispie mieliśmy funkcję:

(defun get-pokemonizer ()
  (let ((upkemonize nil))
    (lambda (letter)
      (setf upkemonize (not upkemonize))
      (if upkemonize
          (char-upcase letter)
          (char-downcase letter)))))

Zadaniem funkcji (get-pokemonizer) jest zbudowanie funkcji pokemonizującej pojedynczy znak. Sama funkcja pokemonizująca zaczyna się od wyrażenia (lambda ..., które oznacza po prostu stworzenie funkcji anonimowej (nienazwanej). Zanim uzasadnię, dlaczego potrzebny jest generator takich funkcji, chciałbym znów odnieść się do kodu z C++ i porównać kody odpowiedzialne za samą zmianę znaku.

#include <cctype>   //potrzebne do std::tolower() i std::toupper()
bool g_upCase = false;
char pokemonize_letter(char input)  //(lambda (letter)
{
    g_upCase = !g_upCase;       //(setf upkemonize (not upkemonize))

    return (g_upCase) ? //(if upkemonize
        std::toupper(input) :   //(char-upcase letter)
        std::tolower(input);    //(char-downcase letter)))
}

W komentarzach zawarty jest odpowiadający kod w Common Lispie. Czytelniku, zastanów się przez chwilkę – co z powyższą funkcją w C++ jest nie tak?

Odpowiedź: stan jest globalny. Wyobraźmy sobie, że chcielibyśmy używać tej samej funkcji wielokrotnie. Do tego jeszcze czasem w osobnych wątkach. Widać wyraźnie, że wiele wywołań funkcji pokemonize_char() będzie pracowało na tej samej zmiennej globalnej, która trzyma stan. Przejście na zmienną statyczną nie rozwiąże problemu – jedynie ograniczy widoczność stanu (co jest dobrą rzeczą). W C++ wypracowano jednak rozwiązanie – jest nim stworzenie obiektu funkcyjnego (inaczej funktora). Jest to obiekt przeciążający operator(), czyli operator wywołania funkcji. Taki obiekt może skutecznie udawać prawdziwą funkcję, a jednocześnie trzymać w sobie stan. Lepsze rozwiązanie naszego problemu w języku C++ wyglądałoby więc tak:

#include <algorithm>
#include <cctype>   //potrzebne do std::tolower() i std::toupper()
//dziedziczenie po std::unary_function ze wzgledu na STL
class Pokemonizer : public std::unary_function<char, char>
{
protected:
    bool upCase;
public:
    Pokemonizer() : upCase(false) {}
    char operator()(char input)
    {
        upCase = !upCase;

        return (upCase) ?  
            std::toupper(input) :
            std::tolower(input);
    }
};

std::string pokemonize_string(std::string input)
{
    std::string outStr(input);
    std::transform(input.begin(), input.end(), outStr.begin(), Pokemonizer());
    return outStr;
}

W tym momencie wywołania pokemonize_string() są już thread-safe. Musieliśmy w tym celu napisać kod tak, by przy każdym wywołaniu pokemonizacji napisu tworzony był nowy obiekt funkcyjny z własnym stanem.

Wróćmy teraz do Common Lispu. Powyższy kod C++ jest odpowiednikiem rozwiązania w Lispie, więc możemy je ze sobą dokładnie porównać. Dla przypomnienia:

(defun get-pokemonizer ()
  (let ((upkemonize nil))
    (lambda (letter)
      (setf upkemonize (not upkemonize))
      (if upkemonize
          (char-upcase letter)
          (char-downcase letter)))))

(defun pokemonize-string (string-to-pokemonize)
  (map 'string (get-pokemonizer) string-to-pokemonize))

Wspomniałem wcześniej, że zadaniem funkcji (get-pokemonizer) jest stworzenie funkcji pokemonizującej pojedynczy znak. Odpowiednikiem tej funkcji w C++ jest konstruktor funktora Pokemonizer. Jest jednak zasadnicza różnica między funkcjami C++ i Common Lispu – w tym drugim języku funkcję są tzw. obiektami first-class. Oznacza to między innymi, że taką funkcję można przechowywać w zmiennej, przypisywać i zwracać z innych funkcji. Dlatego nasz generator pokemonizerów po prostu zwraca funkcję. Innymi słowy, funkcje w Lispie posiadają te cechy, które w C++ musimy symulować za pomocą obiektów funkcyjnych.

Pozostaje jeszcze powiedzieć, w jaki sposób osadzamy stan w naszej funkcji pokemonizującej. W Lispie możemy zastosować tak zwane domknięcia. Jest to bardzo interesująca technika programistyczna. Zauważmy, że przed stworzeniem samej funkcji pokemonizującej (wyrażenie (lambda ...) definiujemy zmienną ((let ((upkemonize nil)) ...). Mówiąc językiem C++, nasza anonimowa funkcja znajduje się w zakresie zmiennej upkemonize. Co więcej, ona korzysta z tej zmiennej.

Powtórzę jeszcze raz – anonimowa funkcja, która ma zaraz zostać zwrócona z generatora używa zmiennej, która została stworzona w tym generatorze w momencie jego wywołania. upkemonize to zwykła zmienna lokalna. Nowy pokemonizer pracuje na obiekcie, który – według C++’owej intuicji – przestał istnieć tak szybko, jak tylko swoje działanie skończył generator. To może być lekko mind-blowing na początku. Dla mnie było.

Ilekroć generator zostanie wywołany, powstanie nowa zmienna upkemonize, która na stałe zostanie związana ze zwróconym pokemonizerem. Ten ostatni trzyma w niej swój stan; z jego punktu widzenia ta zmienna jest zewnętrzna, ‘globalna’. Taką technikę programistyczną nazywamy domknięciem – funkcja “domyka się” nad zmienną zadeklarowaną na zewnątrz niej.

Kilka wniosków, które wynikają z powyższych rozważań:

  • Funkcje wyższego rzędu są bardzo eleganckim sposobem krótkiego zapisywania algorytmów dotyczących całego zbioru danych. Zamiast ręcznie pisać pętle kopiujące, zmieniające czy dzielące duże grupy danych możemy użyć funkcji przyjmujących funkcje jako parametr, by w jednym wyrażeniu zapisać nasze rozwiązanie. W C++ spotykamy się z nimi często w STLu.
  • Funktory to sposób emulacji mechanizmu funkcji jako obiektów first-class – czyli czegoś, co jest fundamentalną właściwością Lispu. Możliwość traktowania funkcji jak każdego innego typu danych jest bardzo przydatna.
  • Common Lisp zawiera mnóstwo cech, które w C++ wymagają strasznego kombinowania – funkcje jako obiekty first-class, wyrażenia Lambda** i domknięcia to tylko niektóre z nich.
  • Można pisać bardzo, bardzo długie elaboraty o prostych problemach ;)

* – Ściślej mówiąc, C++ tylko sprytnie emuluje funkcje wyższego rzędu – taka funkcjonalność nie jest wbudowana w język.
** – Wyrażenia Lambda, czyli tworzenie funkcji anonimowych, są elementem nowego standardu języka C++ o nazwie roboczej C++0x.

COS – C Object System

Tuesday, April 13th, 2010

Piotr Matuszkiewicz znalazł ostatnio link do dokumentu opisującego bibliotekę COS. Projekt C Object System aktualnie rozwijany jest na SourceForge dzięki Laurentowi Deniau, pracownikowi CERN. Cytując wypowiedź Pawła Laska na kanale #lisp, “this is, IMHO, awesome case of CLOS being translated to C”.

Opis dokumentu (a zarazem biblioteki) głosi:

The C Object System (Cos) is a small C library which implements high-level concepts available in Clos, Objc and other object-oriented programming languages: uniform object model (class, meta-class and property-metaclass), generic functions, multi-methods, delegation, properties, exceptions, contracts and closures.

Oparta o Common Lisp Object System architektura COS’a pozwala nam więc używać technik obiektowych daleko wykraczających poza te zaimplementowane w C++ czy Javie.

Poniżej zamieszczam kodu oparty o jeden z przykładów w bibliotece, deklarujący klasę string z metodami do jej tworzenia i usuwania. Widać wyraźnie wpływy CLOS’u.

defclass(File, Stream)
  FILE *file;
endclass

/* ... */

makclass(String);

defmethod(OBJ, ginitWithStr, String, (STR)str)
  useclass(ExBadAlloc);

  self->str = strdup(str);
  if (!self->str)
    THROW(ExBadAlloc);
 
  retmethod(_1);
endmethod

defmethod(OBJ, gdeinit, String)
  free(self->str);
  retmethod(_1);
endmethod

Makra w Lispie – mały przykład

Sunday, April 4th, 2010

Czasem słyszę pytania o to, co takiego ciekawego i przydatnego jest w Lispie. Niech ten post będzie pierwszym, małym przykładem mocy tego języka.

Wyobraźmy sobie, że pracujemy ze skanerem do kodu źródłowego. To takie małe ustrojstwo, które czyta wyrażenie typu: x = a+3; i rozpoznaje składowe: identyfikator, operator=, identyfikator, operator+, liczba. W szczególności chcemy podać do tego skanera własne słowa kluczowe. Autorzy skanera przygotowali do tego specjalną funkcję:

(add-special-identifier (&key identifier string))

Funkcja przyjmuje dwa argumenty – identyfikator, jakim chcemy nazywać nasze słowo kluczowe w kodzie oraz string ze słowem kluczowym. Przykładowo, gdybyśmy chcieli skanować kod języka Ada, moglibyśmy dodać następujące słowo kluczowe:

(add-special-identifier :identifier :begin :string "begin")

Od teraz kiedy skaner rozpozna słowo kluczowe begin w analizowanym pliku, my dostaniemy token o identyfikatorze :begin.
Wszystko wygląda super; zaczynamy dodawać kolejne słowa kluczowe:

(add-special-identifier :identifier :end :string "end")
(add-special-identifier :identifier :if :string "if")
(add-special-identifier :identifier :loop :string "loop")
; ...

Programistę uczulonego na powtarzanie się może zacząć powoli denerwować, że przekazujemy dwa nazwane argumenty do funkcji, chociaż de-facto wyglądają one tak samo – identyfikator nosi taką samą nazwę jak słowo kluczowe. Pytanie, czy nie dałoby podać tego identyfikatora tylko raz?

Oczywiście da się. Możemy napisać funkcję, która nas wyręczy w pisaniu. Ale w Lispie możemy też poprosić kompilator, żeby wygenerował odpowiedni kod za nas. Napiszmy makro:

(defmacro add-keyword (what)
  `(add-special-identifier :identifier ,what :string ,(string what)))

Teraz słowa kluczowe możemy dodawać tak:

(add-keyword :begin)
(add-keyword :end)
; ...

Prawda, że mniej pisania? :) .

Nie wchodząc w szczegóły, w powyższej definicji makra rzeczy poprzedzone znaczkiem ` zostaną wstawione bezpośrednio do kodu źródłowego, a wewnątrz nich rzeczy poprzedzone znaczkiem , zostaną obliczone w czasie kompilacji (dokładniej w tzw. fazie ekspansji makr), a w kodzie znajdzie się wartość tych obliczeń. Przykładowo, wyraźenie ,(string what) w czasie kompilacji zamieni identyfikator na odpowiadający mu string. Powyższe linijki rozwiną się więc do:

(add-special-identifier :identifier :begin:string "BEGIN")
(add-special-identifier :identifier :end :string "END")
; ...

Ładny mi bajer…, ktoś powie – Przecież preprocesor w C też coś takiego umie!.
Tak, to prawda – nasze makro jedynie “rozmnożyło” ten sam argument przekazywany do funkcji w dość prosty sposób. Ale – wracając do problemu – wciąż piszemy ręcznie wywołania funkcji dodających pojedyncze słowo kluczowe. Takie wypisywanie wywołań funkcji nie jest do końca tym samym, co zadeklarowanie: chcę dodać następujące słowa kluczowe: …. Dużo lepiej byłoby móc po prostu napisać:

(add-keywords :abort :abs :abstract :accept :access :aliased :all :array :at :begin :body :case :constant :declare :delay :delta :digits :do
          :else :elsif :end :entry :exception :exit :for :function :generic :goto :if :in :interface :is :limited :loop :mod :new
          :not :null :of :or :others :out :overriding :package :pragma :private :procedure :protected :raise :range :record :rem :renames
          :requeue :return :reverse :select :separate :subtype :synchronized :tagged :task :terminate :then :type :until :use :when :while :with :xor)

i za jednym zamachem zdefiniować wszystkie słowa kluczowe Ady ;) . Znów, możemy napisać funkcję, która w pętli wywoła dodawanie słowa kluczowego, ale pisanie takiej pętli za każdym razem, gdy chcemy dodać nowe rzeczy nie jest tym samym, co powiedzenie: chcę dodać następujące słowa: …. Poza tym, dlaczego to kompilator nie mógłby tego wszystkiego zrobić za nas?…

… Otóż może. Oto definicja makra add-keywords:

(defmacro add-keywords (&rest keyword-list)
  `(progn
     ,@(loop for word in keyword-list collect `(add-keyword ,word))))

Bez wchodzenia w szczegóły – bo nie to jest celem tego wpisu. Powyższe makro wykona w czasie kompilacji pętlę po wszystkich swoich argumentach, która zwróci w formie listy wyrażenia (add-keyword ,word), a które – jak pamiętamy – same są makrami, i chwilę później zostaną rozwinięte w wywołania naszej skomplikowanej funkcji dodającej słowa kluczowe do skanera. Mając takie dwa makra, pojedyncze wywołanie dodające wszystkie słowa kluczowe zostanie w czasie kompilacji rozbite na odpowiednie wywołania funkcji zaprezentowanej na początku. Zamieniliśmy dużo wpisanych ręcznie pojedynczych wywołań funkcji na dwa makra i jedno wywołanie! Tego już tak łatwo w C nie zrobimy :) .

Ten mały i stosunkowo prosty przykład makr Lispu miał pokazać ważną cechę tego języka – ponieważ można w nim wykonać dowolny kod w czasie kompilacji i przerabiać w ten sposób sam kompilowany kod, to można łatwo rozszerzać język i dopasowywać go do rozwiązywanego problemu. Dwoma prostymi makrami stworzyliśmy narzędzie dodające hurtem słowa kluczowe. A to już doskonale odpowiada wyrażeniu: Chcę dodać te słowa: ….

Dwa słowa na koniec. Windowsowej binarki do ClozeCall na razie nie będzie – mam na razie z tym małe problemy :) . Ale każdy, kto ma u siebie zainstalowaną implementację Common Lisp, może sobie pograć :) .

2010 Lisp Game Design Challenge – końcówka

Thursday, April 1st, 2010

Konkurs 2010 Lisp Game Design Challenge, o którym niedawno pisałem, powoli dobiega końca. Ostatni zawodnicy kończą swoje prace; część z nich jest już dostępna do pogrania. Nie miałem jak dotąd czasu zagrać w żadną z nich, gdyż… przed chwilą skończyłem swoją własną. Mój projekt, zatytułowany Cloze Call (od Clozure Common Lisp, na którym pracowałem), jest już dostępny do pobrania w formie źródeł i zasobów (dla osób umiejących obsłużyć implementację Lispa) na stronie Google Project Hosting. Postaram się niedługo przygotować paczkę i binarki dla użytkowników Windowsa. Na razie pozwolę sobie zaprezentować screen z gry:

Cloze Call - screen z rozgrywki

Wahałem się, czy wziąć udział w konkursie – przecież i tak jest sporo innych rzeczy na głowie. Teraz stwierdzam, że było warto. W czasie prac nad grą nauczyłem się bardzo wielu rzeczy o Lispie. I zaprzyjaźniłem się z Emacsem :) .

2010 Lisp Game Design Challenge

Saturday, March 20th, 2010

2010 Lisp Game Design Challenge banner

Przedwczoraj wystartował konkurs 2010 Lisp Game Design Challenge. Zasady są bardzo proste – wystarczy zadeklarować termin startu, wziąć swojego ulubionego Lispa i zacząć klepać :) . Zapisy i dodatkowe informacje znajdują się na stronie głównej oraz stronie rejestracji.

Osobiście poważnie zastanawiam się jeszcze nad wzięciem udziału. Jedynym sensownym terminem startu byłby 24 lub 25 marca. Pomimo tego, że uczelnia przyciska to jednak konkurs ten jest bardzo kuszącą propozycją :) .