The W3b : Thought-storm on the next iteration of the Internet

1/ Here’s a thought experiment about the future of the internet. Can we model it as a complex system in the same way we look at human societies and governments in real life?

2/ Humans began as individuals, who had the ability to form progressively larger organizations which became support networks that helped our species achieve the largest throughput from our lives.

3/ Over time, these organizations came to be controlled by those who had a monopoly on resources – wealth, armies and social power, but the members of these organizations didn’t have any say in how they were run.

4/ The concept of democracy was evolved as a system that could distribute social power in order to catalyze the wider involvement of its members in their own social and economic concerns.

5/ While this form of government is not without issues, it highlights a trend – by having an organization with representation by its members who have a say in how its run, we’ve had a wider ranges of stability, and its evolution is controlled in a (somewhat) scalable manner.

6/ As an analog, the internet started out as a decentralized network of computers where all the information was open – anyone could participate by simply putting up a node.

7/ Over time, centralized systems were created because they offered the benefits of an overarching “support network” – making technology and information accessible to their users because most individuals couldn’t do all this heavy lifting and plumbing on their own.

8/ These organizations, whose members can’t really control how they are run or what they make them do – are not that different from erstwhile kingdoms trying to maximize the profit of their sovereigns.

9/ And by virtue of who controls them or who can influence them – imagine wealthy courtiers and banks who financed kings [see game of thrones] – they dictate the price of admission and inclusion

10/ Monetarily of course, they may even be free – but members give up control over their privacy and data to get in. In turn, these organizations become monopolies and act as gatekeepers of the very information and data that belongs to its users.

11/ While they can empower members to have a voice in the global discourse, their scale implies control and filtering algorithms that evolve in the image of those who hold the most sway on these platforms – in some cases the loudest, the richest, or the most divisive.

12/ So what does this mean for the future of the biggest collaborative system that humanity has ever built together? One potential road could be to reason about how they can mirror the democratic model.

13/ I posit a thought that “It is in the nature of complex information systems to systematically distribute their functioning to sub-systems in order to perform at their peak.

14/ In other words, a series of decentralized, shared ownership systems that come together to provide and replace the functionality that has today been built into the centralized networks described before. I’m going to call this the “W3b” – because, well, why not? (A moniker for Web 3.0)

15/ As Alexis De Tocqueville recognized in the study in which he coined the term, there is often more to decentralization than just the administrative benefits it brings. These networks will have properties beyond just the sum of the properties of their components.

16/ Scientifically, there are no complexity theories to analyze complex networks like there are for algorithms. But if we think about the latent, emergent properties of these networks – we likely cannot predict how they will affect our lives in 20 years, much in the same way we couldn’t have predicted the fake news problem in 1999.

17/ In order to get to such decentralized networks, we’re going to need new forms of technology which can offer interoperability without needing shared trust, since these networks will be just like the internet is today – they will span nation states and have messy real world constraints.

18/ Just like every nation in the world today connects their internal infrastructure to the internet and communication networks, they will buy in to these subnetworks because they will become irrelevant if they don’t – especially when they act as a conduit for international trade, payments, law and cooperation.

19/ What are the conceptual abstractions we need to think about in order to make these subnetworks a reality? We can take a leaf out of the Open Systems Interconnection model (OSI), which is a conceptual model that characterizes and standardizes the communication functions of a telecommunication or computing system without regard to its underlying internal structure and technology.

20/ Much like the seven layers of the OSI model. there are a few different kind of functions that the these subnetworks would need to provide without regard to how they are actually implemented underneath.

  • Identity and authentication (+ Discoverability)
  • Payments and economic transactions (+ Discoverability)
  • Actions (APIs for connecting to databases + Discoverability)
  • Content (Information for consumption + Discoverability)
  • Policy (Encoding and enforcing law)
  • Auditable events (Ledger of activity)

21/ These subnetworks will need to work in conjunction with each other, and transactions done by any entity, individual or organization will need to coordinate with one or more of them.

