PragPub 2013-06: Issue #48

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.

Keeping Rails on the Rails

by Sam Ruby

How the system that keeps the Rails book on track also aids in the development of Rails itself.

Beyond the DOM

by Stephen Rylander

JavaScript MVC frameworks are here to stay. Here Stephen introduces Knockout, one of the best.

Unification

by Paul Callaghan

A technique developed for automatic theorem proving back in the 1960s proves to be a gateway to many other applications built around matching.

Departments

Up Front

by Michael Swaine

Elixir, Rails, Javascript MVC frameworks, and the Unification algorithm.

Choice Bits

We follow Twitter so you don’t have to.

Lester and Rothman

by Johanna Rothman and Andy Lester

Johanna and Andy discuss managing your career over time.

Puzzle

by Michael Swaine

A short session in mental calisthenics.

Puzzle Solution

by Michael Swaine

Herb Simon, polymath.

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

Phishing has John feeling like he’s living in a dream world—only it’s not his dream.

Rear Window

The Electric Pencil

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

The Magic Elixir

by Michael Swaine

This month we begin a series on one of the most exciting new languages to come along in years: Elixir.

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.

Oh, and the series is written by our own Pragmatic Programmer, Dave Thomas, Agile Manifesto signatory and lead author of the famous Pickaxe book.

Dave also wrote Agile Web Development with Rails with David Heinemeier Hansson, and brought Sam Ruby on board for the third edition of this important book. Sam found that Rails was changing too rapidly for the conventional book authoring process to keep up, so he invented a new, agile process. It turned out that his book-updating methods proved useful for the updating of Rails itself. In this issue Sam explains how this symbiotic publishing and software development system works.

Paul Callaghan has been delivering some deep articles recently on Haskell and dependent types. This month he has something a little different: a dive into the workings of the Unification algorithm. It’s been around since the invention of logic proramming and Prolog back in the 1960s, but Unification can be useful in many settings where matching is important.

Stephen Rylander explains why you need much more than just jQuery in your web app development toolbox to be successful today. What you need is a JavaScript MVC framework, and Stephen shows how to get the most out of one such framework, Knockout.

There was a time when IBM ruled the world of computer technology and when you went to work for IBM, you were done thinking about job interviews forever. It was marriage for life. That world no longer exists. Today, your carreer is your job, and you need to manage it well over time. Johanna Rothman and Andy Lester share their insights on how to do that.

Also: John Shade follows the phishing phenomenon to its logical conclusion, and we have another puzzle and all the other regular features. We hope you enjoy it.

Choice Bits

From the Twitterstream

We follow Twitter so you don’t have to.

This past month everybody who was anybody was at Google I/O, as the tweets from the field show. Well, there or sitting outside a bar in Seattle or lost somewhere between to the Sheraton Reston and IAD.

Report from Google I/O

#googleio keynote so far is like a geek Home Depot—tools for these rabidly appreciative developers. — @StevenLevy

Google builds AppAnnie, CrowdIn and TestFlight functionality right into the Android developer console. #googleio — @ginatrapani

The Android developer console now makes beta testing and staged rollout easy. Nice. — @pamelafox

Android app developers to get referral tracking in Google Analytics & will flow to developer console. — @dannysullivan

Maturity of modern Google: 100 minutes in and first (gentle) dig against Apple (for its one-platform messaging app). — @Ihnatko

So is Google Buzz the step below Google High? — @haacked

There’s nothing wrong with #io13 that a good Saturday Mongolian BBQ + Sunday Mexican buffet can’t fix. — @scottdavis99

Status Reports

TSA clown confiscates my girlfriend’s lighter then declares he is going on break... pulling a cigarette from his pocket. — @rit

Go home, Google Maps: you’re drunk. It will not take me 27 minutes to get from the Sheraton Reston to IAD. Even me: #mapguy — @scottdavis99

OK, that’s it. Scoops can wait. It’s a holiday weekend and I’m going to get rained on in peace. — @StevenLevy

Going walking around Seattle. And by “walking” I mean sitting outside the closest bar until it opens. — @jdalrymple

Have convinced the kid that the tooth fairy grinds up kids’ teeth to make tooth paste. #parenting — @doctorow

OH: “You just put your pickle in an olive.” “Yeah, I call that the ‘Popeye.’” — @undees

Pearls of Advice

Optimists optimize. — @emckean

Not taking risks at all is a big risk in itself. — @ellnestam

Whenever I use Siri I call her by her name because it’s nicer. — @SaraJChipps

This Coding Life

Modeling real world data is hard. There’s no way you can get it right without talking to domain experts.... Likewise, if you’re not a domain expert by the time you’re done, I 100% guarantee you didn’t model it correctly. — @tswicegood

It’s amazing how much faster you can code when you don’t care spit about generality and maintainability. — @KentBeck

I am at a Microsoft-sponsored web site and they have “install with cURL” instructions. Times have changed. — @bphogan

If you’re an SF parent that wants to get your kid into coding, see www.meetup.com/Girl-Develop-It-San-Francisco/pages/ — @pamelafox

Baby steps in a promising direction, rather than staring at the perfect process. #agile — @staffannoteberg

Hey SONOS! 1995 called and wants its confirmation dialog boxes back. #BADUI — @MrAlanCooper

Loved finding out that @louisck’s mother was a computer programmer. — @ginatrapani

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: Kent Beck, Sara Chipps, Alan Cooper, Jim Dalrymple, Scott Davis, Ian Dees, Cory Doctorow, Ola Ellnestam, Pamela Fox, Phil Haack, Brian P. Hogan, Andy Ihnatko, Steven Levy, Brendan W. McAdams, Erin McKean, Staffan Nøteberg, Danny Sullivan, Travis Swicegood, and Gina Trapani.

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

Lester and Rothman

Depth or Breadth?

by Johanna Rothman and Andy Lester

Johanna and Andy discuss managing your career over time.

Johanna: Andy, for this month’s column, we decided to talk about how to manage your career over time. One thing I’ve noticed is that few people have linear careers. Have you noticed that too?

Andy: Linear in what way? You mean up the corporate ladder? I don’t know anyone who has gone straight up.

Johanna: Not just up, but even sideways. I don’t know many people who stay in the same domain. Maybe I should tell you my story.

I started as a developer, and did a little stint as a manager, and dove back into development. Then I was a project manager for a two-and-a-half person project while I was a developer. Then I became a tester, but an automated tester, because I was a developer. Then a beta coordinator, which used my project management skills.

After that I started program-managing, which was managing a large program with sub-projects. Then I became a manager, but I moved to managing groups of people, not just one group. Then I became a director-level manager. After I had my second child, when I went back to work, I wanted contract development work so I could go home and nap, so I took test automation, but with C and C++, because I didn’t have any of that. So I had telecommunications, analytical instrumentation, machine vision and robotics, Symbolics and the Lisp machine which was all about operating systems and low level close-to-the-machine applications, and then more machine vision and assorted distributed systems. When I was an employee, I had a ton of systems-level experience, real engineering experience. A lot of that was the time‚Äîthe late ’70s through the early ’90s.

Andy: I know many people who have been like that, but I know just as many who have stuck with programming because it’s what they love to do. That’s pretty much my story. Started out programming, kept at it, kept getting better at it. When I became the manager of the development department, my boss reminded me repeatedly, “If you take this position, you know you can’t code all day.”

Johanna: Yup, that’s why I took that automation job after my second child was born. I knew that coding was going to be easier for me than management.

Andy: I think that different people are built different ways. People like you like the wide areas of knowledge, and I tend to go deep into what I know. I’ve been doing Perl for about 15 years now. Let me test a theory here: How much of your breadth-over-depth tendency is because you get bored easily?

Johanna: Oh, you pegged me! I like projects I can finish, so I can see my results. I like to learn new kinds of domains, because otherwise I get bored. And that’s why managing your career, in some way, shape, or form, if you are like me, is an excellent idea.

But you can’t wait for your manager to do it. You have to start and keep going yourself. If you do a little bit, every week, that’s fine. But you have to do it yourself.

Andy: Absolutely, it’s all your responsibility. I cringe when I see someone on /r/jobs saying something like “My manager isn’t sending me to any training to expand my skills!” Well, no, he won’t if it doesn’t have direct benefit to the company. If you want to learn stuff, and the company’s not doing it, you have to do it yourself. You are the manager of You, Inc., and you are responsible for growth of its one employee.

On the topic of You, Inc., we all have to be prepared to get fired tomorrow. We each have to be ready for the day when, even though we are stellar performers, the boss calls us into the office and gives a speech starting with “Because of the tough economic times, we’ve had to make some hard decisions.” There is no such thing is job security. None. Zero. You want job security, join the military.

Johanna: Exactly. If we don’t keep up with what’s going on in our industry, it won’t be our industry for much longer. I once gave a talk at WIND, Wednesday Is Networking Day. A woman came up to me later, and told me she was a COBOL programmer. I asked, “A COBOL programmer?” She said, “Yes, COBOL, that’s it.” “Don’t you want to learn anything else?” “Nope. I’m happy with COBOL.”

