Scheme in 5000 lines of C part 3: Testing, random thoughts on closures.

I haven't made as much progress on the Scheme recently as I would have liked. Work's been busy, the house has needed some fixing, and I'm still chewing over how I want to implement closures.

Since I want to make *some* progress I rewrote the testing framework. Before I just had some sample strings embedded in main that I read-evaled-printed, and looked at the output to see if the changes I made had the desired effect.

I felt some (a lot of) shame because (semi-)robust testing is supposed to be my day job. So I moved most of that away into a test harness that's pretty stupid/simple but actually performs validation. Funny that.

There's a directory, tests/, that contains the test cases. One per file. Each file has the input that is fed to read-eval-print, the output of which is captured, and then compared to the expected value.

I'm still not quite sure how I'm going to handle closures though. Variable capture I think is going to be fairly easy. I'm not quite sure how I'm going to store references to inner functions though. For example, this function:


(define closure-test
  (lambda (foo)
    (lambda ()
      (set! foo (+ 1 foo))
      foo)))

The outer function (closure-test) will need to hold some sort of managed reference to the inner function so that when closure-test is called it can create a new function object and a new environment, but I'm not quite sure if I want to bake the reference into the bytecode, or do something else. Maybe re-write function objects to include a table of contained functions? That might work.

Follow on to part 4: Scheme in 5000 lines of C part 4: (Un)necessary refactorings
View the source on GitHub: https://github.com/maxburke/evilscheme

