May 30

Defect attractors

There’s a phrase I’ve used on this blog more than once that I had reason to Google just now and found that (to my surprise) the top hits are mostly my writings. It is “defect attractor”.

In this post I’m going to explain why I think this is an important concept that needs to be in the toolkit of every software engineer, and talk about the practice it implies.

Continue reading

May 09

Embrace the SICK

There’s a very interesting article just out, C Is Not a Low-level Language;. in which David Chisnall punctures the comforting illusion that C is really a “close-to-the-metal” language and relates this illusion to the high costs of Spectre and other processor-level bugs.

Those of us who think seriously about language design have long been aware that C’s flat-address-space model is increasingly at odds with the real world of memory-caching hierarchies. Chisnall’s main contribution is to notice that speculative execution, the feature at the bottom of the Spectre and Meltdown bugs, is essentially a hack implemented to allow C programmers to maintain the illusion that they’re running on a really fast serial machine.  But he has other interesting points as well.

I recommend reading Chisnall’s article before you go further with this post.

It’s no news to my regulars that I’ve been putting increasing investment into the Go language and now believe it a plausible candidate to replace C and C++ over most of C/C++’s range – that is, outside  of kernels and hard realtime.  So the question that immediately occurred to me upon reading the article was: Is Go necessarily productive of the same kind of kludge that Chisnall is calling out?

Because if it is – but something else isn’t – that could be a reason not to overcommit to Go.  The twin pressures of demand for lower security defects and the increasing complexity costs of speculative execution are bound to toll heavily against Go if it does demand massive speculative execution and there’s any realistic alternative that does not. Do we need something much more divergent from C (Erlang? Ocaml? Even perhaps Haskell?) for systems programming to follow where the hardware is going?

So let’s walk through Chisnall’s discussion points, bounce Go off each one, and see what we can see.  What we’ll find implies, I think, some more general conclusions about what will and won’t work in matching language design to real-world workloads and processor architectures.

Continue reading

Apr 23

The UPSide state diagram

I think this diagram is now stable enough to put on the record.

UPSide state diagram

UPSide state diagram

Both this diagram and the Go code for the policy logic are generated from this pseudocode:

    render.state("DaemonUp", "Daemon running") 
    render.action("DaemonUp", "ChargeWait", CHARGING)
    render.state("ChargeWait", "Charge wait")
    render.action("ChargeWait", "MainsUp", CHARGED)
    render.action("ChargeWait", "OnBattery", MAINSDROP)
    render.state("MainsUp", "On mains power")
    render.action("DaemonUp", "OnBattery", MAINSOFF)
    render.state("OnBattery", "On battery power")
    render.action("MainsUp", "OnBattery", MAINSDROP)
    render.action("OnBattery", "Overtime", DWELLWARNING)
    render.state("Overtime", "User warned of shutdown")
    render.action("Overtime", "PreShutdown", DWELLTIMEOUT)
    render.state("PreShutdown", "Awaiting power drop")
    render.action("PreShutdown", "ChargeWait", RESTORED)
    render.state("UPSCrash", "UPS goes dark")
    render.state("HostDown", "Host has shut down")
    render.action("PreShutdown", "HostDown", HOSTDOWN)
    render.action("PreShutdown", "UPSCrash", BATTERYDRAIN, unreachable=True)
    render.action("OnBattery", "ChargeWait", RESTORED)
    render.action("Overtime", "ChargeWait", RESTORED)
    render.action("HostDown", "MainsUp", RESTORED_LATE)
    render.action("HostDown", "UPSCrash", BATTERYDRAIN, unreachable=True)

To see the full context of this, clone and explore the docs/ directory.

Mar 11

How to get started on the UPSide project

The current state of play is: We have a high-level system design and a map of the behavior states. We have a capacity target (300W for 15 mins) and a peak-continuous-load spec (400W) We know we’re going to build a double-conversion design and we’re considering a couple of alternative topologies. We pretty much know the external-interface specs (some details may change).