Well, that’s fine for now. But those COBOL programs are being retired. And, if I were her, I sure would like the option of having other choices.

Andy: That’s great that she’s happy with COBOL, so long as she finds employers who want that. I taught myself COBOL back in the late ’80s because I figured it would help my career in the future. Thank goodness I never had to fall back on it.

But we may be misleading our readers by this breadth-vs-depth distinction. Would you agree that neither breadth nor depth is “The Right Answer” to keeping yourself employable? I know if I had to go get a job tomorrow, I could walk into most any Perl gig with my background, but the number of Perl positions seems to be declining over time. Compare that to your situation of having done a lot, but maybe not having expert-level knowledge at most of the things you’ve tackled.

Johanna: Well, in my story, when I looked for contract work, C++ was big. That was in ’92. I had Lisp as an OO language, but there weren’t many jobs in Lisp. If I was going to manage developers and testers, I wanted to understand their issues. I had a hard time with C pointers, and had a lot of memory leaks in my code, so when I managed a group just a year later, I understood the need for tools.

I agree that you have to decide for yourself when to go broad and when to go deep. “The Right Answer” is to keep learning. There are functional skills and domain expertise, and those are just two areas of a technical skill set. You need a lot more than those to keep your skills present and up-to-date.

Andy: One of the phrases I like to keep rolling around in my head is “the velvet coffin.” It’s a situation where you’re so comfortable doing what you’re doing that you don’t bother learning anything new, and you’ll just be happy to die at the given company.

Johanna: Some companies don’t want any change at all. You need to know how comfortable you can be in their environment. If you want a cultural fit with a new employer, you need to understand how much initiative they want. You and I are pretty high initiative people. Not everyone wants high initiative people. I’m big on change‚ÄîI’m a consultant.

Andy: And it’s real easy to get in that situation. Learning new skills falls into Covey’s Quadrant 2: Important But Not Urgent, so we tend to ignore it.

Johanna: Right. When I ask people to look at their job timelines when they think about seeking a new job, I get them to think about their values. What matters to them? Those principles matter. For me, the values of control over my job and learning is huge. I can live with a lot if I have those two values.

Andy: I don’t think company culture stops you from learning on your own. It’s just that some cultures won’t encourage it directly. What to you is “control over my job”?

Johanna: Well, if the company culture is “We have to work from 6am to 10pm every day,” that might prevent you from learning on your own. Control over my job is when my manager tells me the results he or she wants and I get to do it my way. Or, if we are an agile team, and someone tells us what they want and I get to work with the team to define how we do it, that’s control over my job. I am happy to be responsible for the results. I don’t want someone telling me how to do something. That makes me just a little crazy.

Andy: Is there something you can do in managing your career, well before you look for something new, that makes you more likely to find something that will allow you to learn and something that gives you more control over your job?

Johanna: If you approach your current job as something that should allow you to learn something and something that should provide you control, you are practicing.

You can start from where you are. This is why you want weekly or bi-weekly one-on-ones with your manager. That way you can make sure you are on the right track and that you are learning something you want to learn. If you are not, you can rearrange the project (maybe) after a while.

When I was a manager, I had a deal with my staff. I said that we all had to have some amount of scut work, but if that amount ever got to be more than 20 percent, they should let me know, because then we had a problem that we had to solve our way out of. We could all manage 20-percent scut work, but if there was more than that, then we had a huge problem on our hands and we had to solve it. We were not being creative enough.

Andy: How do you know if you’re managing your career properly? Is there a dial or warning light? I know one piece of advice I give is that you should be able to add one new interesting, sellable thing to your resume every quarter.

Johanna: That’s a good thing.

Andy: Say you set up monitoring on your servers using Nagios. Put it on the resume. You learned Solr as a search backend? Put it on your resume. You’ve done the same old thing the past quarter? Nothing to put on your resume? Then you’re stagnating.

Noting these things on your resume also has the benefit of keeping those things fresh in your mind when yearly performance reviews come around.

But what else can we do besides tracking commits to our resumes? Do you keep metrics on how you’ve expanded your circle of contacts?

Johanna: I keep increasing my LinkedIn contacts. I also have a mailing list, and I have statistics on that. So I know how large my mailing list is growing, and that, for me, is what I use for stats now. If I was an employee, I would track my LinkedIn contacts and recommendations.

Andy: Do you actually see value in LinkedIn contacts? I get asked all the time “is LinkedIn worth it?” and the best I can say is “If it gets you a contact to a new job, yes, but it’s no guarantee of anything.” How do you measure the bang/buck ratio?

Johanna: You don’t need to be a “promiscuous” linker on LinkedIn, but if you are not adding people on LinkedIn, you are not doing yourself any favors. There is tremendous power in loose connections. Your loose connections will get you your next job.

Andy: Who do you add on LinkedIn? I assume for you it’s somewhere between “Only people I have worked with that I like personally” and “anyone with a pulse.” Say more about “loose connections.”

Johanna: Loose connections are people who have something or someone in common with you, and are not total strangers. They might belong to a group with you; you might have met them at a conference. Maybe you read something they wrote or vice versa.

If you work in a large company, maybe you work “with” them! But you don’t work directly with them. Now that I’m older, they tend to be children of my friends :-)

Andy: Why do you say they will get you your next job?

Johanna: Because they know someone who knows someone. They are often people who will get you an employee referral. That is what will get you your next job. It works for me all the time as a consultant. All the time.

Andy: What about those of us who are not consultants?

Johanna: They get you employee referrals.

One more thing I want to say as we wrap up. Don’t neglect the interpersonal skills. They are just as important as the technical skills. For some of us, they are more important. I focused on the technical skills for the first 15 years of my career. I shifted to interpersonal skills when I started my consulting business because I realized that’s what I needed to focus on.

Even when I was teaching test automation, project management, and other more technical workshops, I was learning interpersonal skills. Now that I teach interpersonal skills, I am still learning them. So, consider what you need to learn at different points in your career.

Andy: Especially for those of us who have been doing this for a decade or two, we need to remember that any kid fresh out of school can have, in two years time, as much relevant tech knowledge as we have. Sure, I’ve been doing this for 27 years, but nobody cares about my experience in Apple Pascal on the Apple //e. What we have to work with is our understanding of the processes and the human side of the technical world.

Johanna: What stands out for me as I review my career is that it is non-linear. I never would have expected it to take these dips and turns. If you exploit your knowledge, and keep learning, you can keep your career going, which is the point of all of this.

Andy: And we hope it’s been helpful. Next month, we ll be talking about how to build and maintain your business network without feeling sleazy. Until then, we welcome your comments and feedback.

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 r√©sum√©s, 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

A Gentle Introduction

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.

Fifteen years ago. That was the last time I was this excited by a programming language, and that language was Ruby.

It wasn’t for lack of trying. I explored them all as they came out, but none grabbed me—none made me feel like I’d enjoy spending years digging in.

Then I found Elixir. Twice. The first time was a year ago, and I thought it was very nice, but not compelling. But Corey Haines pushed me to look again. He was right. Elixir is special.

Enough with the Fanboy Hype

Sorry.

Elixir is a functional programming language that runs on the Erlang virtual machine. It has a Ruby-like syntax, and features protocols (for extending modules without changing their source), macros, and very good metaprogramming support. It has the benefit of learning from other languages’ experiences, too, so it has many modern features. For example, protocols and macros are lexically scoped, so metaprogramming no longer risks messing up the global execution environment.

Elixir runs on the Erlang VM, Beam, and is fully compatible with existing Erlang code. This means you can take advantage of the high availability, high concurrency, and distributed nature of Beam. It also means you can use all the thousands of existing Erlang libraries, both built-in and third-party. In particular, Elixir can run within the OTP framework.

Enough—Show Me the Code

(If you want to follow along at home, download Elixir. The instructions are on the Elixir site.)

The following code calculates the sum of the elements in a list.

| defmodule MyList do
| def sum([]), do: 0
| def sum([ head | tail ]), do: head + sum(tail)
| end
| IO.puts MyList.sum [1,2,3] #=> 6

Our sum function lives in a module called MyList. The function is defined in two clauses. So how does Elixir know which to run?

Pattern Matching

This is where pattern matching comes in. The parameter list of the first function clause is just the empty list. When you call sum, this clause will match only if you call it with an empty list. If it does match, the function returns 0.

The second clause has a more complicated parameter list: [head|tail]. This is a pattern that matches a list (the square brackets tell us that). The list must have a first element (the head) and a tail (the remainder of the list). If the list we pass in has only one element, the head will be set to that element, and tail will be the empty list.

So let’s call MyList.sum with the argument [1,2,3]. Elixir looks for the first clause whose pattern matches the argument. The first clause doesn’t match—the argument isn’t the empty list—but the second clause does. head is set to 1 and tail to [2,3]. Elixir evaluates the body, head+sum(tail), which means that the sum function is called again, recursively. The sequence of calls looks something like this:

| sum([1,2,3])
| 1 + sum([2,3])
| 1 + 2 + sum([3])
| 1 + 2 + 3 + sum([])
| 1 + 2 + 3 + 0

Pattern matching is at the core of Elixir. In fact, it’s the only way of binding a value to a variable. When we write what looks like an assignment:

a = [1,2,3]

Elixir is busy trying to work out how to have the left-hand side match the right. In this case, it does so by binding the list [1,2,3] to the variable a.

Once a has this value, you can write:

[1,2,3] = a

And Elixir will be happy—the value on the left matches the value on the right. But if you write:

99 = a

Elixir will complain that it can’t find a match. That’s because Elixir will only change the value bound to a variable if it is on the left-hand side of the match operator.

Pattern Matching Structured Data

Matching goes further—Elixir will look at the structure of the two sides when making a match:

| [ a, b, c ] = [1, 2, 3] # a = 1, b = 2, c = 3
| [ head | tail ] = [1, 2, 3] # head = 1, tail = [ 2, 3 ]

Once bound, a variable keeps the same value for the duration of the pattern match. So the following match will only succeed if the variable list is a three-element list where the first and last elements have the same value:

[ a, b, a ] = list

You can mix constants and variables on the left hand side. To illustrate this, I’m going to introduce a new Elixir data type, the tuple. A tuple is a fixed-length collection of values. We write tuple constants between braces:

| { 1, 2, "cat" }
| { :ok, result }

(The :ok in the second line of code is an Elixir symbol. You can think of it as a constant string, or as a symbol in Ruby. You can also think of it as a constant whose value is its name, but that can lead to catatonic states.)

Many library functions return two-element tuples. The first element will be the status of the result—if it is :ok, the call succeeded; if it is :error it failed. The second value will be the actual result of the call, with more information on the error.

You can use pattern matching to determine if a call succeeded:

{ :ok, stream } = File.open("somefile.txt")

If the File.open succeeds, then stream will be set to the result. If it doesn’t, the pattern won’t match, and Elixir will raise a runtime error. (Although in this case, you’re better off opening the file with File.open!(), which will raise a more meaningful error on failure.

Pattern Matching and Functions

Our MyList.sum example showed that pattern matching also applies to calling functions. The function parameters act as the left-hand side of the match, and the arguments you pass act as the right-hand side.

Here’s another (hoary old) example: it calculates the value of the nth Fibonacci number.

Lets start with the specification of Fibonacci numbers:

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

Using pattern matching, we can turn this specification into executable code with minimal effort:

| defmodule Demo do
| def fib(0), do: 1
| def fib(1), do: 1
| def fib(n), do: fib(n-2) + fib(n-1)
| end

Elixir comes with an interactive shell called iex. This lets us play with our fib method:

| elixir % iex fib.ex
| Erlang R15B03 ...
| Interactive Elixir (...)
| iex(1)> Demo.fib(0)
| 1
| iex(2)> Demo.fib(1)
| 1
| iex(3)> Demo.fib(10)
| 89

But there’s a problem with this code. What happens if we call fib(-1)? The third clause will match, and will call fib(-3), which will call fib(-5), and so on until we run out of stack. We should limit the arguments to fib to nonnegative numbers.

In Elixir, we do this with a guard clause. A guard clause enhances pattern matching by letting us write one or more conditions that the arguments must meet if the match is to succeed. In this case, we could write:

| defmodule Demo do
| def fib(0), do: 1
| def fib(1), do: 1
| def fib(n) when n >= 0, do: fib(n-2) + fib(n-1)
| end

The when clause is the guard. It says that the third function clause can only match if its agument is greater than or equal to zero. (Technically, it could have been greater than or equal to two, as the first two function clauses handle the 0 and 1 cases, but for some reason I find using 0 here is clearer.)

The wonderful thing about this is how easy it is to convert a specification into runnable code. And, once that code is written, it’s easy to read it and see what it does.

Something else to note: there are no conditional statements in the implementation of our function (apart from the guard clause). This also makes the code easier to read (and maintain). In fact, many fairly large Elixir modules are written with few or no conditional statements.

Transformation is Job #1

You might be thinking that this all very well, but you don’t write mathematical functions as part of your daily job.

But functional programming isn’t about mathematical functions.

Functions are things that transform data. The trig function sin transforms the value 90° to the value 1.0. And that’s the hint.

Programming is not about data. It’s about transforming data. Every program we write takes some input and transforms it into some output. The input could be a web request, some command line parameters, or the weather in Boise. Whatever it is, our code takes it, and transforms it multiple times on the way to producing the desired result.

And that’s why I think functional programming is a natural successor to object-oriented programming. In OO programming, we’re constantly concerned about the state of our data. In functional programming, our focus is on the transformation of data. And transformation is where the value is added.

Next Month

Next month, we’ll look at functions, both named and anonymous. And we’ll explore the pipeline operator, which lets us write things like:

request |> authenticate |> lookup_data |> format_response

If you can’t wait until then, there are a couple of Elixir screencasts available on my Elixir book’s home page. And if you want the real scoop, you can always buy the book. :)

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.

Keeping Rails on the Rails

System Testing Rails Itself

by Sam Ruby

How the system that keeps the Rails book on track also aids in the development of Rails itself.

A minimal expectation of any book that purports to teach you about a subject is that the examples it provide actually work.

A few years ago, an excellent book by Dave Thomas and David Heinemeier Hansson was no longer meeting that expectation. Not because it wasn't well written (it was!), or even that it wasn't accurate at the time it was written, but rather because the topic it covered (Ruby on Rails) changed tracks underneath them.

I was added to the team for the third edition as an author with the intent of bringing the book up to date. As I was doing so, I found that the book's subject matter was a constantly moving target: Rails was continuing to change underneath me.

As an agile web developer myself, I did what came naturally: I started automating my testing.

You see, the book takes you though a real-world scenario in which you execute commands, edit files, and visit web pages. So I wrote a script that did each of those steps, captured the output, and presented it as a series of web pages. I then wrote a script using the same functional testing methods that are made available to Rails developers to compare the output produced against what is expected.

As you might imagine, from time to time there are failures. Failures generally mean that either the book needs to be updated, or Rails needs to be fixed, or, in some cases, both.

In the process, I've found that this automated testing has not only been helpful to me, but also to the Rails team. The primary focus of their testing is the extensive unit tests coupled with running the code in production. What that combination misses, however, is the running of system tests of Rails using the actual defaults that are provided. This means that I routinely find problems before the Rails team themselves are aware of them. I captured such an example on my weblog last year:

| rake db:migrate
| rake aborted!
| An error has occurred, this and all later migrations canceled:
| uninitialized constant Arel::Relation
| Tasks: TOP => db:migrate
| (See full trace by running task with --trace)

What this means is that anywhere from a couple of times a week to a couple of times a month I get alerted to a failure. Simply by rerunning tests on other configurations, I can determine if the failure is unique to a particular version of Ruby, and what editions of the book the failure affects.

As the scenario sections are numbered, and because I have the ability to rerun specific steps and I know when the tests last passed, I can generally run git bisect to identify the offending commit.

Once I have this information, I approach the Rails team with the following question: "Was this change intentional?" Sometimes the change is intentional. Often it is not, and my output and identification of the commit that introduced the problem is all they need to know to fix the problem. Sometimes they ask me for smaller test cases, which I then produce. Example:

Here’s the test case reproducing the error.

Here’s the output of test case.

Here’s the output showing the use of git bisect to determine the commit that caused the error.

Here’s the Lighthouse Ticket reporting the bug.

In rare cases, such as this one, I may even offer a fix:

For intentional changes, I obviously update the book. Turning around an eBook with changes in a timely manner is a bit of a challenge, but well worth it. Generally we seem to be managing it within 48 hours. Turning around dead-tree versions in a timely manner takes a bit longer, but those versions benefit from the feedback provided by the tens of thousands of people who have had early access to this material in ebook form.

Still more details are available in my 2010 RailsConf presentation on System Testing Rails itself.

Output of runs can be found here.

More recently, there was a change intended for Rails 4.1 to use a new version of minitest. I left a comment containing a description of the failure as well as the output of a minimal test case that demonstrates the problem. In addition to showing the commands that were issued and the output that was produced, a description of the environment is included. This resulted in a fix to minitest.

The scripts themselves are available and can be found here.

In that git repository there is a subdirectory named vagrant that contains all of the necessary configuration to create a virtual machine and run the entire scenario.

You are welcome to poke around, and if you have any questions feel free to participate in the online forum. But most of all, if you are a Rails user, I encourage you to set up your own tests and try out Rails betas and release candidates as they become available. Nothing frustrates the Rails core developers more than to be told about a problem only after a release is made. Don't be that guy! :-)

Sam Ruby is a prominent software developer who has made significant contributions to many of the Apache Software Foundation’s open source software projects, and to the standardization of web feeds via his involvement with the Atom web feed standard and the feedvalidator.org web service.

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

Beyond the DOM

Getting the Most out of JavaScript MVC Frameworks

