Recent Posts

I'm still on a break from recreational programming. I've been gaming a bit to remember why I was writing an Emulator in the first place and got the idea for this article. Here are 16 games that left a major impression on me (and 4 honorary mentions) presented in something close to Autobiographical order:

Elementary School:

• Mega Man 2
• Mechwarrior 2

Middle School:

• Command & Conquer: Red Alert -- also, Starcraft
• Pokemon Blue
• The Legend of Zelda: Ocarina of Time
• Final Fantasy VIII

High School:

• Metal Gear Solid
• Tony Hawk's Pro Skater 2 -- also, Thrasher: Skate & Destroy
• Gran Turismo 2
• Freelancer -- also, Descent: Freespace

College:

• Sid Meier's Alpha Centauri
• Super Smash Bros -- also, Super Smash Bros Brawl
• Ratchet & Clank

Present:

• Super Stardust HD
• Journey
• Fez

Certainly there have been other titles/series I've enjoyed putting hours into: Naughty Dog's Uncharted, Bethesda's Skyrim, Borderlands, and so on. But the above are the games which uniquely effected me. Each holds special nostalgic value, many represent discovery of a genre or fictional setting that I've come to love. Hell, the Tony Hawk's Pro Skater series got me skateboarding in real life and I'm not sure I would have owned an Acura NSX if not for Gran Turismo.

It would be fun to do a similar list for Movies (would I have become a programmer without Hackers?) or Music. I'll call this good for now. :)

My Recent Absence

You may have noticed it has been two months since I've done any serious hacking on my open source projects. That is no accident. It has been a little over 5 years since I decided that programming would be my future.

That decision worked out far better than I could have hoped. I find programming immensely rewarding and, for someone who has only been doing it for 5 years, I think I'm doing reasonably well. I have a steady job that I'm happy with and rewarding friends and hobbies.

But I'm tired. I'm stepping back and trying to take stock of how I use my time at a high level. I'm not micro-optimizing. I'm asking, for the first time in quite a while, how I want to divy up what free time I have and what my priorities are. I'm not sure when I'll come back to programming. I am sure that when I do, my focus and enjoyment of it will be improved. But there is so much I want to do besides code.

It's been a big year. I had two jobs before my present one. I briefly had a supercar. I started a new relationship for the first time since 2007. So perhaps it is no surprise that I haven't found as much time for hacking. That other forms of creation have fallen by the wayside a bit.

I miss the huge chunks of time I had in college. I want to both consume and create. To consume music, video games, MOOC courses, books I've been meaning to read for ages. To create code, mixtapes, music of my own, and who knows what else. But even though its hard to think of all that I get done versus all that I want to do and each weekend flies by like a screaming jet, I have to admit that things are going pretty well.

I can't believe Strangeloop is only a week away!

Thursday:

• Machine Learning for Relevance and Serendipity - Jenny Finkel (keynote)
• Fast and Dynamic - Maxime Chevalier-Boisvert
• Graph Computing at Scale - Matthias Broecheler
• The History of Women in Technology
• Software for Programming Cells - Colin Gravill
• Learnfun and Playfun - Tom Murphy VII
• Linear Logic Programming - Chris Martens
• Creative Machines - Joseph Wilk
• Making Software Development Make Sense to Everyone - Jen Myers (keynote)

Friday:

• The Trouble with Types - Martin Odersky (keynote)
• Abstract Algebra Meets Analytics - Avi Bryant
• Programming a 144-computer chip to minimize power - Chuck Moore
• Web Apps in Clojure and Clojurescript with Pedestal - Brenton Ashworth
• Getting Pushy - David Pollak || Why Ruby Isn't Slow - Alex Gaynor
• Thinking DSLs for Massive Visualization - Leo Meyerovich
• Finding a Way Out - Chris Granger || Servo - Jack Moffitt
• What is a Strange Loop? - Douglas Hofstadter (keynote)
• Thrown for a Loop - David Stutz

This will be the last post about emulation that doesn't involve graphics or disassembly of old NES games, I promise. cl-6502 0.9.5 is out and, in my testing with SBCL, pretty snappy. The book has received updates and is also available on lulu. Below is the 'Lessons Learned - Common Lisp' chapter:

Structures can be preferable to classes

Structures are much more static than classes. They also enforce their slot types. When you have a solid idea of the layout of your data and really need speed, they're ideal.

CLOS is fast enough

CLOS, for single-dispatch at least, is really quite fast. When I redesigned the emulator to avoid a method call for every memory read/write, my benchmark only ran ~10% faster. I eventually chose to stick with the new scheme for several reasons, performance was only a minor factor.

Destructuring is more expensive than you think

