Archive

Archive for the ‘Computer science and math’ Category

Matrix chain multiplication: parallel and sequential

June 25th, 2009 No comments

Yep, that’s the project that uses threads. Nothing more is worth to add — the problem is well-known, as well as the algorithm.

Source: http://www.srednikpe.org/src/matrix/

C++ hidden feature

June 22nd, 2009 1 comment

This is one I didn’t know. Conditional expressions in C++ can be lvalue:

(a == 0 ? a : b) = 42;

More hidden features: http://beerpla.net/2009/06/21/hidden-features-of-perl-php-javascript-c-c-c-java-ruby-python-and-others-collection-of-incredibly-useful-lists/

boost::thread and std::list

June 22nd, 2009 4 comments

I had to create many threads in C++. Of course I didn’t want to use pthread, because it’s ugly C. I chose boost::thread instead. Then I needed some container to keep all these threads. Arrays were out of the question for the same reason as pthread. I could use boost:array but stl::list was easier.

The problem was—how to keep this thread objects? I couldn’t use std::list<boost::thread> nor std::list<boost::thread &> because threads cannot be copied. I had to dynamically create the object in order to prevent the destruction after the scope. But for some reason I got compiler error while trying std::list< std::auto_ptr<boost::thread> > in the line where I pushed_back newly created threads.

The cause of the error was that the argument of std::list::push_back() was a constant reference. And while assinging one auto_ptr to another, the first one is getting call release() method, but it can’t since the reference is constant and release() change the state of the object.

To solve this problem one can use boost::shared_ptr.

Example:

#include <iostream>
#include <list>
#include <boost/thread.hpp>
#include <boost/date_time.hpp>
#include <boost/smart_ptr.hpp>
 
using std::list;
using std::cout;
using std::endl;
 
struct foo
{
	void operator() (int id)
	{
		cout << "starting thread " << id << '\n';
		boost::this_thread::sleep(boost::posix_time::seconds(3));
		cout << "ending thread " << id << '\n';
	}
};
 
int main()
{
	typedef boost::shared_ptr<boost::thread> thread_ptr;
	list<thread_ptr> thread;
 
	cout << "creating threads\n";
 
	for (int i = 0; i < 10; ++i)
	{
		thread.push_back(boost::shared_ptr<boost::thread>(new boost::thread(foo(), i)));
	}
 
	cout << "after creation, now joining them\n";
 
	for (list<thread_ptr>::iterator it = thread.begin(); it != thread.end(); ++it)
	{
		(*it)->join();
	}
 
	cout << "ending program" << endl;
 
	return 0;
}

And the result:

tomek@notlob:~% g++ -o threads threads.cpp -O2 -Wall -lboost_thread-mt
tomek@notlob:~% ./threads
creating threads
starting thread 1
starting thread 0
starting thread 2
starting thread 3
starting thread starting thread 4
5
starting thread 6
starting thread 7
starting thread 8
starting thread 9
after creation, now joining them
ending thread 1
ending thread 3
ending thread 5
ending thread 4
ending thread 0
ending thread 2
ending thread 6
ending thread 8
ending thread 7
ending thread 9
ending program

How not to name variables

June 13th, 2009 No comments

This is is a Python line of code which I found in my project I work with two colleagues:

for mid, mda, xmht, xmat, mhs, mas, mehs, meas, mphs, mpas, mrou in q:
    # ....

No comments.

Semantyka gier

February 9th, 2009 No comments

Krótki wstęp do semantyki gier, który przygotowałem w ramach projektu końcowego z Semantyk Języków Programowania.

prezentacja, notatki

Update: notatki pozostałych studentów.

Programowanie literackie

January 10th, 2009 No comments

Ostatnio miałem ponowną styczność z TeX-em, tym razem konkretnie z Beamerem (całkiem fajne narzędzie do tworzenia ładnych i profesjonalnych prezentacji; być może wrzucę tę, którą zrobiłem na zajęcia). Jest to jeden z programów, które są owiane dla mnie lekką tajemnicą… Już sam fakt że został napisany przez legendarnego Donalda Knutha, powoduje bojaźn i trwogę podczas używania. No dobra, przesadzam, ale TeX to program wyjątkowy. Nie dlatego, że jest bezbłędny (ma już ze 30 lat chyba, a ostatni błąd wykryto w nim kilkanaście lat temu), ale dlatego, że jest napisany… literacko.

Donald Knuth napisał książkę-program pod tytułem TeX: The Program (ISBN: 0201134373). Następnie (a może uprzednio?) napisał narzędzie, które nazwał WEB. WEB pozwalał mu automatycznie skonwertować książkę-program do poprawnego programu w Pascalu (w tamtych czasach był to bardzo popularny język), który po skompilowaniu robił to, co opisano w książkoprogramie. Oprócz tego, pozwalał też wygenerować… książkę. Z nagłówkami, sekcjami, stronami — ot, PDF lub PostScript, nadający się do wydrukowania.