by Stephen Rylander

JavaScript MVC frameworks are here to stay. Here Stephen introduces Knockout, one of the best.

You can’t make soup with just water. Then why do you only use jQuery to build a web application? The answer is you don’t. This article addresses why you need much more than just jQuery in your toolbox to be successful on the web today—what you need is a JavaScript MVC framework.

The War Is Over

A JavaScript MVC framework is a framework that provides data models, views, collections, events, bindings, and dependency tracking. Additionally, some frameworks provide explicit or implicit hooks back into server-side data models via convention-based REST interfaces. The interesting thing is, the war is already over. I know, I know, maybe you didn’t realize there was a war, or maybe it was more of a takeover, but however you cut it—JavaScript MVC frameworks are here to stay. That is a good thing.

How did this war wage on and how did MVC win? Against what or whom?

Well, I may be committing a logical fallacy, but JavaScript MVC frameworks won out over nothing. That’s right—the alternative was nothing. That is, roll your own JavaScript framework or don’t make highly interactive data-driven applications. Take your pick, but either way; it wasn’t going to be a pretty ending. Because unless you had the scale of a corporation building something like Gmail or just a awesome group of co-located skilled engineers who will make sure each JavaScript team agreement is followed to the letter of the law, then you were out of luck.

Which is all fine and good, but, why not just jQuery? jQuery is for DOM manipulation, simplifying Ajax and generally make cross-browser support work. You can use it with a JavaScript MVC framework—don’t worry. jQuery is still the standard DOM abstraction layer.

The last part of how JavaScript MVC frameworks won, besides that they were fighting against the alternative of “do nothing” is the same way that TDD (test driven development, but you know that…) won. It works. It’s dependable. It makes sense. You ship faster. You ship better products. The jury came back on this one—it’s over. Onward we go.

No Lack of Options

There are many options available in this space—too many for your humble author to enumerate. Frameworks like Backbone.js have really caught wind with the community, Ember.js has a very full-featured stack and Knockout is straightforward and based more on MVVM than MVC. Google, of course, has an entry with Angular and that will surely take over the world at some point in time—but not quite yet.

I’m just going to discuss Knockout and use it exclusively in my code samples. Why? Besides my personal experiences with the framework, KO is expressive and straightforward as far as binding syntax, UI refreshes, dependency tracking, and templating.

One last word on jQuery versus JavaScript MVC frameworks, from Knockout’s documentation: “KO doesn’t compete with jQuery or similar low-level DOM APIs. KO provides a complementary, high-level way to link a data model to a UI. KO itself doesn’t depend on jQuery, but you can certainly use jQuery at the same time, and indeed that’s often useful if you want things like animated transitions.”

The key points to a JavaScript MVC framework, as enveloped by Knockout, are: object models, horizontal scaling, shared skill sets, clean code, focus on services, and thinner layers. We’ll discuss each of these.

Object Models

Haven’t we spent enough time in this industry to at least know having an object model is better than a loose association of variables spread across a number of files that somehow, in someone’s mind, resembles a ball of mud? I mean—that’s a lesson that we’ve learned as well, right?

Luckily for us, using Knockout (again, or any first-tier JavaScript MVC framework) we can take advantage of our core domain object model in the browser. Later we’ll see how they can sync up back to the server. For instance, here you can see that we’ve defined a view model for a portfolio (as in investments):

| var portfolioViewModel = {
| name : "401k",
| id : 99,
| owner : “454-abc-565”
| };

This model is similar, if not identical, to what we have on the server-side—that’s important because the data is only persisted after it passes through the domain logic and validation back at the server. However, the server can be the page or a service end point. More on that later as well, but as a spoiler alert, it’s no different than any other contemporary Ajax design.

We named our model object portfoioViewModel. It has three properties, and in this instance each one is initialized. This is all vanilla JavaScript—no magic.

By the way, Knockout is not pure MVC. Don’t worry. It’s MVVM: Model, View, View-Model, where the View-Model is like a special controller that also has all the logic needed to work with the view, convert data back and forth, and protect the other two tiers from each other. It’s an idiom that takes just a little getting used to, but it’s quite powerful for UI development.

Object Models—Dynamically

Knockout allows you to dynamically generate your client models. Why would you want to do this? Simple—maintain the model code once, and use everywhere.

Pretend you have this class server-side.

| public class Portfolio{
| public string name;
| public double marketValue;
| public string ownerId;
| }

It’s inefficient to recreate the class entirely, by hand in JavaScript, on the client, because we wish to work with the same data structures. Why not just serialize the whole structure down? Lots of developers wonder this once they start with a framework, and luckily, most frameworks have considered this and provided solutions.

In Knockout, it’s the ko.mapping plugin.

With this, you can write some code like:

| var myData = getPortfolioWithAjax(); //get an instance of that
| //server-side Portfolio class

Now you will have myData as a Portfolio object, client side in a JavaScript object. This actually turns into another reason to keep your domain model simple, to enable this type of serialization.

Next, you can load that data up into a view model object using ko.mapping.

var viewModel = ko.mapping.fromJS(myData);

At this point, all the public fields in Portfolio (since the private normally wouldn’t be serialized down) are accessible via viewModel, e.g. viewModel.name(). The mapping plugin also handled making the object a KO object, meaning that all of these fields of the object are observables. More on observables later.

Horizontal Scaling

Frameworks like Knockout certainly do not enable horizontal scaling themselves. It just makes it easier and more cost effective. When you have the ability to push more work into the client, driving richer user experiences, faster pages or any of the other benefits of a solid UI, you will do that. When the risk versus reward of doing so is too high, you will avoid richer interfaces. The JavaScript MVC framework is an enabler for you, the developer, to make the trade-off.

Horizontal Scaling via Browsers

In this figure you see that when we are capable of doing more in the browser, we do so. That means more processing, that is the right processing, can be done in the browser. For instance, reordering and filtering a set of data doesn’t require a server session, a post-back, and a retrieval of JSON, XML or (goodness) HTML. If the data set is present, do the work in the browser. And just as jQuery enables us to write quick and simple DOM manipulations, a framework like Knockout has our data in the model and it’s just a matter of resorting. In fact, the UI can respond to the resorted dataset via observables, which we will cover later.

Once more work is done in the browser, the server-side architecture can begin to change as well. Maybe the solution doesn’t require beefy web boxes anymore to deal with constant dynamic data queries, page renders or POSTs. Instead, a thinner Ajax services layer can be rolled out as in the following figure. Here, we can scale our Services tier as our user base increases. The Services tier can deal with the caching of data from other sources, hiding it from the browsers and the web app. It delivers some specialization, which means that different parts of the system can grow organically and respond without a server whose main purpose is serving HTML getting involved.

Horizontal Scaling via Services Layer for Ajax

Shared Skill Sets

One of the not so obvious reasons to get on board a JavaScript MVC framework is the promotion of full stack development—what used to be termed “shared skills.” In the classic web site/application model there are “server-side,” also sometimes called “backend developers,” who do server-ish work; connect to databases, transform data, etc.

Then there are front-end developers (FED’s) who are concerned about the UI and UX via CSS, HTML and JavaScript. The FED makes the application come to life and has traditionally had to pick up whatever loose pieces the server-side developers left them. Sometimes, this could be as ambiguous as server-generated ID tags in HTML elements, or fragments of JSON. Lots of these practices came from Microsoft, though they also brought forward the MVVM model, so they continue to breakeven with lots of developers.

Classic Web Development Model

In this figure you can see how both these sets of skills are required in creating an application, but are disconnected. The disconnection promotes inefficiency all around, as the two often work against each other, and leads to hand-offs during development.

The alternative is illustrated in the next figure. In this world we are leveraging the domain models from the server-side in the front end. This means that the FED’s on the team are working with the domain, and not some mimic of the domain objects. It also means that both server-side and FED’s can work together on what the view-model’s responsibilities should be. Finally, since the JavaScript is now separated from the UI, the code is in a better place to be unit tested and run through automation.

At the end, developers will become full stack developers—able to work from the back to the customer at the browser at the front.

Bridging Skills

Clean Code, REST and Layers

These three topics are tied together in a lot of discussion and literature, so I won’t be the one to break them apart. REST is, for whatever reasons, seen as clean. Maybe because it promotes layers, or because everyone has an affinity for the HTTP spec and its simplicity. Here is how they break down.

Clean Code—because frameworks like Knockout inherently promote modularization, separation from UI, and models, you can generate code that is worlds more readable than can a developer slinging JavaScript alone.

REST—many of frameworks, including Backbone, promote idioms following RESTfull practices to get and put data objects. Knockout doesn’t promote any particular way, but it also doesn’t stop you from following a basic RESTfull approach to talk to the server and manipulate domain-model objects.

Layers—by providing the capability to write Clean Code, following REST patterns, layers will emerge—and when done right, this is considered a good thing. Better the layer you know than the layer you don’t know.

A Word on Templates

