Rambling Thoughts

Internet connecting the wrong masses

noreply@blogger.com (Usuldan) — Fri, 11 Nov 2016 19:22:00 +0000

I used to think that the Internet will serve as a major facilitator for the advancement of free thought and civil liberties. I thought that being able to connect to other people and access to information from across the globe will provide an opportunity to learn about new and progressive ideas, raise awareness of different cultures, and develop an appreciation of how different yet so alike we are as human beings. How naive, how wrong I was!

In my defense, human history presents a constant progress. There are of course some discontinuities in this progress. Up until now, I never felt like my time on this planet was overlapping with one. With all that has happened lately in my home country and given the latest events in the US, I am now convinced that we are witnessing a global regression in human progress. I feel unlucky to be witnessing this. It is quite distressing, especially given how short our lifetimes really are. This is how people must have felt during other tragic times, such as the rise of fascism in Europe before WWII.

This regression is hard to accept, as I tend to think that the new is always better. However, in order for the new generations to reach their full potential, we must leave them a world better than the one we inherited. I'm saddened to see that this may not be at all possible in our case. I hope I am wrong. Perhaps you are thinking that this assessment is highly exaggerated. Yet, the things that are happening in my home country are out of the pages of George Orwell's 1984. You may wake up tomorrow and read on the news that the sky is not blue but red, and whoever claims it is blue would be jailed. Of course what's happening here cannot be used to draw such a bleak picture for the world. Nevertheless, if the US, considered to be the leader of the free world, can elect a racist con artist who has no respect for science and reason as their president, then what else?

I am starting to think that the Internet and the social media have caused all this. The average person suffers from confirmation bias. They use the social media to find more ideas like theirs and connect to people who think like themselves. This will further strengthen their often incorrect convictions. Intellectual people will of course use the Internet for broadening their perspectives. These intellectuals, such as scientists, artists, thought leaders, etc., are people who were already connected even before the Internet era. They always had communities enabling them to keep connected. The conservative masses, on the other hand, did not know about each other. With the advent of the Internet and the social media, now these masses are getting connected and becoming even more conservative. I believe that the Internet has become a bigger booster for conservatism, than for liberal thought.

If the Internet is not going to promote a culture of tolerance, free thought, and personal freedom, then what will? I believe the answer is mobility. Visiting foreign places, meeting people from other cultures, and sharing experiences with them. Obviously this is not easy. I live in a country where a large portion of the population is anti-Semitic, yet never had a single Jew friend; homophobic yet never had a gay or lesbian friend; and even xenophobic yet never even met a foreigner.

Скопје & Prizren

noreply@blogger.com (Usuldan) — Mon, 28 Oct 2013 08:20:00 +0000

We decided to take some time off this year during the Feast of the Sacrifice holiday in Turkey. Republic of Macedonia does not require a visa from us, so we took a 3-day trip there, with the aim of visiting the neighboring Kosovo as well. Given the limited time, we planned to see three cities: Skopje and Tetovo in Macedonia, and Prizren in Kosovo.

Skopje, which we call Üsküp in Turkish, is the capital of the Republic of Macedonia. It is written as Скопје in Macedonian using the Cyril alphabet. The city has been settled since Neolithic times. It came under the control of the Roman Empire, later changed hands between the Byzantine Empire and the Bulgarian Empire, served as the capital of the Serbian Empire, and in 1392, it was conquered by the Ottoman Empire and served as the capital of the Kosova Province until 1912. It is noteworthy that Skopje became part of the Ottomon Empire almost 60 years before İstanbul was conquered. It was under Ottoman control for more than 500 years. It has been part of Yugoslavia until Republic of Macedonia separated from Yugoslavia in 1991.

From Turkey, you can fly to Skopje via İstanbul. The flight takes around 1 hour and 20 minutes. Skopje has an international airport called Alexandre the Great Airport. Despite the name, the airport is humble in size. The naming of the airport, and more importantly, the naming of the country itself is rather controversial. The ancient Kingdom of Macedonia was of Greek origin and centered around the current day city of Thessaloniki (Selanik in Turkish) in the Region of Macedonia within Greece. The famous leader and military commander Alexandre the Great, who lived around 350 BC, is from ancient Macedonia. The Greeks are quite opposed to the name of the current day Republic of Macedonia, as it is geographically located on the northern parts of the ancient Macedonia and ethnically current day Macedonians are a different group of people than the ancient Macedons. My understanding is that Macedonians might have historic ties to the ancient Macedons, but they came under heavy influence of Slavs. As a result, they are more of a Slavic ethnic group today. They speak a Slavic language as well. I personally find it strange that they want to own the ancient Macedon figures like Alexandre the Great and Philip II. Apparently that really upsets the Greeks, who consider these figures as part of their history. Due to the naming controversy, today you might see the words FYROM in some maps, which means The Former Yugoslavian Republic of Macedonia, which is the official UN name due to Greece's protests over the name Republic of Macedonia.

Skopje, the capital of Macedonia, is a city that houses half a million people. Macedonians constitute 65% of the population, whereas Albanians form 25%-30%. There is ~4% Turkish population, and ~3%of Romanis (Gypsies). Close to two thirds of the population is Christians (mostly Macedonian) and one third is Muslims. There does not seem to be any religious tensions. You can see both churches and mosques around. Call for prayers are heard five times a day. The official language is Macedonian in Macedonia, but in places where there is a sizable Albanian population, Albanian Language, written using the Latin alphabet, is co-official, as in Skopje. The money used in Macedonia is Macedonian Denar. In Skopje, some places also take Euros.

Stone bridge in downtown Skopje

From the airport, we take a taxi to the city center of Skopje. It is around 20kms from the airport. As we enter the city, it surprises us to see so many Halkbank branches and ads. Halkbank is a Turkish bank. We check-in at a hotel close to the main square in the city center, aptly named the Square Hotel. The hotel is at the 6th floor of a building. Doesn't look too promising from outside, but it is clean and tidy inside. The Vardar River passes through downtown Skopje. The city is under construction. There was a big earthquake in 1963 in Skopje, which has destroyed the city and it seems the city is truly recovering from that destruction only now. Macedonia is a candidate country for the European Union and with support from the EU, they have started a downtown renewal project. As part of this effort many new buildings and statues are being built.

Warrior on a Horse

However, we feel that the statue thing is a little overdone. There are too many of them and at weird places as well. Some of them are nicely placed though. One such example is the Alexandre the Great statue shown on the left, which is the central attraction in the main square. It is best viewed from the old bridge, as it is placed quite high. From up close, you are more likely to see the underbelly of the horse, rather than the Alexandre sitting on top of it. The funny thing is, Macedonians are not allowed to name this statue as Alexandre the Great, due to the longstanding naming dispute with Greece. As a result, it is named Warrior on a Horse. On the other side of the old bridge, there is another statute, this time of Philip II, standing up with his fist pointed in the air. Again, it cannot be named Philip II, and instead it is named The Warrior. There is also a triumphal arch, again built as part of the renewal project. It is said that the nationalist government has spent more than 200 million for this effort so far, which is striking considering the rather poor country. The unemployment rate is as high as 35%, which is frighteningly high. If you walk a little outside of downtown, you can start seeing graffiti over unkempt and rundown buildings.

Kale Fortress

Across the bridge, you can find the old city, where the Ottoman impact is highly visible. There are Ottoman mosques, such as the Mustafa Pasha Mosque, Hamams, Inns, and a Bazaar. Also on that side of the river, located on top of a hill and overlooking the city center is the Fortress of Skopje, called the Kale Fortress. Kale is the Turkish word for Fortress. So it is the fortress fortress :). The fortress was originally built by the Byzantine emperor Justinian I, but has been partially reconstructed many times. With the lighting at night, it looks very impressive, as seen on the right. The old city has many stores and restaurants with Turkish names and it is easy to find local folks who can speak Turkish. For lunch we had meatballs at a restaurant, and two of the waiters knew Turkish. In fact, one of them was a local Turk.

The next day we took a bus to neighboring Kosovo. The two important cities in Kosovo are Prishtine, the capital, and Prizren. We decided to visit Prizren, as the Turkish connection is stronger there. For those who do not know, Kosovo is a country. However, it is not internationally recognized. Among many who recognize it are the USA and Turkey. It was separated from Yugoslavia as a result of the Kosovo War in 1999, which was fought by the Kosovo Liberation Army with aerial bombardment support from NATO. Turkey has participated in the NATO operations as well. Almost a decade after the war, it declared its independence from Serbia in 2008. However, Serbia still does not recognize Kosovo and has territorial claims on it. Today Albanians form around 90% of the population in Kosovo. Serbian forces have committed war crimes during the war and many Serbians have left during or after the war due to the resulting ethnic conflict. Kosovo is not part of EU yet, given its mixed status as an independent country. But there is a EU mission in Kosovo providing rule of law, such as police officers, prosecutors, and judges. The euro is the official currency in Kosovo.

Namazgah where Fatih has prayed

