Foreign Language Lessons, part 3

July 14th, 2011

So, continuing on with the fun from last time, I went back to the my Lisp program and translated it into Erlang. Unlike the complete re-think I had to pull off in going from Ruby to Lisp, this was very straightforward.

Here’s the meat of the Erlang code:

-record(line, {content, indent}).
-record(node, {content, children}).

parse_text_line(Text) ->
    %% converts " text" to (:content "text" :indent 4)
    Content = string:strip(string:strip(Text, left), left, $\t),
    Indent = length(Text) - length(Content),
    #line{content=string:strip(Content, right, $\n), indent=Indent}.

%% Split a list of lines in two, breaking on the first line whose indent is =< the minimum.
split_list(_MinIndent, List1, []) -> [lists:reverse(List1), []];
split_list(MinIndent, List1, [First|Rest]) when First#line.indent =< MinIndent ->
    [lists:reverse(List1), [First|Rest]];
split_list(MinIndent, List1, [First|Rest]) ->
    split_list(MinIndent, [First|List1], Rest).

%% Parse a list of 'line' record into a tree structure, based on indent
build_nodes([]) -> [];
build_nodes([First|Rest]) ->
    [ChildLines, SiblingLines] = split_list(First#line.indent, [], Rest),
    Children = build_nodes(ChildLines),
    Siblings = build_nodes(SiblingLines),
    Node = #node{content=First#line.content, children=Children},
    [Node|Siblings].

And the equivalent Lisp:

(defun parse-text-line (line)
  ;; converts " text" to (:content "text" :indent 4)
  (let ((content (string-left-trim '(#\Space #\Tab) line)))
    (list :content content :indent (- (length line) (length content)))))

(defun split-list (criterion data-list)
  ;; break a list into two lists; the second begins with the first element that matches the criterion.
  (if data-list
      (if (funcall criterion (first data-list))
          (list () data-list)
          (let ((me (pop data-list)))
            (let ((chunks (split-list criterion data-list)))
              (push me (first chunks))
              chunks)))
      (list () ())))

(defun build-nodes (lines)
  (if lines
      (let* ((me (pop lines))
             ;; split off our children from the rest of the lines.
             ;; the first line with an indent <= ours is a sibling, not a child
             (chunks (split-list (lambda (x) (<= (getf x :indent) (getf me :indent))) lines)))
        (let ((children (build-nodes (pop chunks)))
              (siblings (build-nodes (pop chunks))))
          (let ((node (list :content (getf me :content))))
            (if children (setf (getf node :children) children))
            ;; (format t "~a~%" (getf node :content))
            (push node siblings))))
      nil))

Erlang has obvious Lisp roots, so most of the concepts translated 1-for-1. (I didn’t have any macros in my Lisp code, which might have made that hairier.) Most of it was changing dashes to underscores and moving parentheses around, but Erlang has some new features of interest.

Pattern Matching

Most of the Erlang functions take advantage of its pattern matching. This is a more extreme form of the method overloading that Java developers are familiar with. Erlang does allow varying numbers of parameters, as in

show_indented(Nodes) -> show_indented(Nodes, 0).
show_indented(Nodes, Indent) ->
    ...

where the one-parameter version just calls the two-parameter version with a default indent. But more interestingly, it lets you define functions by the parameter values, as we see here:

build_nodes([]) -> [];
build_nodes(Lines) ->
    ...

The first build_nodes function matches when it’s passed an empty array. If any other value is passed, it fails to match the first version and tries the second. The second matches any parameter, and assigns its value to the Lines variable. The really wacky case of this is in the definition of

main([[$\:|FuncName]|Filenames]) ->
    ...
main(Filenames) ->
    ...

The first one only matches a list whose first element is a string beginning with a ‘:’ (“:my_function”), and handily assigns the rest of the string to the FuncName variable (FuncName = “my_function”) and all the other arguments to Filenames. No match, and it just assigns the whole argument list to Filenames. You could implement that functionality in any other language, but this expression is very concise and clear, very declarative.

The case clause works in a similar way:

case Node#node.children of
        [] -> io:fwrite("~s~n", [NodePath]);
        Children -> show_path(Children, NodePath)
    end

This says, “If node’s children are an empty list, write out the node path; otherwise, assign them to Children, and pass that to show_path() along with NodePath.

On the whole, as odd as Erlang’s syntax is, I find it friendlier than Lisp’s. The pattern matching is weird at first, but very elegant and powerful once you wrap your head around it. I’d be interested to know the reaction of someone new to programming. I suspect they’d be less thrown by the syntactic quirkiness – the arrows and the comma vs. semicolon vs. period for line endings.

Spawn!

But all this is not why I’m learning Erlang. If it were just a stylistic improvement over Lisp, that wouldn’t justify its existence. We’re here for crazy parallel processing hijinks. So ok, here, let me re-write this so that it spawns a new process for every node. When the node is done building its children and siblings, it sends a message with all its data to its parent node, and so on up and down the tree. Ready? Here we go…

build_nodes(Parent, Group, []) -> Parent ! {Group, []};
build_nodes(Parent, Group, Lines) ->
    [First|Rest] = Lines,
    %% split off our children from the rest of the Lines.
    %% the first line with an indent =< ours is a sibling, not a child
    Criterion = fun(X) -> X#line.indent =< First#line.indent end,
    [ChildLines, SiblingLines] = split_list(Criterion, Rest),
    spawn(?MODULE, build_nodes, [self(), children, ChildLines]),
    spawn(?MODULE, build_nodes, [self(), siblings, SiblingLines]),
    receive
        {children, Children} ->
            Node = #node{content=First#line.content, children=Children}
    end,
    receive
        {siblings, Siblings} ->
            io:fwrite( "[~s] ~p~n", [Node#node.content, self()]),
            Parent ! {Group, [Node|Siblings]}
    end.

Here’s the full thing, but that’s about it. Instead of calling build_nodes() directly, we spawn them off and wait for the results. Instead of just returning our list of nodes, we send it to our Parent. (“Group” is just to keep children and siblings separate.) If you look at the diff, you’ll see a couple more minor things, but that’s all there is to the functional change.

So Erlang is surprisingly useful as a general-purpose scripting language. Probably not the first tool I’d reach for, but it doesn’t suck. And all of its limitations and eccentricities pay off when you start spawing processes. They straightjacket you into designing something that’s easily parallelized. I’m imagining trying to do a similar conversion in Java, where I’d be building a shared data structure and having to manage synchronization, thread completion, ordering results, and all that. Bleah.

(I have to point out that this is actually a bad example – this is not the kind of processing you want to parallelize. It schleps around a fair amount of data, and does very little processing. You really want that the other way around.)

Foreign Language Lessons, part 2

July 12th, 2011

So, last time when I was talking about Lisp, I said that even if I didn’t end up using it, I hoped I might learn things from it that I could apply to other languages. I kinda had one in mind when I said it, and that one was Erlang.

What?

Erlang was developed back in the 80s for programming telephone switching equipment. That sounds pretty bizarrely specialized, right? The problem they had was pretty much unique back then. They had all these machines that had to talk to each other. The individual messages, the requests they had to process, were relatively simple, but the system as a whole had to deal with an absolutely ludicrous volume of them and be perfectly reliable. You probably make hundreds, if not thousands, of phone calls a year. If even two or three of them got dropped, you’d say your phone system is pretty crappy. “It keeps dropping calls.” And if the whole system went down for like an hour, they’d never hear the end of it.

These days, a lot of people have this problem. Not just phone companies, but pretty much anyone who runs a popular web site or instant messaging service. A lot of enterprise software now relies on a “message bus” to handle communications between various chunks of code on different servers. Anything having to do with credit card processing or financial markets also needs that cocktail of high volume and high availability.

So what’s so special about Erlang?

Erlang was built from the ground up with this sort of thing in mind, not just as a concern but as its raison d’etre. There are really basic things that Erlang doesn’t let you do because they cause problems at scale in a massively multi-processing environment. Like, it doesn’t let you modify data structures. Once you’ve created them, you can copy them over and change them on the way, but you can’t change the original. Why? Because that forces you to communicate the change explicitly, and nobody has to worry about data getting yanked out from under them.

That’s the programming equivalent of rugby players taping their ears to their heads. The fact that people feel the need to do that tells you something about the seriousness of the situation.

On the other hand, Erlang has features that make it easier to write these sorts of massively concurrent and robust programs. Spinning off a new process is trivial, a single command, as is sending messages to it and even registering it as a service so that other processes can talk to it. Doing that on a remote machine isn’t much more than adding its name or IP to the command. I’ve done that sort of thing in Java, but holy crap it’s a lot of hassle.

The fact that this is a simple and routine part of Erlang programming also tells you something about the nature of the situation.

The crazy thing that Erlang lets you do (again, easily) that I haven’t seen in any other language is that it lets you update code while it’s running. This is not to be confused with the half-assed thing Java application servers do: If they’re running in “development mode” (so not recommended for production use), they can recompile updated JSPs; or they can shut down your whole app and restart it, leaking memory like a sieve the whole while. In Erlang, all these separate processes can individually reload their code whenever it suits them. You don’t have to shut down the server. You don’t have to coordinate all the processes in some way. You just set it up so that the next time a process does its thing, it does it with the new version of the code. Here’s what it looks like:

-module(countdown).
-export([init/0, reload/0]).
-export([tick/1]). % so we can spawn this properly.

%% spawn a countdown process with a default start time of 10 seconds.
init() -> init(10).
init(Time) ->
    register(ticker, spawn(?MODULE, tick, [Time])).

tick(Time) when Time >= 0 ->
    io:format("Tick ~p~n", [Time]),
    timer:sleep(999),
    receive reload ->
        ?MODULE:tick(Time - 1)
    after 1 -> tick(Time - 1)
    end;
tick(_StartTime) ->
    io:format("Boom.~n", []),
    done.

reload() ->
    ticker ! reload.
view raw countdown.erl This Gist brought to you by GitHub.

(Calling “?MODULE:tick()” causes the code to reload; plain “tick()” doesn’t. Full example with alternate version and commentary.)

The syntax probably looks kinda foreign, but simple enough that you can puzzle it out. It just creates a countdown timer called “ticker”, but it comes with a reload command that tells it to update itself. In the middle of counting down, you could swap in a new version that prints something different, or counts slower, or starts counting up. It’s a trivial example, but that’s the point: it’s trivial. Doing this in any other language would be somewhere between mind-bendingly complicated and flat-out impossible. It certainly wouldn’t be something you’d do to make your program more reliable. But Erlang has this whole infrastructure for not only updating your application while it’s running, but rolling back to the old version if you find you’ve screwed something up.

So Erlang is technologically cool, and useful in an increasingly broad range of applications. But part of the appeal for me is also that it’s kinda weird. As with Lisp, the programming toolkit is not like most other languages, and it forces me to think about problems in a very different way. That makes it more interesting as a hobby, and it may also make it more valuable as a professional skill. There’s a lot of demand for Java, but there’s also a lot of competition. Erlang is more of a gamble. It may not catch on, but if it does, all that weirdness is going to thin the competition.

Until then, it also means that the Erlang community is mostly made up of people who actually love programming. They’re not just trying to get a job. They’re smart and passionate about what they do. They’re fun to hang out with and they seem to like beer. So worst case, I’ll have fun learning it.

(Most of Paul Graham’s older essays about why you should use Lisp also apply to Erlang.)

Foreign Language Lessons

July 2nd, 2011

I’ve been tinkering around with Lisp in my spare time lately. I recently finally got around to reading Paul Graham’s Hackers and Painters. He talks a lot about how Lisp was his business’s competitive advantage (he made his bankroll on what became Yahoo! Stores and now runs Hacker News and Y Combinator), and how it’s both the mark and maker of really good programmers. I’ve always written it off as being an “academic” language, but he convinced me to give it a try. I have no expectation of actually using it professionally, but I hoped that I might learn something that would be applicable in other languages.

Lisp is the Latin of programming languages. It’s been around forever (since 1958, which is the paleolithic era for programming). It never really caught on, outside of niche applications and user groups, but it’s never quite died out, and it seems to be enjoying a resurgence. It’s also inspired other languages, like Ruby and Erlang, that I’ve gotten interested in, and people who know it say that even those just have watered-down, training-wheel versions of features found in Lisp.

I had a good little sample problem to try it out on. I’d been sketching out a to-do list tool, something that would let me keep track of projects, nested sub-projects, and tasks. The key was that I wanted to keep the data in plain text, in some readable format, but also be able to munge it – filter and sort it and such; some sort of simple wiki-style markup language. The first part of this was the structure: I’d have a project, with its sub-projects indented below it, and their sub-projects and tasks indented further. The parser would build up a tree data structure. So you’d have plain text input that looks like this:

and you’d want to end up with a data structure like this:

Now, I’d already done this in Ruby. I’d designed a set of classes to represent the stages of the parsed data. I start out with a list of strings, then I break each string into a simple object that just knows “indent” and “content”. It then adds that to the tree structure as a node that knows what its parent node is. As more nodes get added, they become its children. Eventually, I could extend those classes to understand particular bits of project-related markup, like priorities or dependencies. But for now, just the tree structure.

Already, there’s a bit of recursion here: I have a “current” node, the most recently added one. If the next node is indented further, I add it to the current node’s children. Otherwise, I tell the current node’s parent to try to add it. This way, you could pop up several levels before you find a parent to add the new node to. In this example, I try to add node “e” to “d”, then “c”, before finally adding it to “a”. Despite that, it’s still a pretty linear process. Each line is added in order, and you’re just moving up and down the tree, stitching each into place.

So for my first stab at doing this in Lisp, I just sort of transliterated it. I took the logic and structure of my Ruby code, and tried to just turn it into Lisp syntax. That didn’t go so well. It’s a bit hard to explain how it went wrong, other than to say that it came out like the programming version of Engrish. It didn’t work right, it was hard to follow what was going on in the code, and trying to fix it just made it uglier.

Normally, when I’m writing code it’s kinda like sculpting with clay or Play-Doh. I start out with a rough idea of what I want and gradually refine it, mushing chunks of logic around, whittling away bits I don’t need. I can see it taking shape. My understanding of what’s going on, the scope and nature of the problem I’m solving, gets clearer and clearer. This code was just getting messier. It felt more and more like a duct tape and bailing wire job. Even more than other programmers, Lisp people go on about the elegance and clarity of their code. So I gave up for the evening and went to bed pondering how to make it “Lispier”, maybe really work that recursion thing.

In the classification of programming languages, Lisp is a “functional” language, as opposed to an object-oriented or procedural language. The distinctions are a bit blurry, but they’re about how the language encourages you to organize your code and suggests the terms you use to describe the problem you’re dealing with. Like I said, vague, but programming is fundamentally an act of communication, so the mental constructs you bring to it are important.

Programming languages all have nouns and verbs: Data and things you do with the data. Procedural languages focus on the verbs, the procedures. You’re stepping through a process; it’s linear. Procedures are broken down into sub-procedures, but it’s still all about what you’re doing as you step through the process. You have data structures, but you’re kinda just trundling them along through the procedures like a shopping cart.

Object-oriented languages focus on the data, how it’s organized. The verbs are “methods” tied to the data, what you can do with it. Methods may do things with other objects, but they’re defined in terms of the thing doing it.

Functional languages are a little harder to explain. Rather than the steps of a process, they focus on the start and end points, what you put in and what comes out; results, not actions. That isn’t really how people think. We tell stories; we make sense of the world through narratives. But while it’s not entirely natural, the functional way of thinking can be useful because it forces you to focus on what you’re trying to accomplish.

The other part of “Lispy” code is its focus on handling lists of data recursively. You define a function that does something with the first element of the list, then applies itself to the rest of the list. Rather than

new_list = []
for thing in list:
    new_thing = do_stuff(thing)
    new_list.add(new thing)

You do something more like

(defun process-list (list)
  (list (do-stuff (first list))
        (process-list (rest list))))

process-list is a function that calls do-stuff on the first thing in a list, then calls itself on the rest of the list, and gloms the results together to make a new list. Weird way to do things, huh?

Anyway, in my case, I’ve got a node and a list of lines that are all either children or siblings of that node. Once you break the list into those two chunks, you just create a child and a sibling node, and hand them their lines to process. Your output is a list of the siblings, with you in the front. Your child hands you back a list of its siblings, your children, with itself in the front. Your sibling gives you it siblings (which are also your siblings) with itself in the front. By the time they get back to you, all of your siblings and children already have their siblings and children.

That’s a very clean, mathematical way of thinking about it, but it’s seriously non-linear. The Ruby code built its structure in order, “a” through “l”. The Lisp code built it in the following order: d e c b i h k j g l f a. It processes the children from the deepest up, and the siblings from the last to the first. Not intuitive.

The experience of programming Lisp ended up being a lot more like doing math than sculpting Play-Doh. I had to step away from the keyboard and just think about it for a while. But when I figured it out, everything just snapped into place. It wasn’t the gradual refining and polishing of an idea; it was like solving a puzzle. When I hit on the solution, I knew I had it. I felt it in my bones.

So it was a good learning experience. My hope was that Lisp would force me to think differently, and it did. The Lisp program I came up with is fundamentally unlike the Ruby version. (You can see the Ruby code here and the Lisp code here.) I think I’ve kinda wrapped my head around this functional programming approach. That, more than Lisp syntax, is the potentially useful bit.

The thing about functional programs is that they’re much easier to break into seprate processing chunks, whether you’re running them on some Google-grade cluster or compute cloud, or just on a multi-core chip. There’s a lot more demand for that kinda thing these days. The Ruby version of my code has this central tree structure that it adds onto line by line. There isn’t any way to farm that work out to a bunch of independent processes. In the Lisp version, at each node you’re splitting the work into two batches, children and siblings. You could distribute it naturally across as many processors as you have nodes. Each just has to get its set of lines to process, and the tree comes together in this non-linear way as they return their results.

I’ve always been all about code as a communication between programmers, rather than just a way of telling the machine what to do. Lisp doesn’t do so well on this count. It’s certainly not as friendly to the novice programmer. One of the things I love about Python is that pretty much anyone who knows how to program can read it – it looks like pseudocode. That’s so not true of Lisp. The syntax, with all those parentheses, isn’t like any other languages. It makes no sense at first, and takes a good bit of getting used to. (To be fair, it was there first.) But the harder thing is shifting to a new set of ideas and customs. Early on (and occasionally still) I would try to do something that should be simple and obvious, but in Lisp they just don’t do things that way. Like any foreign language, it’s much harder to write than to read, and the idioms are harder to learn than the grammar.

But again, like any foreign culture, once you spend some time there, you get used to it and it starts to feel comfortable, even normal. Recursion goes from being alien and academic to highly practical. All the crazy parentheses actually feel like a more logical and coherent way of grouping functions. And when you come home to Ruby or Java or whatever, you bring a little bit of all that with you.

Business Process Automation

January 24th, 2011

If you’re not familiar with the term, it probably sounds like some marketing bullshit, but it’s actually a good shorthand description of one of the ways that software can be insanely useful. To break it down: “Business process” is a blanket term for all the things that people have do at work to get something done. You’ll have a business process for setting up new customer accounts, fulfilling an order for widgets, or whatever. The “Automation” part is about writing software to make this more efficient. So “Business Process Automation” covers any software that makes people’s jobs easier.

That doesn’t mean replacing people with machines. It’s about letting the computer handle the tedious, repetitive crap, and freeing people up to work on the more interesting stuff. In almost any business process, there will be some amount of straightforward bookkeeping that a computer can handle; but there will also be a need for judgement and common sense, and the ability to deal with ambiguous or unforeseen situations, which computers are fundamentally incapable of.

The simplest, most common example of this is spreadsheet software. A computer can’t tell you what numbers and formulas to put in, or what the results mean—what’s important, what action to take—but it can save you the hassle of re-doing the math every time something changes. It’s a power tool, like a band saw or a nail gun.

The first time this was really driven home for me was years ago, when I was working at a little web development shop. I was chatting with a friend of mine who was a designer there, and she was griping that she’d gotten stuck with this crappy assignment. One of our clients had these tables of financial data on their site that had to be updated every month. They sent the new data to us in a PDF document. Her task was to copy the data from the PDF into HTML. So she opened up the PDF in one window, and the HTML source in another, and copied it one entry at a time: click, drag, ctrl-c, click, ctrl-v; for row after row, table after table. She’d just finished the first batch of this, and it had taken her nearly two full days. Absolutely mind-numbing, and she was going to have to do this every month.

She told me all this, and I said, “You did what? No, that’s crazy; don’t do that again. Give me a little while.” I went off and found a utility to dump out the PDF as text, then wrote a Perl script to parse the data out and stuff it into an HTML template. It took me maybe a day and a half. Now, each month, she just had to run the script and spend maybe fifteen minutes proof-reading the pages it spat out.

This is a tiny example, but it demonstrates the alchemy you can work with software. I got to do this fun little side-project; I freed up nearly 10% of her time, so she could do more valuable work for the company; and I made her job way less sucky. Everybody wins.

Business Software

January 20th, 2011

I’m a programmer. I write business software. Programmers hate writing business software. It’s not cool, and it’s hard. Programmers won’t come out and say that it’s hard; they’ll use terms like “messy” or “uninteresting”. It’s not hard for technical reasons; it’s hard for human reasons. And we, on the whole, are not good with humans. I’m not great with them, but I’m increasingly of the opinion that they’re more interesting than machines.

Let me give you a definition of Business Software that’ll shed a bit of light on the situation: Business Software is software that isn’t used by programmers. It’s used by non-technical people, suits. It’s not useful to us. We don’t care about it. Programmers use programming tools and play video games; end of story. In fact, if the suits think it’s great, that’s a sign that it sucks.

Since we don’t use business software, we don’t know what it should do, whether it’s working right, or how to make it better. There isn’t a good, objective definition of what it’s supposed to do; it’s “whatever the user wants.” Sometimes, it’s based on bizarre business, organizational, historical, or legal requirements. There’s no way to reason it out. If you try, you’ll often find out that your perfectly logical conclusion is in fact disastrously wrong. So we have to ask the users how the software needs to work. That means sitting in meetings. With suits.

Since the users aren’t technical, they can’t just tell you what they want. They probably don’t know, themselves. They don’t know what the limits of the technology are. They have no idea what’s feasible. They ask all sorts of really dumb questions, and expect the impossible. They’re not good at visualizing how they’ll actually use the software. They’re usually wrong about what they think they want. And they will change their minds. So you have to bridge that gap, and you don’t get to just meet them halfway. They might be able to learn a few basic technical things, but you need to learn a lot about their business. So now you have to be the one asking a lot of dumb questions.

So just figuring out what your program needs to do is the really hard bit. You’d think that after suffering through all of that, you’d at least get to do something really cool, but no – the technical solution often turns out to be fairly straightforward, usually something involving a web server and a database. I think that’s why there’s such frantic innovation in tools and frameworks for building web applications: There are all these programmers out there trying to make the technical work interesting.

In fact, to write successful business software, you have to make it deliberately uncool. You don’t use development builds of cutting edge tools and elaborate frameworks; you use simple, stable tools that lots of other people know how to use. In business software, you’re really trying to program yourself out of a job, to make yourself replaceable. You’re trying to take all of this business knowledge, and embody it in code. I’ve heard programmers brag that the guys who came after them weren’t smart enough to maintain their code. That’s completely backwards. If you’re really good, anyone should be able to pick up your code and understand what it’s doing and why. Code is communication, the expression of an idea. Your code should make all of the complex business logic clear and precise. If you’ve done really well, you can even walk non-technical people through it and give them a better understanding of their own business. If other programmers can’t work with it, you either didn’t really understand it, or you didn’t communicate it clearly.

“Legacy code” is a term of distain. It’s shorthand for “crusty old software written in some boring language on an obsolete platform.” In practical terms, it’s anything more than about 6 months old. Real legacy code can even be decades old, written back in the days of Big Iron. It’s been tweaked and stretched and hacked up ever since. It has years of business logic layered on like shellac. To work with it, you have to waste valuable brain space learning about how people did things before we Figured It Out. If you’re really skilled and really lucky, your reward will be that your business software becomes legacy code. It’ll become critical to the business and they’ll use it for years to come. The fullness of time will expose all of the mistakes and misjudgements that you made. You will learn humility, and it will make you a better programmer. It’s a tough love kinda thing.

So why do I write business software? Because I like people. I like trying to figure them out. I like trying to get my head inside their world. All of that stupid, illogical business logic? Most of it really does make sense once you learn the context and history of it. I like that it’s unintuitive; I like that little jolt of surprise I get when I learn that the world is more complex than I’d thought. I also like being useful. Just on the level of pure self-preservation, I figure I’m better off being useful rather than just clever. But I also like the feedback. I get all kinds of warm fuzzies from writing a bit of code that makes someone else’s life a little easier. I’ve come to the conclusion that I was put on this earth to program the Suck out of people’s jobs.