Morning Panel

Day 2 started with a morning panel with:

• Paul Fox from Blockchain.capital
• Leon Gerard Vandenberg from RightsFusion Pty Ltd & Solara
• Oliver Harvey from ASIC
• Ross Buckley from UNSW Law

The panelists took turns in giving their views around blockchain, investments and regulation, leading into a Q&A at the end. I was running late to this session and believe I may have missed Ross’ individual slot.

Paul’s slot - I’m a VC and Bitcoin stole my job

Paul raises an interesting perspective on Angel investors. They don’t invest to make money. To them it’s a hobby. There are other, provably more profitable ways to make money.

He also raises the fact that sure there are lots of ICOs but more and more of them seem to be missing their targets. Many reasons but one he mentioned was China’s clampdown on cryptocurrencies.

ICOs are so hot right now that there are companies dedicated to helping it happen with pre-packaged solutions for launching and marketing the token generation event: https://icobox.io/ 

With so many ICOs it becomes increasingly difficult to discern good ideas from bad ones and then from plain scams. Nevertheless people are still innovating and are not deterred by these challenges. One example is TrustToken, which tokenises physical assets.

Leon’s slot

Leon’s particularly not happy with the current Australian Guidance towards ICOs. The current challenge is how to protect consumers, while still enabling companies and entrepreneurs trying to do a legit ICO - I’m assuming Leon is referring here to the plethora of scam ICOs out there.

To Leon - and many in the audience - an ICO is just another tool with very desirable properties: it gives companies the means to connect with individual investors who believe in their cause without diluting equity. In addition, Leon & his board had their share of bad experiences when trying to seek legal advice around ICOs and explaining their SOL Token

There are many types of tokens/coins: equity tokens, cause coins, utility tokens… I knew about some of these but the concept of cause coins is new to me - say, SaveTheElephantsCoin.

Oliver’s slot

Oliver was basically talking about capital raising. 

In particular he points out that the number of IPOs in the US is at an all time low whereas in Australia the trajectory is in the opposite direction. Unfortunately he didn’t dive into the why of this change in scenery in the US.

Personally I wanted to have asked if the decline in IPOs is due to company expansion by acquisition. Companies like Google, Facebook and Atlassian have acquired dozens of smaller successful companies who could have otherwise gone public - is there a correlation here?

Another piece of data Oliver shared is that 25% of companies listed on the ASX have a market cap of up to $5M - he then goes to say that if a company is looking to raise about that much money crowdfunding platforms such as ICOs might just be the way to go.

Audience Q&A

Are ICOs making entrepreneurs soft? 

The problem raised by this question is whether having too much money too soon - as is the case with lots of ICOs -  can be bad for founders.

The panel’s general opinion is that it can be a hindrance: it may lead to scaling up too soon and losing focus as one now thinks it can do many different things at the same time. VCs in general are sceptical of this.

One way to mitigate this mentioned in the event is to have the funds locked up by smart contracts (potentially tied to milestones as opposed to simple time triggers). 

The bottom line is that ICOs are still evolving.

Why invest in ICOs vs traditional investments? Are we opening the floodgates for less knowledgeable, naive people to invest?

Should mom and dad be investing? Maybe not - there isn’t enough information out there, not enough regulation. We’re not there yet.

That said, what ICOs - in particular the tokens people invest in - provide is unprecedented liquidity. Tokens aren’t going away.

In the midst of all this information exchange Naval Narvikant was mentioned as someone to watch. He’s got a couple of articles and podcasts which have been recommended:

• https://medium.com/@gifted_products/cryptocurrencies-with-tim-ferriss-nick-szabo-and-naval-ravikant-51a99d037e04
• http://unchainedpodcast.co/naval-ravikant-on-how-crypto-is-squeezing-vcs-hindering-regulators-and-bringing-users-choice

Software architecture and engineering for blockchain applications - Ingo Weber - Data61

This next talk was a lot more technical and was delivered by Dr Ingo Weber from Data61. I didn’t take as many notes on this one as a version of the slides is already available.

Dr Weber started with a demo of ethviewer - a way to visualise the ethereum blockchain in realtime and observe how transactions are received, processed and added to blocks. Just plain cool!

The general message is that most blockchain applications have the blockchain as just another component in their architecture and the strengths and weaknesses of each component should be respected and planned for. e.g.: don’t do big data processing on the blockchain

In addition Ingo mentioned the Red Belly Blockchain, an unforkable blockchain built down under.

Blockchain risks, Opportunities and Future scenarios - Mark Staples - Data61

The next speaker, Dr Mark Staples, is also from Data61. 

Dr Staples explores a couple of reports published by Data61 about the future of Blockchain in Australia. These reports can be found here.

What’s changed since these reports:

• Active interest and growing understanding by regulators
• Australia leading the ISO TC307 standard on Blockchain and DLT
• Widespread adoption and benefits yet to come
• Cryptocurrencies are a double-edged sword for Blockchain and DLT
• Technological innovation: Distributed Exchanges, Scalability, Privacy…

LoyaltyX - Philip Sheller

The premise for this talk is that loyalty programs are failing to deliver.

Philip came from Qantas’ Frequent Flyer store and knows a thing or two about loyalty programs. 

The basic idea around LoyaltyX is that customers get rewarded in cryptocurrencies. This presents a couple of interesting benefits:

• They can use the crypto they earn to buy more things at the merchant
• Since it’s crypto, they are not locked in and can take their rewards and spend them elsewhere
• But hey, it’s still crypto so they may choose to hold and trade at a public exchange at a later time - maybe for a profit

They ran a private pilot with UNSW merchants and students and the results are promising.

ROI with a stable cryptocurrency - Kevin Kirchman - WorldFree

Kevin presents on FreeMark. It’s an alternative to blockchain technology aimed at providing a stable coin backed by a basket of commodities. One fundamental difference is that in FreeMark you don’t necessarily  know - or care - where your coin came from.

There are lots of startups trying to solve the stable coin problem. I believe it’s absolutely a problem that needs solving but it’s hard to tell at the moment who will come out on top.

Creating and settling agricultural assets on a blockchain - Emma Weston

Emma talked about AgriDigital, a startup whose goal is to enable trust and transparency for global agricultural supply chains. In a nutshell I believe AgriDigital can be described as realtime payments and digital escrow for settlement with farmers. 

The problem they are trying to solve is for farmers to get paid quicker - oftentimes the farmer who sits at the very start of the supply chain doesn’t get paid within any reasonable amount of time. Sometimes they even loose track of their goods upstream - another reverence to the provenance issue.

For this to work it seems Emma needs a stable coin - again, it’s a hot topic - but for their pilot with RaboBank it was simply agreed that one of their tokens is worth 1 AUD so as to validate the technology.

Final panel - Payment Systems - Reserve Bank of Australia

This section was delivered under the Chatham House Rules. It basically means that no-one can tell you who said exactly what.

+I really enjoyed the discussions here. One topic was the issuance of a digital version of the Aussie dollar (DAD) which would enable many types of sophisticated payment systems. While there isn’t a conclusive indication of the future no Retail Reserve Bank sanctioned DAD was envisioned, but an AUD Bank branded ‘Wholesale only” DAD may be possible. I am pleasantly surprised by the level of thinking on this topic from the Blockchain community and the RBA.

Summary

Even though cryptocurrencies and blockchain technologies aren’t new - bitcoin was created in 2009 - you can see and feel that interest from technologists, the public and regulators has grown tremendously in recent years. 

Blockchain technology, implications and research still have a long way to go but 2018 has started on a really good note and I can’t wait to see what the future holds.

The talks had a healthy mix of research and industry case studies with subjects ranging from the technical challenges of current blockchain implementations to the legal implications of distributed ledger technology.

I’m not sure when and if slides will be published so I’ll do my best to summarise the talks and share its highlights. Most likely this summary will reflect my own biases on the subjects which interest me the most.

Day 1

An Introduction to Distributed Ledger Technology - Ron van der Meyden (UNSW)

Ron is the organiser of the interest group and this particular event. In this introduction he gave an overview of what a blockchian is and how it works. A great start for the day!

Ripple - Dilip Rao

Dilip is Ripple’s Global Head for Infrastructure Innovation. Currently with about $94M in funding, Ripple is backed by some fairly big enterprises and banks as well as high profile customers such as Westpac, Santander, BBVA and dozens more.

Ripple has made some interesting trade-offs:

• It accepts and embraces the fact that banks will not run on a public ledger. It simply won’t happen
  • One of the reasons discussed is the fact that through a combination of various sources and pattern analysis one could figure out trading volumes between banks and enterprises and they are not onboard with that.
• As such Ripple uses its own private ledger based on the Interledger protocol. Only on-boarded participants - banks - may interact with it. 
  • The product is called xCurrent. It allows banks to settle cross-border in real time.
• This highlights an interesting fact: banks don’t need the Ripple cryptocurrency (XRP) to settle transactions

The Interledger protocol allows multiple ledgers to communicate. Currently it can communicate with the XRP(Ripple) ledger to provide fast payment channels. Due to this specialised nature, XRP now has the cheapest cost per transaction as well as being the fastest clocking in at 1500 transactions per second. This article has some more information about this.

These are some impressive numbers - effectively they can match VISA’s throughput - and has definitely brought up Ripple into my radar once again.

Ripple also offers another product, xRapid, aimed at enabling realtime payments and on-demand liquidity by using XRP. Dilip offered Cuallix as a case study for this product. Cuallix is using xRapid to reduce the cost of sending cross-border payments from the US to Mexico. 

P.S.: Just as I was writing this section I came across another article indicating Western Union is doing experiments with Ripple as well.

Blockchain deconstructed : contracts vs smart contracts - Fritz Henglein (University of Copenhagen)

This talk focused on the technical details of smart contracts as currently implemented in platforms such as Ethereum. In particular the fact that the contract rules and its execution are intertwined.

Fritz began his talk with a summary slide on smart contracts which allowed him to expand on the above:

Due to this mixing of rules (contract checking) and execution (contract actions) in the source code - as in Ethereum smart contracts - there is no possibility of having multiple strategies which may be private and can be reused in different smart contracts.

Fritz argues that contract actions - which he called strategies - should be stored separately to the contract rules. In doing so such strategies can be private and re-used in different contracts. He calls this model Managed Contracts which combine the contracts with join execution strategies:

He then moves on to discuss the trade-offs and vulnerabilities of Ethereum smart contracts. I particular he raises these issues:

• Transaction order dependency
  • Messages may have different effect depending on the order in which they are received
• Smart contracts may behave differently depending on the timestamp of a block
  • The timestamp of a block is controlled by miners. He raises that this exposes the contracts to clock manipulation attacks. Frankly I’m not sure if this attack can succeed if a single miner is the bad actor. I’d need to think through this but if someone has an example handy, that’d be great.
• Exception handling and programming language subtleties:
  • Fragile gas management and limited stack 
  • Differences in language constructs such as send vs call
• Reentrancy bugs

Fritz’s proposal to deal with this are Managed Contracts and he refers to a paper - which he co-authored - called Compositional Formal Contracts. The paper proposes the following properties:

• Separation of concerns
• Domain-oriented code
• Analysable
• Composable

I couldn’t find a paper with that exact title but did find two papers co-authored by him with a similar title. Here and here. If you know which one he was referring to, please let me know.  

Rightsfusion Pty Ltd - Solara.io - Leon Gerard Vandenberg | slides

Solara has an interesting premise. In the energy space, consumers and traders have difficulty determining & validating green, renewable energy from fossil fuel energy. Solara allows communities and prosumers (producer / consumers) to factionalize or leverage new ownership models and redistribute and/or monetise their energy & their energy data.

In addition, SOLARA Platform aims to provide a proveably green & clean digital solar asset to a variety or energy data exchanges & markets. The concept of a Tokenised ‘Safe Haven Asset Class’ based on a hybrid portfolio of Solara PAT tokens that could be synthesised by quants to eventually provide a stable coin was contemplated by Leon. (refer to Solara White Paper for details on Project Asset Tokens - PAT tokens)

Another interesting aspect is that Solara is looking to provide “fit for purpose hardware” Solara Hardware Modules to bridge the needs of both the metering and the blockchain worlds - think IoT eSIM cards which are also a secure blockchain keystore (wallet).

Leon & team is currently working towards an ICO (private pre-sale for their SOL Token is now on-going) and looking to build out more team members (including University Labs) and RightsFusion will engage in projects for Solar Communities and solar industry participants.

Lastly, Leon mentioned Polymath in the context of ICO investments: Polymath (Canada) is working on a securities token or their ST standard. Because Solara’s PAT Tokens are a type of Financial Product - PAT Tokens could embrace the Polymath ST standard to extend their eventual reach and a broader participation model.

Note: I also got some extra resources about SOLARA straight from Leon.

The power of possibilities - Niki Ariyasinghe - R3/Corda

Niki gives an overview of Corda, an open-source blockchain project designed for building financial services infrastructure.

The project seems to have come about from the need for banks to collaborate and understand what blockchain means for financial services.

Corda displays a couple of intresting properties:

• It allows for transaction privacy
• It has a pluggable consensus mechanism allowing consensus algorithms to be chosen at transaction time and not at the blockchain level
  • I don’t know enough about corda but this particular point makes me nervous :)

The highlight of this talk for me is Project Ubin: a project by the Monetary Authority of Singapore to provide Central Bank backed Digital cash with the goal to use Distributed Ledger Technology (DLT) to clear and settle payments and securities.

Platform cooperatives - Browen Morgan from UNSW

As per Wikipedia: “A platform cooperative, or platform co-op, is a cooperatively-owned, democratically-governed business that uses a protocol, website or mobile app to facilitate the sale of goods and services”

I didn’t take many notes during this talk but captured a few interesting links:

• CULedger: A permissioned, private blockchain
• Loomio: Collaborative decision-making software
• Provenance: Building trust in goods and supply chain
  • It’s worth noting that the issue of provenance has been mentioned quite a few times during the Symposium

I particularly found ingenious the idea behind the following projects:

• Arcade.city: Think peer-to-peer Uber
• Swarm.city: A decentralised commerce platform 

Issues for law and the legal profession - Lyria Bennet Moses - UNSW 

The last one for the day, this talk is the one I was looking forward to the most. It explores concerns and legal challenges with using blockchain technology. Although not related to blockchain, our work at MODRON offers many parallels with the themes discussed here.

According to Lyria - and it’s certainly true in non-blockchain tech circles as well such as AI and Machine Learning - people ask if blockchain and smart contracts will replace lawyers. 

Her short answer is no. However certain roles might be replaced. It is already happening in domains such as exchange of documents. Basically she thinks that “the things that junior lawyers do” will be replaced by (blockchain)technology.

In addition she offers certain applications where blockchain might be particularly well suited to disrupt such as Registries and Intellectual Property. In contrast, the problem of Information Sharing in law enforcement was mentioned as one needing a cultural solution, not a technological one.

Additional challenges with smart contracts:

• Liability for delays and/or errors
  • e.g.: wrong transaction recorded, delays affecting price points…
• Form of order in, say, land law
• Jurisdiction - in which jurisdiction are you?
• Data Protection:
  • The right to change data
  • The right to be forgotten
  • EU law seems to require these properties
• Regulation
  • Similar issues to when digital signatures started being used for contracts

All the above will also have implications to how lawyers are trained. I love that Lyria mentioned this as I’ve been casting what we do at MODRON under a similar light: our human-centric approach looks to enhance what lawyers can do and over time this will invariably lead to new types of legal professionals.

Lyria’s closing remarks raised the question of wether blockchain even is the thing which will solve these problems. It’s too early to tell but it’s encouraging to see the legal profession as a whole taking the opportunity to re-evaluate how things are done.

What a day! So much to think about and so many great people to connect with. Look out for my summary of day 2!

In a nutshell this involved writing Clojure code all day to build an awesome service we call Synchrony. Synchrony is capable of realtime data synchronisation - not just collaborative editing - and as such its applications are many! This has been proven again and again internally during the Atlassian ShipIt hackatons, and externally via Enso.me, which is powered by Synchrony.

Throughout this journey I took on more responsibility and transitioned into the Development Team Lead role. This gave me the opportunity to help drive the product roadmap and vision within the company in addition to leading a very capable team. What an amazing learning experience it has been!

Today

Fast-forward to today and collaborative editing is finally being used by real customers as part of our early access program! It’s been a great journey and we have achieved a huge milestone!

For a more up to date look at Synchrony I highly recommend Haymo Meran’s presentation at this year’s AtlasCamp. Haymo is a friend and one of the original founders of Wikidocs, the company where the technology behind Synchrony was originally developed.

I’m really proud of what we have accomplished and it’s a great moment to look for a change, again :)

The future

Yes, I am leaving Atlassian - last day is June 17th. I’ll be moving on to a new opportunity about which I’m really excited. But that is the subject of another blog post :)

Nearly 4 years ago I founded the Sydney Clojure User Group. I had been playing with Clojure for a little while and started a small study group to learn more. Initially this group was private and held at the ThoughtWorks office.

After a couple of meetups and conversations I decided to open up the group to the public and then realised we weren’t the only ones interested in Clojure and, even more important, interested in meeting like-minded people, share experiences and help each other.

Back then none of us used Clojure for anything serious. Apart from Steve. Steve is a brave man and was building his new startup on top of Clojure. This was a great source of inspiration and learning for all of us. Steve hired Harry and Harry told us first hand what using Clojure for work could be like.

For all of us hobbyist Clojurists, this was a great start.

Since then we’ve held 37 meetups with an average of 22.25 attendees per meetup. These numbers won’t impress many people, no doubt about that. What is impressive however is how it’s changed over the years.

Where are we at?

Last December I sent out a survey and the result for one of the questions made me smile. The question was: Do you currently use Clojure in your day job?

This is absolutely amazing. It’s great to see how much the community has matured. Nearly 50% of meetup attendees currently work with Clojure in Sydney! I’m fortunate to say I can include myself towards this milestone!

Going forward

We’re now in 2016 and the group shows no signs of slowing down. In fact, we’re picking up the pace a little and starting the new year with a new venue: from now on we’ll be meeting at Atlassian!

I would like to thank ThoughtWorks for all the support in starting and running the meetup. I wouldn’t have been able to do it if it wasn’t for them.

See you at the next meetup!

2015 has been a unusually quiet year in this blog. Thankfully that is because I have been extremely busy in many other areas. I’d like to take the opportunity and look back at 2015’s highlights.

Atlassian

I started working with Clojure full-time at Atlassian and it’s been a great experience so far. One of the big things we’re working on is bringing collaborative editing to Confluence. However we had the opportunity to put our service to the test with the launch of Project Enso, an Atlassian Labs beta product. Check out this teaser video to get a quick feature run down.

Book

Back in March my book - Clojure Reactive Programming - was finally published. I have written about it before so I won’t dwell too much.

One last note on this though: you can get a digital copy of my book for only $5 as part of my publisher’s (Packt) Skill Up offer. Hurry, offer ends on the 8th of January!

Learning

I tend to do a mix of reading, courses and deliberate practice when learning new things. In terms of reading, you can have a look at a few things I read in my Good Reads - 2015 in books profile.

As for courses I decided to give MOOCs a try and am really happy with the courses I picked:

Coursera:

• R Programming - This is a great source for anyone who’d like to get started with data processing. Even though R isn’t one of my favourite languages I cannot deny how easy it is to start making sense of your data.
• Principles of Reactive Programming - As I have been into Reactive Programming myself for quite a while this gave me a bit of perspective on what Scala people mean by it. In particular the parts about Actor systems have been really valuable. Additionally the exercises are challenging and do drive the point home.
• Introduction to Guitar - I have been playing the guitar for a long time now but I have never had any proper education on the matter. I decided to give it a go with this MOOC by Berkeley and am pleased with the results. Especially since I can now put names to things I have done for years :)
• Leading People and Teams Specialisation - Leadership is a broad area and having been under both good and bad leadership I don’t want to make some of the same mistakes I’ve seen in the past. As such, I am seeking advice from multiple different sources - such as some of the books in my GoodReads profile above - as well as this specialisation. It has 5 courses in total. I’m two in and have enjoyed it so far.

Edx:

• FP101x - Introduction to Functional Programming - I picked this course for two reasons: (1) it’s taught by Erik Meijer and I’m fan and (2) as I don’t get to write Haskell all that often I use these courses as practice so my Haskell doesn’t get too rusty. This is an excellent course though if you’re looking to get into functional programming.