My second big speedup came, indirectly, from changing the arguments to the opcode lambdas. By having the opcode only take a single argument, the CPU, I avoided the need to destructure the opcode metadata in step-cpu. You don't want to destructure a list in your inner loop, no matter how readable it is!

Eval-when is about data more than code

That is, the times I found myself using it always involved computing data at compile-time that would be stored or accessed in a later phase. E.g. I used it to ensure that the status-bit enum was created for use by set-flags-if and the *mode-bodies* variable was bound in time for defaddress. Regardless, try to go without it if possible.

Use DECLAIM (and DECLARE) wisely

DECLAIM is for global declarations and DECLARE is for local ones. Once you've eked out as many algorithmic gains as possible and figured out your hotspots with the profiler, recompile your code with (declaim (optimize speed)) to see what is keeping the compiler from generating fast code. Letting the compiler know the FTYPE of your most called functions and inlining a few things can make a big difference.

cl-6502 0.9.4

I haven't been doing any hacking on coleslaw or famiclom for the last month. I've been focused almost entirely on my 6502 CPU emulator. In particular, I've been optimizing it and turning it into a "readable program".

The optimizations have gone swimmingly, taking cl-6502 from 3.8 emulated mhz circa May 1st (commit eecfe7) to 29.3 emulated mhz today (commit b729e8).(0) A factor of 8 speedup feels pretty good though it would be fun to coax more speed out later.

(0): All figures obtained with SBCL 1.1.4 on Debian 64-bit on an old Thinkpad X200. See this 6502 forum post.

I feel that the readability of the program has remained, maybe even improved, through all that optimization. The same overall design is in place; most refactorings were, approximately, tweaking macros and their callsites. The readability is especially improved when the code is broken into chapters, each with an introduction for context, and typeset with LaTeX. The latter is done thanks to a simple Makefile and some very nifty code swiped from Luke Gorrie's snabbswitch. If you've been curious about how cl-6502 is implemented or just wanted to dive in, there's never been a better time. Grab the book!

NES + Lisp + Static Analysis = ?

I'm still planning to make famiclom a full NES emulator. I won't consider it done until I can play Mega Man 2 with it. Hopefully using a USB controller. It doesn't make much sense for Lisp in Summer Projects though. I've already started the project, the scope is ill-defined, and I want to work on something fresh and new to me. So I've come up with a project that I can't possibly complete instead. It'll be great!

In short, I intend to rewrite Super Mario Bros 1. ... in a not-yet-existing lisp-like macro-assembler/incredibly simple compiler. I already have a 6502 assembler/disassembler in cl-6502 and a tool to parse NES roms in romreader. There's also a very thorough annotated disassembly of Super Mario Bros floating around. I've got a good start on a static analyzer that will take the SMB binary and an entry point and try to build a CFG of the game. The current scheme won't work with memory mapped titles but it's good enough for Mario.

Wild Speculation

Once I have a graph representation of Mario Bros, I'll try both manual analysis of the annotated disassembly with a pen and pad, and automated analysis on the graph using Lisp. I'll try to find as many idioms and patterns as possible to condense and improve readability of the code. Then, somewhere in early August, I'll start trying to rewrite the source and see how far I can get.

This approach is probably completely: insane, unworkable, unviable, inadvisable, and just all around wrong. But I think I'll have fun and learn something, so it's good enough for me. And hell, who knows, maybe I'll get lucky and be able to attend ECLM next year. :)

Every. Single. Time.

Installing linux on a Mac never manages to be pleasant. I always remember, "Oh, yeah. I got this to work before." and dive in cheerily only to shortly recoil at what a fucking nightmare it is.

These days I use crunchbang, a very clean Debian-based distro. It's hard to even know who to be mad at. You'd think the installer would just detect the EFI/GPT stuff and "do the right thing" by now. Or be able to resize HFS+ partitions.

Out of Desperation

For whatever reason, I had to resort to this:

1. Resize OS X with Disk Utility to 50% of the current partition size.

2. Install rEFInd as rEFIt is now deprecated/unmaintained.

3. Burn a CD (!!!) since EFI doesn't want to boot from unrecognized USB drives.

4. Boot from the CD and install linux to the freespace.

5. When prompted to install the bootloader, install it on the linux partition, not the disk!

6. Do whatever it takes to get a linux command prompt, rescue disk, whatever. Mount the new install at /target.

7. Run:

   mount -o bind /dev /target/dev
   mount -o bind /sys /target/sys
   mount -o bind /proc /target/proc
   chroot /target
   

   Now you can actually do useful things, like fix the broken fucking bootloader! Note that you may need to ifconfig eth0 up && dhclient eth0 for network access.

8. Install and use gptsync on the drive with the linux partition:

   apt-get update && apt-get install gptsync && gptsync /dev/sda
   

