PragPub 2013-05: Issue #47

Table of Contents

Features

- A Functional Introduction to Lua
by Josh Chisholm
A lot of popular applications were written in Lua. Josh treats Lua as a functional language and makes some sparks fly.

- Dependent Types, Part II
by Paul Callaghan
Paul continues last month's discussion of dependent types.

- Java Active Objects
by Allen Holub
Allen does an end run around the JCP to give Java capabilities it’s missing.

- A Night at the Museum
by David Bunnell
Pioneers of personal computing gather for one amazing night at the Living Computer Museum.

- Launching a Gonzo Engineering Project
by Steven K. Roberts
The legendary gonzo engineer shares his secrets for pursuing crazy dreams and succeeding in this series.

Departments

- Up Front
by Michael Swaine
This month we talk code, careers, and computer history.

- Choice Bits
We follow Twitter so you don’t have to.

- Lester and Rothman
by Johanna Rothman and Andy Lester
If applying for a job is a test, do you need to show your work?

- Pub Quiz
by Michael Swaine
You only come into this pub for the games. Have at it.

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

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

- Shady Illuminations
by John Shade
John exposes the Blink Tag Conspiracy.

- Rear Window
Four personal computing pioneers: software, magazines, hardware, and hacking.

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

Functional Programming and Gonzo Engineering
by Michael Swaine
I’m an old Lisp hacker, so I’m prejudiced, but it sure seems like functional programming is where a lot of the action is today. That’s certainly true for this magazine. I’d say that this issue has a functional programming focus, but that would be a little misleading. Because every issue we publish these days has at least one article on functional programming topics.

You can use a functional approach in pretty much any language. Take Lua, for example, which is just what Josh Chisholm does in our lead article. It’s a good introduction to functional thinking and benefits, whether or not you know Lua. But the power of the functional approach is still being realized. Also in this issue, Paul Callaghan pushes functional programming to new levels with a deep discussion of dependent types. And Allen Holub is here with a proposal to extend Java to support safer concurrency. That’s not functional programming per se, but it’s related.

And there’s more. Have you ever thought about the pioneers of personal computing and wondered where are they now? The answer a few weeks ago was, they’re in Seattle at Paul Allen’s Living Computer Museum. Paul and Bill threw a big bash and invited an amazing list of computer pioneers to a night at the museum. David Bunnell was there and reports on the festivities. With lots of pictures.

And Gonzo Engineer Steven K. Roberts is back with the final installment in his series on how to pursue a crazy dream for fun and profit. Steven know what he’s talking about: he has made a career of this.

You’ll see a few little changes here and there in the magazine this month, and one big one: We’re introducing a new column by Johanna Rothman and Andy Lester. Johanna and Andy are going to be talking about the non-coding aspects of software development: getting hired, hiring good people, dealing with difficult people, and generally prospering and thriving in your work. Although they know a lot about these things—check out the books they’ve written—they aren’t going to lecture you and give you cookbook instructions. Rather, they’ll discuss the issues you face and let you see some of your options so that you can make informed decisions that fit your particular situation.

One other thing: We’ve been polling you on whether you’d be willing to pay something for PragPub. We’d love to keep giving the magazine away, but it’s just not sustainable. The answer seems to be, “Yes—something.” So we’re soon going to be asking you to pay a little something for PragPub. We’re still nailing down the details, and the system won’t be everything we want immediately. We’ll continue to tweak it based on your feedback. Because you’re the boss. Particularly if you’re paying us.

Choice Bits

Twitter Is About Sharing

We follow Twitter so you don’t have to.

We follow only the coolest people on Twitter. So when they share, we figure we should share what they share.

Twitter Is About Sharing Your Experiences

As I wiped a drive for Time Machine storage and named it "TARDIS," I half expected Disk Utility to say, "That the best you can come up with?" — @petdance

About to hand-convert a couple-dozen-page Sites thing to HTML. Maybe I should go to the dentist instead. — @timbray

The deeperI‪go in this rabbit hole, the less awesome firefox's portable profile story is.‬ — @adamgoucher

And now back to my rediscovering just how different OS X and iOS are. ‪#kvo‬ — @invalidname

OH: what, no, I don't use Maven, it uses me. — @venkat_s

Watching WarGames with the kids. Explaining esoteric things like modems, Mutual Assured Destruction, and the joy of terminal interfaces. — @hugs

Apparently the way to make a 9 year old's day is install a pokemon pack into his minecraft game. — @adamgoucher

I cast Monadic Amplify on my self and now I'm a lazy wizard. — @haacked

Anybody have plans to stare at their phone someplace exciting this weekend? (‪@thenardvark)‬ — @MrAlanCooper

I’m at a pub and ‪@dropbox are giving me free Heineken. I’m never leaving Dublin. ‪@ullconf‬‬ — @jdalrymple

It's a sign of a good party when you can't seem to leave. — @amyhoy

Twitter Is About Sharing Your Insights

Like Disneyworld, Twitter is a place to be avoided during the heat of the day. — @mims

"Our knowledge advances not when we have the best theory, or the best data, but when we have really good problems." ‪http://bit.ly/OiTNw4 ‬ — @jayrosen_nyu

@dhh The number of people feeding back “Btc is *sure* to go up” and “Btc is *sure* to go down” is hilarious. — @timbray

Pretty sure the bubble is primarily in "pieces about bitcoin" rather than the currency itself. — @mims

‪The hardest thing about learning is admitting that I don't already know. The "learner's posture" (humility) is step 1.‬ — @tottinge

‪The amazing paradox is that the same individual can be v sensible on most things yet believe in a winged horse.‬ — @RichardDawkins

‪Software is not an industrial process. There are NO economies of scale to be found in development. @kohai ‪@andytennant‬‬ — @MrAlanCooper

"Midnight oil is a fossil fuel... and you're going to run out of it." - ‪@bubs‬ — @amyhoy

‪"Info", "Data", ‬and‪ "Object" in class names are correctly pronounced "ummm."‬ — @KentBeck

Twitter Is About Sharing Deep Thoughts

But if we now experience Gentleman as farce, does that mean that Gangnam Style was tragedy? — @GreatDismal

Where did Noah the librarian put the bees? In the ark hives! — @petdance

‪A modest proposal: pharmaceutical labeling for open source: http://bit.ly/ZQMxOc‬ — @PragmaticAndy

‪Lean Startup Engineering Tag: if you're "it" and you catch someone engineering more than necessary to generate feedback, they're "it‬.‪"‬ — @KentBeck

irb(main):001:0> "diagnosis".pluralize => "diagnoses" Rails is awesome. — @jeffcohen

“Is anybody writing this down?” Author looks for the current tech scene's Bonfire of the Vanities: ‪http://bit.ly/ZZROTP  via ‪@sullydish‬‬ — @jayrosen_nyu

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: Chris Adamson, Kent Beck, Tim Bray, Chris Breen, Jeff Cohen, Alan Cooper, Jim Dalrymple, Richard Dawkins, William Gibson, AdamGoucher, Phil Haack, Amy Hoy, Jason Huggins, Andy Hunt, Andy Lester, Christopher Mims, Tim Ottinger, Mark Pesce, Jay Rosen, and Venkat Subramaniam.

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

Lester and Rothman

Do You Need a Portfolio?
by Johanna Rothman and Andy Lester
If applying for a job is a test, do you need to show your work?

Your current gig is not your job. Your job is to get great gigs—and to get the most out of the gigs you get. In this new column, we’ll be discussing topics ranging from hiring and getting hired to dealing with difficult people at work. And it will be a discussion. We have strong opinions on these issues—and sometimes we’ll disagree—but we don’t think you are best served by some expert prescribing a checklist of things to do. Most of the issues we’ll be talking about don’t have one-size-fits-all solutions. Our goal is to point out the issues, explore them together, share our insights, and get you thinking about them. Because the best solution for you is the one you discover.—Johanna and Andy

Andy: Johanna, so good to see you today. I wanted to talk about portfolios for techies, and their importance in the hiring process.

The first time I saw a really good portfolio, a fellow manager had come in with a portfolio from someone he’d just intereviewed. She was interviewing for a project manager position, and had brought in a three-ring binder with project plans, schedules, requirement documents, and all sorts of work products from her previous jobs. She wasn’t asked to bring it in. She just did.

Two things impressed me: One was that we could get a look at the quality of work that she did. The second, and almost more important, was that it told us that she wanted that job and put a lot of effort into making an impression. She got the job.

Johanna: Articulating the value of your work is what separates you from other candidates. And, it’s simple—although not easy—to articulate the value of your work.

It’s smart for hiring managers to ask for portfolios or examples of work. I don’t think I ever did that when I was interviewing for a project manager job! I did do that once for a specific developer job, but only because the hiring manager asked me in advance to bring work product. I had a work product I was allowed to show to other people.

That’s one of the most difficult things when you build your work portfolio. Being allowed to show the work. Because many of us are under non-disclosure.

What if I’m under an NDA?

Andy: When I talk about portfolios, either online or at conferences, it’s inevitable that someone will bring up non-disclosure agreements. “I can’t bring a portfolio! I’m under NDA!” and all I can answer is “I’m sorry to hear that. You can either make one up or you risk losing the next gig to someone who is able to show the value of his work.”

Johanna: When I help people write their articles for agileconnection.com, one of the things I help with is anonymizing their stories. That’s one of the things candidates have to learn when they build their portfolios.

Andy: How do you mean?

Johanna: Well, all of us have our stories of what we did in the organization. As a consultant, I’m under NDA, too. And, I need to be able to tell my stories about my successes, or I won’t have more clients either. So, when I explain my stories, or write my articles or blog posts, I say, “a recent client” or “Company X” or something like that. That’s what candidates have to do.

It’s the same thing with code and tests. You can’t bring the actual code or tests if you are under NDA. You can show the picture of the code or the tests. You can describe the system and what you and your team did. You can explain the effects and the value. It’s critical that you explain the starting point, what you did, and the ending point, and describe your contribution to business value.

Andy: That’s a bit of a frightening prospect, modifying code that I’d bring into an interview. I’d be afraid that I’d break something somehow.

Johanna : Well, if you’re under NDA, you can’t bring the code itself, can you? That code can’t leave the building. But you can bring a picture of the system. You can explain your effect, right?

Andy: It’s not just explicit NDAs, which I haven’t found to be terribly common outside of high-tech companies, but you need to consider your employer’s work as being under an implicit sort-of-NDA. You may have signed some company confidentiality agreement when you started working at your current company, so be sure to live by that.

What Should I Bring?

Andy: Topic shift: What sorts of work products should people bring in? Programmers ideally bring in code, of course. I suggest bringing both an electronic version, such as on a thumb drive or CD, and a printed copy so that you can discuss it easily at the interview. In both cases, you should be prepared to leave everything at the interview, never to get it back, so don’t bring your only copies, or a big fat thumb drive you’d hate to lose.

I also suggest that programmers not bring in a huge amount of code, only bringing their best work. No hiring manager is going to sift through megabytes of files or hundreds of pages of paper looking at the code.

Johanna: I like bringing in work products on paper, because they are easy to make copies of. Bring in a few pages of work product, say 2-6 pages, of your best examples. Point to the rest online, if at all possible. If you’ve been working for a while, you have a web presence, and your site might speak for itself.

Andy: What you absolutely do not want to do is say “My code is at my website at such-and-such url” and leave it to the hiring manager to go to the website and sift through the work herself. Guide her to the good stuff and don’t make her do the work. You want to make it as easy as possible for her to want to hire you.

For the same reasons, I say that your GitHub profile is not a portfolio, but it can be an adjunct to one. First, GitHub profiles usually have many projects, only some of which you’ve worked on, and you don’t want the hiring manager to have to figure out, or worse, guess at, what you’ve done. Second, you need to annotate your portfolio and explain “I did this on this project, and on that project I did such-and-such.”

Johanna: Right. You need to provide your interviewers enough on-site information so that they see what you can do and then if they like you, they can look online for more. You don’t need to overwhelm your interviewers with a Big Honking Binder. Just the fact that you have a portfolio might be enough to set you apart from the other candidates! And, you want to make sure you have the opportunity to provide your interviewers with a chance to review some of your work.

Andy: Guiding the hiring manager though the forest of your code is just another example of how you, as the candidate, have to do your best to make sure the hiring manager sees the good stuff.

Johanna: Remember, you also want to ask your interviewers questions. If they get caught up in reviewing your work, you might not have a chance to ask them questions. I like leaving them with my portfolio for review. I want to ask them questions in real-time.

Andy: Whenever I set up an interview with a candidate, I ask him or her “please bring in some printed samples of your code for us to discuss.” At least half the time, I get asked “What code should I bring in?” and that’s frustrating. I can only say “Your best work. I’ll leave that up to you.” What I don’t say is “and it would be nice if it related to the work that you would be doing here.”

If you’re applying for a job as a backend web developer working with MySQL and PHP, then it seems to me that the bulk of what you’d bring in would be related to web and/or MySQL and/or PHP, right? No one should have to ask that question.

Johanna: Well, it can be difficult for a candidate to know exactly what code to bring. Maybe I’m a softie, but I would cut the candidate a little slack here. I’ve certainly been in positions back in my developer days where I thought I was interviewing for one job, only to discover that the hiring manager changed his mind and it was a different job when I got there. I bet that happens to a lot of candidates these days, too. Just because you are consistent, doesn’t mean everyone else is!

