“If you can’t explain it simply, you don’t understand it well enough.” – Albert Einstein

This quote annoys me. I’ve spent the last year trying to understand functional programming and this deep, mathematical concept called the monad. It turns out that monads are simple to explain: if you’re mathematically inclined and know your category theory, they’re a monoid in the category of endofunctors. If you’re a programmer, they’re a pattern for the augmentation of function composition.

Since I’m a programmer, the latter explanation appeals to me. (I’m also a mathematician, and I know what all the words mean in the theoretical explanation, but I don’t understand them well enough to use them effectively.) For your basic Python, Ruby, or Javascript developer (nevermind, shudder, PHP), you have to start with explain what function composition is, how you already do it without having a word or even a concept for it, why you want to do it more, how you work around problems involving collections and sequences, and then you have to explain what you mean by “augmentation,” and what it buys you, and how it fits into your existing mental framework of designing and writing software. I’ve been working my way through a series of exercises that have helped me understand what “augmented function composition” is and does for me.

But it took work. It took a lot of work. Even with twenty years of software engineering experience, it took hours of hammering away at the problem, day in and day out, for me to even start to see the benefits of using this pattern. I’ve now got a fairly solid understanding; I’m hoping to apply it to some personal projects in the hopes of reducing my error rate and speeding up delivery.

Lots of people have tried to “simply” explain monads to me. But to understand them, I had to put in the effort. I had to put in the hours. I had to do the work. Sometimes, no matter how well you understand “it”, no matter how simply you explain “it”, your audience simply doesn’t have the knowledge, the mental framework, necessary to understand what you’re talking about.

And some people, no matter how hard they try, will never have that framework. They don’t have a mind capable of grasping it. We would never ask Sarah Palin to try and understand multi-dimensional vector maths; she hasn’t got the mind or temperance for it. It’s not even that she won’t, it’s that she can’t. By nature or nurture, she hasn’t got the headaround for it, and never will.

It’s not about understanding or simplicity; it’s about your audience’s capability and willingness to comprehend.

23Jul

The Metadata Problem in Primitive Lisp

Posted by Elf Sternberg as Lisp

Yep, I’ve definitely gone down the wrong path with my current research project, which means I’ve probably wasted at least a day or two on it, which I find deeply frustrating.

As I’ve been working my way through Lisp In Small Pieces, I’ve been trying to push the boundaries of what the interpreter does in order to make it seem more, well, “modern” to me. The target language is Javascript, both in the interpreter and in the transpiler; I ultimately want to end up with something similar to Gazelle or Pixie, but with even more facility. The laundry list is very long.

The problem I have right now is Sourcemaps. Sourcemaps are a tool supported by all major browsers and Node/Iojs, that translate error conditions that occur in the running code into near-equivalent locations in the original source files. This was meant to support minimizing features like uglify or Google Closure, but it turns out to work just fine for transpilers.

The problem is three-fold: (1) the original Lisp syntax doesn’t support the carriage of metadata along with processing the the source, (2) Lisp macros mangle the source in unhealthy ways, (3) including the metadata necessary to support Sourcemaps makes the reader unsuitable to use as a general-purpose list-processing (i.e. “LISP”) utility for users.

I thought I had a solution using Javascript’s non-primitives for String and Number; that would have let me carry the values forward successfully. Unfortunately, the Javascript non-primitives are not automatically self-evaluating; (new String("foo")) != (new String("foo")), so comparisons and utility at run-time are severely impacted. Expectations are not being met. I know why this is the case, I’m just not happy with it.

An alternative is to encode the reader to pass back the sourcemap as a second AST, and have the reader traverse that as needed to report on state of the compilation.

The problem is that this is a cross-cutting concern, an aspect-oriented problem. Tracking which branch of the AST you just went down, or how far along the linked list that represents that branch, is not easily instrumented in Javascript. I want the evaluate core to operate as McCarthy described in 1959, but if run in a different context (oh, look, a monad!) also returns me optional sourcemap details about the evaluation pass.

I’m going to spend some of today reading through other folks’ solutions. The non-Lispy javascripts are no help; they have their own paradigms for ASTs that don’t involve the self-modifying capacities of Lisp.

15Jul

The Key To Coding is Re-Coding

Posted by Elf Sternberg as chat, programming

In a recent, great article in the New York Review of Books, “The Key to Rereading,” Tim Parks takes the usual metaphor of reading as “the mind is a key unlocking the meaning of the text” and turns it around:

The mind is not devising a key to decipher the text, it is disposing itself in such a way as to allow the text to become a key that unlocks sensation and “meaning” in the mind.

Parks also asserts that this unlocking process isn’t achieved upon a first read, but upon re-reading. Once, again, and again, and again.