9. Reboot and pray.

In Conclusion

Now your glorious Linux distro should boot on your "is-it-designed-not-to-work-with-a-single-fucking-Open-Source-thing?" Mac. Of course, you may need to apt-get remove the busted radeon drivers and add xforcevesa to the linux invocation in your /boot/grub/grub.cfg and remember to always gptsync after any future update-grub operations but...yeah, fuck all these goddamned computers.

Coleslaw 0.9.2

It still amuses me that my most successful project to date is a blog engine. Not that I'm complaining about having contributors. When I last mentioned it, version 0.8 had just been released. Since then there have been 2 new contributors and a bunch of new features. I think the code has mostly improved in cleanliness.

The biggest changes are new shiny docs, a new tags implementation, cleanups to theming, and plugins for Google Analytics, Github Pages, and Sitemap Generation. For the full details, see the changelog.

My plans for 1.0 are primarily to take advantage of the extensible content types added in 0.8 and add some sort of tumblr-like auto-embedding support. But I probably won't get around to working on that for a spell. Why?

Other Lispiness

Because my lisp emulation experiment/art project is ongoing. Nyef was kind enough to share some code he'd hacked up for NES emulation years ago and it helped give me the motivation to rewrite famiclom's PPU (Graphics Card). The former code was largely cribbed from Patrick Walton's sprocketnes and I didn't understand it very well. I've hit the nesdev wiki again and am getting more comfortable with the PPU's actual workings. The code is on github in the new-ppu branch and I'm hoping to spend more time on it this coming week.

I also spent the last week porting cl-6502 to clojurescript for giggles. Heresy, I know. ;)
cljs-6502 is in a basic working state but there are bugs aplenty and I haven't implemented the assembler or disassembler. The must frustrating part was dealing with A) differences in macro hygiene and B) poor macro debugging facilities.

The browser is a fun target though. I'll have to try parenscript or ... jscl! JSCL is a full CL->JS compiler in early development, which I contributed a tiny patch to for fboundp. It's a great project and if you have any interest in helping implement a lisp, I'd encourage you to get involved. The maintainers are very approachable and there's plenty of fun hacking to be had.

All for now. It's time to play around trying static analysis of Nintendo ROMs with Lisp. I'm bound to learn something...hopefully.

A Recent Obsession

"I pretended to work like others from morning to evening,
but I was absent, dedicated to invisible countries."
- Czeslaw Milosz, Nonadaptation

When I started programming, I quickly became fascinated by a question that many of us ponder at some point. Why isn't there a 'best' programming language that makes it simple to express our thoughts and intents to both each other and the machine? That transformed over time into a different question, "Why is programming so hard", but that still wasn't quite right. I think I've finally settled on the real question which is, "Why is modern software so incomprehensible?"

On Modern Software Systems

"As far as his own weak head is concerned, the thought of what huge heads
everyone must have in order to have such huge thoughts is already enough."
- Soren Kierkegaard, Fear and Trembling

I recently informally looked at the size of my software. The answer was predictably both bewildering and unsettling. The day-to-day software I use is comprised of about 35 million lines of source code.

All of that software is free and works well. By that measure alone, we might judge software engineering a success. It is popular in some circles to rail against software engineering methodologies and, often, modern software as well. We must acknowledge, however, that the demands placed on modern software far exceed the demands placed on the software of yesteryear.

This is also reflected in the way we teach Computer Science now. For example, MIT's new undergraduate curriculum shifts focus towards building systems with unreliable, incompletely understood components. The fact that we can build software this way points to a culture of library reuse as our chief abstraction rather than the humble function.

Defining Comprehensibility

"When you have a problem with X, have you pulled up the X server internals?
Have you dug into the problems with your drivers?
No, because the kernel is 10 million lines of code and the only way in is grep!
Fuck that, that's not helping me."
- Brit Butler, Wanting Types, Demanding Mirrors (video coming soon)

But I still yearn for the days when you could conceivably understand your computer soup-to-nuts. In October, I'll have been doing "real programming" for 4 years and I still accept a large portion of the day-to-day workings of my machine as magic. How many of us really have a complete picture of what is going on under the covers? We don't wrap our heads around the workings of a 1-billion transistor processor, much less the massive body of code atop it.

I'd wager 100 kloc is the upper bound on a well-organized system I think I could mostly keep in my head. That's 2000 pages or 5 400-page volumes at 50 lines/page. While prose is very different than code this would seem to be roughly the same order of magnitude as prominent fiction series like LOTR, Harry Potter, Game of Thrones, etc.

