Dropping Perforce

In the last year, I’ve been using Perforce extensively and my opinion about it matured and radically changed with respect to what I expressed in one of my last posts.
Essentially, there are no faults in Perforce I was not aware of or some other problem inherent with Perforce. I just found out I’m far more productive with other tools.
The first problem is typical of my setup and has nothing to do with Perforce: my home server connection is faulty. Sometimes there is no way to access the server from outside and sometimes the 1666 port is not reachable because of firewalls. Of course, it is not Perforce fault: in this situations it is often the case I could not reach 22 as well (that is the port I use mainly with both git and mercurial through ssh). However, I’ve been able to place the repositories on an external server (where I can’t just install the Perforce server) and I could always use github.
The main advantage with both Mercurial and Git is that if I have connection problems, I can just go on and work locally. Perforce simply sucks in this situation. By the way, when I’m travelling it is quite frequent I’m offline. Both git and mercurial allow me to work with no burden added.
Perforce uses a model different from other modern Source Control Management Systems (SCMSs) which somewhat resembles old locking SCMSs. Essentially, if you have to edit a file you have to mark it for editing. This can have several advantages, however, I never got used to it. Moreover, since I used it to manage .configuration files in my home directory as well, to change a single bloody line of code I had to:

1. cd to the Perforce workspace directory
2. mark the file for editing
3. edit the file
4. commit

Actually, I found this rather cumbersome. I do prefer git/mercurial that do not set permission of all (most[0]) files as not writable.
Moreover, with my desktop computer, my apple laptop, my netbook (dualboot win+lin) and a workstation I had to test some software I already used all the workspaces the free version of Perforce allows me to have. This is rather unfortunate, as I often use virtual machines as well. Of course paying the bloody perforce license to do this kind of things is just stupid.
In the meantime, I found that distributed SCMs had none of those problems. Backup is regularly performed by Time Machine, so that was not an issue either, as long as I keep a clone of each repository on my MacPro. Moreover, the remote server where I keep some projects is very well managed and thoroughly backed-up.
I like the branching/cloning strategy superior (according to my needs) than the integrate stuff Perforce uses. I suppose we can prove them equivalent, however, I like git/mercurial better. I also changed my view on rebase and other commit editing stuff. Sometimes, I find them useful. After all it is my repository: I’m free to screw it up. This does not mean I will or should.
So I stopped moving projects from Mercurial to Perfoce. On the other hand I’m using git to extract projects from Perforce (git-p4, in fact). Well, it works nice. I will keep my Perforce server only for historical purposes, as imported git-p4 project may lose some branching information.

---

[0] Actually you can manually set an option in order to override the thing

Back in Black 2

Some things happened in the last two years. Two more Pycon Italia took place in Florence.
I completed a M.Sc. in Computer Science (in 2 years and 2 months, research dissertation included, which is something rare in my former). Two days after I graduated, I won a scholarship to attend a Ph.D. Course in Information Technology here in Parma, in the Dipartment of Computer Engineering.

This blog "re-edition" is kind of an experiment. Don't know if I have the time to write regularly here, nor if I like this platform. Essentially, I would have preferred a least web oriented platform (that is to say, writing posts offline). Blogspot should support this (I did import some of my old posts this way). Howerver, it seems that all of them can be imported. I don't really know why.

I also tried to write my own blog platform. Lack of motivation doomed this projects to failure. Moreover, I would need a rather costly high quality hosting which, by now, is an overkill as I can place massive amounts of data both on mobile me (public.me.com/enricofranchi) and on Dropbox.

I considered mobileme as a host, however, I would have limited choices on the platform (static HTML only). Rapidweaver/iWeb are not my cup of tea, either.

Thus, I chose an online blogging platform. As I already have lots of stuff with Google and I severly dislike Wordpress, I moved the whole thing here.

Perforce Conversion?

I’ve always been critical on user interfaces. In two different senses.

Bad user interfaces drive me crazy: I think designing crappy user interfaces should be a criminal offence.

