PragPub 2013-07: Issue #49

Table of Contents

Features

Programming Elixir

by Dave Thomas

Elixir is a modern, functional programming language designed for high availability and concurrency. It has Ruby-like syntax married to the power and reliability of the Erlang VM. If you wanted to get into functional programming but were put off by the academic feel, now’s the time to jump in.

Why Lisp Still Matters

by Michael Bevilacqua-Linn

This issue begins a series on the Clojure language by Michael Bevilacqua-Linn.

An Interview with Tom Preston-Werner

by Jack Kaufman

The co-founder of GitHub chats about being an entrepreneur.

Dependent Types III

by Paul Callaghan

In this final installment in his series on functional programming, Paul shows how much power can be packed into types.

Living with Lambdas

by Alfons Haffmans

You can work in the functional programming paradigm in C++. And you may be surprised at how complete C++’s support for functional programming is.

Departments

Up Front

by Michael Swaine

No, the guy on the back page isn’t David Crosby. Although we can see why you might think so.

Choice Bits

We follow Twitter so you don’t have to.

Rothman & Lester

by Johanna Rothman & Andy Lester

Johanna and Andy share their networking secrets.

Puzzle

by Michael Swaine

A short session in mental calisthenics.

Calendar

Want to meet one of the Pragmatic Bookshelf authors face-to-face? Here’s where they’ll be in the coming months.

Bookshelf

What’s new and what’s hot from the Pragmatic Bookshelf.

Shady Illuminations

by John Shade

John doesn’t exactly review a book.

Rear Window

The personal computer revolution had its roots in 1970s counterculture.

Except where otherwise indicated, entire contents copyright © 2013 The Pragmatic Programmers.

Feel free to distribute this magazine (in whole, and for free) to anyone you want. However, you may not sell this magazine or its content, nor extract and use more than a paragraph of content in some other publication without our permission.

Published monthly in PDF, mobi, and epub formats by The Pragmatic Programmers, LLC, Dallas, TX, and Raleigh, NC. E-Mail support@pragprog.com, phone +1-800-699-7764. The editor is Michael Swaine (mailto:michael@pragprog.com). Visit us at http://pragprog.com

ISSN: 1948-3562

Up Front

From the Secrets of GitHub to Lambdas in C++

by Michael Swaine

Dave Thomas continues his three-part exploration of the Elixir language this month, taking what we learned last month about pattern matching and seeing how Elixir really shines when it turns its pattern-matching light on functions. But that’s not the only functional programming wisdom we have to share. You actually can do functional programming in C++, and Alfons Haffmans has all the gory details.

This month also sees the end of one series of articles and the beginning of another, both focusing on functional themes. Paul Callaghan is wrapping up his series on functional programming, advanced types, and Haskell, while Michael Bevilacqua-Linn starts a series on Clojure with a look at the enduring virtues of Lisp—as realized in Clojure.

If you’re working on your own little software project that’s going to change the world, chances are that where you’re working on it is on GitHub. But GitHub is itself a software project and a startup business, and the story of how it got started and the funding and pricing decisions made early on has lessons for any entrepreneur. Jack Kaufman interviewed GitHub co-founder and CEO Tom Preston-Werner, and you can read what he has to say here this month.

Johanna Rothman and Andy Lester are back with more insights on your career. This month they are talking about how to do business networking without feeling sleazy. John Shade doesn’t mind feeling sleazy, but he does mind having to read 1346-page books, and shares his thoughts in this issue.

Plus there are all the usual features, including a sudoku/anagram puzzle and from the vault, a picture of the “Father of Visual Basic” from his long-haired hippie days.

Choice Bits

From the Twitterstream

We follow Twitter so you don’t have to.

Programmers tweet the darnedest things.

Deep Thoughts

“Political language is designed to make lies sound truthful and murder respectable.” - George Orwell — @dhh

“Evil is a product of the ability of humans to make abstract that which is concrete.” - Sartre — @marick

“Computer programs are an exercise in artificial inelegance.” - Unknown — @aaronblenkush

State surveillance “like pointing at a pixel with a hotdog.” — @doctorow

RT @_svs_ Any sufficiently advanced incompetence is indistinguishable from malice. — @lxt

“Kids: they dance before they learn there is anything that isn’t music.” - William Stafford — @yourdon

The Reviews Are In

Wish #WWDC breakfast had fruit available. — @dastels

JavaScript has a certain beauty to it. Like shiny, clear, broken glass. On a cold toilet seat. In winter. — @PragmaticAndy

“The victory of machine over spirit." - Heine, on the merciless pianoforte, 1843 — @GreatDismal

Coffee shops that aren’t open at 7:30 in the morning?! What kind of heathen world have I awoken too?? — @tswicegood

Showing @kiaofz @elixirlang. He says it’s like the room temperature superconductor of programming languages. — @pragdave

Words to the Wise

Every “That took a lot less/more time than I expected!” is a teachable moment about software estimation. Ignore it at your own expense. — @clarkware

You really have to love writing and reporting. Like it’s more important to you than anything else in your life. — @mmhastings

To understand what recursion is, you must first understand recursion. — @MrAlanCooper

Seven blind men tried to describe an elephant and it got annoyed and trampled them. Moral: don’t grope an elephant you can’t see. — @cdespinosa

Once you learn to see queues and bottlenecks, you’ll see them everywhere. — @mtnygard

RT @lruettimann: Follow the money. When the conferences are big and the parties are large, the industry is worth watching. — @johannarothman

Even a stopped clock is 13:37 once a day. — @undees

Who Are Those Guys?

First, they’re not all guys. Second, we have to confess that we cleaned up their punctuation and stuff a little. OK, who we followed this month: Dave Astels, Aaron Blenkush, Mike Clark, Alan Cooper, Ian Dees, Cory Doctorow, Chris Espinosa, William Gibson, DHH, Michael Hastings, Andy Hunt, Brian Marick, Michael Nygard, Johanna Rothman, Travis Swicegood, Dave Thomas, Laura Thomson, and Ed Yourdon.

Fair’s fair. You can follow us at www.twitter.com/pragpub.

Rothman & Lester

Responsible Networking

by Johanna Rothman & Andy Lester

Johanna and Andy share their networking secrets.

Andy: This month we’re talking about business networking. It’s one of those things that we tend to shy away from because it sounds sleazy, but really it’s not. At least not if you’re not doing it sleazily!

Johanna: To me, building a network is a critical part of being able to hire and be hired. It was a huge part of my success as a hiring manager, and now as a consultant, it’s a major part of my success. I don’t have to cold call, because my people know me. So networking is something I’ve done all of my professional life. But I don’t believe in “working a room” or being sleazy about it. How about you?

Andy: One of the things I see online and when I talk to people at conferences is that they don’t know what “networking” means. People read articles that talk about how important it is to build a professional network, but they don’t learn what it means to build it or, when you do build it, what you do with it.

Johanna: Ah, so maybe the first thing we can do is help people with that. To me, building a professional network is creating a community of like-minded people that I can help. It’s not about just professional help, although that’s part of it. I’m happy to help them in other ways. Do they need a good recommendation for a good book to read about parenting? Back when I had small kids, I was happy to suggest that. I’m sure I’m out of date on that now.:-)

Andy: To me, “networking” just means “talking to other people and getting to know them, and letting them know you.” It’s mostly a social thing. It doesn’t mean going up to complete strangers and saying “Hi, I’m Dave Jones, and I’m looking for a job.” It does mean meeting people and then remembering them.

Johanna: Yes. And, creating a warm relationship.

Andy: Some networking is pretty obvious. You and I, for instance, have collaborated on articles and I’ve reviewed a couple of your books. In the meantime, you know about me, and I know about you. The excellent thing about that is now I have someone that I can talk to about getting a job.

Johanna: If you go to user group meetings, you learn what’s going on for the other person and you empathize with their problems.

Andy: If I got fired tomorrow (and, dear reader, YOU can get fired tomorrow: There is NO job security in the world), you would be one of the first people I’d talk to.

Johanna: And I would be happy to be that person.

Andy: I’d say “Johanna, I just got laid off. Can you give me ideas of people who might be able to find my next job?” I wouldn’t say “Johanna, I need a job, hire me,” but I know that that’s what many people think networking is. I’d ask for your help, but not a handout.

Johanna: That’s because we’ve built a relationship over time. We’ve empathized with each other. We’ve listened to each other. I might suggest three or four people you could talk to. I might suggest some recruiters you could talk to, also, because I happen to know recruiters, but the most valuable piece of networking is those three or four people you could talk to, to see who they know.

Andy: And when I talk to those recruiters, I would tell them that you referred me to them. Because you have a relationship with those people and your name means something. “Oh, Johanna referred you? What can I do for you?”

Johanna: And that increases my value to those recruiters. Just today, I was looking for a post in another blog, and I emailed the blog owner. His blog had moved, and there was no forwarding address. He realized I was in Chicago, and asked if I was available. I had to tell him I was home already! But now that I know he’s there, I can introduce the two of you, since you live in the Chicago area. That’s nice to know.

Andy: Chances are that people who are reading this article are involved in open source, and that’s fantastic as far as networking. Open source is inherently social and networked, and that networking is a great way to make your experience in open source pay off in another way. If you’ve worked on a project with someone, that’s a contact. You know her skills, she knows yours, and that’s an important connection.

Johanna: Right, and the vouching for each other is such an important thing. I may not have worked with you on a software project, but working with you on columns means I know something about how you work. I can be some kind of a reference. That says a lot.

Andy: I think people get nervous about the idea of going to other people about jobs or business, too. I think it adds a bit of stress to the proceedings, and it doesn’t need to.

Johanna: Since you’re not asking for a job right away, I hope it eases the nervousness or the stress. Especially since you want to offer something. Even if you just offer a, “Hello, it’s nice to meet you,” and a smile and a handshake. When I was in Chicago this past week at a conference, I was in a blogger’s lounge. I was supposed to meet people and network. So that’s what I did. I wrote for a while, and every hour or so, I made it my business to stand up and meet people I hadn’t met yet.

Andy: The other day after I picked you up at that conference and we were looking for some place to eat, that was a great example of networking. I’m from the Chicago area, but I didn’t know the north side very well. So we’re driving up Lake Shore Drive, and I think “Oh, I know someone up on the north side, I’ll ask her where to have dinner.” So I call her up, and say “Hey, what’s good on the north side near the lake?” and she says “What are you in the mood for” and I say “BBQ or steak,” and she sends us off to a great BBQ place.

Johanna: It was great! We had a great meal. That’s one of the benefits of networking.

Andy: Networking about jobs is the same thing, just on a different topic. I didn’t ask Melissa to buy me dinner. I just asked for her advice, and she was more than happy to give it to me. We talked about what we were looking for and she gave us a couple of different options. It’s the same as if I came to you and said I was looking for a job, and you said “Well, are you looking for sysadmin work, or DBA, or...” and you could provide different options.

There’s nothing scummy or salesmany about calling up a friend and saying “Hey, what’s good for dinner in this neighborhood,” and so too it is with networking in the business world.

So what kind of people did you meet at the bloggers’ lounge?

Johanna: I met some recruiters, and many HR people. It was at SHRM (Society for Human Resource Management), the humungous HR conference. At any given time, there were about 20 to 30 people in the bloggers’ lounge. To our readers, I’m at least sort-of known. But to these people, I’m an unknown—and I knew that! So I knew I would have to put on a smile and shake hands and introduce myself. So I did.

It was hard the first few times, so I focused on the table I sat at. There were only four people there. And they were friendly. Once I got past those four people, it was easier. I’d also been following some of them on Twitter, so I knew them and told them I followed them on Twitter. That made it easier too.

Andy: Do you feel that difficulty every time?

Johanna: Yes. When I’m in a new situation, I feel uncomfortable. I hate small talk. Hate it. I’m much more comfortable in geek-land. Even though these were bloggers, these were not geeks. So, I was out of my element. I suspect many of our readers can identify with my feelings.

Andy: Absolutely. Many times I’ve given a presentation on networking and job-hunting and afterwards had someone come up to me and say “Well, I’m just not a social person,” which I understand. I’ve not always been as gregarious as I am now. However, the reality is that the person who has a good social network, and who is known by her peers, is going to have more job choices when it times to find a gig.

Johanna: I think that’s why I work so hard at building my network. If I keep building it, I don’t have to build it all at once when I need a new engagement. I have a flow of clients.

Andy: How do you maintain your network? You’re a big fan of LinkedIn, yes?

Johanna: Yes, I am. LinkedIn is the 600-pound gorilla. It allows me to “collect” everyone in one place. And, until exporting contacts broke, I could export my contacts and keep a copy on my hard drive. But I do like it. I find that it allows me to maintain relationships with people in ways I did not expect. I cannot use Facebook for professional relationships. I cannot tell what is private and what is public, and that changes capriciously. But on LinkedIn, you always know. I like it when LinkedIn tells me that someone has changed jobs and I can congratulate that person. That’s part of building a relationship.

Andy: What do you do when you see a job change? You just send the person an email saying “Hey, good job on the job?” Are you sending them email directly or through LinkedIn?

Johanna: Well, I look at what their previous job was, and what their current job is. Sometimes, they have a lateral move. But sometimes, they have a big new job, or they have a promotion or a big change, and then I send a congratulatory email. I’ve had my consulting business almost 19 years, and some of the people have turned into C-level folks. I send them emails directly. I don’t send them email through LinkedIn. Why make them go through another step?

Andy: How much of your network is geek, and how much is non-geek?

Johanna: About 80 percent of my network is geek, and about 20 percent is non-geek. I have a lot of recruiters in my network. That’s because of the hiring books.

Andy: I’ve been spending some time recently adding more of my open source contacts to my network.

Johanna: Well, it’s not the size of your network, it’s what your network can do for you. I also have an email newsletter and I actively ask people to link with me, because when they change jobs, I lose them if they don’t link. I tell people about my books on my newsletter, and workshops, and then, of course, some really great tips.

Andy: I need to actively pursue more links with people who are not geeks. Remember Melissa who we got the dinner recommendation from? She’s a VP at a big educational not-for-profit in Chicago. Earlier that day she’d been telling me about the business problems of working at a not-for-profit and working with the public school system. It was fascinating and educational to hear about entirely non-geek parts of the business world.

Even if all you go to is geek user group meetings, find out the non-geek things about what your geek brethren do. Maybe that guy that you always talk to about Linux distributions works in auto parts manufacturing, or real estate database maintenance, or city government, or health club administration. There are so many different non-geek parts of the world it’s helpful to hear about.

Johanna: People who are loose connections are more likely to help you get your next job. I have a blog post about this. It’s also helpful to prevent you from turning into a dull person!

Andy: Good point. It doesn’t help that we’re often perceived as being unable to talk about anything other than computers and Star Trek.

Johanna and Andy: Gentle readers, we invite you to network with us. As long as you tell us that you read this article, or why you want to network with us, we are happy to connect with you on LinkedIn. Here are our profiles: Andy is here and Johanna is here.

Andy: I hope this has helped some readers get over the fear of the big scary idea of networking and brought it down to size. Next month, we’ll be talking about one of my favorite topics: How do you know what to put in your resume, and what to leave out?