The concept of a server-side template can’t help but be contentious. Why? Because it’s rendering a view on the wrong tier of the application. The browser is responsible for the view. But in the traditional web site sense all it receives is an HTML document. That would be fine if the web were still just about traversing resource links to new documents all day, but it’s not.

For example, if your server-side template is rendering a view, let’s say it’s working on the table that is in the middle of a page, and it needs to use another value that was rendered somewhere else in the page to do a row calculation. Ignoring that there are other solutions to avoid such a mess, what is the answer? Trick question: no matter the answer, it’s all server-side so devoid of browser context and requiring a page refresh. Plus, is a server-side page template rendering being done in the View or the Controller? It’s not the view, as the view is certainly not on the server. But, it can’t be the controller, as the controller doesn’t work directly on the view. This model just doesn’t work for every use case the way it used to.

In the last part of this article we’ll dive into some of the core concepts of the framework and explain what makes these important to building powerful apps and growing a team of full-stack developers.

Bindings

Pretend you want to take an object, like a transaction from a Portfolio (e.g. buy 55 shares AAPL at 454.341) that is loaded up into your client side view-model and display each row in a table. It’s all client side at this point, and there is no need to write any more JavaScript. Just use declarative bindings such as:

| <td><span data-bind='text: ticker'></span></td>
| <td><span data-bind='text: name'></span></td>
| <td><input type="text" data-bind='value: shares' /><td>
| <td><input type="text" data-bind='value: price' /><td>

The data-bind syntax is the glue here—and it does exactly what it says, replaces the value for a given HTML element with the value associated with that field on the JavaScript view-model object. This is triggered after calling ko.applyBindings(myModel). It can also iterate over a collection of objects like:

<tbody data-bind="foreach: trxns">

where trxns are all the transactions in a portfolio, an array in the Portfolio object. The value binding is the most basic. There are bindings for all sorts of situations, like text, html, css, if, checked, hasfocus—and what is not there can be developed without too much effort. This too can be found in the Knockout documentation.

Dependency Tracking

This is arguably the most sought-after feature of JavaScript MVC frameworks, and Knockout has an easy-to-use implementation. Dependency tracking enables automatic UI refreshes based on model data value changes. For instance, when the underlying model for the field “name” changes, the UI will update. The bindings are two-way—so updates to a textbox that is bound to an observable will update the model.

The key to this is observables. Your JavaScript object properties need to be initialized as Knockout observables. This puts an abstraction between the actual property and how it’s changed or read. At the same time, Knockout can track the property, know when it’s changed, and fire the events to update anything that is bound to this property. This code illustrates the Portfolio JavaScript object as an observable:

| var portfolioViewModel = {
| name : ko.observable(‘401k’),
| id : ko.observable (99),
| owner : ko.observable (“454-abc-565”)
| };

Now, when the name field is updated, Knockout knows and can respond by triggering the bound items to update. You can also manually subscribe to change events to be notified of a change.

Templates

With a client-side template you’ll find a new canvas of possibilities. Since you are in your view to do view rendering, you can keep iterative looping structures and their associated template close by. As well, the basics of client-side templating mean that the server side can be more concerned about getting the correct data, in the correct format, and not the semantic nature of the data returned. In this way, the FED’s on the team can handle binding large amounts of data into the appropriate UI structures. It can be changed, swapped, iterated on—all independent of any server-side compiles or deployments.

| <div data-bind="template: { name: 'transaction-template',
| data: trxns }"></div>
| <script type="text/html" id="transaction-template">
|     <p> data-bind="text: name"></p>
|     <p>Purchase Price: <span class="price"
| data-bind="text: price"></span></p>
| </script>

Here we have the trxns collection, from our view-model. The first line says: “bind this data set to the named template and put the content here in my div.” There are many different ways to work with templates and a myriad of applications for them—this is the most basic. Templates work in conjunction with observables and declarative bindings—it is the transportation and implementation engine for those concepts in most cases. The client-side templates also put the CSS and the actual markup closer together, as these are components that should ride side by side and exhibit some cohesion.

Debugging

The most applicable tool to debugging Knockout applications, or any JavaScript MVC framework applications, is Firebug for Firefox or any other browser development tool in your favorite browser.

For example, if you want to validate that your bindings are working when an observable is updated, you could type something like this right into the console in firebug and watch the UI for the update. The below would turn any field, bound to MarketValue to 555 in the UI.

| viewModel.HoldingTransactions()[0].MarketValue(555) //updates the
| //model directly for the first transaction in the
| //transactions collection on the view model

Conclusion

JavaScript MVC frameworks are enabling technologies. They enable you to bring domain concepts cleanly into the front end, work with familiar concepts, and promote full-stack development. They also may help your application improve its layering and use of REST-based lightweight service tiers, and you’ll generally end up with more modular clean code.

They do this through declarative bindings, dependency tracking, and templating. A JavaScript MVC framework can be a great benefit to the technology your team uses as well as the possibilities that are opened up when a solid abstraction and framework are in place. Happy coding.

Stephen Rylander is a technical lead with Morningstar focusing on web platforms on a global scale. He focuses on technical design, high quality code, teams and automation. Stephen has worked on four different public web platforms handling millions of daily page views, from finance to ecommerce to music and entertainment. He is adept at working with globaly distributed teams and has accepted that enjoying software development more than most people is just somethign he'll have to live with. He is also married, loves to cook and has two beautiful children.

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

Unification

It’s Not Just for Prolog

by Paul Callaghan

A technique developed for automatic theorem proving back in the 1960s proves to be a gateway to many other applications built around matching.

We interrupt this series on dependent types for a brief diversion into an important algorithm in advanced programming languages: unification!

Unification is basically a way of matching pairs of expressions and combining the information in a consistent way, and it finds many uses in AI and in advanced programming languages. Unification was developed in the 1960s by J. A. Robinson as part of the resolution technique in automatic theorem proving. It is a cornerstone of the computation mechanism in Prolog and related logic programming frameworks, such as miniKanren.

It is used in Haskell and related languages as part of the type checker, particularly when polymorphic type variables are in use, where it is used to match type expressions and to propagate consequences. For example, map has type (a -> b) -> [a] -> [b] (which means, given a function converting some type 'a' to another type 'b', and a list of such 'a' values, then the result is a list of such 'b' values). If map is applied to a function of type Int -> String then the type checker expects the second argument to be a list of Ints and infers that the result will be a list of Strings.

Unification is also a powerful tool in the proof assistant tools for dependent types, where it is used for matching and filling in potentially any details—not just type variables, but potentially any part of your program. It’s also a key component of the automatic tactic commands which can fill in many of the obvious cases of proofs.

But I think unification is just a great piece of Computer Science to know and to study! It encompasses several useful theoretical ideas, has clear practical uses, and is a good gateway to even more interesting topics. It’s a good programming exercise too, since it covers quite a few techniques that are needed in (formal) language processing—and it serves as a non-trivial example of Haskell.

Plus, seeing a clear program for some theoretical idea is fantastic reinforcement for the underlying theory! I believe this is a great way to learn: we can write ideas down and experiment freely with them, and it seems to be the way many programmers do think—a better fit than the more traditional “here’s the theory” approach.

A few years back, I had the good fortune to put this approach into practice in a final-year undergraduate module on advanced logic and programming techniques: the first half of the module was a walk-through of implementing a simple theorem prover. A small but committed group of students signed up, plus a guy who decided I was the least bad option from a set of choices. I’m pleased to say “strategic choice guy” really enjoyed it, got good grades on it, and was himself pleased that he now really understood some theory he’d been required to memorize for the exam the previous year (and saw the point of it). Result!

Informal Overview

We’ll be writing code to take two expressions and produce some result that indicates whether a match is possible and if so, under what circumstances the match works. The expressions are mainly basic functions & arguments style, with fixed function names and constants mixed up with “variables,” pretty much what you’d see in C. Some concrete examples:

0 and 0 are unifiable—they are the same constant

true and false are not unifiable, because they are different constants

f(0, g(true)) and f(0, g(true)) are unifiable—same function applied to unifiable arguments

the following (taken a pair at a time) are not unifiable: f(0, true), f(1, true), f(0, false), f(0, true, 2), and g(0,true) -- for reasons of: different arguments (twice), different arity (argument count), and different function symbol

The above are yes/no questions. It gets more interesting when we add “variables.” The quotes are deliberate since they aren’t variables inside the (programming) language, but instead variables at the next level up. It’s sometimes useful to call these “flex” variables to distinguish them from the conventional variables in the programming language—which we shall call “fixed” variables for obvious reasons. The point is that we look to refine (fill in) the values of the “flex” variables to see if two expressions can be made to look the same, possibly leaving some of the flex variables unsolved.

In the article, I’ll use a Prolog-style convention of starting the names of all flex variables with an uppercase letter, so X, X1, X_two, XYZ are all flex variables. In contrast, names with initial lowercase letters will be constants and fixed variables.