On the other hand, I’ve always been on the “command line side” when speaking about development tools.

Of course I use graphical editor (gvim is a graphical editor, and Emacs as well). But the center of my development is the shell. From the shell I call the editor, from the shell I run the build tools, etc etc etc. That’s to say I’m pretty “against” bloated IDE’s, even though recently I started some serious experimentation with Emacs, but that’s wholly another story.

Back to SCM I recently took some SCM classes (a whole course on source configuration management, indeed). And during the course, we had some lab exercises with Perforce. I never used Perforce before that: I knew there was this Perforce thing which was better than CVS but costed lots of $$$ and was closed source and if you used that you were almost as evil as if you used Windows.

In the meantime I got bore with the free software movement, started using the Mac (which is almost as evil as Microsoft) and lots of proprietary software which makes my life far easier. However, many teams switched to subversion (which is far better than CVS as well) and some times later I experienced the distributed SCM revolution. I started with git which I rapidly dropped favouring Mercurial.

Using Perforce seemed to me quite anti-climatic, in this sense. But Perforce had something I always desired in SCM tools. That is to say a very good graphical interface. Especially for version graphs. And a graphical merge tool. An integrated graphical merge tool, so that you don’t have to find one when on Windows, for example.

Moreover, branching is a breeze. The integrate command is something wonderful. Indeed I never used that much branching in my home projects. Now I just can’t thing how could I do without it. In this sense, the GUI is rather didactical: I just can explore menus and commands and learn new functions of my tool.

Moreover, installing the server is really easy (differently from subversion). And my dyndns powered machine can host all my work. Very interesting indeed.

I forgot to mention: as long as I use less than 2 users, I can use the Perforce server for free. Since they are my own projects...

Emacs, Carbon Emacs and color-theme

I don’t like very much standard emacs theme, especially when in “GUI” mode (that is to say Carbon Emacs/Aquamacs if you are on the mac).
Luckily color-theme module does an excellent job. I have a long list of themes ready to be selected. In fact, for nostalgic reasons I like the “Classic” theme.
I wanted this theme to be automatically loaded when I start Emacs. Unfortunately default OS X Emacs does not have color-theme installed (and I don’t mind the way it looks by default in the terminal). So it was only a matter of conditionally branching between GUI emacs and terminal Emacs.
Moreover, I could not use (require ‘color-theme), for this would give error when run in the terminal version. This is my solution:

(defun my-color ()
 (load-library "color-theme")
 (color-theme-initialize)
 (color-theme-classic))
    (if window-system
     (my-color))

Missionaries, Cannibals and Prolog

Apparently, many generations of computer scientists have been concerned with the problem of letting cannibals and missionaries crossing a river with the very same boat.

Before them, logicians were looking for a way to have married couples doing the very same thing with slightly different inherent problems.

Centuries ago, the problem was that no woman should be with another man without her husband being present (this is now called a threesome). However, since women now are emancipated and nobody cares if a woman is with another man (with the possible exception of her own husband, especially when there are no football matches on TV), the cannibal problem seems more interesting.

It is widely accepted that if missionaries outnumber cannibals, they convert the cannibals. Since we believe in freedom of cult, no cannibal shall be converted. Someone may be familiar with another version of this problem, since once having people converted was considering a good thing, while having missionaries eaten was bad.

However, recently cannibals became vegans and until Churches will develop soy-missionaries the problem is how to let cannibals retain their own religion.

Basically, this is the job for a Prolog interpreter. Though humans solved this problem long ago, a human can only solve the problem for small numbers of cannibals and missionary (and though we hope both populations remain small in number, cannibals can always mate and missionaries can convert new people).

This is a short Prolog program that given an initial state (all cannibals and all missionaries on the same side of the river) and the desired final state (all cannibals and missionaries on the other side of the river), computes the strategy our poor bootman has to pursue in order to carry over the whole lot of people.

initial_state(mc, mc(left, bank(3,3), bank(0,0))).
final_state(mc(right, bank(0,0), bank(3,3))).