Johanna Rothman helps leaders solve problems and seize opportunities. She consults, speaks, and writes on managing high-technology product development. She enables managers, teams, and organizations to become more effective by applying her pragmatic approaches to the issues of project management, risk management, and people management. She writes the Pragmatic Manager email newsletter and two blogs on www.jrothman.com.

Andy Lester has developed software for more than twenty years in the business world and on the Web in the open source community. Years of sifting through resumes, interviewing unprepared candidates, and even some unwise career choices of his own spurred him to write his nontraditional book on the new guidelines for tech job hunting. Andy is an active member of the open source community, and lives in the Chicago area. He blogs at petdance.com, and can be reached by email at andy@petdance.com.

Send the authors your feedback or discuss the article in the magazine forum.

Programming Elixir

Part 2: Functions and Pipelines

by Dave Thomas

Elixir is a modern, functional programming language designed for high availability and concurrency. It has Ruby-like syntax married to the power and reliability of the Erlang VM. If you wanted to get into functional programming but were put off by the academic feel, now’s the time to jump in.

Last month, we looked at the basics of pattern matching, and saw how it is universal in Elixir—it is the only way to bind a value to a variable or parameter. But pattern matching really shines when we apply it to functions.

Anonymous Functions

Elixir has a nice set of built-in modules. One of these, Enum, lets you work on enumerable collections. One of its most commonly used functions is map, which applies a transformation function to a collection, producing a new collection. Let’s fire up the Elixir interactive shell, iex, and try it.

| iex> Enum.map [2,4,6], fn val -> val * val end
| [4,16,36]

The first argument we pass to map is the collection; in this case a list of three integers. The second argument is an anonymous function.

Anonymous functions (I’m going to call them fns from now on) are defined between the keywords fn and end. A right-facing arrow, -> separates a list of zero or more parameters on the left from the body of the function on the right.

We passed map the function fn val -> val*val end. This fn takes a single parameter, val, and the body of the function multiplies that value by itself, implicitly returning the result.

A fn is just another Elixir value, so we also have written this code as:

| iex> square = fn val -> val * val end
| #Function<erl_eval.6.17052888>
| iex> Enum.map [2,4,6], square
| [4,16,36]

You can call fns using something like a regular function call:

| iex> square.(5)
| 25

The period and the parentheses are required.

Boy, That’s Way Too Much Typing!

No, it’s not, and we don’t reward whining around these parts anyway.

But, that said, Elixir does have a shortcut. (What follows is for Elixir 0.9. The syntax is likely to change in the near future.) Let’s jump straight to the code.

| iex> Enum.map [2,4,6], &1*&1
| [4,16,36]

When Elixir sees &[1-9], it knows that it needs to generate an anonymous function. The function will have from 1 to n parameters, where n is the highest numbered &n value. The body of the function is basically the expression containing the ampersands, with each ampersand value being mapped to the corresponding parameter. So, &1*&1 is logically the same as fn p1 -> p1*p1 end, and rem(&1,&2) becomes fn p1,p2 -> rem(p1,p2) end.

Because fns are just values, you can even write the code as:

| iex> square = &1 * &1
| #Function<erl_eval.6.17052888>
| iex> Enum.map [2,4,6], square
| [4,16,36]

This is a fantastically useful shortcut, but there is a gotcha. When deciding what code to make the body of the fn, Elixir starts at the ampersand term and looks up the parse tree for the immediately enclosing expression. With &1*&1, it’s the multiplication operator. With rem(&1,&2), it’s the function call to rem.

But things go a little haywire if you write &1+&2+&3. That’s because, internally, this is represented as (&1+&2)+&3. Elixir translates the expression containing &1 and &2, so now we have (fn p1,p2 -> p1+p2)+&3. Elixir then complains that &3 can’t exist without a preceding &1 and &2. (And this is why the syntax is likely to be overhauled).

Anyway, the moral is: use the ampersand syntax for simple expressions, and regular fn…end for the rest.

Named Functions

Anonymous functions tend be be used for callback work—they are typically short and localized in their use. Named functions, however, are where the real work gets done.

Named functions can only exist inside Elixir modules. Here’s an example:

| defmodule AsciiDigit do
| def valid?(character) do
| character in ?0..?9
| end
| end
| IO.inspect AsciiDigit.valid? ?4 # => true
| IO.inspect AsciiDigit.valid? ?a # => false

To follow this code, you first have to know that the syntax ?x returns the integer character code for x (so ?0 is 48).

Our example defines a module called AsciiDigit containing a single function, valid?. This takes a character code and returns true if it is a digit from 0 to 9. We use the range operator .. to define the first and last valid character, and the in operator to check for inclusion.

Elixir supports pattern matching when determining which function to run. You can use def multiple times for the same function, each with a different pattern of parameters. Elixir will dynamically choose the one where the parameters match the arguments passed.

An oldie-but-goodie shows this nicely. The specification for the Fibonacci sequence (Brian Hogan groans) is

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

This isn’t code—it’s a mathematical definition. However, we can turn it into code with almost no effort:

| defmodule Fibonacci do
| def fib(0), do: 1
| def fib(1), do: 1
| def fib(n), do: fib(n-2)+fib(n-1)
| end
| Enum.map 0..10, Fibonacci.fib(&1) #=> [1,1,2,3,5,8,13,21,34,55,89]

(I know, I know—this is not an efficient way of calculating the series. I want to show Elixir, and not worry about faster algorithms.)

Despite appearances, there’s just one definition of the fib function in there. It just has three heads—three patterns of arguments that select different bodies.

The first two heads select the cases where the argument is 0 or 1. They use the abbreviated form of the body, do: expr to return 1. The third form is the recursive step. If neither of the first two match, the third one executes.

What happens if we pass our function a negative argument. Right now, it will loop until we run out of stack or patience—subtracting 1 or 2 from a negative number will never reach 0. Fortunately, Elixir has guard clauses, which allow us to put additional constraints on pattern matching.

| defmodule Fibonacci do
| def fib(0), do: 1
| def fib(1), do: 1
| def fib(n) when n > 1, do: fib(n-2)+fib(n-1)
| end
| Fibonacci.fib(10) #=> 89
| Fibonacci.fib(-10)
| # => ** (FunctionClauseError) no function clause matching in Fibonacci.fib/1

Now, when we call fib with a negative number, Elixir can’t find a function clause that matches, and so it raises an exception. If you really wanted to, you could handle this case in code, giving a more application-specific error:

| defmodule Fibonacci do
| def fib(0), do: 1
| def fib(1), do: 1
| def fib(n) when is_integer(n) and n > 1, do: fib(n-2)+fib(n-1)
| def fib(x), do: raise "Can't find fib(#{x})"
| end
| Fibonacci.fib(10) #=> 89
| Fibonacci.fib(-10) #=> ** (RuntimeError) Can't find fib(-10)
| Fibonacci.fib("cat") #=> ** (RuntimeError) Can't find fib(cat)

We extended our guard clause to check that the parameter is an integer, and then added a 4th function head that accepts any parameter and reports an appropriate error.

Verifing Credit Card Numbers

Most of the long number strings we deal with every day (credit card numbers, IMEI numbers in your phone, and so on) have a check digit. This is normally the final digit of the number, and it is calculated using some algorithm that combines all the previous digits. So, when you enter your credit card number, the web page can recalculate the check digit, and verify that it is the same as the last digit in number you gave. It isn’t a check against fraud; it’s simply a quick way of picking up typos.

Probably the most widely used technique is the Luhn Algorithm. It reverses the digits in the number, and splits them into two sets: digits at odd positions in the string, and digits at even positions. It sums the odd digits. For the even digits, if multiplies each by two. If the result is 10 or more, it subtracts 9. It then sums all the results. Adding the sum of odd and even positions will yield a result that’s divisible by 10 for valid numbers.

When I first started with Elixir, my head was still full of conventional ways of doing things. As a result, I’d write something like the following:

| defmodule CheckDigit do
| import Enum
| def valid?(numbers) do
| numbers = reverse(numbers)
| numbers = map(numbers, fn char -> char - ?0 end)
| numbers = map(numbers, fn digit, index -> {digit, index} end)
| { odds, evens } =
| partition(numbers, fn {_digit, index} -> rem(index, 2) == 0 end)
| sum_odd = reduce odds, 0, fn {number, _index}, sum -> sum + number end
| sum_even = reduce evens, 0, fn {number, _index}, sum ->
| result = number * 2
| if result >= 10 do
| result = result - 9
| end
| result + sum
| end
| rem(sum_odd + sum_even, 10) == 0
| end
| end

Ugh! Let’s step through it (hopefully you’re wearing boots).

The Enum module has lots of functions for dealing with collections. We’ll be using many of them in this code, so we import the module. This means we can write map instead of Enum.map.

Our valid? function is passed a list of UTF-8 digits. By coincidence, that’s exactly what the single quoted string literal generates.

Using the description of the Luhn algorithm, we reverse the digits, and then convert the UTF representation to the actual integer value (so ?1, which is 41, gets mapped to 1). At this point, given the argument '123', we’d have a list of integers [3, 2, 1].

Now it gets messy. We need to partition the digits into those on an even position and those at an odd position. To prepare to do that, we use map, passing it the function fn number, index -> {number, index} end. This function takes the actual digit value, along with its index in the list, and maps it to a tuple containing each.

At this point, alarm bells should be ringing. This is just too damn hard. But we plow on, because that’s what programmers do.

The partition function takes a collection and a function. It returns a tuple where the first element is a list of values for which the function returned true, and the second element is the rest of the values.

Now we have to sum the odd values. Whenever you need to reduce a collection to a single value, you’ll probably want to use the reduce function. It takes the collection, an initial value, and a function. This function receives each element of the collection in turn, along with the current value. Whatever the function returns becomes the next current value. So, summing a list of numbers can be done with

| Enum.reduce list, fn val, sum => val + sum end
| # or
| Enum.reduce list, &1 + &2

But what we have is a list of {value, index} tuples. This means we need to use pattern matching on the first parameter of the function to extract just the value. (The underscore in front of _index means we’re ignoring this field.

Summing the even numbers is similar, but we have to do the doubling, and the conversion of numbers ten or above.

At the end of all this, we can test this in iex. I’m using a standard Visa test credit card number here, so don’t go booking a trip to Tahiti using it.

| $ iex validate_cc.exs
| iex> CheckDigit.valid? '4012888888881881'
| true
| iex> CheckDigit.valid? '0412888888881881'
| false

Tidying Up

Our solution works, but the style isn’t very functional. (That’s a polite way of saying it’s butt ugly). To tidy it up, I look for places where there’s clearly something wrong, and see if I can fix them.

The first problem I see is the first three lines. I’m transforming the given number into a reversed set of digits, each with an associated index.

The word transform is the clue. Functional programming is all about transforming data. It’s so important that Elixir has a special operator, |>. This lets us build pipelines of functions, where each transforms the results of the previous. It lets us compose functionality.

Using the pipeline operator, we can rewrite the first three lines as

| numbers
| |> reverse
| |> map(fn char -> char - ?0 end)
| |> map(fn digit, index -> {digit, index} end)

We take the original list, transform it by reversing it, then by converting character codes to integers, and then by adding the index.

The pipeline operator looks like magic, but it’s actually quite simple. It takes the value of the expression on its left, and inserts it as the first argument of the function call on its right, shifting all the other arguments down.

So the second ugliness is all this partitioning and summing. Our problem is that we’re thinking imperatively, not functionally. We are telling Elixir each step of what to do, when instead we should be thinking of the specification of what we want, and let it work out the details.

Think back to our Fibonacci example. There we implemented our specification as three function heads, which matched the two special cases and the one general case. Can we do the same here?

Rather than processing our list of digits one element at a time, what if we process it in twos? This means we’re working with a pair of digits—the first will be the one at an odd position, the second at the even position. We know how to calculate the Luhn number for these two digits, and then we can add the result for them into the result for the remainder of the list. That’s our recursive step.

When we finally empty the list, we will have calculated the required sum, so we can simply return it.

There’s one other case to consider. If the list has an odd number of digits, then when we get to the end, we’ll only have a single element. But we know that element is at an odd position, so we can simply add it to the accumulated sum and return the result.

So, here’s the new version of our code:

| defmodule CheckDigit do
| import Enum
| @doc """
| Determine if a sequence of digits is valid, assuming the last digit is
| a Luhn checksum. (http://en.wikipedia.org/wiki/Luhn_algorithm)
| """
| def valid?(numbers) when is_list(numbers) do
| numbers
| |> reverse
| |> map(&1 - ?0)
| |> sum
| |> rem(10) == 0
| end
| defp sum(digits), do: _sum(digits, 0)
| defp _sum([], sum), do: sum
| defp _sum([odd], sum), do: sum + odd
| defp _sum([odd, even | tail], sum) when even < 5 do
| _sum(tail, sum + odd + even*2)
| end
| defp _sum([odd, even | tail], sum) do
| _sum(tail, sum + odd + even*2 - 9)
| end
| end

The pipeline at the top is now a lot simpler—there’s no messing with indexes, and no temporary variables. It reads like a code version of the spec.

The sum function is an example of a common pattern. We need to set the initial value of the value we’re summing, but we don’t want the code that calls us to know about that detail, so we write a version of sum that just takes the numbers, and then calls the actual implementation, passing in the list and a zero for the initial value. We could give the helper functions the same name, but I prefer using _sum to differentiate them. (Many Elixir programmers would have called them do_sum, but that always strikes me as being too imperative.)

The _sum function has 4 heads:

If the list is empty, we return the sum that we’ve been accumulating in the second parameter.

If the list has one element, add its value to the sum so far and return it. This is the terminating condition for a list with an odd number of elements.

Otherwise, we extract the first two elements from the list. This uses the pattern [odd,even|tail]. The first element is bound to odd, the second to even, and the remainder of the list is bound to tail.

Looking back at the Luhn algorithm, we have two cases to consider. If the result of multiplying the even number by two is less than ten, then that’s the number we add into the sum. We use a guard class to check for this.

Otherwise we have to subtract nine from the product. That’s what the 4th function body does.

Notice how we’re passing the updated sum around as the second parameter to the function—this is a universal pattern when you want to accumulate a value or values across a set of recursive function calls.

What’s Different About this Code

When you write in a language such as Java, C#, or Ruby, you’re working at a number of levels simultaneously. Part of your brain is thinking about the specification—what has to get done. The other part is thinking about the implementation—the nuts and bolts of how to do it. And that’s where things often get bogged down.

Look at the last example. We’re iterating over a set of digits. We’re selecting those with odd or even positions. We’re performing conditional calculations. We’re summing the result. And there isn’t a single control structure in the program. No ifs, no loops. The code pretty much reflects the specification of what we want to happen.

And that’s one of the reasons I’m a fan of functional programming in general, and Elixir in particular.

Next Month

Let’s start getting parallel. We’ll see how we can use Elixir to run hundreds of thousands of processes, and how to coordinate their work.

While you’re waiting, check out the screencasts available on my Elixir book’s home page.

And if you want the real scoop, you can always buy the book. :)