There is a torrent of OpenGenera floating around that contains about 870 thousand lines of Lisp. It should be about 20 years old. That means my current desktop is a 40-fold increase in size over Genera. Windows 3.11 is probably bigger than Genera and the size of a Desktop OS probably hasn't doubled every 4 years for the last two decades...but it is an interesting figure.

MenuetOS is a more provocative example. Menuet is a desktop OS written exclusively in x86 assembly. There is an open source 32-bit version and a closed source 64-bit one. I haven't read it so I can't say whether or not it is comprehensible. It is only 36 kloc for the kernel and 58 kloc for the apps though. Even with limited hardware support, 94k for a graphical OS is a noteworthy point in the design space.

What I Want

"So. I ask: how many people does it take, at a minimum, to maintain
our current level of technological civilization?"
- Charlie Stross, Insufficient Data

I am explicitly not asking for a world where desktop OSes are limited, comprehensible systems over full-featured ones that can't fit in one human's head. I'm not worried about bus factors. But an Operating Systems and Hardware/Software Interface course are not enough!

I want a completely open, comprehensible system that does something cool. It doesn't have to be self-hosting. It does have to be something I can study and change, observe and modify at every level of the system. It should be something that actually shipped to consumers at one point. The absolute lack of such a system for people trying to learn frustrates and disappoints me.

My Little Contribution

"We should burn all libraries and allow to remain only
that which everyone knows by heart."
- Hugo Ball

All this is exactly why I started working on a Nintendo emulator in lisp. It's still early days but it's my forever project until it's done. 6502 emulation is done, some basic Nintendo functionality is working. Once the NES is 90% complete, I plan to try writing a simple lisp-like language that targets the NES. I'll then use that to produce an annotated, high-level reconstruction of my favorite childhood game, Mega Man 2. It is a bit ridiculous and probably overreaching but it's worth a shot. And in some way, it's the computing toy I've always wanted.

It's been a while since I posted some poetry. Since I'm pretty sure I'll need glasses in the next year, here's a piece by Milosz about eyes.

Eyes

  My most honorable eyes, you are not in the best of shape.
  I receive from you an image that is less than sharp,
  And if a color, then it's dimmed.
  And you were a pack of royal greyhounds once,
  With whom I would set out early mornings.
  My wondrous quick eyes, you saw many things,
  Lands and cities, islands and oceans.
  Together we greeted immense sunrises
  When the fresh air set us running on trails
  Where the dew had just begun to dry.
  Now what you have seen is hidden inside me
  And changed into memories or dreams.
  I am slowly moving away from the fairgrounds of the world
  And I notice in myself a distaste
  For the monkeyish dress, the screams and the drumbeats.
  What a relief. To be alone with my meditation
  On the basic similarity in humans
  And their tiny grain of dissimilarity.
  Without eyes, my gaze is fixed on one bright point,
  That grows large and takes me in.

"Low-level programming is good for the programmer's soul." - John Carmack, via ahefner

"What I like about Lisp is that you can feel the bits between your toes." - Drew McDermott, via Michael Weber

Previously...

I never did enough systems programming. In college, I actually convinced my Operating Systems professor to let me do the course project in lisp. So when I decided I wanted to get closer to the metal a year ago, I thought I'd look into Nintendo emulation with Common Lisp rather than systems hacking with C. Besides, my needs for a web server or other daemons were filled. So I embarked on that weird journey and came out with a shiny, readable, reasonably fast 6502 CPU emulator in under 800 lines of code. It even has an assembler and disassembler!

Announcing Famiclom version least-positive-fixnum

But a CPU emulator isn't much fun. No graphics, no sound, no I/O! After a break from September through January I got back to work in earnest a month ago. It started with getting Klaus Dorfmann's exhaustive correctness tests for the CPU added to my testsuite and a lot of bugfixing. Then I used pcwalton's lovely Rust code as inspiration and started getting the memory mappers and PPU (graphics) working with lispbuilder-sdl. So far we only support NROM mapped games though MMC1 should be coming soon(tm). As you can see at the top of the post, there are still some rendering bugs to work out. All testing so far has been done on CCL and SBCL on Linux.

Current Status

The good news is that the CPU, PPU, and .nes file reading are all done in ~1570 lines of Lisp code! The CPU in particular I think makes for quite nice reading at this point. The main NES code still needs work. The bad news is that while the CPU runs at 2-3x the speed of the NES the graphics are about 15-20x slower so I'm going to have to spend some time optimizing. I'm in #lisp on freenode regularly and would love advice or patches from any low-level SBCL or lispbuilder-sdl hackers. :)

Where to next?

1. Preliminary input handling is written, hook it into the main event loop.
2. Finish MMC1 loader. Get Mega Man 2 title screen loading at least.
3. Fix rendering bugs and try to play a few games.
4. Optimize and/or add audio support!