Above we say that the initial state has the boat on the left, three cannibals and three missionaries are on the left bank and no one is on the other one. The final state encodes what we have already said.

Now we have to describe possible moves:

move(mc(left, L, _R), Boat) :-
    choose_passengers(L, Boat).

move(mc(right, _L, R), Boat) :-
    choose_passengers(R, Boat).

choose_passengers(bank(C, _M), boat(2, 0)) :- 
    C > 1.
choose_passengers(bank(_C, M), boat(0, 2)) :- 
    M > 1.
choose_passengers(bank(C, M), boat(1, 1))  :- 
    C > 0, M  > 0.
choose_passengers(bank(C, _M), boat(1, 0)) :- 
    C > 0.
choose_passengers(bank(_C, M), boat(0, 1)) :- 
    M > 0.

Basically, when the boat is on the left bank, we choose passengers from the left bank. When the boat is on the right bank, we choose passengers from the right bank. We can only take 2 people on the boat. That means that, provided there is enough people on the bank, we can only carry 2 cannibals, 2 missionaries, 1 cannibal, 1 missionary or 1 cannibal and 1 missionary. Since the boatman is usually agnostic, the cannibal aboard with one missionary is not going to be converted.

The Prolog system choses one of the possible moves and proceeds. If the move is wrong, it back-tracks and tries another solution. Until the number of choices is small, it is rather efficient.

The predicates that describe how the system changes when one move is performed are:

update(mc(B, L, R), Boat, mc(B1, L1, R1)) :-
    update_boat(B, B1),
    update_banks(Boat, B, L, R, L1, R1).

update_boat(left, right).
update_boat(right, left).