I have also been dabbling more and more with Elm and PureScript. But more on that later. Maybe. :)

Speaking

Another good year in this area. Here’s what I spoke about this year:

• Concurrent programming with Futures (in Portuguese) - QCon, March 2015 - Sao Paulo, Brazil
• Something about types being useful? - Sydney Clojure User Group, May 2015 - Sydney, Australia
• Workshop: From Zero to Pong Using Elm - LambdaJam, May 2015 - Brisbane, Australia
• Realtime Collaboration with Clojure - EuroClojure, June 2015 - Barcelona, Spain

Training

In case you don’t know one of my hobbies is weightlifting. Names such as Clean, Clean & Jerk, Snatches and Deadlifts are common in my day to day and 2015 has been a super year for my strength goals. In particular I’ve reached 120kg for my Squats and 140kg for my deadlifts which are my all time goals. For a bit of perspective I currently weigh 69kg.

These numbers are good but they are not elite level. However what makes them impressive - for me anyway - is that four years ago I injured my lower back and was diagnosed with Level 1 spondylolisthesis. My doctor at the time told me I wouldn’t be able to lift anymore and I was extremely down for quite a while. It wasn’t until I switched doctors and dedicated 100% to having proper form that I was able to reach a whole new strength level.

These results make me extremely happy. In case you’re into this sort of thing you can check a short video of my best lifts here.

That’s it

It’s been a great year. Let 2016 be even better!

Happy new year and keep on kicking ass :)

You can get it at the publisher’s website or on Amazon. I had a great time writing it and I truly hope you find it useful!

I’ve met a few authors here and there and I heard more than once that a book is never really finished. I now know what they mean.

The book doesn’t cover everything I wanted to write about due to time and space limitations. Having said that, now that the book is out I do plan to expand on a few things using this blog.

Stay tuned!

Thanks to everyone who gave me feedback on early drafts of the book! :)

Functional Programming

I have been advocating Functional Programming and Clojure for a while now and 2014 has been good to me. It was the first year where I was paid to work almost entirely in functional languages. Most of it was in Scala and a little less in Clojure.

I did have a short 8-week gig in Javascript but even then I tried to make it as functional as possible - e.g.: making use of Reactive Programming techniques (Rx-style)

I’m also thankful for the opportunity to have organised the first Sydney edition of ClojureBridge, a workshop aimed at increasing diversity in the Clojure community by delivering free workshops for women. You can read more about what we did on the day here.

Another bit of exciting news is that I’ve decided to quit ThoughtWorks. Starting in January I’ll be doing Clojure full-time at Atlassian. I’ve written about it here.

I’m looking forward to a very functional year!

Writing

Early this year I was invited by Packt Publishing to write a book on Reactive Programming in Clojure. I’ve announced it before in this blog but it is definitely a highlight of this year.

The book has been a while in the making and I had no idea of the amount of effort involved in writing one. I’m mostly content-complete now but working through a number of useful bits of feedback I got from early reviewers. I expect to be done with these in January and then the book should go into production.

I’ll keep everybody posted :)

Reading

Most of what I read this year - with the little free time I had - were academic papers and I would like to highlight a few that I particularly enjoyed:

• Monads for functional programming
• Propositions as Types
• Theorems for free!
• Monoids: Theme and Variations (Functional Pearl)
• Functional Reactive Animation
• Push-pull Functional Reactive Programming
• Elm: Concurrent FRP for Functional GUIs

Additionally I can’t help myself and recommend that you read Functional Programming in Scala if you have any interest in FP and Scala. Rúnar and Paul have done a great job and put a lot of good advice in this book.

Speaking

Between work and writing the book I’m happy I managed to speak this much:

• The Algebra of Library Design - Sydney Clojure User Group, October 2014 - Sydney, Australia
• High Performance web apps in Om, React and ClojureScript - LambdaJam, May 2014 - Brisbane, Australia
• Taming asynchronous workflows with Functional Reactive Programming - EuroClojure, April 2014 - Krakow, Poland
• Taming asynchronous workflows with Functional Reactive Programming (portuguese) - QCon, March 2014 - São Paulo, Brazil
• Monads in Clojure - Sydney Clojure User Group, February 2014 - Sydney, Australia

Content

Here’s the Top 5 posts from this blog in 2014:

• Functional Composition With Monads, Kleislis and Functors - With learning Scala and Scalaz, I’ve come to learn new ways of composing programs. This short post is a brief look on one of them, Kleisli arrows.

• Monads in Small Bites - Part I - Functors - I’m pleasantly surprised this post ranked this high. It’s from a series about Monads and I’m glad it has been helping people understand the general idea behind them.

• Clojure and ‘Why Calculating Is Better Than Scheming’ - A fresh look at this popular paper by Philip Wadler from a Clojure perspective.

• Clojure, core.async and the Lisp Advantage - core.async is still all the rage in the Clojure community and this post from 2013 gives a brief introduction as to what it’s all about.

• Purely Functional Data Structures in Clojure: Red-Black Trees - This post is from a series - though I only have two posts at the moment - about persistent data structures in Clojure.

If this tells me anything it’s that I need to blog more!

Happy new year! Here’s to an amazing 2015!

After 4 years and 8 months I have made the hard decision to change jobs: Friday, 19th of December, was my last day at ThoughtWorks.

In this time I have made many friends and have grown a lot as a professional. Consulting presents so many new challenges that often times the technical problems you are trying to solve are the easiest part of the whole project. I am thankful for that.

I am also thankful for the opportunities I’ve had.

A few years ago I started dedicating most, if not all, my free time to learning Functional Programming. ThoughtWorks supported and encouraged my endeavours in doing so and that is a big part of enabling me to create and grow the Clojure community in Sydney through #cljsyd.

Additionally ThoughtWorks has also recognised the importance of Functional Programming in modern software development and allowed me to work almost exclusively in FP languages such as Scala and Clojure for the past year and a half.

About three years ago I wrote a post detailing my first year at ThoughtWorks. Much of it is still true so there is no point in repeating it. ThoughtWorks remains a great place to work.

What’s next?

My next challenge will be at Atlassian, an Australian Software company best known for being the creators of JIRA, Confluence, Stash and many other products.

Over the years I have met several Atlassians - that’s what they call themselves - and many of them have been heavily involved in the Functional Programming community. So when I was contacted by a friend saying Atlassian needed an experienced Clojure developer I was intrigued.

A few months ago Atlassian acquired WikiDocs, a startup whose business is to build technology that enables real-time collaborative editing. It turns out that this product is developed in Clojure and Clojurescript. That’s essentially what I’m going to be working on - I’ll write more about it once I settle in.

When I started learning Clojure over 3 years ago, little did I know that I’d be working full-time with the language so soon and I am super excited about it. It’s great to see that much effort paying off like this.

My start date at Atlassian is the 5th of January and I am looking forward to meeting a bunch of great people and making new friends.

It was the first ever ClojureBridge edition in Sydney and if you haven’t heard of it before, its goal is to increase diversity in the Clojure community. It does so by offering free workshops targeted at beginners.

You should totally read Julian Gamble’s post about the event for details. He’s was one of the volunteers on the day and has done a great job of describing his experiences.

I just wanted to take the opportunity to highlight and thank all volunteers who also gave up their time for free to help and coach 24 people eager to learn Clojure. They are: Alexandra Luca, Claudio Natoli, Julian Gamble, Marcin Nikliborc, Navin K, Scott Robinson, Svetlana Filimonova & Vineeth Varghese.

Without you, the event would not have happened!

A big thank you to our main sponsor - ThoughtWorks - who provided the venue, food, drinks and, of course, Clojure cupcakes.

Another big thank you to Atlassian who gave some cool gifts to our attendees! (Sunnies and hats!).

Last but not least, a huge thank you to all attendees who were absolutely stellar and made the event an amazing experience!

I had a blast organising and running the event and hopefully we will have a new edition soon! I hope it ignited the desire to learn even more about Clojure and Functional Programming!

Happy holidays!

λ♥

The best part of every conference is the networking. Meeting new and interesting people is priceless and I did plenty of that - mostly over Polish beer and food. Polish beer isn’t the greatest but if you must have it, better stick to Żywiec. It’s widely available and was the one which didn’t give me a headache :) - I’ve been told there are amazing microbreweries though I didn’t get a chance to try any while in Krákow.

The food on the other hand was excellent every single time. But I digress.

There’s no point in me describing the talks I watched as someone else has already done a much better job of it: it’s all in this gist by Philip Potter.

I gave a talk titled Taming Asynchronous Workflows with Functional Reactive Programming. You can check out the slides here. The video will be available in this link soon. I’ve received a lot of great feedback on it both at the event and afterwards through different channels. I’m really happy with how it turned out.

In this talk I mentioned publicly for the first time* that I am working on a book called Clojure Reactive Programming to be published by PacktPub. It seemed appropriate to announce it here as well.

As of yet there’s no set date but I’m spending most of my free time working on it. I’d say I have 55% of it done. Feel free to ping me directly if you’d like to know more. Alternatively you might want to follow the twitter account I created for the book.

There’s not much there yet but I’ll try and post book updates somewhat regularly.

See you around.

* Strictly not true as I’ve announced it before but this was the first time for a wider Clojure audience and the first time captured on camera so there’s no denying now ;)

Today I’ll be exploring a few different ways in which you can compose programs. I’ll be using Scalaz in this post.

The examples that follow all deal with Vehicles - more specifically makes and parts:

1
2
3
4
5

  import scalaz._, Scalaz._
  import scalaz.Kleisli._

  case class Make(id: Int, name: String)
  case class Part(id: Int, name: String)

Next we have a couple of functions which interact with these case classes:

1
2
3
4
5

  val make: (Int) => Make = (_) => Make(1, "Suzuki")

  val parts: Make => List[Part] = {
    case Make(1, _) => List(Part(1, "Gear Box"), Part(2, "Clutch cable"))
  }

So we have a function from Int to Make and then a function from Make to List[Part]. From set theory we know this implies we must have a function from Int to List[Part]. This is nothing more than simple function composition:

1
2
3
4
5
6
7
8

  val f = parts compose make
  f(1)
  // List[Part] = List(Part(1,Gear Box), Part(2,Clutch cable))

 // alternatively you can use 'andThen' which works like compose, but with the arguments flipped:
 val g = make andThen parts
 g(1)
 // List[Part] = List(Part(1,Gear Box), Part(2,Clutch cable))