The astonishing thing to me at least is that anyone actually needed to say this. Every person who lives in the world of mathematics (and computer science is a branch of mathematics, although if homotopy theory is correct every branch of mathematics is in fact a subset of computer science theory) knows this beyond any shadow of a doubt. I hinted at this earlier is my article “A-hah! Learning and Grind Learning,” after which someone said to me that the “A-hah!” moment only comes after the grind, that you’ve spent all the intellectual energy necessary to push the neurons into the right pattern, after you’ve felt those neurons reaching out to each other, after the whole of the pattern coheres after hours and hours of study and research and experimentation, there’s this sudden “Oh! That’s how it works!” moment.

Reading papers, writing code that does what those papers describe, tracing the meaning of that code as it does what it does, all leads to that moment when the key turns in the lock. When you get it. I liken it more to knowledge beating down the doors inside my head, relentlessly creating meaning where once there was none. That’s a slightly more violent metaphor than Parks’s, but it comes down to the same thing. The knowledge isn’t really in either the book or in your head. It’s when you’ve done the same exercise twice and in different ways that the noise of syntax and source code fades into the background, and the glittering beauty of the lambda calculi, or the sheer messiness of ad-hoc continuations like try/catch/finally, become utterly clear.

The other day, Jim Bird wrote a pretty good article on why there’s so much bad software out that, and the article laid the blame on bad managers. While I think Bird’s approach is correct, he’s actually missing one critical detail.

It’s not always that managers are “bad.” Bird’s list of badness include poor planning, failure to test at each level of development, failure to talk to customers or put prototypes and minimum viable products in front of them, failing to follow best practices, and ignoring warning signs.

Bird concludes with: “As a Program Manager or Product Owner or a Business Owner you don’t need to be an expert in software engineering, but you can’t make intelligent trade-off decisions without understanding the fundamentals of how the software is built, and how software should be built.” Which is completely contradictory advice, because I think you do need to be, or hire, someone who can deep dive into the engineering production pipeline.

The practice of the “five whys” says that asking “Why did this happen?” through five layers of reasoning will bring you to the actual root cause of the problem. There’s an old joke that states that the fifth why is always some variant of, “Because we were lazy.” The Wikipedia article linked to actually ends with an example of that!

But I think laziness is the second most common problem in software management. The most common problem is fear.

This is most obvious in the high-tech corridors of San Francisco and Seattle, but it’s true everywhere. We’ve created a perverse incentive structure where the best way to move up is to move on: the quickest way to get a raise in this business is to leave your job and move on to a different job. Poaching is widespread and pernicious.

On the other hand, managers are terrified of losing people. Hiring well is hard,and losing an employee means losing whatever institutional memory they had built up before they left. Along with the pressure of producing software, they have to know that their developers could flee at any moment. So managers are willing to let some things slide if it means they’re able to hang onto their “10X” developers: they’ll ignore standards and allow redundant, dead, unrefactored, cut-and-paste, poorly abstracted, globally defined, untyped (or worse, “Any” typed), uncontracted, YAGNI, lacking test coverage code. Managers who have been out of the coding loop too long or who are unsure of their position lack the backbone necessary to tell developers, “Make it better.” It’s not enough if the code “passes quality assurance” if QA doesn’t know the ranges each level of abstraction is expected to honor.

But this is the kind of code 10X programmers develop. It’s mostly junk: it’s held together with baling wire and its interactions exist only as a terrible map hidden away in the developer’s brain. It only becomes useful after 10 other developers have cleaned up all its rough edges and applied its cruft to more enviroments than the 10X guy’s laptop.

But because that code does what the spec says it should do, provided the “just right” environment and the “just right” amount of babysitting, upper management thinks he’s a genius and his line managers are terrified that he might leave. Everyone seems to think the 10 people actually making his code saleable are overhead.

It’s not enough if the code “sells well” in its first few months if future maintainers can’t read what’s later presented to them– especially after the original developer has left company. It’s not enough to have a VCS (Version Control System) if the manager doesn’t have or won’t enforce standards of communication and etiquette in commit messages, code review requests, or code review responses.

The problem is ubiquitous, and it’s exacerbated by the external realities of the peripheral price spirals caused by this environment: the insane housing prices in SF and Seattle create an awareness in the developers that the grass may be greener elsewhere, that affording that next residence or next toy is just a job hop away.

There is no job loyalty, sadly. The closest companies can do is offer stock options, in a golden handcuffs pattern that keeps only the most dedicated, or most desperate, or least ambitious. And keep re-offering them to valuable employees. (True story: my tenure at Isilon ended in 2008 with the mass layoffs of the recession and Isilon’s buyout by EMC. In March 2009 my Palm Pilot, which had been silently sitting in its cradle for years, beeped suddenly. Curious, I read the message: Your last options award from Isilon has matured. Submit your resignation. A little late, but I had cashed everything I could already.)

But if companies want to stop spinning their wheels, they need to get things right the first time. Yes, that means slow down. Yes, that means, plan ahead. But most important of all, have a spine. A culture of excellence requires a culture of courage.