For example, are f(V1, g(x)) and f(y, g(V3)) unifiable? Yes, we can make them the same by changing the flex variables: in particular, replacing V1 with y and V3 with x, to get the unified expression as f(y, g(x)). We refer to the (flex) variable mapping as a substitution, and it is a mapping of (flex) variable to some sub-expression. When we apply the substitution to either of the input expressions, we will get back the same unified expression.

More formally, unification is a procedure for finding the most general unifier (MGU) for two expressions. The MGU, if it exists, is expressed as a substitution. The “most general” part is important: it means that it does the minimum work to make two expressions unify, imposing the smallest possible number of constraints. For example f(V1, V2) and f(V3, x) could be made identical with a substitution V1 => y, V3 => y, V2 => x, but this forces use of some (fixed) value y which could be a premature choice. The MGU here is V1 => V3, V2 => x, i.e. indicating that V1 and V3 should be the same something, but not constraining yet what that something is.

Finally, the flavor of unification covered here is the vanilla kind, called “first order unification”—which means flex variables can’t appear instead of function names, but only in place of function arguments. There are more powerful versions of unification, including various kinds of “higher order unification” where this restriction is relaxed in various ways, or kinds of unification under quantifiers (or binders), or kinds of unification which are interleaved with the computation mechanism of the language. I’ll leave you to read up on these if you are interested (but do check out Dale Miller’s work on “higher-order pattern unification” for a practical subset).

If you want to see the code from this article in full, in particular used as part of a simple resolution-based theorem prover, take a look at the github repo.

Basic Types: flex variables

Firstly, we need to represent the expressions to be unified. Let’s start with the flex variables. The underlying name will be a simple string, but we want to be careful how they are used, and attach some special functionality to them, so we use a common technique of wrapping the string up in a type of its own, just as we would encapsulate data inside a new class in Ruby.

data VarName = VarName String deriving Eq

We want VarName values to be equal when the underlying strings are equal, and Haskell’s deriving mechanism for type classes gives us this standard definition for free. For example, VarName "foo" == VarName "foo" will return True, but VarName "foo" == VarName "bar" will return False. Recall that == is overloaded via a Haskell “type class,” and the type checker selects the appropriate code to use based on the types involved. Next, we want to select how the overloaded show function behaves, but we don’t want the default version from deriving. So instead we explicitly declare this:

| instance Show VarName where
| show (VarName v) = v

Which basically says, to show a VarName value, grab the wrapped-up string with pattern-matching and just return that string. So, show (VarName "foo") will return "foo".

Note that wrapping the strings up gives us some freedom to change the underlying representation later, i.e., gives us some encapsulation and abstraction. To protect this, we’ll also use the following function to build flex vars instead of the bare constructor (so if the representation changes then only the implementation of this function needs to change, and not all of the places it is used).

| mk_var :: String -> VarName
| mk_var = VarName

Basic Types: Expressions

Next we need a tree-like type to represent expressions. The Term type is defined as follows, where each term has two possibilities: either it is a (flex) variable OR it is a fixed name applied to zero or more terms.

| data Term
| = Var VarName
| | Fn String [Term]
| deriving (Eq,Show)

Here are some example values in this type:

flex vars by themselves look like Var (mk_var "X1")

fixed vars and constants are represented as “function” symbols applied to zero arguments, so Fn "x" [] or Fn "true" []

a function f applied to a flex var and a constant looks like Fn "f" [Var (mk_var "X1"), Fn "zero" []]

nested function calls like f(g(zero), X1) correspond to nested uses of Fn, e.g., Fn "f" [Fn "g" [Fn "zero" []], Var (mk_var "X1")]

We use Haskell’s default definitions of equality and showing, but the show results aren’t easy to read (but are fine for checking intermediate results and for debugging). Instead, we’ll define a pretty-printer to produce more convenient output. Haskell has several libraries for defining pretty-printers, typically providing a type for documents and many utility functions for building documents in various combinations. Since pretty-printing is going to be useful for several types, let’s have an overloaded function for it by using a type class.

| class PrettyPrintable a where
| pp :: a -> Doc

This introduces a new class with a single “interface” function called pp which converts some value in a type into a Doc value. Flex var values need to be pretty-printable, so we define pp for VarName as follows, and it just wraps up the simple string form of the variable inside a document.

| instance PrettyPrintable VarName where
| pp v = text $ show v

Next, we can pretty-print expression trees by defining each of the cases. Var nodes just get their contents pretty-printed—and note the use of overloaded pp on the VarName value. Function nodes are handled in two cases: names with no arguments are shown as is, and names with one or more arguments are shown in the usual way, with commas before each additional argument. Notice that the call to pp in the Var case is going to run a different version of pp because it’s called on a value of a different type. Haskell’s type class system manages all of this for us, selecting the right piece of code to use, without any need for extra annotations. We can just write what we mean, i.e., “just pretty-print this thing” and be confident that the right code will run.

| instance PrettyPrintable Term where
| pp (Var v)
| = pp v
| pp (Fn n [])
| = text n
| pp (Fn n (t:ts))
| = text n
| <> char '('
| <> pp t
| <> hcat [char ',' <> pp t | t <- ts ]
| <> char ')'

The <> (cf Perl’s 'diamond' symbol) operator is provided by the pretty-printing library to join two document fragments together, and hcat joins a list of such fragments with <>. (Ok, this use of pretty-printing is a bit boring. The library also supports indenting, paragraph filling, line wrapping—all very useful in the full prover, but we don’t really need them here.)

An Important Operation: Collecting Variables

In various places we need to find out which flex variables appear in some value, be it a term or something more complex. It’s a notion we need in several places so a natural candidate for overloading again, hence we define another type class. A type can be in this type class if we provide a definition of vars_in for it.

| class ContainsVars t where
| vars_in :: t -> [VarName]

Next, the definition of vars_in for Term. The leaf case is easy: if the node has is a single Var then return the singleton list of the flex var we find. The branch case requires a bit more thought.

| instance ContainsVars Term where
| vars_in (Var v) = [v]
| vars_in (Fn _ ts) = -- ???

Intuitively, we want the variables in all of the argument subtrees and then join them together. However, we need to be careful here. Have you spotted my bit of sloppiness yet? Have I used an appropriate type for the result value? Not really. Tsk! I should really be using a set-like container type rather than a simple list. Lists allow duplicate elements (and quite rightly so), but for the way we’re going to use collections of variables, duplicates will mean useless extra checking and hence slower code. Something like a set type, including something like a Ruby hash, is a better match since variables would only appear once. Of course, representation here only affects efficiency and doesn’t affect the correctness of the code, but it’s a good reminder for us to always be on our guard and to use the type system to keep us honest...

Anyway, the point is, when we merge the results from two or more calls to vars_in, we need to remove duplicates. Let’s use a powerful feature of Haskell to encode this detail once and for all, and ensure consistent treatment. The code is this:

| import Data.List(union)
| instance ContainsVars a => ContainsVars [a] where
| vars_in xs = foldl union [] [ vars_in x | x <- xs ]

It literally says, a list of things can be in the ContainsVars type class if the base element already is; and the “constructive proof” (see last month’s article) of this is a definition of vars_in which produces the appropriate result by calling vars_in on each of the elements in the input list and then doing a big (set-style) union on the lists to remove duplicates. (FWIW I’m using foldl for technical reasons concerning how union works.)

This is quite powerful stuff! It allows us to call the overloaded function vars_in on a list of things, and we can be sure that the resulting value has no duplicates. The mechanism works recursively too, so vars_in [[[Var v ]]] (i.e., in a triply-nested list) will return [v] because the code above will be used three times to flatten the structure and flatten it in the right way. Few other languages provide this kind of powerful support.

Back to the code for Term though. With the general instance rule above, our code is nicely simple now. Just this!

| instance ContainsVars Term where
| vars_in (Var v) = [v]
| vars_in (Fn _ ts) = vars_in ts

Toward Substitutions

The traditional presentation of substitutions is something like a hash, storing an expression for each variable to be replaced. We’re going to be a bit more abstract, and use a type class to represent this abstraction. (Implementing an actual instance for this is left as an exercise.) What do we need from a substitution? Basically, a way to see if a given (flex) variable has a replacement term, and ways to build and combine substitutions. Any type being used as a substitution must therefore supply these four basic definitions:

| class ContainsVars s => Substitution s where
| lookup_var :: s -> VarName -> Maybe Term
| emptySubstitution :: s
| (+->) :: VarName -> Term -> s
| extend_with :: s -> s -> s

The type class has ContainsVars as a 'superclass', which means that all instances of the class must also be in the ContainsVars class. This is mainly to encode the idea that vars_in is useful in combination with substitutions, and frees us from saying that a substitution type also has vars_in defined for it; but (in other cases) the presence of a superclass can reflect an expectation that the parent class’s functionality is usually necessary in the child class’s instances, i.e., hard to define without it.

The lookup_var function takes a substitution value and a flex variable, and returns Nothing if the variable is not in the substitution, else returns some Just t if a term is found. Notice that the Maybe concept is a natural fit here: it says exactly what can happen, and avoids messy exceptions. It also forces calling code to handle both cases explicitly. A single substitution mapping is built with an infix operator +->, for example as mk_var "X" +-> Fn "foo" [Fn "y" []]. Bigger substitutions are formed from two smaller ones with extend_with, and emptySubstitution provides a 'zero' value.

