The following code is for a function called metacadr, which takes an argument in the form of “c[ad]*r” and returns a function that will traverse a linked list, for which the payload of some nodes may themselves be linked lists, creating a linked tree, and return an arbitrary value from an arbitrary node.  This code is in coffeescript, but if you read javascript, it’s pretty readable. The function car means “Give me the value of this node” and cdr means “Give me the handle to this node’s next node.”

metacadr = (m) ->
  seq = m.match(/c([ad]+)r/)[1].split('')
  return (l) ->
    inner = (l, s) ->
      return nil if nilp l
      return l if s.length == 0
      inner ((if s.pop() == 'a' then car else cdr)(l)), s
    inner(l, seq)

I wrote several unit tests with empty lists, simple lists, and tree lists, and all of them reported this function was fine. So when I began to use it and the library it supports in production, it immediately created wild errors deep inside other pieces of code. Can you tell what’s wrong with it?

The unit tests only ran metacadr() once per try. It was only trying to assert that the function it created would process its sequence of arguments correctly. What I didn’t test was this: did the function returned behave correctly when used multiple times?

You see that .pop() in there? It’s a disaster waiting to happen. It’s not a traversal, it’s a mutation. Worse, it’s a casual mutation in a language that always (always!) uses pass-by-reference. When I call inner(l, seq), I kinda expected seq to be copied, but it wasn’t; only the reference was copied. I expected I was calling .pop() on something safe and reusable, but it had a handle on my original sequence, which it destroyed. The function returned by metacadr only worked once.

Lessons learned for Javascript:

  • Casual mutation and call-by-reference are deadly together
  • Using .pop(), .push(), .shift(), .unshift() is almost always the wrong thing to do
  • If your function returns a function, you must test the returned function multiple times to make sure its behavior isn’t self-destructive

In case you’re wondering, the function now looks like this:

metacadr = (m) ->
  ops = {'a': car, 'd': cdr}
  seq = vectorToList (m.match(/c([ad]+)r/)[1].split(''))
  (l) ->
    inner = (l, s) ->
      return l if (nilp l) or (nilp s)
      inner ops[(car s)](l), (cdr s)
    inner l, seq

Improvements: I’ve replaced the ‘if’ expression with a lookup table. This removes a problematic codepath and encourages more defensive programming. By using a linked list I’ve correctly created a traversal sequence that is non-destructive.

I could have gone with an iterative solution, keeping an index, and all the usual Javascriptiness, but for me, this is the elegant (and hence correct) solution.

Over at Chris Parnin’s website there’s an article that explains why you should never interrupt your programmer, but the real issue is encapsulated in Jason Heeris’s famous cartoon, and if you’re not going to bother clicking over there, the gist is this: it shows a developer looking at a single ‘if’ statement, from which she imagines, slowly, piece by piece, an enormously complex mental idea of what the code is supposed to do, of pieces of the code interacting in one correct way, all the modules communicating with set flows in a pattern that produces an outcome. In the penultimate panel, someone interrupts her with a trivial matter, and in the last she’s back at the ‘if’ statement, starting over, the scaffold gone.

Every part of that cartoon, and the associated article, is a mistake. It’s not a lie: everything that article talks about is completely and utterly true; in modern development environments, knowing the state of a single byte can require one contemplate, to an absurd degree, the meaning of very large systems. Object-orinted programming was supposed to alleviate this problem by having every object be its own, independent unit of knowledge, communicating with neighbors and siblings through well-defined and very small communications channels.

It didn’t work out that way. We weren’t disciplined enough to make it work that way. Instead, we would up with UML and RationalRose and ad-hoc Yourdonesque entity relationship diagrams and codeflow systems that try to specify the system in the large, and leave it up to the individual developer to remember, to the absurd degree shown in the cartoon, all the conditions that make the state memoized by a given object relevant and meaningful.

I’m not that smart.

No, really. I’m an average programmer whose favorite game is finding the right tool for the job. Time and again, my experience has shown that the right tool is one that constrains the problem to four lines of code, and constrains those lines further to function calls with type signatures that ensure the code is passed between them correctly. In 99.94% of programming, we only ever do four things:

  • receive
  • validate
  • transform
  • emit

That’s it. If you think your code does anything special at all, you’re probably wrong. You’re as likely to be doing something not on that list as you are of select() being broken (and hint: select() isn’t broken).

