September 14, 2009

List comprehensions and generators: Python and haskell for beginers

List comprehensions and generators are features I always liked from Python. I'll try to write a post I would love to read some time ago when I first met these wonders...

A comprehension list is a way to obtaining a lis in a "descriptive fashion", for example: the list of the first ten powers of 2:

[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

Could be obtained from the list comprehension:

[2**n for n in range(0,11)]

Which could be read as: "2 to the n-th, for n in the range from 0 to 11". EIn this case range() is a number generator.

What does being a generator mean? It simply returns an iterator and it will produce numbers as long as we ask for them (there's a more performant function to do this, called xrange(), with better memory usage).

We would like to build, for example a generator that returns the numbers in the fibonacci sequence. Let's see which Python provides to achieve this.

The next code counts. Forever. It returns one number every time we ask for it:

def count():
x = 0
while True:
yield x
x = x + 1

The yield operator is powerful enough to build a generator. It returns the control to the caller of the generator function. Everytime the generator is invoked again (with the next() method it continues the execution in the line next to the last executed yield, avoiding any infinite loop as the while True may suggest.

In a Python console we can give it a try:

>>> a = count()

Now we do the same with the ever-useful sequence (the first two numbers are hard-coded since they are the base cases of the recursive definition of the sequence)

def fib():
i = 0
first = 0
yield first
second = 1
yield second
while True:
next = first + second
first = second
second = next
yield next

Now great, everything is very ince but where do these list comprehension and generator stuff come from? Well, list comprehensions are a feature that python "borrowed" from another language...Haskell, from the functional pradigm.

How do we do this same thing we've done in Python with Haskell? Let's start with the list comprehensions:

Main> [2^n| n<-[0..10]]

Which can be read as: "The 2-to-the-nth that come from taking n from the list that goes from 0 to 10", since Haskell talks the mathematician language, it doesn't have problems like Python's range(n,m), which goes from n to (m-1)...

Let's continue. Do you notice anything strange in the Haskell line? A generator!, to be more precise... two! Why?

Main> [0..10]

Generates the sequence that goes from 0 to 10 while n <-[0..10] in the context of the comprehension list "takes n's" from that list.

Something important to say about generators. Python and Haskell allow generator chaining, try these codes in both Python and Haskell (respectively):

Main> [ (x,y)| x<-[0..5], y<-[11..15] ]

[(x,y) for x in range(0,6) for y in range(11,16)]

They generate the same!

Speed test

Anybody reading this is ready to go on reading by his own about generator and comprehension list wonders... you can find some links at the end of the post.
Bu I kept playing and tried some things... For example, have a look at these definitions in Haskell to generate the fibonacci sequence:

fibo 0 = 0
fibo 1 = 1
fibo n = fib (n-1) + fib (n-2)

fib :: Int -> Integer
fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

fibo is the recursive version, SLOW. Every time I ask for the n-th numer it recalculates the (n-1)-th and (n-2)-th and for each of these goes on like that... clearly taking exponential complexity.

En cambio fib is a version that makes use of the super-great functionalities present in functional languages: the folds, high order functions. This last version has lineal complexity, which means, it can compete with the Python version with no (prior) disadvantage (in algorithmic means). Let's do this!

The contestants :

fib :: Int -> Integer
fib n = fibs !! n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)


def fib():
i = 0
first = 0
yield first
second = 1
yield second
while True:
next = first + second
first = second
second = next
yield next

Try this.... my results in the next post.
Hoe you enjoyed this post!

Este link Pyton comparison with haskell from python docs.

November 3, 2008

Hack.Lu 08

Finally got home from the old continent. I've been presenting a work I've working on the last months. First of all I must say the organization of Hack.Lu was great. It's a small single-track conference where most of the people are from France, Germany, Belgium and of course, Luxembourg!
I've met a lot of cool people and must say Fred (one of the conference organizers) did a great job and helped me a lot, thanks fred.

As for the talks, there were quite several I liked, I will only mention two:

  • Various Ways of Classifying Malware (H. Flake and S. Porst from Zynamics): They showed the awesome tool called VXClass, which is intended to aid in malware classification into families. As always, great apps. from bright people. I recommend you have a look on what they're doing

  • The guys from RedTeam Pentesting GmbH showed what they've learned while doing JBoss pentests. Basically walked through configuration issues and exploited them live. A very interactive talk and with a lot of things to take into account while deploying/doing-something with the JBoss plattform.

Regarding my presentation, I'll soon publish the code and upload the slides. It is basically an environment which uses instrumentation provided by Core Grasp. Check out soon for the material.

That's all for now,


June 5, 2008

ET Phone Home: about neutrinos

(this entry is a translation from the original spanish version of this blog)

Yesterday reading slashdot I ran into a
paper (pdf) about some guys talking abount intergalactical communications (sounds like science fiction but basically they talk about very big distances across space) which as the communication medium use neutrinos.

To have a better understanding of what they were talking about I went back to read more carefully what neutrinos are, which types of neutrinos we can find, etcetera. Some history:

(NOTE: I discovered that physics papers like this one are very difficult to read for a newbie like me. I feel them like a 13th century narration about some sort of mathematical construction but ok then, must be their own style)


Neutrinos are from the
Los neutrinos son de la familia de los fermions family, which are very-very small particles, so small that they can penetrate any matter type (even smaller than photons).

So W. Pauli postulated the notion of "neutrino" so he could fix a math error in a formula while he was measuring the conservation of energy and momentum in beta decays (according to the wise Wikipedia, this is when as a result of a radioactive decay a beta particle -electron or positron- is expelled). He postulated (apparently) in order to describe a non-detected particle which was carrying the energy missing in his lab tests, measuring energy, momentum and angular momentum.
The name "neutrino" was given byE. Fermi but I will not go further on this since I haven't read anything.

Back to the paper. They first discuss which types of neutrinos are better for this type of communications, based on their signal/noise level acceptance. They also evaluate differently "energized" neutrinos (measured in eV, electronVolt - 1 MeV/c² = 1.783×10−30 kg, seems like in particle physics, quantum level, mass and energy are interchangeable, thanks to Einstein's work, so this measure is used as a mass unit and energy one).

One of the things they postulate is that the people from SETI which are a foundation which tries to explain life in the universe, doesn't find a single signal coming from the outer space (or further...) because information is no longer transmitted over photon-based channels or even bigger particles. Hence, since we (humans) don't have the technology needed to catch smaller particles we cannot listen to ET's family calls.

The paper the discusses how to code information (using neutrino's oscillation) whith neutrinos properties. It seems also that they propose some sort of super-neutrino-ray which works in a very high level of energy (or mass) but ok then, my super null-understanding of the topic doesn't allow me to go further.

I recommend you read the paper, I didn't finish it, and could understand some amount below 10% :D. But what I COULD, is to remember why I wanted to study physics after computer science. :D

February 27, 2008

Cape Town Open Education Declaration

Basically I already wrote about this in another blog, it didn't seem to get much attention...

Anyway, now I have my own blog and I can post whatever I want (:D) I'll express some thoughts I have bouncing in my mind...

What is this declaration about?

It's a list of items about the usage of free resources in the education field.

Full declaration text can be found here. Among other things that I'd like to mention from the inititative we can highlight:

  • Promote the usage of free resources such as course materials with open licenses, class programs, textbooks, games, software and other material which support learning and knowledge sharing..

  • Promote the usage of free technologies which facilitate a collaborative and flexible learning, sharing teaching experiences which help educators benefit from their pair's ideas..

A lot of times I see myself discussing about WHY free software works. The people with whom I discuss (in a constructive way, of course) sometimes think "hey, I'm trying to make an idealist stubborn change his mind", might be, I really don't know. What I do know is that using open source and free software (which by the way, are very different) and free license schemes (i.e. non-software material distributed under licenses which allow sharing, modifying and redistributing it, e.g. Creative Commons) allow to build a more agile and flexible interchange, useful for the community and for future generations.

From the educational point of view (which I'm interested in today) It's important to see how this 'sharing' influences our student's education.
Once (a few hours ago...) a friend of mine (which is also an educator that I deeply respect) told me "If you don't let the students write and become authors, they won't read whatever you write, no matter what it is". This is a great point, What would happen if we extend this notion to education and knowledge?

I think that leaving that expositor-like role while we teach is crucial if want to change the way knowledge is transmitted.

Promoting the idea of free resources and not privative (I repeat, I'm not talking exclusively about software) collaborate in building a different type of mind openness.

To close this post, I hope you could understand what I wanted to say, and feel free to go deeper inside free teaching resources.

Here I leave some interesting links about topics which I have just mentioned and others that I haven't.

Open education initiatives: A list of Cape Town - related inititatives.

Creative Commons.

Free Software in Wikipedia: Some history and explanation of the term.

Free Software Foundation: That.

Pagina de R. Stallman

PS: Please note that English is not my primary language, feel free to read the original Spanish version of this post here.


February 21, 2008

RFC: Traits for PHP

Reading PHP-internals list ( I found that Stefan Marr sent a very interesting patch.
It's an implementation of Traits for PHP.

But what does Traits stand for?

Traits are basically Behavioral Blocks which group functionality (they group methods / functions indeed).

Depending on which programming language we are keen on we are used to dealing with interfaces, making our object hierarchies implement these interfaces. For example:

Interface TheInterface
   public void method1();
   public int method2();

interface TheOtherInterface
   public void methodA();
   public int methodB();

class TheClass implements TheInterface, TheOtherInterface
   /* Here all methods corresponing to both interfaces
     * should be implemented

But what happens with object hierarchies? Sometimes we have to choose between an elegant OO design, loyal to all the OOP concepts that we know (wtf?) like Encapsulation, Inheritance, Abstraction, Polymorphism (I really don't remember anything about these, I only know how to apply them..) that adequately represents the problem we want to model, OR, make a very nice and reusable code, not paying (too much) attention to best practices and principles of OOP...

So we have class hierarchies where classes extend other classes, creating complex families, with parent and child clases with inherit some of their parents' methods, with different access permissions (protected, private, final, sealed, etcetera, depending on the programming language...)

But sometimes, we have functionalities we would like all the class families to enjoy, for example: If we want all the families to know how to cook an asado, wherever they were born since they live in Argentina like me:

Let's consider this example:

We have a (not very useful) hierarchy, which models families of different origins. All the families have a surname and know how to procreate.
So families know how to cook different types of food, depending on their origin. The italian know how to cook pasta, risotto and canoli, japanese are expert sushi cookers and sake drinkers. We, the argentinean, know how to cook asado, drink mate and going to the cancha (soccer stadium), but not me... I don't go to the cancha.

It would be great if any family living in Argentina know how to cook asado and drink mate... So we can build a small "package", or Trait with different abilities, for example:

trait ArgentineanFood
   public void cookAsado(){
     // code to cook asado...
   public void drinkMate(){
     // code to drink mate...

So we could have a class like:

class ItalianFamily
   use ArgentineanFood;
   public void cookRisotto(){...}
   public void cookPasta(){...}
   public void cookCanoli(){...}

And easily have an italian family which knows how to cook and consume argentinean food, weird uh?? (I have to say that most of the Argentinean population has italian origins...)

I like to think that this is a way of crossing the hierarchy in an horizontal way, I try to explain this on the class diagram (click to enlarge):

Traits for PHP

There are lots of details to deal with. For example name conflicts. What happens if two traits have methods with the same name? who resolves this?

In this first implementation there is no conflict solving. In fact, traits are "flattened" inside the code of the class. The decision of which trait wins the conflict is left as a programmer decision.
We could do things like:

class Talker {
    use A { !smallTalk }
    use B { !bigTalk }

Where the Talker class has methods from traits A and B but exludes the method smallTalk from trait A and bigtalk from trait B. We can also rename trait methods while using it in a class.

One advantage we can find in this implementation is that it hasn't any runtime penalty, since its like a formal way to copy n' paste code.

I recommend you read what this guy Steffan wrote, everything for the PHP implementation is clearly explained.

Ok, so I quit writing not to bore you. I hope you could understand everything I wanted to share.


Further reading
Read here.
more on traits here.
Or you can read Nathanael Schäarli's Thesis.