I like the answer, “your best work.” That’s nice and open-ended. Candidates, bring several samples. That way, you’re covered.

Andy: Sure, but put a bit of thought into it, too. If the ad is looking for PHP and PostgreSQL, then bring in some PHP or a similar language and some code that shows you know your SQL. You want to bring things that show that you are able to do the things they need you to do. Sometimes people ask “Should I bring in the game I wrote?” and I think that’s OK, but it shouldn’t be the primary thing you bring in, unless of course you’re going to work for a game company.

How Can I Show My Other Skills?

Johanna: What should a Scrum Master bring? How do you bring evidence of facilitation? That’s a pretty hairy problem. It’s the same problem with project and program managers.

Andy: For that matter, what about sysadmins? Testers? Web designers?

Johanna: Testers can bring in bug reports! Well-written bug reports with some of the specific details blacked out—that would be great. I would love to see those. Test managers can bring in defect trends and other metrics they track and why they track them. I always want to know why people track data.

For project managers, Scrum Masters, manager types, I would ask them to bring impediment reports/obstacle reports and what happened. How did their teams improve over time? What did they do to faciltiate their teams’ improvements?

Andy: I’ve never heard of an impediment report. What’s that? I’m not Scrummy.

Johanna: I wrote about this in Manage Your Project Portfolio. One of the issues in an agile project, and even in non-agile projects, is that “things happen” in projects and programs. Great project managers and Scrum Masters manage risk lists and action items. They facilitate the work of the project teams. In Scrum they call it removing obstacles. So, in Manage Your Project Portfolio, I called it an obstacle report. It prevents you from getting work done, and it prevents the team from moving forward. In Manage It!, I called it an action item list. It doesn’t matter what you call it.

It matters that you have one, and that you work it. It matters that you have a way to facilitate the team. I want to know what that is.

Andy: So who gets these obstacle reports?

Johanna: If you’re the manager/sponsor, you see the obstacle report, because you remove the obstacles that the PM cannot remove. If I’m the hiring manager, I want to know what the project manager cannot remove. Or what the Scrum Master cannot remove. This goes directly to the kind of culture the candidate came from. I can then ask more questions about that culture, and learn about whether that person can fit into my culture.

See, the candidate’s portfolio really provides me with substantial insight as a hiring manager.

So, what would you look for from a sysadmin’s portfolio? Maybe uptime reports, or how he/she gets things from a queue, or something like that?

Andy: For a sysadmin, I’d like to see things that he’s done to improve his day-to-day life, or evidence of those things. Maybe screenshots from his Nagios monitoring system, or shell scripts he’s written to take care of simple monitoring that’s specific to his shop.

Johanna: I think sysadmins have scripts they bring from job to job.

Andy: I’d love it if I could see policy manuals that he’s written, but I realize that the chances of that are tiny. But just think about what an understanding of the sysadmin job it must take to write policies. They might be personal policies regulating use, or they might be operational policies. If he’s written a disaster recovery plan, that would be gold.

Johanna: Yes, and that is almost certainly covered under NDA. As a hiring manager, you NEVER ask someone to break NDA. That is unethical. You can ask someone to describe the disaster recovery plan. You can ask how long it took to write, and how many levels of approval, and all that. But you never ask someone to break NDA. That’s just wrong.

Andy: So if someone is under hard NDA, what can they do? For programmers, I explicitly tell them to either go work on some open-source project, or create a new project from scratch and open-source it. I usually get the complaint “That will take a long time!” to which I can only answer “Do you want to put yourself in front of the competition or not?”

Johanna: Or look for another company! Much of what programmers write is run-of-the-mill code. Very little really should be covered by NDA. But all of it is. If a programmer is unemployed, they should just start an open-source project on GitHub and show their stuff, or contribute to an open-source project.

If they have explained to their boss that they are looking for a job (and under many circumstances, they should), they should get permission to bring their code as part of their portfolio with them.

They can always bring a picture of the system and describe their part of the system, without showing the code. When I was a developer, that’s what I did. I brought pictures of the systems I worked on and described in detail how the systems worked and my parts in making them work. I was using assembler, FORTRAN, proprietary message-passing (pre-object oriented languages) and Lisp back then. I am an older programmer :-)

Andy: You know what else you can do to get an idea of how to build a portfolio? Talk to your graphic designer friends. Those guys know from portfolio building. Listen to one of them explain what goes into his portfolio and why, and see how it can apply to what you plan.

How Should I Present My Portfolio?

Andy: I want to get back to one other point: Portfolios are not standard. In Land The Tech Job You Love, I wrote that Ilya Talman, one of the top technical recruiters in Chicago, told me that he estimates only 15 percent of hiring managers ask to see samples of work. Does that number match your experience, Johanna?

Johanna: Yes. Very few hiring managers ask. I didn’t even put that into Hiring Geeks That Fit, because so few candidates know to build portfolios. It’s hard enough to hire great people. I didn’t want to make it more difficult! It’s a great way to make your candidacy stand out.

Andy: The beautiful thing about that is that having a portfolio of your work sets you apart from other candidates. I wonder if anyone reading this article has ever heard of someone bringing in a portfolio of work without being asked? Probably not. It will set you out from everyone else. Of course, it’s possible that the hiring manager won’t care. I suggest that the potential upside is huge, and the only downside is possibly spending time and a few dollars on a portfolio that isn’t looked at. No hiring manager is going to mark it against you that you brought in work.

How do you suggest that a candidate introduce the portfolio of work? At the interview? In correspondence before? How can he present it without sounding pushy or like he’s trying to take over the interview?

Johanna: You can say, “Hiring manager, I have a portfolio of my work in addition to my resume. When would you like to see it?” That’s a nice open-ended question that you can ask at the time you set up the in-person interview. Bring the portfolio with you, along with a paper copy of your resume. Always bring a paper copy of your resume. You never know what has happened to your resume. And, if you prepare the hiring manager that you are bringing your portfolio along with your resume, they may treat you differently from the beginning. They may allocate more time for your interview.

Andy: I suggest bringing at least five paper copies of your resume.

Johanna: I usually recommend at least one, but that’s because it’s generally easy for the company to make copies. Five paper copies means you’re not sure it’s easy for them to make copies.

Andy: Or I don’t want them to have to. It’s like business cards: Low cost for big simplicity when it’s necessary

Johanna: Absolutely. Make it easy for them to interview you.

Andy: The thing that candidates have to remember is why we advocate portfolios so strongly. The work products that candidates bring in are explicitly to back up the big talk in the interview. Anyone can say “Oh, sure, I’ve worked in Ruby on Rails before” but it means much more if I can see work she’s done with Rails. It also lets me see if the work she’s done is any good. Maybe she’s used Rails, but is doing it wrong. The hiring manager wants evidence one way or the other.

Johanna: Absolutely. I hope we’ve given our readers some inspiration next time they go out on an interview.

Next month we’ll be discussing managing your career over time.

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.

A Functional Introduction to Lua

Creating Some Fireworks with Lua
by Josh Chisholm
A lot of popular applications were written in Lua. Josh treats Lua as a functional language and makes some sparks fly.

If you write code in mainstream programming languages, you might never have heard of Lua. But I bet you've heard of Angry Birds, Wikipedia, or World of Warcraft. So what made their developers use Lua in those mainstream products? Perhaps it's because Lua is lightweight, cross-platform, embeds and extends well, performs well, has a small memory footprint, and a shallow learning curve. I'd like to believe some are attracted to Lua because it supports different paradigms and includes some pretty sweet functional programming capabilities.

You probably know some JavaScript. Although Lua has quite a different heritage, it shares many design ideas with JavaScript and feels similar. Syntactically, Lua is a bit less spiky:

function hello() {

say("Hi there, I'm JavaScript");

}

function hello()

say "Howdy, I'm Lua"

end

Just like JavaScript, Lua owes a lot to Scheme, a Lisp dialect. But because both JavaScript and Lua appear closer to Java and C, you wouldn't immediately recognize the Lisp underpinning either of them. Look beyond the syntax and Lua has some features that make it great for using functional techniques as part of a multi-paradigm approach.

First-Class and Higher-Order Functions

Saying functions are 'first-class' just implies there's nothing special about them, so they can be treated like any other value. A 'higher-order' function does at least one of two things: it either takes other functions as arguments, or it returns functions. These are important capabilities in functional languages, but they are missing or a bit funky in many mainstream languages.

Suppose we have a handy list of cats. We can use Lua's 'table' concept, a swiss-army style collection that behaves like both an array and a hash:

local cats = {

{ name = "meg", breed = "persian" },

{ name = "mog", breed = "siamese" }

}

A function that collects the names of all of our cats would look like this:

function namesOf (things)

local names = {}

for index, thing in pairs(things) do

names[index] = thing.name

end

return names

end

print(namesOf(cats)[1])   --> meg

print(namesOf(cats)[2])   --> mog

Lua uses 1-based indexes, which are easy to think about but can be easy to get wrong.

We could write a very similar breedsOf(cats) function, but we'd have to repeat the logic for iterating over the collection of things. We'd also use 'special-purpose' language syntax twice (for...in). Higher-order functions give us a uniform way of combining functions to reduce duplication:

function map (things, fn)

local mapped = {}

for index, thing in pairs(things) do

mapped[index] = fn(thing)

end

return mapped

end

function namesOf (things)

return map(things, function(thing)

return thing.name

end)

end

function breedsOf (things)

return map(things, function(thing)

return thing.breed

end)

end

print(namesOf(cats)[1])    --> meg

print(breedsOf(cats)[2])   --> siamese

Via this sort of reuse, functional programs tend to consist of lots of very small things.

Recursion

Recursive functions eventually call themselves, like this:

function factorial (n)

if n == 0 then

return 1

else

return n * factorial(n - 1)

end

end

print(factorial(5))   --> 120

Easy to follow, but executing this function for some values of n will result in a stack overflow error. That's because on each successive invocation of factorial(n - 1), the machine must retain a reference to the previous iteration on its stack. The stack is finite, so it eventually runs out of space and the program explodes:

print(factorial(-1))

lua: factorial.lua:5: stack overflow

stack traceback:

factorial.lua:5: in function 'factorial'

factorial.lua:5: in function 'factorial'

...

Lua 5.0 added 'proper tail calls,' a sort of functional goto that makes it possible to structure a recursive function such that it never runs out of stack space:

function factorial (n)

return factorialUntil(n, 1)

end

function factorialUntil (n, answer)

if n == 0 then

return answer

else

return factorialUntil(n - 1, n * answer)

end

end

print(factorial(-1)) --> Loops forever, but doesn't crash

Can you spot the difference? For a Lua function to benefit from tail call optimization its return value needs to call a function (often itself) and do nothing else. Expressions are allowed to appear in the arguments, as in return factorialUntil(n - 1, n * answer) because function arguments are evaluated immediately. But expressions such as return n * factorial(n - 1) cannot be optimized because the * is the last operation, instead of the recursive function call.

Functional Primitives

We had to define our own map() earlier, which we'll use again in a minute. Let's define a few more functional primitives that we can arrange into bigger and better things:

function each (things, fn)

for i, thing in ipairs(things) do

fn(thing)

end

end

function filter (things, fn)

local filtered = {}

each(things, function(thing)

if fn(thing) then

table.insert(filtered, thing)

end

end)

return filtered

end

function cons (things, ...)

local all = {}

each({...}, function(t)

table.insert(all, t)

end)

each(things, function(t)

table.insert(all, t)

end)

return all

end

I should point out that all of these are relatively slow, because they copy elements between Lua tables. We can guarantee immutability of these tables, so we could avoid copying and simply manipulate 'pointers' into a limited set of underlying tables. That's what proper functional languages like Haskell do by default. But I want to focus on functional semantics rather than performance, so we'll keep things simple.

Functional Flames

We're ready to tackle an actual problem that a typical Lua hacker might face. Lua is often used as a scripting language for games. These days games often include particle systems that generate organic-looking graphical effects. I've always wanted to build a particle emitter, so today I'm going to start a fire, functional style!

A functional particle system wouldn't retain mutable state, so it might be a function that accepts state (particles) as an argument and produces new state (new particles).

But before I can start writing my particle system, I need something capable of drawing. I was without my computer this weekend, so that gave me an excuse to use Codea, a cute little iPad Lua development environment with a drawing API.

The Codea runtime calls a draw() function in your code, once per frame. After drawing each particle, I'll mutate the flame to acquire a new state of the flame as a whole. This bit is necessarily imperative, so let's keep it short and sweet:

f = flame({}, 0)

function draw()

each(f.particles, function(p)

drawParticle(p.style)

end)

f = f.next()

end

As we shall see, f = f.next() is in fact the only example of mutable state we'll need.

Next, a drawing 'adapter' renders each particle as an ellipse in Codea's drawing API:

function drawParticle(style)

fill(style.red, style.green, style.blue, style.alpha)

ellipse(style.x, style.y, style.radius, style.radius)

end

So, what exactly is a 'flame'? In my model, a flame comprises of many particles, each of which 'evolves' over time to make a new flame:

function flame(particles, t)

local newParticles = evolve(particles, t)

return {

particles = newParticles,

next = function()

return flame(newParticles, t + 1)

end

}

end

Each particle changes style over time, taking a step function describing how it changes style over time:

function particle(step, style, t)

local newStyle = step(style, t)

return {

style = newStyle,

next = function()

return particle(step, newStyle, t + 1)

end

}