22/ But how would these be used? Let’s take the example of an autonomous entity which has a very simple need – they want to subscribe to a streaming movie provider and watch it.

  • They use the content subnet to find a provider that streams movies.
  • They utilize the identity subnet to create an account with this provider, which is an auditable event
  • The provider verifies this against the identity subnet and creates an account, asks for payment information
  • The entity then identifies on the payment network, and initiates a payment authorization against the provider
  • Once the provider receives this authorization, they can stream the movie to the entity.

23/ By decentralizing and sharing ownership of the most critical parts of the new w3b, new generations of software can be written that would allow scalable solutions to some of the most critical challenges we face today – from cyber security to fake news.

24/ In addition, large centralized network companies will no longer have the monopolies that they currently do, leading to a more equitable distribution of the wealth that is being created.

25/ By making micro transactions and payments tied to identity, content and services outside of centralized control, political machinations are less likely to influence w3b users.

26/ And further, having machine readable cryptographically verifiable audit streams of events, provenance of data, content, transactions, identities and finances will mean that tools and services can be built upon them in standard ways by anyone.

A John Perry Barlow Story from 1998

I grew up in New Delhi in the late 90s on a steady diet of 2600, phrack, BBSes and the EFF. Two of the people I’d read a lot about, and was subsequently very inspired by, were JPB and Mitch Kapor, as founders of the EFF – and I decided one day that I’d like to actually reach out and talk to Barlow (I didn’t actually have a goal in mind, now that I think about it).

Figuring that an email would never get a reply, I added him on AIM. To my utter surprise, he added me back – and after introducing myself as a high schooler who was a fan of the work he was doing, we communicated over the next year or so on a wide variety of topics that included open source, free software and the state of the internet in India at the time. For the next 10 years or so, when AIM was still active, he was one of the very few people still on my contacts list who would go “online” and “offline” with a regular cadence — one of the only reasons I ever even logged into AIM was to (rarely) say hello :).

Of course, I stopped using the service a long time ago, and lost touch with him – but his declaration of independence of cyberspace was something that I leaned on when researching about internet censorship and policies a few years ago. I never did reach back out to him, and there was no pressing need to either.

On hearing the news of his passing away, I’m reminded of how prescient and applicable his words have been to the issues and challenges that we see in the internet of today – but also how he personally upheld one beautifully phrased paragraph in particular, by virtue of his accepting a request from, and interacting with a random high schooler from half way across the world.

Cyberspace consists of transactions, relationships, and thought itself, arrayed like a standing wave in the web of our communications. Ours is a world that is both everywhere and nowhere, but it is not where bodies live.

(Cross posted from the original hackernews comment)

Live life’s questions

Life, as we lead it, is very uncertain. All of the myriad ingredients that constitute our daily existence are nothing but ephemeral experiences, and many wise voices over millennia have spoken about the follies of being too attached to them. As a species though, most humans tend to value what they have lost, what they don’t have, or what they can’t have much more than what they can or do. We tend to become too comfortable in who we are and how we live – be it our ability to take risks, go out of our comfort zone, make new close friends, move across continents, end or begin relationships, or just do what our heart desires most – mostly in the fear of violating established norms and society’s image of us. And just plain inertia.

The ability to deal with this uncertainty is arguably one of the most important and yet underdeveloped skills we possess. We tend not to think about how often we require it, and how critical it is to almost every aspect of our lives on a daily basis. One of my favorite quotes is from the German poet Rainer Maria Rilke, who expressed very beautifully in a letter to a young poet, some advice on how to deal with uncertainty,

I beg you, to have patience with everything unresolved in your heart and to try to love the questions themselves as if they were locked rooms or books written in a very foreign language. Don’t search for the answers, which could not be given to you now, because you would not be able to live them. And the point is to live everything. Live the questions now. Perhaps then, someday far in the future, you will gradually, without even noticing it, live your way into the answer.

How we see life is a choice that we make for ourselves. We can be struck by the overwhelming pain, suffering, poverty, anger and hate that are rampant in our world today and complain about how hard things have become and how we are completely powerless to do anything about it. Or we can find the good in every day things and refuse to be sledgehammered by the reams of bad news that seem to be the staple of the world today – to step up and resolve to do whatever it is that we care for without worrying about the likely or unlikely consequences of our actions.