(Fibonacci image from http://www.maths-rometus.org/)

Dave Thomas is a programmer who likes to evangelize cool stuff. He cowrote The Pragmatic Programmer, and was one of the creators of the Agile Manifesto. His book Programming Ruby introduced the Ruby language to the world, and Agile Web Development with Rails helped kickstart the Rails revolution.

Send the author your feedback or discuss the article in the magazine forum.

Why Lisp Still Matters

Getting Clojure

by Michael Bevilacqua-Linn

This issue begins a series on the Clojure language by Michael Bevilacqua-Linn.

Welcome to the first in a series of Pragmatic articles on Clojure, a dynamically typed, practical programming language that targets the JVM and other modern runtimes. Clojure is a language in the Lisp tradition, and in this article we’ll examine one of the things that makes Clojure, and other lisps, special.

Lisp is the second oldest high-level programming language. It was originally created in 1958 by John McCarthy, and has gone through over 50 years of evolution. One of the most recent branches of this evolution is Clojure, a fairly new language targeted at working programmers.

Newcomers to Lisp, Clojure newbies included, are often put off by what seems like a strange syntax. The parentheses are in different places! Oh my!

Given that this syntax is an obvious barrier to widespread adoption, why would anyone decide to create a new Lisp in this day and age?

It turns out that the choice of syntax isn’t arbitrary. It enables the most powerful metaprogramming system yet created. It’s powerful enough that the majority of the language is implemented using it. Putting it another way, a Clojure developer has the power of a compiler writer at their fingertips.

In this article, we’ll introduce this system and see how it’s related to Clojure’s interactive programming environment, the Read Eval Print Loop or REPL.

You know what a REPL is: A user of the REPL types in some Clojure code. The REPL then reads it in, turning it from a string into another data structure. That data structure is then evaluated to produce a value, which is printed. Finally, the REPL will loop back to the beginning, waiting for new input.

The REPL is a good place to get a feel for Clojur. Let’s start off in the classic style by running hello, world in the REPL.

| => (println "hello, world")
| hello, world
| nil

If we’d like to add two numbers together, the syntax looks the same. Here, we add 21 and 21.

| => (+ 21 21)
| 42

Even creating a function follows the same syntax. Here, we create a say-hello which just prints "hello, pragmatic programmers".

| => (defn say-hello [] "hello, pragmatic programmers")
| #'matters/say-hello
| => (say-hello)
| "hello, pragmatic programmers"

There’s one interesting difference between these examples. In the first example, we saw "hello, world" printed, followed by nil. In the second two, there was no nil, we only saw the results 42 and #'matters/say-hello, respectively.

The Eval in REPL takes our code and executes it. Evaluating a bit of code will always produce a value. Since a call to println has no interesting value, it’s being executed only to print something, nil is returned. Our other two examples do have interesting values, the value of two numbers added together and the name of a function we just defined.

Let’s dig into the notion of evaluation in a bit more detail. We’ll build up a simple model of how it works. Most things in Clojure evaluate to themselves. For instance, here we evaluate the integer 1 and string "foo" in the REPL.

| => 1
| 1
| => "foo"
| "foo"

Some things don’t evaluate to themselves, like the calls to println and + we saw earlier. With those, the arguments were first evaluated and then passed into the println function or + operator.

This is a bit more clear if we nest some calls, as we do below. First (* 10 2) is evaluated to get 20, then (+ 22 20) is evaluated to get the final value of 42.

| => (+ 22 (* 10 2))
| 42

We can nest these calls arbitrarily deep, by adding one more layer in the following snippet.

| => (+ 22 (* 10 (/ 4 2)))
| 42

Occasionally, it may be handy to turn off evaluation. We can do so by prepending our snippet of code with a single quote, as we demonstrate here.

| => '(+ 1 1)
| (+ 1 1)

Now that we’ve got a better idea of what evaluation is, let’s take a closer look at what’s getting evaluated. When we type something into the REPL, we’re typing in a series of characters, a string. This isn’t what ultimately gets evaluated by Clojure. Instead, these characters are first passed into the R in REPL, the reader.

The reader takes a series of characters and turns them into some other data structure. To understand this a bit better, let’s take a quick detour into a couple of Clojure’s built-in data structures: vectors and keywords.

Keywords are used much as we would use a keyword in Ruby or an enum in Java, and are prepended with a colon.

| => :foo
| :foo

Vectors give us fast positional access to their elements. They can be created by placing the elements of the vector inside of square braces. We create a vector and name it some-keywords in the following snippet.

| => (def some-keywords [:foo :bar :baz])
| #'matters/some-keywords

We can use first to get the first element of a vector.

| => (first some-keywords)
| :foo

In the preceding example, the actions of the reader take place behind the scenes, as part of the REPL. Let’s make things a bit more explicit by using read-string. This takes a string directly and reads it. Here, we’re using it to read in a new vector and name it some-more-keywords.

| => (def some-more-keywords (read-string "[:foo :bar :baz]"))
| #'matters/some-more-keywords

We can treat it just as we did our original vector.

| => (first some-more-keywords)
| :foo

So far, the reader might remind you of something like Json or YAML. It takes a string and turns it into some more complicated, probably nested, data structure. That’s not far off, but something about it might strike you as odd. Here I am claiming that the Read in REPL reads in data that we can manipulate in our code, much like a Json or YAML parser would.

But aren’t we typing code into the REPL? How does that work?

To find out, let’s take a look at another Clojure data structure, the list. In Clojure, as in other Lisps, a list is a singly linked list. One way to create a list is to use list, as we do in the following code snippet.

| => (def a-list (list :foo :bar :baz))
| #'matters/a-list

Another way is to simply enclose the list elements in round braces. Here we do that using read-string this time, just as we did with our earlier vector.

| => (def another-list (read-string "(:foo :bar :baz)"))
| #'matters/another-list

These two lists are equivalent.

| => (first a-list)
| :foo
| => (first another-list)
| :foo
| => (= a-list another-list)
| true

Let’s take a look at another list. Here, we create a list with three elements, the symbol + and the integers 21 and 21.

| => (def funky-looking-list (read-string "(+ 21 21)"))
| #'matters/funky-looking-list

And here, we use the first function to get the first element.

| => (first funky-looking-list)
| +

Our first two list examples just contain keywords; our final one obviously contains code! Clojure code is just Clojure data, a property known as homoiconicity. The evaluation rule that we hinted at earlier for function calls is actually the evaluation rule for lists. We can see this by evaluating funky-looking-list manually, as we do in the following snippet.

| => (eval funky-looking-list)
| 42

Because Clojure code is just Clojure data, we can manipulate it just as we would any other data. This gives us, the humble application- or framework-programmer, an incredible amount of power.

To see how, we’ll need to understand Clojure’s macro system. A macro is a special kind of function. It’s intended to take a piece of data which represents code, also known as a form. A macro transforms one form into another before Clojure’s compiler compiles it. Finally, the evaluation rule for a macro is special in that a macro does not evaluate its arguments.

Let’s take a look at a simple macro. This macro takes two arguments, a name and a string to print. It then creates a function that prints the passed-in string.

| (defmacro make-printer [name to-print]
| (list 'defn name [] (list 'println to-print)))

Here we’ll use it to create a function named foo.

| => (make-printer foo "this is a foo")
| #'matters/foo

| => (foo)
| this is a foo
| nil

If we’d like to see what this macro expands out to, we can use macroexpand-1 on a call to it, as we do in the following code.

| => (macroexpand-1 '(make-printer foo "foo"))
| (defn foo [] (println "foo"))

In make-printer we constructed the list that our function definition consists of using list and '. Clojure has a feature that makes this easier, syntax quote, represented by a single backtick.

Syntax quote is much like regular quote. The main difference is that it allows us to turn evaluation back on inside of it using unquote, represented by a tilde. In addition, syntax quote will fully qualify any symbols it comes across, which helps avoid a common pitfall in macro writing known as unintentional name capture.

Here, we’ve got a simple use of syntax quote. As we can see, it evaluates the inner forms (+ 1 2) and (+ 3 4) as we’ve applied unquote to them, but leaves the outer form unevaluated.

| => `(+ ~(+ 1 2) ~(+ 3 4))
| (clojure.core/+ 3 7)

Syntax quote is useful because it allows us to write macros that look like templates for the code that they’ll generate. For instance, here’s our make-printer rewritten to use syntax quote.

| (defmacro make-printer-2 [name to-print]
| `(defn ~name [] (println ~to-print)))

And here’s what it expands out to.

