Y Combinator in Python

I just finished reading The Little Schemer. What an awesome book! I love the Q&A format of this book and can't wait to read the next book in the series, The Seasoned Schemer.

Chapter 9 and 10 (the last two chapters) were really good. Chapter 10 is about writing a small scheme interpreter. But its Chapter 9 that I want to discuss in this blog post because Chapter 9 introduces the Y Combinator.

I've tried to understand it in the past and failed (the wikipedia page is completely unintelligible) , but this book explains it in a brilliant way. In fact it derives the Y combinator from the ground up, making sure each step is easy to understand.

As an exercise, I tried to write it in Python. This is how it came out:

def Y(le):
    def _anon(cc):
        return le(lambda x: cc(cc)(x))
    return _anon(_anon)

If you don't know the Y combinator already, that probably looks quite cryptic.

To give a simplified explanation, the Y combinator is a function that takes one function as input and creates a recursive version as an output. Maybe an example will illustrate the point better:

def _1(factorial):
    def _fn(n):
        if n == 0: return 1
        else:
            return n*factorial(n-1)
    return _fn

Take a look this function. The function name is _1. The function body has something that looks like a recursive factorial implementation, except that it never calls itself (remember, the function name is _1). Instead, it recurses on "factorial" which is a parameter of the function _1.

Basically, the "factorial" parameter is a function, so the meaning of _1 is:

• If n is zero, return one
• else, take the factorial parameter, and call that function with parameter n-1, and after that returns, multiply with n and return the value

Exploring a bit more:

def error(n): raise Exception

f = _1(error) # passing function "error" as the parameter
f(0)   # prints 1
f(1)   # Exception

The above function f is passing error as a parameter to _1. So if n is zero, it returns 1. Otherwise, it goes to the else part and calls the function that we passed as parameter, in this case error, which raises an exception.

In order for this to be recursive, we don't want it to call error, we want it to call the same function again. What if we passed the same function as a parameter? So in the else part, instead of calling error, it would call itself. Something like this

f = _1(_1(error))
f(0)   # prints 1
f(1)   # prints 1
f(2)   # Exception

f = _1(_1(_1(_1(error))))
f(0)   # prints 1
f(1)   # prints 1
f(2)   # prints 2
f(3)   # prints 6
f(4)   # Exception

Hmm, in each case, the recursion finally stops with an exception when it encounters the error function. A truly recursive version would be like