Prizren is located on the slopes of the Sar Mountains and the road from Skopje to Prizren has nice views. It takes around 3 hours by bus, but half an hour of that is spent waiting for the passport control on the Macedonia-Kosovo border. Prizren is a very attractive little city, full of history. Perhaps the right description for it is 'boutique'. As we leave the bus station, on the other side of the street, we find the Namazgah. This is the place where Fatih Sultan Mehmed has stopped to pray when Prizren was conquered by the Ottoman Empire in 1455, that is 2 years after the Fall of Constantinople. The remains from the Namazgah are partially restored, as seen on the left. It does not look pretty, but it does have historical significance for us.

Stone bridge over the Bistrica

The city houses less than 200 thousand people, which are predominantly Muslim Albanians. There is also a Turkish minority, which seems quite active in the political scene. Turkish is a co-official language in Prizren, Albanian being the main language spoken by the population. Everyone seem to know a little Turkish though. They speak it with a cute accent, somewhat resembling the Black Sea coast accent from Turkey. Bistrica river passes through the city. On the right, you can see an old stone bridge over the river. You can walk along both sides of the river and pass through nice little cafes, restaurants and other local stores. The city is quite lively. Historical sites are very well preserved. The city is very clean and tidy.

As you walk along the river towards the city center, you can catch the view of the Fortress of Prizren, which is located on a hill overlooking the city center. The fortress was built by the Byzantines, was expanded by Serbians, and was given its final shape by the Ottomans. Unfortunately, we did not have the chance to climb the fortress to get a view of the city from up there, because it started to rain heavily an hour after we reached Prizren.

In the city center, you can find the town square, which is called the Shadervan, meaning Fountain in Turkish. There is indeed a fountain in the middle of the town square. The square hosts many small restaurants. We had lunch in one of them. The cabbage salad and the thin sliced beef steak were delicious. Located next to the town square is the Sinan Pasha Mosque, built in 1615. There is also a Hamam close to the city center. There are also Eastern Orthodox Churches. One of them is the Our Lady of Ljevis Church, which we saw from outside, but were not allowed to get in or take pictures. It seems many churches were burned during the ethnic clashes and even today there is animosity against Serbians and thus against the Churches. We hang around the cafes at night, stayed at a very central hotel close to the main square, and took the bus next morning back to Skopje. Before boarding the bus, we tasted local Böreks at a pastry store. Böreks are filled pastries made of a thin flaky dough (known as phyllo in the US). They were delicious.

As soon as we arrived in Skopje, we took a bus to the nearby city of Tetovo. During the Ottoman times, this place was named Kalkandelen. The city is the political capital of the Albanian minority within the country and Albanians form the relative majority here. In 2001, there was a minor civil war within Macedonia, and Tetovo played a central role during that time. The conflict was resolved by granting more rights and better representation to the Albanian minority. An example is the right to have universities that teach in the Albanian language.

Painted Mosque

The Pena river passes through the city and you can find an Ottoman Hamam next to it as you walk towards the city center. You can also find, located very centrally, the Painted Mosque. This mosque, shown on the right, was originally built in 1438, and later reconstructed in 1833. The mosque is unique because it does not follow the traditional Ottoman architecture. It has floral paintings. Inside the mosque, under the dome, you can see panoramic drawings of trees, plants, and buildings. This is the first time we see an interior mosque decoration like that. From the outside, it also looks interesting. The back side of it looks as if it is made out of playing cards :). The mosque has a nice small courtyard, which also houses an Ottoman mausoleum (called a Türbe), which houses the tombs of the financers of the mosque. Tetovo also houses an Ottoman fortress overlooking the city and a historical Bektashi Tekke, that is a Bektashi Dervish Lodge.

We had a nice dinner in Tetovo and returned back to Skopje at night. There was a concert in the main square which continued until midnight. Early next day, we went back to the airport for our return flight to İstanbul.

Macho Grande

noreply@blogger.com (Usuldan) — Sun, 27 Oct 2013 09:19:00 +0000

One of the most hilarious scenes from the movie "Airplane 2: The Sequel":

Unnamed crew member (witness):

Flew with Striker during the war
He never forgets the night they bombed Macho Grande
How they survived was a miracle
He won't ever get over Macho Grande, those wounds run pretty deep

Striker:

Was the squadron leader
He brought them real low, but he couldn't handle it

Buddy:

Was the bombadier
He went into pieces
It was awful how he came unglued
He bailed out

Howie:

Was a rock, best tail gunner in the outfit
They lost Howie the next day

Andy:

Was the navigator
He was alright
He hung tough

Ideal occupations

noreply@blogger.com (Usuldan) — Sun, 20 Oct 2013 18:46:00 +0000

Here are 10 occupations I wish I had pursued, in no particular order.

1. Architect: The kind that designs major buildings. Nothing is higher than architect.

2. Poet: I do this as an amateur and I think I am good at it. However, all those moments will be lost in time, like tears in the rain :)

3. Mechanical engineer: As a kid I always admired my uncle who is a top-notch mechanical engineer. If I ever win the lottery, I'll do a masters in this field.

4. Game designer and programmer: I wish I was the person who led the development of Diablo series. This is perhaps the closest to my actual occupation, but the mixture of programming, story telling, art and graphics makes game design unique.

5. Fighter jet pilot: I am afraid of heights, so this is quite far fetched. But I am fascinated by fighter jets. I used to build and paint plastic model kits of them. It seems in the near future fighter jets will be commanded from land stations. So it seems I missed this opportunity by 50 years or so.

6. Professional tennis player: I am too much of a couch potato to do a sports professionally. Tennis is the only sports activity I enjoy performing, despite enjoying watching any kind of sports on TV (I can even watch a curling game). I was a big Agassi fan back in the day. Before that I was a fan of Boris Becker. Nowadays I am more interested in female players.

7. Philosopher: I do have a doctorate of philosophy. I wish I was doing my qualified job :)

8. Singer: When I was young, I saw Joe Cocker in Unchain My Heart's video clip and was impressed. I think that is why I enjoy growing my beard. He has that rugged voice that I like. If I were to drink and smoke, I could bring my voice to that level.

9. Resistance leader (like that's a job): Not sure where this came from. The only resistance I lead today is against my inner urges...

10. Iron chef: I like cooking. I am a big fan of Iron Chef Rokusaburo Michiba from the Japanese series. What a name! Iron Chef Michiba always writes his menu in calligraphy before starting to cook. Planning is key to any activity.

Iterating visitables

noreply@blogger.com (Usuldan) — Sun, 28 Apr 2013 15:12:00 +0000

A common design pattern in programming is the 'visitor design pattern' (see here). The idea is that, the caller passes a visitor object to the callee, and the callee uses this object to make calls as it visits some internal structure that it maintains, passing the info about the visited objects as a parameter to the calls made on the visitor object.

Here is a real-world use case I run across recently: I was using a persistent R-tree library written in C++. R-tree is a tree used for indexing spatial data, such as 2-d and 3-d objects. This particular implementation provided a visitor interface, where querying the R-tree index was done by passing a visitor object to its query method. Every time a node of the tree is visited during the answering of the query, the query method makes a call to the visitor object, passing in the node being visited as a parameter.

An alternative approach, typically used with indexes like this is iteration (cursors in DB lingo). An iterator can be used to iterate through the results. In my use case, I needed to provide an iterator interface over the R-tree index. Doing this kind of adaptation requires use of non-traditional abstractions, which we will get to soon. Take a few minutes to think about a solution, and you will see that it is not at all straightforward.

Btw, I should note that the problem of providing an iterator interface on top of a visitor one is quite real, and something you can run across in real life programming, as I did. See here for a StackOverflow question about the same issue (which I tried to answer). It is also worth noting that the reverse problem of providing a visitor interface over an iterator one is trivial.

Here I will give a simple example that involves a counter to illustrate the problem. Let us first introduce abstract classes that define the concepts of visitor and visitable.

template<typename Data>

class Visitor

{

public:

  virtual ~Visitor() { }

  virtual bool visit(Data const & data) = 0;

};

template <typename Data>

class Visitable

{

public:

    virtual ~Visitable() {}

    virtual void performVisits(Visitor<Data> & visitor) = 0;

};

Let us illustrate their use with a simple counter that is visitable:

class Counter : public Visitable<int>

{

public:

    Counter(int start, int end)

        : start_(start), end_(end) {}

    void performVisits(Visitor<int> & visitor)

{

        bool terminated = false;

        for (int current=start_; !terminated && current<=end_; ++current)

            terminated = visitor.visit(current);

}

private:

    int start_;

    int end_;

};

Here, we have a Counter class that provides a Visitable interface for visiting numbers between 1 and n. Using it is rather straightforward:

class CounterVisitor : public Visitor<int>

{

public:

    bool visit(int const & data)

{

        std::cerr << data << std::endl;

        return false; // not terminated

}

};

int main(void)

{

    Counter counter(1, 100);

    CounterVisitor visitor;

    counter.performVisits(visitor);

    return EXIT_SUCCESS;

}

How can we convert this code to use iteration, rather than visitation? Let's first define the concept of an iterator:

template<typename Data>

class Iterator

{

public:

    virtual ~Iterator() {}

    virtual bool isValid()=0;

    virtual void moveToNext()=0;

    virtual Data const & getData()=0;

};

It is worth noting that I am not using STL style code here, to make the exposition more general. I am following a mainly OO approach. Here is what we want to do ideally:

int main(void)

{

    Counter counter(1, 100);

    Iterator<int> & it = magicFunction(counter);

    for (; it.isValid(); it.moveToNext()) {

        int const & data = it.getData();

        std::cerr << data << std::endl;

}

    return EXIT_SUCCESS;

}

Below are two ideas on how to achieve this, both with serious shortcomings.

Idea 1) We write a wrapper that collects all data items into a collection and then we can provide the usual iteration interfaces.