Every web page is like this: your server gets a request, you emit a page. You get an event, you emit a new DOM fragment that updates the page. Every video game is like this: you get a joystick event, you emit a new game state with your dude’s jump variable set, your starship’s turn rate updated. Every clock tick is just something you received and have to transform into a new view for the user. Sometimes, what you receive has to be combined with other data extant to your system, but that’s merely part of the validation and transformation.

Four lines of code, each leading to a different function that performs its responsibility. Each function completely testable. Each function correctly constrained, either by its types or its contracts or both.

Even I can hold four lines of code in my head.

You still shouldn’t interrupt me.  Those four lines describe specific issues that I do have to hold in my head.  They’re easily spec’d, and easily written, but they still require a lot of thought.  By realizing that all programming comes down to these four steps, and that every program is actually an amalgam of several different sequences of these four steps, I’ve been allowed to think one step higher.  But I’m still thinking at the limit of my ability, so don’t interrupt.

19May

There are no good naming conventions.

Posted by Elf Sternberg as Uncategorized

The other day I was working on a DSL (Domain Specific Language), for which I had a complete AST (Abstract Syntax Tree). The AST used nested arrays to represent the tree structure, and each node of the tree structure was itself an array, with positions in the array representing the array type and payload, the second element of which could be a leaf value or an array of more nodes. I was working in a dynamic language (and, given my description, you may be able to recognize which one), so I had no type safety; arrays were arrays, and interpreting whether one meant “part of the tree” or “part of a node” was entirely segmented only in the developer’s brain, and not by any syntax checking compilation pass.

As a convention, the entry point for a function that determines what any given AST “means” has the following signature:

result = evaluate(expression, environment)

Pretty much since 1959, every interpreter that reads and processes a DSL has a function with those four variable names, “result,” “evaluate,” “expression,” and “environment.” The expression is the thing you’re about to interpret; the environment is the current scope, local and global variables, the context in which the expressing is going to be interpreted and evaluated. I’ve seen this signature over and over, in every book on compilers and interpreters I’ve ever read.

Because it’s a convention, I thought nothing of it. Because a list of expressions is itself an expression, the variable name for either state was expression. Because of the weird nested arrays thing (totally not my fault; I blame Christian Queinnec), when there was a bug in my program the state dumps were unreadable and hand-tracing the excution was mind-boggling. I was getting lost in “What does this mean?” over and over. It’s a fairly small interpreter, so getting lost in that little code was a bad sign.

There is a principle in Python that a public variable name should reflect usage and not implementation. But the more I struggled with the issue, the more I realized that distinguishing between the two implemented types made my eyes cross, and if I changed the names to distinguish which was which I could make sense of what I was reading. I changed “expression” to “node,” and where I was managing a child collection I changed it to “nodes”.

That made all the difference. I was now able to see which array was of what, and was able to debug the broken operation.

I then went and changed “node” and “nodes” back to “expression” and “expressions”. Because that was a historical convention, I felt obliged to honor it, and if someone else encountered my code I wanted them to see the “what” and not the “how.”

This led me to three important realizations.

  1. There is no such thing as a good naming convention. There are only good naming habits. When implementing a well-known algorithm (in this case, the classical interpreter phase “reduction of expressions”), it may make sense to follow historical examples to continue tradition. But more importantly, it is important to name things clearly. Naming things is supposedly one of the two hardest problems in computer science. Work hard on good names.
  2. Change your names to reflect your current issue. If you’re implementing something difficult, feel free to use Hungarian Notation if it gets you through the problem.
  3. Don’t leave it that way. Having done whatever was necessary to get the code done, now go back and change the names back something that reflects both the public API and the future maintainability of your code.

10Apr

Software development needs copy editors

Posted by Elf Sternberg as programming

Magazine, newspaper, and book publishing, in both fiction and non-fiction, all have two specialized roles that the work goes through before it reaches it’s final form:

The Project Editor and the Copy Editor.

Software teams have a project editor, although usually he’s called the project manager. In literature, the project editor doesn’t usually edit; his responsibility, like that of the project manager, is to see the work go from manuscript to bound volume, and is responsible for schedule, budget and the interaction of other departments such sales and marketing, in order to assure the success of the work.

There is no job in software anything like the copy editor. And that’s a problem.