Pretty boring stuff.

A more realistic example accounts for failure in our functions. One way we can encode this is using the Option data type:

1
2
3
4

val make  = (x: Int) => (x == 1).option(Make(1, "Suzuki"))

val parts = (x: Make) =>
  (x.id == 1).option(NonEmptyList(Part(1, "Gear Box"), Part(2, "Clutch cable")))

Now we have a function make: Int => Option[Make] and a function parts: Make => Option[NonEmptyList[Part]]. Based on our first example we should have a way to create a function from Int to Option[NonEmptyList[Part]]. This isn’t immediately obvious however.

While make does return a Make, it is wrapped inside an Option so we need to account for a possible failure. This leads to our first attempt:

1
2
3
4
5
6

  val f: Option[Make] => Option[NonEmptyList[Part]] = {
    case Some(m) => parts(m)
    case _ => None
  }
  val g = f compose make
  g(1) // Some(NonEmptyList(Part(1,Gear Box), Part(2,Clutch cable)))  

While this works, we had to manually create the plumbing between the two functions. You can imagine that with different return and input types, this plubming would have to be rewritten over and over.

All the function f above is doing is serving as an adapter for parts. It turns out there is a couple of ways in which this pattern can be generalised.

Monadic bind

Option is a monad so we can define f using a for comprehension:

1
2
3
4
5

  val f = (x: Int) => for {
    m <- make(x)
    p <- parts(m)
  } yield p
  f(1) // Some(NonEmptyList(Part(1,Gear Box), Part(2,Clutch cable)))

Which is simply syntactic sugar for:

1
2
3
4
5
6
7
8
9

val g = make(_:Int) flatMap (m =>
    parts(m).map(p => p))
g(1)
// Some(NonEmptyList(Part(1,Gear Box), Part(2,Clutch cable)))

// you can also use the symbolic alias for 'bind', which makes it a lot nicer
val h = make(_:Int) >>= parts
h(1)
// Some(NonEmptyList(Part(1,Gear Box), Part(2,Clutch cable)))

The reason this is better is that make and parts could operate under a different monad but the client code would not need to change. In the example below, we’re operating under the List monad:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

val words: (String) => List[String] = _.split("""\s""").toList
val chars: String => List[Char] = _.toList

val f = (phrase: String) => for {
  m <- words(phrase)
  p <- chars(m)
} yield p

f("Motorcycles are fun to ride!")
// List(M, o, t, o, r, c, y, c, l, e, s, a, r, e, f, u, n, t, o, r, i, d, e, !)

// or even:
val g = words(_:String) flatMap (w =>
    chars(w).map(c => c))
g("Motorcycles are fun to ride!")
// List(M, o, t, o, r, c, y, c, l, e, s, a, r, e, f, u, n, t, o, r, i, d, e, !)

We used the exact same for comprehension syntax to compose these operations. This works because both Option and List are monads.

Notwithstanding, this still feels like unnecessary plumbing. All we are doing with the for comprehenstion / flatMap is extracting the values from their respective monads to simply put them back in. It would be nice if we could simply do something like make compose parts as we did in our first example.

Kleisli Arrows

A Kleisli arrow is simply a wrapper for a function of type A => F[B]. This is the same type of the second argument to the monadic bind as defined in Scalaz:

1

bind[A, B](fa: F[A])(f: A => F[B]): F[B]

By creating a Kleisli arrow from a function, we are given a function that knows how to extract the value from a Monad F and feed it into the underlying function, much like bind does, but without actually having to do any binding yourself.

To use a concrete example, let’s create a kleisli arrow from our parts function:

1
2

kleisli(parts)
// scalaz.Kleisli[Option,Make,scalaz.NonEmptyList[Part]]

You can read this type as being a function which knows how to get a value of type Make from the Option monad and will ultimately return an Option[NonEmptyList[Part]]. Now you might be asking, why would we want to wrap our functions in a kleisli arrow?

By doing so, you have access to a number of useful functions defined in the Kleisli trait, one of which is <==< (aliased as composeK):

1
2
3
4

  val f = kleisli(parts) <==< make
  // same as   kleisli(parts) composeK make

  f(1) // Some(NonEmptyList(Part(1,Gear Box), Part(2,Clutch cable)))

This gives us the same result as the version using the for comprehension but with less work and with code that looks similar to simple function composition.

Not there yet

One thing that was bugging me is the return type for parts above:

1

Make => Option[NonEmptyList[Part]]

Sure this works but since lists already represent non-deterministic results, one can make the point that the Option type there is reduntant since, for this example, we can treat both None and the empty List as the absence of result. Let’s update the code:

1
2
3
4
5
6

val make  = (x: Int) => (x == 1).option(Make(1, "Suzuki"))

val parts: Make => List[Part] = {
  case Make(1, _) => List(Part(1, "Gear Box"), Part(2, "Clutch cable"))
  case _ => Nil
}

It seems we’re in worse shape now! As before, parts’s input type doesn’t line up with make’s return type. Not only that, they aren’t even in the same monad anymore!

This clearly breaks our previous approach using a kleisli arrow to perform the composition. On the other hand it makes room for another approach: Functor lifting.

Lifting

In Scala - and category theory - monads are functors. As such both Option and List have access to a set of useful functor combinators. The one we’re interested in is called lift.

Say you have a function A => B and you have a functor F[A]. Lifting is the name of the operation that transforms the function A => B into a function of type F[A] => F[B].

This sounds useful. Here are our function types again:

1
2

make: Int => Option[Make]
parts: Make => List[Part]

We can’t get a function Int => List[Part] because make returns an Option[Make] meaning it can fail. We need to propagate this possibility in the composition. We can however lift parts into the Option monad, effectively changing its type from Make => List[Part] to Option[Make] => Option[List[Part]]:

1
2
3

val f = Functor[Option].lift(parts) compose make
f(1)
// Some(List(Part(1,Gear Box), Part(2,Clutch cable)))

f now has the type Int => Option[List[Part]] and we have once again successfully composed both functions without writing any plumbing code ourselves.

Mark pointed out to me that lift is pretty much the same as map but with the arguments reversed. So the example above can be more succintly expressed as:

1
2
3

val g = make(_:Int).map(parts)
g(1)
// Some(List(Part(1,Gear Box), Part(2,Clutch cable)))

Summary

If you are only now getting to this whole Functor/Monad/Kleisli thing this was probably quite heavy to get through. The point I am trying to make here is that learning at least some of the abstractions provided by Scalaz is certainly worthwhile. They encode common patterns which we would otherwise keep re-writing a lot of the time.

Special Thanks to Mark Hibberd who kindly reviewed an early draft of this post.

So much so that I received some community feedback in the form of emails and pull requests which is simply great!

The latest and most substantial pull request, submitted by Vadim Platonov, added the ability to customise validation messages in anyway you like, as you can see in the section Internationalization and customised error messages of the README.

However the documentation only gives a simple example and while I believe it should show users how this opens up several different usage patterns, I thought I’d expand that in this post and integrate bouncer with the excellent Internationalization library tower to show how validation and I18n could work together in this configuration.

If you’ve never used bouncer before, I’d recommend you have a quick look at the Basic Validations section of the README before continuing.

Setup

The first thing you’ll need to do is create a new leiningen project and add both bouncer and tower as dependencies in your project.clj:

1
2

[bouncer "0.3.1-beta1"]
[com.taoensso/tower "2.0.1"]

Next, in your core namespace - or wherever, really - require both libs and set up a dictionary to be used in the examples:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(ns bouncer+tower.core
  (:require [taoensso.tower :as tower
             :refer (with-locale with-tscope t *locale*)]
            [bouncer.core :refer [validate]]
            [bouncer.validators :as v]))

(def my-tconfig
  {:dev-mode? true
   :fallback-locale :en
   :dictionary
   {:en
    {:person  {:name {:required "A person must have a name"}
               :age  {:number   "A person's age must be a number. You provided '%s'"}
               :address {:postcode {:required "Missing postcode in address"}}}
     :missing  "<Missing translation: [%1$s %2$s %3$s]>"}
    :pt-BR
    {:person  {:name {:required "Atributo Nome para Pessoa é obrigatório."}
               :age  {:number   "Atributo Idade para Pessoa deve ser um número. Valor recebido foi '%s'"}
               :address {:postcode {:required "Endereço deve ter um código postal"}}}
     :missing  "<Tradução ausente: [%1$s %2$s %3$s]>"}}})

Also, we need someting to validate so go ahead and create a map representing a person:

1

(def person {:age "NaN"})

Customising bouncer

Since 0.3.1-beta1, bouncer’s validate function receives an optional first argument called message-fn. As the name implies, it is a function from error metadata to, most likely, a string. This is our opportunity to use tower’s features to translate our error messages.

In order to accomplish that, we’ll be using this message function:

1
2
3
4
5
6
7
8
9
10
11
12

(defn message-fn
  "Receives a locale, tscope and a map containing error metadata.

  Uses this information to return a I18n'ed string"
  [locale tscope {:keys [path value]
                  {validator :validator} :metadata}]
  (let [tr-key (->> (flatten [path validator])
                    (map name)
                    (clojure.string/join "/")
                    keyword)]
    (with-tscope tscope
      (t locale my-tconfig tr-key value))))

In order to understand the function above, let’s validate the person map using identity so we can inspect the error metadata that will be the third argument to this function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(validate identity
          person
          :name v/required)

;; [{:name
;;   ({:path [:name],
;;     :value nil,
;;     :args nil,
;;     :metadata
;;     {:optional false,
;;      :default-message-format "%s must be present",
;;      :validator :bouncer.validators/required},
;;     :message nil})}
;;  {:age "NaN",
;;   :bouncer.core/errors
;;   {:name
;;    ({:path [:name],
;;      :value nil,
;;      :args nil,
;;      :metadata
;;      {:optional false,
;;       :default-message-format "%s must be present",
;;       :validator :bouncer.validators/required},
;;      :message nil})}}]

As we’re only validating the name in this case, that’s all we get in the return value of validate. However you can see how we have all sorts of useful information now - hopefully this makes the message-fn code above easier to understand.

Take it for a spin

We’re now ready for a couple of examples, using two different locales. Let’s get on with it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(validate (partial message-fn :en :person)
          person
          :name v/required
          :age  v/number
          [:address :postcode] v/required)