Unfortunately, this idea has a critical shortcoming. It requires space in the order of number of items visited. In some applications this is unacceptable. A good example is the R-tree example I gave earlier, where the number of query results might be too large. If the only thing you want to do is to compute some aggregate over the results, or perhaps just look at the first k of the results, this approach will be very costly in some cases. So we rule it out as a general solution.

Idea 2) Another idea is to use threads.

We can spawn a new thread that will execute the performVisits method. We can then start waiting on a conditional variable until the spawned thread signals us about a result. When a visit call is made on the spawned thread, the current data item will be saved into a shared variable, the spawned thread will signal us about the readiness of the result, and it will start waiting on another conditional variable until we signal it for the next request. This way our iterator can return the item stored in the shared variable when the getData method is called. When the moveToNext is called for the next step of the iteration, we could signal the spawned thread's conditional variable, so that it can do the next visit. Meanwhile we can wait on our conditional variable for the results. This could continue until the the visit is completed.

Unfortunately, this switching between threads is really costly if we end up doing it on a per-item basis. Alternatively, we can buffer some data items to improve performance. In general, threads are somewhat heavyweight, and also this kind of implementation is somewhat dirty. It can be made to work, however.

The second idea is actually moving us in the right direction: Threads have their own stack! So what we need is a different stack. We do not need concurrent execution, however. Instead we need alternating execution between two contexts with their own stacks. An abstraction that can provide this is 'coroutines'. See here, if you are not familiar with coroutines. Coroutines enable two functions to suspend and resume each other. That's where the name 'co' comes from. I won't describe them in detail here.

C++, being the flexible language it is, can support coroutines via a library. boost::coroutines is one such library and surprisingly it is very easy to use (assuming 'easy' can be applied to anything in boost).

Below, I will provide the code for a class that can convert a visitable into an iterator. Fasten your seatbelt:

template<typename Data>

class VisitableIterator : public Iterator<Data>

{

private:

    typedef boost::coroutines::coroutine<void()> coro_t;

    typedef coro_t::caller_type caller_t;

public:

    VisitableIterator(Visitable<Data> & visitable)

        : valid_(true), visitable_(visitable)

    {
coro_ = coro_t(boost::bind(&VisitableIterator::visitCoro, this, _1));

    }

    inline bool isValid()

    {

        return valid_;

    }

    inline Data const & getData()

    {

        return visitor_.getData();

    }

    inline void moveToNext()

    {

        if(valid_)
coro_();

    }

private:

    class InternalVisitor : public Visitor<Data>

    {
    public:

        InternalVisitor() {}

        inline bool visit(Data const & data)

        {
data_ = &data;

            (*caller_)(); // return back to caller

            return false;

        }

        inline void setCaller(caller_t & caller)

        {
caller_ = &caller;

        }

        inline Data const & getData()

        {

            return *data_;

        }
    private:
Data const * data_;
caller_t * caller_;

    };

    void visitCoro(coro_t::caller_type & caller)

    {
visitor_.setCaller(caller);
visitable_.performVisits(static_cast<Visitor<Data> &>(visitor_));
valid_ = false;

    }

private:

    bool valid_;
coro_tcoro_;

    InternalVisitor visitor_;
Visitable<Data> & visitable_;

};

In the code above, we see a class called VisitableIterator. The class provides a constructor that takes a Visitable object as parameter. Since it extends an Iterator, it provides the appropriate methods to perform iteration over the visitable object.

The code makes use of a coroutine. The coroutine is stored in the variable coro_. The code for the coroutine is specified in the visitCoro function. The visitCoro function takes as a parameter a caller object. The caller object represents the caller of the coroutine and is used to transfer the control back to the caller when needed. The visitCoro function makes use of a visitor object of type InternalVisitor, named visitor_. This is the object that implements the visit function. After performing each visit, it saves the current data item and transfers the control back to the caller. Since it needs to perform this transfer, it needs access to the caller object, which is kept in the caller_ variable. There are a few other details that should be obvious from the code.

Here is how we use this:

int main(void)

{

    Counter counter(1, 100);

    VisitableIterator<int> iter(static_cast<Visitable<int>&>(counter));

    for (; iter.isValid(); iter.moveToNext()) {

        int data = iter.getData();

        std::cerr << data << std::endl;

}

    return EXIT_SUCCESS;

}

That was not too hard!

I have not yet investigated performance implications. Would update once I do.

Varints

noreply@blogger.com (Usuldan) — Sat, 02 Feb 2013 19:33:00 +0000

Variable length encoding of integers results in using less space for small integers and more for big ones. This comes handy in a few places. For instance, if you are encoding a string, you have the choice of using a null-terminated string or a length-encoded string. In the former case, you only use 1 extra byte, but end up with the restriction of not being able to include the 0 byte in your string. If you go the length-encoded way, then you can use 4-bytes to encode the string length. In this alternative, the 0 byte can appear in the string without any issue. However, for short strings, using 4 bytes for the length is very wasteful. To solve this, one can use variable length encoding for the string length, which makes it possible to use up only 1 byte for the encoding for a small string.

Another useful scenario is when you have a single integer type in your system, say a 64 bit signed integer, but most of the time, the integers you represent have a much smaller range. Again, the variable length encoding will help minimize the size of the encoding, in case you want to write things to disk or send data over the network. In fact, Google Protocol buffers uses a variable length encoding for a similar purpose. Wikipedia has an article on variable length encoding of integers here. Apparently it was popularized by the MIDI file format. IBM's SPL language uses a simpler version of variable length encoding for serializing its string types (see here).

