Category Archives: Technology

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.

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.

Setting up a Rails project with Heroku, Eclipse and Domains

I always forget the single steps to create a new rails application that has a staging & production environment, can be deployed to Heroku and has the nameservers properly configured. So here’s the outline (so you and I never forget it):

1) Create Application

rails new $APP
cd $APP

2) Create Eclipse ./.project file

<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
  <name>$APP</name>
  <buildSpec>
    <buildCommand>
      <name>com.aptana.ide.core.unifiedBuilder</name>
    </buildCommand>
  </buildSpec>
  <natures>
    <nature>org.radrails.rails.core.railsnature</nature>
    <nature>com.aptana.ruby.core.rubynature</nature>
  </natures>
</projectDescription>

3) Update Gemfile

source 'https://rubygems.org'

gem 'rails'
gem 'jquery-rails'
gem "jquery-ui-rails"
gem "anjlab-bootstrap-rails", "~> 2.0.4.4", :require => "bootstrap-rails"

group :assets do
  gem 'sass-rails'
  gem 'coffee-rails'
  gem 'uglifier'
end

group :development do
  gem 'sqlite3'
end

group :production, :staging do
  gem "pg"
  gem "therubyracer"
end

gem "devise", ">= 2.1.2"
gem "cancan", ">= 1.6.8"
gem "rolify", ">= 3.1.0"

4) Install Bundle

bundle install --without production staging

5) Clean Up

rm ./README.rdoc
rm ./public/index.html
rm ./public/favicon.ico
rm ./doc/README_FOR_APP
rm ./app/assets/images/rails.png

6) Create Root Controller

rails generate controller root index

7) Update Routes

root :to => 'root#index'

8) Create Git Repository & Init

git init
git remote add origin $URL

9) Overwrite ./.gitignore