Linters and style checkers can make sure that you have the right number of indentations, ensure that your line length fits into the house editor, check you have comments where comments are required. What they can’t do is ensure that your variable names have meaning, that your classes are SOLID, that each function does one thing and does it well, and that a future maintainer can look at any given piece of code and not say “WTF?”

Every creative profession that works on a commercial production line, that is treated as a craft, has an editorial pass. If you’ve ever worked in advertising, there’s one guy whose job is to make sure the studio musician is creating background music that matches the taste of the ad; there’s also someone who makes sure that every background image in an animation matches the overall feel of the production. These aren’t “I know it when I see it” jobs, either; these are people who are expert studio musicians and illustrators who have earned the trust of their peers and graduated to the role of guiding others to excellence.

Every creative profession except software. Software developers are a weird bunch: the good ones are absolutely ready to take criticism from their peers, as they want to get better. The bad ones believe that “it passes all the tests, so you shouldn’t care about its style” and you can’t tell them anything at all. Given just how much money is sloshing around this industry, any change to impose more discipline is opposed with ferocity. We all have someplace else to go.

Software copy editing would be a line job; it wouldn’t be management, and yet it would have the final, human-eye check on whether or not something goes into the repository. It wouldn’t be about if the code is testable; it would be about if the code is maintainable. Can a future code monkey at a glance see what you meant and how you acheived it? As a line job, it would be dependent upon the productivity of others to succeed, yet in agile the editor would have no velocity himself.

There are tons of anti-patterns that are opposed to this idea:

  • “I don’t want to pay some guy just to sit around and read code.”
  • “Testing will find all the bugs.”
  • “The next revision will be a complete re-write, so code readability isn’t an issue.”

I’m sure you could name more.

But if you really give a damn about code quality, and your company has more than twenty developers, consider hiring a software copy editor, a hands-on, polyglot programmer with an opinion about how software should be written, who has the chops necessary to gatekeep your code quality and mentor your junior developers.  You’ll save more than you spend: a good copy editor will reduce your need for testing cycles; the whole point of the job is to ensure no code escapes your office that isn’t clear, sane, readable, testable, and maintainable, and to teach those fresh-out-of-college faces how code in the real world looks.

09Apr

SMART goals and Petered principles

Posted by Elf Sternberg as Uncategorized

List three to five goals for the next year. These goals must be SMART (Specific, Measurable, Attainable, Relevant, Time-Oriented). Include both those goals that would help you in your current role as well as those that prepare you for future roles in the organization.

Few work-related things fill me with greater dread than this annual question. And I’ve gotten it at every job I’ve ever worked at where there were more than a hundred people.

I’m a programmer. In every position I’ve ever worked, I was hired on the basis of a skillset I had at the time. Spry hired me because I knew Perl when Perl was barely a year old; F5 because I knew Perl and Curses; Isilon because I knew both kernel development and web application development at a time when both were truly esoteric; Canvas because I knew both Django and assembly language; IndieFlix because I knew Django; Spiral because I knew Single Page Development when that was brand new; CK12 because I knew web development and the EPUB 2.0 standard.

While I was there, other problems became apparent to me: Spry needed me to learn both C++ and Python; F5 needed me to learn Lex & Yacc; Isilon needed me to learn server development; IndieFlix needed me to take my hobbyist-level transcoding skills and go professional; CK12 needed me to learn WebGL. None of those needs were apparent until they were immanent. It’s not as if I could scan the horizon of issues and see, “Months from now we’re going to discover that this rendering technique won’t work on an iPad without WebGL” or “Months from now, we will discover that the application server needs an ‘always on’ userspace component for consistent kernel communication; I’m going to need to know how to write one of those.”

Questions like the one above imply a kind of restlessness that can only be cured one way: with money. The idea is not that you want to be great at your job; the idea is that you want to be great at the job that leads toward ascension, and in most corporations the only ladders available lead away from a lifetime of training and experience toward “leadership.” I have deep respect for good leadership, and I hear the siren song that says, “You have all these skills; your duty is to help others achieve the skill level you have.”

Given the level of interpersonal skills I have, I ultimately end up wondering: “If they achieve the same skill level I have, does that mean you’ll Peter them too?”

As a software developer, I love learning new things. I’ve been studying a couple of things at random: Category theory, type systems, interpreter cores; basically, a lot of meta around the lambda calculus. Along the way I learned a little Haskell, and learning even a little Haskell made me a much better programmer. The odd thing is that few of those interests map to those of my employer; usually, they don’t want esoterica, they want better in the realm in which they work. It has been my fortune to have “significant advanced skills” in customer-facing engineering; it’s my misfortune to realize that I’ll be working in the same four damn languages for the rest of my life if I want to keep making the same salary.