update_banks(alone, _B, L, R, L, R).
update_banks(boat(C, M), left, 
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM - M,
    RM1 is RM + M,
    LC1 is LC - C,
    RC1 is RC + C.

update_banks(boat(C, M), right,
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM + M,
    RM1 is RM - M,
    LC1 is LC + C,
    RC1 is RC - C.

Eventually, we have to tell legal and illegal configurations apart. Basically, if in the bank we leave there are more missionaries than cannibals, we are breaking the law. If not, everything is fine (since the boatman works for free, so he does not have to pay taxes).

legal(mc(left, _L, R)) :-
    \+ illegal(R).

legal(mc(right, L, _R)) :-
    \+ illegal(L).

illegal(bank(C, M)) :-
    M > C.

The solution algorithm is trivial:

solve_dfs(State, _History, []) :-
    final_state(State).

solve_dfs(State, History, [Move|Moves]) :-
    move(State, Move),
    update(State, Move, State1),
    legal(State1),
    \+ member(State1, History),

solve_dfs(State1, [State1|History], Moves).

print_moves([]).
print_moves([M|Ms]) :-
    writeln(M),
    print_moves(Ms).

go :-
    initial_state(mc, State),
    solve_dfs(State, [State], Moves),
    print_moves(Moves).

We generate new moves and check if the updated state would be legal and if we did not get in the same state before (if it happens we are looping, the boatman becomes hungry and eats whoever is on his boat -- that’s the main reason why he does not travel with the empty boat).

The full source is here:

Using template programming for efficiency reasons

Suppose we want to write a

unsigned int pow(unsigned int n, unsigned int exp) 

function which computes the power of a given number.

A C implementation is rather trivial:

unsigned int
traditional_pow(unsigned int n, unsigned int exp) {

        unsigned int value = 1;

        for(unsigned int i = 0; i < exp; ++i) {

                value *= n;

        }

        return value;
}

Basically we could write the very same thing in C++. We could also perform some minor optimizations in the code in order to make it look more efficient. However, compilers are quite good in optimizing code. Indeed, they are better than humans.

Nonetheless, that function contains jumps. Notice that even though the exp parameter is known at compile time (which is a pretty common use-case), there is no way for the compiler to kill jumps short of doing a pretty expensive and thorough inter-procedural analysis. Which is not performed by gcc even using -O3.

The only result is having traditional_pow inlined in main. This is rather unsatisfactory: branching is among the more costly operations in modern CPU's.

We could try a recursive implementation:

unsigned int
traditional_rec_pow(
        unsigned int n,
        unsigned int exp,
        unsigned int acc) {
        switch(exp) {
                case 0: return 1;
                case 1: return acc;
                default:
                return traditional_rec_pow(n, exp-1, acc*n);
        }
}

unsigned int
traditional_rec_pow(unsigned int n, unsigned int exp) {
        return traditional_rec_pow(n, exp, n);
}

Here we are using an accumulator (a standard functional programmer's trick) in order to make the function tail recursive. With mild optimizations turned on, code generated for traditional_rec_pow looks like a less optimized version of traditional_pow (tail recursion is eliminated, though). Full optimizations yield a 74 lines long version of the function, where some special cases have been optimized.

We are very far from the intuitive idea of full optimization of pow if exp is known at compile time. We think that the compiler should be able to produce the very same code it would for the expression:
n * n * n * n * n * n

in case exp==5.

I promise you: we can do that.
I wrote the recursive functional version as an introduction to a templatic variant. The idea is that if exp is known at compile time, it can become a template parameter.

The structure remains similar, with template specialization used instead of explicit switch/if. This is even more readable for a functional programmer!

template<unsigned int exp> inline unsigned int
pow(unsigned int n, unsigned int acc) {

        return pow<exp-1>(n, acc*n);

}

template<> inline unsigned int
pow<1>(unsigned int n, unsigned int acc) {
        return acc;
}

template<> inline unsigned int
pow<0>(unsigned int n, unsigned int acc) {
        return 1;
}

template<unsigned int exp> unsigned int
pow(unsigned int n) {
        return pow<exp>(n, n);
}

Note that we give special cases for exp==1 and exp==0. They are needed because otherwise compilation would not terminate (well, it terminates with an error for implementation reasons).

Here some computation is implicitly performed at compile time. Suppose in the body of the main we call

pow<3>(3);

With no optimizations, the compiler generates some functions. There is the pow<1> specialization (which basically returns acc). Acc is the second parameter and according to OS X intel conventions that is 12(%ebp), while the return value is in %eax:

.globl __Z3powILj1EEjjj
                .weak_definition __Z3powILj1EEjjj
        __Z3powILj1EEjjj:
        LFB13:
                pushl        %ebp
        LCFI0:
                movl        %esp, %ebp
        LCFI1:
                subl        $8, %esp
        LCFI2:
                movl        12(%ebp), %eax
                leave
                ret
        LFE13:
                .align 1

For each exp value greater than one a function is generated. Each of this functions calls the one "before":

.globl __Z3powILj2EEjjj
                .weak_definition __Z3powILj2EEjjj
        __Z3powILj2EEjjj:
        LFB19:
                pushl        %ebp
        LCFI3:
                movl        %esp, %ebp
        LCFI4:
                subl        $24, %esp
        LCFI5:
                movl        12(%ebp), %eax
                imull        8(%ebp), %eax
                movl        %eax, 4(%esp)
                movl        8(%ebp), %eax
                movl        %eax, (%esp)
                call        __Z3powILj1EEjjj
                leave
                ret
        LFE19:
                .align 1
        .globl __Z3powILj3EEjjj
                .weak_definition __Z3powILj3EEjjj
        __Z3powILj3EEjjj:
        LFB18:
                pushl        %ebp
        LCFI6:
                movl        %esp, %ebp
        LCFI7:
                subl        $24, %esp
        LCFI8:
                movl        12(%ebp), %eax
                imull        8(%ebp), %eax
                movl        %eax, 4(%esp)
                movl        8(%ebp), %eax
                movl        %eax, (%esp)
                call        __Z3powILj2EEjjj
                leave
                ret
        LFE18:
                .align 1

Notice that __Z3powILj3EEjjj(pow<3>) calls __Z3powILj2EEjjj(pow<2>), which calls __Z3powILj1EEjjj(pow<1>). A part from this, most instructions deal with the stack (in order to create and destroy the current function stack frame) and multiply the first parameter for the second one, passing the result to the subsequent call.

Notice that no function contains conditional operations, tests or jumps a part from the call to the subsequent function in the chain. This is the kind of things optimizers shine on.

Indeed, even -O does the right thing. All the functions are inlined and the generated code is (not considering stack operations):

movl        8(%ebp), %eax
movl        %eax, %edx
imull        %eax, %edx
imull        %edx, %eax

Wow! This is how we would have written by hand. Notice that if we have multiple pow<n> calls, specialized ( and optimized code) is generated for each variant. For example this is for pow<11>

.globl __Z3powILj11EEjj
                .weak_definition __Z3powILj11EEjj
        __Z3powILj11EEjj:
        LFB17:
                pushl        %ebp
        LCFI0:
                movl        %esp, %ebp
        LCFI1:
                movl        8(%ebp), %eax
                movl        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %edx, %eax
                leave
                ret

From foldl to difference lists

Most declarative languages have lists. Usually this lists are either a nil atom (empty list) or a cons (a couple whose second element is a list). It is easy to see how we can append things to the head of the list.

In my former article we explored lists and foldl. Indeed, it is clear that we need an accumulator because appending at the end of the list is basically not possible (with decent performance). Appending at the end of the list means copying the whole list. Why? Consider how lists are done.

You have the head (say X1) and a pointer to another list. And this other list is built in the very same way. The last element has a pointer to an empty list.








If we want to add something at the end (even though we had a magical last::[E] --> E
function which got to the last element of a list in O(1) time) we need to "modify" the last element in the process. Since modifying is not allowed, we need to create another last element whose car (first element) is 3 (following our example) and whose second element (cdr) is a cons(4, []). Of course, at this point we should modify another element in the list. Basically we need to create a copy of the list. That's O(N).

However, if we bound the cdr of the last element not to an empty list but to an "unbound variable" we could simply add at the end cons(4, Unbound2), binding the Unbound1 to cons(3, Unbound1). Amazing... there are two major drawbacks.

First, we need logical variables. Which is simply true if we are using Prolog or Oz (sorry, no Erlang this time). In Erlang/Haskell you just can't do almost anything with unbound variables. In Prolog you can.

The second problem is our magical last function. We can build such a function, though it runs O(N). We can't do better. That means that appending at the end of a list, even though we left the tail of the list unbound, costs a lot. Well, usually O(N) is good, the point is that this operation is very low level and if we got a lot of O(N) stuff in inner "loops" the algorithm will suck.

Now, let us get back to the reverse with accumulator.

standard_reverse(Xs, Ys) :- standard_reverse(Xs, [], Ys).
standard_reverse([X|Xs], Acc, Ys) :-
    standard_reverse(Xs, [X| Acc], Ys).
standard_reverse([], Ys, Ys).

Let us change the argument order:

standard_reverse2([X|Xs], Ys, Acc) :-
    standard_reverse2(Xs, Ys, [X| Acc]).
standard_reverse2([], Ys, Ys).

Ok, this change seems unimportant to say the least. Let us do a further modification: instead of using two arguments for the reverted list and for the accumulator, let us use one single argument which includes both. For example Reverted-Acc.

diff_reverse([X|Xs], Ys-Acc) :-
    diff_reverse(Xs, Ys-[X|Acc]).
diff_reverse([], Ys-Ys).

Extremely nice! Here we have difference lists. Difference lists are a subject difficult to master. Their declarative meaning is quite obvious (and I will explain it in the next paragraphs), however their procedural/operational meaning is quite messy.

Basically a difference list is a way to represent an ordinary list. For example the list [1, 2, 3] can be represented by the difference lists [1, 2, 3, a]-[a] or by the difference list [1, 2, 3, a, 4]-[a, 4] or by [1, 2, 3]-[] or in another thousand of different ways, the most interesting of which is [1, 2, 3|X]-X. Notice that the latter unifies which any of the others. The careful reader may have noticed that now we may have a way to get to the last element of the list in order to add stuff in O(1). But let's not jump to conclusions.

Any ordinary list L can be represented as L-[], so it's easy to build a difference list representing an ordinary list. Unfortunately this difference lists is fully specified (if L was).

A classical problem in Prolog is appending two lists. This should be an O(M) operation, where M is the length of the shortest list. In fact in Prolog it is O(N) where N is the length of the first list:

myappend([], Xs, Xs).
myappend([H|T], Xs, [H|Ys]) :-
    myappend(T, Xs, Ys).

Now, let's benchmark the thing:

?- time(myappend([1, 2, 3], [2, 5], L)).
% 4 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
L = [1, 2, 3, 2, 5].

?- time(myappend([1, 2, 3, a, b, c], [2, 5], L)).
% 7 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
L = [1, 2, 3, a, b, c, 2, 5].

However, we can do that in O(1) using difference lists:

append_dl(Xs-Ys, Ys-Zs, Xs-Zs).
?- time(append_dl([1, 2, 3, a, b, c|Xs]-Xs, [2, 5]-[], Z)).
% 1 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Xs = [2, 5],
Z = [1, 2, 3, a, b, c, 2, 5]-[].

When applicable, this is very nice. There is not much more on difference lists, still having the ability to add elements at the end of a structure is great. How? Think about it:

push_back(X, L-[X|Xs]).
?- X = [1, 2|Xs]-Xs, time(push_back(3, X)).
% 1 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
X = [1, 2, 3|_G305]-[3|_G305],
Xs = [3|_G305].

Now we know how to put new elements to the front or to the back of a difference lists. That means we can build a deque.

Accumulators and Foldl in declarative languages

Using accumulators in declarative programming is common. Basically it is possible to convert not tail recursive functions into tail recursive ones using an accumulator.
Consider a very simple procedure: sum numbers in a list. The naive implementation is:

naive_sum([]) -> 0;
naive_sum([H|T]) ->
    H + naive_sum(T).

This one is not tail recursive. Every time the second clause matches, naive_sum is called and the return value of the recursive call is needed in order to compute the result. The standard way to write this one is:

standard_sum(L) ->
    standard_sum(L, 0).
standard_sum([], Acc) -> Acc;
standard_sum([H|T], Acc) ->
    standard_sum(T, Acc+H).

Notice that this way the last operation of each recursive calling clause is the recursive clause. This means that the new call can take the place of the old one. Simple. It’s so simple (and the pattern is so common), that it has a name foldl.

.
sum(L) ->
    lists:foldl(fun(X, Y) -> X + Y end, 0, L).

Basically, it's one of the primitives of functional languages. For example, in Haskell, it would be:

mysum lst = foldl (+) 0 lst

However, an Haskell programmer would write. This trasformation is known as eta-reduction.

mysum = foldl (+) 0

In Prolog, the naive and the "standard"sum becomes:

naive_sum([], 0).
naive_sum([H|T], Res) :-
    naive_sum(T, Res1),
    Res is Res1 + H.
standard_sum(L, Res) :-
    standard_sum(L, 0, Res).
standard_sum([], Acc, Acc).
standard_sum([H|T], Acc, Res) :-
    Acc1 is H * Acc,
standard_sum(T, Acc1, Res).

Since Prolog clauses can't return a value (because they are not functions, of course!), we need an extra argument which unifies with the result. Besides, in the Prolog version it is quite explicit that naive_sum can't be tail recursive. The difference between the naive and the tail recursive version is that the first one uses linear (O(N)) space and the latter uses constant (O(1)) space. Both are O(n) in terms of running time.
Another typical example on accumulators use is the "revert list" in Prolog. This is the naive version:

naive_revert([], []).
naive_revert([H|T], L1) :-
    naive_revert(T, T1),
append(T1, [H], L1). 

This is both not tail recursive and has a worse than expected running time: indeed it is O(N^2) while it should be O(N).
The first solution is using the built-in reverse predicate. It is even the right thing to do in production, but it is not useful to learn. :)
Let’s examine the following code:

standard_reverse(Xs, Ys) :- standard_reverse(Xs, [], Ys).
standard_reverse([X|Xs], Acc, Ys) :-
    standard_reverse(Xs, [X| Acc], Ys).
standard_reverse([], Ys, Ys).

Once again, we got tail recursion (using an accumulator). Basically we read the first element in the first list and we push it in the accumulator. When we take another element this one is pushed again (and the former is after this one). Then, when we finish the list, we unify the accumulator with the last value. This version is O(n) in time and space.
The Erlang version is extremely similar (and slightly more readable):

standard_revert(L) ->
    standard_revert(L, []).
standard_revert([X|Xs], Acc) ->
    standard_revert(Xs, [X|Acc]);
standard_revert([], Acc) -> Acc.

We can explore this definition further:

rev(_Op, [], Acc) -> Acc;
rev(Op, [H|T], Acc) ->
    rev(Op, T, Op(Acc, H)).
strange_revert(L) ->
    rev(fun(A, B) -> [B|A] end, L, []).

Here, instead of using the [X|Xs] constructor explicitly, we moved it in anonymous function. Notice that we also reverted the parameters. That is to say we don’t have a cons function:

Cons = fun(H, T) -> [H|T] end

but a :

Flipped_Cons = fun(T, H) -> [H|T] end

This is not unexpected. Let’s consider the definition of the foldl function itself:

foldl(_F, Acc, []) ->
    Acc;
foldl(F, Acc, [H|T]) ->
foldl(F, F(Acc, H), T).

They look very similar. Indeed they have almost the very same shape. We just have to flip a couple of parameters (foldl has the accumulator as the second parameter, not as the third one). We must notice that the foldl above is not akin Erlang foldl. In Haskell the type of foldl is:

Hugs> :type foldl
foldl :: (a -> b -> a) -> a -> [b] -> a

The binary operation has the accumulator as the first parameter (here it has type a), which is the same convention we adopted for the handmade foldl written above (from now on our:foldl). Erlang standard foldl follows another convention, the binary function has the accumulator as the second parameter.

foldl(Fun, Acc0, List) -> Acc1
Types  Fun = fun(Elem, AccIn) -> AccOut
Elem = term()
Acc0 = Acc1 = AccIn = AccOut = term()
List = [term()]

If we want to use foldl to build the reverse function we must chose which foldl to use. our:foldl needs the Flip (Flip_Cons) operation, while the standard Erlang foldl is fine with a Cons operation.

foldl_revert(L) ->
    lists:foldl(fun(H,T) -> [H|T] end, [], L).
foldl_revert2(L) ->
    our:foldl(fun(T,H) -> [H|T] end, [], L).

And here we are foldling in Prolog:

foldl(Functor, Acc, [H|T], Foldled) :-
call(Functor, Acc, H, Acc1),
foldl(Functor, Acc1, T, Foldled).
foldl(_Functor, Acc, [], Acc).
cons(T, H, [H|T]) :- !.

Extol of Declarativeness

Far too many programmers underestimate the beauty of declarative programming. This is something which cames from the industry: functional languages are traditionally under-employed and perceived as academic choices. In fact a lot of research has been done with Lisp and Prolog (mostly in U.S.A. and Europe respectively) in AI and formal languages fields.

However, declarative languages are very suited for the industry and to solve practical problems. Indeed, one of the most used domain specific languages (SQL) is a declarative language (even though not a turing complete one). Nobody thinks that SQL is academic. It’s just a good language for the task (and the underlying mathematical model).

Indeed, Prolog would be suited for the task as well (and Datalog is a proof), was it not turing complete (indeed, termination is a very good property to have in a query and data manipulation language.

Programming without explicit state is a nice property. A typical example is transactional semantics: in imperative languages implementing transactional behaviour is quite a hard task. Every operation must be logged (or check-pointed or both). Another option is some kind of shadow copy behaviour. Basically you access data through a pointer, which points to some kind of structure. If you want to edit the structure, you make a copy of it, edit the copy and set the pointer to point the copy if and only if every operation in the transaction has success.

 

 

 

All these operations are costly. Basically this kind of behaviour is free in functional languages. You return from a function and if you had no explicit side effects (which is not possible in haskell and easily avoidable inpr other functional languages) you automatically roll back to the state before the function call. This behaviour has some runtime cost, and this is the reason why functional languages are usually quite fast and not extremely fast (especially in certain tasks). However, its both easy to code (in fact you do not have to do anything explicitly) and rather optimized, since it’s done by the system (which should be rather efficient).

On the other hand, some other operations are quite more costly in functional environments. This happens when you often modify structures: that is to say when the algorithm uses on destructive write operations. Sometimes, declarative languages have limited support for “classical” variables: think about Oz cells, Lisp or OCaml. Erlang has ets, dets and mnesia tables. However, these algorithms are usually rather tricky to parallelize. In the most lucky environment some data decomposition comes natural, unfortunately this is not always the case. On the other hand, in declarative environments parallelism is almost free.

In Erlang parallelism is build into the very language core. In Haskell writing concurrent software is extremely easy (or at least not any more difficult than writing non-parallel software). Oz, with its dataflow variables, is also an interesting choice (and presents a concurrency model extremely educative and different from the ugly thread/synchronized Java vision). Basically in Oz variables themselves can be used to let threads communicate.

In many declarative languages variables can be bound or unbound. Unbound variables shall be bound before being used. That is to say that reading an unbound variable is a programming error (however, this does not go unnoticed and is quite different from reading an uninitialized variable/pointer). In Oz, if you have many threads and a thread tries to read an unbound variable, it hangs until someone binds that variable.

This is a nice way to do concurrency: variables are used. They can be used to build barriers, for example. They are a good IPC primitive as well. Since in Oz variables are logical variables (read-only, once bound), there is no need to worry about multiple writes. Nice.

Do not program defensively. (Sure?)

How it is true that pragmatics matters in programming! That is to say, best practices in a given environment/platform may be bad practices in another. For example the following lines are quoted from Erlang's Programming Rules as recommended from Ericsson:

A defensive program is one where the programmer does not “trust” the input data to the part of the system they are programming. In general one should not test input data to functions for correctness. Most of the code in the system should be written with the assumption that the input data to the function in question is correct. Only a small part of the code should actually perform any checking of the data. This is usually done when data “enters” the system for the first time, once data has been checked as it enters the system it should thereafter be assumed correct. 

There is a whole generation (more likely a couple or more) of C programmers grown with the idea of defensive programming. Which may be a good idea, indeed, especially considering the quite large bug number of C programs. Java programmers more or less share the same idea (further misled by a wrong idea of typing, but that's entirely another story). 

Here, we find that defensive programming not only is not considered a good practice: it's even considered a bad practice. Indeed, the Unix operating system, about 30 years ago used a similar idea: less code to manage erroneous conditions (in comparison with Multics). Kernel Panic and reboot. Of course there is quite a difference between "not recovering from errors" and "not doing defensive programming".

The point is that well written code can't be put in a "wrong" state by a wrong input. At least it should not. A typical example is a buffer overflow: as far as I'm concerned, a legitimate behaviour is a core dump (as long as the dump is not user accessible, of course!). The wrong behaviour is corrupting memory (which is C behaviour out of the box).

Back to Erlang, the example code of the section is:

%% Args: Option is all|normal
get_server_usage_info(Option, AsciiPid) ->
Pid = list_to_pid(AsciiPid),
case Option of
all -> get_all_info(Pid);
normal -> get_normal_info(Pid)
end.

Which is quite explicative: if Options is neither all nor normal, Erlang "crashes", it does not do something implementation dependent or lets the user crack the process. Besides, Erlang was created from real needs from the industry, thus is a practical language suited to solve practical problems (and is also a beautiful functional language).

I want to stress the industrial nature of Erlang to show that the advise does not come from academics or inexperienced programmers unaware of "real world" needs. Maybe there is still hope.