“The city’s central computer told you? R2D2, you know better than to trust a strange computer!” – C3PO

Two days ago I was on a fantastic presentation of Roman Cheplyaka
from Barclays Capital, leading British Investment bank about their Haskell based Financial application. It was nice surprise that Haskell, even though it is considered as almost exclusively academic language is used in such a gigantic investment bank.

Their system is built using internal DSL language that is specified using Haskell’s Type classes. These DSL language constructs are very lispy in their nature and because they don’t like writing lisp code that much (they hate parenthesis as 90% of mortals ) they created Haskell functions that are truly in the spirit of Haskell and they create that lispy code in the background. On the other hand there are rules how these DSL constructs are translated into Haskell again and therefore they are able to use Haskell to build internal DSL that can use every regular Haskell feature and on top of that their DSL constructs in the type safe manner. But their internal framework is typeless lispy framework. I almost instantly remembered the Greenspun’s Tenth Rule and this is apparently also true for Haskell.

I personally think that their solution clearly shows the power and expressiveness of dynamically typed lisp dialects because homoiconicity is so important for domain driven design approach and for programming in general. They created lisp inside Haskell to be able to overcome the constraints of static typing and also needed to create explicit rules for DSL translation. He also pointed out the problem that the more you are safe the more you’re constrained and the more you’re unsafe the more you’re free. I personally don’t see the reason to write let’s say twitter client with programming language that has memory management freedom like C or C++ but having computational freedom(I have compiz so I’m comfortably memory numb ) of lisp is so convenient that it seems to me that it is always better to write program in that functionally bottom up style. Macros are much easier than to write n levels of different abstractions just to end up with some lisp subset.

Few days ago, I watched a fantastic tutorial about overtone programming where the guy used awesome emacs. I was completely unaware that there is such a good extension like auto-complete-mode.

It completely changes the way you use your editor. Now it is much mode like modern IDEs

I wanted to use that with LaTeX so fortunately there is extension for autocomplete mode that enables completition of LaTeX commands. I’ve installed it and it worked only after typing M-x ac-start; it didn’t worked as I type and I couldn’t see why. After few hours of googleing and reading source code and docs I’ve found that it doesn’t work with flyspell mode enabled. It is mentioned in the secion of known bugs but I was lazy to read the whole documentation . I have added startup hook for latex to start flyspell mode automatically. After I’ve disabled flyspell it worked as a charm . So if anyone has the same problem just disable the flyspell mode

Now I just need to find that awesome color scheme that the guy has in his emacs

Last few days I was on a vacation with my girldfriend, my good buddy and his girlfriend and I’ve brought with me K&R to read if I had some time. While there were playing rummy I’ve finally learned how pointers really work and wrote my first complete and usable C program
I had started to read that book several times but this is the first time I actually wrote something that was complicated enough to really help me understand pointers.

This is my version of quick sort (what else I’m going to write )

This is my header file. I’ve created struct to connect data structure and it’s size into single argument to the functions (main reason was to play with structs and malloc, nothing more )

quick_sort.h

#include <stdlib.h>

typedef struct {
    int *data;
    int size;
} Array;

void quick_sort(Array *array);

Here is the quick sort implementation.

quick_sort.c

#include <stdio.h>
#include "quick_sort.h"

static int smaller(int a, int b) {
    return a < b;
}

static int larger(int a, int b) {
    return a > b;
}

static void checkPtr(void* ptr) {
    if(ptr == NULL) {
        printf("Not enough memmory");
        exit(EXIT_FAILURE);
    }
}

/*
 * returns array elements safisfying comp function.
 * comp is called as comp(array_elem, array[0](which is pivot))
 */
static Array *find(Array *array, int (*comp)(int, int)) {
    int pivot = *array->data;

    /* create output array. maximum for the size is one
       less the input size(because first is pivot) */
    int *data = malloc((array->size-1) * sizeof(int));
    checkPtr(data);

    /* create output struct and set it's data */
    Array *result = malloc(sizeof(Array));
    checkPtr(result);

    result->data = data;

    int added = 0;
    /* populate output array with desired elements
       skip first one because it is the pivot */
    int i;
    for(i=1; i < array->size; i++) {
        int current = *(array->data+i);
        if((*comp)(current, pivot)) {
            *(data+added) = current;
            added++;
        }
    }
    result->size = added;
    return result;
}