I’m expecting both my prototype copy of the forebrain Unix SBC (an Olimex LIME2) and the interface contract for the high-power subsystem to land on my desk tomorrow.

Interest in this project continues to be huge. Another company wants in as of this morning. The volume of feature requests is high enough that I’m buckling under the editing load.

The rest of this post is instructions to potential contributors about how to get on board.

1, Get an ID on GitLab. Tell me what it is so I can add you to the project group.

2. If you have a feature request, please Don’t post it on this blog. Add it to the “General feature request thread” on the tracker.

3. Read the wiki. Read the tracker issues. I try to keep both pruned so the volume is not overwhelming. Read the Rejected Ideas page on the wiki, too.

4. Read the design documents in the project wiki. The important one is the transaction design; the I2C message inventory will change, but the basic state diagram probably won’t.

5. Participate in the design discussion. This takes place in tracker threads.

6. When we’re ready to breadboard a prototype, throw some parts money in the tip jar we don’t have yet. If you must contribute before then the PayPal blogbutton works fine.

7. Prototype builds will probably go down at PA Makerspace in Phoenixville, PA. If you are within driving distance and a competent electrics tech, consider joining us for a build.

8. Once we have a full design with a PC board and enclosure: if you have a shop facilities for it, try to replicate the build. We’ll know we have the build recipe debugged when other people can do it.

9. If your favorite hardware feature request doesn’t appear in the version 1 prototype, relax, We may think it’s a good idea but be holding off till v2 out of a desire to keep v1 simple and launch fast.

10. If your favorite software feature request doesn’t appear in the version 1 prototype, pitch in and make it happen. A Unix SBC is not a difficult programming environment – the OS on this one is a Debian port.

After step 10 and a couple of design iterations the future becomes less clear. maybe try to get it into volume manufacturing through a partnership with an established vendor.

Mar 06

Stop logging in local time!

Inertia is a powerful force. The computing world retains a lot of practices that are odd little dysfunctional relics of past stages of its technology. The one I’m here to talk about today looks like this:

Mar 6 15:11:07 snark postfix/qmgr[3927]: 0422513A6C53: removed

That’s a log message hot’n’fresh from my /var/log/mail.log file. It’s entirely typical of traditional log formats on Unix systems, and these things offend the bejeezus out of me every time I see them. Now let me show you how this would look in a sane universe:

Continue reading

Feb 12

“The Lost Art of C Structure Packing” now covers Go and Rust

I have issued a new version, 1.19, of The Lost Art of C Structure Packing.

The document now covers Go and Rust as well as C, reflecting their increasing prominence as systems-programming languages competing with C and being deployed in contexts where structure-size optimizations can be of some importance.

TL;DR: C alignment and packing rules map over to Go in the most obvious way except for one quirk near zero-length structure members. Rust can be directed to act in a C-like way but by default all bets are off.

Feb 04

How “open source” was coined

Yesterday was the 20th anniversary of the promulgation of the term “open source”. Three days before that, Christine Peterson published How I coined the term ‘open source’ which apparently she hd written on 2006 but been sitting on since.

This is my addition to the history; I tried to leave an earlier version as a comment on her post but it disappeared into a moderation queue and hasn’t come out.

The most important point: Chris’s report accurately matches my recollection of events and I fully endorse it. There are, however, a few points of historical interest that can be added.

Continue reading

Dec 18

C, Python, Go, and the Generalized Greenspun Law

In recent discussion on this blog of the GCC repository transition and reposurgeon, I observed “If I’d been restricted to C, forget it – reposurgeon wouldn’t have happened at all”

I should be more specific about this, since I think the underlying problem is general to a great deal more that the implementation of reposurgeon. It ties back to a lot of recent discussion here of C, Python, Go, and the transition to a post-C world that I think I see happening in systems programming.

(This post perhaps best viewed as a continuation of my three-part series: The long goodbye to C, The big break in computer languages, and Language engineering for great justice.)

Continue reading

Dec 16

You’re gonna need a bigger Beast