end

I've used one object-oriented detail here, by keeping state (or style) close to behavior that manipulates that state (the next function). But since I'm keeping clear of mutable state, I don't think the pure functional police can bust me.

My model describes a step in the evolution of the whole flame in three parts:

function evolve(particles, t)

return generate(mutate(prune(particles)), t)

end

Particles are generated at a point in time, then they repeatedly mutate until they die. Given a set of particles, we 'prune' any dead particles, 'mutate' each remaining particle, and 'generate' new particles to keep the flame alive. Each operation produces a new set of particles, the state of the flame as a whole:

function mutate(particles)

return map(particles, function(p)

return p.next()

end)

end

function prune(particles)

return filter(particles, function(p)

return p.style.alpha > 0

end)

end

Before we can generate particles, we have to describe what it means to be a particle in a flame. I'm sure there are established models for this, but I have a vague mental image of how I want my fire to look, so I'm going to make an approximation based on my fuzzy knowledge. In my eyes, flames seem to consist of upwardly moving particles that also move smoothly from side to side, change color, get smaller, and gradually disappear. So my spark particle is this somewhat random looking transformation of position, color, and size over time:

function spark(style, t)

return {

x      = style.x - math.sin(t * 0.5),

y      = style.y + 1,

red    = style.red   + (math.sin(t * style.seed) * 40),

green  = style.green + (math.sin(t * style.seed) * 33),

blue   = style.blue,

alpha  = (style.alpha - 5 * style.seed) * 0.97,

seed   = style.seed,

radius = 5 - t * 0.03

}

end

What are all these magic numbers? What's this 'seed' thing? These are just some dials I came up with to tweak the 'personality' of each spark and to give the overall flame a varied-but-consistent feel. The sparks I was fiddling with? Oh yes, those were generated by this last piece of my functional puzzle:

function generate(particles, t)

return cons(particles,

particle(spark, {

x = 0,

y = 0,

red = 255,

green = 40,

blue = 10,

alpha = 220,

seed = 0.3

}, 0),

particle(spark, {

x = 1,

y = 2,

red = 220,

green = 30,

blue = 10,

alpha = 180,

seed = 0.5

}, 1)

-- snip: lots more spark particles!

)

)

Several more particles and lots more knob twiddling later (omitted for brevity) and the outcome is something like the smooth flame animation I was daydreaming of:

The individual frames don't do it justice, so you'll have to imagine the upwardly, side-to-side movement and color progression as each particle burns and fades into nothingness. Or you can grab the code from github and fiddle with it in Codea or elsewhere.

Twiddle those knobs again, tweak the magic numbers, add different kinds of particles, and you'll generate a completely different effect. As it stands, this is about right for some jazzy looking torches in my new dungeon adventure game!

Josh Chisholm is a co-founder of Featurist, a software development consultancy based in London. He started programming because he wanted to write games. After over a decade of serious programming, he's just getting back to where his fun began. His first commercial game will hit a device near you, any day now. He occasionally tweets as @joshski but he regularly plays with code at github.com/featurist. Send the author your feedback or discuss the article in the magazine forum.

Dependent Types, Part II

Tests and Proofs
by Paul Callaghan
Paul continues last month's discussion of dependent types.

This month we continue looking at some core ideas in dependent types and the associated theory and technology, as we translate the Haskell word-wrap code from Issue 45, start to consider relevant tests and proofs, and discuss the details arising.

As we get deeper into the more powerful language features, it’s worth restating some of the key points of the style of programming advocated here. It should help to place the various new ideas in context.

First, strategic and deliberate use of types to help write better code. This includes a stronger description of what some code "does" with its inputs and outputs, and actively using type information to guide development—even using type information to fill in bits of the program for us, or better still, allow us to omit some of the routine details. (I’ve already highlighted some similarities between this way of using types and current ideas on TDD; see Issue 39. I’ve yet to see anyone use the information contained in test cases to automatically generate bits of code though!)

Another aspect is the willingness to introduce new types to help clarify code and ensure no details are left unconsidered. It’s important that new types can be added without much ceremony, and that existing types can be combined in various new ways and used consistently. Notice that this is almost diametrically opposed to ‘Stringly-typed’ programming and its close relatives!

Secondly, careful use of the language to highlight the ‘why’ of something working. For me, a program should tell a story and be clear about how it works. Although I appreciate the practical and economic reasons for getting the functionality in place before the aesthetics, it does make me slightly uncomfortable. One reason is that programs are not usually written to obey a collection of observations: there’s an underlying need to be met or problem to be solved, independent of the technology in use; an idea or goal that we can talk about and understand. I like to see that higher level thinking reflected in programs (and I like my technology to help reduce the gap between brain and program, as I tried to explain elsewhere).

In contrast, test cases are mainly a set of observations that we expect the program to obey, and such a set of observations is not the same as a coherent model. Compare this to how science progresses, from observations to models and laws which are then assessed against previous observations and against the predictions they make for new situations. We may hope that the test cases approximate some kind of model, but it’s still an approximation and doesn’t have the same strength as a model. For example, how are we sure that the test cases are consistent, that we’re not trying to get the program to do contradictory things?

Or sure that there are no important gaps? We could try further testing, but I suspect that most of you would start to check your tests against some kind of model in your minds of what the program should do. So even if you’re using tests, you still probably do have some model! Why not try to use that model more directly then, and get some leverage from it? What’s stopping you?

I don’t claim that this position is 100-percent perfect and all of the details have been worked out, and it’s unlikely that any language or paradigm will reach 100 percent (and that includes ‘graduate student’). But on reflection, I’d rather have a great language for 80 percent of my code with warts of varying (but manageable) complexity for the remainder, rather than an ‘okay’ language for 90 percent.

Translating the Code to Idris

As a first step, before we start playing with more advanced ideas, let’s see if we can get the word-wrap code running in Idris. Here’s the small test suite. Only minor changes are needed here, since Idris is pretty Haskell-like—and the changes are just in the type signature.

(Note: I’m using Idris version 0.9.7 for this article, same as for last month’s, though there have been a few useful changes to Idris since that article appeared. Let me know on the magazine forum if you have problems though.)

tests : (Nat -> String -> String) -> List Bool

tests wrap = [ wrap 1 ""   == ""

, wrap 1 "x"  == "x"

, wrap 1 "xx" == "x\nx"

, wrap 1 "xxx" == "x\nx\nx"

, wrap 1 "x x" == "x\nx"

, wrap 2 "x x" == "x\nx"

, wrap 3 "x xxxx" == "x\nxxx\nx"

]

At present, the type signature is not optional in Idris. This point is worth a few comments. Remember that type signatures are (mostly) optional in Haskell, and the exceptions occur when you’re using tricky combinations of type-class-based overloading? This is because most of the time, the Haskell implementation can infer the type automatically, though on occasion will need some hints on resolving the overloading. The same might be possible in Idris for relatively simple code. So why does the current implementation take a firmer line and require them everywhere?

Part of this is probably implementor convenience, though note that in this more type-orientated language we’ll be using type information in stronger ways so it’s mostly in our interest to play along and provide such type information. In comparison, Haskell’s type inference follows the traditional idea that you write some code and then see what the compiler makes of it. Computer says yes, or computer says no. But in our context, types are much more central to the activity of programming, much like the role of tests in TDD, and the system will use the additional information to guide the construction of the code.

Straying briefly into a theoretical distinction—but only to make sure I’ve properly got this point across—notice that type inference and type checking are not the same thing. The former takes some complete code and tries to work out its type, and it’s pretty much a bottom-up operation: we traverse the syntax tree and eventually return a type (or some error messages). Type checking could be implemented in a similar way, where the checking part compares an inferred type to the claimed type, but there are other options. One of these is to work top-down through the syntax tree, effectively propagating the constraints from the claimed type and onto the code itself.

Idris’ type checker is more in this style, particularly since it’s also used to ‘elaborate’ input syntax (i.e., raw code with implicit arguments and overloading) into the full, unambiguous internal abstract syntax. To sum up, Idris probably could drop the restriction in simple cases but it helps the machine (to help us) if we provide the type signature, and it helps us by early catching of errors.

Plus, type inference is starting to look a bit overrated and opinion is turning towards elaboration via type checking as the more powerful notion. Inference is a convenient feature to have, but it does place some annoying limits on various programming language features. For example, see how Scala and Haskell have to limit their implementation of ‘Generalized Algebraic Data Types’ (GADTs) to retain type inference. In contrast, languages like Idris—which use checking via elaboration—aren’t so constrained by type inference and so can support the full range of inductive families (which we will look at soon).

The switch of emphasis from inference to checking also mirrors what I mentioned above about stronger ways to use type information to guide program development.

Next change: instead of Int I’ve switched to Nat. We’ll be using Nat quite a bit so why not start now. The Nat type is defined like this.

data Nat = O | S Nat

It means, a natural number is zero (that’s a capital O) or the successor (S) of a natural number. If you ever did number theory, you might recognize these as part of the Peano axioms.

Notice that it automatically excludes negative numbers, and right away we have a win because using it will allow us to completely ignore the possibility of wrap being passed a nonsensical length value. (There are other ways to do this too, usually involving propositions, but this is the most direct way.)

Now, don’t worry, we’re not going to be doing heavy-duty arithmetic with this version of numbers. Instead, this type is going to be used to represent and check constraints, and this will only involve small amounts of computation. Plus: quite often these constraints will completely disappear in the compilation process and thus have little or no run-time cost!

The recursive nature of Nat is also important in related proofs, and we’ll be using it a few times here so it’s important to understand the details. Do you remember the proof by induction rule from school math? The statement of it, i.e., the proposition it represents, is this:

nat_ind : (P: Nat -> Type) -> P O ->

((x:Nat) -> P x -> P (S x)) -> (n:Nat) -> P n

So, given some property P, a proof that P holds for zero, and a proof that P x -> P (S x) for all x, then we can prove P holds for all non-negative numbers. Notice that there’s no upper limit to the available numbers, unlike Int etc., so when we say ‘for all’ we really do mean it. The proof of this rule is a simple recursive program, shown below. Notice how it works, e.g., when given a concrete number—say S (S (S O))—then its output is succ_case _ (succ_case _ (succ_case _ zero_case)),namely, it constructs a proof that P holds for that exact value. Curry-Howard in action again!

nat_ind P zero_case _         O     = zero_case

nat_ind P zero_case succ_case (S x)

= succ_case x (nat_ind P zero_case succ_case x)

This idea of proof by induction can be used with other types too. For example, the zero case for lists is for the empty list, and the successor (or step) case maps to consing an element onto a list. Induction on trees works in a similar way, e.g., simple cases for leaves and more complex cases for branching nodes. You may have realized that this pattern of induction is quite close to what you know about folding on such types! It is.

Finally, I use List Bool instead of [Bool] to avoid issues with the overloading of [ ... ] notation for lists and vectors. There’s other overloading afoot here too—Idris supports automatic casting from conventional numerals (1,2,3...) to equivalent Nat values so we don’t have to write S (S (S O)) for 3 etc.

Aside: Constructive Mathematics

I spoke above of uses of nat_ind constructing a proof for some proposition for some concrete value. This idea of constructing proofs from direct evidence is a powerful idea in mathematics, and has been studied for many years. See wikipedia for an introduction and for more detail see Constructive mathematics from Stanford’s encyclopedia of philosophy.