I want to open a parenthesis here and talk about type names in programming languages briefly. Until C99, there was a lot of confusion in C in terms of the sizes of the types. How big is a long? Well, it depends on the system. Historically, not all systems supported all sizes, so the size for different types were not fixed. With C99, inttypes.h now defines types such as int64_t and uint64_t, which remove the ambiguity (there is also the craziness of int_leastX_t and int_fastX_t stuff, and in fact uintX_t is optional, but let's not get into that). What surprises me is that, Java has decided to call its types byte, short, int, long, etc. I much prefer int8, int16, int32, int64. If short is defined as a signed integer with a size of 16 bits (which means the size is not an implementation detail), why not call it int16, which makes it easier to remember as well.

Going back to variable length encoding, the idea is to divide the integer into 7-bit blocks, and use 1-byte (8-bits) to encode each block. The trailing 0-only bytes need not be encoded, saving space for small valued integers. When encoding, we go from the least significant block to most significant block, and set the most significant bit of each block to 1, except for the last one, which will have 0 as its most significant bit. As a result, a most significant bit value of 1 for a block is an indicator that the block is a continuation block, whereas a 0 value means that the block is the termination block. Here is an example:

89657 = 10101111000111001

Divide into 7-bit blocks

101 - 0111100 - 0111001

Set the most significant bit to 1 for all but the leftmost block, which is padded with 0's instead:

00000101 - 10111100 - 10111001

Recall that we encode starting from the least significant block, so we get:

10111001 - 10111100 - 00000101

To decode, we apply the following procedure. If the first block starts with a 0, we have a single block. Otherwise, we collect all the consecutive blocks that start with 1, until we reach the block that starts with a 0 - the termination block. We then strip the most significant bits from each block and concatenate. In the running example, we have:

Strip the most significant bit:

0111001 - 0111100 - 0000101

Reverse block order:

0000101 - 0111100 - 0111001

And concatenate:

10101111000111001= 89657

This works for unsigned types. For singed types, the negative numbers will have their most significant bit set. So -1 will take a lot of space. If you have an application where you want the encoding to take up less space if the absolute value of the number is small, then you can apply a mapping like the following:

0 -> 0

-1 -> 1

1 -> 2

-2 -> 3

2 -> 4

...

-2^(n-1)+1 -> 2^n-3

2^(n-1)-1 -> 2^n-2

-2^(n-1) -> 2^n-1

Code not reusable is not worth writing. So, below is the C++ code for this, which I hope you will find reusable:

#include <inttypes.h>

#include <cstdlib>

class VarintUtils {

private:

    template <typename T>
staticchar * encodeUnsigned(char * buf, T value) {
do {

            uint8_t byte = static_cast<uint8_t>(value) & 0x7F;

            value >>= 7;
if (value)

                byte |= 0x80;

            *(buf++) = byte;

        } while (value!=0);
return buf;

    }



    template <typename T>
staticchar * encodeSigned(char * buf, T value) {

        size_t const size = sizeof(T)<<3;
T newValue = (value << 1) ^ (value >> (size-1));
return encodeUnsigned(buf, toUnsigned(newValue));

    }



    template <typename T>
staticchar * decodeUnsigned(char * buf, T & value) {

        value = 0;

        size_t shift = 0;

        uint8_t byte;
do {

            byte = *(buf++);

            value |= (static_cast<T>(byte & 0x7F) << shift);

            shift += 7;

        } while ((byte&0x80)!=0);
return buf;

    }



    template <typename T>
staticchar * decodeSigned(char * buf, T & value) {

        buf = decodeUnsigned(buf, toUnsignedRef(value));
T half = toUnsigned(value) >> 1;

        value = (value & 1) ? ~half : half;
return buf;

    }



    // conversion from signed to unsigned
inlinestatic uint32_t toUnsigned(int32_t value) { return value; }
inlinestatic uint64_t toUnsigned(int64_t value) { return value; }
inlinestatic uint32_t & toUnsignedRef(int32_t & value)

      { returnreinterpret_cast<uint32_t &>(value); }
inlinestatic uint64_t & toUnsignedRef(int64_t & value)

      { returnreinterpret_cast<uint64_t &>(value); }



public:
inlinestaticchar * encode(char * buf, uint32_t value) {
return encodeUnsigned(buf, value);

    }
inlinestaticchar * encode(char * buf, uint64_t value) {
return encodeUnsigned(buf, value);

    }
inlinestaticchar * encode(char * buf, int32_t value) {
return encodeSigned(buf, value);

    }
inlinestaticchar * encode(char * buf, int64_t value) {
return encodeSigned(buf, value);

    }
inlinestaticchar * decode(char * buf, uint32_t & value) {
return decodeUnsigned(buf, value);

    }
inlinestaticchar * decode(char * buf, uint64_t & value) {
return decodeUnsigned(buf, value);

    }
inlinestaticchar * decode(char * buf, int32_t & value) {
return decodeSigned(buf, value);

    }
inlinestaticchar * decode(char * buf, int64_t & value) {
return decodeSigned(buf, value);

    }

};

Interestingly enough, you can perform binary search on a variable length encoded buffer. You might wonder why this is useful. Well, imagine you have a large graph stored using the adjacency list layout. Further assume that you have remapped the vertex ids so that the ones with the highest degree have the lowest ids. Now you can get significant compression if you encode adjacency lists using the variable length encoding of vertex ids. However, once you do that, how are you going to find if a given vertex is a neighbor of another vertex? You would have to resort to a linear search. Well, it is relatively easy to implement binary search on a variable length encoded list (of course, assuming it is sorted).

The idea is to readjust the location of the mid byte so that it aligns with the start of a variable length encoded value. Here is the code:

class VarintUtils {

...

private:

    template <typename T>

    static char * binarySearchGeneric(char * start, char * end, T value) {

        char * origin = start;

        T refval;

        while (start < end) {

           char * mid = adjust(start + (end-start) / 2, origin);

           char * midNext = decode(mid, refval);

           if (refval==value)

               return mid;

           if (refval>value)

               end = mid;

           else

               start = midNext;

}

        return NULL;

}

    static char * adjust(char * bufCurr, char * bufStart) {

        if (isFinalByte(*bufCurr)) {

            if (bufCurr==bufStart || isFinalByte(*(bufCurr-1)))

                return bufCurr;

            bufCurr--;

}

        while (bufCurr!=bufStart && !isFinalByte(*(bufCurr-1)))

            bufCurr--;

        return bufCurr;

}

    inline static bool isFinalByte(char c) {

        return (0x80 & c)==0;

}

public:

    inline static char * binarySearch(char * bufferStart, char * bufferEnd, uint32_t value) {

        return binarySearchGeneric(bufferStart, bufferEnd, value);

}

    inline static char * binarySearch(char * bufferStart, char * bufferEnd, uint64_t value) {

        return binarySearchGeneric(bufferStart, bufferEnd, value);

}

    inline static char * binarySearch(char * bufferStart, char * bufferEnd, int32_t value) {

        return binarySearchGeneric(bufferStart, bufferEnd, value);

}

    inline static char * binarySearch(char * bufferStart, char * bufferEnd, int64_t value) {

        return binarySearchGeneric(bufferStart, bufferEnd, value);

}

};

Well, one weakness of the above implementation is that, mid point is determined by considering the number of bytes between the start and the end. However, towards the end of the list, the numbers are larger and thus may take more bytes. Still, for long lists, this provides good speedup compared to a linear scan.

That's all for today...

I had a dream...

noreply@blogger.com (Usuldan) — Sun, 07 Oct 2012 16:09:00 +0000

It was 12 years or so ago. At the time there was no such thing as a smart phone. I had a dream one night, where I was sitting in front of a computer and was looking at the world map. I was zooming in and in and in, and eventually I was able to see all the details down to roads, buildings, trees, etc. The only difference from today's map applications with satellite view support was that, it was all live! Looking at Apple's new map application with the 3D turned on over Manhattan suddenly reminded me this long forgotten dream.

It seems so many people have complained about Apple's map app. Unlike what most people say, I like it better than Google Maps on iPhone. First of all, it supports vector graphics, so the maps are crystal clear and do not require downloading different images for different zoom levels. 3D views with buildings is also great. Most importantly, it brings turn-by-turn directions with voice support. There are two missing things though. First is the public transportation data. Google Maps was great for finding subway routes and times in NYC. Second is the inaccuracies in the map data. This latter thing is only a matter of time to fix. I don't criticize Apple for releasing the app. They have to start from somewhere. I am sure within a year all inaccuracies would be fixed in the map data.

What I hate about Apple is their DRM stuff though. I had 30 episodes of Twin Peaks and 14 episodes of Firefly bought from iTunes. I wanted to move them to my external disk so that I can play them on my TV without hooking up my computer to the TV. Guess what, you can't do that without buying an Apple TV. After some searching around and with the suggestion of a friend, I found the software called Requiem. It is the only free DRM removal tool that can wipe out the DRM from your movies without playing and re-recording them (there are many paid tools that do the latter). So you get the same original content, just without the DRM on it.

The tool works like a charm, but it is somewhat hard to get to. Due to legality issues, it is hidden behind the Tor network (which uses onion routing to hide the web end points). It can be reached from here: https://tag3ulp55xczs3pn.onion.to/ and works for the latest version of iTunes. It took around 10 hours to remove the DRM from 52GB worth of video. There were no problems.

Long time no see

noreply@blogger.com (Usuldan) — Tue, 24 Jul 2012 08:20:00 +0000

It has been some time since my last entry. I have been busy with settling down in a new place and starting a new job.

I am now living in Ankara, more specifically in Bilkent/Ankara. So far it has been great. I knew I had a longing for coming back to Turkey, but it turned out my longing was even stronger than I thought. I feel like a small kid who is overjoyed at getting ice cream.

Ironically, after more than 10 years and 10s of thousands of miles, I ended up moving 100 meters away from where I used to live in Bilkent when I was a student :D

It is not my observation, but as an American friend has observed and very aptly so, people are friendly but rude in Turkey, as opposed to being polite but distant in the USA.

While waiting in line for something, the guy next to you may start telling you about his entire life, or after learning that you are a computer engineer, may ask you to fix a problem he is having with his mobile phone. I don't mind though, I have missed my own people, the way they are.

One of the things I really enjoy is that, I am not the crazy driver anymore. In fact, I feel like a really good driver after seeing what everyone else is doing in traffic. This is a major change, as in the US I was getting traffic tickets regularly, and was feeling really bad about it. I am not used to being the bad guy. Finally that problem is solved.

Food that I love and food that I used to eat is finally back in my life. This is by itself worth everything. In fact right now it is Ramadan, which means I get to see more variety in food. Also, it is the first Ramadan back at home after 10 years. Feels great to eat with long time friends and family.

There is one annoying question I sometimes get from some people though: "Why did you leave such a wonderful place and job?" These people have unrealistic views of how life is in the US, most likely influenced by what they read in the media and what they see in the movies. I get annoyed at this question because it is asked as if the questioner has perfect knowledge of the issue, but in fact he/she knows nothing about it :D

Having a satisfactory job in Turkey is key to happiness for those returning back. Most people who came back like me are extremely satisfied, as long as they are happy with their jobs. Usually the job opportunities and the amount of money you can make is not as good in Turkey, but there are other things that can balance it out.

So far I am enjoying being an academic. Teaching is fun. Being with young people and helping them learn makes me feel better about myself. Research opportunities are decent here as well. I think I have done enough development over the last 6 years in the industry, so that I have no qualms about not having done practical work in my field. Now it is time to go back to full-time research and have fun.

Btw, we are finally finishing our book on Stream Processing. Below is what the cover would look like (yes, the breve in my name is missing, but this is just an initial draft :D). We are going to have a web site as well: http://www.thestreamprocessingbook.info/. I will be teaching Streaming Systems in Spring 2013, hopefully using this book. And my co-authors will teach the same course in Columbia University!

Edirne

noreply@blogger.com (Usuldan) — Wed, 23 May 2012 12:20:00 +0000

It is May 18th and raining outside, as we are waiting under a tent for a spring break concert to start. All of a sudden the rain goes berserk and we are wet from tip to toe. The concert is cancelled and we take refuge in a parking garage. It seems like the rain is going to stay tomorrow as well. Not a good time to go sightseeing in İstanbul. Luckily, the rain is moving from west to east. Thinking outside the box, we decide to go to Edirne the next day. This way we escape from the rain and get to visit the historical sights in Edirne.

Edirne, the westernmost city in Eastern Thrace, happens to be the second capital of the Ottoman Empire. As such, there are some historical sights to visit. A daily trip to Edirne from İstanbul is a stretch, but we take our chances. Once we are outside of İstanbul, there is no traffic on the highway. The sight is quite pleasant, with green plains lying on both sides. After a 2.5 hour drive, just when we are wondering where the entrance to the city center is, we find Edirne right in front of us.

Selimiye from distance

Selimiye Mosque marks the city. It is visible from pretty much anywhere. In fact, it is the only sight we know in Edirne. We are trusting mobile Internet for the rest. It turns out it is May 19th today, a national holiday in Turkey - Commemoration of Atatürk, Youth and Sports Day. There are some celebrations going on, yet we don't have any problem finding a parking spot for our car on the street. Edirne city center looks clean and tidy in general. However, there are some buildings that look a little run down and we see a lot of street sellers and beggars around. We decide to visit the Selimiye Mosque as the first thing. As I look at it from distance, Selimiye Mosque looks almost surreal to me. With its majestic appearance, it feels so detached from the city that surrounds it. It is grand in size and delicate in style.

There is a graveyard next to the mosque, where we find interesting headstones. These graves belong to high profile people from the old days. The various shapes and sizes of the tombstones relate to their social status and occupation. The informational text given on the wall contains a poem from Yunus:

Yunus der ki gör takdirin işleri
Dökülmüşler kirpikleri kaşları
Başları ucunda hece taşları
Ne söylerler ne bir haber verirler

Yunus says: "All this is done by Fate alone."
From their eyes, all their brows and lashes are gone;
To mark their place there is only a headstone.
They never speak nor send any news at all.

The interior of Selimiye's big dome

Commissioned by Sultan Selim II (Selim the Blond), Selimiye Mosque is considered to be the best work of Mimar Sinan, the famous Ottoman architect. We go inside the mosque through the courtyard, which is surrounded by cloisters. It is as beautiful inside as it is outside. Selimiye has one large dome and several smaller half domes. The interior is very spacious as it is not segmented by colons that you typically find in other grand mosques that have multiple domes. The use of red and blue inside the mosque is quite impressive. As a mystery, there is a reverse tulip hardly visible inside the mosque, embossed on a marble leg. Overall, it is the most elegant mosque I have ever seen. There is a sizable complex that surrounds the mosque, as is common with other imperial mosques. Some part of this complex is converted into a museum that showcases artifacts from the Ottoman era. We visit the museum. It is nice, but there are no descriptions given for the items on display. That is weird.

The interior of the Old Mosque

It starts to rain very lightly. We decide to go for a lunch, hoping that the rain will go away. We ask around to find the best place to get Edirne meatballs and fried liver. Osman seems to be the place to eat. The food is good. The fried liver is thinly sliced, different than the Albanian liver I am used to. I like the Edirne meatballs. Finally, we order a local specialty for desert: Cheese Halva (Peynir Helvası). Mmmm, yummy...

After lunch it continues to rain lightly. We buy umbrellas just in case it starts to rain more heavily. Our next two stops are the two imperial mosques that are very close by. The first one is called the 'Old Mosque'. Strange name for a mosque. As the name suggests, it is old, and follows the older Seljuk architecture. There are equal sized domes, nine of them, in a 3x3 grid. Jokingly, I call it the 'Silo Mosque', as it looks like a series of silos. It lacks a courtyard. While it does not look too impressive from the outside, it is beautiful inside, with giant calligraphy decorating its walls and nice ornaments under its 9 domes.

The courtyard of the Üç Şerefeli Mosque

The next stop is the 'Üç Şerefeli Mosque'. We learn that this mosque is one of the first representatives of the traditional Ottoman mosques. With its courtyard surrounded by cloisters, the extended complex next to it, and most importantly the large dome surrounded by four smaller ones. The cloisters are roofed by many small domes, each having a unique decoration beneath. The mosque has four minarets, each of which has a different height, width, and style. We read that the minaret with three balconies have three independent stairs running through it. A feature shared by Selimiye, even though we are not allowed to experience it firsthand.

We decide to walk to the old palace after learning that it is half an hour away. After a 15 minute walk, we reach the outskirts of the city. There is no one around. There seems to be a restoration project on a historical walking bridge that goes over a stream of water. We take the bridge. There are green plains on both sides, with some orderly trees. We see some ruins on the right-hand side, which appears to be the site of the old palace. On the left-hand side there is another imperial mosque, which turns out to be the Beyazıd II Mosque. We decide to go and see the palace, or what remains of it, first.

The remains of the Edirne Palace

There is an information panel illustrating the original palace, which was a complex of multiple buildings spread out on a large area. Ironically, the old palace is called the 'New Palace' :D It must be because it replaced the older palace in Bursa - the first Capital of the Ottoman Empire. There are multiple restoration projects going on. One of them, the restoration of the palace kitchens, is complete. A quick search on the Internet reveals that an explosive depot near the palace was set on fire during the Russo-Turkish War of 1877–1878 by the governor of Edirne in fear of a Russian takeover of the depot. The palace was destroyed together with the explosives.

Tower at the Edirne Palace entrance

There is a small historical bridge in the entrance of the palace area, which has a small tower next to it. I have my second surreal experience here, as there is a motor road passing through the palace area and over this bridge as well, at which point the road goes down to a single lane. It is not clear what this road is doing in the middle of the historical palace area, let alone how cars manage to go over this single lane bridge in both ways without any control signs. We walk pass the small bridge. On the other side there is a stone that was used to display the heads of beheaded statesman, like the famous grand vizier Merzifonlu Kara Mustafa Pasha, who led the unsuccessful siege of Viena in 17th century.

We leave the palace area and walk towards the Beyazıd II Mosque. It has a distinguishing white color. Not too impressive in terms of its size, especially when compared to the other imperial mosques in the city. But it has a large complex outside. It turns out that this complex houses one of the first medical schools and hospitals of the Ottoman era. After taking a quick tour of the mosque proper, we visit the museum.

Beyazıd II Mosque

Once inside the museum, we break for a Turkish coffee. Turns out to be a big mistake as the museum is about to close. There is a sign that says that the museum was awarded the European Council's "Museum Award" in 2004. Certainly deserves it. We only have time to properly visit the medical school and the outpatient rooms. Each room contains an illustration of the daily life there, such as students and professors interacting in study rooms, patients being treated in outpatient rooms, or medical experiments being conducted in labs. This is some 500 years ago, so it is quite interesting to see the medical technology of the day. The museum has plenty of descriptions in both Turkish and English. Unfortunately, we can only briefly look at the hospital area as the museum closes.

A horse carriage in Karaağaç

We walk back to the city, passing through the gypsy neighborhoods. We take a walk in the main street of Edirne, which is crowded with young people. We go back to our car and drive to Karağaç - a small quarter across the Meriç River, the only land on the western side of the river that belongs to Turkey. There is a cute bridge across the river, which carries vehicles as well as pedestrians. Karağaç is very silent. The nature is beautiful. Trakya University has its Faculty of Fine Arts here, which has a traditional looking building with a modern sculpture in its garden. A mile or so away from the small town is the border crossing into Greece. We go there in the hopes of seeing the exact point where supposedly the Turkish and Greek soldiers are standing on their respective sides of the border. Unfortunately, the crossing is closed at the time we reach there. Before leaving Karağaç we stop at a cafe near the leg of the Meriç bridge to get some tea. The view is great. This marks the end of the trip. The drive back to İstanbul's Anatolian side is something we don't want to remember :D

Barcelona

noreply@blogger.com (Usuldan) — Sun, 06 May 2012 08:43:00 +0000

Day 1: We land at the Barcelona Airport in the early afternoon. The airport is nice, quite large. Terminals are rather far apart. A bus runs between the terminals as well as to the Renfe train that connects to the Metro. We take the Renfe train first and then use the Metro to go to the Sants station, and from there to the Rocafort station. The Metro is very easy to use, trains are frequent, and it is clean. Sometimes there is too much walking between stations at connection points. Our hotel, Evenia Rocafort, is 3 blocks away from the Rocafort station. The hotel is clean, nothing fancy but good.

It is Friday. The weather is perfect for a vacation. It is sunny, yet you can walk around all day and not sweat one bit. We walk to the Catalonia Square, passing by University of Barcelona. An interesting thing we notice along the way is the octagonal blocks. The streets widen at intersections where each corner is cut to create extra space. The sidewalk part of this space is often used by the corner cafes for outside tables, whereas the street part is used for short-term parking lots. It makes the intersections look very spacious and creates nice views for outside dining.

La Boqueria market

From the Catalonia Square, we walk down La Rambla. It is simply amazing. Wherever you turn, there is something interesting to see, such as street performers, interesting shops and cafes, historic buildings, etc. Take any one of the many side streets and you'll come across countless interesting views. We visit the La Boqueria market. Very nice and clean. Fruits, nuts, sweets, meat, fish, etc. Extremely colorful. We then visit Plaza Real. It is a square in Barri Gotic, full of restaurants and people. All restaurants have outside seating and a nice view of the square. We pick one restaurant and order some 'tapas'. Tapas are a wide variety of appetizers. Rather than ordering one dish, you order many small ones and share. It is a nice concept. We also order one seafood paella. The food is not that good in the restaurant we pick. We like the olive oil but nothing else :). As we will later find out, there are better places in Plaza Real to eat. We go back to La Rambla and walk all the way down to Columbus monument and from there go to the marina. There is the Maramagnum mall there, with a nice view of the sea. We return back by walking up on La Rambla. We eat some ice cream on the way back. We take one of the side streets from La Rambla towards Raval and reach our hotel.

Day 2: We start Saturday by walking to the Espanya Square. We find a patisserie for breakfast. As we will experience the next day, it is difficult to find a good breakfast place in Barcelona. It seems people usually have coffee and croissant for breakfast and lunch is the most important meal in Spain. This patisserie is excellent though. It has great sandwiches and nice sweets. Great variety. Interestingly, very little English is spoken :).