Scheme in 5000 lines of C part 2: (let ((them (eat 'cake))))

I've spent the last week implementing the Scheme binding constructs let and let* for my little toy Scheme (https://github.com/maxburke/evilscheme). In Scheme, as with Common Lisp, the difference between let and let* is that let* ensures the bindings are evaluated left-to-right whereas for let they are unspecified. So, if you have let*, you should have let. Easy peasy! (If I'm wrong please let me know!)

The binding constructs surprisingly easy to implement. The VM which started out as purely stack-based (ie, (+ 1 1) became PUSH 1, PUSH 1, ADD) now has instructions for loading from, and storing to, basically arbitrary locations on the stack. The compiler now creates a spot for the active local variables and loads from/stores to those stack slots as required. The slots then are recycled as scopes are exited/entered. On my list for future refactoring is merging the opcodes used to load from/store to stack slots with the opcodes used to load from/store to argument slots because it's the same thing now.

The compiler -- so far -- is sort-of-multi-pass. It does a single pass over the source AST and does a rough compilation. After it performs some clean-up passes on the generated bytecode.

One pass removes the nops that are inserted into the bytecode stream as a result of branching. One difficulty I ran into when compiling conditional branches is that in many cases the branch targets weren't yet known, and when they were known it was a lot of messy code to find where the actual branch target was. The workaround I picked was to insert nops as branch targets, and then use these nops as the first instruction of the resulting basic blocks. It sounds kinda convoluted but it was much cleaner and straight forward to implement. This nop-removal pass, well, removes the nops and updates the branch instruction targets accordingly.

Another pass inspects all branch targets and if the instruction is a return, it replaces the branch with a return instruction. This is the only optimization pass. So far.

The last pass promotes all tail calls to use the VM's tailcall opcode. Scheme has a requirement that implementations must be tail recursive and, although I'm not gunning for 100% standards adherence, I wondered how difficult it would be to add. This pass takes calls that could be tail calls (basically any instruction sequence of a call proceeded immediately by a return) and replaces it with a tail call. The VM then ensures that these tail calls are executed in constant space.

I'm going to tackle closures next because it's been something on my want-to-do list for a while. After that I'll probably tackle the garbage collector, alternative lambda syntax (ie, (define (foo a b c)) in addition to (define foo (lambda (a b c)))), interactive REPL + error callbacks instead of just assertions, benchmarking, and proper quasi-quotation. I'm not sure what I'll do with continuations, that part of the spec I may skip entirely because I'm too dumb to understand how call/cc actually works, but some sort of co-routine mechanism will probably end up going in.

Follow on to part 3: Scheme in 5000 lines of C part 3: Testing, random thoughts on closures.
View the source on GitHub: https://github.com/maxburke/evilscheme

Scheme in 5000 lines of C

Every time I see a blog post spring up talking about a new (basic) implementation of Scheme that is written in 30 lines of Ruby, Javascript, or Python I get the sense that there's something missing.

In fact, there's a lot that's missing.

These environments already come with a garbage collector, so the implementation never describes implementation. The intricacies and tradeoffs of object storage? Also skipped over. Parsing? Nope. What about compilation? Never done.

I appreciate code golf and it's fun to see these new, super small, implementations show up, and don't mean to belittle the effort their developers invested, however I haven't been able to learn much from them. So, I thought I'd give it a go on my own.

The hard way.

In C.

Not that cutesy C with C++ comments, variable-declaration-wherever-you-want-it, or inline functions, but the super crusty C89 supported by Microsoft Visual C++, the one where Dave Cutler personally wrote the front end himself while fighting off the red menace and arm wrestling bears. (And GCC/clang too... I guess. Twist my rubber arm.)

I've got a bunch of stuff cobbled together now where it sorta kinda works. It parses, it generates an AST, it compiles the AST into a bytecode, and the bytecode runs. Hey, that almost makes it more functional than some video game console toolchains I've used.

One decision I made recently which simplified the VM conceptually was creating value types (fixnum/flonum/bool/char/reference/inner reference) from reference types (cons cell/vector/string/function). This allowed the VM's execution stack to contain either a raw value, like a fixnum, or a reference to a heap-allocated object, making stack operations simple.

Originally I had it so that the storage of conses was handled by holding a pair of pointers to other objects but I recently switched this so that a cons is now a vector of length two. This means that value types do not need to be boxed in order to be stored in a cons and also simplifies the operations on it.

I've got a few compiler-related tasks I'm going to work on now that it's executing, such as handling specific essential syntax forms. I've got a garbage collector to do as well, but I'm not worried about that one as I've already written several, including one that shipped in a console video game.

If you want to follow along, I've got my code stashed on GitHub. It's still pretty rough around the edges though, so beware at this point!

Maybe when (or if!) I finish, it'll actually be under 5000 lines of C :-)

Follow on to part 2: Scheme in 5000 lines of C part 2: (let ((them (eat 'cake))))

New job!

I started a new job last month! I'm managing my department's just-formed test engineering group. The group has eight people in both Burnaby and Montreal and we're responsible for developing and maintaining our build farm, performing integration testing, developing/implementing new (for the department) testing processes, and auditing current test coverage. Basically if it's related to testing, and it's something more complicated than running the unit tests, this group will be involved.

I'm really excited about the opportunities that are on the horizon. I started at EA over 10 years ago as a game tester and started as a developer in this group's long dead predecessor doing clear box software testing, so it's in a way like coming home. Since it's removed from the secret squirrel work that I was working on before I will also be a lot more free to talk about what I'm doing.

The first couple weeks on the job were spent getting to know the people, getting to know the work, and setting up a plan where I want the group to go over the next 12 months. As the people on the team aren't new, just repurposed from other groups, most of the work they do in the short term isn't going to change. Longer term the goal is to have detach from their old teams so that they can focus more on the work our department does as a whole.

I'm not going to give up coding quite yet. I've currently got my sights set on our build farm and its reporting infrastructure. It's been cobbled together out of a number of shell/build scripts and it's creaking. One of the more recent additions to the group, Dave, is tackling both this and the database back end to make the system more reliable and easier to report on.

I hate SharePoint.

The web dashboard is built on SharePoint. I suppose there's some sort of redeeming quality I haven't yet seen because apparently a lot of people pay a lot of money for the product but deep down I sincerely doubt it. Anyways, the rationale of our build web dashboard using SharePoint is that there is a need to keep some platforms hidden from the world while they are covered by NDAs -- but the rest of the baggage SharePoint has brought means it takes 20 seconds to retrieve the "current status" web page. If you want to filter this information -- which is pretty common for most people as our group supports 150+ libraries built in 40+ configurations, making a status table pretty useless to get your desired information -- it hits the server again, which means waiting another 20 seconds.

I despise SharePoint.

I've started the process of removing Sharepoint completely and instead use some simple scripts to pull the information from the database and authenticate it via LDAP. I moved the rendering client-side, using jQuery and Bootstrap for a little style. Page load is now down to ~2 seconds with most of it being spent in database queries, and that should remedy itself when Dave's finished his schema rework.

The site is much easier to work on now. Deploying the new pages is handled by syncing them from Perforce. Since all the UI code is in Javascript most of it can be tweaked locally on the desktop without having to setup a local server. Or find the one machine that we have a SharePoint developer environment installed on and without colliding with someone else who also needs to use it, and then package+deploy your changes to the production servers hoping that the servers don't barf on your changes leading you to get a nastygram from IT.

Have I mentioned that I hate SharePoint?

I hope to finish the web page updates this week. Once that's done I have to work on a metrics solution for our console unit tests and dig back into valgrind.

The One-on-One

Any developer worth hiring will tell you that the best meeting is the meeting that doesn't happen. Some will even be so kind as to tell you that at the beginning of every meeting they're invited to!

The one meeting that I always get value from, however, is the one-on-one. Whether or not I'm having the meeting with my manager or someone on my team I'll always come away with something that made the time invested worth while..

The one-on-one is a meeting where there may be venting, there may be difficult conversations, there may be awkward silence, but the manager's job isn't to be defensive or aggressive, it's to play the part of a good listener. If there is a slip up then the trust will be damaged, if not broken entirely, and will take a long time to repair. This isn't the trust that's related to integrity, such as failing to meet a promised deadline, but the "I won't tell you that I'm unhappy with what's going on and I'm looking for new jobs on Monster.com when you're not around" kind.

Although work status will frequently come up during the one-on-one I make it a point to never explicitly put it on the agenda. I want the meeting to be about the status of Fred, not the status of  Fred's work, which means the first question I always lead with is "How are you doing?". I'll also ask some variant of "what's getting in your way and what's on your mind?", which has a subtle, but key, distinction from being work status related as this could lead beyond a discussion of the issue that he's blocked on and into one about how he'd really like to get two days off to help his girlfriend move but he's not sure about taking it because of the amount of work that's piling up. Their response to that question leads quite naturally into "what can I do to help you?"

I've never encountered a programmer that has said "I really like that this meeting was booked in the middle of the afternoon, I really didn't need to be concentrating on finding that one rare concurrency bug." I could be wrong.


The team is being paid to do good work, and I'm being paid to shelter them from BS, so in order to shelter them from BS and allow them to do good work I try to keep meetings to a minimum and preferably at the periphery of the day. Putting a meeting in the middle of the day kills what your team members are working on, causing them to take a while to get back up to speed once it has concluded. I try to put my one-on-ones at the beginning or end of a solid work block, such as the beginning of their (not your!) day, and either before or after lunch, typically avoiding the end of the day because the end of the day can vary with whatever is going on. A good read on this topic is Paul Graham's essay, Maker's Schedule, Manager's Schedule.

Co-routines in C(++)

A little while ago I put together a small co-routine library in C targeting x86/Windows. It uses micro-stacks of about 4kb, minus a small tax for library overhead, for each co-routine which places some constraints on the work that can be done but I figured that it'd complement Windows' fairly heavyweight fiber library.

The code sets up a new thread context, by setting esp to point to the new co-routine stack, and then uses setjmp and longjmp to yield the co-routine to the main execution context and to resume the co-routine from where it left off.

One known issue is that if you build C++ code with Visual C++'s /EH command line options the compiler will automatically run destructors on stack objects as it unwinds past them, and so any objects you create in your co-routines will be destroyed prematurely. Building without exceptions enabled will work around this.

Code: https://github.com/maxburke/coroutine

Management 102: Post shake-up stability

My last post mentioned a few points to keep in mind now that you're a fresh manager. In this one I'm going to go into the first tasks you need to accomplish in first day after the reorganization has been announced. The reorganization doesn't have to be a full company shake up, it could be something just as simple as two people shuffling around.

Hopefully you've had some advance notice that this was coming, giving you some time to plan things out, knowing who will be reporting to you, and possibly what you'll be working on. (Digression: I dislike the term "report" in the management-hierarchy-sense. I guess it comes out of industries where there's a more rigid command-and-control type of infrastructure. Like the military. But the people in your group aren't soldiers; no, you're paying them good money so that they can flex that brain of theirs, not just follow orders. The company's paying you to be their BS shield.)

Re-orgs are kept on the down-low to keep the hand wringing to a minimum, but see if you can suss out who else is in the know, and if they are currently managing some of your new group. Same goes with the new projects you'll be overseeing. The goal here is that once day one arrives you'll look like you have some clue as to what's going on and who these people are. You'll want to sort out a transition plan for your current responsibilities so that you don't appear to have bolted on your old job.

If you've got some time to kill before the big day you might want to start planning your schedule, where you'll fit in your new one-on-one meetings. Getting your one-on-one's setup is a great first step as this is where you put your finger on the pulse of the team; far beyond a face-to-face status report it's where you find out what's on their mind, what troubles may be lurking below the surface. I believe that the one-on-one is so important that I'll go into it in detail in my next entry.

It's a good idea to also have some plan of what you want them to do in the short term, until you can really start digging into the new problem space, even if the plan is to keep on keepin' on. Don't let them twist in the wind.

Once the one-on-ones have been sorted out and you've met them, it's probably a good time to get the team together for a lunch, to get away from the work and get to know each other a bit.

As the day winds down you should start seeing some semblance of routine; maybe you'll have your first official meetings with the team. Your old job should be fading from view, as you'll have plenty to do with your new team and you don't want to give them the impression that they're not the most important part of your work life.

In the end you want to make sure that there's no large clouds of uncertainty hanging over your team's heads. Don't sweat it, you're going to do great!