We will definitely make mistakes as we do so. As Peter Drucker once said, “People who don’t take risks make two big mistakes every year. People who take risks make two big mistakes every year”.  The impulse to change the world is not naive – it is inherently built into every one of us and in times of fear and frustration, we would do well to remember that the smallest of actions can make a difference. After all, it is much easier to connect the dots looking backwards than forward. We must put our trust in the fact that the dots will somehow connect in our future.

For the longest time, I used to wonder what kind of questions Rilke referred to when he wrote that letter I quoted above. And one day, a serendipiteous click led me to a commencement speech by Jeff Bezos that gave me some insight into what those might have been, and I’d like to share that,

How will you use your gifts? What choices will you make?

Will inertia be your guide, or will you follow your passions?

Will you follow dogma, or will you be original?

Will you choose a life of ease, or a life of service and adventure?

Will you wilt under criticism, or will you follow your convictions?

Will you bluff it out when you’re wrong, or will you apologize?

Will you guard your heart against rejection, or will you act when you fall in love?

Will you play it safe, or will you be a little bit swashbuckling?

When it’s tough, will you give up, or will you be relentless?

Will you be a cynic, or will you be a builder?

Will you be clever at the expense of others, or will you be kind?

Take that risk. Find your voice and tell your story. We have a duty to make the world a bit more interesting than how we found it.

In praise of melancholy

The pursuit of happiness is a very curious goal that modern society has imprinted upon all of us. When asked what we desire most in the world, happiness, along with success, is perhaps at the top of the list. But we must ask ourselves – what does being happy mean to a group of people who have never experienced anything else? Not having anything to compare their normal state of being must surely be unrewarding – it is only after every one of them experiences sadness in one form or the other that would make them appreciate the state of being happy. So why is this seemingly unattainable goal sought after with single-minded devotion?

It is interesting that two of the most influential thinkers of the modern age – the Danish philosopher Søren Kierkegaard and Friedrich Nietszche – have felt that a certain amount of suffering is essential to the soul. It is not an accident that some of the most creative outputs of the past millenia have been a direct result of the feelings of melancholy. Van Gogh for instance once wrote in his diary about his experiences of mental anguish,

.. One feels as if one were lying bound hand and foot at the bottom of a deep dark well, utterly helpless ..

Experts today put forth the theory that his works may have been influenced by the pain he felt as a result of certain types of migraines and headaches.

Closer to the modern era, it is a well known fact that the most famous music compositions of the 2oth century have been odes to love – mostly written at a time when the participants of that particular relationship were at odds with each other, or were suffering the loss of their significant other to a host of things ranging from death to distance.

There is a theory that an NYU behavioral economics professor, Adam Alter, proposed a couple of years ago that ties in to this.

Sunshine dulls the mind to risk and thoughtfulness.

He has a very interesting explanation of this theory, which hinges on the fact that when our mood is dampened by bad weather, it turns us inwards and goads us to think more deeply and clearly. As he writes in his book “Drunk Tank Pink: And Other Unexpected Forces That Shape How We Think, Feel, and Behave”,

Humans are biologically predisposed to avoid sadness, and they respond to sad moods by seeking opportunities for mood repair and vigilantly protecting themselves against whatever might be making them sad. In contrast, happiness sends a signal that everything is fine, the environment doesn’t pose an imminent threat, and there’s no need to think deeply and carefully.

When we’re facing major emotional hurdles — extreme grief, an injury that brings severe pain, blinding anger — our emotional warning light glows red and compels us to act.

The next time a set of clouds come floating by and cast a gloomy shadow on an otherwise sunny day – both metaphorically and otherwise – we would do well to cast our thoughts inwards, and consider it but an opportunity to let our thoughts run deep and our creative juices flow free, rather than be consumed by something as trivial as our inability to affect change as quickly or efficiently as we would like.


Dreams in Hollywood

On a recent trip to Los Angeles, the driver of the car that picked me up from the airport started talking about his life through the course of our journey. Having come to LA as an aspiring actor almost 30 years ago, he told me how he had dreamt big, and gotten parts in independent and mainstream movies, but always remained on the sidelines. Enough to generate hope that things would work out, but not enough to actually do so.

“I went to school with Helen Hunt. Do you know why she became famous?”, he asked.

Before I could really say anything, he continued.