National Art Museum of Catalonia

From there, we go to National Art Museum of Catalonia (MNAC) on the Montjuic hill. There are open space walking stairs on the way, which is nice :), as we have plenty of walking to do in the rest of the day. The MNAC building is very impressive, especially from the outside. From MNAC we can see a mountain towards north with a church at the top. We don't know what it is but decide to find a way to go there the next day (it turns out it is Sagrat Cor church on top of mount Tibidabo). We buy a combined ticket that gives us the right to visit 6 different museums. MNAC has many paintings from Catalan painters. It is a little sparse in terms of the collection it contains, but quite nice. Not crowded at all. From there we walk to Poble Espanyol - an open-air architectural museum in the form of a small Spanish village. Very nice. It has various small shops, even a glass making exhibition. From there, we walk back to Espanya Square.

Sagrada Familia

We take the Metro to the Passeig de Gracia station. From there we walk a few blocks to see Casa Batllo, one of Antoni Gaudi designed buildings. We don't visit the inside as there is a long line. We walk another few blocks to see Casa Mila/La Pedrera, another one of Gaudi's apartment buildings. This one is much bigger and has a rather remarkable rooftop. We do not enter due to long lines at this time. We will come back to La Pedrera later to see the roof. We search for a restaurant for lunch. We walk towards east, passing by many restaurants, but not picking any, in the hopes of finding a better one. By the time we find a restaurant, we realize that we are almost at Sagrada Familia. The restaurant is called Brasila, and has nice outside seating area. We get one large pizza and various tapas. From there we visit Sagrada Familia and are amazed by its size, even though it is not even finished. The Nativity facade is particularly amazing. I personally feel that this is the most impressive building I have ever seen. From there we walk to Hospital of the Holy Cross and Saint Paul through Gaudi Avenue. It is a nice walk with an impressive historic building at the end.