;; [{:address {:postcode ("Missing postcode in address")},
;;   :age ("A person's age must be a number. You provided 'NaN'"),
;;   :name ("A person must have a name")}
;;  {:age "NaN",
;;   :bouncer.core/errors
;;   {:address {:postcode ("Missing postcode in address")},
;;    :age ("A person's age must be a number. You provided 'NaN'"),
;;    :name ("A person must have a name")}}]

Now let’s get some messages in portuguese, shall we?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

(validate (partial message-fn :pt-BR :person)
          person
          :name v/required
          :age  v/number
          [:address :postcode] v/required)


;; [{:address {:postcode ("Endereço deve ter um código postal")},
;;   :age
;;   ("Atributo Idade para Pessoa deve ser um número. Valor recebido foi 'NaN'"),
;;   :name ("Atributo Nome para Pessoa é obrigatório.")}
;;  {:age "NaN",
;;   :bouncer.core/errors
;;   {:address {:postcode ("Endereço deve ter um código postal")},
;;    :age
;;    ("Atributo Idade para Pessoa deve ser um número. Valor recebido foi 'NaN'"),
;;    :name ("Atributo Nome para Pessoa é obrigatório.")}}]

In case you’re too lazy to do this all from scratch, I created a github repo containing this example ready for you to play with. Go get it.

Conclusion

Hopefully this gives you a little taste of what you can do with the latest version of bouncer. Remember this is but one of many ways you could integrate the library so get creative :)

Once again, thanks to Vadim Platonov for submitting this pull request.

As for this year’s highlights, let’s get started:

Clojure

clj-syd - the Sydney Clojure User Group - continues going strong and this is in great part thanks to the amazing community behind it. You can have a look at our wiki page for 2013 to see what we’ve been up to.

A major highlight is the fact that we brought Ambrose Bonnaire-Sergeant - creator of core.typed - to Sydney to give a talk on his creation. You can read a summary of the talk on our mailing list.

On a more personal note I’ve been basically living in Melbourne for the past ~6 months working on a full-time Clojure project. I have learned a lot and can’t wait to share a whole lot with the group once I’m back in Sydney.

Speaking

I was fortunate enough to speak at a couple of really cool events this year as well as a few user group talks. Here they are:

• Functional Reactive Programming in Clojurescript - LambdaJam, May 2013 - Brisbane, Australia

• Clojure macros workshop - LambdaJam, May 2013 - Brisbane, Australia / CUFP, October 2013 - Boston, USA

• Intro to core.async - #cljsyd - Sydney, Australia & #cljmelb - Melbourne, Australia

I have also attended Clojure/West in Portland back in March. Great conference, great content and amazing people. I put together some slides with my notes on SlideShare.

Books

2013 was a great year for Clojure as we saw quite a few new books be released during the year. I’ll briefly mention a couple:

Clojure Cookbook

As the authors describe it: “Clojure Cookbook marks Clojure’s entry in O’Reilly’s prestigious Cookbook Series. The book will contain hundreds of real-world problems and solutions, ranging from basic utilities to rich web services to heavy data processing.”

I have contributed three recipes to this book so I’m quite happy to see them make it in. You can buy the early digital edition from O’Reilly’s website.

The book is the main effort of authors Luke Vanderhart and Ryan Neufeld with contributions from the Clojure community around the globe. They’ve put together quite the selection.

Clojure Recipes

Shameless plug of one of #cljsyd’s regulars, Julian Gamble, who’s been working on this for a while. The book should be released at the end of January 2014 and I’m looking forward to it.

Clojure High Performance Programming

I’ve only just started reading it but I already like what I see enough to mention it here.

Content

Here’s the Top 3 posts from this blog in 2013:

• Clojure and ‘Why Calculating Is Better Than Scheming’ - A fresh look at this popular paper by Philip Wadler from a Clojure perspective.

• Clojure, core.async and the Lisp Advantage - This year saw much excitement around Clojure’s core.async library and this post gives a brief introduction as to what it’s all about.

• Purely Functional Data Structures in Clojure: Red-Black Trees - This post is from a series - though I only have two posts at the moment - about persistent data structures in Clojure.

Non-tech news

For those who know me my passion for sports - such as martial arts, rock climbing and strength training - is no secret and in 2013 I became a certified personal trainer in Australia. I did this mostly for personal development and to better my own training. The certification is already paying off. It was a great course.

Happy new year! Here’s to an even better one ahead of us!

CUFP - Commercial Users of Functional Programming - is a Workshop-like conference targeting the practically-minded functional programming community.

As it’s stated on their website, “The CUFP workshop is a place where people can see how others are using functional programming to solve real world problems […]”.

One of the things that make the event special is that it runs together with ICFP - International Conference on Functional Programming - which is an event on the far opposite side of the spectrum with language designers, professors, compiler implementors getting together and thinking about the future of their languages and fields. The diversity of the event is astonishing.

CUFP itself runs for three days and is divided into a traditional conference format day with several talks and two tutorial days.

I was there for all three days and on the last one I delivered my own tutorial about writing macros in Clojure - more on that later.

As far as the talks of day 1 go, someone already did a great job of summarising them. I highly recommend you go read it.

Day 2

In total there were 9 tutorials being offered - two of which made up a two-day Haskell tutorial. That’s the one I decided to attend.

In the instructions, the instructors mentioned that we could use an online Haskell IDE to follow the course should we choose not to install the Haskell platform on our laptops.

I decided to give it a go. The tool is called FP Haskell Center and has been developed by the awesome guys at FP Complete.

It’s important to note this is an online IDE - but the editor isn’t the only thing being offered though. The Haskell Centre offers a complete deployment solution as well - though I didn’t have the chance to play with it.

Back to the tutorial, I used the FP Haskell Centre for day one and it worked great as far as online IDEs go. Compilation and inspecting types do suffer from the round trip over the web and by the end of the day I was feeling a little frustrated with all the waiting. The tool is great and if they offered an offline version, I’m sure the experience would have been improved tenfold.

Day one was taught by Andres Löh from Well-Typed, a Haskell consultancy.

It was full of exercises in the various basics of Haskell such as expressions, functions, IO, pattern matching and even Monads. I had a lot of fun working through them and it reinforced my opinion about Haskell being as practical a language as any other - but with several advantages.

Day 3

Given my frustration with FP Haskell Center being a bit slow I decided to install the Haskell platform on my new laptop and configure emacs with haskell-mode. I was much happier with this setup. haskell-mode has a lot of nifty features that were extremely useful during the tutorial.

The second day of the Haskell tutorial gave way to Simon Marlow, a software engineer from Facebook UK and author of Parallel and Concurrent Programming in Haskell - also available freely online.

Not surprisingly, his half of the tutorial was about Concurrency. We started with several exercises on IO involving more Monadic functions that we hadn’t learned the previous day. We then moved on to study the basic Haskell concurrency constructs and primitives. All very interesting stuff.

If you have the chance to attend a tutorial by these guys, do yourself a favour and go for it.

Day 3 - 2pm onwards

Unfortunately I missed the second half of the second day as I, too, had to deliver my own tutorial/workshop.

Titled “Bending Clojure to your will: Macros and Domain Specific Languages”, the tutorial had participants work their way through several difference exercises aimed at teaching the various nuances of writing macros.

The tutorial has failing tests for all exercises so it’s dead easy to know when you have arrived at a solution - all participants seemed to have had a great time learning this stuff and I even saw a couple of positive tweets about it - I’m really happy with how everything went.

The best tweet though was the one saying that someone from the Haskell tutorial decided to switch to mine half-way through. So I see that as a win :) Here’s said tweet.

I’ve pushed the exercises to github should you want to try them by yourself. Slides are also available though they will likely not make sense out of context.

Enjoy! :)

This post is part of a series about Chris Okasaki’s Purely Functional Data Structures. You can see all posts in the series by visiting the functional-data-structures category in this blog.

Recently I had some free time to come back to Purely Functional Data Structures and implement a new data structure: Red-black trees.

Red-black trees

Red-black trees are a type of self-balancing binary search tree. Back when I first learned the balancing algorithm used in operations such as insert and delete, I remember it being a particularly tricky one.

Traditionally, red-black trees are implemented destructively - meaning insertions and deletions happen in place. So in imperative languages like C or Java there is a lot of node pointer manipulation floating around, making this algorithm error prone.

This post, as its title implies, will deal with the functional implementation which, besides simpler, is also persistent.

Invariants

A big disadvantage of binary search trees is that they operate poorly on sorted data with O(N) worst case, pretty much becoming nothing more than a linked list.

This is where Red-black trees come in: when inserting/removing new nodes, the tree balances itself thus guaranteeing search times of O(logN). It does so by satisfying two invariants:

• No red nodes can have red children
• Every path from the root to an empty node contains the same number of black nodes

The image below - taken from the book itself - concisely summarises the 4 cases involved in these invariants, starting at the top and then moving counter-clockwise.

With this in mind I set out to write the balance function in Clojure.

The code

In the functional version of a Red-black tree all pointer manipulation required in its destructive counterpart simply disappears, rendering the algorithm a lot simpler.

Nevertheless, we’re left with some complexity in the balance function around testing a node’s colour as well as its children’s and grandchildren’s.

My first attempt at writing it started like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(defn mk-tree [color left value right]
  {:color color :left left :value value :right right})

(defn balance [tree]
    ;; case 1
    (let [{z :value d :right} tree
          {x-color :color x :value a :left} (-> tree :left)
          {y-color :color y :value b :left c :right} (-> tree :left :right)
          d (:right tree)]
      (if (and (= x-color :red) (= y-color :red))
        (mk-tree :red
                    (mk-tree :black a x b)
                    y
                    (mk-tree :black c z d))
        tree)
        ...))

I was extremely unhappy with this. A lot of boilerplate around bindings and tests. And this is only the first case.

But if you read Okasaki’s implementation of the algorithm in ML - or Haskell - you’ll quickly realise how concise and elegant it is. The main reason for that is pattern matching, something we don’t have built-in in Clojure.

However, Clojure is a Lisp and has a powerful macros system at its disposal. That has given us core.match, a pattern matching library for Clojure.

core.match

Using core.match, I rewrote my balance function:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