“Because her father, Gordon Hunt, is a famous actor/director” [known primarily for The Jetsons and Scooby Doo]. “She wasn’t really the prettiest one in the class, and there were definitely more talented people than her. But she got ahead.”

Of course, I have no way of confirming whether he indeed went to school with her, but it’s definitely a plausible story. Wealth and power always beget more wealth and more power. Why not indeed?

The thing that got me thinking was the fact that 30 years later, his once active career has dropped in scope to driving limousines for a living. He mentioned that he enjoys his job, but ultimately given a choice, it’s not what he’d be doing. How then does one realize when to give up? At what point could he have turned around and said – the acting gigs aren’t really going anywhere, perhaps I should try and develop an alternate career? Is there a framework that people have that allows one to take such a major decision? Would it have helped him lead a more fulfilling life than the one he does today?


Making sartorial statements as an engineer

Silicon Valley prides itself on being a spearhead in providing amazingly flexible work environments to its employees. There are barely any established timings to get in and out of work, lunch jogs are du jour , working from home is a luxury given to most people, appearances aren’t important as long as they’re not offensive, and people are judged by not how they dress but what they achieve. The epitome of meritocracy, one might say.

So why don’t engineers pay more attention to how they clothe themselves? (Just to be clear, I’m talking about men here.)

Unlike the social interactions that make up most of a sales or marketing role in any organization and thus demand non trivial thought being given to one’s sense of dress, there is really nothing more for an engineer to do (in between a spate of meetings) than to sit down and actually start building something. Which means they can dress as comfortably as they want, without the stress of needing to decide what to wear everyday. Rather than take this as a blank cheque to dress “down” into the apocryphal hoodies and t-shirts, why not take this as a challenge to creatively explore their individual sense of style? What better circumstances to develop and perfect this highly personalized sense of self expression than in an environment that doesn’t penalize you if it doesn’t always work?

One of the things that always irks me is the perception that most people have – real or imagined – of engineers being unable to fend for themselves when it comes to making a sartorial statement. The media as usual does an amazing job in portraying the typical inarticulate, t-shirt-hoodie-torn jeans wearing programmer who works out of a windowless basement, with only code, soda and perhaps some science fiction keeping him company. Even Obama has gone on record making a dig at Mark Zuckerberg’s rare use of a jacket and tie. But is this stereotype really warranted?

Building software for the most part is a very solitary endeavor, and requires equal parts creativity, analytical skill and an eye for detail. I think of it as an art – one that compares most favorably to writing a novel, the creation of a painting or even the composition of a symphony. And as befits any artist, engineers take pride in their craft – there are umpteen blog posts and talks about the elegance of a certain algorithm or the simplicity of a piece of code that achieves something complex. Why then don’t more of them take pride in presenting themselves?

I don’t disagree that there’s a level of creativity involved and some people may not consider themselves well suited to pulling together various items of clothing in an aesthetically pleasing manner. But in this day and age, it’s really not that hard to find a host of resources on the web that offer everything from helpful tips to services that help you overhaul your wardrobe!

Software has been “eating the world” for a long time now, but it is the relatively recent focus on combining it with good design that its use becomes increasingly prevalent in every aspect of life. Practitioners of the art of making software (or hardware for that matter) should really stand up and take their place front and center of the well dressed world, and get rid of the stereotypes that have dogged them for years. After all, they are not sitting down in a basement all by themselves any more – they are under the lens of the entire world as it watches them create the next wave of innovation.

And they might as well pose for the camera in a tweed sports jacket and sharp shoes than a company hoodie and flip flops.

Can there be an algorithm for creativity?

Artificial Intelligence has always been one of the most fascinating aspects of computer science. With devices getting smaller, the cloud more ubiquitous, and processors becoming more powerful, we are starting to find ourselves in the beginning of an era where machines will get progressively smarter. Apple’s Siri, Google Now, and Microsoft’s Cortana are but some examples of teething intelligent assistants that we all hope will one day become sentient, autonomous and (hopefully) friendly sidekicks that make our life easier.

The creation of software such as this has been made easier with the development of what is today called Deep Learning – an advancement in the field of machine learning where sophisticated neural networks are being trained with more and more data to learn behaviors, recognize images, understand speech and respond in natural language to domain specific queries. How these systems work is pretty simple to understand.