Barcelona Cathedral

We take the Metro to Jaume I station and visit the Barcelona Cathedral. There is a long line at the entrance, but it is moving fast. It is very crowded inside, but quite amazing. Very impressive from the outside as well. We walk back to La Rambla and get a ticket to a Flamenco show. Never seen one before. The dance is amazing. We are not too impressed by the guitar. But the 'cante' is the part that ties them all together. Full of intense emotions. From there we walk back to the marina, and have dinner with sea view at TapaTapa in the Maremagnum mall. The food is decent, view is good. We go upstairs to Starbucks. It has a great view as well. It is already late and it starts raining. We take a taxi to the hotel.

La Pedrera

Day 3: We start the day by searching for breakfast. Yesterday's breakfast is still in our minds, and we fail to find a place that looks equally good. We walk up to La Pedrera still hungry. We end up picking up a boring (and unexpectedly expensive) sandwich. We then visit the rooftop at La Pedrera. Nice architectural elements and good view of the city, including a view of Sagrada Familia. From there we take the Metro to Valcarca station near Park Guell. The park is on a hill and again there are open space walking stairs that help you climb there. The park is nice both in terms of the nature and the Gaudi-designed buildings. It is extremely crowded though.

Sagrat Cor

We walk to the El Puxtet station and decide to take the Metro to the Tibidabo mountain. It turns out one needs to first take the metro to the Avenue Tibidabo station, then take the 'Blue Tram', and then take the Finicular to the top of the mountain (some ~550 meters). Before we start our journey, we first enter a patisserie next to the El Puxtet station. We eat an interesting desert that has ice cream inside (much to our surprise). Almost no English is spoken in this place. We then take the Metro to Avenue Tibidabo station. The weather is beautiful and the Blue Tram has a long line, so we decide to walk up to the Funicular. It is a long uphill walk, but the sights are great. Nice buildings in every corner. The Funicular takes us up to the mountain. We are surprised to see that there is an amusement park at the top of the mountain. There is even a roller coaster :) But we are more interested in Sagrat Cor church. It has a very commanding location at the top of the mountain and sees the entire city. We take an elevator to the top of the church, then take the side stairs to the top balcony, and another set of stairs to the very top. Simply breathtaking. For me, this was the best part of the trip.

Arc de Triomf

We take the Metro back to the top of La Rambla and from there walk to Arc de Triomf and visit the Ciutadella Park. The park is lively. We walk from the park to the beach. There is a walking way along the beach that has trees on both sides. It runs all the way to the marina. We take it. There is a small market place at the end that has a line of tents along the road, selling olive oil, sweets, sausages, etc. There is a street performer playing the didgeridoo. We pass through the Columbus monument and go up La Rambla back to Plaza Real to eat. This time we pick a nice restaurant called Kabul. We order a variety of tapas. Small fried fish tastes much like the Black Sea anchovy. We walk back to the hotel.

Fortress of Montjuic

Day 4: We decide to go to the same patisserie we went in Day 2 and avoid the painful breakfast place search. It is as good as the last time, if not better. From there we climb up to Montjuic again, but this time to visit the Joan Miro museum. The giant carpet is impressive. The paintings are 'interesting'. We are convinced that Miro has succeeded in "assassinating painting" (in his own words). We take the teleferique to the fortress of Montjuic. It has an impressive view of the sea as well as the city.

We walk down the hill to El Raval. We walk through Rambla del Raval and see the big cat. We pass through Old Hospital de la Santa Creu. We then go to Barcelona Museum of Contemporary Art (MACBA). It has a nice building. The second floor is closed and the museum does not contain that many pieces in its collection. There are too many videos for my taste. Not impressed, especially compared to MoMA in New York.

Palau de la Musica Catalana

We wander around in Barri Gotic. We walk through Via Laietana. We go to Picasso museum only to find out that it is closed on Mondays. We find a restaurant named Bilbao-Berria for dinner. It has outside seating facing the Barcelona Cathedral! It has Basque style tapas. It is open buffet. The tapas look somewhat like sushis with the rice replaced with bread :) They are spiked with toothpicks and you pay at the end by the number of toothpicks you accumulate in your table. A lot of seafood varieties. Salmon, tuna, cod. Simply delicious. The best tapas we had so far. There is a street show taking place in the small square in front of the church. We visit Palau de la Musica Catalana and buy a ticket for a concert at night. We do some shopping until the concert. We listen to Carmen and Rodrigo's guitar concerto. We are able recognize only 3 pieces as familiar (not bad for us). The concert hall is amazing, a UNESCO world heritage site. We walk back to the hotel.

Day 5: It turns out that our last day in Barcelona is May 1st, which is Workers Day. Our plans in terms of visiting the Dali museum, which is an hour and a half away by Renfe train, go down the drain, as the museum is closed. We use the internet connection in the hotel to find a good breakfast place. It is named Federal Cafe and serves Australian style breakfast. It has a modern design. The food is good. We finally have some eggs for breakfast.

Labyrinth Park of Horta

We take the metro to the Mundet station to visit Labyrinth Park of Horta. It is a historical garden. Not a big tourist place so most people seem to be locals. Popular among families with kids. There is a long line though. The garden is very calm. Good for getting fresh air and clearing up your mind. The main attraction though, is the big labyrinth made out of cypress trees. We rest in the park for some time, and take the metro back to Jaume I station. We visit the Picasso museum again, and again find it closed, this time due to May 1st. We contend ourselves with the Picasso paintings we saw in MNAC two days ago. We visit the Santa Maria del Mar church. Cannot see the inside as it is closed. We find a pizza place called Bubo, which has outside seating with a nice view of the church.

Santa Maria del Mar