/*
 * join smaller, larger and array[0](which is pivot)
 */
static void join(Array *array, Array *smaller, Array *larger) {
    int pivot = *(array->data);

    /* add smaller to the start of array */
    int i;
    for(i=0; i < smaller->size; i++) {
        *(array->data+i) = *(smaller->data+i);
    }
    /* add pivot */
    *(array->data+(smaller->size)) = pivot;

    /* add larger after pivot */
    const int index_offset = smaller->size + 1;

    for(i=0; i < larger->size; i++) {
        *(array->data+i+index_offset) = *(larger->data+i);
    }
}

static void swap(int *data) {
    if(*data > *(data+1)) {
        int tmp = *(data+1);
        *(data+1) = *data;
        *data = tmp;
    }
}

void quick_sort(Array *array) {
    if((array->size == 0) | (array->size == 1)) {
        return;
    }

    if(array->size == 2) {
        swap(array->data);
    }

    Array *smaller_elements = find(array, smaller);
    quick_sort(smaller_elements);

    Array *larger_elements = find(array, larger);
    quick_sort(larger_elements);

    join(array, smaller_elements, larger_elements);

    free(smaller_elements->data);
    free(larger_elements->data);
    free(smaller_elements);
    free(larger_elements);
}

And here is the test code

quick_sort_test.c

#include <stdio.h>
#include "quick_sort.h"

void print_array(Array *array) {
    int i;
    for(i = 0; i<array->size; i++) {
        printf("%02d ", *(array->data+i));
    }
    printf("\n");
}

int main (int argc, char** argv) {
    int *data = malloc((argc-1) * sizeof(int));

    int i;
    for(i = 0; i < argc-1; i++) {
        /* nth element of data is (n+1)-th cmd line argument */
        *(data+i) = atoi(*(argv+i+1));
    }

    Array *a = malloc(sizeof(Array));
    a->data = data;
    a->size = argc-1;
    printf("before\n");
    print_array(a);
    quick_sort(a);
    printf("after\n");
    print_array(a);

    return EXIT_SUCCESS;
}

I’ve written this in about two hours..but I’ve hit one vary nasty bug(at least for me ). The code worked but only for the arrays up to 16 elements . I had no idea why and finally I found that problem was in first malloc call. It was

    int *data = malloc((array->data)));

I thought it should work because I didn’t know how malloc works. I thought it can either allocate desired amount of memory or that it can also allocate amount needed to store passed object. Why it worked up to 16 elements… I have no idea . Anyway..afther changing that to

    int *data = malloc((array->size-1) * sizeof(int));

it worked as expected. After these kind of bugs, you really start to appreciate garbage collector

This was very interesting and fun coding session and I will definitely continue to play with C when I have some spare time

I’ve stumbled across fantastic make tutorial/ and I’ve made my first fully hand written make file . I’ve made some changes so here is my customized version that really fits small projects.
To use this make file just copy it in the empty directory and change EXECUTABLE_NAME variable to the name of your app. After that run

make create-project 

and here you go

Put your sources in src dir and headers in include.
Object files will be put in obj dir and executable will be put in the bin directory.

You need to also change the names of your header files and object files in _DEPS and _OBJ variables.

INCLUDE_DIR=./include
OBJ_DIR=obj
SRC_DIR=src
BIN_DIR=bin
EXECUTABLE_NAME=quick_sort_test
CC=gcc
CFLAGS=-I$(INCLUDE_DIR) -Wall

_DEPS=quick_sort.h
DEPS=$(patsubst %,$(INCLUDE_DIR)/%,$(_DEPS))

_OBJ=quick_sort.o quick_sort_test.o
OBJ=$(patsubst %,$(OBJ_DIR)/%,$(_OBJ))

$(OBJ_DIR)/%.o : $(SRC_DIR)/%.c $(DEPS)
        $(CC) -c $< -o $@ $(CFLAGS)

$(EXECUTABLE_NAME): $(OBJ)
        $(CC) $^ -o $(BIN_DIR)/$@ $(CFLAGS)