I have only one goal: Get better at what I do. Everything else is commentary.

05Apr

A-hah! learning and Grind learning

Posted by Elf Sternberg as Uncategorized

I have two modes of learning, and one I enjoy, and one I resent mildly.

A-HAH!

“A-hah!” learning happens from time to time while I’m working through a larger problem in my head. One might call it the holistic learning moment; I’m reading a textbook or paper and suddenly I get it. I not only understand what the author is trying to say, but I get the ramifications of it. This happens a lot when I’m reading about type systems and it clicks for me that a type system is an additional language, with it’s own strengths and weaknesses, that helps the developer say what the program means, and more importantly, lets the programmer talk about the genericity and applicability of his code. These come in a flash, as if several different bundles of neurons that had been slowly growing toward each other suddenly connected and something suddenly makes a lot of sense.

The Grind

“Grind” learning happens when I have to learn something that should have been an “a-hah” event but wasn’t, and I have to repeat the lesson over and over until I internalize and understand it. A recent example is in my Language in 20 Minutes exercise. the hardest thing for me to get was the difference between dynamic and lexical scoping from within the interpreter. I had to write, rewrite, and rewrite again the way a functions’s free variables are informed by its lexical scope (the closure), and the way its bound variables are populated by values found in the current execution scope.

In some ways, the second problem was informed by the idea that I didn’t even have the notion of “bound” and “free” variables in my mind until I started reading up on the lambda calculus and trying to grok what it means and how it works. But even though I do have those terms now, it’s been difficult for me to internalize the ways of lexical and dynamic scoping.

It doesn’t seem to be a matter of problem size. The LangIn20 project is very elegant and doesn’t have many moving parts. SparQL is a large project that has a lot of moving parts; both were grinds to master.

I wonder what, in particular, contributes to a problem being an “A-hah!” versus a grind, and if I can turn more of the latter into the former.

This may be an idiosyncrasy, but I doubt it, because I see too many examples of it in open-source code all the time: I have this strong suspicion that software developers think too holistically. There’s even a rather trenchant and famous cartoon illustrating how a developer loses context with a simple interruption and has to rebuild the scaffolding of his thoughts before he can fix the issue.

I had this problem recently. I’ve been noodling with a small lisp interpreter that I was building as an exercise, and one of my steps was to write a lisp-like “cons” list library, recodify each node from a record-in-a-vector to lists-in-lists, and then build upward from there. My target language was Coffeescript. There are three major components to the interpreter: an eval() function, the environment, and the syntax.

Special forms are injected into the environment at initialization time, and obviously both the “define function” and “if” statements need to be able to call eval() to evaluate their arguments, since this is an interpreter that works its way to the bottom of the AST and then evaluates upward to a final result.

As I was making the changes, I got terribly lost making the special forms respond to cons lists rather than vectors or dictionaries. The structure of a node from the reader became (type value blame), where a value would be a cons list of nodes when type became “list”. The distinction between the two types became muddled in my head, and I kept worrying about what it would mean to switch to the other phase of processing.

And then I realized: I should stop worrying. Everything I needed really was right before my eyes. Knowing the code in front of me, I could easily reason about everything I was doing right then, right there. This data structure would get handed off eventually, but I shouldn’t care. There shouldn’t be context above and beyond what’s on the screen.

I think this is why I’m really starting to like F# and Haskell and that family of languages so much. (And Lisp, really); I shouldn’t have to think that hard, I shouldn’t be spending every day at the utter limit of my human understanding just to get my job done. I know, that’s the holy grail of development, yet I’m convinced that it’s not only a reachable goal, it’s one we perversely avoid. We’re proud to plumb code through multiple layers when we ought to be ashamed of it.

I think we ought to consider the baseball bat as a unit of code quality: if the code is so hard to understand the next guy will want to come after you with a baseball bat, maybe you should consider re-writing it.

My first impression was , “What a fucking bunch of greybeards.”

I went to Beerly Functional, a get-together of down-in-the-trenches programmers who were either using or interested in using Functional Programming, and my first impression upon walking into the room was exactly that: What a bunch of fucking greybeards, myself included.