| => (macroexpand-1 '(make-printer-2 foo "foo"))
| (clojure.core/defn foo [] (clojure.core/println "foo"))

Much of Clojure’s core functionality is built using macros. For instance defn expands to def and fn, as we show below.

| => (macroexpand-1 '(defn say-hello [] "hello, pragmatic programmers"))
| (def say-hello (clojure.core/fn ([] "hello, pragmatic programmers")))

In summary: Clojure code is just Clojure data. We can use the macro system and syntax quote to write code templates that look like the code they generate. This makes macroprogramming, an inherently difficult activity, about as easy as it’ll ever get. In fact, the macroprogramming so enabled is powerful enough that much of Clojure’s functionality is implemented using it.

A couple of final notes on Eval. First off, the model of Eval that we built up here is incomplete in several ways. Most notably, Clojure supports a form of lazy evaluation, which defers the evaluation of a form until it’s needed. Second, it’s tempting to think that the Eval in other languages, such as Javascript, is the same as the Eval in a Lisp like Clojure.

Don’t be fooled by those imitators! In Javascript and most other languages, Eval operates on strings. This means writing any significant program must be done by string manipulation, an extremely error-prone and difficult proposition for large problems.

Next month, we’ll examine another thing that makes Clojure special. Clojure has a unique, intuitive view on state and identity that make it ideal for concurrent programming. Thanks for reading. I’m looking forward to next month!

Michael Bevilacqua-Linn has been programming computers ever since he dragged an Apple IIGS that his parents got for opening a bank account into his fifth grade class to explain loops and variables to a bunch of pre-teenagers. He currently works for Comcast, where he builds distributed systems that power infrastructure for their next generation services, and wrote Functional Programming Patterns for the Pragmatic Bookshelf. He tweets occasionally at @NovusTiro.

Send the author your feedback or discuss the article in the magazine forum.

An Interview with Tom Preston-Werner

Chatting with the CEO of GitHub

by Jack Kaufman

The co-founder of GitHub chats about being an entrepreneur.

Jack Kaufman has created a book filled with interviews with tech entrepreneurs. This interview with the CEO and co-founder of GitHub is from that book.

jk: Why did you decide to raise $100 million dollars for GitHub?

tp: Well, there were a couple of reasons. A big one was we’re growing as a company. Around the time we took the investment we were around 100 people. So leading up to it we spent a lot of time talking to various VC’s over the years, just kind of seeing what they were like, seeing what they thought about the landscape of software development and developer tools. So we got a good sense of the variety of venture capitalists and how they might be able to help us.

About a year ago now, almost, we started thinking more seriously about the size of the company, where we were going, what our ambitions were, and what the best way to achieve those dreams were. Being a bootstrapped company, we were making money. We were hiring really well. We weren’t constrained so much by money but the ambitions that we had. What we wanted to achieve we felt could be done more quickly if we removed money as a limiting factor.

So if we were able to invest more, more quickly, then we could build out the enterprise, offering additional products, be able to hire for a wider variety of things, and just invest more in research and development-type efforts more quickly to do all the things that we had in our minds.

So we met all the best VC firms that we could. We got introductions. We’d been around for long enough at that point that we could reach out and get introductions to pretty much any of the VC firms that we wanted to, so we went for the very best ones that we could find. We contacted them, some we’d already been talking to, some of them were new.

We just started having dinners and talking casually with various people from these top-tier firms and kind of feeling out where they were at as far as what they believed in. A lot of it was looking for a philosophical mesh, someone that had the same kind of view of what the future of software development could be.

Over the course of about six or seven months we talked to a variety of them and got to a point where there were some really excellent partners. A huge piece of it was finding the right person that would come on our board, what their background was, what the background of the VC firm was, how they worked together, what their offering was as far as what they get you, their connections, how much noise can they make for us, all these kinds of things went into that equation.

So we looked at our situation and we said, well, the landscape was really excellent for taking investment. This was in early to middle 2012. We’ve been profitable for a long time so the VC firms already knew about us. They already knew that we were capable of running a business. We knew that they weren’t going to come in and start interfering.

Another thing that was on our minds was being able to be independent, not giving up control. So that was a big part of it, just feeling out the various firms and seeing what their perception for founder-led companies was. None of us had any interest in stepping down or hiring an external CEO or executive team or anything like that. We wanted to maintain control so we needed to find a partner that had that same type of viewpoint.

When we came across Andreessen Horowitz, they matched all of these criteria. Just having people like Marc Andreessen and our board member, Peter Levine, who’s been a CEO before, ran Xen-source, and was a big part of their toss before that. Having these guys available to us to ask questions and for them to look at what we’re doing and offer suggestions about how we might accomplish what we want to faster and easier, it has been awesome and that’s exactly why we brought them on board.

The money is great. The people are even better. Combine them both and you get a future of GitHub that is much richer and happens much faster than it would have otherwise. At the same time, we’re not giving up any control and we didn’t have to give up that much of the company for it. So at the end of the day, it’s a win-win for everyone.

jk: What are some of the ways that you and your team market GitHub and grow GitHub?

tp: The biggest thing for us was getting it used in our programming community, which was the Ruby programming community, in the early days. So finding people that are close to you and being part of the community is a great way to get started when you don’t have much of a product yet and you don’t have much money to market it properly. Then integrating into a community and sharing it with that community is really powerful.

We went to programming meet-ups, that’s where our community was here in San Francisco. I guess that most people can find a community, whether it’s in person or virtual, that you can start hanging out with, figuring out what people’s needs are. When you build a product, those are the people that are going to be most interested.

If they find it useful and they start using it, then they’ll want to tell their friends about it. So you can start spreading it in that kind of way; starting with a community that really cares, that you can talk to in person.

From there, what we did was we started going to conferences. We started talking about it publicly after it had publicly launched. In the early days too, we used a strategy that’s pretty common in these days, but that was really effective, which Gmail used very effectively, which was during the private beta phase, we made it so that you had to have an invite to get an account. You could use the site from a consumption perspective but you couldn’t upload any code or anything unless you had an account.

To do that, we invited our friends, the people that we knew initially, and we said “Here are five invite codes that you can send to your friends.” So it creates an artificial scarcity of invites that makes two things possible.

The first one is it prevents too many people from getting on your system too quickly. This is especially important if you haven’t figured your back-end out completely yet and you don’t want to suffer scaling issues. You can see problems as they arise instead of just being covered [in] an avalanche of people all at once. That’s not a good experience for anyone.

And number two, it makes your site seem more attractive. This is the “you want it because you can’t have it” kind of mentality. This makes people tweet about it. People are tweeting about wanting invites, seeing if their friends have any. So you get a bit more exposure that way than you would otherwise, I think. That worked really well for us. I mean, you’ve got to have some traction for that to work but if you can get to the right place, then it’s super effective.

So we did that in the earliest days. Once we publicly launched, we started going to conferences, internationally too, this was big for us. We started traveling internationally to a bunch of conferences talking about GitHub and holding what we call “drink-ups,” which are essentially meet-ups but we just meet at a bar and buy developers beer and they are immediately our best friends and they check out the site.

They like us because we do that and we get people together that wouldn’t normally be together to talk about being developers and programming and everything so it’s just a very good social way to bring people together. Which is what we have this for, bringing a group together, making it easier to work together. We’ve been doing that for years and it’s been really effective. It’s an incredibly cheap way to do very strong loyalty-creating advertising. If you can buy someone something, whether it’s with beer or... well, beer works really well.

We haven’t done much traditional marketing. We don’t do advertising, really, anywhere. We gave out shirts and things at the conferences. If you’re going to give out stuff, having it be really good quality is super important because nobody’s going to wear a crappy t-shirt that has a crappy logo on it. You have to think about the design and the quality of the shirt. Since the very beginning, we’ve only ever printed on American Apparel shirts, which are quite expensive from the giving-them-away standpoint. Wholesale, those shirts are like $8 and something and then it’s another couple of dollars to get them printed. So at the end of the day, you’re talking $10 to $15, depending on the design, per shirt.

So if you go to a conference and you give away 300 to 500 of those, it’s not cheap. It’s a significant investment but it’s worth it because then people will actually wear the damn things instead of just putting them in their closet and using them as rags for changing their oil.

So you can either invest a small amount and get zero return, or you can invest a more significant amount and get a real return. For us, we chose the latter and that’s been really effective too because people care about your brand and over time if you are cheap about marketing kinds of things, people will realize that, and they’ll associate your brand with just cheap, crappy merchandise. So if you’re going to do merchandise, you’ve got to do it well, otherwise just don’t do it at all.

Now we sell hundreds of thousands of dollars of merchandise through our store every year. People buy this stuff willingly now because they like the brand. They know that we create quality merchandise. From a marketing perspective, they’re happy to pay for it because they know that it’s good and that we care about that stuff. The only way that that can happen is if you care about it and if you spend some money on it.

jk: Why did you decide to use a freemium model for GitHub? How do you think the freemium model has helped grow GitHub?

tp: We decided to go freemium when we launched initially. There were a couple of different ways that we could have charged for GitHub. Chris and I sat down when we were first starting it and talked about what the billing model was going to be and we looked at who the users were going to be. There are really two kinds of users at GitHub. There’s open-source users and then there’s private, company users.

We said, well, we could charge everyone to use GitHub, including both open-source people and regular-company people, but the problem is that kind of sucks for open-source users. I mean, they’re doing open source, a lot of them, in their free time. The whole point of open source is that it’s free and it’s open, everyone can do it. So we said it would make more sense to make it free for people doing open source because otherwise they’re probably just not going to use it for that at all and that would be terrible.

Having a lot of people use GitHub for free for open source would get us a significant advertising surface area; this ties into the last question. Another huge way that we advertise is by making it free for open-source users. Because now look at all the open-source on GitHub that people from around the world are searching for and ending up on our website. That only happens because so many people can use it for free. So that’s an investment in open source, really, and it has an advertising outcome and that’s worked really well too.

So having it be free for open source users has a lot of benefits and it allows us to contribute back to the open-source community, which we love. We are open-source developers ourselves, we come from that, and we would never have been able to build GitHub without all of the open sources available. So any time we can contribute back to the open source world, we do.

So we said, okay, if it’s going to be free for open-source people then the way that we would make money is by charging company people using it for private repositories. So what’s the best way to do that? The thing that is really limiting for us, the thing that’s most important for us, is this concept of the project or a repository. This is how Git works, really.

So let’s make it really easy to understand and, say, free for open source users and if you want private projects, then you pay for those. And the more private projects you have, the more that you pay so let’s have some plans and then let’s charge a pretty reasonable amount for them so that people can get started really easily.

You have to remember, five years ago nobody even knew what Git was, so the only way that we figured that we could get people on board was by making the cheapest plan super affordable, give them, I think, five repositories, which is enough to get started, and charge a small enough amount per month that basically you don’t notice. Then the reasoning that it ended up being $7 a month was that, well, you think $5 is small enough that most people aren’t going to worry about it too much. That’s pretty easy to get into, $5 a month.

Ten dollars a month is probably the point around where people start noticing. It’s like $10 a month, that’s significant. That’s over $100 a year. That’s something I would notice, $10. And if anyone’s going to pay $5 for something without worrying about it, then they’ll probably pay $7. The difference is too small to be really noticeable. So we went with $7 because it was not $10 but so little over $5 that it’s indistinguishable.

And that’s worked super well. We have a ton of people paying $7 a month and it represents a huge amount of our user base. It makes us really strong: because we have so many customers paying a small amount, it means that if any one customer decides to leave the service, it’s not a huge deal. So if you can get a lot of users paying a small amount, that’s a pretty big win.

That’s what we launched with. We didn’t know how well that was going to work but it seemed to us that it was right, that that was the right model to launch with. So that’s what we did and people started paying immediately for it and it was easy for them to ramp up. The cheapest plan was cheap enough that they didn’t care. If they got more repositories then the next plans were not these huge monetary jumps and they could ramp up as they used the product more.

The freemium model doesn’t work that great for everyone but it worked well for us because it is a rich product and you can use the entire thing. Every feature of GitHub that there is, you can use for free if you’re using for open source. Everything. There’s nothing restricted. There is not a single feature that you get when you pay for it that you don’t get when you use it for open source except privacy. That’s it.

So the model’s very simple for people to understand. They come on board, and they can try it out for free. They know that if they pay for it, they’re getting exactly the same thing, it’s just now they have control over privacy. So that’s why we chose it. Because we wanted to be able to make money on it, we wanted to have a business model.

We didn’t want to make it just free for everyone and we wanted it to be free for open source so we had to charge for privacy where it makes sense for that to be the distinguishing factor and it came out of how we wanted to charge for it. We didn’t go into it saying, “We should probably do freemium.” That didn’t matter. I don’t even know if freemium was a thing back then. We just did what we thought would be the best from a business perspective and it ended up being freemium and it ended up working super well for us.

jk: What do you think are the most important responsibilities for the CEO of a startup or business to have?

tp: I think what’s really important is setting the vision for the company and often this lands on a CEO. As CEO of GitHub, I am one man. Decisions at GitHub don’t happen just from me. Everything that we do, we get together and we talk about it. Talking about things and arguing through things helps us make better decisions so it’s rare that I would ever come up with a big change for the company by myself.

So when I say the CEO should be setting the vision of the company, he or she is probably the only one that is going to be called on to communicate the vision of the company and make sure that the vision of the company has been established and is well communicated, and that falls on me right now.

I happily take that on because it’s the best way to run a team without having to tell everyone what to do all the time, which is stupid. That’s not how you should ever run a business. What you want to do is set a compelling vision that people can get behind and then just let them do it.

The way I like to talk about it is I point the direction that we’re going and everyone else figures out how to get there. As long as people understand and can believe in the vision and see that as something that’s valuable in the world and you hire the right people, then they’ll do that and that’s why you hired them. You hired them to help you do that and you have to let them go do that. So that’s what we do. There’s a huge amount of autonomy at GitHub, letting people figure out the best solutions for things, coming up with new products, everything.

But it all is in service to the big idea of the company. So for us, the big idea that we have right now is to make it easier to work together than to work alone. It’s a concrete thing but it has broad application, which is great. It’s not so narrow that you can’t work on a lot of stuff towards that goal. It can be applied to a lot of what you do and it’s big enough and important enough where people can look at it and say, “Yes, I want to do that and that’s going to enrich my life to help do that.”

I think a vision statement should be one sentence and probably not more than about 10 words. That’s when you get a really compelling vision. It has to be simple enough, broad enough to be big, so big enough that it’s hard to do but narrow enough that you know what it means and how you can apply it. That’s a huge role of the CEO. That’s one of the biggest.

jk: What piece of advice that you haven’t already mentioned would you give to someone looking to start a business?

tp: I’d say the biggest hurdle to running a business is just doing it, is just the bravery involved in stopping what you’re doing now and deciding to go do it. That’s the hardest part. We can all come up with great ideas and everyone has a million ideas for mobile apps that are going to change the world. The hardest part is sitting down and saying, “I’m going to do this, and it’s going to be hard but I’m going to keep doing it.”

So that’s the thing, it takes a large amount of mental fortitude to do it. But for those that are inclined to do so, especially people that come from a developer background, I’d say it’s the best thing that you’ll ever do, the best, most rewarding, most important, and the biggest chance to learn and change the world that you can ever embark upon. Even if you fail, even if things don’t work out, you’re a developer. You’re not going to be lacking for work. If you’re a developer who’s starting a company, that makes you even more employable, even if it fails.

That’s the hardest thing, is just deciding... deciding to do it and doing it and being serious about it and not stopping when it gets hard. Because you’re going to run into stuff, and you’re not going to be able to find the right co-founder. You’re not going to get investment when you think you should. People aren’t going to pay attention. Your stories don’t get on the homepage of Hacker News as often as you want. None of that matters. The only thing that matters in running a successful business is just keep doing it. Eventually you’ll figure that out.

Jack Kaufman is a 17-year-old who is passionate about business, entrepreneurship, and technology. He is the author of The Found a Business Book, which contains 33 interviews with successful technology entrepreneurs. Next year Jack will be heading off to Haverford College, and you can follow him on Twitter at @kaufman_jack.

Send the author your feedback or discuss the article in the magazine forum.

Dependent Types III

From Properties into Types

by Paul Callaghan

In this final installment in his series on functional programming, Paul shows how much power can be packed into types.

Depending upon your perspective, I have some good news or some bad news. This is the last article in my series.

I’ll use it to cover some important ideas about programming with dependent types and develop a stronger version of the line-packing code. Inevitably, due to article constraints, some details will be left out or left dangling, but perhaps you will find solace when you discover I'm writing a book. Additional resources are mentioned at the end of the article.

In the May issue of PragPub, we had begun to explore the kinds of property that we wanted to establish, for example, that the function for splitting a long word into chunks of size n did not produce chunks that were longer than n. This we could write as the proposition that for all sizes n and lists l, that the maximum length of the split chunks is less than or equal to n, hence:

ok_split : (n:Nat) -> (l:List a) -> LTE (maxLength $ splitIntoSize n l) n

But actually proving this wasn’t terribly attractive. Remember that in this world, proving such a thing corresponds to writing some code that, through a mix of pattern-matching and use of other code, yields a type equal to the above. The great thing is that working in this “classical” style is not the only option, and we can use the richer programming language to do it in a more convenient way.

A key part of this extra power comes from “Inductive Families”: a generalization of data types that allow us to embed data, logic, and dependencies in the data we work with. This extra information helps to make the reasoning more direct, and hence easier to do the proofs. You’ll also see some interesting effects on the programs we write, such as not having to write code for cases that logically can’t ever occur.

A simple but significant example is taking the head of an empty list. Some languages return nil for this (which has its own problems), others like Haskell cause a run-time error because there’s no sensible way to continue.

It’s arguably the Haskell version of most other languages’ null pointer exception (NPE), and like the NPE, there’s no good reason why we should have to run the risk of it happening. One easy way to eliminate it is to have a form of lists that carry size information in their types, and only allow use of head on a non-empty list.

Note that the compiler will complain if we ever try to take the head of an empty list in this type, before the code ever runs, and once it is past the compiler, it does not need to be checked again. Ever. It is not the same as dynamic or run-time checks, which may have to repeatedly check and if the check fails, do something annoying like throw an exception. I know which one I prefer. Yes, you have to do a bit more work, but I claim the tradeoff is starting to tilt in our direction as we explore and develop the technology.

Working with Vectors

Quite a bit of the word-wrap code deals with limits on sizes, so let’s have a type that shows some size information on the outside of the box. Lists with sizes are usually called “Vectors,” and they are defined in the Idris Prelude like this:

| data Vect : Type -> Nat -> Type where
| Nil : Vect a O
| (::) : a -> Vect a n -> Vect a (S n)

This definition and some supporting functions are automatically available in your Idris session or program without needing any additional imports. (Other more specialized functionality is available in the Idris library too, which you can just import when required.)

The first line says there’s a group or family of related types Vect a n where a is some type (anything, pretty much) that is the type of the elements in the vector, and where n is a size expressed as a natural number (i.e., 0 or 1 + x where x is a natural number: please see previous articles).Notice that the size can’t be negative, since this can’t be expressed in the Nat type.

Then, there are two “canonical” ways to build such vectors. First, the Nil constructor that creates a vector of size zero (and with any element type, because there are no actual elements to constrain us to a particular element type!). Second, the constructor (::) (also called 'cons' or 'vcons' in discussions) that joins an element onto a vector of size n to give a vector whose size is one bigger. These are the only ways to build proper elements. Notice that the pattern is similar to how we define vanilla lists, but we have added meaningful size information.

So, building elements is slightly different, since the constructors don’t have to build into the exact same type each time. What does this mean? Well, for lists [] is a list and so is x :: xs—lists all around. For vectors, Nil produces a vector of a particular size (zero) and (::) builds vectors of non-empty size (one plus the size of its tail). Not that these are the only ways to build the respective cases, it’s just how we chose to define vectors.

We can use this information in reverse, too, to take information in the type to influence or restrict or direct the de-construction (i.e., pattern matching) of values as we manipulate them. This is an important point: the extra information makes pattern matching different in various interesting ways, which we’ll see through various examples.

Last time, I mentioned the safe vector head operation. Since it doesn’t make sense to take the head of an empty vector, we write the type signature to make it clear that we avoid the size zero case. How’s it avoided? Because S n for any choice of n will never unify with O, hence any attempt to call head on an empty vector will fail type checking.

| head : Vect a (S n) -> a
| head (x::xs) = x

The definition above is also 'total' because no Nil case is required, and the checking mechanism can infer this from the type signature. We don’t have to work this bit out, and if we tried to add it, the checker would complain. (See the May article for further information on totality.) But if we wanted to remind ourselves of this fact, and protect against certain code changes, then we could write an assertion head Nil impossible as one of the clauses.

Notice we don’t need to mention a or n in the pattern above. This information is left implicit, and filled in as needed—yep, you guessed it, using mostly unification again. However, have you noticed that a and n don’t behave the same way? The payload type a is a parameter of the type, since it is the same every where it appears, whereas the size n is called an index because it can change depending on the various constructors. Just keep this in the back of your mind for now.

Some More Vector Functions

There are some basic vector operations we’ll need later on, so let’s take a quick look. First, vector append, or joining two vectors together. The definition is quite boring, pretty much what you’d expect for vanilla lists, although remember that the implicit arguments (a and n) are being manipulated behind the scenes. The key thing is the type it has: it basically says that appending a vector of size m with one of size n gives one of size m + n.

| (++) : Vect a m -> Vect a n -> Vect a (m + n)
| (++) [] ys = ys
| (++) (x::xs) ys = x :: xs ++ ys

Notice what this type is NOT saying though: it gives no guarantee that we don’t mix up the vector contents in any way, like repeating elements or reversing them or putting elements from the first vector at the end. We could, if we wanted, but it might not be worth the effort. Remember that, like with tests, we probably want a tradeoff between thoroughness and reasonable confidence.

For the line-packing code, I’m assuming that respecting the line width is the key thing, and so the code here is slanted towards that. But if it gives me nicely formatted junk, then it’s still junk, but simple testing will quickly highlight any problems. (Yes, I’m suggesting that some things are easier to check with testing; and some with the techniques here, i.e., that it isn’t a one-size-fits-all and that we should explore why. More simply, mistakes in ordering could be apparent with basic testing (e.g., always building a result list in the wrong order), whereas mistakes in slicing and packing might be harder to spot (e.g., off by one error in indexing in some edge case). The point is, the cases and their effects differ, and it’d be great to exploit this. But I haven’t got time to investigate that here! Rats.)

Another useful function here is take on a Vector. Conventional take n xs on lists usually allows a short list to be returned if the slice size n is bigger than the length of the input list xs. To simplify things later and avoid an explosion of cases, I’m going to use a precise version that only works when the input vector contains at least enough elements, and can’t be used if the input is smaller than required. (Note: this version of take differs from the version currently used in the Idris Prelude.)

| take : (n:Nat) -> Vect a (n + o) -> Vect a n
| take O _ = []
| take (S n) (x :: xs) = x :: take n xs

The two clauses should make sense, but again the interesting part is the type. Like with head, the type will ensure that it can only be used when there are enough elements to take. Similarly, we’ll also use drop : (n:Nat) -> Vect a (n + o) -> Vect a o, with the requirement that there are enough elements to drop.

You may be wondering about how these constraints work. Basically, there are two main aspects. Firstly, the arguments could be concrete enough to computation to reach a unifiable state with the type, and the code is allowed to run. For example, take 3 [1,2,3,4] is ok and gives back the expected result. Secondly, if direct computation doesn’t yield a match, then you can try using what you know about the various arguments to prove that the call is ok. For example, you want take 3 v though you have only v : Vect a m, but if you also have a proof hyp : m = n + o then you can use hyp to get a version of v with the matching type. Yes, it’s more work, though typically this kind of extra reasoning is providing explicit justification for some detail in code that would normally be handled by hand-waving and/or finger-crossing.

Customizing Code to People?

Before we move on, I just want to flag up some of the interesting discussion on Reddit arising from the April article.

It’s worth a read. It covers some more background and shows that some aspects of this field are still open to healthy and active debate. One thread mentioned other possibilities such as Intersection Types. The main discussion covered the “fragility” of code under certain kinds of changes.

For example, the take code above passes the type check because of the way that x + y is defined and how it computes. Fortunately for us, the pattern of recursion in the current definition mirrors the pattern we need in take so we don’t have to justify it. To put it another way, we get the “theorems” that O + y = y and (S x) + y = S (x + y) for free from the current definition because the LHS reduces to the RHS through one step of computation, and so we don’t need to mention these explicitly in the definition of take. Contrast that with x + (S y) = S (x + y) which would have to be proven and then explicitly applied.

(Side point: are we really happy with the above definition of take? Sure, it passes the type checker, but is “computer says yes” enough? Do we need anything else?)

And if we changed the definition of + without changing its type? Then we might get a different set of free theorems, meaning some existing code could now be broken and need additional justification. So, the point is that computation behavior is kind of part of the interface, not just the type, and it can affect code. The discussion on Reddit contains more detail, but I want to highlight one thought here.

Have you read any math proofs recently? Ever seen the phrase “it is obvious that ...” and not entirely agreed with the statement? (I hope it’s not just me.) Typically, the author is moving from one proposition to another by use of various standard or free theorems, like the simple properties of + above. But typically for beginners, some of these steps need to be pointed out explicitly, and are steps that they need as part and parcel of their understanding of the proof.

Note, too, that mathematicians sometimes highlight a few of the potentially mechanical steps because they are central to the (human) understanding of the proof. So, they don’t show the smallest proof possible, but instead, according to their audience, will flag the key conceptual steps that make the proof “work.” That is, they can vary the presentation and sometimes want to draw out the steps that are important for the overall understanding. Let’s call these the “a-ha steps.”

To take this idea one step further, the explanation of the proof can depend on who is reading it. Different people require different levels of detail and explanation. (There have been a few research papers that look at these ideas, under titles like “informal mathematics” or “mathematical vernacular.” Contact the author for more details if you are interested.)

Does this apply to code as well? I think so, and it’s maybe something we should be more conscious of. For example, I’m happy with fairly complex combinations of higher order functions and overloading, but it might be too daunting and non-obvious for a relative beginner. I want to keep my code, but also want the beginner to be able to follow it without having to rewrite the code in simpler terms.

Can we accommodate both positions? And the various positions in-between? Do we have to have a single version of the code for everyone? Must all programmers have to reach the same level of understanding? I suggest not; it should be possible to map from my code (or even sparser code!) to various levels of explanation suitable for people of different levels of experience and ability. Already we are moving away from the idea of a program as a piece of text in a file towards something richer, like a tree in an IDE that supports meaningful operations like syntax-directed editing or refactoring. Can we go even further and have semi-formal kinds of “programming vernacular”? I think so.

Briefly returning to the Reddit discussion, my point is that sometimes we do need to flag up the “a-ha steps” in code, such as how the basic properties of + are used in take, and so make it an explicit part of the module that provides +. This would reduce some of the potential fragility and maybe help comprehension of the code.

Sigma & Dependent Tuples

Here’s another technical point I want to introduce. Well, you’ve seen it implicitly via the definition of the Vect type, but I want to look at it in isolation because it is both important and interesting. We’ll see the concepts used in some of the record-like structures soon.

Tuples are an ordered sequence of values, like (1, "foo"). Idris provides a baked-in form of 2-tuple (pairs) and provides bigger tuples by a bit of syntactic sugar. But, we can define our own version like this:

| data Pair : Type -> Type -> Type where
| pair : A -> B -> Pair A B

The example (1, "foo") can be rewritten as pair 1 "foo". Now, the key detail is that the values in the fields, and the types of their values, are independent of each other. We can combine any two things! We can even combine pairs of types, e.g., pair Nat Bool is valid and means just what it says: a pair of types. (Remember another key detail of some type theories, including Idris’, is that types are first-class citizens too and so can be manipulated like conventional data. Contrast this to most mainstream languages, where the world of values and the world of types are entirely separate.)

What happens if we add some dependency? The Sigma A B type below is like the Pair type, but now, the type of the second element depends on the value of the first element. This is signified by the second value having type B x where x is the first value.

The curly braces indicate implicit arguments, ones that are normally inferred from the context. (This exact type is not in the standard library though its functionality is present through the Prelude’s Exists type for reasons I won’t go into here.)

| data
| Sigma : (A:Type) -> (B:A -> Type) -> Type
| where
| sigma : {A : Type}->{B:A->Type}->(x:A)->(y:B x)->Sigma A B

So, can we write sigma O True as a (dependent) pair of a Nat and a Bool? Er, no. You’ll be told that Idris “Can’t unify Bool with B O.” The implicit parameters mechanism is trying to find a value for the implicit B value, and got stuck because there’s no obvious B such that B O is equal to Bool.

What about the simplest one, that of a function that returns the Bool type whatever its input, i.e., \_ => Bool? That would work, but it’s only one of the infinite number of functions that return Bool from input O, and it might not be the one appropriate for where the sigma value might be used, hence the mechanism holds back from this.

Typically, complex values like sigma pairs are used in a particular context, and the context provides sufficient information to solve the unknowns. For example, the following type checks without any other intervention (because the declared type of foo is used to inform the checking of its definition).

| foo : Sigma Nat (\_ => Bool)
| foo = sigma O True

Alternatively, you can manually supply one of the unknowns, like this: sigma {B = \x => Bool} O True. We do sometimes need to add such hints. How do we get values out of a Sigma value? By pattern matching, of course. There are two standard accessor functions, traditionally called pi1 and pi2 for projection of the first (resp. second) field.

| pi1 : {A : Type} -> {B : A -> Type} -> Sigma A B -> A
| pi1 (sigma a _) = a
| pi2 : {A:Type}->{B:A->Type} -> (p:Sigma A B)->B (pi1 p)
| pi2 (sigma _ b) = b

The interesting case is pi2, where the result type B (pi1 p) must use pi1 to get the first value so it can compute the actual type from B.

Using it with our foo example value above, it means the result type is (\_ => Bool) (pi1 foo) which reduces to Bool.

Let’s try a more complex result type now. Since we can put arbitrary values in the types, we can run arbitrary code there. Our next example selects which type to return by testing its input. Values t2 and t3 are declared to have the same type. However, their type uses function b_or_c which indicates the type Bool when given a O value, else Char. In this way, we can wrap up essentially different kinds of data under the same type, and unpack them in a consistent way too.

| b_or_c : Nat -> Type
| b_or_c = \n => if n == O then Bool else Char
| t2 : Sigma Nat b_or_c
| t2 = sigma O True
| t3 : Sigma Nat b_or_c
| t3 = sigma (S O) 'a'

To demonstrate that these values are in the same type, let’s put them together in a list.

| t4 : List (Sigma Nat b_or_c)
| t4 = [t2,t3]

We can even do map pi1 t4 and get back [O, S O]. What about map pi2 t4? Can we get the list of second values? No, because that would mean trying to build the list [True, 'a'] which isn’t allowed in this exact form. The type system requires the elements to be a predictable type so it can treat them all consistently and not have to do additional run-time checks etc etc. This means we can’t use the OOP style of “heterogeneous list” (i.e., posh for “different things”). But all is not lost! Let’s do something interesting: define a slightly more powerful version of pi2 that wraps up the second element with its type in a new Sigma value.

| pi2_t : {A : Type} -> {B : A -> Type} -> Sigma A B -> Sigma Type (\t => t)
| pi2_t {A} {B} p = sigma (B $ pi1 p) (pi2 p)

And now we can run map pi2_t t4 to get [sigma Bool True, sigma Char 'a'], which is a “homogeneous list” (same things) of type List (Sigma Type (\ t => t)). Notice that we’re storing the type as a piece of data: types are first-class citizens too, remember! So the above result is entirely safe and we can use it for other things, e.g., select out the items that have a Bool type and do something Bool-y to them. To underline the point: we couldn’t do direct extraction of the second elements because it means a list of mixed types, which isn’t allowed. Instead, we can re-wrap the second elements with their type, and now manipulate this safely with similar values.

Now, you may balk at having to wrap up a value with its type and pass the two around, but isn’t this pretty much what most OO implementations are doing? They aren’t passing raw data, but data plus some structure or information like a table of functions or some kind of prototype or dictionary? It’s a big topic, but see if you can ponder the following without blowing your mind too much: with a very powerful type system, are we starting to come full circle and get back to the flexibility we thought we lost when we moved to static types? Paradise recaptured? Maybe in a better form?

Considering the Split

Back to the code. I’m using a more recent version of Idris now, specifically, 0.9.8. You may want to update.

First up is the operation that splits long words into fragments. What are the details we perceive as risky? What do we want to be sure about? As I suggested above, it’s not always feasible to cover all the bases and so it’s worth thinking about priorities.

Since this kata is about line packing to a certain width, then sizes seem to be a key aspect. For sake of argument, I’d like to be sure that a word of size M is split into as many chunks of size N as possible, followed by a piece of size less than N‚Äîwhich could even be zero if M is a multiple of N.

In the previous code, we were basically crossing our fingers on a few details that the pieces ended up the right size with the left-over bits last. We could have written a few tests to explore the code’s behavior and gained some confidence, or written something in the comments about what callers of the code should be able to expect, but that’s not the same as certainty.

To start, let’s think in data terms about what output result we want from splitting. We want a list of equally-sized chunks, and the left-overs. We also want to be sure that the left-over chunk is too small to be a proper chunk. So, we can try the following:

The type SplitBy a n type represents the splitting of some thing into chunks of size n. The other parameter a is a placeholder for the element type of the input collection (list, vector, ...) that is to be split.

| data
| SplitBy : Type -> Nat -> Type
| where
| Split : (vs : List (Vect a n))
| -> (m : Nat) -> (LT_ m n)
| -> (v : Vect a m)
| -> SplitBy a n

The single constructor Split requires (i) a list vs of vectors of size n to hold the proper chunks; (ii) then a number m and some evidence that m < n; then (iii) a vector v that is of size m, which holds the left-overs.

These various details mean we can’t do things like make chunks of random size, or have the leftovers too big. It also forbids splitting into chunks of size zero (because no Nat value is less than zero!), which I flagged a while back as being a potential pitfall‚Äîlike is the result infinite?

With this, we can say what we expect the type for split_up to be: taking a size and a list of some size, and producing a splitting by that size. There’s one restriction though: it doesn’t make sense to split into size zero chunks, so let’s use the type to avoid that case. Hence, we propose the following: (BTW, it’s not ideal having the (S n) in the result type, and there’s probably a neater way to do it. Suggestions welcome!)

split_up : (n:Nat) -> (Vect a m) -> SplitBy a (S n)

If we can produce a definition of split_up with this type, then it will automatically obey some of the properties we require of the output. Notice that instead of working with externally stated properties (as propositions or, in some sense, tests as well), we’re starting to move that information into the data our code is operating on. This is an important point about the benefits of richer types: instead of separating code and tests or code and properties, we’re working with something a lot more uniform and meaningful. Also, we now have more opportunity to exploit that information to help us program. I think this is real progress!

The SplitBy type could be extended to capture other invariants and properties, such as the left-over vector really being the last m elements of the original input, or that the number of size n chunks is correct or that the chunks contain appropriately correct text. However, some of these properties are straying into the responsibility of the various functions that will operate on this type. For example, we can define splat to unpack the splitting, and state a property about how split_up and splat are related. Other properties might be useful too, particularly as lemmas in a bigger proof, e.g., splat (Split [] _ _ y) = toList y to check what happens for a short list. Also useful is add_elm which puts another chunk in the list.

| splat : SplitBy a n -> List a
| splat (Split xs _ _ y) = concat (map toList xs) ++ toList y
| split_splat : (n:Nat) -> (l:List a) -> splat (split_up n (fromList l)) = l
| split_splat = ?hard_exercise_left_for_the_reader
| add_elm : Vect a n -> SplitBy a n -> SplitBy a n
| add_elm v (Split vs a b c) = Split (v::vs) a b c

Doing the Splits

The general algorithm should not surprise you. The key decision point is whether the size of elements remaining is less than the chunk size or not. Intuitively, if it is smaller then we return a SplitBy value with no big chunks and with the input as the left-overs. Otherwise, we can use take to slice off a chunk, then we add this chunk (using add_elm) to the result of splitting up the rest of the input after the first chunk has been removed with drop.

Now, how do we encode this understanding in the programming language? Here’s a naive version of the split_up code. Most of it seems straightforward so I just write it in directly, but I can’t be bothered to work out the proof term so I leave a “hole” called ?case1_pf to be filled in later.

The comparison is done with compare m (S n), essentially the spaceship operator <=> found in Ruby, and it returns LT if the first argument is less than the second, else EQ or GT as appropriate.

The syntax with (thing) is important, but for now just regard it as allowing us to do more pattern matching on the result of (thing), in this case to pattern match and branch on the comparison result, similar to case in Ruby. (Also don’t forget about that annoying detail of needing (S n) instead of n to avoid the split-by-zero difficulties. It is clearly a smell!)

| simple_split_up : (n:Nat) -> (Vect a m) -> SplitBy a (S n)
| simple_split_up n {m} xs with (compare m (S n))
| | LT = Split [] m ?case1_pf xs
| | _ = add_elm (take (S n) xs) $ split_up n (drop (S n) xs)

This won’t get past the type checker, basically because there are a few implicit details in the second case that can’t be inferred immediately from the code. The main problem is in the second case, that it Can't unify Vect a m with Vect a (S n + o), or, that there’s no evidence around that m and S n + O are equal sizes. Let’s see what is available to the checker in the second clause by stubbing out pieces of it with holes.

| simple_split_up : (n:Nat) -> (Vect a m) -> SplitBy a (S n)
| simple_split_up n {m} xs with (compare m (S n))
| | LT = Split [] m ?case1_pf xs
| | _ = add_elm ?case2_arg1 ?case2_arg2

When we enter proof mode with the command :p case2_arg1 and do intros to see what is available to help, we see this:

| ---------- Assumptions: ----------
| warg : Ordering
| a : Type
| m : Nat
| n : Nat
| xs : Vect a m
| ---------- Goal: ----------
| { hole 5 }:
| Vect a (S n)

From this, we need to build a value of type Vect a (S n) from the value xs : Vect a m but there’s nothing here at all that help us to relate m and S n. The compare test has sent us to the case where m is greater than or equal to S n. But there’s no evidence here that confirms this or allows us to exploit that information easily, and we need this to help build the relevant results, e.g., we need to know this in order to use take. In effect, even though we’re in the appropriate branch, we are not really much the wiser about why we are there!

These are Not the Patterns You are Looking For

So, we need more information. I mentioned before the idea of first writing the program you want to write, then write another program that runs the good program. We can take this approach with patterns too, so let’s think about the patterns we’d really like to work with. Remember that pattern-matching is about classifying and decomposing data, and what we’re going to do is extend the collection of patterns we can work with.

This idea has been around in various forms for quite a few years, under the general name of views. You can create views in databases to control or to simplify access to data. Professor Philip Wadler (he of monads fame) has developed similar ideas in the context of functional programming. Dr. Conor McBride has developed these ideas into a powerful framework for programming with dependent types. What you see next is a simple (and brief) example of this.

In our context, a view has two components: a data type that encodes the various patterns, and a “covering function” that converts our target data into a value in the view type.

For the split_up function, we’re interested in decomposing the input vector into two cases. One case is for the “too small” case, and we’d like to get a proof of it being too small. The other case is for “big enough,” where we want a different proof that proves that fact. But, to simplify the coding, we want the “proof” in a slightly different form. Saying a >= b is equivalent to saying there is a number c such that a = b + c. In constructive style, we “prove” a >= b by supplying such a number c and a proof that it’s the value that solves the equation. Hence, using the machinery of dependent types and inductive families, we define this:

| data CompareLT_ : Nat -> Nat -> Type where
| LessCase : (LT_ a b) -> CompareLT_ a b
| GteCase : (c:Nat) -> (b + c = a) -> CompareLT_ a b

Remember: it encodes the end result of a comparison. Next, we define the covering function, which converts our input into the comparison result. I’m not going to explain everything here, but roughly: the first case says any value x is greater or equal to O and the difference is x; the second says O is less than 1 + anything, and the proof is obvious; and the third says to decide the result for (1 + x) compared to (1 + y), then get the result for comparing x and y and modify the results accordingly. (That is, the result for compareLT_ 6 4 will use the result for compareLT_ 2 0.)

| compareLT_ : (a,b : Nat) -> CompareLT_ a b
| compareLT_ x O = GteCase x refl
| compareLT_ O (S y) = LessCase ltZero
| compareLT_ (S x) (S y) with (compareLT_ x y)
| | LessCase pf
| = LessCase (ltSucc pf)
| | GteCase c h
| = GteCase c (replace {P = \z => S (y + c) = S z} h refl)

With this in place, we can now write a fairly straightforward definition of split_up. I’m using proof mode to construct the arguments for the add_elm function, and the proof steps are shown below. (Remember that the proof process builds a term that then gets slotted in, so we could replace the proofs by hard code if we want. If you type the name of a completed proof in Idris, you’ll see the underlying term.) The proofs build pretty much the code you’d expect, apart from a few fiddly details with implicit values and the need to tease out details from the constraints, for which the proof mode gives us a lot of support.

| split_up : (n:Nat) -> (Vect a m) -> SplitBy a (S n)
| split_up n {m} xs with (compareLT_ m (S n))
| | LessCase pf = Split [] m pf xs
| | GteCase d hyp = add_elm ?gte_arg1 ?gte_arg2
| Main.gte_arg1 = proof {
| intros;
| let take_call = Main.take {o=d} (S n);
| refine take_call;
| compute;
| rewrite sym hyp;
| exact xs;
| }
| Main.gte_arg2 = proof {
| intros;
| let rec_call = \v => split_up {a=a} n (drop {o=d} (S n) v) ;
| refine rec_call;
| compute;
| rewrite sym hyp;
| exact xs;
| }

The above example could be done more directly, where instead of the view giving us proofs that we use in take etc., it could instead give us the decomposed value directly. That is, a different view could allow us to analyze a vector (with respect to a target length n) as either a short vector OR as a chunk of size n paired with the remainder of a given size). This might be a good exercise to try.

To sum up, we now have a word-splitting function that we can be sure produces correctly sized output. It’s a total function, so we can be sure all possible cases are covered and that the code doesn’t crash or loop. That is, assuming the checker in Idris is correct! (Correctness of the checker is a very important issue, but I’ve not got time to cover it now.)

The Rest of the Code

Very brief details now. The input to the line-packing needs to be a list of fragments that do not exceed the line size. We can wrap up each fragment in a new type, storing each vector with a proof that its size is less than or equal to the limit. I’m cheating a bit here, and reusing the compareLT_ code from earlier, so the code requires the length to be strictly less than the limit + 1.

| data MaxVect : (a:Type) -> (n:Nat) -> Type where
| MVect : (i:Nat) -> Vect a i -> LT_ i (S n) -> MaxVect a n

Next, we unpack the split-up long words into a sequence of such units, each of them obviously within the width limit. (Annoyingly, the (S n) here comes from the attempt to avoid the split-by-zero case...)

unpack_split : SplitBy a (S n) -> List (MaxVect a (S n))

And then, we can start packing these units together, inputting a list of fragments and then merging adjacent ones (with the separator element) if the result doesn’t break the line limit. Notice how the input and output types are basically the same, though the contents may vary.

| pack : (n:Nat)
| -> (separator : a)
| -> List (MaxVect a n)
| -> List (MaxVect a n)

And then we glue the various stages together to get the complete program! Phew.

The full version of the code will appear on GitHub after a few days, after a bit more tidying up, as this gist.

Finishing Off

What else can be done? We might want a few concrete tests, though more as a sanity check rather than anything like TDD because we’ve already done a lot of the hard work via the type system.

We could start writing down and investigating useful properties, like the packing process not permuting or changing the content being packed. We could even start trying to prove them. Another possibility is to first use a QuickCheck-style tool to try properties on a big set of examples to see whether obvious counter-examples exist. It’s up to us, and how much confidence we require in any part of the code.

Also, I expect there are quite a few ways this code could be improved and simplified, so don’t take the above code as the last word!

What do you think of this kind of program?

Some bits look strange because they are quite different, even for reasonably experienced functional programmers, and programming this way does require developing a few new skills. In return, we are able to be more exact about how certain parts of the program work, to be more thorough on details that are often left implicit, and obtain high levels of confidence as well. Plus, you can get these inside a uniform language that has plenty of scope for powerful abstractions, and where serious proof becomes easier to deal with. If such details are important for a certain project, then this tradeoff might be one that works for you.

So Much Left to Cover!

This series of articles has been a tour of some advanced ideas in functional programming and beyond. I hope you’ve found it interesting.

We started from the view of “functional programming” as a style of programming that really takes data structures seriously, and thus a style where we seek to identify relevant forms of data and solve problems by transforming data from one kind of data to another.

I’ve shown some examples where taking this idea as a key design principle has led to pretty straightforward and flexible code.

We also touched briefly on the idea that many aspects of your programs, such as navigation schemes for web apps or complex interactions with users, can be brought to the fore as data structures rather than left as implicit details buried under other stuff, and making them more explicit as data might help to simplify those parts of your code.

Throughout this, a powerful type system was used both as a tool for structuring and organizing code, and as a safety net. We saw ways in which the type information can even be exploited by advanced editors to guide the programming process. I suggest that using types well is a key part of the data-first style of functional programming. The relationship with testing was also considered.

Finally, we had a look at one possible future direction for this style of programming, toward languages that combine very powerful ideas about types with strong support for reasoning. It was quite a different world, but one with many advantages.

There are quite a few more related topics to explore, such as effects (refining some of the ideas about monads), and functional reactive programming. If you’re reading this and know something about these topics, do consider writing an article or three for this magazine (that’s my suggestion, not the editor’s!).

And if you want to know more about advanced functional programming or type theory? I’ve mentioned various books in earlier articles, as well as looking at the web pages for Idris or Agda and the various resources they mention. Joining the mailing lists is also useful, and many of us on the lists are more than happy to help with queries.

Also worth a mention is a very new book on Homotopy Type Theory. This was released only a few days ago (June 20th), but chances are you might have seen some mention of it already on Twitter.

It’s notable for quite a few reasons, despite the dry title. First, it explores the promising links between the foundations of type theory and some key areas of math. Secondly, it includes contributions from a very high caliber of people, a core group of about 20, with various contributions from many other experts. Thirdly, this group managed to put a substantial book together in under a year, and over GitHub no less. Fourth, despite the subject matter, from what I’ve seen it seems extremely well written, engaging, and accessible to a wide range of people (just try it!)

And you can download it for free! There’s even a version formatted for e-book readers! Plus the whole book’s repository is on GitHub so you can fork it and submit pull requests. It isn’t your normal academic book! (As soon as I finish writing this article, I’m going to dive back into the book. You’re lucky I managed to finish this article...)

Anyway, that’s it from me. Thanks for reading, you’ve been a great audience, and I hope you found something interesting in this series!

I’m off now, to read some more about Homotopy Type Theory.

And then, I have a book to write.

Dr Paul Callaghan first learnt about type theory in 1996, and was immediately fascinated. It filled in many of the unsatisfactory gaps in conventional functional programming, and helped him understand why some programs in Haskell felt wrong and incomplete. Paul was fortunate to do research work with some very talented people from 1997 to 2007, during which time he implemented a niche proof assistant called Plastic and experimented with various ideas like DSLs, Mathematical Vernacular, and Coercive Subtyping. Other bits of his bio can be seen on earlier articles. Paul currently works on a variety of bespoke rails apps at TranscendIt, and thanks TranscendIt for its continued flexibility with his writing schedule! Paul also flies big traction kites and can often be seen being dragged around inelegantly on the beaches of North-east England, much to the amusement of his kids. He blogs at free-variable.org and tweets as @paulcc_two.

Send the author your feedback or discuss the article in the magazine forum.

Living with Lambdas

Functional Programming in C++

by Alfons Haffmans

You can work in the functional programming paradigm in C++. And you may be surprised at how complete C++’s support for functional programming is.

Functional programming and C++. This combination will strike an equal mixture of disgust and terror in some of you. Others may be intrigued but daunted by the prospect.

Yet C++ has always been a multi-paradigm language. And while previous attempts to add practical functional programming features required significant effort, recent additions to the C++ standard, like lambdas, have improved the situation. This paper explores the out-of-box support for functional programming provided by the new standard. We’ll look at techniques typically found in introductory functional programming textbooks. This article assumes familiarity with C++, but not necessarily with basic functional programming.

The source code is available in github and is compiled using gcc 4.8 installed on Mac OSX using MacPorts.

Object-Oriented and Functional Programming Style

The heart of object-oriented programming is the encapsulation of data and methods in a coherent class or object. Each class or object represents an entity in the real world. Each object is responsible for the management of its state and as long as it fulfills the contract implied by its interface the implementation is of no concern to the caller. Objects interact by sending each other messages through method calls that change the internal state of the receiving object. Classes can be combined through inheritance or composition to form more complex entities.

The for-loop is a typical construct used in C++ classes. The for-loop processes elements in a container. These elements can be object instances or pointers to object instances. Usually the for-loop uses iterators to point to the next element to process in its body. The body of the for-loop typically has statements that affect the state of the element referenced by the iterator. When the for-loop reaches the end of the container all elements have been processed and some or all of them have been modified in some way. Any reference to the list acquired before the for-loop was executed will now reference the changed list. The same thing goes for references to elements in the list. So the execution of the for-loop may cause side-effects in other parts of the program, either by design or by accident. The type of programming that emphasizes the use of mutable data and statements is called an imperative programming style. It is hard to prove by simple statement inspection alone if an imperative program is correct, because its state may be affected by changes away from the statement being reviewed.

In contrast, functional programming stresses the construction of computations or functions acting on immutable values. Data and operations on the data are not co-mingled. Immutable data acts like a value like 1. You can hold a reference to 1, but 1 itself is immutable. You can add 2 to the reference but the reference itself still points to 1. This referential transparency through the use of pure functions and immutable data lies at the heart of functional programming.

Functions are first-class objects in a functional language. You can reference a function like you would any other data. Functions can have functions as arguments or return functions. Functions that take functions as arguments or that return functions are called higher order functions. You can use higher order functions to combine simpler functions into more complex ones. They play an important role in functional programming. for-loops are replaced by recursion for list processing.

Because functions play such an important role we need a formal way to represent them. This article uses Haskell’s notation for function signatures. A binary function f with arguments of type a and b and a return value of type c is represented:

The representation of function implementations uses a slightly different notation: the return type follows the double colon :: after the argument list. Here’s the type signature of the identity function:

Here are two implementations of id:

id (int x) ::int = x

In a function definition a -> b, the arrow -> can be looked at as a type that takes two other types a and b to be fully defined. Types that are parameterized by other types, like the arrow operator -> are referred to as type constructors. In general, M a represents a type constructor M that takes a single type variable a, and M a corresponds to the C++ class template template < typename a > struct M..... The arrow operator corresponds to the function wrapper std :: function < a(b) >. Another frequently used type constructor is [ a ], which creates a list of elements of type a. [a] corresponds to the stl containers std :: list < a > or std :: forward_list < a >.

Lambda Expressions and Closures

Lambda expressions allow you to create functions on the fly. The expression in the body of the lambda can reference variables that are not specified in the argument list of the lambda expression. Those variables are called free variables. Free variables are assigned the value found in the environment (i.e., the scope) in which the lambda expression is defined. This capture of the enclosing environment by the lambda expression is called a closure.

The (slightly abbreviated) C++ syntax for the lambda expression is:

The capture specifier [...] specifies how the free variables are captured. If it’s empty [], the body of the lambda can’t reference any variables outside its scope. The [=] specifier captures free variables by value, whereas the [&] captures them by reference. The ( params ) is the parameter list and -> rettype is an optional return type specifier. Lambdas can be bound to variables using std :: function or auto.

| int x = 0;
| int y = 42;
| auto func = [x, &y] () { std :: cout << "Hello world from lambda
| : " << x << "," << y << std :: endl; };
| auto inc = [&y] () { y++; };
| auto inc_alt = [y] () mutable { y++; };
| auto inc_alt_alt = [&] () { y++; x++; };
| func(); //prints: Hello world from lambda : 0,42
| y = 900;
| func(); //prints: Hello world from lambda : 0,900
| inc();
| func(); //prints : Hello world from lambda : 0,901
| inc_alt();
| func(); //prints: Hello world from lambda : 0,901
| inc_alt_alt();
| func(); //prints: Hello world from lambda : 0,902
| std :: cout << " x :" << x << "; y :" << y << std :: endl;
| // x :1; y :902

Listing 1: various ways lambdas capture the environment

Listing 1 illustrates the use of the capture specifier. The lambda func has no arguments and prints the value of the two free variables x and y to stdout. x and y are initialized to 0 and 42 respectively, preceding the lambda definition. The capture specifier of func is [x,&y] so x is captured by value and y by reference. The next three lambdas increment the free variables x and y. The lambda inc captures y by reference. inc alt, on the other hand, captures y by value. The keyword mutable allows the lambda expression to change y. inc alt alt captures the complete environment by reference, and increments both x and y. Then func is called each time y is changed. The values of x and y printed by func are shown in the comment. Since y is captured by reference is can be changed through side effects. On the other hand x is captured once and remains the same.

| [...] // as opposed to [=] or [] or [l] std :: function<int (int)> factorial =
| [&factorial] (int x) -> int {
| std :: cout << x << ",";
| if (x == 0) return 1;
| return x * factorial(x-1);
| };
| auto res = factorial(10);
| std :: cout << std :: endl;
| std :: cout << "res : " << res << std :: endl;
| //prints : 10,9,8,7,6,5,4,3,2,1,0,
| // res : 3628800

Listing 2: implementation of factorial using lambda recursion

Listing 2 shows a recursive implementation of the factorial function n!. Each invocation of the lambda prints the value of the argument x. The return type is specified using the optional return specifier. Notice that the lambda itself needs to be captured by reference.

Partial Function Application

A partially applied function is created when a function is called with fewer arguments than its argument list requires. In that case, a lambda is returned with the remainder of the arguments. In C++ partial function application is supported by std :: bind and std :: placeholders :: ... Both are defined in the header < functional >. The placeholders are in the namespace std :: placeholders and are named _1, _2, etc.

std :: bind takes a callable object or a function pointer as its first argument. Subsequent arguments are either values, or placeholders provided by std :: placeholders. std :: bind returns a function object. The relative position of the values and placeholders corresponds to the position of the argument in the argument list of the function f to which they’re bound. A placeholder corresponds to an argument of the callable returned by std :: bind. The number of arguments is equal to the number of distinct placeholders.

| auto repeat = [](int n, double y, std :: function<double(double)
| > f) {
| while (n-- > 0) {
| y = f(y);
| }
| return y;
| };
| auto rpl = std :: bind (repeat,
| std :: placeholders :: _1,
| std :: placeholders :: _1,
| std :: placeholders :: _2);
| std :: function<double (double)> l1 = [](double x) { return
| 2*x-0.906;};
| auto val = rpl(9, l1);
| std :: cout << " result : " << val << std :: endl;
| // print 4145.03

Listing 3: std :: bind example

Listing 3 illustrates the use of std :: bind and std :: placeholders. It’s used to create a function that calls another function repeatedly with the result of the previous function call. Lambda repeat is a higher-order function that repeatedly calls its third argument. This function is initially called with the value of the second argument. The number of repetitions is given by the first argument. std :: bind is used to create a function that uses the number of repetitions as the initial value. The callable object rpl returned by std :: bind uses the number of repeats as the initial value because the first and second argument of repeat are bound to the same placeholder. rpl(l1, 9) calls lambda l1 nine times, with 9 as the initial value. The result is printed to stdout, and its value is shown in the comment.

Currying

Currying (named after the mathematician Haskell B. Curry) is a technique that turns any function into a function of one variable. Currying is related to but is more powerful than partial function application. The curried version of a function is a higher-order function that returns a partially applied version of the original function.

The function signature of a function designed to curry binary functions f(x,y) is:

| curry2 :: ((a,b) -> c) -> (a -> b -> c)
| f :: (a,b) -> c => (curry2 f) :: a -> b -> c

curry2 takes a binary function and returns a unary function. This unary function returns another unary function when it is called with an argument of type a. This function is a partially applied version of the uncurried function f, where the argument a is provided. When you call this function with an argument of type b you obtain the value returned by uncurried function f. Here’s an example where plus is being curried:

| plus :: (int x,int y) :: int = x+y => cplus(int x) :: (int -> int)
| -> (int y) :: int -> x+y
| plus(5, 6) = 11 <=> (curry2 plus)(5)(6) = 11

(curry2 plus) is the curried version of plus. The return types have been shown explicitly to highlight the fact that functions are returned. curry2 plus)(5) returns a lambda that represents the plus function partially applied to 5. This is then called with 6 as the argument with an unsurprising 11 as the result. A simple implementation of curry2 to curry binary functions in C++ is shown in listing 4:

| template <typename R, typename T, typename U>
| std :: function<std :: function<R (U)> (T)> curry(std :: function<R (T
| ,U)> op)
| {
| return [=] (T x) { return [=] (U y) {return op(x, y);};};
| }
| auto l = curry<int,int, int> ([](int x, int y) { return (5 + x
| ) ∗ y;});
| std :: cout << l(1)(1) << std :: endl; //prints 6

Listing 4: curry for binary operators

Currying and partial function application simplify the design of higher order functions since we only have to consider unary functions. In fact currying plays an important role in functional programming.

Neither the C++ language nor its standard library provide facilities to curry functions. In fact, in C++ functions are not written in curried form. Compare this to Haskell where functions are curried by default. The programmer needs to either use a third-party library or roll her own implementation. Writing a curry operator has become a lot easier now that lambdas are supported.

Map, zipWith, and Zip

map applies a function f of type a -> b to each element of a list [a] and returns a new list [b].

The std :: for_each function appears to fill the the bill. It takes two iterators and a unary callable object as input. The callable is called with every element in the range delimited by the iterators, and its final state is returned. std :: for_each is clearly an imperative implementation of a for-loop.

A better choice is the std :: transform function. This function has two forms. The first one takes a unary callable object as input and applies it to the elements of one range and returns another.

| template < typename input container iterator,
| typename output container iterator,
| typename unary operation >
| output container iterator transform
| (input container iterator begin1,
| input container iterator end1,
| output container iterator destination1,
| unary operation unaryop);

In the second it takes a binary callable function, applies it to two input ranges, and returns the resulting range:

| template < typename input container iterator1,
| typename input container iterator2,
| typename output container iterator,
| typename binary operation >
| output container iterator transform
| (input container iterator1 begin1,
| input container iterator1 end1,
| input container iterator2 begin2,
| output container iterator destination1,
| binary operation binaryop);

Listing 5 shows a possible implementation of the map function for a std :: forward_list.

| template<typename A, typename F>
| auto map (F f, const std :: forward_list<A>& L) −> std ::
| forward_list<decltype(f(A()))>
| {
| std :: forward list<decltype(f(A()))> H;
| std :: transform(L.begin(), L.end(), std ::
| front inserter(H), f);
| H.reverse ();
| return H;
| }

Listing 5: map for std :: forward_list

Notice that map has two type parameters. The first specifies the type of the element in the input container L. The second type parameter specifies every generic callable. std :: function could have been used to provide a more type-safe interface. However, that would not allow us to use inline lambda functions. The type of each lambda is unique and therefore would not be converted to std :: function. The type of element in the result list is determined using decltype on the return type of the callable f.

| [...]
| std :: function< std :: function <int(int)>(int)> cplus = [] (int
| x){
| return [=] ( int y) {
| return 4 ∗ x + y;
| };
| };
| auto l = std :: bind([](std :: function<int(int)>
| f){return f(2);},
| std :: bind(cplus , std :: placeholders :: 1));
| map(show, map(l , L));
| //prints 6,270,358,94,182,6,14,398,−358,

Listing 6: using std :: bind to combine functions

In listing 6 std :: bind combines two functions and the result is then mapped over the list. The inner bind takes the curried plus function cplus as the first argument and puts a placeholder as the second argument. The lambda returned by the inner bind is then used as an input to the outer lambda. The first argument of the outer bind is a lambda that has a function as input. In the body of the lambda this function is called with 2. The placeholder is bound to the first argument of cplus and 2 is used as the value for the second argument. So in effect the function f(x) = 4*x+2 is mapped over the list. The result is printed to std :: cout. 94 the result of 4*23+2, 182 the result of 4*45+2, etc. This shows how function combination can be used to limit the number of iterations and list copies.

The second flavor of std :: transform applies a function to the elements of two lists to produce a third. This corresponds to zipWith:

zip :: [a] -> [b] -> [(a,b)]

The first argument of zipWith is a curried function, with input parameters of type a and b respectively and return type c. This function is applied to a list of elements of type a and b respectively. The result is a list of type c. A closely related and widely used function is zip, which takes two lists and returns a list of pairs.

| template<typename A, typename B, typename F>[caption=zipWith and
| zip implemented with std :: transform, label=zipWith]
| auto zipWith (F f , const std :: forward list<A>& L, const std ::
| forward list<B>& R) −> std :: forward list<decltype(f(A() ,B()))
| >
| {
| std :: forward list<decltype(f(A() ,B()))> H;
| std :: transform(L.begin(), L.end(), R.begin(), std ::
| front inserter(H), f);
| H.reverse();
| return H;
| }
| template<typename A, typename B>
| std :: forward list<std :: tuple<A,B>> zip (const std :: forward list<
| A>&L, const std :: forward list<B>&M)
| {
| return zipWith ([] (const A& a, const B& b) {return std ::
| make tuple(a,b);}, L, M);
| }

This listing shows the implementation of zipWith and zip for a std :: forward_list using std :: transform. The type of the return list is derived by calling decltype on the function f, which is called with an instance of A and B.

| [...]
| std :: forward list<int> L = {1,67,89,23,45,1,3,99,−90};
| std :: forward list<char> R = {'a','b','l','u','t','v',
| 'r','6','h'};
| auto H2 = zip (L, R);
| map([] (std :: tuple<int,char> v) { std :: cout << v << ",";
| return v;},H2);
| //prints : (1,a),(67,b),(89,l),(23,u),(45,t),(1,v),(3,r),
| (99,6),(−90,h) ,

Listing 7: zipping two lists

Listing 7 illustrates the use of zip on two lists.

| template<typename A, typename B, typename F>
| auto zipWith (F f) {
| return [=](const std :: forward list<A>& L) {
| return [=](const std :: forward list<B>& R) −> std ::
| forward list<decltype(f(A() ,B()))> {
| std :: forward list<decltype(f(A() ,B()))> H;
| std :: transform(L.begin(), L.end(), R.begin(), std ::
| front inserter(H), f);
| H.reverse();
| return H;
| };
| };
| };
| [....]
| auto op = [] (int x, char z) {
| return std :: make tuple(x,z);
| };
| auto res = zipWith<int ,char>(op)(L)(R);
| map([] (std :: tuple<int,char> v) { std :: cout << v << ",";
| return v;}, res);
| //prints : (1,a),(67,b),(89,l),(23,u),(45,t),(1,v),(3,r)
| ,(99 ,6) ,(−90,h) ,

Listing 8: curried version of zipWith

Listing 8 is closer to zipWith’s curried version shown in the function signature above. The listing shows the same zip operation as the previous one. However, the call to zipWith requires a complete specification of the template types. This increases the line noise somewhat. C++’s type system is not powerful enough to infer the types from type of the arguments to op.

Reduce and the List Monad

The type signature for reduce is:

reduce moves or folds a binary operation over a list and returns a result. The type of the first argument to the binary operation is the same as the type returned by reduce. It’s also the type of the first input variable encountered after operator specification. The first input variable is used to initialize the first argument to the binary operation, when the first element of the list [b] is being processed.

In fact map can be implemented in terms of reduce. In that case, the type a would be the list type, and the initial value would be the empty list. The binary operator would then concatenate the result of a unary operation onto the list. Because map can be implemented using reduce, reduce is more powerful than map.

The stl function that closely matches the type signature for reduce is the std :: accumulate function found in the < numeric > header.

The version we use second takes a binary operator and a couple of list iterators as input.

| template < typename input container iterator,
| typename T typename binary operation >
| T accumulate (input container iterator begin,
| input container iterator end,
| T initial value,
| binary operation binaryop);

The function signature of std :: accumulate tracks that of reduce fairly closely. The main difference is the order of the arguments and the lack of curry.

| std :: forward list<int> L = {1,−6,23,78,45,13};
| auto max = [] (int x, int y) { return (x > y) ? x : y;};
| auto res = std :: accumulate(L.begin(), L.end(), std ::
| numeric limits<int> :: min(), max);
| std :: cout << "maximum : " << res << std :: endl; //prints 78

Listing 9: example of std :: accumulate

Listing 9 shows how we can use std :: accumulate to the maximum value in a list. std :: numericlimits < int > :: min returns the smallest possible integer value and is used to initialize the search. The binary operation is just a lambda wrapped around the compare operator and std :: accumulate returns the expected result.

| auto show = [] (int v) { std :: cout << v << ","; return v;};
| typedef std :: list<int> list t;
| list t L = {1,−6,23,78,45,13};
| auto m = [] (list t L, int y) { L.push back( 2∗y + 1);
| return L;};
| auto res = std :: accumulate(L.begin(), L.end(), list t(), m);
| map(show,res); //prints 3,−11,47,157,91,27,

Listing 10: processing a list using reduce

In listing 10 std :: accumulate is used to process a list by applying a function to each element. Notice that the body of the lambda m does in fact two things: The actual operation we would want to perform (2*y+1 in this case) as well as the concatenation of the result of this operation to the target list.

| [...] typedef std :: forward list<int> list t ;
| list t L = {1,−6,23,78,45,13};
| auto op = [] (int y) {return list t({2∗y+1});};
| auto concat = [] (list t A, list t B) { A.splice after(A.
| before begin () , B) ; return A;};
| auto bind = std :: bind(concat , std :: placeholders :: 1 , std ::
| bind(op, std :: placeholders :: 2));
| auto show = [] (int v) { std :: cout << v << ","; return v;};
| auto res = std :: accumulate(L.begin(), L.end(), list t(),
| bind);
| map(show, res); //prints 27,91,157,47,−11,3,(i.e reverse order
| )