clean:
        rm -f $(OBJ_DIR)/*.o $(BIN_DIR)/*

create-project:
        mkdir $(SRC_DIR)
        mkdir $(OBJ_DIR)
        mkdir $(BIN_DIR)
        mkdir $(INCLUDE_DIR)

I’m currently writing my Msc thesis using Emacs so I am learning more and more new cool features of Emacs. Today I’ve found very nice looking plugin called Weblogger that enables you to write blog posts directly from Emacs(Horay!!! all keyboard shortcuts available ) It is available on ELPA so it is very easy to install it. After that you need to call

M-x weblogger-setup-weblog

and after that you can start writing new posts with

M-x weblogger-start-entry

After you’ve finished you can add it by just saving the buffer as usually with C-x s. If you then change it and then save again it will be updated .

I think I’m starting to do more and more things from Emacs
Anyone knows good file browser extension?

I have been using Emacs for Clojure development for quite some time
and I used M+. key to navigate through Clojure code. It seemed that this works
but often very strangely. I realized that this is because it is not using Emacs etags but rather Slime’s version that works only files that are loaded in current Emacs session. I wanted to use etags and searching on the net I found some advices how to do that.

Create file containing regular expression for Clojure syntax as suggested in mentioned blog post. Let’s say put it /opt/clojure.etags.

/[ \t\(]*def[a-z]* \([a-z-!]+\)/\1/
/[ \t\(]*ns \([a-z.]+\)/\1/

Based on this advice, I created Emacs function that creates TAGS file for maven project. I use Maven for building clojure projects so this is very usefull function to create TAGS file for /src directory under the project root. Just copy this function into your .emacs file

(defun clojure-maven-etags (project-root)
  "Create tags file for clojure project."

  (interactive "DProject Root:")
  (eshell-command
   (format "find %s/src -name \'*.clj\' | xargs etags --regex=@/opt/clojure.etags -o %s/TAGS" project-root project-root)))

Now you can easily create TAGS file for all defs from your maven based Clojure project. Call it with M-x clojure-maven-etags.

Lazy evaluation in one very nice feature found in programming languages with functional programming capabilities such as lisp, haskell, python etc. It mans that evaluation of variable value is delayed to the actual usage of that variable.

It means that for example if you wanted to create a list of million elements with something like this
(defn x (range 1000000)) it is not actually created, but it is just specified and when you really use that variable for the first time, for instance when you want 10th element of that list interpreter creates only first 10 elements of that list. So the first run of (take 10 x) actually creates these elements and all subsequent calls to the same function are working with already existing elements.

This is very useful because you can create infinite lists without out of memory errors.The list will be large just how much you requested. Of course, if your program is working with large data collections it can hit memory limit in the usage of these infinite lists.

On the other hand corecursion is dual to recursion. What this means? Well just like the recursive functions, which are expressed in the terms of themselves, corecursive variables are expressed in the terms of themselves.

This is best expressed on the example.

Let’s say we want list of all prime numbers. We can say that Nth prime number is the number larger than N-1th prime and not dividable by any of N-1 prime numbers before him. This is where corecursion comes into place.
When you specify the some element of list in the terms of last or some other previous elements of the same list that is called the corecursion.

For our example the code in Clojure is like this:

(def primes
     (lazy-cat [2 3]
               (map next-prime (rest primes))))

(defn next-prime
  [last-prime]
  (first (drop-while #(not (prime? %))
                     (range last-prime Integer/MAX_VALUE))))

(defn prime?
  [num]
  (every? #(not (zero? (mod num %)))
          primes))

Here we defined list primes which is a concatenation of vector [2 3] and “something” that is returned from function map. The important thing is that this map is called on (rest primes) so it effectively depends on primes recursively. primes is defined with map which runs on (rest primes).

map calls provided function next-prime for each element in the list (rest primes)

The catch is to see the start of evaluation. What is (rest primes)? It is everything except the first eleement: 3, x1, x2, x3, x4……
because with lazy evaluation we can have “unknown values” which are still not evaluated.

so first time next-prime is called with argument 3 because it is the first element of (rest primes)

how next-prime works? well, it received the number 3 and it knows that next prime is larger than 3 so it creates lazy list from 3 to Integer.MAX_VALUE and then for each number it tries function prime? which checks whether the number is actually prime number. By our definition prime number is first larger number than last found prime number not dividable by any previous prime number.

so first time we call prime? with 4
primes is 2,3
then we find that 4 is dividable with 2

then we try next value from list which is 5 and we call prime? with 5
primes is 2,3
it is not dividable with 2 and 3

next-prime returns 5 as next prime number so now (rest primes) is not 2, 3, x1, x2…. but 2, 3, 5, x2…..

since we already executed map on element 3 we now call next-prime on next element which is 5

next-prime again creates list from 5 to Integer/MAX_VALUE and calls for each prime?

first value is 6
primes is 2,3, 5
6 is dividable with 2 it is not prime

next with values 7
primes is 2,3, 5
it is not dividable with any of 2, 3 and 5
so next-prime returns 7 and now list is 2, 3, 5, 7, x3, x4, ……

and by this we created list of all primes numbers and we can get get, for example list of first 20 numbers with (take 20 primes). We created only those first 20 numbers and nothing more.

next time we can call (take 21 primes) and then oly 21st element will be actually calculated. Others are calculated and stored in primes variable.

In the simmilar fashion we can create list of Fibonacci numbers

or list of factorials.

list is 1, 2, 3, 4, 5
and the factorial list is 1, 2, 6, 24, 120

the catch is to see that this can be expressed in corecursive way because 5! is 4!*5, the 6! is 6*5!
the value of element N is some function on element N-1..

in the simmilar was that prime N is the function of of previous N-1 elements

this is left as exercise

While reading design milk rss feeds
I stumbled upon intersting image

even though this image is not related to the software engineering, i think it emphasizes important principle in software design. When you for instance, look at original EJB platform, it is built to be “good”; Everything is nicely separated, million interfaces etc. everything done by the book. And then you need to explain a little ruby kid why he has to write dozen of files to create hello world app. It was designed to be “one to rule them all”, you know, to be silver bullet for everything. And therefore it imposes certain limitations that at first, seemed like good ideas..

But look at other software systems, like for instance spring or rails. You don’t ever wonder why you do something, it is obvious that it’s the only way to be done. You never think of architecture of the system, you just use it. Their design is transparent, you understand it from the start and you feel good about it.

I’ve heard one good quote about software design

When I’m working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong. – R. Buckminster Fuller

This is very true. If you try too much to create software to be architectural miracle from the start, you’ll probably end with something that was good idea, but ended up like a piece of over-architecture junk. But if you first try to create something where architecture is almost invisible and good as much as possible for that particular problem and then refactor it as your problem evolves over time, your will end up with architecture which is very suited to the problem. Not something that is overly complex and seems like a good way to write software, but in reality it is not.

Today I moved my website to the new hosting. Since 2003 I was using the servers at my university and this is the first time i actually paid for hosting .
So maybe you’ll have some troubles next few days but i can’t do anything to speed up updating of DNS caches

Recently I wanted to prepare my CV and because I know that LaTeX is extremely powerful text preparation system i searched on the Internet for some kind of template for CV resumes….

I found one very simple and elegant document class called moderncv.
This is how my CV looks like when using this document class.

This document class is very easy to use. This is just an starting template. You can add as many sections as you like and also omit some parameters to the commands. Also you can add your bibliography for example for published articles and conference papers.

\documentclass[11pt,a4paper]{moderncv}
\moderncvtheme[red]{casual}         

\title{your Curriculum Vitae title}
\firstname{Name}
\familyname{Lastname}
\mobile{Mobile}
\phone{Phone}
\email{Email}
\homepage{Homepage}
\extrainfo{Extra Info}
\photo[64pt]{picture}
\quote{Subtitle}
\address{Address}{City, Country}

\begin{document}
\maketitle

\section{Section Name}
\cvline{Subject}{Description.}
\cventry{Time}{Position}{Company Name}{City}{Country}{Description}
\cvcomputer{Skill}{Description}{Skill}{Description}
\cvlanguage{Language}{Proficiency}{Description} 

\end{document}

Those commands highlighted with red colour are the ones that are related to the moderncv package, the others are standard LaTeX commands You can change the colour of the resume, the type of the theme(casual or regular) and also you can omit some of the personal information if you don’t want it in the CV. In each of the moderncv specific command you can omit some parameter but you need to place empty brackets(if you don’t do this compiler will complain).

Here is the output of this simple LaTex file and here are the source files for this example.