Consider the task of understanding and recognizing the contents of an oil painting which portrays a woman standing in a park. The intelligent system could start by analyzing the smallest possible chunks of the painting – which are called features – in this case, a series of dots of paint, organized by color. It might then do a second pass to recognize higher dimension features, and try to determine interconnections between these dots to determine which ones constitute a line. The third pass might analyze the contours of the known lines, and determine shapes – circles, squares, and other irregular ones. If the system has been trained to map a known set of shapes to real life objects, it may be able to in the next pass perceive an eye, a nose, a tree and other objects that make up the painting. And lastly, it may put these things together to understand that two eyes and a nose make up a human – so this must be one, and that trees with grass and butterflies are generally found in a park, so this must be a park.

And so it goes, from being able to detect the contents of a painting to figuring out which videos on Youtube have cats in them.

But a missing component of real intelligence is creativity, one definition of which is the ability to come up with unique and novel explanations for events and occurrences that can not always be explained by observing the past. As David Deutsch writes in his excellent piece on AI in Aeon magazine,

I myself remember, for example, observing on thousands of consecutive occasions that on calendars the first two digits of the year were ‘19’. I never observed a single exception until, one day, they started being ‘20’. Not only was I not surprised, I fully expected that there would be an interval of 17,000 years until the next such ‘19’, a period that neither I nor any other human being had previously experienced even once … How could I have ‘extrapolated’ that there would be such a sharp departure from an unbroken pattern of experiences, and that a never-yet-observed process (the 17,000-year interval) would follow?

All of the programs that have been written so far have had the ability to compute of course. Increasingly, they have even had the ability to know – to store knowledge and intelligently answer questions about things. But none of them, so far, have been able to want. What then would it mean for a program to not go as far as to be called sentient or alive, but be merely creative?

One way to answer that would be to define creativity as the process of finding relationships between facts from different branches of knowledge. As these facts become more and more removed from each other, the larger is the impact of such a connection being made. While we may want much of this relationship-creation to happen in some orderly fashion, the reality is that most of this happens in a very serendipiteous manner. Is it then possible to simulate this accidental fact correlation in a program?

If we analyze a deep learning program trying to identify features for a given task, we will see that its probabilistic nature means it is bound to commit mistakes. There will be times when it throws up a false positive – identifying an object as something that it is not. Most times, the evaluator will mark this as a “negative example”, in order to make sure that this particular mistake is not repeated the next time a similar case is seen.

But what if this is how a machine makes a mistake? After all, this is no different from an artist making an errant daub of paint on their canvas and realizing that it actually fits in well in a way they never imagined before. Could we then train a system to take these mistakes and channel them into a positive feedback loop that improves the tasks this machine was doing, especially if it were creatively inclined like producing a piece of music, analyze some art, or even paint a piece of art?


Religion and the curious death of free speech

Religion, if you look at it, is ultimately just an idea. One, admittedly, that has the support of a large number of people. But as an idea, it is by itself not sacred. The illusion or reality of its sacredness is driven wholly by how it is perceived by those who believe in it and put it on a pedestal. Unlike people however, an idea doesn’t have any rights. When someone has a very emotional response to an attack on an idea they believe in, it does not in return give them the right to defend it with violence. They may at best have the opportunity to provide counter arguments, engage in constructive criticisms of the discrepancies in their opponent’s claims, or even completely disconnect themselves from said opponents. But never through violence.

Whenever the concept of free speech is mentioned in most contexts, religious or otherwise, Voltaire’s quote is pretty hot property. To defend till death someone’s right to express themselves even if you didn’t personally agree with them? A remarkably romantic concept. If death is the ultimate price to pay to protect someone’s freedom of expression though, as the Charlie Hebdo attacks so tragically illustrated, why go down the road of even provoking someone to the point that they would bay for blood? What’s wrong with just expressing opinions that don’t hurt anyone? Shouldn’t the creatively inclined have an unofficial motivation – or even an official regulation – that should make them responsible for their content, given the volatile times that we live in and where trigger happy adherents are more than eager to mow down anyone mocking their ideas?