Listing 11: unary operation and reduce

Listing 11 refactors the code in listing 10 by separating the unary operation and the list concatenation. The generalized function signature of the unary operator (the lambda bound to op) is a -> [b]. At first blush this looks like a clunky re-implemention of the map function but in fact it’s more powerful.

| template<typename A, typename F>
| auto mapM (F f , std :: forward list<A> L) −> decltype(f(A()))
| {
| typedef typename decltype(f(A())) :: value type ret t;
| L.reverse ();
| auto concat = [] (std :: forward list<ret t> L, std ::
| forward list<ret t> R) {
| L.splice after(L.before begin(), R);
| return L;
| };
| auto op = std :: bind(concat , std :: placeholders :: 1 , std ::
| bind(f , std :: placeholders :: 2));
| return std :: accumulate(L.begin(), L.end(), std :: forward list<
| ret t>(), op);;
| }

Listing 12: the list monad

Listing 12 shows the implementation of a function called mapM based on the refactoring done in listing 11. Its signature resembles that of map. Just like map, mapM takes a unary function f and a list and returns a list:

mapM :: (a -> [b]) -> [a] -> [b]

However, note that f returns a list of elements, rather than a single value. This makes mapM a lot more powerful.

| [...]
| auto show = [] (std :: tuple<int ,char> v) { std :: cout << v <<
| ","; return v;}; static char digits[] =
| {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'
| , 'i', 'j' };
| typedef std :: forward list<std :: tuple<int , char>> list t;
| auto op = [=] (int y) {return list t ({std :: make tuple(y,
| digits [ abs(y) %10]) }) ; } ;
| map(show, mapM(op, std :: forward_list<int >({1,−6,23,78,45,13}))
| );
| //prints :(1,b),(−6,g),(23,d),(78,i),(45,f),(13,d),
| auto res = map(op, std :: forward list<int >({1,−6,23,78,45,13}));
| std :: cout << std :: endl << "−−−−−−−−−−−" << std :: endl;
| for (auto& el : res) {
| std :: cout << "[";
| map(show, el);
| std :: cout << "], ";
| }
| //prints :[(1,b),], [(−6,g),], [(23,d),], [(78,i),], [(45,f),],
| [(13 ,d) ,]

