JavaScript Framework

Victor Lingenthal and myself have created a new open-source MVC-JavaScript framework called BetaJS. Among its features are the following ones:

  • Models
    • Computed Properties: Aggregated properties depending on other properties are automatically updated
    • Sophisticated server synchronisation, html storage and caching stack: Queries are only executed on the server if necessary. Depending on the capabilities of the server’s REST-API, the client-side simulates all missing capabilities.
  • Views
    • Html-Property-Bindings: Changing properties in models automatically updates the affected elements in templates. You can use that to apply css classes or input values.
    • View Library: Containers, ListViews, Buttons, etc.

The system currently lacks proper documentation and tutorials. You can take a look at the demos though. On our roadmap is the development of an operational transformation system to easily continue working with an app offline and synchronising everything when you come back online.

Ruby-on-Rails-like PHP Framework

We have created an open-source Ruby-on-Rails-like light-weight PHP Framework called PHPrecious here. Feel free to check it out and play around with it. There is a full demo included in the demos folder.

Every component in the framework is as loosely coupled as possible. You can use it as a web framework as well as for server-site php scripts and daemons.

It mostly lacks proper documentation at this moment. Hope the demo helps you a little.

GitHub

This is just a quick announcement that we have migrated all our projects like PGSolver, MLSolver, FADecider and so on to GitHub. This allows you to get the newest versions of our software easily and to contribute your own code to our codebase.

Assuming that you might be an avid user of Subversion, you might want to read this tutorial which explains Git from a Subversion-point-of-view.

Once upon a time in Japan, one year ago

The following is an old blog post from last year that I’ve posted on a different blog that I’ve now closed. In restrospective not much has changed since then in my views. I have to admit, however, that some thoughts are fairly pathetic – I guess I was still overwhelmed by everything when I wrote it.

I’ve spent the first couple of days in Tokyo and went then to Kyoto. Tokyo is an incredibly large city packed with skyscrapers. If you go up one of the high buildings around the center to get a good view, it seems like the city is never ending, like the whole world is covered with skyscrapers. Like the Death Star (without being dramatic here). It’s almost surreal. Let there be no doubt, the skyline of New York is one of the most impressive sceneries, but compared to Tokyo, Manhattan is just a very small district in this gigantic city. It has multilayered streets all over the place. It is also the first city I’ve seen that has cars but no parking spots.

I’ve spent the rest of my time in Kyoto. It is the old royal city south of Tokyo, much smaller and greener than Tokyo. The best way to get around there is to get yourself a bike. My colleague was so friendly to give me one of his bikes which made it perfectly easy for me to visit all the places I was looking for. Japan in general and Kyoto in particular are beautiful. The people devote quite some attention to small little details. Every tree has been brought into perfect shape and each plant’s color is intense. Lime green. Crimson red. It’s just a form of art. It’s like stepping into a science fiction movie. Which sounds cliche and overgeneralizing but to me it was.

As you may know, one of the most important occasions for Japanese people is the so-called cherry blossom season, which is a two weeks long period in which the cherry blossom trees bloom. It usually takes place by the end of March, but this year the trees started to bloom a little later, so I was lucky enough to enjoy the trees at full peak. People are sitting under the trees and have picnics. It is a national celebration called “Hanami”, and most Japanese people get a warm tone in their voice when talking about their cherry blossom trees. You don’t really get it at first, but you start to understand after some time that the Hanami means a lot to them. It also shows you how much of a national tragedy Fukushima was, as they didn’t celebrate the Hanami last year.

When you go by the river in Kyoto, you see many people sitting around just looking at the river or the trees besides the river. They just enjoy the beauty of the moment. We have somehow forgotten how this works; we are always obsessed by using our time as efficiently as possible, even our free time.

For me, life has always been about choosing between hedonism and delayed gratification, and I think that is pretty typical for Western cultures. Hedonism, I always thought, might give you an instant gratification, a good fun, without giving your life any meaning. You’re missing the big picture and you might as well lose yourself in perpetuating meaningless stuff over and over again. Delayed gratification, on the other hand, seems to give you the big picture. It allows you to focus on doing something you might not enjoy too much, but you are promised to be rewarded later on for doing it.

I’ve always interpreted the carpe diems along these lines. Steve Job’s quote “Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life” seems to support this interpretation. You should always have the big picture in mind.

But what I now begin to understand is that delayed gratification tends to build up endless chains of in-order-to-thinking, postponing the gratification possibly infinitely long. “I’ll be dead soon” also means that you might as well be dead without being ever gratified for whatever it is you’re doing. Your big picture might not even work out as you planed it, and then you’re screwed.