Something’s still missing, of course, and that’s more detail about how the various functions interact, and what restrictions should apply. For example, we require a properties like lookup_var (s1 `extend_with` v +-> e) v == Just e, or emptySubstitution `extend_with` s2 == s2. Ideally we would prove these inside a system like Idris (see previous articles), but in Haskell that’s not really an option so instead we could try some QuickCheck property tests, or traditional tests, or even write down the proof in the comments. What about cases like v +-> Fn "f" [Var v]—is this valid?

For now—to save time and space—let’s just assume that the code does what we guess it does and that nasty things won’t happen. It’s not ideal, but the key thing is that you realize that some gaps are left and that you have some idea about ways to address the gaps!

Equipped with a notion of substitution, we can start to explain how to apply substitutions to various structures. Again, it’s an operation we want to overload, hence we use another type class. There’s a new detail here, of a member function’s type containing a class constraint: in this case, it means the code for apply may rely on its first argument implementing the above interface for substitutions, but it doesn’t—and need not— rely on a particular concrete implementation.

| class Substitutible t where
| apply :: Substitution s => s -> t -> t

Defining substitution for Term can be done by cases, again. When substituting on a flex var, we check to see if the var is in the substitution mapping and, if so, we return the replacement term. If not, we return the original term. For the branch case, we just apply the same substitution to all of the child terms. Similar to vars_in, we can deal with the case of apply over a list with a single rule (just map the substitution over the list) and hence shorten the branch case.

| instance Substitutible Term where
| apply ss (Var n) = case lookup_var ss n of
| Just t -> t
| Nothing -> Var n
| apply ss (Fn n ts) = Fn n (apply ss ts)
| instance Substitutible a => Substitutible [a] where
| apply ss = map (apply ss)

This is getting a bit abstract, so let’s end this section with a brief concrete example.

apply (mk_var "X" +-> Fn "y" []) (Fn "f" [Var (mk_var "X")]) will return Fn "f" [Fn "y" []] after traversing the tree and replacing the flex var X with the constant y.

Make sure you understand how the code above arrives at this result.

And So On to Unification

The groundwork is in place, so it’s time for the main attraction. We’ll be using unification on a pair of terms, but potentially the notion can apply to other structures so let’s overload the name. Cue a type class:

| class Substitutible t => Unifiable t where
| unify :: Substitution s => t -> t -> Maybe s

Slightly more complex than before, but let’s consider it a piece at a time. Firstly, it promises a function unify :: t -> t -> Maybe s, with a few additional constraints. Firstly, the result is Maybe s to represent the fact that unification can fail (with Nothing) or succeed (with Just x where x is the resulting MGU). There’s a constraint on the type of unify which requires it to return something that is a substitution, which means the result is at least relevant to the task in hand! There’s also a superclass constraint, which means we can only define unification on types which already can have a substitution applied to them. To sum up, this says we can define substitution on a pair of values when we know how to substitute over them, and the result should be usable as a substitution.

