Thursday, December 30, 2010

IntelliJ 10 and PyCharm

So now I'm downloading IntelliJ 10. I already bought the upgrade, without even trying it. I am a very happy IntelliJ 9 user, the upgrade price is reasonable (especially because I qualify for academic discounts).

Moreover, I tried Pycharm and startup times have improved greatly. And IntelliJ is also very fast, almost comparable with some not too lightweight editors. I think I can live without many of the improvements they did to the X version of IntelliJ, however faster startup + mercurial + github integration for me are worth the price. And then there is the question of Python and Ruby plugins, which alone can make the difference.

If the Python plugin is as good as PyCharm (and it should) then I can do without upgrading WingIDE. WingIDE is still GTK (which bugs me a lot). And it is a nice IDE, I love it. However, it lacks refactoring. Ok, most refactoring in Python can't be done automatically, however simple local variables renames could (and both Eclipse and PyCharm do them).




Saturday, December 25, 2010

PyCharm...

I must buy just because of this:

Well... more on this here

Friday, December 17, 2010

Networks: an introduction

I usually do not discuss here things closely related to my research area. This is for a number of reasons: for example, I usually write this blog in my spare time and I focus on different subjects. There are exceptions... for example I'm writing about PageRank (here, here and I have not yet finished), which is rather close to a specific part of what I'm doing (no, I'm not re-writing Google from scratch ;) ).

Nowadays I have lots of interest in network and graph theory. I like it because it keeps my maths fresh (I miss maths a lot, in fact) and most computer science and engineering subjects can be better grasped with a sound and complete (pun intended) understanding of graph theory.



I recently found a wonderful book, which is "Networks: An Introduction" by M.E.J. Newman. This is not about "computer networks" (though they are dealt with). It is about the maths behind networks. It is a single book which cover all the basis of network theory.

Different kinds of networks are described (biological, social, information). Network properties, metrics and measures are defined, and results on average properties for each kind of network are given, together with the large-scale description of such networks. Then, a whole lot of computer algorithms are presented. Models to generate networks (random graphs, Barabasi and Albert model, Strogatz and Watts model) are explained and eventually network processes (epidemics, percolation, node removal/addition, dynamic systems, search) are presented. Basically, it's all there.

Moreover, the book is very readable, even with little experience on the subject and each part is mostly independent. That is to say, it is possible to start reading almost from any point, which makes the book a great reference. But it is also a great introduction to the subject. And > 300 references mean that the book is a great hub to start further explorations of the world of networks.

, ,

Wednesday, December 15, 2010

Introducing Page Rank Maths

In my previous post, I started introducing Google PageRank. Now I'm starting to dig into PageRank maths. PageRank definition is not very "computation oriented".

r(Pi) = Pj ∈ Li  r(Pj)

|Pj|
(2)
There is not a clear temporal ordering of pages or any other sensible starting point. Hopefully, an iterative method may converge to the result. So we subscript the rank with a number indicating the step and express the (i)-th step in terms of the (i−1)-step:

rk(Pi) = Pj ∈ Li  rk−1(Pj)

|Pj|
(3)
Of course, we are not happy with the whole "may-converge" thing and would rather have some precise results. The first step is using some convenient notation: formula 2.2 is easy to grasp but awkward to manipulate.
The idea here is express the equations in matrix form. Let L = (eij) be the adjacency matrix of our graph. In other words:

eij =
1    if there is a link from i to j
0    otherwise
(4)
Then we consider the matrix H = D−1·A, where D = max(I, D) and D is the diagonal matrix of the degrees of the nodes. In Python we can compute H with:
import numpy as np

def h_matrix(adjacency_matrix):
    degrees = np.sum(adjacency_matrix, axis=1)
    degrees[degrees==0] = 1
    return np.dot(np.diag(1./degrees), adjacency_matrix)


# ...

The H j-th row can be interpreted as the distribution of probability for jumping from node j to each other node. If our graph is the web, H has billions of rows (and columns) but in average each page has about 10 out links. H is a very sparse matrix, indeed.
Let π be the rank-vector. Then we can reformulate the problem as:
πT = πT·H
(5)
Basically we are looking for the eigenvector associated with the eigenvalue λ1 = 1. The idea here is to use the power method. The power method is an iterative method that computes the eigenpair (λ1, π) of a matrix A. A must satisfy some basic hypotheses for the power method to work. Let {λ1,…,λn} be the set of eigenvalues of A, then it must be true that |λ1| > |λ2| ≥ … ≥ |λm|. As a consequence, λ1 ∈ \mathbbR.
Then it is possible to compute (λ1, π) with:

yn=Axn
      
xn + 1 = yn

cn
(6)
Then xn→ x and cn→λ1.
Here cn is a scaling factor; e.g. λ1, ||Anx0||, the component of yn of maximal magnitude. Now, the fact that we suggested λ1 as a possible scaling factor is not a mistake: it is proved that the actual Google matrix has λ1.
Moreover x0R(A−λ1I), where R(M)={v|v=Ax}. However, in practice "most" starting vectors x0 are good.
If H were a usable Google Matrix, things would be very nice. H is essentially the matrix of a random walk over the graph. We could just see the whole thing as a Markov process. More on this can be found in [3].
The analogy with Markov processes here can give us some insight on the problems with the H matrix. If we interpret nodes as states, we can see that a closed class of state (possibly a singleton) would be a serious issue. And any node with no outgoing links constitutes such a class.
In the Markov chain interpretation, if such a node is reachable, then we would just remain there. Such nodes would be rank sinks. In such a setting, every web site with no outgoing links would acquire a rank far superior to its actual importance. Using Markov chains terminology, the H matrix is substochastic.
Another problem is related to cycles. E.g., consider the matrix
C =
0
1
1
0

Then: C2n = I and C2n+1 = C. As a consequence we cannot expect to converge (notice, here we have eigenvalues with same magnitude, so we know that the power method is not going to work).
Luckily enough, these problems are rather easy to fix modifying the matrix. More on this, later!

References

[1]
M. Franceschet. PageRank: Standing on the shoulders of giants. arxiv.org.
[2]
M.E.J. Newman. The structure and function of complex networks. Arxiv preprint cond-mat/0303516, 2003.
[3]
M.E.J. Newman. Networks: An Introduction. Oxford University Press, 2010.
[4]
L Page and S Brin. The pagerank citation ranking: Bringing order to the web. 1998.



Lisp and Scheme

Here (scheme-vs-common-lisp) an interesting comparison between Common Lisp and Scheme.
Looks rather objective. I actually prefer Common Lisp... the only two I really hate are:
  1. 2-namespaces... but funcalling is not bad as I remembered, so I really don't care anymore (perhaps "hate" is a bit of a misnomer here)
  2. no standard prescribed TCO (though the implementations I chose support it, so after all I DGAF)... ah, no call/cc. However, I don't like call/cc (perhaps I have not grasped it fully)

Well... In fact I quite like that in Lisp I have conditions (which are just a generalization of exceptions). I'm quite used to using exceptions. And Lisp also offers throw/catch and named blocks which may be used to jump.

It looks like unwind-protect and call/cc do are not good friends. Moreover, I do not fiddle very often with control structures. However, I write quite a lot of code making use of control structures... error conditions and such.



Tuesday, December 14, 2010

TTH and listings

TTH is a beautiful TeX/LaTeX to HTML converter. Its main focus is converting math formulas without resorting to images. An example can be seen here.

It is easy to use, easy to install and work acceptably. The only trouble I had so far regards including source codes. TTH supports verbatim but does not support lstlisting. Consequently I defined the conditional \iftth with
\iftth
It is by default false (under latex) but it is true when running tth. This way I can have conditional commands such as:
\newcommand
    \sourceinclude[1]
    {\iftth \verbatiminput{#1} \else \lstinputlisting{#1} \fi}

Doubling the RAM...

gives new life even to a macpro!

T8AJ4E7HMJFJ

Monday, December 13, 2010

Other applications of the ideas behind Page Rank

One of the problem a search engine has to solve is to sort the potentially very long list of matches for a given query with a sensible ordering. Sensible here means that ideally the more interesting results come first.
Many strategies could be applied here (and there is a lot of ongoing research on the subject). Many complex strategies are already applied. However, the basic idea [4] Google used was very simple (as an idea) and very robust.
It is easy to see that the idea was simple. Let r(Pi) be the ranking of page Pi, Li be the set of pages linking to Pi, and |Pi| be the number of outbound links of |Pi| then:

r(Pi) =

Pj ∈ Li 
r(Pj)

|Pj|
(1)
Simple, indeed. With the minor problem that we have no starting point to trigger the computation. Luckily enough, iterative methods come to help. More on this in a few paragraph. I have not yet clarified the "robust" part.
In fact the kinds of ideas underlying the PageRank are rather old. Similar ideas have been spotted in bibliometrics, econometrics and sociometrics. This is not to be considered a defect (lack of novelty), rather I consider it a feature as in "already field-tested".
Using words, PageRank states that a page is important if many important pages link to it. Which is not different from the usual definition of importance of journals, where a journal is important if many important journals contain articles referring to articles in that journal. Well, in the journal world things are easier as there are far less journals than web pages and there is a clear temporal order that can be used. Moreover, articles usually cite only papers written before them (at least until some research has a paper describing his implementation of time-machines, then he could easily refer to articles not yet published).
In 1949 Seeley proposed to "measure" the popularity of a child (he was researching relationships in children social group) considering the popularity of the children which enlisted him among his friends. That is, once again, something like Pi = f(F11,...,F1k), where F1j is a child who listed 1 among his friends. The very same criterion can be applied to recommendations.
Leontief won Nobel Prize for Economy for his ideas on econometrics on the input-output model, which is yet an application of the same underlying ideas. Here I won't give further details. These example come from [1] where further details are given.


I explore further how to compute the PageRank here.

Sunday, December 12, 2010

Combinatory Logic in Lisp

Many year ago, I was introduced to a formalism called "combinatory language". I quite fell in love with it, but that my personal taste. Combinatory logic, according to Wikipedia, was originally introduced as a notation to remove variables from logic. However, in the presentation I'm familiar with variables are used [1]. In fact, I have seen it a computation model: combinatory language is proved equivalent to lambda calculus (trivial) and as such it is also a computation model (and a possible foundation for functional programming).

The fundamental units are combinators, that is to say elementary (higher order) functions. The result of the computation comes from function application (but the elementary functions are so simple that it is possible to see implement the evaluation just as a simple rewrite system). In fact, just two combinators are needed S and K (definition follows). Usually the I combinator is defined as well, but that can be defined in terms of K and S, so it is not "primitive".

Quite interestingly, it is possible to use combinatory logic to define regular first order logic. So it can be a model for mathematics as well... and some rather important (and difficult to prove) theorems in logic are rather elementary and easy results in combinatory logic. But well... to the metal.

Let us have an infinite sequence of variables (lowercase) and a finite or infinite sequence of constants (uppercase), including the three fundamental combinators I, K, S.  Variables and constants are atoms. The definition of combinatory term is as follows:
  1. Every atom is a combinatory term
  2. If X and Y are combinatory terms, (XY) is a combinatory term as well
A combinator is a combinatory term whose atoms are only S, K, I. Variables are disjoint from constants.

Since combinatory logic is very "operative" we define the fundamental computation tool, which is the weak reduction.
  • IX -> X
  • KXY -> X
  • SXYZ -> XZ(YZ)
  • X -> X
where the parentheses have the usual meaning (that is to say xzu where u is the result of evaluating yz). Right now I don't want to introduce axioms regarding variables. Now I rewrite the combinators as "usual functions" to clarify what they really do:
  • I(f) = f
  • (K(a))(x) = a
  • (S(f, g))(x) = f(x, g(x))
  • (B(f, g))(x) = f(g(x))

The B combinator is not fundamental, and can be easily defined as S(KS)K. So now we have a pretty clear idea of what combinators are. I corresponds to the identity function. K is "like" a function returning a constant whatever arguments we pass. In fact K is a "function" which given something yields the function always returning that something. B is a function composition operator. S is a bit harder to understand (but wait to see the Y combintor! ;) ),

My first significant lisp program years ago was the implementation (in lisp) of the the basic computable functions (primitive recursive and mu operator, IIRC what I did). I thought that a nice example of another lisp program could be implementing the combinators in Lisp. After doing some more theory (e.g., we haven't yet stated how to "compute" programs or represent numbers), we can go for the implementation.



References
  1. R. Hindley, B. Lercher, J. P. Seldin, Introduction to combinatory logic (CUP Archive, 1972), p. 170




, , , , , ,



Powered by ScribeFire.

Saturday, December 4, 2010

Pointfree programming

I have to admit that, nowadays, I'm not a huge fan of Haskell. It may be that I learned it when "Real World Haskell" did not exist. I learned on excellent Hudak's book, and although it is a very nice book (as implied by the adjective "excellent") I think that the focus is quite too academical (which is an awkward criticism from me). When learning a language I like books which give me the pragmatic of the language (that is to say "how I'm I expected to write the code") but also practical examples. Something to hack myself in order to dig into the language.

Unfortunately back then most of the "nicer" example could be run easily on Windows or Linux but not OS X (some graphic library, IIRC). So... I grow tired of Haskell rather soon (it's not nice to code continuously referring to library indexes to see if what you are doing has already been done and trying to understand the logic of some very idiomatic piece of code you have not been introduced to).

RWH does a very nice job in teaching Haskell (and perhaps you can read Hudak as a second book, if you need). However, it came somewhat too late. Perhaps another time I will start with Haskell again.

Moreover, while code in RWH is idiomatic and readable, I think that many programming styles popular in the Haskell community (judging from pieces of code I stumbled upon surfing the web) tend to be so clever that "I'm not able to debug them". Not unless I have decomposed them...

For example, I quite like the idea that everything is curried. I got a BSc in maths before turning to computer science and I have seen plenty of complex function. I'm used to functions that take other functions as argument, return functions. Functions (sometimes called operators) which bridge spaces of functions and similar stuff.

Consequently I quite like the idea that + is a unary function which returns a unary function (that is to say an "adder").

def add(x):
    def adder(y):
        return x + y
    return adder

This is a bit awkward in Python, however you can use stuff in the functools module to do the trick. However, Haskell is built around this very concept. If you just write (+ 1) you have the "increment" function. While I think this is nice (after all I don't really like to write a full lambda to do such a thing), abuses are easy to spot.

Another thing I rather like is the fact that you can omit "unused" parameters.

E.g., it is perfectly ok to write:

inc = (+ 1)

Which makes sense: (+ 1) is the function which adds 1 and we just give it the name inc. So far so good. If you are not very happy with operators, the classical example is:

sum = foldr (+) 0

instead of

sum' xs = foldr (+) 0 xs

(these examples come from the point-free Haskell guide). And I agree (to a point). In fact I still believe that there should be just one way to do things; however, Haskell guides make it very clear that the first version is preferred. Moreover, you can always write down the second variant and then remove dummy variables.

What I especially like is how it stresses the functional nature of the language: you don't "define" (defun?) functions, you just give them names. Functions just are. Ok, to much lambda calculus lately.

The point is that Haskell programmers tell you that:

fn = f . g . h

is clearer than
fn x = f (g (h x))

On that I strongly disagree. Since I have been introduced to the function composition operator, I have found that most people get it wrong. I have no idea (afterall you just substitute the composition operator with an open parentheses and everything is fine). Now, that is not necessarily a problem: not everyone is destined to become a programmer (and an Haskell programmer).

On this I found some support in the lisp/scheme/clojure community:

Avoid functional combinators, or, worse, the point-free (or `point-less') style of code that is popular in the Haskell world. At most, use function composition only where the composition of functions is the crux of the idea being expressed, rather than simply a procedure that happens to be a composition of two others. Rationale: Tempting as it may be to recognize patterns that can be structured as combinations of functional combinators -- say, `compose this procedure with the projection of the second argument of that other one', or (COMPOSE FOO (PROJECT 2 BAR)) --, the reader of the code must subsequently examine the elaborate structure that has been built up to obscure the underlying purpose. The previous fragment could have been written (LAMBDA (A B) (FOO (BAR B))), which is in fact shorter, and which tells the reader directly what argument is being passed on to what, and what argument is being ignored, without forcing the reader to search for the definitions of FOO and BAR or the call site of the final composition. The explicit fragment contains substantially more information when intermediate values are named, which is very helpful for understanding it and especially for modifying it later on.

which comes from here. Of course this can be an instance of "Lisp syntax is not very good at doing this kind of things, so you should not even try them". And it is not hard to see that (compose foo bar) could not be used extensively as function composition in Haskell, as it carries more syntactic noise. Clojure actually has builtin comp and partial functions:

clojure.core/comp([f] [f g] [f g h] [f1 f2 f3 & fs])  Takes a set of functions and returns a fn that is the composition  of those fns. The returned fn takes a variable number of args,  applies the rightmost of fns to the args, the next  fn (right-to-left) to the result, etc.clojure.core/partial([f arg1] [f arg1 arg2] [f arg1 arg2 arg3] [f arg1 arg2 arg3 & more])  Takes a function f and fewer than the normal arguments to f, and  returns a fn that takes a variable number of additional args. When  called, the returned function calls f with args + additional args.

Which is useful, are used sparingly.

However, when you start freely mixing the various features of Haskell syntax you have got a real mess. At least in my opinion. Functions taking multiple parameters in Haskell are really just unary functions returning functions.

E.g., (A x B) -> C in fact is just A->(B->C).

From the point of view of a programmer coming from another language, you can "bind" only a subset of the arguments of a function. Which, in Haskell terms means that you simply get a function instead of just a value.

For example, (map (*2)) is a function that doubles all the value of a list. It's just like that! And if you don't have the list in a variable: you can compute it on the fly (e.g. filter odd [1..10], which means take only the odd values from the range [1..10] -> 1, 3, 5, 7, 9).

The first tentative fails:

Prelude% map (*2) filter odd [1..10]
%interactive%:1:9:
    Couldn't match expected type `[a]'
           against inferred type `(a1 -> Bool) -> [a1] -> [a1]'
    In the second argument of `map', namely `filter'
    In the expression: map (* 2) filter odd [1 .. 10]
    In the definition of `it': it = map (* 2) filter odd [1 .. 10]

Here the problem is that the "second parameter" of map should be a list. However the compiler finds "filter". Filter is a perfectly legal value for a function, only it has type (a1 -> Bool) -> [a1] -> [a1] and not [a]. In other words, we are passing a function where a list is expected.

Essentially the compiler just reads the arguments and tries to "fill" the parameters. In this case, however, it does not work. We should have written map (*2) (filter odd [1..10]).

See the parentheses? They do the right thing. Now the compiler knows that it is supposed to pass map the return value of the filter function.

However, now we have a "moral" problem: we have parentheses. Point free... does not work! We would have to write

f lst = map (*2) (filter odd lst)

instead of

f = map (*2) (filter odd)

In fact the latter is not valid. (filter odd) has type [a]->[a], not [a]. Still, I the use of parentheses is very readable in my opinion. But we want to use point free, remember? "Luckily" map (*2) has type [a]->[a] and (filter odd) also has type [a]->[a]. They can be composed! How?

map (*2) . filter odd

Now, if you are a real Haskell programmer, you are going to like it. I somewhat like it... it has some perverse elegance, I have to admit. Then imagine that you can compose this way any function. Haskell programs are highly composible.

In fact it is not hard to write very very complex functions just chaining other functions with . (and $). E.g., which is the function that computes the sum of all the perfect squares of a sequence of numbers, excluding the ones smaller than 50?

sum . dropWhile (< 50) . map (** 2)

The point is that there is no limit to the nonsense you can do this way.

Friday, December 3, 2010

Closures in imperative settings: hidden and not so hidden problems (Python)

Nowadays, the number of essentially imperative languages that have some degree of support for closures is not a small one. Even languages which traditionally do not have closures like C have been extended in order to support something which roughly behaves like a closure. E.g., the Apple blocks extension goes in this direction. Perhaps one day I will discuss this feature. Even the good old gcc nested function extension (with all its drawbacks) does the job. And in Java you can do with an anonymous class. Of course Python and Ruby have "almost" full support for closure. What do we mean with "almost full"? The point is that a closure is essentially a functional concept. In functional languages you usually don't change the contents of a variable. Either you can't (Haskell) or you shouldn't (Lisp). On the other hand imperative languages do not have the restriction and imperative programmers, even those using closures, do not think that it is a bad thing.  However, both Python and Ruby suffer greatly on this. In our first example we are using closures, although many imperative programmers may have written code like that without being aware they were dealing with closures. Consider a simple graphical program using the omnipresent Tkinter framework.
import Tkinter as tk

class Window(tk.Frame):
    def __init__(self, root):
        tk.Frame.__init__(self, root)
        self.value = 0
        def inc():
            self.value += 1
            self.label.config(text=str(self.value))
        self.label = tk.Label(text=str(self.value))
        self.label.pack()
        self.button = tk.Button(text="Increment", command=inc)
        self.button.pack()

root = tk.Tk()
w = Window(root)
w.pack()
tk.mainloop()
It may be not clear, but inc is a closure. In fact the self variable is a local variable to the __init__ method and is referenced inside inc, defined in __init__. The above code runs fine. However, if we do not define value as an attribute of self, errors arise. Consider this code:
import Tkinter as tk

class Window(tk.Frame):
    def __init__(self, root):
        tk.Frame.__init__(self, root)
        value = 0
        def inc():
            value += 1
            self.label.config(text=str(value))
        self.label = tk.Label(text=str(value))
        self.label.pack()
        self.button = tk.Button(text="Increment", command=inc)
        self.button.pack()

root = tk.Tk()
w = Window(root)
w.pack()
tk.mainloop()
It looks right, but it is not. In fact, a "UnboundLocalError: local variable 'value' referenced before assignment" exeception is thrown. Why? When executing value += 1 does not find any local variable value, because value is not local: it's local to the enclosing scope. And is not global. So the error. If you are wondering what happens if value is global (and in inc you ask for a global value variable)... things work. But every time a global is used a programmer dies somewhere. Who knows who's next... In fact in Python closure can read variables from the enclosing scope. They can modify them (for example using methods which mutates them, or like in the first example, rebinding an attribute). However, you can't "rebind" the variable. And since integers are immutable, += 1 "assigns" a new integer.

, , , ,

Powered by ScribeFire.

Thursday, December 2, 2010

Connected. Take this REPL, brother, and may it serve you well.

Ok... slime is finally come to reason.
Reading documentation usually helps.

Yeah... auto-completes too.

, ,

Powered by ScribeFire.

Wednesday, December 1, 2010

Land of Lisp (part 1)

I did not want to buy this book. I have a pretty busy schedule and I /knew/ that if I had it on my desk it would have made things worse. Moreover, Lisper have the tendency to make every other language inadequate; considering that I am (unfortunately) not going to use Lisp in the near future, that would be on the demotivational side of things. Just hope to be able to use clojure, but that's another story.

The introduction is one of the funniest pieces of half-technical writing I ever read. In the rest of the book the humor is present and that is great value. I don't consider myself a Lisp expert; however, it's about a decade since my first exposure to Lisp, I have recently dig into scheme and used quite an amount of functional, logic, dynamic, high-level and whatever languages. That means that I was afraid the first chapters of the book would just be very boring to read (because I already know the contents), but perhaps a necessary evil to familiarize with the concepts and the philosophy of the book, which could prove useful when reading more advanced stuff.

Well, I was right and I was wrong. I was right since it's pretty hard resisting to read the book, even though I have some compelling things to do (or maybe more so). O was wrong because the first chapters are a pleasant reading /even if you know/ the concepts presented. Perhaps it is even more interesting as my brain is not involved into understanding difficult new concepts but can just enjoy the beautiful presentation of familiar stuff.

Besides, the book is a wonderful introduction to the functional way of thinking and covers relatively advanced topics. You can really learn Lisp from the book, even if you don't know a thing about Lisp and functional programming. However, it is nice to read for someone familiar with FP and not with Lisp. I believe that it is funny even for experienced Lisp hackers, as the comics and jokes inside the book are really funny.

Clojure is mentioned, as are Scheme and Arc. However, the focus is just Common Lisp. It is not hard to port the examples to other Lisps, however. As macros are introduced relatively late, the example could also be used with other languages, such as Python.