(defn balance [tree]
  (match [tree]
         [(:or {:left {:color :red
                       :left {:color :red :left a :value x :right b}
                       :value y :right c}
                :value z :right d}

               {:left {:color :red
                       :left  a :value x
                       :right {:color :red :value y :left b :right c}}
                :value z :right d}

               {:left a :value x
                :right {:color :red
                        :left {:color :red
                               :left b :value y :right c}
                        :value z :right d}}

               {:left a :value x
                :right {:color :red
                        :left b :value y
                        :right {:color :red
                                :left c :value z :right d}}})]
         (mk-tree :red
                     (mk-tree :black a x b)
                     y
                     (mk-tree :black c z d))

         :else tree))

If you look closely at the patterns being matched, you’ll see they cater for all 4 cases and allow for both matching and binding in the same expressions. With only a little over double the size of a single case using the previous function, we now have a fully functioning balance implementation. This is better, but I wanted more.

What I really wanted to be able to write is this:

1
2
3
4
5
6
7
8
9

(defn balance [tree]
    (match [tree]
           [(:or (Black. (Red. (Red. a x b) y c) z d)
                 (Black. (Red. a x (Red. b y c)) z d)
                 (Black. a x (Red. (Red. b y c) z d))
                 (Black. a x (Red. b y (Red. c z d))))] (Red. (Black. a x b)
                                                              y
                                                              (Black. c z d))
                 :else tree))

Unfortunately core.match doesn’t support records/protocols yet. However, while reading core.match’s source code, I found a test that implemented the balance algorithm using a different way of representing a tree.

You see, I went with the map approach because I like how you can ask for the specific keys that represent the parts of the tree, such as :color, :left, :value and :right. But if you’re happy with using positional elements in a vector to represent your tree, our balance function in Clojure becomes this:

1
2
3
4
5
6
7
8
9

(defn balance [tree]
  (match [tree]
         [(:or [:black [:red [:red a x b] y c] z d]
               [:black [:red a x [:red b y c]] z d]
               [:black a x [:red [:red b y c] z d]]
               [:black a x [:red b y [:red c z d]]])] [:red [:black a x b]
                                                            y
                                                            [:black c z d]]
               :else tree))

Which is amazingly similar to the protocols/records version above.

I guess one of the lessons here is that by carefully choosing the data structure to represent your problem, your implementation can become substantially simpler.

As usual, all code is on github, with the Red-black tree specific section in this direct link. The project also includes tests.

Until next time.

Concurrency is the word but it often leads to complex code, dealing with locks, mutexes etc…

There are several different abstractions which allows us to both model and think about asynchronous code in a more sane fashion: futures, promises and events/callbacks are but a few of them.

I won’t get into the merits - or lack thereof - of these alternatives in this post but rather focus on a different alternative: Communicating Sequential Processes - CSP.

CSP and Go

CSP isn’t new. It was first described in 1978 by Tony Hoare and languages such as Occam and Erlang stem from it.

It has however gained momentum by being natively supported by the Go programming language.

I haven’t read Hoare’s paper so I’ll use a little bit of what I know about Go’s implementation of CSP.

Go introduced the concept of a goroutine. It looks like a function call:

1
2
3

// doing some stuff...
go myFunction("argument") //does stuff in the background...
//continuing about my business...

What this does is it creates a lightweight process and returns control immediately to the caller.

It is lightweight because it doesn’t map 1-1 to native OS threads.

The reasoning behind it is that creating too many threads can bring your machine (or VM) down due to the amount of stack allocated to each one.

goroutines are cheap to create so you can have hundreds of thousands of them, and the runtime will multiplex them into a thread pool.

The immediate advantage is that it is dead simple to achieve a higher degree of concurrency.

So far it sounds awfully similar to using futures with a pre-configured thread pool and a bit of syntactic sugar. But this is not the end of it.

Communication

goroutines really shine when your several lightweight processes need to talk to each other. This is where a new abstraction comes into play:channels.

Channels are first-class citizens - meaning you can pass them as arguments to functions as well as the return value of functions.

Using them is straightforward:

1
2
3
4
5
6

c := make(chan string)
go func() {
  time.Sleep(time.Duration(5000) * time.Millisecond)
  c <- "Leo"
}()
fmt.Printf("Hello: %s\n", <-c) //this will block until the channel has something to give us 

The code above creates a goroutine from an anonymous-executing function that will, in the background, sleep for 5 seconds and then send the string Leo to the channel c. Since control is returned immediately after that, the call blocks on the next line where it’s trying to read a value from the channel using the <-c statement.

Lisp

“But What does all this have to do with Lisp?” - ah! I’m glad you asked.

It actually has more to do with Clojure - and by extension, Lisp.

Clojure is a modern Lisp for the JVM, built for concurrency. The core team recently released core.async, a new library that adds support for asynchronous programming much in the same way Go does with goroutines.

To highlight the similarities, I’ll show and translate a couple of the examples from Rob Pike’s presentation, Go Concurrency patterns.

Setting the scene

Say you’re Google. And you need to write code that takes user input, - a search string - hits 3 different search services, - web, images and video - aggregates the results and presents them to the user.

Since they are three different services, you wish to do this concurrently.

To simulate these services, Rob presented a function that has unpredictable performance based of a random amount of sleep, shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var (
    Web   = fakeSearch("web")
    Image = fakeSearch("image")
    Video = fakeSearch("video")
)

type Search func(query string) Result

func fakeSearch(kind string) Search {
        return func(query string) Result {
              time.Sleep(time.Duration(rand.Intn(100)) * time.Millisecond)
              return Result(fmt.Sprintf("%s result for %q\n", kind, query))
        }
}

This is one way we could write such function in Clojure:

1
2
3
4
5
6
7
8

(defn fake-search [kind]
  (fn [query]
    (Thread/sleep (int (* (java.lang.Math/random) 1000)))
    (str kind " result for " query)))

(def web   (fake-search "Web"))
(def image (fake-search "Image"))
(def video (fake-search "Video"))

Google Search 2.0

The first example is the simple case: we hit the services concurrently, wait for them to respond and then return the results:

This example is from slide #46.

1
2
3
4
5
6
7
8
9
10
11
12

func Google(query string) (results []Result) {
    c := make(chan Result)
    go func() { c <- Web(query) } ()
    go func() { c <- Image(query) } ()
    go func() { c <- Video(query) } ()

    for i := 0; i < 3; i++ {
        result := <-c
        results = append(results, result)
    }
    return
}

And here’s the Clojure version:

1
2
3
4
5
6
7
8
9
10
11
12

(defn google2-0 [query]
  (let [c (chan)]
    (go (>! c (web query)))
    (go (>! c (image query)))
    (go (>! c (video query)))
    (reduce (fn [results _]
              (conj results (<!! (go (<! c)))))
            []
            (range 3))))

(google2-0 "Clojure")
;; prints ["Video result for Clojure" "Web result for Clojure" "Image result for Clojure"]

The >! operator puts a value into a channel inside a go form. The function then uses <!! to block on the c channel until it gets a value we can use.

Google Search 2.1

This is virtually the same example but this time we do not wish to wait on slow servers. So we’ll return whatever results we have after a pre-defined timeout.

This example is from slide #47.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

c := make(chan Result)
go func() { c <- Web(query) } ()
go func() { c <- Image(query) } ()
go func() { c <- Video(query) } ()

timeout := time.After(80 * time.Millisecond)
for i := 0; i < 3; i++ {
    select {
    case result := <-c:
        results = append(results, result)
    case <-timeout:
        fmt.Println("timed out")
        return
    }
}
return

You’ll notice the use of select here.

select waits on multiple channels and returns as soon as any of them has something to say.

The trick of this example is that one of these channels times out, at which point you get the message “timed out”, effectively moving on to the next iteration and ignoring that slow server(s) response.

We can express the same intent in Clojure as well:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(defn google2-1 [query]
  (let [c (chan)
        t (timeout 500)]
    (go (>! c (web query)))
    (go (>! c (image query)))
    (go (>! c (video query)))

    (reduce (fn [results _]
              (conj results (first (alts!! [c t]))))
            []
            (range 3))))


(google2-1 "Clojure")
;; prints ["Video result for Clojure" nil nil]

Everything looks the same but we’re using alts!! to wait on the channels c and t (the timeout channel). This is analogous to Go’s select form in that it waits for any channel to receive a value or, in this case, to timeout.

Note the nil values. Those came from servers which did not respond in time and were simply ignored.

Effectively what this means is that each time you run this function you’ll likely get different results, depending on how long the fake-search function takes to run.

Amazing, huh?

The big deal

But here’s the big deal about this: although core.async looks like it’s deeply integrated into the language, it is just a library!

It’s not a separate compiler. It’s not a new language. And it’s not a special version of Clojure.

Since Clojure supports macros - like all Lisps - the core team was able to create the syntax required to easily use core.async. And that’s the beauty of it!

The Lisp advantage, once again.

Clojure’s advantage

Now one thing I haven’t mentioned is that Clojure is particularly well suited for this - and in a way even more so than Go: Clojure is opinionated and favours immutability.

That means that when using channels - and in fact any type of concurrent programming - you can safely share your data structures between concurrent units of work. Since they’re immutable, you can’t shoot yourself in the foot.

One last thing: core.async states as one of its goals Clojurescript compatibility, bringing channel based concurrent programming to the browser. Exciting stuff.

More on core.async

core.async is still in alpha but you are encouraged to take it for a spin. Documentation is still lacking so I recommend you look at:

• Rich’s blog post about it
• The source code on github
• The walkthrough namespace, which showcases its features.

Also, the full Clojure code I used here can be seen in this gist.

YOW! LambdaJam is a conference targeted at intermediate and advanced functional programmers and is organised in talks, jams and workshops.

• Talks are the traditional format and are 30 minutes long;
• Workshops aim to introduce a specific subjects to attendees in great detail and are up to two hours long;
• Jams are hands-on sessions. Participants will be guided through pre-defined problems around a given subject/technology and encouraged to work through the solutions either by themselves or ideally as small groups. Jams are also 2 hours long;

Sounds pretty amazing, doesn’t it?

If you’re still not convinced, check out the program.

The conference will run for 2 days, May 16-17, in Brisbane. Tickets are on sale.

Clojure

Besides the conference itself, Clojure/core will be giving an Intro to Clojure workshop in Sydney, Melbourne and Brisbane. It’s a great opportunity to learn from the language maintainers.