Książkoprogram to tak naprawdę dokumentacja i kod w jednym. Programista pisze na przemian kod i tekst. Może przy pisaniu kodu korzystać ze wszystkich dobrodziejstw TeX-a do opisywania swojego kodu, tworzyć odnośniki do innych fragmentów kodu, etc. Lepiej to zobaczyć na przykładzie: kwadrat.w. Użyłem wesji WEB dla C/C++, która nazywa się CWEB. Aby otrzymać program C, wystarczy polecnie:

$ ctangle kwadrat
This is CTANGLE, Version 3.64 (Web2C 7.5.6)
 
Writing the output file (kwadrat.c):
Done.
(No errors were found.)
$ gcc -o kwadrat kwadrat.c -lm
$ ./kwadrat
Podaj a: 1
Podaj b: 10
Podaj c: 5
x = -9.472136
x = -0.527864

Aby otrzymać dokument TeX-a, należy napisać:

$ cweave kwadrat
This is CWEAVE, Version 3.64 (Web2C 7.5.6)
 
Writing the output file...
Writing the index...
Done.
(No errors were found.)
$ pdftex kwadrat.tex
This is pdfTeXk, Version 3.141592-1.40.3 (Web2C 7.5.6)
(...)
Output written on kwadrat.pdf (3 pages, 63651 bytes).
Transcript written on kwadrat.log.

Oto wygenerowane pliki: kwadrat.tex, kwadrat.pdf i kwadrat.c. Niestety nie wiem jak zmusić czystego TeX-a do poprawnego czytania UTF-8, dlatego w PDF-ie nie ma polskich liter.

Szczerze mówiąc nie mam zdania na temat literate programming. Jeśli ktoś lubi tak pisać, to proszę bardzo — całkiem przyjemnie się czyta taki dokument. Jednak ja nie lubię się rozpisywać nad kodem, dla mnie sam kod (z komentarzami) stanowi wystarczającą dokumentację. ;)

Warto jeszcze dodać, że wsparcie dla literate programming jest zaimplementowane w Haskellu. Ale to już lepiej poczytać na Haskell Wiki.

Program verification conditions

December 22nd, 2008 No comments

Yay, another parser in Haskell! That was a Haskell week, but I’m glad I had an opportunity to recall this beautiful full-of-math language.

This program reads an annotated program — a program with assertions. Assertions are just logic formulas. We use them to describe the program state between instructions, ie. variable x is equal to variable y squared. But assertions cannot be random, they must be derived from Hoare’s logic axioms and rules (which base on the formal semantic of the language). How do we know if there is an derivation of a program?

Here verification condicitions come. They are logic formulas too, but generated from annotated program. If all of them are true, then the program is derivable. More information here: http://www.macs.hw.ac.uk/~air/hic-hisd/ and http://www.daimi.au.dk/~bra8130/Wiley_book/wiley.html. The whole point is about formal verification of programs. Nowadays compiler can tell only whether given program has a syntax or type error. It doesn’t know anything about how this program should work and can’t say something like: “This program certainly does not multiply matrices.”. Assertions are some way to tell the programmer’s intentions to the compiler: “This is my piece of code and it should multiply two matrices”, and thus, by generating verification conditions and using automated theorem proving it could say: “It does.”.

So after a boring digression… this program reads an annotated program in a simple imperative language and generates verification conditions. That’s all.

All files are here: http://srednikpe.org/src/vc/

Reverse Polish notation calculator in Haskell

December 22nd, 2008 6 comments

Just a few lines of code, written when I was slightly bored.

module Main where
 
data Token = Plus | Minus | Divide | Times | Num Integer
 
rpnEval :: [Token] -> Integer
rpnEval = rpnEval' [] where
		rpnEval' (i:s) [] = i
		rpnEval' s ((Num i):t) = rpnEval' (i:s) t
		rpnEval' (a:b:s) (op:t) = rpnEval' ((evalOp op a b):s) t
 
		evalOp Plus = (+)
		evalOp Minus = (-)
		evalOp Times = (*)
		evalOp Divide = div
 
toToken :: String -> Token
toToken "+" = Plus
toToken "-" = Minus
toToken "*" = Times
toToken "/" = Divide
toToken s = Num (read s)
 
main = do
	l <- getContents
	mapM print $ map (rpnEval . (map toToken) . words) (lines l)

Update: See comments for better solution.

Kości

August 30th, 2008 3 comments

Nie mieliśmy kości na sesję, to trzeba było coś napisać. NWOD-owy rzucacz kośćmi w Pythonie:

#!/usr/bin/python
 
import time
import random
import sys
 
# argumenty: 
ile_scian = int(sys.argv[1])    # ilusciennymi koscmi rzucamy
sukces = int(sys.argv[2])       # od ilu oczek jest sukces
ile_rzutow = int(sys.argv[3])   # ile razy rzucamy
 
def kostka(sciany):
    rzut = random.randint(1, sciany)
    print rzut
    return rzut
 
print '------------------------------'
 
random.seed()
 
sukcesy = 0
 
for i in range(0, ile_rzutow):
    rzut = kostka(ile_scian)
 
    if rzut >= sukces:
        sukcesy += 1
 
    while rzut == ile_scian:
        print 'Przerzut!'
 
        rzut = kostka(ile_scian)
 
        if rzut >= sukces:
            sukcesy += 1
 
print
print "Sukcesy: ", sukcesy

gdb

August 30th, 2008 2 comments

Debuggowanie potrafi niemal wykładniczo skrócić czas szukania błędów w programie, więc warto nauczyć się sprawnie obsługiwać debugger. Dotychczas GNU Debugger był dla mnie czarną magią, a wzorem — ten  z Visual Studio. Tylko gdzieś słyszałem/czytałem, że gdb ma takie same możliwości, ale nie dane mi było się o tym przekonać. Niedawno musiałem się nauczyć jego obsługi, dlatego napiszę sobie ściągawkę (nie, żeby z niej korzystać, ale żeby utrwalić).

Zanim zaczniesz

Musisz najpierw skompilować program z informacjami dla gdb. Robi opcja -g dla gcc.

Komendy

Zamiast miłego interfejsu graficznego, jest miły wiersz poleceń (co dla programisty jest wygodniejsze, bo nie musi odrywać rąk od klawiatury :>), w którym wpisujesz polecenia. Nie musisz podawać jej pełnej nazwy, wystarczy jednoznaczny początek (najczęstsze polecenia mają jedno/dwuliterowe synonimy). Działa dopełnienie tabulatorem! W razie czego: help komenda.

Start

Pierwszy paremtr to nazwa pliku wynikowego programu. Drugim może być numer procesu tego programu, jeśli chcesz zacząć debuggować już działający program.

Przydatne komendy:

  • run [argumenty] –  uruchamia program z podanymi (opcjonalnymi) argumentami
  • continue – jeśli program jest zatrzymany, wznawia jego działanie
  • finish – program się wykonuje aż do napotkania “return”; innymi słowy program działa aż do końca aktualnej ramki stosu

Stop

Żeby się gdzieś zatrzymać, trzeba ustawić breakpointy:

  • breakpoint funkcja – ustala breakpoint na początek funkcji
  • breakpoint [plik:]linia – ustala breakpoint na określoną linię pliku
  • info breakpoints – wypisuje utawione breakpointy
  • delete n – usuwa n-ty breakpoint
  • condition n cond – ustala warunek dla n-tego breakpointa (program zatrzyma się na nim, jeśli zostanie spełniony warunek cond)
  • ^C - czyli przerwanie z klawiatury, również zatrzymuje działający program i oddaje kontrolę gdb

Co się dzieje?

Kilka przydatnych komend, aby zorientować się, co się aktualnie dzieje:

  • list – listing kodu (10 linii obecnego kontekstu, podana nazwa funkcji, numer linii, etc.)
  • frame – aktualna ramka stosu oraz aktualna instrukcja
  • backtrace – ślad stosu
  • print x – wypisanie wartości x (to może być dowolne wyrażenie, razem ze zmiennymi w programie)

Tropimy

To, co najważniejsze, czyli śledzimy program krok po kroku:

  • next – następna instrukcja (lub n instrukcji), bez wchodzenia wgłąb procedur
  • step – j/w, ale z wchodzeniem wgłąb

Psujemy

Można przetestować kilka rzeczy w trakcie trwania programu:

  • set x wartość – ustawiamy zmiennej x wartość
  • call f(x) – wywołujemy funkcję f z argumentami (w tym wypadku tylko x)

Format zapisu zmiennych, funkcji i adresów.

Czasem chcemy się odwołać do zmiennej z jakiegoś innego zakresu albo funkcji składowej, wtedy piszemy zakres::x, jeśli np. zakres jest klasą, a x jej metodą/polem, albo zakres jest funkcją, a x jej zmienną lokalną. Odwołanie do konkretnej linii ma składnię plik:linia, np. test.c:244. Adres zapisujemy z gwiazdką na początku, np. *0×000000.

A na koniec: quit. I tyle. To było zaledwie 1/5 możliwości gdb, mimo to spokojnie wystarczy do efektywnego debuggowania. Chociaż dziesiątki printfów mają swój urok. ;)