I’m taking a management-approved break from NTPsec to do a repository conversion that dwarfs any I’ve ever seen before. Yep, more history than Emacsmuch much more. More backtrail than entire BSD distributions, in fact about an order of magnitude larger than any repo I’ve previously encountered.

Over 255000 commits dating back to 1989 – now in Subversion, formerly in CVS and (I suspect) RCS. It’s the history of GCC, the Gnu Compiler Collection.

For comparison, the entire history of NTP, including all the years before I started working on it, is 14K commits going back to 1999. That’s a long history compared to most projects, but you’d have to lay 18 NTPsec histories end to end to even approximate the length of GCC’s.

Continue reading

Nov 28

Proposal – let’s backport Go := to C

The Go language was designed with the intention of replacing C and C++ over much of their ranges. While the large additions to Go – notably automatic memory allocation with garbage collection – attract attention, there is one small addition that does an impressive job of helping code be more concise while not being tied to any of the large ones.

I refer to the := variant of assignment, which doesn’t seem to have a name of its own in the Go documentation but I will pronounce “definement”. It must have an unbound name on its left (receiving) side and an expression on the right (sending) side. The semantics are to declare the name as a new variable with the type of the right-hand expression, then assign it the value.

Here’s the simplest possible example. This

void foo(int i)
    int x;
    x = bar(i);
    /* More code that operates on i and x */

becomes this:

void foo(int i)
    x := bar(i)
    /* More code that operates on i and x */

A way to think about definement is that it generates a variable declaration with an initialization. In modern C these can occur anywhere a conventional assignment can.

Definement is a simple idea, but a remarkably productive one. It declutters code – scalar and struct local-variable declarations just vanish. This has two benefits; (1) it improves readability, and thus maintainability; and (2) it eliminates a class of silly errors due to multiple declarations falling out of sync – for example, when changing the return type of a function (such as bar() in the above example), you no longer gave to go back and tweak the declaration of every variable that receives a result from its callsites.

Definement syntax also has the property that, if we were to implement it in C, it would break cleanly and obviously on any compiler that doesn’t support it. The sequence “:=” is not a legal token in current C. In gcc you get a nice clean error message from trying to compile the definement:

foo.c: In function ‘foo’:
foo.c:3:5: error: expected expression before ‘=’ token
  x := i

This makes it a low-risk extension to implement – there’s no possibility of
it breaking any existing code.

It is worth noting that this will actually be slightly simpler to implement in C than it is in Go, because there are no untyped constants in C.

I think there’s a relatively easy way to get this into C.

First, write patches to implement it in both gcc and clang. This shouldn’t be difficult, as it can be implemented as a simple parser change and a minor transformation of the type-annotated AST – there are no implications for code generation at all. I’d be surprised if it took a person familiar with those front ends more than three hours to do.

Second, submit those patches simultanously, with the notes attached to each referencing the other one.

Third, wait for minor compilers to catch up. Which they will pretty quickly, judging by the history of other pure-syntax enhancements such as dot syntax for structure initialization.

Fourth, take it to the standards committees.

OK, am I missing anything here? Can any of my readers spot a difficulty I haven’t noticed?

Will anyone who already knows these front ends volunteer to step up and do it? I certainly could, but it would be more efficient for someone who’s already climbed the learning curve on those internals to do so. If it helps, I will cheerfully write tests and documentation.

EDIT: No, we can’t backport C++ “auto” instead – it has a different and obscure meaning in C as a legacy from B (just declares a storage class, doesn’t do type propagation). Mind you I’ve never seen it actually used, but there’s still a nonzero risk of collision with old code.

UPDATE, DECEMBER 2ND: I have been in touch with Ken Thompson. He approves, raising two minor technical caveats about stack growth and name shadowing.

Nov 18

Language engineering for great justice

Whole-systems engineering, when you get good at it, goes beyond being entirely or even mostly about technical optimizations. Every artifact we make is situated in a context of human action that widens out to the economics of its use, the sociology of its users, and the entirety of what Austrian economists call “praxeology”, the science of purposeful human behavior in its widest scope.