It’s probably not a surprise now that I want to define how to unify lists of things before we proceed to unify terms. Informally, two lists [a, b, c] and [a', b', c'] are unifiable if each pair of elements a, a', b, b', c, c' are all unifiable and there are no elements left over (i.e., the lists are the same length). However,the interesting part is that we want to propagate information from the first match into the rest of the matches, thus propagate the information that was learned from the first match so as to simplify or constrain the remaining matches. We also want to stop matching when one of the pairs fails, because there's no point in continuing. Let’s see the code now:

| instance Unifiable a => Unifiable [a] where
| unify [] [] = Just emptySubstitution
| unify [] _ = Nothing
| unify _ [] = Nothing
| unify (l:ls) (r:rs) = do s1 <- unify l r
| s2 <- unify (apply s1 ls) (apply s1 rs)
| return (s1 `extend_with` s2)

The first line says, we can unify lists of things if we can unify the individual things. The first case says that two empty lists match, and the substitution is the empty or 'zero' one. The next two lines catch the unequal lists cases, and both return the 'fail' result. (We could also test the length of the lists first, but I opted to keep the code simpler.) The final case is the interesting one. You can read the code as: do the first match on the two head elements and get substitution s1, then apply s1 to both of the remaining lists and try to unify the results to get another substitution s2, and finally return the combination of s1 and s2. Makes sense?

What about the failing cases, you ask? Well, that’s the joy of the monad pattern. Recall that this pattern allows us to pipeline computations together whilst hiding some of the plumbing. The error handling is the plumbing here, and if that’s hidden we are left with the key details of the algorithm, as if we did not need to handle the errors. It really helps, I hope you agree.

For the record, here’s the monad instance for Maybe. The key lines are marked. Line 2 says, if the first value in a sequence fails, then fail overall. Line 3 says, if the first value succeeded and produced a value, then pass this value to the next stage and continue. This precisely the boring and repetitive plumbing that we want to leave out of the main code.

| instance Monad Maybe where
| Nothing >>= k = Nothing -- line 2
| Just x >>= k = k x -- line 3
| return = Just

Now let’s consider terms. There are four cases to consider, namely the four combinations of var nodes and branch nodes. The first case (lines 1-3) is matching flex var to flex var: if the variables are the same, then succeed with no further substitution required, else substitute one for the other. (It doesn’t really matter which one is replaced in this kind of unification, as long as we replace consistently...)

The second and third cases, of a flex var vs a branch node, are mirror images and we can consider them together. The intuitive action is to substitute the var for the branch value, but we can’t do this unconditionally. The risk is that the flex variable might appear in the branch term, and this would lead to an infinite loop when applying the substitution (because we could effectively get substitution V1 +-> Fn "h" [Var V1]), so we first perform an “occurs-check,” test for the flex var appearing in the list of variables from the branch term, using the vars_in function defined earlier. If the check is True, then we can’t unify and so return Nothing. Otherwise, it’s safe to build the obvious substitution.

The final case compares two branch expressions. The function names must match exactly, hence return Nothing if they differ. Otherwise, we unify the lists of argument values. Happily, the Unifiable [a] instance above makes this easy.

| instance Unifiable Term where
| unify (Var l_v) r@(Var r_v) -- 1
| | l_v == r_v = return $ emptySubstitution -- 2
| | otherwise = return $ l_v +-> r -- 3
| unify (Var l_v) r@(Fn _ _) -- 4
| | l_v `elem` vars_in r = Nothing -- 5
| | otherwise = return $ l_v +-> r -- 6
| unify l@(Fn _ _) (Var r_v) -- 7
| | r_v `elem` vars_in l = Nothing -- 8
| | otherwise = return $ r_v +-> l -- 9
| unify (Fn l_n l_ts) (Fn r_n r_ts) -- 10
| | l_n /= r_n = Nothing -- 11
| | otherwise = unify l_ts r_ts -- 12

Closing Words

I hope you now understand how unification works, but there are several questions left unanswered, both about the general algorithm and the code I’ve presented. The over-arching one is, does either of them actually work? This question has several aspects:

will the algorithm always terminate (and not drop into an infinite loop)?

are there any missing cases?

is it really returning the most general result, as claimed?

will it always return the correct result?

I’m not going to attempt any answers this time. A good place to start looking for more information is a paper by McBride that uses the richer tools in dependent types to develop a version of unification where some of the key properties just drop out as consequences of the program passing the type checker.

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.

Puzzle

Puzzle In Puzzle

by Michael Swaine

A short session in mental calisthenics.

This month we present another Sudoku puzzle with a bonus anagram. Simply fill in the empty cells with the nine unique letters you’ll find in the the grid in such a way that each row, column, and small square contains each of the nine letters exactly once. Once you finish it, rearrage those nine letters in an order that doesn’t appear in the grid to reveal the secret word. Good luck!

U
G
X

X
N
X

M
X
X

C
X
X

G
X
X

X
X
T

X
X
O

P
M
X

U
X
X

X
X
G

X
X
X

X
O
X

X
X
U

X
X
X

P
X
X

X
P
X

X
X
X

M
X
X

X
X
N

X
C
P

I
X
X

T
X
X

X
X
G

X
X
C

X
X
U

X
T
X

X
G
P

And the word is: _ _ _ _ _ _ _ _ _ .

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

Puzzle Solution

The Missing Letter

by Michael Swaine

Herb Simon, polymath.

Here’s the solution to last month’s puzzle. You’re noticing the empty cells, right? They all represent the same letter, but since that letter didn’t appear in the puzzle grid, you could fill in any letter not already used. But to solve the second part of the puzzle, you need to pick the right letter. It turns out that if you fill in those empty slots with the letter M, you can rearrange the nine letters to spell HERBSIMON, i.e., Herb Simon, or as Wikipedia puts it, “one of the most influential social scientists of the 20th century.”

E
H
I

R
X
S

N
B
O

S
X
B

I
N
O

E
H
R

O
R
N

B
H
E

X
I
S

B
E
X

I
N
H

S
O
R

R
I
S

X
O
E

N
B
H

H
N
O

R
S
B

I
E
X

H
I
N

X
R
E

O
S
B

B
E
X

O
S
I

H
R
N

S
O
R

N
B
H

E
X
I

Calendar

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

2013-05-28, Fluent 2013

Flow Control with Promises: Learn to control async tasks in JavaScript with Promise-based interfaces.

Trevor Burnham (author of CoffeeScript and Async JavaScript )

2013-05-29, DevSum 2013, Stockholm

Change -- How long does it take?

Staffan Nöteberg (author of Pomodoro Technique Illustrated and Pomodoro Technique Illustrated (audio book) )

2013-06-03, Core Vim Masterclass, Online

Core Vim Masterclass

Drew Neil (author of Practical Vim )

2013-06-05, Software Architecture Summit, Berlin

Various topics related to Java and architecture

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-06-06, Agile Development Conference/Better Software, Las Vegas

Exploding Management Myths: Johanna will explain the management myths and what to do instead. She'll tackle favorites such as 100% utilization, no time for training, promoting the best technical person and more.

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

2013-06-10, Norwegian Developer Conference, Oslo, Norway

Three talks

Andrew Hunt (author of Practices of an Agile Developer and Pragmatic Thinking and Learning )

2013-06-10, Scaladays NYC

Using Akka and Scala in a custom Paxos implementation.

Michael Bevilacqua-Linn (author of Functional Programming Patterns in Scala and Clojure )

2013-06-12, QCon New York

"Well Behaved Web Apps in the Haute Societe of Native Apps"

Adrian Kosmaczewski

2013-06-12, NDC Oslo

Talks on various topics

Venkat Subramaniam

2013-06-14, Ruby Nation - Washington, DC

You Might "Are Gonna Need It" - Dealing with a MonoRail ahead of time

David Copeland (author of Build Awesome Command-Line Applications in Ruby )

2013-06-18, WordPress Lake County (IL) Meetup Group

Resumes and Job Interviews From Both Sides of the Desk

Andy Lester (author of Land the Tech Job You Love )

2013-06-23, SPA2013 London, UK

Case: study: Is eXtreme Programming still alive and kicking?

Rachel Davies (author of Agile Coaching )

2013-06-24, MADExpo, Hampton, VA

10 Habits of Highly Effective Senior Software Engineers

David Copeland

2013-06-24, MADExpo, Hampton, VA

Deliver Results, Not Promises

David Copeland

2013-07-01, Indianapolis CocoaHeads

TBA

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

2013-07-16, ÜberConf

Workshops and talks on various topics.

Venkat Subramaniam

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-25, OSCON, Portland

Getting Started with 3D Programming in Three.js (tutorial)

Chris Strom

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

Building Native iOS Apps With RubyMotion

Jonathan Penn

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

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

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, Barcelona Ruby Conference

Hexagonal rails

Matt Wynne

2013-09-14, Baruco

TBD

David Chelimsky (author of The RSpec Book )

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-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

At the end of 2012, there were 6.8 billion mobile subscriptions worldwide, including both smart and not-so-smart phones, according to the ITU; close to 70% of smartphones now run Android. But how much do you know about your Android phone or tablet?

Get under the hood and customize and automate your Android device in unique and interesting ways, from creating your own talking clock to sounding an alert when approaching geographic coordinates, with Mike Riley's latest book, Ultimate Android Power Tips: Make Your Mobile Work For You. Now available in beta.  

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^ | NEW | Crafting Rails 4 Applications
2^ | NEW | Programming Elixir
3v | 2 | Programming Ruby 1.9 & 2.0
4 | 4 | Agile Web Development with Rails 4
5v | 1 | Programming Erlang
6^ | 10 | Practical Vim
7v | 5 | The Definitive ANTLR 4 Reference
8^ | NEW | Learn to Program
9v | 8 | The Cucumber Book
10^ | 11 | The RSpec Book
11v | 3 | Test iOS Apps with UI Automation

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

The Phish Cheer

by John Shade

Phishing has John feeling like he’s living in a dream world—only it’s not his dream.

This is apparently not a new Google feature introduced at Google I/O:

“Proof of concept phishing attack with a fake browser window created with HTML/CSS/Javascript.”

Hurray. Research continues to advance the state of stealing your passwords.

Wikipedia tells us that phishing is “the act of attempting to acquire information such as usernames, passwords, and credit card details (and sometimes, indirectly, money) by masquerading as a trustworthy entity in an electronic communication.”

The people who track this sort of thing tell us that phishing is on the rise. And not just because of the tour.

Phishing is the only truly unsolvable problem in computer security. It exploits what will always be the weak link in electronic communication: humans.

OK, that’s not entirely true. It’s true enough that people are the weak link. But it’s not true that this weak link can’t be eliminated. True computer security can be achieved by eliminating the middle (man). Machine-to-machine communication eliminates sluggishness, ambiguity, and a host of other problems in eliminating the human element. Some problems just go away entirely when you take humans out of the equation. You don’t need laws against drunk driving or other unsafe driving practices, or traffic cops to enforce those laws or traffic court to decide cases, if cars drive themselves.

But as exciting as the prospect of phasing out humans is, it only goes so far. You probably can’t entirely remove the human from commerce or politics. There will continue to be some humans in cyberspace for the forseeable future.

And if you’re human, you can be phished.

Once you know you’ve been phished, though, the forensic phase begins. Or phorensic phase. And that’s a different game. Now the predator-prey relationship is flipped. Phlipped. It’s now about phinding the phisherman. And here we have decades of relevant data drawn from police procedurals. We know how conventional police find conventional crooks: the crooks brag to their friends. Or phriends. Who aren’t such good phriends. Because, duh, they are friends with crooks.

So the crooks have an equally unsolvable problem of security. Unsolvable for exactly the same reason, because they have to depend on exactly the same weak link: humans.

And we can see a familiar meta-game here. Each new advance on one side leads to advances on the other, in an ever-escalating cat-and-mouse game that produces ever more complex and clever cats and mice. (If you build a better mouse will the world beat a path to your door?) For the mouse, the goal is to keep from being noticed as long as possible. Because as long as the victim doesn’t know she’s a victim, the vicious meta-game of cat and mouse hasn’t even begun.

We begin to see where this is heading. In the Wikipedia phrase “masquerading as a trustworthy entity,” the word “entity” is a free variable. Really, phishing makes you think you’re somewhere you aren’t by faking an environment. Clearly, the phishing operations of the future will create ever-more complex and persistent fake, or phake, environments, keeping the victim in phishspace as long as possible, postponing the inevitable moment when the fakery is exposed and the hunt begins.

But does the fakery ever have to end? The internet is already being balkanized. Might it not come to include one or more phish domains, imitating the rest of the internet, bounded by invisible walls, keeping the victim inside?

Imagine a virtual world, created just for you, your own private and thoroughly convincing phishspace. If it never gave you reason to doubt it, you would move about in it as obliviously as you do in the “real” online world.

Thin tendrils could reach out to capture your email and facebook traffic, or, alternatively, any email or other connection could result in your contact being absorbed into the phishspace you’re in.

The difficulty (for the phisher) would come when your bank account became empty. If the phisher is doing all this to grab your money, then the game will end as soon as the bank in the real world notifies you that you’re broke.

So the phisher doesn’t make you broke. If he just syphons off a fraction of a cent here and there, like a bank cyber-embezzler, he ought to be able to keep the game going indefinitely. especially if he absorbs all your connections and all their connections, and taps all their bank accounts....

Eventually this would reach some sort of Borgesian superposition of inevitability and impossibility. Eventually, one of these phish worlds would succeed in swallowing the real world, and we’d find ourselves—without knowing it—living in a phuture where everything would be exactly as it is now except that some kajillionaire or group of kajillionaires would be sucking the blood of the world unnoticed.

And we wouldn’t be able to distinguish that world from the world we currently live in.

Crazy idea, I know.

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. Vide supra. Follow John on Twitter, send him your feedback, or discuss the article in the magazine forum.

Rear Window

A Parting Shot

From our album of computer history, the Electric Pencil. Photo courtesy of Paul Freiberger.

It was called Electric Pencil, and it was the first successful word processing program for personal computers. Retired camera operator Michael Shrayer had never even heard of word processing in 1976 when he created Electric Pencil. He just wanted a better way to produce the manuals for his software utilities than a typewriter. It seemed to him that he ought to be able to use his computer to write them. This was by no means an obvious decision. The computer in question was an Altair 8800, the first successful personal computer, and his model was tricked out with a few kilobytes of RAM and the necessary peripherals to let him type and save and print code. In other words, the state of the art in personal computing circa 1976. Shrayer was soon writing versions for almost every new computer created by every kitchen-table entrepreneur. As shown in the picture, The Pencil was still going strong in 1981, seen here running on a Radio Shack computer. That’s Shrayer himself in the snazzy 1981 shirt.