Looking at the Japanese culture, I now realize that it is neither necessary nor desirable to choose between hedonism and delayed gratification. You should focus on the big picture, but you should also try to enjoy life every day. There is so much beauty in this world. We just need to relearn how to see and enjoy it. Today might by your last day, so don’t waste it doing stuff that you hate. Don’t waste it following other people’s dreams. I might be completely off the point to identify this as being a Japenese thing. (Edit: I am now pretty sure I was off the point.) Maybe it was just me thinking along these lines when I was there.

Religion in Japan obviously is quite different from ours. The original Japanese religion is Shinto and now coexists with Buddhism. There are many temples for both religions and some of them are even mixed. The Shinto religion is a polytheistic nature religion, where you basically have gods for everything. But instead of going there to just praise a lord, you pray for health or fertility or good luck in an exam. Your relationship with the god is much more demanding from your site. What I found particularly sympathetic were trees that they’ve put in front of the temples on which everybody can attach small papers that you want the god to take care of. If you think of fortune cookies, you basically take the good wishes with you and let the restaurant deal with all the bad stuff. It’s an optimistic and non-fatalistic way to deal with the future.

I probably don’t have to tell you much about the food: it’s incredibly good and fresh, and the Japanese dishes that we get in the Western world are only just ten percent of the different kinds of dishes that you get here. Many of them were exotic but also very tasteful. Be careful when trying Japanese sea cucumber though, which tastes pretty terrible, at least from my point of view. And even some Japanese people admitted that only a small fraction of them actually likes sea cucumber, so I think you’ll be on the safe side if you don’t like it.

In comparison to Japanese dishes, our food looks like it’s prepared by some uncivilized barbaric tribe. Instead of using elegant chop sticks, we get a set of tools to work on the food in order to get the stuff into manageable pieces. Even when you consider Western food like steaks or whatever, it’s a good question to ask why it’s not already cut. It would be much nicer to eat.

Everything, every ritual is carried out with the uttermost perfection. If people hand you stuff, they always turn it around in front of you before giving it you so that you can see the item in the right order. And they always give it you with both hands. This gesture somehow turns a simple action like giving you some stuff into an almost transcendental celebration.

People seem to have a fundamentally different understanding of how people should behave in society. Let me give you two examples. The public places and streets in Kyoto have no trash bins, but there is also no trash lying around. Not a single thing. I first thought that you’re probably going to be punished quite badly when being caught throwing stuff on the ground, but that’s not the thing. People see public places like their own gardens. The public is themselves. So why should they throw garbage on the ground? That just doesn’t make sense. Of course, our society has a completely different take on this. Throwing garbage on the ground in public places? As long as no one sees me, who cares?

Also small-scale stealing seems to be out of the picture. People let their bikes just stand around, leaving bags of stuff that they just bought in the baskets, and go into a shop to buy some other items. They just leave their bags and bikes without attendance. That’s amazing and it seems to just work like that.

People also seem to be generally friendly and kind. Although many do not speak English, people always try to help you, even if it takes them quite some time to accompany you to your desired destination. As a practical advice, you should take any directions that people give you with caution, as people sometimes rather give you a wrong direction than telling you that they don’t know where you should go. From what I’ve understood it’s about not giving you negative feedback. It’s about not losing your face, and that goes for both parties.

So go with the flow and try to be polite and sensitive yourself. I’ll definitely come back soon.

New paper on Cunningham’s Rule & a new Wiki for TCS

David Avis and myself have just finished a paper on Cunningham’s Rule for solving linear programs, featuring an exponential lower bound. Have a look at the preprint here and let us know what you think.

We also thought about a way of providing other scientists with additional material such as instances of linear programs, animations and so on. We decided to start a Wiki for theoretical computer science and add an entry on Cunningham’s Rule as a start. We invite other scientists to add their research to the Wiki!

Scientific Sermon: Computing Winning Sets From Winning Strategies

[latexpage]
In our last post of the series, we have seen how to obtain winning strategies in polytime if all you can do is compute winning sets (without strategies) in polynomial time. In this post, we’ll try to solve a related problem: given a pair of strategies for both players that are guaranteed to be winning on the winning sets of the game, can we extract these winning sets in polynomial time? The answer is, as we will see, yes.

In order to simplify the problem, let $G$ be a parity game and $\sigma$ be a player 0 strategy. We can define everything accordingly for player 1.
Define the player 0 $\sigma$-winning set as follows:
\[
W_0(G,\sigma) = \{v \in V \mid \text{all $\sigma$-conforming plays starting in $v$ are won by pl~0}\}
\]