Constructive mathematics is distinguished from ‘classical mathematics,’ and a key difference is the view taken of the logical proposition A or not A, known as the Law of Excluded Middle (with the key section for us here.

So, do you accept that for some proposition P, e.g,. ‘the sky is blue,’ that it’s true that P is true or not-P is true? I.e, that ‘the sky is blue or the sky is not blue’ is true? Constructivists basically do not accept this as a rule of reasoning, and so do not accept any reasoning or proof that relies on it.

If you’re used to Boolean logic, then pause a while and think about this issue. Excluded middle does hold there (check the truth table, for example). But, Boolean logic is only one model of reality, and a simple one at that, and not always the one we need to use.

For added effect, choose some emotive statements—such as ‘bikes are cooler than cars’’and substitute them for P, and see what you feel about the result. (Also look to see how many times people try to apply this as a rule of logic in programming language discussions!)

Finally, take a look at Raymond Smullyan’s Drinker paradox. The proposition is ‘There is someone in the pub such that, if he is drinking, everyone in the pub is drinking, or more formally exists x . (D(x) larr forall y. D(y)) (read as ‘there’s an x such that: D(x) implies for all y then D(y)’).

Does this proposition make sense to you? Do you think it is true? It is an example of something provable in classical logic (by using excluded middle) but not true in constructive mathematics. Also note that this is the same kind of reasoning that allows classical mathematicians to conclude that some P holds for some X if they prove that not-P does not hold for all Y (informally: that something exists if it is not impossible...). In contrast, a constructivist proof would be a program that constructed something that exhibited the required properties, ie. tells you how to do it. Do you see the difference?

Translating the Word Splitting

The first attempt is below, adding some basic definitions that aren’t in the Idris basic library (or Prelude) at present, and adjusting the types.

null : List a -> Bool

null []     = True

null (_::_) = False

iterate : (a -> a) -> a -> List a

iterate f a = a :: iterate f (f a)

splitIntoSize : Nat -> List a -> List (List a)

splitIntoSize n

= map (take n)

. takeWhile (not . null)

. iterate (drop n)

But now we run into another important issue: totality. There are several aspects to this, but for now, the point is that we’re not sure that the above code terminates. Informally, termination means that it always produces an output in finite time for all inputs, and does not crash or go into an infinite loop.

Totality (and termination) is important in dependent type systems because it’s a key requirement for using code inside types. If the code crashes or loops, then the type checker might crash or loop. If we’re wanting to view types as propositions and programs as proofs, and wanting to rely on the results, then we obviously do not want crashes or infinite loops!

As a concrete example, say we change nat_ind from above to the following incorrect version, where the recursive call is applied to (S x) instead of x and the zero case is removed.

Happily, it won’t even type check (the result of the recursive call doesn’t match what is expected)—which is great, because it shows how the more detailed types already save us from such mistakes. But suppose it did pass type checking, then what would happen when the code was used? It would be an infinite loop, because the recursion would never terminate. If we repaired the argument on the recursive call, then the code would crash because there’s no clause to handle the zero case.

Clearly, we couldn’t trust any proof that used that code.

nat_ind P zero_case succ_case (S x) =

succ_case x (nat_ind P zero_case succ_case (S x))

See the section 8.5 of the Idris tutorial for more information about Idris’ totality checking. Notice the remarks on totality checking being ‘conservative,’ in the sense of maybe disallowing some fairly reasonable code rather than risk allowing non-total code to be passed. If some definition is rejected, we just need to be more explicit about why it is safe. (We’ll see some ways of doing this when we get to inductive families.)

I will be using the %default total global directive in the code for this article to require that all of the code passes the totality check. It’s probably wise to aim for most code to pass the totality checks because it is a good check on code being ‘sensible.’ Most of our code should terminate, exceptions being things like event loops or tricks with laziness, so it’s good to have this confirmed and thus remove one source of potential bugs. It’s also useful to know that our code handles all relevant cases and doesn’t miss anything, hence addressing another source of potential bugs.

Maybe Idris should even have %default total as the default mode? Not all code will be total, so Idris provides various options to accommodate exceptions, such as directives on individual functions. We’ll see some of these later.

One other detail to be aware of: the Idris compiler is designed to handle non-lazy code, so basically, some non-total definitions can cause the run-time stack to overflow. Be careful though: the current version of the REPL’s evaluation mechanism supports some laziness, so some examples that work in the REPL might crash when compiled.

You can avoid surprises by requiring totality by default in all definitions, and carefully choose whether you allow a tricky definition to be excepted from this. Non-total code can also crash due to unimplemented cases.

In the above code, the question mark of totality hangs over the iterate function. Clearly, it does not terminate—it is intended to generate a potentially infinite list. It’s kind of safe in a lazy context because we only generate as much as we need and tend not to let it run unchecked, e.g., we tend not to try to take the length of the list of results produced by iterate, but the risk is still there of doing this accidentally or indirectly. We can’t take that risk if proofs depend on it, hence we need something more. How do we isolate why it is ok in this situation, and convey that to the machine? What would make it safe?

One way is to recognize that the recursion in iterate isn’t the nice, well-behaved recursion we enjoy with lists, trees etc., and adjust how we approach the question of totality. That is, the reason for ‘why’ it is safe (in certain circumstances) is not the same. Technically, iterate uses the "dual" notion of vanilla recursion, which is often called co-recursion, and instead of generating simple data (i.e., finite), the potentially infinite value is described as ‘co-data.’

Idris has some experimental support for co-data, e.g., see Release 0.9.5.

But we’re not going to explore that avenue now! Instead, here’s another technique that sometimes comes in handy: we add some kind of measure to the definition so that the pattern of recursion turns into a well-behaved version. The measure acts like a counter that says how many times we can (or should) need to iterate; hence prevents us from unbounded recursion. The basic function is this, and it passes the totality checker.

bounded_iterate : Nat -> (a -> a) -> a -> List a

bounded_iterate (S n) f a = a :: bounded_iterate n f (f a)

bounded_iterate Z     _ a = []

For the case above, where (drop n) is the thing we want to apply repeatedly on a list (assuming n > 0), then one good measure is how many items are in the list. Since drop n (where n > 0) cuts at least one element off if the list is non-empty, then we’ll at most have as many steps as there are elements in the list. (You could improve this by using the list length divided by n plus 1 for any left-overs, if you want, but it doesn’t change the result.)

Let’s make the use of a measure more explicit, and revise the code. It passes the totality checks, and we can test it in the REPL with expressions like print $ splitIntoSize 4 [1..101]. (It won’t print directly in Idris 0.9.7 but will show you which calls to the FFI it should make....)

hacky_iterate : (a -> Nat) -> (a -> a) -> a -> List a

hacky_iterate measure f x = bounded_iterate (measure x) f x

splitIntoSize : Nat -> List a -> List (List a)

splitIntoSize n s

= map (take n)

$ takeWhile (not . null)

$ hacky_iterate length (drop n)

$ s

Now, what happens if we try a split size of 0? I’ll leave you to find out. But notice that there was nothing to prevent our doing this, and indeed, nothing to guarantee that our measure function (just length) was sufficient to produce a correct answer, with or without a sensible value for n. We need something else, and indeed have several sensible options to try. Do not for a minute assume that this is just how stuff is, and that we have to put up with such gaps!

A First Stab at Proofs

One way to get more confidence in the results is to write down a few test cases and check that the results are what we expect.

We could also adapt the QuickCheck framework to Idris. QuickCheck is a library for property-based testing, where you can state properties to test and the library runs the properties on many different inputs. This helps you to explore properties of your code, and also helps to find counter-examples for properties that don’t hold—which could be due to bugs in your code or properties that can’t be satisfied—or both.

With excellent timing, @jessitron has just published a good introduction to the key ideas and how they relate to example-based testing.

For more detail, see the relevant chapter of Real World Haskell and research papers on integrating QuickCheck into Agda (another dependently typed language and proof assistant).

Interestingly, some people like to use QuickCheck to ‘debug’ proofs as well, in the sense of working towards a good statement of some desired property by eliminating versions for which QuickCheck finds counter-examples, and they only start to do serious work to prove a theorem when they have reached a point where QuickCheck fails to falsify it.

Better still, if we want more certainty, we can try some proofs. There are many ways to approach this, and many properties we might want to explore. We’ve already proved one theorem of course, via the type checker, that splitIntoSize n turns a list of things into a list of lists of the same thing.

Here’s a simple property about length, that splitIntoSize n l yields a list of lists where the longest fragment (or sublist) is not longer than the limit n. More formally the proposition is, for all limits n and all lists l, then the maximum length of a fragment is less than or equal to n. I’ll postpone the details of how we represent and reason about inequalities, but here’s the statement of the proposition with some auxiliary definitions (maximum value in a list, then maximum length of sublists in a list).

maxList : (Ord a) => a -> List a -> a

maxList z = foldr max z

maxLength : List (List a) -> Nat

maxLength xs = maxList 0 (List.map List.length xs)

-- the proposition...

ok_split : (n:Nat) -> (l:List a) ->

LTE (maxLength $ splitIntoSize n l) n

How to prove something like this? I’m not sure whether we can (I’ve not tried), and we may yet need to exclude the n == O case.

Typically, we’d try induction on the limit n to see if it falls out easily, or maybe try induction on the input list instead. Either way, we’ll end up trying to prove a step case by pushing constraints around and maybe proving smaller results about how maxLength works on non-empty lists. We might also have to prove some simpler things about splitIntoSize first.

That sounds a bit too much like hard work though, and it probably is. I wouldn’t like to have to do it either (and I never fancied the traditional ‘formal methods’ taught in universities either, for much the same reasons).

Can we do better though? I think so. In some sense, the proof above is trying to establish something complex about code written in a (relatively!) traditional way, like with boring types. You might call it an attempt to retrofit some justification onto existing code, which just sounds like it’s not going to end well (the "tests first" people have a good point here!)

One of the pioneers of dependently typed programming, Conor McBride, has a great phrase that covers this retrofitting: ‘It’s like trying to fit toothpaste back in the tube.’

One Way Forward

The suggested answer to this mismatch is to build more of the understanding of ‘why it works’ into the program, using a richer type system to convey some of that information—plus we’ll use advanced tools like proof assistants to help deal with the extra layer of detail.

It’s time to wind up this article, so little space left except to give a quick peek at next month’s content. We’ll start to look at Inductive Families, a generalization of simple data types that allow us to embed data and logic in the types, and look at how they change the style of programming.

The presence of extra information in the types will make it easier to reason about certain properties (compared to the more indirect style required by the naive approach above), but also help to simplify the code by eliminating redundant cases and filling in the obvious things.

Quite a bit of the word-wrap code deals with limits on sizes, so it’s natural to want our word fragments to carry some size information. Hence we’ll make extensive use of vectors (or sized lists). Vectors are defined in the Idris Prelude like this:

data Vect : Type -> Nat -> Type where

Nil  : Vect a O

(::) : a -> Vect a n -> Vect a (S n)

Basically, it says Vect A n is a type, where A is the type of the payload data and n the length of the vector; then Nil constructs a vector of size zero, and (::) (i.e., vector cons) adds an element onto a vector of size n to give a vector of size S n (or 1 + n). We’re using Nat for sizes again, firstly because we don’t want negative sizes, but we do want arbitrary non-negative numbers—plus we want the inductive structure of Nat for use in various proofs.

I’ll leave you with a simple but very important definition, of taking the head or first element of a vector, similar to Haskell’s head or Lisp’s car. In functional languages, head [] fills much the same role as nil pointer exceptions (NPEs) in other languages.

(If a functional programmer gives you grief about NPE’s and why you don’t use option types like Maybe in your language, feel free to ask them about head []. It might be fun, unless they’ve already learned a bit of dependent types.)

We could get head to return a value in an option type, but this is a bit cumbersome. Wouldn’t it be better if we knew it was never actually called on input that was empty? And didn’t require any run-time checks either? This is quite straightforward with dependent types. We just define head on a sized vector as follows. The type says it can only work if the size is non-zero (literally, of size 1 + n for any n), and always returns a value of the payload type. Totality isn’t a problem either: there’s no Nil case, but the type constraint means that a Nil is never required (and indeed, just can’t occur), hence the definition is total as it stands.

So there you go: a fully safe head function! And this is only the beginning.

head : Vect a (S n) -> a

head (x::xs) = x

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.

Java Active Objects

A Proposal
by Allen Holub
Allen does an end run around the JCP to give Java capabilities it’s missing.

Multithreading is not for the faint of heart. Nevertheless, it's an essential part of server-side Java programming. The java.util.concurrent package went a long way to making multithreaded programs possible, but it didn't really solve the core problem: multithreaded programs are still way too complex, almost impossible to debug, and require you to have a deep knowledge of both multithreading theory and practice. Things don't have to be that difficult, however.

It turns out that one of the best solutions to the problem—one that's actually easy to do, without any of the complexity of a typical multithreaded system—is an architectural one. The design pattern in question is Active Object. The term was coined by Doug Schmidt in the mid nineties (for the ACE cross-platform threading framework), but the concept itself has been around much longer. In fact, it's built into many languages, ranging from Ada tasks (circa 1980) to Scala actors. The first time I saw the pattern was in Intel's Real-time Multitasking Executive embedded operating system (RMX), which also used the term "task." I'll use the word task as well.

A task, then, is an object that performs some sort of work for you asynchronously in the background. You ask it to do the work, and eventually, it does it. Many, if not most, multithreaded systems can be thought of in terms of tasks. For example, instead of executing a SQL query on a "worker thread," with all the concomitant synchronization problems, you can ask the database-update task to do the work for you in the background. If you care, the task can tell you when the work completes (or you can wait for it to complete). Tasks can talk to each other and, in fact, an entire program can be written as a set of cooperating tasks (that's what RMX did). This is a very different way of programming than many of us are used to, but it works well, and is way easier to program than standard solutions once you get used to it.

This article, then, is a modest proposal to add tasks to Java by means of annotations. An annotation-based solution is not optimal, since a few features would be better done by the compiler itself, but it's doable without having to convince Oracle to make changes to the language (which can take many years), and can be done as a simple open-source project without the Machiavellian political machinations of the JCP. This is very much a work in progress, and I'm sure I've missed whole swaths of issues, so I'd very much appreciate any comments and suggestions you may have; send me an email at jao@holub.com. I'll summarize the comments and post them to a JAO page on my website.

I've already implemented enough of an annotation-based task framework that I'm convinced it's workable, but I want some feedback before I proceed, which is my main motivation for writing about it here. I'm very interested in your comments. Once I've incorporated these, I'll actually open up the project for you to use. Again, send me an email and I'll tell you when/where to find the full implementation when it's available.

Also, as a heads up, I'm assuming in this article that you know a little about multithreading in general, java.util.concurrent in particular, and that you're at least superficially aware of the lambda-Expression extensions that will be part of Java 8. For the latter, pick up a beta copy of Venkat Subramaniam's Functional Programming in Java from the Pragmatic Bookshelf. You'll need to know this stuff anyway, and there's no time like the present to come up to speed.

Tasks

The best way to understand how to implement a task using Active Object is to look at one.

First, consider this class:

class NormalClass

{

private double val = 0.0;

//

void doSomething()

{   val = 1.0;

}

//

void doSomethingElse()

{   val = 2.0;

}

}

The class is dangerous in a multithreading scenario because both methods can be called simultaneously, so the value of val (which is not atomic—it's updated in multiple steps) could be undefined—a classic race condition. You can, of course, use synchronization to solve this problem, which in this trivial case is easy. But once the class becomes realistically complex, synchronization can become very difficult.

Now let's do the earlier work using an Active-Object-based Task:

public class MyTask

{

private double val = 0.0;

private BlockingQueue<Runnable> dispatchQueue

= new LinkedBlockingQueue<Runnable>();

//

public MyTask()

{

new Thread(

new Runnable()

{   @Override public void run()

{   while(true)

{   try

{   dispatchQueue.take().run();

}

catch (InterruptedException e)

{   // okay, just terminate the dispatcher

}

}

}

}

).start();

}

//

void doSomething() throws InterruptedException

{   dispatchQueue.put(

new Runnable()

{   public void run(){ val = 1.0; };

}

);

}

//

void doSomethingElse() throws InterruptedException

{   dispatchQueue.put(

new Runnable()

{   public void run(){ val = 2.0; };

}

);

}

}

Or, if you're using Java 8, you can simplify considerably using lambda expressions. The following code works just like the previous example (and I'll continue to use the lambda syntax from here on out):

public class MyTask

{

private double val = 0.0;

private BlockingQueue<Runnable> dispatchQueue =

new LinkedBlockingQueue<Runnable>();

//

public MyTask()

{

new Thread( ()->

{   while(true)

{   try

{   dispatchQueue.take().run();

}

catch (InterruptedException e)

{   // okay, just terminate the dispatcher

}

}

}

).start();

}

//

void doSomething() throws InterruptedException

{   dispatchQueue.put( ()->{ val = 1.0; } );

}

//

void doSomethingElse() throws InterruptedException

{   dispatchQueue.put( ()->{ val = 2.0; } );

}

}

The main issue, here, is that the Active-Object version is fully thread safe. No synchronization is required. You can program within the class as if the application were single-threaded.

The core of the Active Object pattern is a BlockingQueue and a single "dispatcher" thread. A blocking queue has two essential properties: (1) It's thread safe—multiple threads can enqueue concurrently, and (2) a dequeueing thread blocks until (waits for) an object to become available on the queue. The single dispatcher thread is idle until somebody enqueues a Runnable() object, at which time the thread dequeues the object, executes it, then goes back to waiting for the next request.

An Active Object, then, is effectively single threaded, even though it's used in a concurrent environment. Active Objects are concurrent relative to each other, but within the object, it's as if everything is single threaded. As a consequence, Active Objects can be written without worrying about threading issues, and so are much simpler.

The whole point of the exercise is the one I mentioned a few sentences back. There's absolutely no need for synchronization here (beyond the implicit synchronization in the BlockingQueue, of course.) Even if doSomething() and doSomethingElse() are called concurrently, the actual work (the assignments to val) are done serially by the dispatch thread, not concurrently.

In the Real World

Of course, in the real world, it's not that easy.

Active Objects assume that none of the objects that they use change unexpectedly, and that assurance can be tricky to get when you don't have the compiler helping you. For one thing, objects can come from outside (as method arguments, for example). Similarly, if you ever return a reference to an internal object, then another thread could be modifying that object while the Active Object uses it. Since the Active Object isn't synchronizing, this concurrent modification is a very real problem.

The best solution is to be very hard core when it comes to object orientation: In a pure OO system, objects are intelligent agents that do work for you in an opaque way. You make requests, the object does the work, and it gives you a response. You have no idea how it does its work.

A properly done object has to be rigid about basic principles like data encapsulation and implementation hiding. That is, it should simply not be possible to discover or impact how an object works from the outside. I think of it as using a rule I've epononymously dubbed the Holub Replacement Principle: it should be possible to completely discard the implementation of a class (all method bodies, all fields, everything), replace the old implementation with a new one, and, as long as the interface hasn't changed, the class's clients—the set of objects that use the class—shouldn't notice. Well-structured objects like that are vastly easier to maintain than typical Java classes, which leak implementation details all over the place. For example, I've written extensively about how accessors and mutators (get/set functions) hurt maintainability, and they do that because they violate encapsulation. For example, if during the normal course of maintenance, you need to get rid of, or change the type of, or add an ancillary field to a field that's exposed using accessors, you're in deep trouble. Every call to the accessor is now broken. You can't fix this problem with an automated refactor.

Designing systems that don't have things like get/set methods in them is both possible and easy, once you get the hang of it (which, admittedly, can take some training), but at the core is the notion of delegation: ask for help, not for information. Put another way: don't ask some object for the information you need to do your work; rather, ask the object that has the information to do the work for you.

Which brings us back to tasks: A Task is an object that does something for you. It does that something in the background at its own pace, and can notify you when the work is done. You talk to it asynchronously (you make a request, but you don't get an immediate response, and typically don't wait for the response). Threads, then, are implicit in the notion of tasks, since a task typically does its work on a background thread.

When it comes to Tasks, this sort of hard-core encapsulation moves from a nice-to-have to a necessity. If you violate the encapsulation, the now-accessible internal fields become simultaneously accessible by multiple threads, and the whole design pattern breaks down and fails.

Looking back at the earlier example, if val were public, or if there was a getVal() and setVal() that accessed it, then we'd have absolutely no advantage in using the Active-Object pattern. That is, if a thread other than the dispatcher thread can access the local field, then we have to synchronize in the normal way. The whole point of the exercise is to eliminate the need for synchronization, however. Hard-core encapsulation is mandatory.

So, when possible, we want the compiler to enforce the rules for us. If we modified Java to force us to use good OO structure, we wouldn't be programming in Java anymore. However, we can use the annotation preprocessor to identify Active Object-based tasks and identify (or prohibit) coding problems that would break the Active Object.

Let the Compiler Do the Work For Us: A Basic @Task

Let's look at how that annotation processor works.

There are two problems with manually implementing Active Object: (1) It's annoying to do the boilerplate work of setting up the dispatch mechanism, and (2) it's difficult to guarantee that the active object is actually safe to use—there are no [*** Delete 'no'? ***] problems like unwanted external access to what should be guarded fields, for example. Both of these problems can be solved by adding a handful of annotations to the compiler, and then using a mix of compile-time validation and automatically injected code to make everything work transparently. The new(ish) annotation APIs make this process relatively easy.

Let's start with a task definition (Listing 1). A task is specified with the @Task annotation preceding the class definition. This annotation causes several things to happen. First of all, the annotation processor generates a subclass that does the following:

1. The subclass contains a dispatcher equivalent to the BlockingQueue and associated thread in the earlier example.

2. The subclass constructor takes care of creating and starting that dispatcher thread. This thread dequeues requests and executes them.

3. The subclass provides overrides for every public method of the superclass. The overrides create the equivalent of the Runnable objects in the previous example. Each of these Runnables calls the equivalent superclass method and then handles return-value processing. The subclass overrides enqueue the Runnable objects on the dispatch queue.

In addition, the annotation preprocessor guarantees that certain conditions hold in the superclass (and prints an error message if the class isn't valid):

1. There are no protected fields. A protected field can be modified without synchronization by a subclass, so it isn't safe. protected methods are safe only because protected fields are not permitted.

2. There are no public fields that are not also static and if they're references, reference "read-only" objects. Since a public field can be modified by a thread other than the dispatch thread, it just isn't safe to expose it unless it's read-only. A read-only field either holds a primitive-type value, or it's a reference to an immutable object. By "immutable" I mean that all fields of the referenced object are either final instances of basic types or final references to classes. The rule is applied recursively to all referenced objects. String and Number objects are immutable, for example. If immutability can't be guaranteed at compile time (if the field is an interface reference, for example), then the generated subclass's constructor checks for immutability at run time.

3. There are no public final or static methods. A static method could be called by another thread, and could access other static fields that might be used by the dispatch thread. Public final fields are prohibited because Java's annotation mechanism doesn't let us modify existing classes—everything has to be done by overriding methods. You can't override a final method, though. That's why rules like this also exist in annotation-based frameworks like Mockito.

4. The Task class itself may not be final for the reason I just mentioned.

5. No Task can access the private or protected fields of another Task, even if they're instances of the same class. Think of private as object-level, not class-level, privacy.

6. A method may return a local variable, a synthesized value, or a read-only field, only. Code is generated in every subclass override that enforces this rule. If you need to return the value of a modifiable field, return a copy. This isn't a bomb-proof test because a badly written method could insert a non-read-only field into a third object and return that third object, but it's better than nothing. I may add code that recursively checks all the fields of all returned objects, but that's quite a bit of runtime overhead. I'd be interested in your comments on this one. It's okay to return "unmodifiable" versions of the standard Collection classes, as are generated by various Collections-class methods.

7. Method arguments must be primitive types or references to read-only objects. This rule is also enforced at runtime if it can't be verified at compile time. It's okay to pass "unmodifiable" versions of the standard Collection classes, though this exception is risky because it's possible to modify the wrapped collection after it's been wrapped.

8. Method arguments may be assigned to fields only if they're read-only. Code is generated in every subclass override to enforce this rule. If you need to preserve a non-read-only-argument's value between calls, store a copy.

Essentially, all these rules are attempting to ensure that no objects used by the Task are modifiable by other threads. The rules aren't perfect—we'd really need to modify the language itself to handle every case—but they find the majority of problems.

In terms of programming, you don't need to worry about synchronization at all. You'll never use the synchronized keyword or the java.util.Concurrent classes. Just program as if the Task were single-threaded.

1 @Task

2 class MyTask    // may not extend anything

3 {

4     private method(){...};  // is okay

5

6     public int getX()

7     {   return x;   // illegal

8

9     public void setX(int val)

10     {   x = val;    // illegal

11     }

12

13     public void f( Cls args            ) // okay if immutable

14     public void g( @Unmodifiable Cls2 arg ) // suppresses all

// checking for unmodifiability/immutability.

15                 // (required for some legacy classes).

16

17     Response<T> doSomething( ArgVal val )

18     {

19         T returnValue;

20         //...

21         return new Response<T>(returnValue);

22     }

23 }

Listing 1: A Task Definition

Methods that don't return void must return a Response<T>, a wrapper around the actual return value. Remember, all methods are effectively asynchronous, so the return value won't be valid until the method completes, which could be a considerable time after the called method has returned. Response<T>, is an interface that extends java.util.concurrent.Future<V>, so can be used exactly like a Future if you have an existing multithreaded system. Among other things, you can wait on the Future for the request to complete, and you can abort the request (which in this case means remove the request from the queue). The Response<T>, defines a few additional methods that I'll discuss in a moment.

Though all of the above seems like a lot of rules to remember, in practice it's not such a big deal. Just make everything that you can private, and remember that nobody outside the class is allowed to access local fields, and that objects that come in from outside are also potentially dangerous, so make copies of these objects before storing them. The rules help you get things right by pointing out dangerous situations.

I should also say that I've deliberately not made things safe as a side effect, because that can violate the Least-Astonishment principle. For example, if you pass a method a standard Collection object, I don't wrap it in an unmodifiable variant automatically because the code within the method won't be expecting that change. I'd rather have a compile-time error than a mysterious runtime exception.

Talking to the Task

The notion of a BlockingQueue is handy when thinking about Active Object, but it turns out that it's much more useful to talk to tasks using a messaging system—a very lightweight and entirely in-memory system that works much like JMS.

Messaging systems support queues, of course, and that's the default way that things work in Tasks. A task effectively has a queue attached to it, and the methods of the task enqueue requests, then return. A "message," in this context, is an enqueued request.

However, messaging systems also support the notion of topics, and that's occasionally handy. The basic difference between a topic and a queue has to do with how many objects are involved in the communication. In the case of a queue, only one object—the Task—receives requests. In the case of a topic, several Tasks could "subscribe" to the topic and be notified when other tasks (or just plain objects) "publish" to the same topic. In JMS, the published request could be handled by one or all of the subscribers, but in the current task framework, the request is handled by a single Task. You don't know which one, however.

In the current Task implementation, queues are the default way of doing things, and the queues aren't named—the Task-object reference serves the same purpose. If you want to use topic-based communication, you need to add an argument to the Task annotation:

@Task(useTopics)

All methods of all instances publish to the topic—it doesn't matter which instance you use to publish the request. That is, no matter how many instances you create, there will be only a single dispatcher thread and a single queue. All Task instances will effectively publish to that single queue. All instances of all tasks queue up at the read end of the single queue, and the instance that handles the request may not be the one through which you published the request.

Work is distributed on a first-available basis to all the waiting tasks, which run in parallel. The other way you can think of it is that when topics are on the scene, all instances of the Task share a single dispatch queue, and publishing to a topic-based Task effectively queues the request up on that single queue. Requests are dispatched to whatever Task objects are waiting. The mechanism is similar to a thread pool.

@Task(useTopics=true, instances="3")     // instances can be any

// positive number or 0 (the default if missing).

As a convenience, you can specify the number of Task instances in the annotation, and then you don't have to explicitly create any of them. They'll be created by a machine-generated static initializer, and you can send a message as if you were using a Singleton. That is, given

@Task(useTopics=true, instances="3")

public class MyTopicClass

{

public void doSomething(){ /*...*/ }

}

you publish to the topic like this:

MyTopicClass.publish().doSomething();

Think of publish() as the equivalent of getInstance() on a Singleton.

Bear in mind that individual tasks cannot (easily) talk to one another. They can't access each other's private fields, for example, so topics are useful primarily for doing things that can be done independently: managing a pool of database connections, for example, or handling multiple, but independent, HTTP/REST requests sent to a web server. You'd have one database connection (or one HTTP client) per Task. The tasks run in parallel, but they are effectively independent of one another.

Getting Responses (Return Values)

So far, we've looked at sending requests to the Task, but how do you get a response? Since a Response is a Future, you can use the existing java.util.Concurrent mechanisms, but that's supported primarily to talk to legacy code. Using a Future is easy, though, because that's what the request actually returns:

Future<T> t = myTask.doSomething(val);

You can also wait for the task to complete like this:

Future<T> t = myTask.doSomething(val).thenWait();

Finally, when you want a response to be handled by the task that sends the request, use:

receivingTask.doSomething(val).thenDo(this, (v)->{ ... f(v); ... } );

One task sends a request to another task (the receivingTask, above). When that task is done, it sends another request object (specified in the lambda) back to the originating task (this). That is, the lambda is wrapped up as if it were a standard request and then queued up on the request queue of the task specified in the first argument to thenDo() (typically this). That task will run the lambda when it gets around to it, just like any other asynchronous call, so everything remains single-threaded (and thread safe).

It's important to realize that the code in the lambda is executed in the context of the sending, not the receiving, Task. An exception is thrown if the first argument to thenDo() is a topic-style Task or a normal class, declared without the @Task annotation. That is, this mechanism is meant to send a response to the Task that made the original request only.

Finally, the call:

receivingTask.doSomething(val).thenExecute( (v)->{ ... f(v); ... } );

executes the specified lambda when the request completes. This method is for non-Task objects that are delegating to Tasks. The lambda is executed on a pooled thread. Since the lambda can access local fields in the calling class, there are potential synchronization issues here, so be very careful.

Conclusion

So that's the core of the Active Object framework. The main reason for doing all this work is to make it easy to program asynchronous tasks. The code within the Task, since it's effectively single-threaded, doesn't require any synchronization at all, so is easy to write, debug, and maintain. If the entire program is task-based, then that same ease of maintenance applies to the entire system. The one problem the framework can't solve is synchronization when you mix Task objects with standard multithreaded code, but you can't do everything.

Just to reiterate what I said at the beginning of this article: the framework is partially built at present, and is definitely a work in progress. The main reason for writing this article is to get some feedback before I spend any time chasing down the wrong path, so if you have comments, please send them to jao@holub.com. I'll summarize the comments and post them to a JAO page on my website. Eventually, the entire framework will be published as open source, and there will be a book describing how it works and how to use it in much more depth than I've done here, but you've got to start somewhere!

Allen’s long-running columns for Dr. Dobb’s Journal (C Chest), JavaWorld (Java Toolbox), SD Times (JavaWatch), and others have been highly influential in the industry. His open-source Java threading library predated the java.util.concurrent system, and the associated book (Taming Java Threads) was one of Apress's all-time best sellers. He's written a total of nine books on programming topics. More info at his site. Send the author your feedback or discuss the article in the magazine forum.

A Night at the Museum

...Where Old Computers Refuse to Die
by David Bunnell
Pioneers of personal computing gather for one amazing night at the Living Computer Museum.

If there is a corner of heaven reserved for computer geeks, it must be very similar to Paul Allen’s Living Computer Museum, located in a 3-story warehouse south of downtown Seattle.

One wonderful evening in early April, I found myself milling about this museum with 150 technology pioneers, old-timers, game-changers, the people who laid the foundation of today’s digital reality, at a festive reception hosted by Paul Allen and his co-founder at Microsoft, Bill Gates.

Stuffed full of ancient, historical computers that have been painstakingly restored, the museum is a grand testament to the history, the glory of computers, how they evolved, and how they changed the world. Here you will find some of the few if not only actual working, fully functional mainframe and minicomputers as well as an extensive collection of the earliest personal computers (also “up and running”).

While I don’t know anything about most of the pre-personal computers, it was nonetheless impressive to see a working Xerox Sigma 9, circa 1971, and to learn it was used to send the very first message over the ARPAnet, which is the precursor of today’s Internet.

And amusing to know that there once was a computer called the “XKL TOAD-1,” TOAD standing for “ten on a desk,” because it could scale down to desktop size. Introduced in more recent computer history, 1999, my guess is the manufacturer, “Large Systems Group,” figured they had a Macintosh killer.

Because my career spans the personal computer era, I was naturally more interested in the personal computers. In my office at MITS during the late 1970s, I had an Altair 8800 interfaced to a teletype machine, a setup similar to the one at the museum, and I still have an Altair stashed away somewhere. (Occasionally my wife asks me, “That old computer you have in the basement, do you think it’s worth anything?”)

Each personal computer in Paul Allen’s collection evoked memories. Seeing the Radio Shack TRS-80 with its cassette tape drive reminded me of the days when I was writing instructional manuals for computer games and how cumbersome it was to load programs into early PCs using cassette tapes. The first IBM Personal Computer brought back a flood of images, emotions related to the startup of PC Magazine, mailbags full of subscription cards delivered to my house near Golden Gate Park in San Francisco, how the magazine grew to over 400 pages by its second issue, how we fought with our financial backer, how he sold PC Magazine out from under us, the resulting lawsuits, PC World, clashing media moguls Bill Ziff and Pat McGovern. I couldn’t look at the first Macintosh without thinking of Steve Jobs, the great opportunity he gave me to create Macworld magazine, how fast he walked and how difficult it was to keep up with him, his 30th birthday party, Ella Fitzgerald singing “Happy Birthday, Steve,” my teenage daughters stuffing the elevators at the Saint Francis Hotel with balloons.

My god, I thought, even if I was the only person here, I could spend hours and hours in this incredible place.

But then I was not the only one. As fascinating as the computers and related displays were, the assembled collection of digital luminaries was even more special. A one-time happening, a “be-in” for nerds, this particular human configuration will never be repeated, ever. I needed to pull myself away from the machines and mingle.

About then I bumped into Paul Terrell, yes, the Paul Terrell, founder of the first chain of computer stores, the BYTE Shops, the man who took a chance on two scruffy, barefooted hippies named Jobs and Wozniak by agreeing to sign a purchase order for 50 Apple I computers, their first sale, the beginning of their company.

Paul Terrell and David Bunnell

Terrell was just as I remembered him, ruddy faced, exuberant, and bubbling over with stories about the early days. We laughed and laughed about how MITS CEO Ed Roberts, sometimes referred to as “the Father of the Personal Computer Industry,” had me phone Terrell to tell him MITS was cutting off the BYTE Shops from receiving any more Altair Computers because Terrell had the audacity to carry competing products.

I was 25, MITS’s marketing director, and I thought this was crazy, why couldn’t the BYTE Shops carry competing products? Retail stores routinely carry competing products, but Roberts wasn’t having any of this. In 1976, if you wanted to sell Altair Computers, they had to be exclusive. As for add-ons, memory boards, and the like, they could come from other companies, but only if we preapproved them.

At the time, of course, Terrell wasn’t so sanguine, he was pissed. So he made deals to sell everything but Altairs‚ IMSAI, SOL, Apple I, Commodore PET computers, and this only made the BYTE Shops more successful while MITS went into a steep decline, was bought by a company no one had heard of, PERTEC, and by 1980 dissolved into a puddle like the Wicked Witch.

I found myself standing next to the great engineer, Lee Felsenstein, both of us admiring the SOL Computer he designed with its beautiful tactile keyboard that was so much ahead of its day. Did he remember hand-delivering a SOL to me at the Albuquerque office of Personal Computing magazine? Yes, he did, and Lee even recalled how we went out drinking afterwards.

It was a kick for me to describe to Felsenstein how the SOL became my very first word processor. “I loaded Electric Pencil into the SOL using its cassette recorder, a process that took several minutes and invariably failed once or twice,” I explained, “then I typed in my document and after making all the corrections I sat an IBM Selectric typewriter next to the SOL and typed the document over again.”

Lee looked at me as if I was nuts, but I pointed out his was still an improvement over just using the typewriter!

By now, Bill Gates had arrived and was standing near the early Microsoft exhibit reading his first resume, which is posted on one of the Living Computer Museum walls next to Paul Allen’s first resume. Written in 1974 with identical formats, the resumes reveal both boys were looking for a job as a Systems Programmer or Systems Analyst, and both listed their previous salary as $15,000 a year.

Bill Gates and David Bunnell

Along with their ages, the resumes strangely include their physical dimensions: Bill was 18, 5'10" and weighed in at 135 pounds while Paul was 21, 5'11" and 185 pounds.

I chatted with Bill for a few minutes and asked him if he would pose for a photo with me so that I could impress my granddaughters that I actually do know him, a topic of some dispute on the home front.

Next, I hung out a while with Bob Frankston, co-creator of the world’s first electronic spreadsheet program, VisiCalc, the program that got the personal computer into the business world. We were joined by John Draper, famously known as “Captain Crunch,” who along with Steve Wozniak invented “the little blue box” for cheating phone companies out of what were then egregious long-distance charges. Ironic but fitting for the evening, one man made personal computers legitimate for business, the other invented hacking.

The night went on like this. Roger Melen recalled the great story of the infamous “Dazzler,” the aptly named circuit board he invented to interface the Altair to a color monitor, thereby displaying stunning, kaleidoscopic colors, akin to giving your computer LSD. Left running in the window of the world’s first computer store, Arrow Computing on Pico Avenue in Santa Monica, it literally caused a traffic jam because people slowed up, stopped even, just to look at it. The Santa Monica police told Dick Heiser, the owner of the store, to take it out of the window or turn it off.

And Dick Heiser was there, of course. We chuckled about his quote in a 1976 issue of Computer Notes where he said it “wasn’t enough to be optimistic” about the future of personal computers, you had to be “wildly optimistic.” What an understatement that turned out to be!

My co-founder at PC Magazine, Jim Edlin, and I were treated to a few surreal moments with David and Betsy Ahl, the husband-wife editors of Creating Computing who were called in by Ziff-Davis Publishing to salvage PC Magazine after I quit and took all the employees with me to start PC World. I told David and Betsy they were “lucky” our lawyers instructed us to not damage anything as we went out the door because that was our inclination.

Jim Edlin and David Bunnell

“But you changed the map,” Betsy said. And she was right, we did change the map, which was the guide to where all the articles and ads were supposed to be placed in the upcoming issue. That was the last thing we did before walking out the door. Harmless mischief, really, but this was 30 years ago and I had forgotten about it.

The ensuing litigation was at the time the largest lawsuit in California, both sides claimed to be seriously aggrieved, we basically hated each other, but here we were cheerfully now recalling the incident about the map, looking back at the times of our young lives when we could do anything, when nothing stopped us, the days when we exceeded all reasonable expectations.

A gathering of legends at the Living Computer Museum

There’s more, of course, I could go on and on. Out of the 150 people I must have spent a moment or two with half of them and some of these moments were just as amusing (in my mind at least) as the ones above. But hopefully I captured the essence of it, a night at the Museum where Old Computers Refuse to Die, a night for the ages.

Thank you, Paul Allen.

David Bunnell is a writer and self-described "media architect." In the early 1970's he worked at Mits, the first personal computer company, where he met and collaborated with Microsoft founders Paul Allen and Bill Gates. After leaving Mits, he published Personal Computing magazine, the first of his many publications that include PC, PC World, Macworld, BioWorld, NewMedia, Upside and others. He has written several books on computing and on health, plus dozens of articles. Today, he is the Media Chief at The Unfrazzle Company, a startup that is launching smartphone apps to address the needs of family caregivers. He can be reached at david@davidbunnell.com. Send the author your feedback or discuss the article in the magazine forum.

Launching a Gonzo Engineering Project

V: Building the Team
by Steven K. Roberts
The infamous 580-pound, 105-speed BEHEMOTH, with Mac, SPARC, and DOS environments as well as satellite datacomm, HF/VHF/UHF ham radio, heads-up display, head mouse, handlebar keyboard, 6-level security system, speech synthesis, 72 watt solar array, and deployable landing gear to keep the monster upright on killer hills. The bike now resides in The Computer History Museum in Mountain View, California.

This is the fifth and final installment in a series of articles unlike anything we’ve ever published. Steven K. Roberts has figured out how to live passionately, pursuing crazy dreams and building fantastic machines (like BEHEMOTH and Microship, both of which are pictured and briefly described here) and going on amazing adventures. He calls what he does Gonzo Engineering, and in this series he tells you everything you need to know in order to pursue your own crazy gonzo engineering dream. Links to previous articles in the series appear at the end of this article.

If you’re at all normal (which I cannot assume, but hey, we’re talking statistics here), you can only work in isolation for a limited time before reaching burnout—whether from loneliness, overload, or a lack of constructive feedback. It’s analogous to music: I’ve played the flute all of my adult life and have a familiar set of ruts that I fall into when jamming by myself. But shove me in front of a microphone with other musicians, and after a few fumbling minutes of feeling like an incompetent klutz, I find myself playing fresh material. I recently started the piano, just to keep my lazy old wetware on its toes in new territory.

It’s like this with the design process, and not just for the practical reason of distributing workload. Everybody brings ideas and experience to the party, and when you’re in the envelope-pushing business you need all the inspiration you can get. Even for those rare folks who indeed know it all, proceeding indefinitely without intelligent company is just plain difficult. The trick is recognizing and attracting the kinds of people who have a lot to offer, and it’s no accident that those are the very folks who are already overloaded and unlikely to list “volunteerism” as a hobby. Just as with sponsor relationships, this has to be a win-win, and that can take a lot of unconventional forms. (It can also be based on money or barter; we’ll get to that in a moment.)

Attracting a Volunteer Community

What can a gonzo engineering project offer potential co-conspirators, assuming there’s not a big pot of cash available for hiring first-class talent? In my projects over the years, there have been a few “perks,” some accidental, that have kept me surrounded with interesting people:

For the Glory!

Perhaps the most obvious benefit that a volunteer crew can derive from pouring creative energy into a project is the resumé-enhancing halo effect of association with something exciting. It is thus exceedingly important that you don’t greedily hold on to all the credit, but instead share the spotlight with those who have made contributions. In my own case, I actually get a lot of pleasure from this: when I kick back with a beer and contemplate the bike or boat, I see decades of intelligent friends, mad marathons of midnight machining, student teams working with rising panic as the end of a quarter nears, and pivotal moments of insight contributed by people who haven’t been blinded (as I often am) by staring at the same problem for months. In articles, interviews, and speeches, I give credit where it’s due.

Of course, offering this as a sort of barter is a bit iffy; if a project is just getting started, promises of fame come off a bit like overly ambitious hand-waving, like a startup promising founders’ pool to someone who helps cobble together the “About Us” HTML. It takes a bit of time for this to become as attractive as it sounds.

The Bottom Line is Fun

All that seductive fame ’n glory aside, I have found over the years that the best motivation happens to be the most pure: fun. This is, after all, why most techies do what they do, and one of the best compliments I ever received on the project was from a fellow who dropped by for an afternoon of brainstorming: “Thanks for reminding me why I became an engineer.”

I am convinced that the best way to build a team is to simply do something so cool, so exciting, that people jump at the chance to participate. This is the kind of energy that gets creative juices pumping, and feeds the project... I dunno about you, but after a few years of pushing toward the same goal I tend to get a bit jaded. There’s nothing like the arrival of someone who’s turned on by the Microship fantasy to get fresh ideas percolating and knock a few jobs off the list (especially TBDWLs). (Editor’s helpful gloss: To Be Dealt With Later.)

Geek’s Vacations

It occurred to me a few years ago that I could carry this amusement theme to the next level by formalizing a “geek’s vacation program.” It’s simple: we invite clever folks to come stay with us for a week or so, taking a break from their normal jobs to do design or fabrication work for the pure pleasure of it. We provide food, beverages, a frolicsome atmosphere, and a few outings of playing tourist here in the Pacific Northwest. In exchange, we get the focused intellectual energy of some truly amazing people, and always manage to learn something.

Social Engineering

It didn’t occur to me in the Early Days, but another one of the most alluring features of these projects, from the perspective of our volunteers, has been purely social. Once it reached critical mass, with enough participants to make overlap likely, a new component entered the picture: folks would come by the lab to help, then meet each other and form new friendships. This has led to businesses, lasting relationships, and uncountable pizza nights... I’m not the only one who tires of working alone, it seems. If you make your Gonzo Engineering project entertaining enough to lure clever people, you’ll find that it might take on a life of its own. That’s where the real magic begins.

A skunkworks-like microculture developed around my projects, attracting programmers and machinists, hams and cyclists, human-powered vehicle gurus and chip designers. I recall one night a few weeks before the long-awaited launch of BEHEMOTH back in 1990... the stereo jamming, the windowless lab at Sun Microsystems a sea of fluorescent-lit clutter, the SPARC beeping every few minutes with incoming mail as I worked to nail down the logistics of the tour. Michael Perry was writing FORTH code to drive the audio crossbar, Steve Sergeant was chasing a noise problem, Steve desJardins was working on the landing gear 4-bar linkage, and Zonker Harris was squinting into a dense matrix of Lemo connector pins with a soldering iron in his hand. Over at the Rockwell milling machine named Cecil (Cecil be da Mill), David Berkstresser was standing in a sea of aluminum chips, conjuring a piece of structural artwork for the bike’s trailer hitch. I heard the mill spin down, then David hollered, “Hey! Does it ever make you feel funny that so many people are working so hard to get you out of town?”

The Microship, the result of an 8-year development project involving extensive sponsorship, students, and volunteer teams. This is an amphibian pedal/solar/sail micro-trimaran with retractable wheels, hydraulic systems, 480 watts of peak-power-tracked solar panels, and zippy performance under sail. BEHEMOTH, the Microship, and the later Nomadness project are all documented at microship.com.

Education

There is yet one more “intangible” motivation before we get to some of the more traditional methods of luring people into your lair. If you’re doing something that’s pushing envelopes and is exciting to media and sponsors, it’s a fair bet that it represents a very real learning opportunity. We’ve had people offer to help with “anything at all, even sanding,” just for the chance to hang around the lab and absorb techniques or arcane knowledge. The irony here is that this is one of my main motives as well, and is perhaps the source of my greatest pleasure in working with volunteers. In the process of grappling with interesting problems, everybody brings something to the party and the educational opportunities are endless.

Sharing the Wealth

And then there’s the stuff that really makes a geek’s eyes light up: new toys. In the midst of all your rhapsodizing to a potential volunteer about education, networking, and fun, it never hurts to mention that there may be excess goodies to share. I’ve had leftover antennas, computers, radios, nautical components, and more—much of which has found a new home with some of our star volunteers as an extra “thank you” for all the help. There’s an ethical component here as well: quite a bit of this is sponsored, and it feels a bit weird to take donated stuff and hawk it on eBay (I’ve done it a few times, but only with explicit approval from the sponsor or in cases where the company no longer exists). Passing along a few extras to people who have participated in the project feels reasonably consistent with the spirit of the gifts, and certainly generates a lot of smiles. So do team T-shirts.

Paying for It

Despite all the motivations folks might have for hanging around and helping you for free, however, we still have to accept the annoying truth that people have other things to do with their time. This translates into having to find more traditional ways to get help... and if you’re anything like me, your dream project probably doesn’t include a budget for full-time employees. For a while during the dotcom boom, I was able to make enough from corporate speaking gigs to keep a composites guru on-site, but even that was a non-traditional deal that included room and marginal board (in an old camper) as part of the consultancy package. Actual employees are another matter entirely, opening up regulatory cans o’ worms, workman’s comp insurance, and the expectation of timely paychecks.

But there are alternatives.

First, if the associated business model we discussed earlier is generating cash flow, you can “share the wealth” by giving someone a piece of the action to take an active role. Given that the project itself is coupled synergistically with the nickel-generator, this may translate into on-site help that can keep you moving through the creative doldrums.

Second, if you have a tight relationship with a sponsor and are in the process of conjuring something that the company might be interested in leveraging, then you might be able to bargain for time from one of their employees. This is great, as you don’t have to play business-owner any more than necessary, and if the project doesn’t reach escape velocity you haven’t thrown a wrench into anyone else’s career.

I would be careful with bartering a vague “partnership” unless the project has a very real deliverable and corresponding business model. This is usually not the case with the kinds of passionate pursuits we are considering, and things can change a lot between concept and execution. If someone has been faithfully putting in the hours with the promise of residuals from future patent or book royalties, and instead gets to watch you getting Slashdotted and BoingBoing’d all by yourself, you could have anything from a lost friendship to a lawsuit on your hands (depending on how close your understanding was to a “legal contract”). Seriously, be careful with this. Don’t get into that kind of debt. Or any kind, if you can help it.

Tapping Academia

There is one other way. Lemme tell you a tale of Microship development...

In the Spring of ’93, I arrived in San Diego to speak at Qualcomm, one of my favorite sponsors—the creators of the bike’s satellite communication system and gurus of CDMA and other DSP-flavored wizardry, a company managed by engineers instead of MBAs. A friend there pointed me to nearby Scripps Institution of Oceanography, where I might have a chance to pick up a few tricks from guys who know how to keep electronics working at sea (a non-trivial problem, with delicate high-impedance circuitry surrounded by conductive aqua regia). Armed with an introduction, I wandered over and did a casual bike show ’n tell for a Friday afternoon Scripps cookout.

As I was standing by the keg nursing a pint, my bike parked a few feet away and the surf pounding just beyond, a classic Hollywood stereotype of the brilliant young PhD walked over and said, “Fascinating. Have you gotten any results yet?”

“Well, I’ve fallen in love a few times,” I answered.

He looked at me blankly for a moment and then cracked up. “No, seriously...”

This was my introduction to academia. I hung around a few days, seeking space at the Scripps facilities, eventually managing to arrange a secure place to park the diesel Mothership and stash my gear in a run-down storage facility in a desolate nearby canyon... but with no net connection, phone, or actual workspace. It was an excellent toehold, though, and the chain of contacts kept growing as I explored the couch circuit. A few days later I met with a professor in the Electronic & Control Engineering department at UCSD (University of California at San Diego).

Almost immediately a potential win-win emerged. Although it wasn’t widely viewed as a problem among the academics, there was a serious shortage of hands-on engineering opportunity for students: they could actually make it through four years and get an undergraduate degree without ever picking up a soldering iron. I found this shocking, and had a solution to offer: “Hey, give me some lab space and I’ll teach a senior projects class.”

I stumbled into university culture with naiveté and an utter disregard for hierarchies—to me, there was no essential difference between deans, chancellors, TAs, and professors. Only much later did I understand that there is a pervasive caste system, which explained my tendency to ruffle feathers. Other than holding on to lab space long enough to get the Microship built, however, I had no pretensions of a career, publishing in refereed journals, or chasing the holy grail of tenure.

Nor did I anticipate the complex politics of space wars. My first lab was an abandoned bookstore... but the day after I installed a monitored security system and set up a working facility, a construction crew hacked straight through the drywall, knocked down shelving, looked around in annoyance at my stuff, and asked me what the hell I was doing there. “We’re tearing out this end of the building and you gotta get this crap outta here NOW, before our contract penalty clause kicks in and costs us a thousand bucks a day. Which is what it’s gonna cost you.” But this disaster was tantamount to a back door from the institution-hacking perspective: now that finding space for me could be defined as an emergency, I landed within a few hours in the Microwave Lab, vacant for the quarter and perfect for my needs.

I moved out two years later.

Occasionally real professors wondered aloud what some rube without a degree was doing with 800 square feet of prime lab space, complete with a dozen benches, adjoining office, and Faraday cage. “I hear he’s having those kids build circuit boards. “What the hell does he think this is, a vo-tech school?” But I was fortunate to have three faculty members solidly on my side (the only ones who had worked in industry), and was buffered by a well-publicized program that gave students the chance to design and build real systems, not just run simulations as an antidote to the textbook world of lumped constants and zero-rise time pulses (much .edu about nothing).

The experience did cure me of any lingering wistful regret about having missed those idyllic college years, despite the daily consumption of epicurean cafeteria fare. All around me, students were undergoing a sort of extended agony of uncertainty and stress, many of them deep into engineering school without any notion of what real engineers actually do. But what mattered most was assembling an effective student team every quarter, learning how to be a manager, and getting on with the project. My job was to identify and attract folks on the fringe, give them interesting design challenges, and leverage their work to propel myself into the next adventure.

Within a few months we had about ten FORTH nodes scattered around the lab on benches arranged like finger piers in a marina, all chained to a Hub and forming a classroom-scale Microship emulator by a braided 6-wire bus and running a protocol designed by one of our wizard volunteers (giving us pier-to-pier networking).

Nodes were assigned to any task that could be clearly defined, and some of the student teams produced decent work. Audio, serial, and video crossbar networks flickered to life, collectively forming Grand Central Station. A couple of shy fellows managed with a little coaching to decode the communications between a Sony DAT recorder and its remote control, then replicate it to allow software to drive the unit. (“This is the happiest moment of my life,” one said as they arrived, newly confident, to give their final report in suits and ties.) After a couple of failed attempts, we found two guys to design the controller for the boat’s video turret with its steerable high-quality camera: Working with a wizard student from the Mechanical Engineering department who designed the mechanics, they conjured a beautiful piece of work that survived all the technological attrition of the ensuing years and became part of the final system. These were the exceptions, and they made it all worthwhile.

Other projects weren’t so successful. The first attempt to write a GUI for the crossbars took two guys two quarters, yielding a fat listing of impenetrable C code for a ’286 that talked directly to the display drivers. It never really worked, but the fault lay with my vague specifications; exasperated one afternoon, I learned HyperTalk and wrote a Mac-based front end in about six hours. Some teams never got past their initial learning curves, and one pair working on power management turned their final report into an explanation of the FET, complete with characteristic curves and massive amounts of replicated library material, counting on the ancient tradition of BS to carry the day. One fried the fuse in my beautiful new Fluke multimeter trying to measure the current capacity of a power supply by measuring across it; I sent him downtown on a quest for a replacement with the explanation that one of the first requirements of engineering is knowing how to track down parts. Someone power-cycled my Tektronix scope with every measurement; someone else cut a live multi-conductor power cable with diagonal cutters and made the sparks fly; yet another wired a fully populated DB-25 with about a half-inch stripping on each wire, rendering it virtually untouchable without causing a short. And I’ll never forget, “Steve, do these colors on the resistors really mean anything?”

But you know, it was worth it. I relate all this to give a realistic view of the Gaussian distribution curve, which has to be taken into account when accepting free help in a classroom setting. In sum, I consider it a win-win.

Making the Academic Connection

Now that I have either teased you or frightened you with visions of naive students poking with sharpened sticks at your delicate labor of love, I should add that this is not an easy relationship to initiate, nor is it always something you want. Only a small number of engineering schools offer the quality of education that is likely to return more value than it costs you to deploy... if you want to be a volunteer teacher, that’s fine, but if you are hoping a team of bright-eyed young geeklets will speed your dream on its way to reality, you’ll need to be willing to take charge of a few things. Choose the institution carefully, be sure you are able to drive the project-definition and ongoing assessment processes, maintain close faculty alliances, and put serious time into fine-tuning all the associated relationships.

One more caveat: student project energy is viewed as a scarce resource in the very places where the quality is likely to be highest, and I have run into places where a savvy faculty member is already guarding it jealously with no shortage of pet projects in reserve. Such people will make it highly difficult for you to get a foot in the door, necessitating a higher level of institution-hacking (or, more likely, looking elsewhere entirely).

If your nearby school looks promising and goes well beyond textbooks (or wants to, and sees you as a resource to that end), spend some time making connections among students, professors, and alumni. What do they want? PR? IP rights to anything invented on-site? Leveraged corporate sponsorship with the companies you already have on board? Curriculum development? Or just a lighter workload for their own lazy or inexperienced teachers? The latter can make for easy entry, but can also backfire if it is an indicator of overall academic sloppiness... whether the result of incompetent faculty, or tenured people more interested in publication and funding than undergraduate engineering education. This is more common than one might hope, alas.

Afterword

I hope I have given you some useful tools in this little series. Every gonzo engineering project depends most obviously upon whatever flavor of geek expressionism lies at its core, yet it is excruciatingly vulnerable to the realities of human limitation. The basic rule is to just keep moving in the same direction for a long time, but that isn’t enough... even if you are of the Wizard class, eventually you still need stuff, exposure, cash flow, and help.

The tips I have presented here are not theoretical. In 1983 I fled the suburban lifestyle and took off across the US on a recumbent bicycle. 17,000 miles later, I was on the third version of the bike and had a book under my belt as well as relentless media coverage, a team of volunteers, and enough corporate sponsors to make the massive undertaking possible. A crazy dream had turned into a career; now, over 25 years later, I am still reaping the benefits of this process when working on my new projects. I mentioned at the beginning that I was about to reveal all my “trade secrets,” things I’ve never publicly discussed before.

This is true, and the reason is that it is kind of a zero-sum game. In the heat of the BEHEMOTH bicycle era, I was not only careful about inviting competition into my odd little niche, but also conscious of the delicacy involved in the intertwined mesh of relationships... all critical to the ongoing operation. It would not have felt right to publicly explain how to schmooze for goodies or gently manipulate the media into helping build a consistent image when I was dependent upon such relationships for my very existence.

But this is valuable information, as timely as ever, and as I make the transition to a full-time life aboard a voyaging sailboat I find that I’m willing to share now. Enjoy. And good luck!

Earlier articles in this series can be found here, here, here, and here.

Steven Roberts was the original “technomad,” covering 17,000 miles around the US on a computerized recumbent bicycle from 1983-1991 while publishing tales via CompuServe and GEnie, then extending the same design objectives to water with an amphibian pedal/solar/sail micro-trimaran that consumed all available resources until 2002. As is typical of homebuilt boat projects, however, by the time it was finished he didn’t really want to do that anymore... so he has since made the transition to a full-time life aboard a 44-foot steel pilothouse sailboat, and is now based in the San Juan Islands north of Seattle. The ship is extensively networked with embedded data collection and control systems, streaming telemetry, and a user-interface layer reminiscent of the Enterprise... with a wrap-around console that includes communications, R&D lab, audio production studio, and a piano. Roberts has published six books ranging from travel and adventure to microprocessor design, and prior to becoming a technomad spent a decade developing custom industrial control systems, early home computers, and other paleo-geekery. More on his technomadic projects can be found at microship.com (with the new boat at nomadness.com). He is publishing the ongoing technical narrative of the new project as a monthly PDF Nomadness Report, as well as a series of Boat Hacking design packages detailing the subsystems. Send the author your feedback or discuss the article in the magazine forum.

Pub Quiz

He Says It’s Simple
by Michael Swaine
It’s a hero sandwich of a puzzle. It’s a Sudoku. And an anagram. And as a puzzling bonus, one of the critical clues has been left out as an exercise for the solver. And there’s another very misleading clue about swords in the subtitle.

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 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 name of a computing legend.

Oh, there's one difficulty. As you can see, one of the nine letters doesn’t appear anywhere in the puzzle grid. You’ll have to figure out what it is and where it goes yourself. Good luck!

O

N

R

S

B

H

R

N

O

I

R

S

B

H

E

N

B

E

S

I

O

B

I

The missing letter is: _ . And the computing legend is: _ _ _ _ _ _ _ _ _ .

The subtitle is a clue, if you focus on its swords. Solution right here next issue. Or on Twitter right now, no doubt.

Calendar

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

- 2013-04-29, RailsConf, Portland OR
Rails Vs. The Client Side Noel Rappin (author of Rails Test Prescriptions)

- 2013-05-03, NFJS, Charlotte, NC
Talks on JVM related languages Venkat Subramaniam (author of Practices of an Agile Developer, Programming Groovy, Programming Scala, Programming Concurrency on the JVM, Programming Groovy (2nd edition), and Functional Programming in Java)

- 2013-05-03, Rustbelt Refresh
HTTP: Get to Know the Foundations of Your Career Jonathan Penn (author of Test iOS Apps with UI Automation)

- 2013-05-04, MobiDevDay Detroit 2013
iOS Media APIs Chris Adamson (author of iOS SDK Development)

- 2013-05-07, Great Indian Developer Summit, Bangalore
Workshops and talks on various topicsVenkat Subramaniam

- 2013-05-14, Triangle.rb, Raleigh NC
Pragmatic Agility Andrew Hunt (author of Practices of an Agile Developer and Pragmatic Thinking and Learning)

- 2013-05-14, JUG, San Francisco, CA
Scala for the IntriguedVenkat Subramaniam

- 2013-05-16, London, UK
Starting (or Restarting) Your Agile Project Right! Join us if you need to define where your project is headed and what done means. Discount for both workshops. Johanna Rothman (author of Behind Closed Doors, Manage It!, Manage Your Project Portfolio, and Hiring Geeks That Fit)

- 2013-05-16, Milwaukee Perl Mongers meeting
Beyond grep: ack and other code search tools Andy Lester (author of Land the Tech Job You Love)

- 2013-05-17, London, UK
Master Class: Coaching for Leaders. Are you using all possible coaching stances? Explore with a master coach. Discount for both workshops. Johanna Rothman

- 2013-05-17, The Founder Forge Chicago
The lessons learned in hiring and growing a development team. Should you hire a team with breadth or depth? What should you look out for when reviewing resumes and code samples? How do you make sure your new hire fits your culture from day one? Ka Wai Cheung (author of The Developer's Code)

- 2013-05-17, NFJS, Dallas, TX
Various topics related to JVM and HTML5Venkat Subramaniam

- 2013-05-20, Agile Sweden 2013, Stockholm
Impact Mapping Staffan Nöteberg (author of Pomodoro Technique Illustrated and Pomodoro Technique Illustrated (audio book))

- 2013-05-20, Let's Test Conference, Sweden
Tutorial: Hiring for Your Team: Culture Trumps Skills Johanna Rothman

- 2013-05-21, Let's Test Conference, Sweden
Keynote: Becoming a Kick-Ass Test ManagerJohanna Rothman

- 2013-05-21, Lake / Kenosha County PHP Users Group
Beyond grep: ack and other code search toolsAndy Lester

- 2013-05-22, GR8Conf, Copenhagen
Talks on various topics related to Groovy and the JVM. Venkat Subramaniam

- 2013-05-24, Path to Agility, Columbus OH
KeynoteAndrew Hunt

- 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

- 2013-06-05, Software Architecture Summit, Berlin
Various topics related to Java and architectureVenkat Subramaniam

- 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

- 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-10, Norwegian Developer Conference, Oslo, Norway
Three talksAndrew Hunt

- 2013-06-12, NDC Oslo
Talks on various topicsVenkat Subramaniam

- 2013-06-12, QCon New York
"Well Behaved Web Apps in the Haute Societe of Native Apps" Adrian Kosmaczewski

- 2013-06-18, WordPress Lake County (IL) Meetup Group
Resumes and Job Interviews From Both Sides of the Desk Andy Lester

- 2013-06-23, SPA2013 London, UK
Case: study: Is eXtreme Programming still alive and kicking? Rachel Davies (author of Agile Coaching)

- 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-09-11, BDD Kickstart, Barcelona
Get a flying start with BDD, the collaborative process that's changing the face of software development. Matt Wynne (author of The Cucumber Book and Cucumber Recipes)

- 2013-09-14, Baruco
TBD David Chelimsky (author of The RSpec Book)

- 2013-09-14, Barcelona Ruby Conference
Hexagonal railsMatt Wynne

- 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-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 (4th edition), Programming Ruby 1.9 & 2.0 (4th edition), and Agile Web Development with Rails 3.2 (4th edition))

Bookshelf

Pragmatic Bookshelf News

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

What’s New

Now you can go beyond throwing angry pigs at birds (or vice-versa) and build your own awesome mobile game or sophisticated multi-media mobile app. For cross-platform development (iOS and Android) using Corona, grab a copy of Create Mobile Games with Corona. For Android development using Processing, have a look at Rapid Android Development: Build Rich, Sensor-Based Applications with Processing. Think of it as one less excuse to get started on the mobile application you’ve always wanted to build.

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

Programming Erlang

2^

3

Programming Ruby 1.9 & 2.0

3^

6

Test iOS Apps with UI Automation

4

4

Agile Web Development with Rails

5^

9

The Definitive ANTLR 4 Reference

6v

5

Modern C++ Programming with Test-Driven Development

7v

2

Functional Programming Patterns in Scala and Clojure

8^

NEW

The Cucumber Book

9v

1

Practical Programming

10^

NEW

The RSpec Book

11v

8

Practical Vim

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 Death of Blinky
by John Shade
John exposes the Blink Tag Conspiracy.

Mozilla developers are plotting the death of the blink tag.

You remember Blinky:

HTML:

<p>Best-selling author Malcolm Gladwell scores again

with his latest book, in which he explains how to

<blink>think without thinking</blink>!</p>

Blinky has been bleeding for years from many wounds, but this final cut is being administered by the Mozilla Foundation, and that should trouble you. Because the name Mozilla means “Mosaic Killer” (you can look it up). So it should be obvious to anyone who lives their life by conspiracy theories that the true secret agenda of the Foundation is to kill every innovation introduced by the first visual Web browser, Mosaic, famously developed by Marc Andreessen and Eric Bina at the National Center for Supercomputing Applications, may their praises never cease.

Actually I think the blink tag was first implemented in the Netscape Navigator browser, not Mosaic, and by some anonymous engineer engineer, not by Andreessen or Bina, but that’s close enough for conspiracy theory. And mark my words, Blinky is just the start.

But for Blinky, this is the end. If the Mozillers do this thing, the blink tag will no longer be supported by Firefox’s Gecko HTML rendering engine, which means that it will no longer be supported by any current browser implementation anywhere.

A sad day for fun-loving Web design, right? The end of an era. It is that, but it’s also appropriate, because that thing needs to die. The blink tag was a mistake from the very start. Blinking clearly doesn’t belong in html.

It should have been implemented in CSS.

And of course it was. It’s right there in CSS3, hiding in the text-decoration property. It looks like this:

HTML:

<p>Best-selling author Malcolm Gladwell scores again

with his latest book, in which he explains how to

think without thinking!</p>

CSS:

/*  Nothing funny going on here.

Or IS there? */

p {text-decoration:blink}

Well, it looks like a maniacally throbbing paragraph or whatever, but this is how you use it. But only if it’s supported in your browser, and you know what I’m going to say next: Blink style support is sadly lacking in most browser implementations.

Well that tears it. In a situation like this, it clearly becomes incumbent on developers to take matters into their own hands and reinvent blink.

There’s Flash, of course. And who knows, now that its champion at Adobe is working for Apple, maybe the Steve Jobs Flash fatwa will be reversed.

But I wouldn’t count on it.

This hero tried to solve that problem, but failed. The comments in the article suggest a workaround, though.

I sure hope somebody solves the problem. And so should you. Because even if you never blink any text, are you going to stand idly by while the Mozillers take away everyon’s right to blink text? I don’t think so.

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. The blink tag was pretty much his only unadulterated pleasure, and now they’re taking that away. Follow John on Twitter, send him your feedback, or discuss the article in the magazine forum.

Rear Window

A Parting Shot

Four pioneers in personal computing.

Pioneers in personal computing software, magazines, hardware, and hacking. Left to right: Bob Frankston, co-inventor of the electronic spreadsheet; David Bunnell, marketing director at MITS and creator of PC World, Macworld, and other computer magazines; Lee Felsenstein, Homebrew Computer Club moderator and creator of the Processor Tech Sol and Osborne 1 computers; and John “Captain Crunch” Draper, legendary Blue Box inventor and phone phreak. Photo courtesy of David Bunnell and taken at the Living Computer Museum in 2013.