This isn’t just abstract theory for me. When I wrote my papers on open-source development, they were exactly praxeology – they weren’t about any specific software technology or objective but about the context of human action within which technology is worked. An increase in praxeological understanding of technology can reframe it, leading to tremendous increases in human productivity and satisfaction, not so much because of changes in our tools but because of changes in the way we grasp them.

In this, the third of my unplanned series of posts about the twilight of C and the huge changes coming as we actually begin to see forward into a new era of systems programming, I’m going to try to cash that general insight out into some more specific and generative ideas about the design of computer languages, why they succeed, and why they fail.

Continue reading

Nov 13

The big break in computer languages

My last post (The long goodbye to C) elicited a comment from a C++ expert I was friends with long ago, recommending C++ as the language to replace C. Which ain’t gonna happen; if that were a viable future, Go and Rust would never have been conceived.

But my readers deserve more than a bald assertion. So here, for the record, is the story of why I don’t touch C++ any more. This is a launch point for a disquisition on the economics of computer-language design, why some truly unfortunate choices got made and baked into our infrastructure, and how we’re probably going to fix them.

Along the way I will draw aside the veil from a rather basic mistake that people trying to see into the future of programming languages (including me) have been making since the 1980s. Only very recently do we have the field evidence to notice where we went wrong.

Continue reading

Nov 07

The long goodbye to C

I was thinking a couple of days ago about the new wave of systems languages now challenging C for its place at the top of the systems-programming heap – Go and Rust, in particular. I reached a startling realization – I have 35 years of experience in C. I write C code pretty much every week, but I can no longer remember when I last started a new project in C!

If this seems completely un-startling to you, you’re not a systems programmer. Yes, I know there are a lot of you out there beavering away at much higher-level languages. But I spend most of my time down in the guts of things like NTPsec and GPSD and giflib. Mastery of C has been one of the defining skills of my specialty for decades. And now, not only do I not use C for new code, I can’t clearly remember when I stopped doing so. And…looking back, I don’t think it was in this century.

That’s a helluva thing to have sneak up on me when “C expert” is one of the things you’d be most likely to hear if you asked me for my five most central software technical skills. It prompts some thought, it does. What future does C have? Could we already be living in a COBOL-like aftermath of C’s greatest days?

Continue reading

Jul 17

A teaching story

The craft of programming is not a thing easily taught. It’s not so much that the low level details like language syntaxes are difficult to convey, it’s more that (as I’ve written before) “the way of the hacker is a posture of mind”.

The posture of mind is more essential than the details. I only know one way to teach that, and it looks like this…

Continue reading

Jul 12

Fuzzbombing: abort() calls for great justice!

The Colossal Cave Adventure restoration is pretty much done now. One thing we’re still working on is getting test coverage of the last few corners in the code. Because when you’re up to 99.7% the temptation to push for that last 0.3% is really strong even if the attempt is objectively fairly pointless.

What’s more interesting is the technique one of our guys came up with for getting us above about 85% coverage. After that point it started to get quite difficult to hand-craft test logs to go to the places in the code that still hadn’t been exercised.

But NHorus, aka Petr Vorpaev, is expert at fuzz testing; we’ve been using American Fuzzy Lop, a well-designed, well-documented, and tasteful tool that I highly recommend. And he had an idea.

Want to get a test log that hits a particular line? Insert an abort() call right after it and rebuild. Then unleash the fuzzer. If you’ve fed it a good test corpus that gets somewhere near your target, it will probably not take long for the fuzzer to random-walk into your abort() call and record that log.

Then watch your termination times. For a while we’d generally get a result within hours, but we eventually hit a break after which the fuzzer would run for days without result. That knee in the curve is your clue that the fuzzer has done everything it can.

I dub this technique “fuzzbombing”. I think it will generalize well.

Jun 30

Open Adventure 1.1, and some thoughts on software preservation