Questions such as these have resurfaced time and again in my mind, in the Indian context and otherwise. As a country that purportedly guarantees the freedom of speech to its citizens, it has for a very long time – due to action and inaction – diluted the ability of its constitution to do so.

I have always found it surprising that whenever a major event happens at the world stage, Indian leaders are almost never quoted in the many statements of consternation or condolences that eventually get broadcast around the media. Imagine my surprise then at the spate of statements from not only the government, but also the Hindu right wing against the Charlie Hebdo attacks. Because in that week, an attack on free speech that was barely covered by the world media was going on in Tamil Nadu in southern India and had some wide ranging repercussions.

Because of incessant threats against him, with his books being publicly denounced in the streets by right wing Hindu groups,  and with no governmental organization supporting him, one of India’s most revered Tamil language authors, Perumal Murugan resigned from writing and went back to being a school teacher. Not only that, he took the rather extreme steps of having copies of his books recalled, asking literary festival organizers not to invite him, his readers to dispose of the copies they owned, and publishers to stop printing any more copies. Apart from the usual buzz in the liberal media, this event went mostly ignored – and the petitions filed by none other than the ruling BJP and its allies resulted in a complete shutdown of the author’s hometown for a week. And not a single statement was heard from the government about it.

Romila Thapar, the famous Indian historian put it very eloquently last year,

It is not that we are bereft of people who think autonomously and can ask relevant questions. But frequently where there should be voices, there is silence. Are we all being co-opted too easily by the comforts of conforming? Are we fearful of the retribution that questioning may and often does bring?

Why then should we defend the deliberately provocative?

Because ultimately, if we want to live our lives in a meaningful manner, in a way that we are not censored, our voices are not muffled or our actions impinged upon, we must all have the ability to provoke. And a mindset to rationally support others who do.

Because if we do not, then the rights and freedoms that we have left will be throttled even further than they already have by the treacherous cocktail of state actors, non state actors and the skirmishes between them. It is important to understand that religion, just like other human ideas, is open to satire. That it is dangerous to put any icons, institutions or figures that are ultimately a human creation, over and above satire.

Respect should be accorded to them yes – but not at the expense of the liberties and rights that are accorded to human beings.

An Armenian vignette

If there are places we call third world countries today, then I would call Armenia a fourth world country

As our jet black GMC Yukon sped through an interchange to get on to the I-405 in Los Angeles yesterday, those were the words my Uber driver said with all the passion he could muster in response to my question about how his home country had turned out almost two decades after he left.

Armen Nazaryan* was born and grew up in the city of Yerevan, the capital of Armenia. He worked as a tailor, a plumber, and then a jeweler before he moved to Los Angeles in the early 90s, starting life afresh in the jewelery business. Educated throughout his life in Russian, the lingua franca of the then USSR, he has barely managed to dislodge his pleasant but thick Russian accent in all his years in the US. As he says of the Armenian community in LA, which also happens to be the second largest anywhere in the world after Armenia itself,

“It’s entirely possible to live in Glendale and never speak any other language but Armenian all your life”

He has been very happy in his adopted country, and when I asked him if he’d ever go back, he talked at length about why not.

“Ever since the USSR collapsed in 1991, all the power and money in the country has been concentrated in the hands of maybe a dozen families. The entire economy is corrupt, with kickbacks and bribes ruling the roost. I feel sorry for my country – it used to be very nice when I was growing up – but today, I would never want to live there. My life is here. I can speak my language, Jons [the grocery store] has traditional Armenian foods, and I earn good money here. Why would I go back into that mess?”

As we started talking about his experiences driving for Uber, he described to me his favored algorithm to optimize for rides in the city.

“In the evenings close to dinner time, I park near high end restaurants. Once that crowd finishes, I head to clubs that I know are open late – not all of them, just the few that have clientele leaving them all night. And once that is done, I go to the top hotels which generally have people heading to airports early in the morning. I make good money doing this”.

The obvious question in my head was of course – why, as a trained jeweler, was he driving full time for Uber? As curiosity got the better of me, I decided to ask why before the ride ended.

“Ah”, he said, after a pause that had warning bells going off in my head about whether I’d asked too personal a question.

As I started to offer an apology, he started to talk and so I shut up.