.bundle
db/*.sqlite3*
log/*.log
*.log
/tmp/
doc/
*.swp
*~
.DS_Store

10) Commit

git add .
git commit -a -m "Initial Commit"
git push origin master

11) Create Heroku Endpoints & Push to Heroku

heroku create $APP-staging --remote staging
heroku create $APP --remote production
git push staging master
git push production master

12) Prepare Heroku Domain

heroku domains:add --app $APP www.$APP.com

13) Setup your Domain

  • Domain Forward to http://$APP.herokuapp.com
  • NameServer Settings: www.$APP.com CNAME $APP.herokuapp.com

A) References

Applied Engineering: Modules, Functors and Maps

[latexpage]
In the last post of the series, we introduced the functional programming language OCaml and basic types like lists. We applied higher-order functions like map to them (recall that a higher-order function essentially is a function taking a function as an argument).

Recall that we’ve considered the list of people:

let people = [
  (0, "Hank");
  (1, "Karen");
  (2, "Becka");
  (3, "Mia");
  (4, "Julian");
  (5, "Trixi")
]

If we now want to look up the name of the person with id, let’s say, 4, we can only walk through the list until we find an entry that matches the respective number. This is a very inefficient algorithm for looking up data (its worst-case and average-case complexity are both linear). We can be much faster using a different data structure that stores all entries in order and applies binary search. The classic structure is a balanced tree and all database system rely on such organization of data. Luckily, OCaml already provides a module for handling such data. A module can be seen as a namespace for types and functions that belong together.

We will use the map module that allows to quickly look up a key and return a corresponding value – in our case, the keys would be the people’s ids and the values would be the people’s names. The map module is general enough to allow arbitrary keys and arbitrary values to be stored in a balanced tree.

If you think about that for a minute, you might see an issue here. In order to organize the data in the tree, you need to be able to compare keys with each other, so they can be arranged in the right order. But how would the map module compare stuff with each other if the map module doesn’t know how to compare certain types? Well, it doesn’t. We have to specify how our keys should be compared with each other.

How do we explain to the map module how our keys can be compared with each other? By parametrizing the map module by an auxiliary module that explains the key comparison. More precisely, we map the auxiliary module to a concrete map module by a functor (a mapping from a module to a module).

module IntMap = Map.Make(
  struct
    type t = int
    let compare = compare
  end
);;

On other words: we define the module IntMap to bethe  Map.Make-Functor applied to the auxiliary module with key type int (our people’s ids) and the comparator compare (OCaml provides a “magic” compare function for every type that we use here – for ints, it’s the natural ordering on integers).

Next, we want to convert our list of people to an IntMap, mapping ids to people’s names. In order to build and use the map, we need three IntMap-functions: one to create an initial empty IntMap-instance, one to add assignments to it and one to look up keys.

IntMap.empty: 'a IntMap.t
IntMap.add: int -> 'a -> 'a IntMap.t -> 'a IntMap.t
IntMap.find: int -> 'a IntMap.t -> 'a

Recall that ‘a is a type variable. In our case, the type variable corresponds to the value type – and since the map does not care about the specifics of this type, we don’t have to fix it via any auxiliary modules and functors.

The first function, IntMap.empty, simply returns an empty instance of an IntMap. The second function, IntMap.add, takes a key, a value and an existing IntMap as arguments and returns a new IntMap that added the new key-value assignment to the existing IntMap. The third function, IntMap.find, takes a key and an existing IntMap as arguments and returns the corresponding value (assuming that the key-value pair is present).

Our conversion function therefore looks as follows:

let int_list_to_map int_list =
	let empty_map = IntMap.empty in
	let rec helper rest_list acc_map =
		match rest_list with
			[] -> acc_map
		|	(domain, range)::rest_list' ->
                                helper rest_list' (IntMap.add domain range acc_map)
	in
		helper int_list empty_map

The function starts with an empty map and then walks recursively through the last, adding the assignments one by one to the map. We can now use it to generate our people mapping and use it to look up people’s names:

let people_map = int_list_to_map people
let people_func p = IntMap.find p people_map

Recall that in our initial post, we had two more lists – the list of constraints (which person likes to sit next to which person) and the table configuration (which is seat is close to which set). Every entry in each of these lists is a triple – two ids and a value (how likable / how close).

let constraints = [
	(0, 1, 1.0);
	(0, 2, 1.0);
	(0, 3, -0.5);
	(0, 4, -1.0);
	(1, 0, 0.75);
	(1, 2, 1.0);
	(1, 3, 0.5);
	(1, 4, 0.5);
	(1, 5, -0.75);
	(2, 0, 0.5);
	(2, 1, 0.5);
	(2, 3, 0.75);
	(2, 4, -0.75);
	(3, 0, 1.0);
	(3, 5, 0.5);
	(4, 1, 0.5);
	(5, 0, 1.0);
	(5, 1, -0.5)
]

let table = [
	(0, 1, 1.0);
	(0, 4, 1.0);
	(1, 0, 1.0);
	(1, 4, 1.0);
	(1, 2, 1.0);
	(1, 5, 0.5);
	(2, 3, 1.0);
	(2, 1, 1.0);
	(2, 5, 1.0);
	(2, 4, 0.5);
	(3, 2, 1.0);
	(3, 5, 1.0);
	(4, 0, 1.0);
	(4, 1, 1.0);
	(4, 5, 1.0);
	(4, 2, 0.5);
	(5, 3, 1.0);
	(5, 4, 1.0);
	(5, 3, 1.0);
	(5, 1, 0.5)
]

We again want to convert both lists to maps, but in this case, the key consists of two ids, i.e. is an int product-type. We need to create a new module IntMap2 by mapping a new auxiliary module (that allows to compare key pairs with each other) to a map:

module Int2Map = Map.Make(
	struct 
	  type t = int * int
	  let compare = compare
	end
)

let int2_list_to_map int2_list =
	let empty_map = Int2Map.empty in
	let rec helper rest_list acc_map =
		match rest_list with
			[] -> acc_map
		|	(domain, domain2, range)::rest_list' ->
                                   helper rest_list' (Int2Map.add (domain, domain2) range acc_map)
	in
		helper int2_list empty_map

let constraint_map = int2_list_to_map constraints

let table_map = int2_list_to_map table

We again want to define functions to look up the respective values by key pairs. There will be cases, however, in which certain key pairs don’t exist in the mappings. We didn’t specify, for instance, any constraints for the two seats 0 and 2 with respect to each other, because we implicitly assign them the proximity value 0. Similarly, this holds true for the constraints. We need to make sure, therefore, that our look up routines catch the exception in which no key pair could be found.

let constraint_func p q =
	try
		Int2Map.find (p, q) constraint_map
	with
		Not_found -> 0.0

let table_map = int2_list_to_map table		

let table_func p q =
	try
		Int2Map.find (p, q) table_map
	with
		Not_found -> 0.0

We say here, try to execute the look up code provided by the Map module. If it raises the exception Not_found, return 0.

Next, we need to define a new type for handling dinner table assignments. It should be a map from a person’s id to a seat id – in other words an int IntMap.t. To play around with it, let us setup a test assignment that assigns each person the seat with the same id:

let test_assignment = int_list_to_map [(0,0); (1,1); (2,2); (3,3); (4,4); (5,5)]

So far, so good. To get a feeling of what’s going on, let us print the table assignment. We will make use of another higher-order function provided by the Map module that allows us to walk through the map:

IntMap.fold: (int -> 'a -> 'b -> 'b) -> 'a IntMap.t -> 'b -> 'b

This looks pretty complicated, so let’s check the details. The first argument is function that accepts a key and a value, and maps some data (of type ‘b) to updated data (of type ‘b again). The second argument is the map and third argument is some initial data (of type ‘b). Overall, the routine routines data of type ‘b. Internally, the function starts with initial data and the first key-value-pair and calls the user function to obtain an updated data object. It continues in that fashion with the second key-value-pair until all key-value-pairs have been handled. The final updated data object is then returned.

We will make us of it build a textual representation of dinner table assignments:

let format_assignment assignment =
	IntMap.fold (fun person seat acc_format ->
		acc_format ^
                people_func person ^
                " sits on seat #" ^
                string_of_int seat ^ "\n"
	) assignment ""

How does it work? It starts with the empty string “” and adds a line for every assignment pair in the user defined function. The current string is given by the accumulator variable acc_format. The output accumulator is built by concatenating (denoted by ^ in Ocaml) the accumulator variable with the person’s name and the seat number.

Applying that to our test assignment, we get the following output:

# print_string (format_assignment test_assignment);;
Hank sits on seat #0
Karen sits on seat #1
Becka sits on seat #2
Mia sits on seat #3
Julian sits on seat #4
Trixi sits on seat #5

We conclude the post by realizing the assignment value function of our initial post that allows us to rate a given dinner table assignment:
\[
\sum_{p,q \in People} constraint(p,q) \cdot proximity(assign(p), assign(q))
\]
We make extensive use of the fold operation again (which corresponds to the sum operation here):

let assignment_value assignment = 
	IntMap.fold (fun p _ acc_value ->
		IntMap.fold (fun q _ acc_value' ->
			acc_value' +. constraint_func p q *.
                        table_func (IntMap.find p assignment)
                                   (IntMap.find q assignment)
		) people_map acc_value
	) people_map 0.0

For the record, the assignment value of our test assignment is 3.5. We should find an assignment that yields a higher value, right? We will see how to accomplish that in our final post in the series.

Tech Scene: Payment Models for Digital Goods

In the history of the internet, a couple of different payment models have emerged for digital goods. There are various types of digital goods, many of them existed long before the internet: Books, News, Music, Videos, TV-Shows, TV-Channels to name a few. Some goods are inherently digital like virtual goods in computer games.

In the beginning of the internet, there was only one payment model: free digital goods sponsored by advertisement, and we still have that model today. But there were only a couple of digital goods available in the old times, mostly news articles.

Newer models emerged since then. The music and movie industry for instance decided to offer most of their goods by direct payment per item. For virtual goods like in Zynga games, the freemium model disrupted major parts of the gaming industry – you can play the games for free, but once you’re hooked, you have to pay in order to succeed.

The disruption of the direct payment model for music is now driven by services like Spotify or Simfy. Instead of letting you pay for every single item, you have to pay a flat fee per month to listen to any music you want to. You don’t own the titles anymore, you just get the right to listen to them as long as you’re paying for the service.

Which payment model is best depends on the type of goods you offer. I think there are three categories of digital items: collectable, consumable and enabling items. A collectable item has an intrinsic value to people and they want to own it (even after consuming it). Consumable items on the other hand only have value to people before they’ve consumed them. An enabling item allows people to improve on something existing, so they need to have it to get one step further.

Of course, no item falls completely into one category and it also depends on the mindset of the customer where to put an item. To me, books and movies are mostly collectable items which is why we still mainly use direct payment for such goods. TV-Shows and music on the other hand is more of a consumable item – sure, there are some shows and some music that pop-culture aficionados want to watch or to listen to all day long over and over, but most shows are only consumed once or twice. Likewise, we usually listen to a number of songs until we get bored of them and move on. We don’t really care whether we still have them. Hence, flat fee models are on the move for consumable items. It goes without saying that the freemium model is best fitted to enabling items such as virtual goods.

What category is news? Most of the time, it is a consumable good, because news are usually only relevant to you until they’re not new anymore. Because that’s what news is – it’s new. Sure, news portals do contain articles that have long-term value, but mostly it’s only relevant for a short time. So what’s the right payment model? In the old times of the internet, it was free to the consumer and sponsored by advertisement. It was okay for some time that this payment model didn’t produce much revenue, because real news publishing was still happening offline. Nowadays, the digital news portals have to generate more revenue as the offline revenue stream is breaking down.

So what other payment models are there? News publishers transfers their issue-based offline system to the net by offering flat fee subscriptions on a monthly or yearly basis, or per-issue payment like in the offline world. Considering news issues on a fine granular level, you pay a flat fee for reading any number of articles in the issue. So that’s the flat fee model for a consumable item. Makes sense. But there are still not enough people falling for that, as there are still many free news websites.

There is a tendency of news publishers to introduce (soft) paywalls to account for that. A (soft) paywall restricts your access to digital goods – articles in particular – by requiring you to pay a very small fee per article you’re reading or by allowing you a small number of articles to read for free until you either have to pay on a per-article basis or by subscription.

Time will tell whether per-article payment works. Since articles are mostly consumable goods of short relevance with many free competitors, I would rather suggest a different payment model. It should neither be for free, nor be a flat fee, nor be a per-article payment. The problem with the per-article payment is that you can’t really give people a demo of what they’re going to get. Then again people are hesitant to pay for the article as they might regret it in case the article didn’t meet their expectations.

My suggestion therefore would be a model that I call “capped satisfactory payment”. It consists of two rules. You pay on a per-article basis, but if you didn’t like the article after reading, you can get your money back for the article. Obviously, you combine that with a fair-use policy and tracking of rejected articles, so you exclude free-riders. The second rule is to cap the overall payment for read articles per issue. In other words if a reader really digests a lot of articles in an issue, he shouldn’t pay much more than the flat fee for the whole issue in the first place. To my mind, this model communicates clearly that you take the readers’ opinion seriously while reducing the hurdle for the consumer to read and pay for an article dramatically.