Listing 13: comparing mapM and map

Listing 13 uses mapM to redo the previous example shown in listing 7.

The main difference is that the function op that is mapped over the list returns a list rather than a single element, like it did in listing 7. In fact we could extend this example by having op return more than one element, or no elements at all. Regardless, mapM would return a list of results.

If you try to do the same thing with map, a list of lists is returned.

In a typical scenario you’d want to apply a number of operations to a list. mapM allows each function to have the same signature. It takes a single element and returns a list of elements. The next application on a list returned by map would (as you can see when the results are printed in the example) require an iteration over the result list. In fact, the resulting list is fundamentally different from the input list. It’s the ability of mapM to join the result lists of the operation into a single list that provides a great deal of power.

In fact the type signature of mapM is that of the monad implementation for lists. The use of monads and other types provide a powerful extension of the functional approach. I hope to discuss the support for those in a follow-up article.

Conclusions

Is functional programming possible for the mainstream programmer in C++? In this article I’ve discussed basic functional techniques, like lambda expressions and closures, partial function application, currying, map, and reduce. In addition, I’ve introduced a more powerful, monadic form of the map function. I’ve shown that the new additions, notably lambdas and closures, to the standard have made the use of these functional techniques a possibility. Sometimes using functional features introduces a lot of line noise in the form of accolades, returns, or semi-colons. But C++ has never been quiet in that respect, and the standard has added features, like the auto declaration and range-based for loops, that reduce this noise somewhat. The use of currying in particular may introduce some added noise in that regard. Error messages generated by the compiler are another concern. I have not shown the reader the reams of messages produced when something goes wrong. Again, this is not something entirely new to C++, but it can be a daunting task to work through.