“I was doing well in the jewelry business, with clients around LA and New York. My main client though, who had 90% of my business, was in New York on 9/11 and was lost when the WTC fell. I lost everything then, and couldn’t recover”

Not knowing what to say, I stayed silent.

“But it’s okay you know? Life throws all kinds of punches at you. We must all absorb them and continue forward – otherwise, where would we be?”

*name changed

Practical applications of Y Combinators in Clojure

When the term Y Combinator is mentioned in most technology circles today, the image it usually conjures up is of the well known startup incubator with their orange logo and a list of famous funded companies. There’s a very interesting reason they chose this name, and their FAQ page 1 gives some context on why they did so,

The Y combinator is one of the coolest ideas in computer science. It’s also a metaphor for what we do. It’s a program that runs programs; we’re a company that helps start companies.

Which of course begs the question –  why are Y Combinators so cool and are there any real reasons to know about them?

This post aims to provide insight into some practical applications of Y Combinators, and I highly recommend reading some of the following resources on the topic that do a great job in articulating the theory behind them. 2 3 4

A gentle introduction

Let’s assume we want to write a recursive function that does something useful, but with a catch – we don’t want to invoke this recursive function directly from within itself. Why would we want to do this? Multiple reasons might force us to – perhaps we’d like to avoid stack overflows, or perhaps there are other deeper reasons which are out of the scope of this post. 5 6. Irrespective – how then would we go about doing so?

In other words, the problem we’re trying to solve is to “introduce a self reference to the function, without a direct self reference”.

Before diving into the programming aspects, let’s consider this in a purely mathematical form. A recursive function can be defined partly by itself. So, in the case of the Fibonacci series,

\text{Fib}(0)=0\text{ as base case 1,}
\text{Fib}(1)=1\text{ as base case 2,}
\text{For all integers }n>1,~\text{ Fib}(n):=\text{Fib}(n-1) + \text{Fib}(n-2).

Now, how would we give such a recursive function an input, such that its output is the same as its input? For example, in the following function,

\text{F}(x) = x * x

there are two inputs: 0 and 1, for which the function’s output is the same as the input provided to it. This is defined as the fixed-point of this function.

If we can now find a fixed-point p of F such that F(p) is equivalent to p, we can use F(p) or p interchangeably (since they are the same thing) as the “recursive” function without direct self-reference 7.

It turns out that for any generic λ-expression f , (\lambda x. f(x x))(\lambda x. f(x x)) is a fixed-point of f 8.

Given this, we can build a function that returns a fixed-point for any function f by taking the function in as an argument:

\lambda f. (\lambda x. f(x x))(\lambda x. f(x x))

This is known as the fixed point or Y combinator. Therefore, for any function f, Y(f) is a fixed-point of f. That is, f(Y(f)) is equivalent to Y(f).

A real world example

So far so good. But how is this useful and why should you know about it? Let’s examine the case of a Clojure function that gives us the sum of a sequence of numbers 9.

;; An example of a recursive function to sum a sequence of numbers
(defn sum-seq [x]
 (if (empty? x)
  (+ (first x) (sum-seq (rest x))))) ;; invokes itself

;; (sum-seq [1 9])
;; => 10

As we can see, this function invokes itself  at the very last line, which is the kind of behavior we’re trying to avoid. How would we write this without a direct self reference? One way to think about this is to express it as a sequence of function calls that starts by being given a function, and returns to us not the result itself, but a sequence of “next” functions to compute the sum of that sequence. Here’s an example,

;; Function that returns the next function to compute the sum of a sequence of numbers
(defn sum-seq-fn-gen [func]
  (fn [s]
    (if (empty? s)
      (+ (first s) (func (rest s))))))

;; user> ((sum-seq-fn-gen nil) [])
;;  0

;;  user> ((sum-seq-fn-gen (sum-seq-fn-generator nil)) [9])
;;  9

;;  user> ((sum-seq-fn-gen (sum-seq-fn-gen (sum-seq-fn-gen nil))) [1 9])
;;  10

This looks like it works. But as we can see, in order to get the sum for a two element vector, we needed to invoke this function thrice – clearly not a great use of our editing skills or time. How would we make this simpler? By simply finding the fixed point for this function, we could achieve what we set out to do! 10. Let’s start by writing a fixed point combinator.