If you’re attending the conference already, you’re in luck because there is a 20% off discount on the link above if you attend both the conference and the workshop.

In case you’d like to attend the workshops only, you can buy individual tickets for Sydney, Melbourne and Brisbane.

Scala

Tony Morris will also be delivering a Functional Programming in Scala workshop in Brisbane and 20% off combo tickets can be bought from the EventBrite page for LambdaJam.

See you there

Got tickets yet? No? What are you waiting for?

If you haven’t read SICP, you should. It’s an amazing book. It uses Scheme, a dialect of Lisp, as the vehicle to present fundamental programming concepts.

Philip Wadler - the author of this particular paper - contrasts teaching in Scheme to teaching using KRC and Miranda, pointing out four major features he considers important and lacking in Scheme. They are:

• Pattern matching
• A syntax close to traditional mathematical notation
• A static type discipline and user-defined types
• Lazy Evaluation

Note: KRC influenced Miranda which in turn influenced Haskell. Their syntax is similiar, so where Wadler used Miranda code snippets in the paper, I’ll be using Haskell in this post.

As an aside, although the paper talks specifically of Scheme, the term Lisp is used quite loosely and could lead the not-so-careful reader to be misled regarding a whole family of languages. Lisps have come a long way and modern dialects - of which I’ll be focusing on Clojure - address many of the concerns raised by Wadler.

Let us begin.

Pattern Matching

Here Clojure, and most - all? - Lisps, are out of luck.

The example used in the paper is that of summing all integers in a list. First in Haskell:

1
2

sum []   = 0
sum x:xs = x + sum xs

Now in Clojure:

1
2
3
4

(defn sum [coll]
  (if (empty? coll)
      0
      (+ (first coll) (sum (rest coll)))))

The question here is this: Which snippet is easier to read/reason about? the Haskell code!

I must confess that I, too, miss pattern matching sometimes. However we can still improve our Clojure version to read nicer on the eyes by using destructuring:

1
2
3
4

(defn sum [[first & rest :as coll]]
  (if (empty? coll)
      0
      (+ first (sum rest))))

And that’s pretty much it. Without proper pattern matching, we can’t get much better than that.

In addition to the Haskell snippet being easier to read, it’s also easier to prove correct by structural induction, as demonstrated in Wadler’s paper.

Note: core.match adds support to pattern matching in Clojure. At the time of this writing, it’s considered “alpha quality”

Data structures

The paper continues to discuss exercise 2-27 from the SICP, where the reader has to write code to represent a binary mobile, which consists of a left and right branch with each branch being a rod of certain length, from which hangs either a weight or another binary mobile.

Translating the Scheme example to Clojure, such a structure is represented using lists, like so:

1
2
3
4
5

(defn make-mobile [left right]
  (list left right))
  
(defn make-branch [length structure]
  (list length structure))

Wadler then contrasts this with the equivalent Miranda code, translated below to Haskell, taking advantage of algebraic data types:

1
2

data Structure = Weight Int | Mobile Branch Branch
data Branch = Branch Int Structure

The first claim is that the Haskell/Miranda data type declaration makes it clearer what the data structure looks like, which is fair.

Also, the compiler can catch errors early on.

However, when writing idiomatic Clojure code, here’s how I’d actually create this structure:

1
2
3
4
5

(defn make-mobile [left right]
  {:left left :right right})
  
(defn make-branch [length structure]
  {:length length :structure structure})

Granted, it’s still not as clear and the compiler can’t validate the shape of our data structure.

This is however cleaner than the previous version and drives home the point that Clojure isn’t limited to lists, having literals for other data types such as the hash maps used in this example.

The second part of this claim is that through custom data types and pattern mathing, extracting values from those structures becomes simpler:

1
2
3
4

totalWeight (Weight w) = w
totalWeight (Mobile l r) = totalWeightBranch l + totalWeightBranch r

totalWeightBranch(Branch d s) = totalWeight s

Once again Clojure can improve things by taking advantage of its builtin data structures and destructuring:

1
2
3
4
5
6
7
8

(defn total-weight [{:keys [left right] :as structure}]
  (if (number? structure)
      structure
      (+ (total-weight-branch left)
         (total-weight-branch right))))
      
(defn total-weight-branch [{structure :structure}]
  (total-weight structure))     

For a language with no pattern matching nor algebraic data types, this snippet is clear, concise and elegant - and a real improvement over the Scheme version discussed in the paper - which was essentially handicapped by the use of lists to simulate ‘structs’.

As far as Clojure goes, this claim ends here: the next point in the paper, about changing from using list to using cons, is rendered moot since we’re using hash maps to represent our mobiles.

Lisp lists are not self-escaping

Creating lists in Clojure goes like this:

1
2
3

(list (list 1 2) nil) ;; ((1 2) nil)

'((1 2) nil) ;; ((1 2) nil)

Both statements above are equivalent, with the second one being clearly more concise.

The claim here is that the fact that you need to either use the list function or quote the form is cumbersome and can be confusing to beginners.

Clojure solves this by providing literals to another data structure - vectors:

1

[[1 2] nil]

Simple and concise - in fact, in idiomatic Clojure code, you’ll rarely see quoted lists where a vector will do.

This is possible because both lists and vectors conform to a higher level abstraction called a Seq, in terms of which most list operations are defined.

This eliminates the two following points mentioned in the paper as it allows a beginner to defer his/her understanding of quoted forms to more advanced lessons/usages.

Programs that Manipulate Programs - the interpreter example

Here Wadler shows a simple grammar for an interpreter in both Miranda and Scheme.

He claims that since Haskell/Miranda have free data types, representing such grammar becomes simpler:

1
2
3
4
5
6

data Term = Var [Char]
          | Lambda Var Term
          | Apply Term Term
          | Closure Env Var Term
type Env = [(Var, Term)]
type Var = [Char]

This is true in that one can easily scan the snippet above and deduce quickly what Term looks like.

Then, by using pattern matching, eval could be implemented like so:

1
2
3
4
5

eval e (Var v) = lookup e v
eval e (Lambda v t) = Closure e v t
eval e (Apply t0 t1) = apply (eval e t0) (eval e t1)

...

I do believe this makes Haskell an excellent choice for writing interpreters and compilers.

However, the flip side is that entering such terms in Haskell is cumbersome. Consider the term below:

(λx.(x x)) (λx.(x x))

This is how to represent this term using the grammar defined above:

1
2

(apply (Lambda "x" (apply (Var "x") (Var "x")))
       (Lambda "x" (apply (Var "x") (Var "x"))))

The strength in Lisp lies elsewhere. Since we have quoted forms, entering a similar term is a lot less verbose and closer to its intended representation:

1

'((lambda [x] (x x)) (lambda [x] (x x)))

This is, of course, at the expense of making eval a more complicated function:

1
2
3
4
5
6
7
8
9
10

(defn eval [e t]
  (cond (variable? t)
        (lookup e (variable-name t))
        (lambda? t)
        (make-closure e (lambda-var t) (lambda-body t))
        (apply? t)
        (apply (eval e (apply-operator t))
               (eval e (apply-operand t)))))

...

The paper leaves out an important advantage of Lisps though:

Because we can write code for our made up language directly in its (almost)abstract syntax tree form, Lisps are the ideal choice when writing Internal Domain Specific Languages.

Lazy Evaluation

Lists

Haskell and Miranda are lazy languages and that yields a lot of power. This claim is more specific to the use of lazy lists - or sequences, streams - and starts off with a snippet that calculates the sum of squares of all odd numbers from 1 up to 100:

1

sum [ i*i | i <- [1..100], odd i ]

What follows in the paper is a not-so-clear snippet of equivalent functionality using Scheme streams.

Clojure features lazy sequences and list comprehensions, making the above Haskell example trivial to write:

1

(sum (for [i (range 100) :when (odd? i)] (* i i)))

If you’re following at home with the original paper you’ll see this is more readable and elegant than the equivalent Scheme example.

Another - also idiomatic - way to write the same expression is by using a combination of map/filter:

1