We then visit Neu Camp (no games this weekend), by taking the Metro to the Les Corts station. Again May 1st is at work. The stadium closes early that day. We visit the Barcelona store. Nice items, but extremely expensive (I am a Real Madrid fan, anyway). We view the stadium from the outside and travel back to La Rambla, Liceu station. We walk down to the beach area and rest. We walk back to Barri Gotic and pass through Santa Maria del Mar again. This time it is open! The inside is very impressive. Looks bigger inside than outside. The colons are nicely laid out. We find a place to have some deserts. Nice almond cake! We do some more shopping. We walk back to the top of La Rambla and decide to take a look at Sagrada Familia again to see it at night, hoping that it is illuminated. We take the Metro, and after a few stations find out that Sagrada Familia is dark, no lighting. We take the Metro back to Gran Via avenue and walk to the hotel, ending the day and ending the trip.

Güzel şiirler

noreply@blogger.com (Usuldan) — Tue, 27 Mar 2012 17:08:00 +0000

Karacaoğlan'dan:

Şu yalan dünyaya geldim geleli
Tas tas içtim ağuları (zehirleri) sağ iken
Kahpe felek vermez benim muradım
Viran oldum mor sümbüllü bağ iken

Aradılar bir tenhada buldular
Yaslandılar şıvgalarım (dallarım) kırdılar
Yaz bahar ayında bir od (ateş) verdiler
Yandım gittim ala karlı dağ iken

Farımaz (Usanmaz) da deli gönül farımaz
Akar gözlerimin yaşı kurumaz
Şimden geri benim hükmüm yürümez
Azil (Rezil) oldum güzellere bey iken

Karac'oğlan der ki bakın olana
Ömrümün yarısı gitti talana
Sual eylen bizden evvel gelene
Kim var imiş biz burada yoğ iken

Şah İsmail'den:

Şahın bahçesinde men garip bülbül
Efkarım artmakta, halim pek müşkül
Koparmadım asla, kokladım bir gül
Kafir oldum ise imana geldim

MET & Art of the Arab Lands, Turkey, Iran, Central Asia, and Later South Asia

noreply@blogger.com (Usuldan) — Wed, 21 Mar 2012 01:08:00 +0000

While I am at it, let me post this as well...

I went to see the MET last week (I almost had an art attack last few weeks :D). There was a new section called 'Art of the Arab Lands, Turkey, Iran, Central Asia, and Later South Asia'. There we saw this rather interesting miniature below. Miniature is a type of painting where perspective is missing and various things are abstracted. It is a form of art. You can check out Persian and Ottoman miniature.

Anyway, the below miniature is from a 16th century book by the Persian poet Sa'di. What is interesting about it is that, it shows the Prophet Muhammad's face. I have never seen this before, as usually the face is drawn blank or is veiled. After doing some web search, I later learned that the Prophet's face was drawn in Persian illustrations until the 1500s.

Last 10 days...

noreply@blogger.com (Usuldan) — Wed, 21 Mar 2012 00:19:00 +0000

Last ten days in the US... The days are passing by veeeerrrry slowly, not without events though.

I had visitors last week and had great time in NYC. However, something rather strange has happened one night. We were returning from the city at around 11-11:30pm or so and were just about to get out of the White Plains train station. I was driving and stopped at the red light in front of the back exit of the parking area. As we were waiting, 90 degrees to our right, around 100-200 meters ahead, a guy was riding a bicycle. He suddenly hit the curb, fall down from his bike, hitting his head on the side of the curb. It is somewhat interesting that all three people in our car were actually looking at that direction (for no obvious reason) and saw the exact moment of the fall. I think the guy had a medical problem before he fell, because no one falls like that!

We waited for around 30 seconds and the guy was not moving at all, as far as we could see from the car. So we decided to go and check. I went near the guy and asked him if he was ok. However, he was not moving at all and not speaking. So we decided to call 911. Unfortunately, my phone was out of battery (as I played with the damn thing all day in NYC). Then we tried my friend's phone, which is a phone from Turkey but open to international calls. However, it did not call 911 (not good). Around that time a guy came by who also saw the accident. He had a phone and called 911. I went back to my car and parked it at a less obstructing place (noticing that I was occupying the entrance lane in reverse direction!). A lady in a car also came by and told me that she also saw it happening. After telling her that we called 911, I went back next to the guy. Blood was coming from his face. I couldn't tell from where particularly. Then he started moving his left hand towards his face. But no speaking or no other movement. I think it was not a voluntary movement. It was a good sign though. Then the police and ambulance came by. The ambulance took him. One of his shoes was thrown off. They put that next to him as well. It made me feel rather strange, but I can't tell exactly why.

The medic (or whatever they are called, I am using Starcraft terminology here) was so relaxed as she carried through the procedures. She must be seeing this all the time. We were pretty much shocked, in complete contrast to her. We told the police what we saw and I gave my contact info. This was a very strange event ending that day. I had even more trouble sleeping than usual that night.

Ok, this was pretty depressing...

On the good side of things, I managed to sell my giant kitchen table today. A lady came with the biggest SUV I have seen in my life and took it. Despite the size of the SUV, the table did not fit as is! So I had to disassemble it. I was very happy to get rid of it though. Interestingly, the lady's grand father was Turkish. He migrated to Hungary after the World War I. Small world!

More interestingly, I was at the Wells Fargo the other day (trying to move the many many millions of dollars I amassed over the years to Turkey). After they made me wait for an HOUR before I can talk to someone who can do a wire transfer, I was not in a good mood at all. However, the guy asked me about my home town soccer team and mentioned the name of an English born Turkish player who played briefly for the Turkish national team. Mustafa Izzet or Muzzy was the soccer player. That got me into the right mood very quickly :D Again, it is a small world. Not to mention another guy in the same branch of the bank, who is an Albanian, and knows some Turkish...

Something different: I have decided, yet again, that I will wear a wrist watch. Every few years I make an attempt to wear a watch. It usually lasts a year or so. Usually something happens to the watch and I give up. The last time I got a watch I lost it during military service. It became a somewhat entertaining subject during those days, as I lost the watch in the toilet. Now that might sound rather silly, but those who know squat toilets (they are called alaturka toilets in Turkey) may understand and those who have done their military service may even sympathize (for others: imagine the dirtiest possible toilet and multiply that by two). After this event, when someone asked the time during my 3 weeks at the military, I used to say "It is shit past shit!" :D

Anyways, I bought my third Skagen watch. I was unhappy with the first two (the first one's front got scratched easily, the second one's water resistance was a joke). But I like how they look and they are thin. I have high hopes for this one...

I am gonna end this post with one of the marches we used to sing in the military service and my adaptation of it (mine was called the Toilet March). This part is for Turkish speakers only :D

Aylardan Kasım, günlerden Cuma
Gece nöbette, çıktı çatışma
İndik mevziye, mevzi karanlık
Mevzi değil bu, sanki mezarlık
Ana bilmeyiz, baba bilmeyiz
Bu vatan için, dağdan inmeyiz
Kahpe PKK, dinle bu marşı
İşte geliyor, askerin şahı

My adaptation means no disrespect to any person or institution. It was a result of my frustration with the lack of hygiene in the barracks (for the 3 week paid service). This version became popular in our barracks at the time.

Aylardan Nisan, günlerden Cuma
Gece koğuşta, çıktı kokuşma
İndik helaya, heryerde boklar
Maşrapa, kağıt, onlar da yoklar
Şifon çekmeyiz, su dökmeyiz
Dört bir duvara, sıçar geçeriz
Her gün bir manga, bok temizleriz
Askerin şahı, DAHT ERleriz

Not: Bilmeyenler için, DAHT ER bize verilen isimdi, yani 'Dövizli askerlik hizmetine tabi er'.

Many moons have passed since I left the town of Tristam behind me!

noreply@blogger.com (Usuldan) — Mon, 20 Feb 2012 02:27:00 +0000

I have played Blizzard games since I was in high school, starting with Warcraft. I recall loading Warcraft I to my Intel 486 PC using a dozen floppies. The computers have come a long way since then. The last Blizzard game I played was Starcraft II, around 2 years ago. I liked its storyline as well as the ability to choose alternate flows in a few locations. It seems the online play is more popular. I never got into playing things online, as I like to play at my own pace against the computer and with a storyline. I think I might have hit an age threshold and SC2 might be the last one for me. Never say never though.

A friend of mine, who is a Physicist, told me that someone from Blizzard has called him recently to inquire about underwater sound effects. When I was an undergrad, I always thought Blizzard must be the coolest place to work on earth. I will never know if that is the case, as life is too short to try out all you wonder about. But I know one thing for sure, these guys do a great job and take it very seriously. Anyway, I don't expect any calls from Blizzard, but if Diablo himself were to call me, I would give him some advice on evilship (is that a word?). Sometimes the urge to do bad is nearly overpowering, but that is a different story.

I recall watching one of Diablo's cinematic trailers (which are usually top notch), and I remember the dialog 'Many moons have passed since I left the town of Tristam behind me...'. I am at a stage of life where I can say the same, just replace Tristram with Trabzon and that is it. 4 years of college, 5 years of Ph.D. and 5.5 years of work, since I left Trabzon behind me. I am close to another big change in life. After more than 10 years in the US, I am returning back to Turkey, to Ankara to be specific. This has been the most difficult decision I made in life so far and all kinds of thoughts are rushing through my head for the last several months. I guess they are not going to stop until I do move back.