;; Y combinator
(defn Y [m] ;;  λf
  ((fn [future] ;; λx
     (future future)) ;; f(x x)
   (fn [future] ;; λx
     (m (fn [arg]
          ((future future) arg)))))) ;; f(x x)

If we were to pass the sum-seq-gen function to this Y combinator we just wrote above, life becomes much simpler.

;; user> ((Y sum-seq-fn-gen) [1 2 3])
;; 6

;; user> ((Y sum-seq-fn-gen) (range 0 1000))
;; 499500

So far so good. But the real power of a combinator isn’t just that it allows us to just write non-direct-reference recursive functions. It is that it allows us to create very useful wrappers around our functions, which can allow us to achieve all sorts of cool things without ever needing to rewrite our original function. As an example, let’s consider the use case of needing to log every internal function call that’s going on in the sum-seq-fn function. In the regular programming model, we would need to add these log lines to the sum-seq-fn itself, which is a huge overhead. But by using combinators, we can just define a LoggingY that will do this for us.

;; A logging fixed point combinator
(defn LoggingY [r]
  ((fn [f]
       (prn "Logging call: " f)
       (f f)))
   (fn [f]
       (prn "Logging within second f: " f)
       (r (fn [x]
              (prn "logging within third fn: " x)
              ((f f) x))))))))

viksit.explorations> ((LoggingY sum-seq-fn-gen) [1 2 3])

"Logging call: " #<explorations$LoggingY$fn__14921 viksit.explorations$LoggingY$fn__14921@1ed99bdc>
"Logging within second f: " #<explorations$LoggingY$fn__14921 viksit.explorations$LoggingY$fn__14921@1ed99bdc>
"logging within third fn: " (2 3)
"Logging within second f: " #<explorations$LoggingY$fn__14921 viksit.explorations$LoggingY$fn__14921@1ed99bdc>
"logging within third fn: " (3)
"Logging within second f: " #<explorations$LoggingY$fn__14921 viksit.explorations$LoggingY$fn__14921@1ed99bdc>
"logging within third fn: " ()
"Logging within second f: " #<explorations$LoggingY$fn__14921 viksit.explorations$LoggingY$fn__14921@1ed99bdc>

Without having to change the original function, we’ve just added some deep instrumentation into our function.

A memoization example

Let’s consider a slightly more non trivial example. What if we wanted to make a recursive function more efficient by introducing memoization? Could we write a generic non-recursive function and then apply an equally generic combinator to memoize it? Absolutely!

For this exercise, let’s define a more generic fixed point U combinator 11, which applies an “abstract” function myapply on to the function f. We can use the freedom of choosing myapply, for example, to transparently interpose memoization.

;;  U = λh.(h h)
;; Generic U combinator
(defn U [f]
  (f f))
;; More generic function that can take an application function
(defn UM [myapply f]
  (defn g [v]
    (fn [args]
      (myapply (f v) args)))
  (f g))
;; A non recursive function that gives us the nth fibonacci number
(defn fib-nr [f]
  (fn [n]
    (if (< n 2) 1
        (+ ((f f) (- n 1))
           ((f f) (- n 2))))))

We can now create a combinator ready 12 function that returns an anonymous function that will cache a function’s arguments and results for it.

(defn make-memoizer []
  (let [application-cache (atom {})]
    (fn [function & args]
        (if-let [e (find @application-cache args)]
          (val e)
          (let [result (apply function args)]
            (swap! application-cache assoc args result)

;; Time taken to fetch the 38th fibonacci number
viksit.explorations> (time ((U fib-nr) 38))
"Elapsed time: 9700.194 msecs"

;; Time taken to fetch the same, but with memoization (!)
viksit.explorations> (time ((UM (make-memoizer) fib-nr) 38))
"Elapsed time: 0.153 msecs"

As we can see, by never having to modify the original function, we’ve been able to use a variety of specific or generic combinators to provide wrappers that can help in making programs more optimal, easier to debug and ultimately, fine-tune.


  7. Seriously, highly recommend reading up on what fixed point combinators really mean
  9. Courtesy
  10. This almost seemed like magic the first time I encountered it!