(sum (map #(* % %) (filter odd? (range 100))))

Deciding which one is clearer is left as an exercise to the reader.

Special forms and lazy evaluation

In this section, Wadler brings another example from SICP where the reader wishes to implement his/her own if form.

As we know, in order to implement our own version of if, we need to use macros. That is because in Lisps arguments to functions are eagerly evaluated.

One might implement it like this:

1
2
3

(defmacro my-if [pred then else]
  `(cond ~pred ~then
          :else ~else))

In Lazy languages, such as Haskell and Miranda, this problem doesn’t occur allowing such functions to be defined without the need for special and/or quoted forms:

1
2

myIf True  t e = t
myIf False t e = e

However this completely dismisses the power of macros which allow you to extend the language in ways no other language allows - as is extensively demonstrated in books such as On Lisp and Let Over Lambda.

As Guy Steele once put it: ”[…] If you give someone Lisp, he has any language he pleases”

Conclusion

Hopefully this post doesn’t come off as trying to invalidate Wadler’s paper - that is not my intention.

While I do think a few of the points discussed are only applicable to the domain in which his paper was written - teaching - they are still valid and worth understanding.

I do however expect to have given you a different perspective on it, showing the strengths of modern Lisps such as Clojure and how it approaches these issues - such as by using its rich set of data structures, literals and techniques such as destructuring.

This post is part of a series about Chris Okasaki’s Purely Functional Data Structures. You can see all posts in the series by visiting the functional-data-structures category in this blog.

Last year I started reading a book called Purely Functional Data Structures. It’s a fascinating book and if you’ve ever wondered how Clojure’s persistent data structures work, it’s mandatory reading.

However, all code samples in the book are written in ML - with Haskell versions in the end of the book. This means I got stuck in Chapter 3, where the ML snippets start.

I had no clue about Haskell’s - much less ML’s! - syntax and I was finding it very difficult to follow along. What I did notice is that their syntaxes are not so different from each other.

So I put the book down and read Learn You a Haskell For Great Good! with the hopes that learning more about haskell’s syntax - in particular, learning how to read its type signatures - would help me get going with Puretly Functional Data Structures.

Luckily, I was right - and I recommend you do the same if you’re not familiar with either of those languages. Learn You a Haskell For Great Good! is a great book and I got a lot out of it. My series on Monads is a product of reading it.

Enough background though.

The purpose of this post is two-fold: One is to share the github repository I created and that will contain the Clojure versions of the data structures in the book as well as most solutions to the exercises - or at least as many as my time-poor life allows me to implement.

The other is to walk you through some of the code and get a discussion going. Hopefully we will all learn something - as I certainly have when implementing these. Today, we’ll start with Leftist Heaps.

Leftist Heaps

Leftist Heaps - or trees - are a variant of binary heaps that can be used as priority queues. On top of the standard invariants of binary heaps, it obeys the leftist property:

• Every node has a rank, which is the distance from its right spine to the nearest leaf
• A node’s left child has a rank at least as large as its right child

In a nutshell, these are the operations we need to be able to perform on a leftist heap:

• insert a value into an existing heap
• merge two heaps
• find the minimum value in a heap
• delete the minimum value, returning a new heap

Since the book uses ML/Haskell, it starts with a data type definition for Heaps that exposes these and a couple of other auxiliary functions. I decided to take a stab at writing the solution using Clojure’s protocols and records:

1
2
3
4
5
6
7
8
9

(defprotocol Heap
  (is-empty?   [this])
  (insert      [this v])
  (merge       [this other])
  (rank        [this])
  (find-min    [this])
  (delete-min  [this]))

(defrecord LeftistHeap [rank value left right])

When implementing the algorithms the base case for the recursive solutions will involve dealing with nil values which at first seems like it wouldn’t be a problem. However, protocol functions dispatch on the type of its first argument so what happens if I call the function is-empty? on nil?

Luckily, Clojure allows us to extend a protocol to core types:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

(extend-protocol Heap
  nil
  (rank [_] 0)
  (merge [_ other] other)
  (is-empty? [_] true)

  LeftistHeap
  (is-empty? [this]
    (nil? this))

  (rank [this]
    (:rank this))

  (merge [{val-this :value left-this :left right-this :right :as this}
          {val-other :value left-other :left right-other :right :as other}]
    (cond
     (is-empty? other) this
     (<= val-this val-other) (ensure-leftist left-this
                                             (merge right-this other)
                                             val-this)
     :else (ensure-leftist left-other
                           (merge this right-other)
                           val-other)))

  (insert [this v]
    (merge (->LeftistHeap 1 v nil nil)
           this))

  (find-min [{v :value}] v)

  (delete-min [{left :left right :right}]
    (merge right left)))

Note how I extended a few of the protocol functions to the nil data type, allowing me to continue with this implementation with no nasty hacks.

There’s one last bit missing: a function that will ensure each heap retains the leftist property:

1
2
3
4
5
6
7

(defn ensure-leftist
 [this other v]
 (let [rank-this (rank this)
       rank-other (rank other)]
   (if (>= rank-this rank-other)
     (->LeftistHeap (inc rank-other) v this other)
     (->LeftistHeap (inc rank-this) v other this))))

The reason this function is isolated is that the Heap protocol defined above is fairly generic and could be used for defining other types of heaps - and I didn’t feel it warranted its own interface.

We can now play with it and create a new leftist heap:

1
2
3
4
5
6
7

(-> (->LeftistHeap 1 3 nil nil)
                   (insert 2)
                   (insert 7)
                   (insert 4)
                   (insert 10)
                   (insert 1)
                   (insert 20))

While I quite like this approach, I thought I’d also implement this solution using Clojure’s core data types - maps in this case - and no protocols. The code is shown below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

(defn mk-heap [rank value left right]
  {:rank rank :value value :left left :right right})

(defn heap-rank [heap]
  (if (nil? heap)
    0
    (:rank heap)))

(defn ensure-leftist-heap [value heap-a heap-b]
  (let [rank-a (heap-rank heap-a)
        rank-b (heap-rank heap-b)]
    (if (>= rank-a rank-b)
      (mk-heap (inc rank-b) value heap-a heap-b)
      (mk-heap (inc rank-a) value heap-b heap-a))))

(defn merge-heaps [{val-a :value left-a :left right-a :right :as heap-a}
                   {val-b :value left-b :left right-b :right :as heap-b}]
  (cond
   (nil? heap-a) heap-b
   (nil? heap-b) heap-a
   (<= val-a val-b) (ensure-leftist-heap val-a
                                         left-a
                                         (merge-heaps right-a heap-b))
   :else (ensure-leftist-heap val-b
                              left-b
                              (merge-heaps heap-a right-b))))

(defn heap-insert [value heap]
  (merge-heaps (mk-heap 1 value nil nil)
               heap))

(defn heap-find-min [{v :value}] v)

(defn heap-delete-min [{left :left right :right}]
  (merge-heaps right left))

Using it is equally simple:

1
2
3
4
5
6
7

(->> (mk-heap 1 3 nil nil)
                    (heap-insert 2)
                    (heap-insert 7)
                    (heap-insert 4)
                    (heap-insert 10)
                    (heap-insert 1)
                    (heap-insert 20))

That’s it for now.

As I implement more of the book’s code and exercises I’ll add them to the github repo - it also includes tests for all implementations.

Enjoy :)

It’s a validation library for Clojure apps and it lets you write code like this:

1
2
3
4
5

(def person {:name "Leo"})

(validate person
    :name required
    :age  [required number])

If you’d like to see more examples and a detailed guide check out the github repository. The README should get you started.

This post however isn’t only about announcing bouncer. It’s also about the motivation and implementation details behind it.

There are a couple of Clojure validation libraries already out there so why would I write a new one? Well…

• Writing Clojure is fun! (who knew? :P)

• Because I believe this problem can be solved more elegantly with the use of Monads

If you’ve been following me for a while, you’ll know that I spent most of 2012 deepening my knowledge about functional programming.

In that journey, the unavoidable subject of monads came about - and it was both interesting and enlightening enough that made me write a whole series of posts about it.

After learning what they are and then thinking about the validation problem for a while, I couldn’t help but notice that the problem had a lot in common with the State Monad.

In order to explain how the two relate, I’ll have to digress for a moment. It’ll all make sense in the end - or so I hope

Purity

In pure functional languages, such as Haskell, functions can’t have side effects. These include performing IO, changing global variables or launching missiles.

Because of that, functions in Haskell are pure: if you repeatedly call a function f with the same argument x over time you will always get the same result back.

Pure functions are not a feature of Haskell though. We, too, can write pure functions if we wish:

1
2

(defn double [x]
    (+ x x))

The function double above is pure. If we call it with 10, we can be sure the result will always be 20.

This leaves us with a question though: If we were to write our programs with pure functions only, how would we perform computations that need to carry state - state that needs to change over time - around?

A good example of such computation is generating random numbers.

Most programming languages provide generators capable of creating random numbers on demand. Using them is usually trivial. Here’s an example in Java:

1
2
3
4

Random gen = new Random();

gen.nextDouble(); // 0.0037635726242281065
gen.nextDouble(); // 0.15821091918430885

Impurity alert!

The function nextDouble above is obviously not pure. Multiple invocations of it with the same argument - in this case, none - returns different results.

nextDouble is keeping some sort of global state between function calls.

This is where the State Monad comes in. It allows such functions to remain pure.

The State Monad

The State Monad provides a way to abstract state from the function that needs to operate on it.

Sounds confusing? Hopefully an example will clear things up.

Let’s have a look at the clojure function rand:

1
2
3
4

(rand)
;; 0.04388682005715605
(rand)
;; 0.43057496371080517

rand suffers from the same problem as nextDouble we saw above. It keeps it’s own state that is shared across calls, therefore being an impure function.

Now let’s write a pure version of rand. We’ll call it pure-rand:

1
2
3
4
5
6
7
8
9
10

(def gen (java.util.Random.))

(defn pure-rand [g]
    [(.nextDouble g) g])

(pure-rand gen)
;; [0.5783608063218478 #<Random java.util.Random@7f30ab6>]

(pure-rand gen)
;; [0.9251968987499839 #<Random java.util.Random@7f30ab6>]

This is interesting. pure-rand now takes a generator as an argument and returns a two-element vector containing the random number itself - the result we’re actually interested in - and the generator that was passed in.

Recall however that the generator returned, albeit the same object, is in a new sate.

By re-writing the function like this, we’ve regained purity, as demonstrated below:

1
2
3
4
5

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

As you can see, as long as we provide the same generator - the same argument - we get the same result back.

If you’re wondering why I’m returning a two element vector from our little function, the answer lies in the State Monad implementation as found in the algo.monads library.

From its docstring:

State Monad: Monad describing stateful computations. The monadic values have the structure:

(fn [old-state] [result new-state]).

It expects a function that receives its old state and returns the result and the new state - these are called monadic values.

By designing the function to follow this contract, we can leverage the domonad macro - think of it as syntactic sugar for working with monads:

1
2
3
4
5
6
7
8
9
10
11

(require '[clojure.algo.monads :as m])

((m/domonad m/state-m
    [a pure-rand
     b pure-rand
     c pure-rand]
     [a b c])
     (java.util.Random. 100))

;; [[0.7220096548596434 0.19497605734770518 0.6671595726539502] 
;; #<Random java.util.Random@358ddfd6>]

In the example above, we’re using our pure-rand function in the context of the State Monad to generate 3 random numbers - based on some initial state - and returning them as a vector.

As we’ve seen before the result is itself in a vector alongside the new state.

This is where the State Monad and the validation problem meet:

In bouncer, each validation function is designed to be compatible with the State Monad, just like pure-rand above:

It receives an initial state - at first, the map to be validated - and returns a vector with the map of errors and the new state: the original map augmented with any errors from previous validators.

The end result, should one or more validations fail, is a map with all errors that might have happened, plus our new state.

Now if you head to the github repository and read the examples by keeping the State Monad and the above explanation in mind, the similarities should be obvious.

Wrapping up

As I mentioned in the beginning of the article, there are other validation libraries for Clojure and at the time of this writing they have more features than bouncer - by all means have a look at them.

However I will keep maintaining bouncer for a couple of reasons:

• That’s what I’m using in my current side project
• It takes a fundamentally different implementation approach that is in itself worthy of exploration
• If nothing else, this is yet another example of where Monads can be useful.

Acknowledgments

Thanks to Steve and Julian for reviewing early drafts of this post as well as Nick for being such a PITA :) - our discussions led to a considerably nicer design.

As usual, let me know your thoughts.