Functional programming emphasizes referential transparency through the use of immutable data. Changes are made to a copy of that data item. In the implementations of map and reduce shown here, new lists are created containing the changed data elements. To remain referentially transparent this requires that the copy semantics of the objects is relatively straightforward. That, in turn, requires the use of straightforward data types, which behave like values, and don’t maintain state. The creation of a completely new list of data items introduces an obvious performance penalty. In languages designed for functional programming the cost of this approach is reduced because items are in fact reused. In C++ the tradeoff of referential transparency versus performance is a real one.

The extension of the functional approach to a richer class of problems, like IO, has introduced a whole new set of concepts. The extent to which those concepts are supported in C++ is a topic I’d like to address in another article.

Alfons started developing software in earnest when he was working on his PhD in physics. He transitioned into the IT side of the finance industry where he has been working on trading systems in C++, python, and Perl. A few years ago he developed an interest in functional programming, learned lisp, and authored lisp libraries for mongodb and twitter, which can be found on his github page. When he’s not programming he’s trying to improve his ironman performance, to little or no avail.

Send the author your feedback or discuss the article in the magazine forum.

Puzzle

A Sudoku-Anagram Mashup

by Michael Swaine

A short session in mental calisthenics.

Here’s another programming-related sudoku puzzle.

It uses letters rather than numbers, but otherwise it works just the way you expect. Your task is to fill in the empty cells so that every row, column, and each of the 3x3 squares contains one each of the nine letters you’ll find in the cells already filled in.