Open Adventure 1.1 has shipped. There are a lot more changes under the hood than are readily apparent. In fact there have been no changes in gameplay at all, and only minor changes to the UI (reversible with the -o oldstyle switch).

We (Jason Ninneman, Per Vorpaev, Aaron Traas, Peje Nilsson and I) could have taken the approach of changing the original rather ugly C code (mechanically translated from FORTRAN) as little as possible, simply packaging it for compilation and release in a modern environment.

I elected not to do that, one reason being that I think we honor hacker tradition better by bring the code forward as a dynamic, living artifact that invites being hacked on than museumizing it as a static one. There’s also the fact that the extreme obscurity of the code made it difficult to appreciate what a work of genius Adventure actually was. (The code we inherited had over 350 gotos in it – rather hard to see past those.)

So we’ve taken a different path. We’ve translated the code into (almost) fully idiomatic C (but not trying to introduce pointer idioms; that should make translation to future languages easier). We’ve replaced the rather cryptic custom text database file that used to define the dungeon with a YAML document that is orders of magnitude easier to read and modify. We haven’t hesitated to use technology that wasn’t even a gleam in anyone’s eye when Adventure originated – the YAML is compiled to C structures at build time by a Python script.

The effect (we hope) is Adventure as it would have been written if Crowther & Woods had had today’s tools to do it – the same vision and design logic, expressed in modern coding idioms. Worth doing, because there are still some things to be learned from this design.

Probably the single cleverest thing in it – which pretty much has to go back to Crowther, Woods couldn’t have bolted it on afterwards – is the way movement in the dungeon is handled. The dungeon’s topology is expressed by a kind of pseudocode broadly resembling the microcode found underneath a lot of processor architectures; movement consists of dispatching to the sequence of opcodes corresponding to the current room and figuring out which one to fire depending not only on the motion verb the user entered but also on conditionals in the pseudocode that can test for the presence or absence of objects and their state.

It was hard to fully understand and appreciate this before, because the code was a spaghetti tangle in what looks today like a shockingly primitive style. The abstraction of the dungeon topology into a declarative specification that – in effect – loads microcode into the game engine was a thing you could half-see, but the impact was blunted by the unreadability of both the code and the specification format. Lifting the specification to YAML was like polishing a rough diamond, revealing beauty and brilliance.

And that’s before we even get to Adventure considered as a work of communicative art. It’s had so many successful descendants – like, every dungeon-crawling game ever, and every text adventure ever – that it’s difficult to see with fresh eyes. But if you make the effort, it is astonishing how mature the wry, quirkily humorous, slightly surrealistic style of this very first game seems. The authors weren’t fumbling for an idiom that would be greatly improved by later artists more sure of themselves; instead, they achieved a consistent and (at the time, unique) style that would be closely emulated by pretty much everyone who followed them in text adventures, and not much improved on as style, even though the technology of the game engines improved by leaps and bounds.

I don’t know how they did it, and the authors would probably not be able to explain if we asked. But I think it is damned impressive how well this game has aged – the code may have needed a refresh, but the design still shines. I’m proud to have helped restore it, and hope I have brought it to a state where it can be forward-ported to future languages for as long as programming is a living art.

May 14

The advent of ADVENT

A marvellous thing has just occurred.

Colossal Cave Adventure, the original progenitor of the D&D-like dungeon-crawling game genre from 1977 and fondly remembered as ADVENT by those of us who played it on PDP-10s, is one of the major artifacts of hacker history.

The earliest version by Crowther and Woods (sometimes known as 350-point Adenture) was ported to C by Jim Gillogly in ’77 just after it first shipped. That has been part of the bsd-games collection forever.

What I have have just received Crowther & Wood’s encouragement to polish up and ship under a modern open-source license is not the Gillogly port; it’s Crowther & Woods’s last version from 1995. It has 18 years of work in it that the Gillogly version doesn’t.

I feel rather as though I’d been given a priceless Old Master painting to restore and display. Behooves me to be careful stripping off the oxidized varnish.