Email conduct!

noreply@blogger.com (Usuldan) — Tue, 31 Jan 2012 01:50:00 +0000

I have noticed that the young generation is lacking in knowledge of proper email conduct. First of all, unless it is by mistake, leaving the subject line empty is unacceptable. Second, unless an email is a continuation of a previous conversation, it should properly address the person who is receiving the email. Third, it should have proper spacing. Fourth, the email should end with a proper regards. Thanks, Regards, Cheers, whatever is suitable for the occasion.

For instance:

Dear X,

Bla bla bla.

Regards,
Y

Unfortunately, I often get emails of the form:

Hi,bla bla bla. -Y

The use of mobile phones for emailing has made things even worse. Both the content and the spacing are sacrificed. Punctuation within text is butchered as well.

Another pet peeve of mine is that, the text font should be consistent throughout the email, unless there are special formatting needs. A common error I see is:

Dear [Name copied from Web, in different font], bla bla bla.

I have noticed that folks from Asia do this more often for some reason. It looks bad because it makes it obvious that the name was copied and pasted from a web page, and no effort was made to fix up the font.

There is something else that I don't like. I am Turkish and I do write emails in Turkish a lot. Unfortunately, many people avoid using the Turkish characters ı,ü,ö,ğ,ç,ş and instead substitute them with i,u,o,g,c,s (which are also in the Turkish alphabet). This is usually done because many people use English keyboards and switching the language results in remapping many of the punctuation keys (as the Turkish alphabet has more characters than the English one) and makes it difficult to type if you are used to writing a lot of English (academics, engineers, etc.). I wonder if a keyboard layout that uses a meta-key to print the Turkish characters would be a better choice. For instance, command+u could give ü. But I don't think there is such a layout.

In many cases, the mindless substitution of Turkish characters does not result in any information loss. In fact, there are tools that would automatically correct Turkish text written using the English alphabet into the proper Turkish form with great accuracy (I use an emacs mode for that). However, people often do not use such tools (it is a pity, as there used to be a Firefox plugin for this!, which makes it rather easy).

When the meaning of a word is altered due to these substitutions, one can usually figure out the intended meaning from the context. For instance, if you see 'sikildim' in the text, it literally means "I'm fucked". However, it is highly likely that you meant "I'm bored", that is 'sıkıldım'. While what you meant would be usually obvious from the context, I don't think you want to leave this particular one to the context!

Interestingly, there is a curious property of the Turkish alphabet that saves the day for this particular scenario. The upper case version of the letter ı is I in Turkish. In fact, we have i,İ and ı,I in Turkish, whereas in English there is only i,I (I can't help but point out the symmetry and consistency in the Turkish version :D). Interestingly, without changing the keyboard layout to Turkish, one can write 'sIkIldIm', which means "I'm bored". On the down side, it immediately brings up the other meaning to one's mind as well. So it is not a complete solution.

Unless I am in a hurry and writing to a close friend, I try to always write my Turkish emails using the correct characters, even on the iPhone. For those who do not know: You can go the settings in your iPhone and enable the international keyboards. Once you do that, you can hold down on a letter and it will show you the alternatives. No excuses!

C++: I hate you, I hate you, I hate you. Leave me alone! Yet, I find you strangely attractive.

noreply@blogger.com (Usuldan) — Wed, 14 Dec 2011 02:36:00 +0000

Had a really bad day with C++. Two strange bugs ruined it for me.

The first one had to do with the use of the ternary operator without proper parenthesis around it, while working with the shift operator on streams:

ostringstream ostr;
ostr << "bla bla" << x?y:z;
// This becomes
(ostr << "bla bla" << x) ? y : z;
// Which was simply becoming
ostr << "bla bla" << x;
A stupid bug like this inside a distributed app caused me to spend several hours. The bug was manifesting itself in a barrier operation, where different sets of distributed processes that were supposed to barrier independently, were barriering all at once, and the resulting incorrect counter was causing a deadlock!

Once I fixed the bug, another one followed. This time operator overloading and function overloading together were causing trouble:

void foo(X x) {}

template<class Y>
void foo(Y y) {}

And there is a class Z that implements an evil cast operator to class X.

In this setup foo(z) resolves to foo<Z>(z) but the coder has intended to call foo((X)z). The code used to work before the templated overload was added.

This was causing a rather strange segfault in a distributed app, and for some reason not showing up in standalone mode. After some more hours, this bug got cleared as well.

Given that I also spent a good deal of debugging and refactoring time yesterday with the evil problem of static object construction order (which is best eliminated via lazy initialization), as well as destruction order, I started to have some questions about C++. Not that I don't know all these problems. I do know them very well. But when there is so much depth and complexity in the application logic (multiple threads, database connections, forked processes, incremental checkpointing, cross-process synchronization, etc), having to deal with the warts of C++ becomes really annoying.

However, despite all its shortcomings, there is something about C++ that still attracts me. It is somewhat like enjoying the smell of your own armpit.

Democracy: Apply Directly Where It Hurts

noreply@blogger.com (Usuldan) — Sat, 03 Dec 2011 04:14:00 +0000

The rhetoric about spreading democracy sounds so phony in light of recent history. While I believe that there are many people in this world who are kind enough to expend their resources for the benefit of others, such behavior is hard to come by in the realm of international relations. Spreading democracy often takes a backseat in the presence of other priorities. There are plenty of cases where oppressive regimes have been supported by the West for the purpose of advancing their agendas, at the cost of the people living under these regimes.

There is this saying, which I heard from my father, that goes something like the following in English: "What goes around will come around for those who are trying too hard to outsmart others." (Çok uyanık geçinenlere döner dolaşıp girermiş.) When we look at examples of foreign intervention in politics and internal affairs of countries, we repeatedly see that in the long term there are unexpected consequences of such efforts.

Let's start with Egypt and the so called Arab Spring. An Arab nationalist, Soviet-leaning Egypt under the rule of Abdel Nasser has been transformed into a pro-American Egypt with normalized relations to Israel under Enwar Sadat. I don't see any problem with this personally, as I have no sympathy for the Soviets. Also, Enwar made a good deal: getting back the critical Sinai Peninsula that was lost during the 6-day wars, in return for recognizing Israel. He paid it with his life. What I don't like though, is the continued US support of the Mubarak regime that followed, in the name of maintaining 'stability' in the region. While I understand the concern for the rise of Islamic extremism, which may impact the so called 'stability' (especially with respect to Palestinian-Israeli conflict), I don't see how supporting an oppressive regime with billions of dollars of aid each year helps make the extreme elements in opposition any less extreme. Martial law for 30 years! So much for spreading democracy. It is not yet clear whether the US support of Mubarak in the past will come back to bite them or not. But if Pakistan and Iran are any indication, it may very well do.

Now let's look at Pakistan and see how Islamic extremism was fueled by US and was not considered harmful, well, until it was. There is this idiom in my mother tongue, that goes like: "This is not a diet, nor a cabbage pickle." (Bu ne diyet, bu ne lahana turşusu.) You can't have a low-sodium diet and have a salt-packed pickle at the same time! Back to Pakistan. Zulfiqar Bhutto who had socialist economic policies was ousted with the help of US, and General Zia took control in a military coup. With the Soviet invasion of Afghanistan, US and Saudi Arabia have provided financial support for the Zia's regime to train large number of Mujaheddin against the Soviets. Under General Zia, the number of Madrassas's (religious schools) in Pakistan has skyrocketed. Students graduating from these schools had no skills to find a job in the market, and have been channeled to join the Mujaheddin to fight against the Soviet invasion in Afghanistan. They later formed the roots of the Taliban. And we all know how that turned out.

In Iran, the democratically elected Iranian government of Mosaddegh was overthrown in a coup. British and the US were behind the move, which was a consequence of Mosaddegh's nationalization of the oil industry that was being run by a British-owned company until that time. Consequently, the US became a major backer of Shah M. Reza Pahlavi, whose monarchy has become increasingly corrupt, extravagant, and out of touch with the general public in terms of Iranian culture and (Islamic) traditions. This gave rise to the Iranian revolution, and today theocratic Iran is one of the most oppressive regimes around the world. Not to mention the whole Iraq/Iran war and the rise of Saddam as a balance against the Islamic Republic of Iran. The Gulf War and the Iraq war that followed have further complicated the whole situation. Unfortunately, two wrongs do not make a right, and in this case many many wrongs did not make a right, at least not yet. Today the sanctions against Iran further isolate the country. It won't help with nuclear proliferation either, as North Korea is a proof to that. Furthermore, the opposition groups within Iran that are already being deprived of their social movement rights may interpret these sanctions as abandonment by the West.

May be Ron Paul, who is seeking to be the Republican Party candidate in the upcoming elections, is right. He says that "America [should] not interfere militarily, financially, or covertly in the internal affairs of other nations", while advocating "open trade, travel, communication, and diplomacy with other nations". Food for thought.

:D

noreply@blogger.com (Usuldan) — Tue, 22 Nov 2011 01:07:00 +0000