Oh, one more thing. When you finish the sudoku, rearrange those nine letters to spell a name that should be familiar to every programmer.

X
C
X

A
X
X

X
X
X

X
X
Y

X
C
J

X
X
X

A
X
X

W
M
X

X
X
X

X
X
X

W
X
X

L
M
J

U
X
X

J
X
H

X
X
C

M
J
W

X
X
C

X
X
X

X
X
X

X
J
U

X
X
H

X
X
X

C
A
X

Y
X
X

X
X
X

X
X
Y

X
A
X

And the name is: _ _ _ _ _ _ _ _ _ .

Solution right here next issue. Or on Twitter right now, no doubt.

Solution to Last Month’s Puzzle

U
G
I

T
N
O

M
P
C

C
P
M

G
U
I

N
O
T

T
N
O

P
M
C

U
I
G

N
I
G

P
U
M

C
O
T

M
C
U

I
T
O

P
G
N

O
P
T

G
C
N

M
U
I

G
M
N

O
C
P

I
T
U

T
I
P

U
N
G

O
M
C

C
O
U

I
T
M

N
G
P

And the secret word is: COMPUTING.

Calendar

Want to meet one of the Pragmatic Bookshelf authors face-to-face? Here’s where they’ll be in the coming months.

2013-07-01, Indianapolis CocoaHeads

iOS Gesture Recognizers

Jonathan Penn (author of Test iOS Apps with UI Automation)

2013-07-04, Agile Evangelist meetup in London

XP at Unruly—a case study of how we do eXtreme Programming in a fast moving product development environment.

Rachel Davies (author of Agile Coaching)

2013-07-10, Core Vim Masterclass, Online

Core Vim Masterclass

Drew Neil (author of Practical Vim)

2013-07-16, ÜberConf

Workshops and talks on various topics.

Venkat Subramaniam (author of Practices of an Agile Developer, Programming Scala, Programming Concurrency on the JVM, Programming Groovy 2, and Functional Programming in Java)

2013-07-24, OSCON 2013

Advanced NFL stats released the play by play data for the 2002 to 2012 seasons. The play data is human generated. Doing any Data Science on it will be difficult until you transform it.

Jesse Anderson (author of The Cloud and Amazon Web Services)

2013-07-24, OSCON, Portland

10 Reasons You'll Love Dart

Chris Strom (author of The SPDY Book, Dart for Hipsters, and 3D Game Programming for Kids)

2013-07-24, OSCON, Portland

Planned Obsolescence: Built to Last, or Build One to Throw Away?, in which we talk about how to avoid over-engineering and still write code we can maintain

Ian Dees (author of Scripted GUI Testing with Ruby, Using JRuby, and Cucumber Recipes)

2013-07-25, OSCON, Portland

Getting Started with 3D Programming in Three.js

Chris Strom

2013-08-12, That Conference (Wisconsin Dells)

Building Native iOS Apps With RubyMotion

Jonathan Penn

2013-08-13, ThatConference, Wisconsin Dells, Wisconsin

Testing Client Side Code with Jasmine and CoffeeScript With more logic moving from the client-side to the server-side, we've got to get better at testing code. In this talk you'll learn about writing tests for client-side code that help drive the d

Brian P. Hogan (author of HTML5 and CSS3, Programming Concurrency on the JVM, The Rails View, Crafting Rails Applications, Deploying Rails, iOS SDK Development, Web Development Recipes, The Developer's Code, Deploying with JRuby, tmux, Programming Groovy 2, Test iOS Apps with UI Automation, The Healthy Programmer, HTML5 and CSS3 (2nd edition), and Crafting Rails 4 Applications)

2013-08-14, CocoaConf Portland

iPad Productivity APIs workshop

Chris Adamson (author of iOS SDK Development)

2013-08-15, CocoaConf Portland

Get on the Audiobus

Chris Adamson

2013-08-15, CocoaConf Portland

RubyMotion

Jonathan Penn

2013-08-16, CocoaConf Portland

Glitch-Free A/V Encoding

Chris Adamson

2013-08-16, CocoaConf Portland

Testing iOS Apps With UI Automation

Jonathan Penn

2013-08-17, Eurucamp Berlin

Modelling State Machines with Ragel

Drew Neil

2013-08-18, Problem Solving Leadership Workshop, Albuquerque, NM

5.5 days of leadership training for people who want to learn to be problem solving leaders.

Johanna Rothman (author of Behind Closed Doors, Manage It!, Manage Your Project Portfolio, and Hiring Geeks That Fit)

2013-08-29, devLink, Chattanooga, TN

How to be a Healthier Programmer: Your health affects your memory and creativity—skills critical to doing your job well. In this talk you'll learn to change habits, boost brainpower, and master exercises that make working at a computer more comfortable.

Joe Kutner (author of Deploying with JRuby and The Healthy Programmer)

2013-09-05, Agile on the Beach, Falmouth, UK

Workshop: The Art of Slicing and Dicing User Stories

Rachel Davies

2013-09-10, 360|iDev—Denver, CO

Dynamic Audio for Apps and Games—In this talk you'll get a brief introduction to the field of sound design and different techniques that can be used to create sound. You'll then be introduced to PureData, an application and platform for working with sound.

Tony Hillerson

2013-09-11, BDD Kickstart, Barcelona

Get a flying start with BDD, the collaborative process that's changing the face of software development.

Matt Wynne (author of The Cucumber Book and Cucumber Recipes)

2013-09-14, Baruco

TBD

David Chelimsky (author of The RSpec Book)

2013-09-14, Barcelona Ruby Conference

Hexagonal rails

Matt Wynne

2013-09-17, CukeUp! NYC

A 1-day conference dedicated to Cucumber, Specification by Example, and BDD.

Aslak Hellesøy (author of The RSpec Book, The Cucumber Book, and Cucumber Recipes)

2013-09-23, Scrum Gathering Paris

Workshop: TRUST with Sallyann Freudenberg. Come to this workshop to find out how to improve trust on your Scrum teams.

Rachel Davies

2013-09-26, CocoaConf Columbus

iPad Productivity APIs workshop

Chris Adamson

2013-09-27, ISVCON 2013—Reno

I'll be covering how ISVs can use The Cloud to lower costs and improve customer satisfaction.

Jesse Anderson

2013-10-17, GOTO Berlin

Keynote speech and case study on how we apply eXtreme Programming to product development at Unruly.

Rachel Davies

2013-10-25, Rakuten Technology Conference, Tokyo

Talk (and possibly a tutorial)

Dave Thomas (author of Programming Ruby (2nd edition), Agile Web Development with Rails (3rd edition), The Ruby Object Model and Metaprogramming, Agile Web Development with Rails 4, Programming Ruby 1.9 & 2.0 (4th edition), Agile Web Development with Rails 3.2, and Programming Elixir)

Bookshelf

Pragmatic Bookshelf News

Here’s what’s new and what’s hot from the Pragmatic Bookshelf.

What’s New

Agile Web Development with Rails 4 has been updated to the final Rails 4.0 release. Learn to Program has been updated to Ruby 2.0. Programming Elixir is updated to the very latest Elixir 0.9.3. The Developer's Code audio book is now ready for your listening pleasure on your commute or your workout. And the latest version of the venerable Pickaxe, Programming Ruby 1.9 & 2.0, is now in print and shipping.

What’s Hot

Top-Ten lists are passé—ours goes to 11. These are the top titles that folks are interested in currently, along with their rank from last month. This is based solely on direct sales from our online store.

1^ | 2 | Programming Elixir
2^ | 3 | Programming Ruby 1.9 & 2.0
3^ | 4 | Agile Web Development with Rails 4
4^ | NEW | HTML5 and CSS3
5v | 1 | Crafting Rails 4 Applications
6v | 5 | Programming Erlang
7 | 7 | The Definitive ANTLR 4 Reference
8v | 6 | Practical Vim
9^ | NEW | The Developer's Code (audio book)
10^ | NEW | The Healthy Programmer
11v | 9 | The Cucumber Book

What’s Happening

But to really be in the know, you need to subscribe to our weekly newsletter. It’ll keep you in the loop, it’s a fun read, and it’s free. All you need to do is create an account on pragprog.com (email address and password is all it takes) and select the checkbox to receive newsletters.

Shady Illuminations

Call It C+++++

by John Shade

John doesn’t exactly review a book.

“Another d-mn’d thick, square book! Always, scribble, scribble, scribble! Eh! Mr. Gibbon?”—variously attributed, possibly Prince William Henry, Duke of Gloucester and Edinburgh.

Ask any ten programmers what the most perfect programming book is, the definitive definition of a language, and you’ll probably get ten identical answers: It’s K&R.

The C Programming Language by Brian W. Kernighan and Dennis M. Ritchie is the gold standard. What you always hear is that it did exactly what it needed to do and did it in a mere 228 pages.

The latest edition of Bjarne Stroustrup’s The C++ Programming Language weighs in at 1346 pages. Six times as fat. Approximating a cube.

So the logical conclusion is that C++ is six times the language that the original C was. Could that possibly be true?

Well, it’s multiparadigmatic by design. So there’s that.

And then apparently the template metaprogramming syntax of C++ is Turing Complete. Just like Magic the Gathering or the type system in Scala or HTML plus CSS or certain novels by Jorge Luis Borges or Conway’s Game of Life or Unix sed or the Federal tax code. So just a part of C++ is equivalent to C. So there’s that.

Let’s say it’s at least plausible that C++ is in fact C*6.

But when does more become too much? For a language or for a book? For a book, is it somewhere shy of 1346 pages?

From Wikipedia:

“A call to delete, which calls the destructor and returns the memory allocated by new back to free store, must be made for every call to new to avoid a memory leak.”

I think Bjarne has been making a lot of calls to new and forgetting to delete.

I want my memory back.

John Shade was born under a cloud in Montreux, Switzerland, in 1962. Subsequent internment in a series of obscure institutions of ostensibly higher learning did nothing to brighten his outlook. His hobbies are complaining and garbage collection. You should see his collection. Follow John on Twitter, send him your feedback, or discuss the article in the magazine forum.

Rear Window

A Parting Shot

Lest we forget that the personal computer revolution had its roots in 1970s counterculture. Picture courtesy of Alan Cooper.

“This picture,” Alan Cooper says, “was taken in Marin County during the Spring or early summer of 1970, right around my 18th birthday.” Within five years, Alan had founded his first company, SSG, producing some of the first serious business software for microcomputers. In 1988, Alan created a visual programming language code-named Ruby(!), later known as Visual Basic; Alan has been called the Father of Visual Basic. You might also know him as the founder of Cooper, a leading interaction design consultancy, or as the author of About Face: The Essentials of User Interface Design and The Inmates Are Running the Asylum: Why High-Tech Products Drive Us Crazy and How to Restore the Sanity. “The future,” Alan reminds us, “is right in front of us, unobscured by anything other than our inability to recognize it.”