It is easy to see that $W_0(G,\sigma) \subseteq W_0(G)$, and $W_0(G,\sigma) = W_0(G)$ iff $\sigma$ is a winning strategy on $W_0(G)$.

Hence, in order to solve our problem, it suffices to compute $W_0(G,\sigma)$.

Now we simplify our problem even more by considering the so-called strategy subgame. Given a game $G=(V,V_0,V_1,E,\Omega)$ and a player 0 strategy $\sigma$, the strategy subgame $G|_\sigma = (V,V_0,V_1,E’,\Omega)$ restricts the set of edges as follows:
\[
E’ = \{(v,w) \in E \mid v \in V_0 \Rightarrow \sigma(v) = w\}
\]
In other words all edges of player 1 remain in the game while all player 0 edges chosen by $\sigma$ are removed from the game.

It is not hard to see that $W_0(G,\sigma) = W_0(G|_\sigma)$, because the game on the right-hand side still includes the strategy $\sigma$. So we have a reduced our original problem to computing $W_0(G|_\sigma)$.

Why is that of any help? If you look closely, you’ll see that $W_0(G|_\sigma)$ is a so-called one-player game, i.e. a game in which at most one of the two players (in this case at most player 1) has more than one strategy. So our remaining task can be phrased as follows: How do we solve one-player parity games in polynomial time?

There are a bunch of algorithms that solve one-player parity games in polytime, but let us consider an algorithm very similar to the recursive algorithm that we have described earlier. You can also take a look at the Wikipedia page for an outline of the algorithm.

Our algorithm is recursive in the number of different priorities. If we only have one priority, we can immediately see who wins the whole game. If we have more than one priority, let $p$ be the largest one.

  1. Case $p$ is odd: Let $P$ be the set of all nodes with priority $p$. We compute the $1$-attractor $U$ of $P$. It is not too hard to see that $U \subseteq W_1$ with the attractor strategy of player 1 on $U$ as winning strategy. We remove $U$ from the game and continue with the rest.
  2. Case $p$ is even: Let $P$ be the set of all nodes with priority $p$. We compute the $0$-attractor $U$ of $P$ and remove it from the game, resulting in a game $G’$. We solve the game $G’$ by recursion and obtain winning sets $W_0’$ and $W_1’$. We compute the $1$-attractor $A$ in $G$ of $W_1’$ and remove it from the game as it is clearly won by player 1. This leaves us with $U \setminus A$ and $W_0′ \setminus A$.
    We now claim that $W_0′ \setminus A$ is won by player 0. Assume it’s not. Then, there must be a player 1 escape going through $A \setminus W_0′ \cup U$ reaching $W_1’$. But since $A$ is an attractor and the game is a one-player game, this is impossible. Let $X$ be the player 0 attractor of $W_0′ \setminus A$. Hence, we can remove $X$ as a save win for player 0 from the game.
    We are left with $U \setminus (A \cup X)$ with which we continue.

As an exercise, you can check that the algorithm runs in polytime.

In the next post of the series, we consider an assumption that you are allowed to make if you’re trying to find a polytime algorithm for solving parity games: you can assume that one of the two players, say player 0, wins the whole game. All you need to do, is to compute her winning strategy.

Java Keystore Creation from SSL Certificate

For Java-based servers that use SSL, you are usually required to convert your SSL certificate to a Java Keystore. It took me some time to figure out the right parameters and tools to create it, so here is the shortcut to creating the file.

Requirements:

  • Your domain name, i.e. “facebook” (without the top-level domain), which we will denote by [NAME] (we assume top-level domain “com” for the time being)
  • A password for the keystore which you will need for the Java server, which we will denote by [PASSWORD]
  • A program called keytool which should be part of your Java SDK
  • The SSL certificate files “[NAME].com.crt”, “ca.key” and “gd_bundle.crt”

You can then go a head and execute the following to commands which will create the keystore file “[NAME].keystore” for you.

openssl pkcs12 -export -in [NAME].com.crt -inkey ca.key -out [NAME].p12 -name [NAME] -CAfile gd_bundle.crt -caname root -chain
keytool -importkeystore -deststorepass [PASSWORD] -destkeypass [PASSWORD] -destkeystore [NAME].keystore -srckeystore [NAME].p12 -srcstoretype PKCS12 -srcstorepass [PASSWORD] -alias [NAME]

Applied Engineering: Exhaustive Search

In the last post of the series, we’ve introduced modules, functors and maps. We had ended with realization of the value assignment function that maps a given table assignment to a (ranking) value.

In this post, we will conclude the series and solve the optimal table assignment problem using OCaml. We will implement a function that searches through the space of potential table assignments to find (the) one with best possible value. We will use a very simple exhaustive search algorithm here.