I’ve been working my way through a Lisp textbook, Lisp In Small Pieces, by Christian Quinnec. It was originally written in French and is not that well known among English-speaking Lisperati, not in comparison to the Wizard book or Paul Graham’s On Lisp, but what caught my attention was how it really was in small pieces. Each chapter ended with an interpreter described, sometimes in code, sometimes in text; if you were smart enough, you could actually piece the whole thing together and see how it worked.

I decided to make things hard for myself. Since I’m not a Lisperati (although I may well and truly be seduced by Hy), I decided to make things hard for myself by writing the interpreter in Coffeescript. Most Lisp books assume you have a Lisp handy, and Quinnec’s examples are fine and dandy on many variants of Scheme, but for a fun time I decided to write it in something else. Raganwald claims Javascript “is a Lisp,” and if that’s so it ought to be good enough to write a Lisp in it.

I mean, it’s obviously been done before. I tried once before but got lost. LiSP does me the favor of keeping me on track.

You can see all my sourcecode at Github: Lisp In Small Pieces.

Chapter 1 contains the base interpreter. It also contains a hand-written Lisp reader, and refers to another project I have on GitHub, cons-lists, which is exactly what it sounds like, a singly-linked list implementation in Javascript, using nested Javascript arrays as the base. The base interpreter is very primitive– you can’t even create new variable names in the global namespace! Although you can shadow them using lambdas, so it’s pretty much bog standard Lambda Calculus.

Chapter “Lambda 1″ contains a continuation-passing variant of the interpreter from Chapter 1. It’s basically a facile reading of Lisperator’s λ-language intepreter, with my own parser front-end and some CPS style. It passes all the tests, but it’s a distraction.

Chapter 3 contains the same interpreter, only using the architecture Quinnec describes in Chapter 3 of his book.

Chapter 2 describes a number of different methodologies for binding, scoping, and namespaces. The material is interesting but I didn’t pursue writing the various interpreters. I “got” what Quinnec was saying, and if I’m ever interested in writing something with scoping rules outside of the lexical scopes with which I’m familiar, I might revisit the material.

The next step will be to add functions to the Chapter 3 interpreter to do the various continuation management games, like call/cc, throw/catch, and so forth. Because those, I feel I need to understand.

How far will I take this project?  I’m not sure.  Chapter 4 is “Assignment and Side Effects,” so I’ll do that.  Chapter 5 is theory, and 6 implementation, of a “fast interpreter” of the kind French programming language guys apparently love to study.  I’ll read them, but I’m not sure what code I’ll generate out of that.  Chapter 7, “Compilation,” is interesting in that he starts by defining a VM that on top of which our bytecode will run, and implement both the VM and the compiler in Scheme.  I think I want to do that chapter, and then re-write the compiler to create LLVM-compatible code instead, just to learn LLVM.  Chapter 8 implements EVAL, chapter 9 has Macros, and chapter 10 has Object-Oriented Lisp.  So I’ll probably do those as well.

And then… we’ll see.  I surprised myself by doing Chapter 3 in less than two weeks.

I don’t have much experience with Windows, but I have to work in it for ${EMPLOYER} now and then.  I had this weird problem today where the output of a PowerShell script was pre-formatted, but the consumer of that output (namely, a Splunk server) wanted raw numbers.  To force raw numbers on output, PowerShell provides the Format CmdLet.

Now, I really don’t like PowerShell.  It has all the syntax of Perl, all the sensibility of Smalltalk, and all the verbosity of Donald Trump.  But if the client wants it, that’s what you work with.  I did Perl for six years and Smalltalk for two, so PowerShell is rather easy for me.  It’s just knowing what’s available in the library that’s hard, like number format commands.

The Format CmdLet is an in-line operation activated with the -f command.  Its operations have the syntax {0:C}.. For example:

$money = "Total paid: {0:C}" -f $paid

All objects in PowerShell are arrays of some kind. The zero in the snippet {0:C} means “use the first (zeroeth) item”, which is almost always what you want. The “C” indicates that we’re going to use currency. Which currency symbol will be used depends upon your localization settings. The letter may be followed by a number in some cases; this translates to different things (leading zeros for integers, for example; precision for fixed-point reals).

And that’s it. The CmdLet supports the following formatting translations: “C”: Currency; “D”: Decimal; “E”: Exponential; “F”: Fixed Point; “G”: General; “N”: Number; “P”: Percentages; “R”: Round-Trip, a number that precisely matches the format of its input with special considerations for culture-specific notation; “X”: Hexadecimal.

More can be found at MSDN Standard Numeric Format Strings.

In a lot of ways, these look like Python’s old numeric formatting operations.  If you’re familiar with those, these should be straightforward.  It’s just a slightly different syntax, like everything Microsoft does.  I think it’s an attempt by Microsoft to crowd out the open source alternatives by cognitive overload.

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.

Recent Comments