And yet, as I paid attention to what was being said, the reason why we were all there became more and more apparent. We were tired of dealing with lousy development cycles. The biggest promises of Functional Programming are that it narrows the gap, both temporally and spatially, between where you create the bug and where it manifests. Functional programming emerges from the needs of lifelong programmers to stop fucking around with code-run-debug cycles; they want to produce excellent code the first time; they’re willing to adopt strong constraints on shoddy thinking and poor code in order to avoid that. They want to make software that gives a damn. They want to make software that they are comfortable saying, “This cannot fail.” They value quality and correctness, whereas most business people… don’t know how to assess that question, and they see the rapidity and widespread availability of developers in the shoddy languages like PHP and Javascript as signs of those language’s legitimacy.

So we raised a glass together, and we took on our missions: to teach each other what we knew, to get better at our craft, and to sell it to businesspeople who need to know there’s a better, faster way to get quality code in front of consumers.  We were greybeards; lifelong programmers who, whether we’d made our millions or not, wanted to keep making great code, not graduate into management and executive by 30.   We wanted to be the best.  And we knew the tools were within our grasp.

18Mar

Working around the feeling of cheating…

Posted by Elf Sternberg as Uncategorized

This is just going to be random.  Don’t expect it to make sense.

The obvious next steps in my Scheme are: Strings. A Common Lisp 22.1.1  compliant hand-written parser, as a prologue to re-writing it in Scheme, where the record objects used in Coglan’s version are replaced with cons list of the various fields being collected.

Macros.  And that’s where my brain comes a screeching halt.  Because “macros” seem to imply a certain purity of lispyness.  How do I make a Lisp macro engine that successfully handles, and yet successfully ignores, all of the extra stuff after the content?

Maybe I don’t.  Maybe I just write it so that it accepts all that, and more, because ultimately I want to add a deterministic more to the list to carry typing information.

Grief, I have no idea at this point.  I just know what I want it to be able to do next.

16Mar

They lied to me in university…

Posted by Elf Sternberg as Uncategorized

As revealed last time, my university training was focused on a business degree with a programming minor, the point of which was to prepare me for being a dark programmer in some basement of a bank or other financial institution. There was an actual track for this at my university.  As such, my instructors told me not to worry too much about data structures; I didn’t need to know about trees, linked lists, and deques.

They lied.

I thought, since I’d done the exercise, that I was done with A Language In 20 Minutes, but this morning I had an inspiration and so, on the commute into work, I hacked out a new version that’s available on Github. It’s more “functional,” as I said, for some definition of functional.

But what I did add was a Lisp-like list class that behaves more or less like a Lisp cons list: A linked list of two cells, the second of which points to the next cell. Like so:

[(data:C), (next)] -> [(data:B), (next)] ->
[(data:A), null]

These lists start out with just the ‘A’ entry; when you cons an entry, it looks like: cons(D, list), and it would add a ‘D’ entry to the “head” of the list. The amazing thing about this structure is that you only have access to the head, but through it you have access to the whole list.

Amazing.

Really.

When you’re describing the scope of an operation for an interpreter, you still need a traversible, ordered collection of scopes that go all the way from your deepest scope to your root in order to ensure along the way that every variable is defined, and add new variables to your current scope as needed. When you create a new scope in your interpreter, you do it in a given function call that will interpret expressions within that scope. When you leave that function, you need to expunge the memory allocated for your scope. So let’s say that the D object mentioned above is a dictionary for resolving variables in the current scope; by consing it onto your list, you can now traverse the scope, checking all the dictionaries down to the root automatically.

And when you leave the scope, the D object and its list reference get reaped. You get memory management for free.

Admittedly, that’s only true because Javascript has its own memory management going on, but since lots of practice projects involve writing an interpreter on an interpreter, that’s often going to be the case. But it’s a good starting point.  And understanding the principle means that you get to apply it later if and when you decide to write this thing in C++.

The dirty secret inside Coglan’s example (see the first commit to my github) is that his Scope object is a cons list; it’s just a very informally defined one, using the parent field to point to the next cell, all the way down to the “TopScope.”

And, if you look at my javascript, I don’t call things the way most people do. You might write car(list_object) to retrieve the data from the current list object, but all throughout my code I use, in Coffeescript, (car list_object), just because Coffeescript lets me. I’ve created a Frankensteinian example of Greenspun’s Tenth Rule of Programming.

Recent Comments