First, we introduce a new module similar to the Map module we’ve already used previously. It models a set of objects and allows to add, remove, and find elements and to iterate over them efficiently. For our purposes, a set will be the right data structure for walking through the search space.

module IntSet = Set.Make(
    struct 
      type t = int
      let compare = compare
    end
)

let int_list_to_set int_list =
    List.fold_left (fun set_acc list_el -> IntSet.add list_el set_acc)
    IntSet.empty int_list

As before, we have to specify a compare function, and we use the default one once again. We also add a function int_list_to_set that converts a list of integers to a set of integers by folding the list and adding one element at a time using IntSet.add while starting with the empty set IntSet.empty.

If we want to get the sets of people and seats, we could use the mapping function as follows:

let people_set = int_list_to_set (List.map (fun (x,_) -> x) people)
let seats_set = int_list_to_set (List.map (fun (x,_,_) -> x) table)

Before we can turn to the exhaustive search algorithm, we consider one last type that is particularly useful in functional programs: the option type. It is a box that can contain at most one instance of some other type – in other words, it’s either an empty box or a singleton. It is already defined by OCaml, but it can easily be redefined:

type 'a option = None | Some of 'a

You can use the type as follows:

let x = None
let y = Some 5
match option_variable with
  None -> do_something
| Some i -> do_something_else

Back to our initial problem: finding an optimal table assignment. Just for fun, we will also try to find a worst table assignment, so the search algorithm should be given a comparison routine that allows the algorithm to select the more “appropriate” table assignment when comparing two.

We will therefore consider the following two comparison functions:

let better_selector assignment assignment' =
    if assignment_value assignment > assignment_value assignment'
    then assignment
    else assignment'

let worse_selector assignment assignment' =
    if assignment_value assignment > assignment_value assignment'
    then assignment'
    else assignment

Our exhaustive search algorithm will be called find_assignment, and it will be given one of the comparison routines as only parameter. We will then be able to create the following two convenience function searching for either a best or a worst assignment:

let best_assignment = find_assignment better_selector
let worst_assignment = find_assignment worse_selector

The basic idea of our exhaustive search algorithm is as follows. At any point in the algorithm we have four objects:

  1. the currently “best” assignment (initially will be None),
  2. a partial assignment (initially will be the empty map),
  3. the set of empty seats  (initially will be the set of all seats), and
  4. the set of persons without a seat (initially will be the set of all persons)

The algorithm will then proceed as follows. If there are no more people without a seat, the partial assignment (which is a full assignment at that point) will be compared with the currently best assignment, and the better one will be returned. If otherwise there are no more seats left, the algorithm will fail, because there are not enough seats for all persons. If there are still seats and persons left, the algorithm will pick the first person unseated and the first unoccupied seat, seat the person there, and recursively find the best assignment. Then, the algorithm will free the seat again, and seat the second person on the same seat and recursively find the best assignment again. This will be done for all persons unseated, so in the end, we’ll find a best assignment.

Here is the code:

let find_assignment selector =
    let people_left = int_list_to_set (List.map (fun (x,_) -> x) people) in
    let seats_left = int_list_to_set (List.map (fun (x,_,_) -> x) table) in
    let rec find reference assignment people_left' seats_left' =
        if IntSet.is_empty people_left' then
            match reference with
                None -> Some assignment
            |   Some other_assignment -> Some (selector other_assignment assignment)
        else if IntSet.is_empty seats_left' then
            failwith "There are not enough seats!"
        else
            IntSet.fold (fun person reference' ->
                let people_left'' = IntSet.remove person people_left' in
                let seat = IntSet.choose seats_left' in
                let seats_left'' = IntSet.remove seat seats_left' in
                let assignment' = IntMap.add person seat assignment in
                find reference' assignment' people_left'' seats_left''
            ) people_left' reference
    in
        match find None IntMap.empty people_left seats_left with
            None -> failwith "There must be one assignment."
        |   Some assignment -> assignment

So what do we get in the end? A best seating assignment gets a score of 7.5 and the assignment is:

Hank sits on seat #5
Karen sits on seat #4
Becka sits on seat #1
Mia sits on seat #2
Julian sits on seat #0
Trixi sits on seat #3

A worst seating assignment gets a score of -0.625 and the assignment is:

Hank sits on seat #0
Karen sits on seat #3
Becka sits on seat #1
Mia sits on seat #5
Julian sits on seat #4
Trixi sits on seat #2

This completes our visit to the functional language OCaml. If you would like to download the full source code for the example, please click here.

Enhanced by Zemanta