f = _1(_1(_1(_1(_1...... forever

Well, that is basically what the Y combinator does. Using some function passing magic, it converts _1 into the forever recursive version. How?? Well thats the magic!! Its a bit complicated to explain here. Get the book and read Chapter 9. But it works! Check this out:

f = Y(_1)
f(0)   # prints 1
f(1)   # prints 1
f(5)   # prints 120
f(10)   # prints 3628800

Amazing isn't it? And the even more amazing thing is that it is not specific to factorial. See this

def _2(length):
    def _fn(alist):
        if not alist: return 0
        else:
            return 1 + length(alist[1:])
    return _fn

f = Y(_2) # calculate length of a list
f([])   # prints 0
f([1,2,3,4,5])   # prints 5

Woohoo!! On a roll now..

def _3(reverse):
    def _fn(alist):
        if not alist: return []
        else:
            return reverse(alist[1:]) + [alist[0]]
    return _fn

f = Y(_3) # reverse a list
f([])   # prints []
f([1,2,3])   # prints [3,2,1]

You can take any recursive function, and rewrite it in the above style and the Y combinator will make a recursive version of it. How cool is that?

This post is a part of the selected archive.

Mylapore Photos

I went on a Mylapore heritage walk organised by Namma Mylapore on Saturday morning. Namma Mylapore is a group of volunteers that aim to make Mylapore better. The heritage walk is one of the things they do. Apart from that, they also try to clean the roads and other such projects. They meet at 5pm on the first Sunday of every month at the South steps of the Mylapore tank. More volunteers welcome!

Some of the photos from the walk are up on flickr: http://www.flickr.com/photos/siddhi/tags/mylapore/

Event Badge Generator released under MIT License

The event badge generator python script has been released under the MIT License: More info, Download

If you attended Proto.in, you would have noticed the cool preprinted badges for all the attendees. (If not, check out the pics here and here) We had almost 400 people, and no way was I going to manually create each badge, type and place all the text, reduce the size if it didn't fit, split names into two lines if required and all that. So I ended up creating a python script to take a badge template and a list of names and create badges for each one.

I was talking about this script at the lightning talks at BCB4, when Brad Allen from the Dallas Python User Group mentioned how it might be useful for other events as well (mainly with reference to PyCon). Therefore, the script has now been released under an MIT license.

As it stands now, there are some hardcoded variables here and there and some work needs to be done. If you are a python coder, you can probably find your way around and change what you want to change. Sometime in the future I'll parametrise it so that it is relatively easy for non-python coders to use it as well. Eventually, I'm hoping it reaches a stage where it can be used by non-tech event managers.

For now though, it can only be used by those who can read and write basic python. If you are interested in using it or playing around with it, check out the project wiki page.

Some Post-event Blog Posts

A couple of events happened this weekend.

On Saturday, SkillsCamp Pune took place. Freeman has a post-event blog post.

On Sunday, the Bangalore OpenCoffee Club meetup was held. Ramjee has the post-event blog post for this event.

Looks like both the events went off pretty well. Good stuff. Waiting for photos and videos ;)

The problem with voted content: Homogenisation

A couple of things occurred the past week which made me think about voted content. The first was Dharmesh Shah lamenting the loss of reddit and the second was an idea floated on the bangalore barcamp mailing list of having an event where all the talks are voted on by the audience.

Why do I think an audience voted event is a bad idea? Tyranny of the majority. Tyranny of the majority is a term applied to pure democracies where the majority can constantly out-vote the minority and therefore impose their view on the entire population (which is why there are no purely democratic countries, but lets not go there).

Lets take a simple example to see how this works. Say we have an event and 100 people turn up. 60 of them want to attend startup sessions. 40 want to attend photography sessions. There are ten speaking slots. Common sense dictates that having 6 startup sessions and 4 photography sessions is a "fair" distribution for the given audience.

But what happens when topics are put to vote? In every slot, the startup crowd can out-vote the photography crowd. Therefore when put to vote, the most likely outcome will be 10 startup sessions and no photography sessions.

But it doesn't end there. The next time the event comes up, the audience will be reinforced by those who liked it the first time around. Therefore in the second edition, there will be more startup enthusiasts in the crowd and fewer photography buffs. Over time, this positive feedback cycle will reinforce itself until the crowd and the topics become homogeneous.

This is exactly what happened to reddit for example. Topics that appealed to the majority go to the front page. As users visit the site, those who like the topics on the front page tend to stay, while those who don't will leave. Those who stay cause more such articles to get to the front page, which in turn attracts people who like those topics. A vicious positive feedback loop occurs as the crowd and the topics become homogeneous, eventually driving out minority interests.

The cool thing about a barcamp is that there is a great deal of variety in the topics. Therefore, even if you are in the minority, there is a good chance that you will find someone with your interests at the event. The biking collective was a good example of this. Such a session would never have survived a voting round. But the barcamp format meant that it was possible for those interested in the topic to meet up and have a session.

That is why I feel that efforts must be taken to preserve diversity.

Having said that, there is merit in voted sessions. Voted sessions avoid the situation where people talk about stuff that no one wants to hear about. But it makes more sense if voted sessions are just one of the tracks in the barcamp, not the whole event.

Organising your own OpenCoffee Club

Bangalore OpenCoffee Club Meetup

Following on from the Chennai OpenCoffee Club, Vaibhav and Ramjee are organising an OpenCoffee Club in Bangalore. OpenCoffee Club is is a place for people involved in the startup ecosystem to meet in an informal setting.

Read more about the Bangalore OpenCoffee Club and if you are interested in attending, join the bangalore opencoffee google group.

Organising your own OpenCoffee Club Meetup

Starting your own opencoffee meetup is very simple. Here is what we did:

• Decide on a time and place. The place should allow a small crowd to have noisy discussions as they roam around the place. Make it easily accessible. We chose 3pm Sunday mainly because there is less traffic — otherwise it is a pain driving through rush hour.
• Next you need to announce the meetup. We
  • Posted about it in our blogs. Kiruba picked it up and posted it in his blog
  • Sent a mail to the python, ruby and linux user groups
• For other cities, the local Barcamp, MoMo, LUG and other such groups are good places to announce the event
• Finally you need to turn up at the give time and place and let the event happen. We had a quick introduction at the beginning then broke for food/coffee and let the individual discussions happen.

Thats pretty much it. The cool thing about OpenCoffee Club meetups is that there is very little organising overhead, which makes it easy to organise and attend.

Lightning Talks at BCB4

We decided to have a session of lightning talks at the Python hall at BCB4. A lightning talk is a quick 5 minute talk. Usually there are a number of lightning talks one after another. The idea of the lightning talk is to give a quick introduction to a topic that might be new for the audience, with the discussions taken after the session.

It went of pretty well, one of the more fun sessions. It's really nice to see ideas bouncing off every five minutes, and with Kausik keeping strict time, the session flow was good.

After seeing it work nicely at the Python hall, I converted my Speed Geeking session into a lightning talk session. The reason was that there were about 20 people in the audience, which is too small for a speed geek, but good for lightning talks.

In this post I'll summarise the topics from the two lightning talk sessions. Click the links for more information on the topic.

• Code like a Pythonista: Brad Allen from the Dallas Python User Group talked about David Goodger's tutorial, Code like a Pythonista.
• Printing badges with Python: This was my session on how I used a python script to create attendee badges for Proto.in. If you attended Proto, you would have seen those badges. They were generated using a Python script.
• Restructured Text: Restructured Text is another variant of text markup languages like Textile and Markdown. It is the standard markup language used in docstrings in Python.
• Sudoku Solver: Anand had a talk on writing a sudoku solver. Very nice little program that uses a backtracking algorithm to solve sudoku puzzles.
• pygoogle: pygoogle is a python interface to the Google web search API. This session showed how you can use it for search engine optimization.
• Web.py: Demonstation of a quick web app written using the lightweight web.py framework. Web.py powers sites like Reddit and Open Library.
• Wicket and JTrac: Peter Thomas gave a talk on his open source project, JTrac, which uses the Apache Wicket framework.
• Agile Software Development: Agile software development explained in a few minutes!
• Second Life: An intro to Second Life, with an emphasis on the Second Life economy.
• Creative Commons: An intro to the CC philosophy.
• ShowMeDo: ShowMeDo is a site for the sharing of technical material through the medium of screencasting.
• Tempostand: Tempostand is a platform for independent artists to share their music under a Creative Commons license

Two sessions of thirty minutes each for a total of one hour of lightning talks. That one hour threw up these twelve topics. Good ideas and technologies to investigate in more detail. If you are going to be taking a session at an unconference, try out the lightning talk format.

Tanjong Rhu

Tanjong Rhu
Originally uploaded by Siddhi

Taken on Singapore National Day, August 9, 2006. This apartment complex is located opposite the stadium. I was just looking around and saw the beautiful sight of the moon rising over the apartments.

Google Uses Crowdsourcing To Create Maps In India

Brady Forrest over at O'Reilly Radar has a post on how Google is using Crowdsourcing to create maps in India.

Google has been sending GPS kits to India that enable locals to make more detailed maps of their area. After the data has been uploaded and then verified against other participant's data it becomes a part of the map.

He quotes a speech by Michael T Jones, CTO of Google Earth, who in a talk said:

Now, everything you see here was created by people in Hyderabad. We have a pilot program running in India. We've done about 50 cities now, in their completeness, with driving directions and everything - completely done by having locals use some software we haven't released publicly to draw their city on top of our photo imagery.

Pretty interesting stuff. Read the whole post for more information.

How well are VC firms doing? Not too well.

Matt Marshall over at Venture Beat analyzes how well VC firms are doing, and the answer: not too well. According to the post, the average VC firm only gives a 2.7 percent annual compounded return over five years which is pretty dismal. Whats more, the median VC firm is losing money, and the average is only pulled up by good numbers at the upper end.

Another analysis by Dan Primack looks at returns post-bubble and finds that the median VC return is -2.6 percent year on year. Dan concludes that the vast majority of VC funds raised since 2001 have underperformed a typical savings account.

SkillsCamp Pune

SkillsCamp Pune is coming up on the 18th of August. The aim of SkillsCamp is to create an open courseware focusing on technical topics. Think of it as MIT OpenCourseWare for software development. The idea is that each session will be a 15 minute workshop which will be recorded and then put online or on a DVD. It's an unconference, so participants can take a session on any topic that they want. Expect tech stuff like python, rails and so on to be recorded.

The organisation team for SkillsCamp is being led by Freeman Murray. I first met him at BCB3 when he was wearing a very nice creative commons t-shirt and then again at Proto.in and BCB4. At BCB4 he recorded a videocast while I showed him ShowMeDo, which aims to do something similar to SkillsCamp via screencasts.

It's interesting to see these initiatives for bringing in sharing of technical knowledge, especially because there is a serious shortage of good training material for a lot of newer technologies. Personally, I am a huge fan of screencasts as a wonderful medium for capturing and distributing this knowledge.

Review of BarCamp Bangalore 4

So BarCamp Bangalore 4 has come and gone. It was interesting as always. Lots of interesting people and things going on. I already wrote a post about Anand and the Open Library project and I'll be writing a few more detailed posts about the other stuff that I found interesting at BCB4. In this post however, I want to concentrate on the event itself.

Also, on the topic of BCB4 reviews, some other posts from across the blogosphere -

• http://latelyontime.livejournal.com/155355.html
• http://ramblings.ajaxed.net/2007/07/30/barcamp-bangalore-4-day-2/
• http://silicontryst.wordpress.com/2007/07/31/caution-demoing-product-at-barcamp/
• http://mataal.multiply.com/journal/item/42
• http://remainconnected.blogspot.com/2007/07/i-missed-day-1-of-barcamp-bangalore-4.html

To start off, the event was huge. Around 600 people turned up I believe. Now whether that is a good thing or not is something that we'll discuss in the last section of this post.

Another interesting innovation was the introduction of collectives. A collective is a group getting together to discuss a common topic. This was in response to the last time when a complaint was that if someone was interested in one topic it was hard to know where all it was happening. This time you could just head out to the collective venue and sit through all the collective sessions.

Now to dissect the event ;) I'll start out with the broader principles and finally come to the minor areas.

The law of two feet

To start off, one thing I liked the large number of parallel sessions. This is an area where a number of people complain - too many parallel sessions - but according to me, there needs to be way more sessions than you can possibly attend. This is because a crucial cornerstone of an unconference, borrowed from open space technology, is the law of two feet. Harrison Owen, the creator of Open Space says this about the law:

This law says that every individual has two feet, and must be prepared to use them. Responsibility for a successful outcome in any Open Space Event resides with exactly one person -- each participant.

The basic principle is that if you are not getting anything out of a session, use your two feet to move to a better session. The law can only be useful if there are enough sessions to choose from. So for the law to be successful, you need to have a lot of stuff going on. By "stuff going on," I don't mean formal sessions only. Hallway discussions and informal or ad-hoc sessions also count.

One of the things that I really enjoyed this barcamp, and thought was an improvement over last time, was the amount of stuff happening in parallel. I was able to extensively use the law of two feet to good effect and ended up in a number of good sessions.

Small groups in a circle

Another thing that I took away from Owen's writings on open space technology was the role of the circle. I've seen this validated time and time again — the best discussions happen with a small number of people facing each other in a circle. Take a look at this photo from the social tech session. I can't display it here since it is all rights reserved :( - http://www.flickr.com/photo_zoom.gne?id=937911412&size=l

Studies have shown that the design of an interaction space has a profound effect on the types of interactions that go on there. Put people in a classroom and there is a clear divide between the presenter and the audience. The result is that you will likely get a presentation plus Q&A format, with a mostly passive audience. Put people in a small circle and you will get a completely different set of interactions.

Again for first timers, it often seems that the thing to do is to sit passively in the sessions. This often leads to confusion when a lot of interesting discussions are happening in the hallway.

I thought the classrooms at IIM are too big. I liked the rooms at Thoughtworks from BCB2. Probably the right size for having a session.

Whenever they start is the right time. When it is over, it is over.

These are two more principles of open space. Basically what it means is that a group will start when it needs to. The discussion will run its course. And then the session will end. "Run its course" could mean 5 minutes, half an hour, one hour, whatever. As long as participants are interested, the discussion is on. When the energy drops, the discussion is over and the session is closed.

The conclusion to draw from that is that it is impossible to fix an exact start and end time on a session. Some sessions start late because you are waiting for people. Some start early because there are interested people around.

I am reminded of Prayank's hands-on tutorial on flex (a detailed post on this will come later), a very nice session that was conducted in the middle of the lunch session when everyone was out eating. But there were a few people interested and the room was free, so the session was held then.

Again, sessions finish when they finish. Some discussions go on for a while. It can be a killer to cut the session short due to time constraints. Some sessions only go on for 15-20 minutes. It makes sense to move on rather than to fill the time.

I thought that the idea of encouraging sessions outside the rooms were brilliant in this regard. When the session is held on the garden or in the hallway or in coffee day, there are no time constraints and the sessions follow the principles automatically.

The paper wiki

The paper wiki just didnt work properly this time. One of the by-products of having a collectives system is that each collective had its own schedule. This is great if you plan to sit in one collective, but it was confusing if you wanted to move from room to room and wanted to see what was going on at a particular time across collectives. In the end I just went to the rooms to see what was happening instead of relying on the paper wiki. This was kind of messy and definitely one area to look at.

For instance there were a lot of corridor sessions scheduled for post lunch, 3pm on Sunday - Bikers, Photo, Speed Geeking, Python, Functional programming, and virtually nothing for 4pm. Session coordinators didn't realise this situation because there was no centralised paper wiki where you could see the timings across collectives properly.

I liked the paper wiki at BCB2. Very straightforward and everyone knew at what time a session was happening.

Dissecting the hallway discussion

The interesting thing about a hallway discussion (or any session outside the classroom for that matter) is that it follows these principles automatically. No one needs to tell anyone anything, it just happens like it is just the natural state of things. Hallway discussions are by nature limited to 10-15 people due to practical constraints. The participants are almost always in a circle facing each other. Those not interested almost always move on, and interested people join in. It is almost always participatory. And hallway discussions just start on their own and end when its over.

Amazing isn't it? Can we replicate these in planned sessions? I say yes. Hold the session outside the rooms — in the corridor, garden or coffee day or anywhere outside — and it will automatically follow the principles.

Getting the first-timer oriented

The thing about a barcamp is that it can be extremely disorienting to a first timer. Almost everything is structured in a way that is counter-intuitive to previous experience. The large number of parallel sessions, sessions that start late or early, sessions that end late or early — it can all be very disorienting.

A good paper wiki can be critical here. I also think if there are a large number of first timers, it probably makes sense to have an introductory session on 'navigating through a barcamp.'

Other minor points

An issue was that many uninterested people came along. This might be true, but it could also be a case of first timers not knowing how to get the best out of an unconference. The main thing is to get interested people into the event. I think pitching the event to the mainstream is a bad idea. Whoever is interested should come. If that is 50 people then that's okay. If that turns out to be large, then that's okay too. But it should happen organically. There need not be a deliberate focus on doing a big event. BCB is popular enough that it doesn't need to focus on publicity.

One more point that irked a lot of people was companies that did repeat sessions in the rooms because 'they didnt get enough of a response the first time.' Guys, the idea in a barcamp is to share and learn, not to use a captive audience as a focus group. I have no problems with companies showing a demo of their product. These sessions can sometimes be pretty interesting. But to do it again in the room is probably not correct. If you really, really want to do a repeat, use the corridors. Especially if there was not enough response the first time. If there was a great response then maybe its okay, but even then I'd suggest a corridor for the session.

Many complained about sessions overflowing their time. This is the problem with rooms. It's hard to apply the "when its over, its over" principle because the next session has to start. This was hardly an issue with the corridor discussions because there is always more corridor space.

Conclusion

Okay, this post is big enough already. What did I like? I liked the stuff happening in parallel and the hallway discussions. I thought the session rooms were too big and the paper wiki was very confusing. On the whole I was mostly in the hallway discussions, so it was a very good barcamp for me, though I can see how those who tried to decipher the paper wiki and plan the sessions to attend would have had a tough time.