Strangeloop 2013 Schedule

posted on 2013-09-12 09:55:00

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

Lessons from cl-6502

posted on 2013-07-05 11:44:00

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.

My Lisp Summer Project

posted on 2013-06-21 14:58:00

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. :)

Linux on Intel Macs

posted on 2013-05-21 16:30:00

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:

Resize OS X with Disk Utility to 50% of the current partition size.
Install rEFInd as rEFIt is now deprecated/unmaintained.
Burn a CD (!!!) since EFI doesn't want to boot from unrecognized USB drives.
Boot from the CD and install linux to the freespace.
When prompted to install the bootloader, install it on the linux partition, not the disk!
Do whatever it takes to get a linux command prompt, rescue disk, whatever. Mount the new install at /target.
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.

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

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

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 and other lispiness

posted on 2013-05-11 20:41:00

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.

Towards Comprehensible Computing

posted on 2013-04-10 17:07:00

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.

Sight

posted on 2013-03-26 10:24:00

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.

So Close and Yet So Far

posted on 2013-03-16 12:22:00

Famiclom Progress

"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?

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

On Inaction

posted on 2013-03-04 16:28:00

Seeing Value

I've been experiencing the Dunning-Kruger effect a lot lately. At least, I've been feeling like a fraud. And while I could list reasons I'm not a great programmer, asking why I felt like a fraud has led me to something more interesting. I don't think I've worked at a company where I knew "where the money is coming from". What does that mean exactly?

I haven't worked for a company whose revenue comes from a product I use or want to use.
I haven't worked for a company in an "obvious" growth market.
The software I write generates revenue indirectly through customers I never interact with.

All of this creates a surprising problem for me: The value I add is opaque from my perspective. I take it on the word of my superiors and peers that any value is present. This makes it essential that I trust and enjoy working with those people.

The Mythical Customer

It might not be immediately apparent why this is a problem. Find a company with decent people and culture and you don't need to be directly connected to the product or customers. Just churn out code and have fun. Advertisers will foot the bill. While it's true that you can sustain a business this way it certainly isn't ideal. The issue comes from just how decoupled the product becomes from the revenue. When it's time to grow revenue, you have to do it by attracting more eyeballs. Here's how that works:

A Product Manager decides on new features or a UI overhaul to increase site traffic.
Programmers implement those features with small tweaks and adjustments.
The changes are released and traffic is measured for an increase. A good shop will use A/B testing to try and at least ground these decisions in data.
Improved numbers are sent to advertisers to garner more customers and/or revenue.

But Product Managers are not users. Programmers are not users. Advertisers are not users. Sure, we use the product some to verify the code works during testing but we're not invested in it. A/B testing is not the same as user input. There is also no requirement that you correlate traffic with actual perceived value. Many companies just read traffic AS perceived value. Frankly, that's bullshit. Our loyalty is necessarily to the advertisers. They pay us...but the users are the real customers. The product just happens to be paid for by collecting data about how they use it.

So What?

Thus far, none of this should surprise anyone who has worked in the tech industry. Hell, this shouldn't surprise anyone with a Facebook account. It points however to a serious cultural problem in many tech companies: not letting (or demanding) your technical experts be, well, technical experts. A friend of mine calls this "{} for $". Many people rant about this as "Taylorism in software". It cannot be overstated that no programming paradigm nor software engineering methodology will eliminate the need to connect engineers to the product. Similarly, letting the engineers take the reigns is not anathema to good product design or improved value to the business. And this is not new. Quoth Don Eastwood in a 1972 Status Report on MIT's Incompatible Timesharing System:

"In general, the ITS system can be said to have been designer implemented and user designed. The problem of unrealistic software design is greatly diminished when the designer is the implementor. The implementor's ease in programming and pride in the result is increased when he, in an essential sense, is the designer. Features are less likely to turn out to be of low utility if users are their designers and they are less likely to be difficult to use if their designers are their users."

Earlier in the report, Eastwood says, The system has been incrementally developed almost continuously since its inception. Hello, agile kids. I'll say it again. Any company pretending that software engineering methodology or a given technology replaces the need to connect engineers with what they're building deserves to be skewered. The reason knowing "where the money is coming from" is so essential is that software is different than any other product in history. Because the design in a fundamental sense is the product. If you don't know what I'm talking about, I'd encourage you to watch Glenn Vanderburg's talk from RailsConf 2011. If your engineers don't understand the reason for what they're building, then the product can at best accidentally support the business. If you think you or your company can just scrape by for your whole career without getting eaten, I'd encourage you to reevaluate that assumption.

Finding Alternatives

One big reason most companies are hierarchies more concerned with maintaining market position than creating value is the inherent risk. Real growth comes from bets and empowering people to change what's needed to find "a better way" or "The Right Thing"...and that's terrifying. Few individuals or institutions have the guts, bravery, and stamina for continuous reinvention. It's exhausting. Not to mention that it puts the focus squarely on a company's employees. It seems our best chance at winning big comes from those kinds of risks though. Github and Valve's experiments in distributed management are a brilliant step in this direction.

In the Interim

A lot of what has had me feeling like a fraud is remembering how much I have to learn. Learning is a kind of reinvention itself though and one of the reasons I've loved computers since the beginning. So I'll keep learning and next time I'm in a programming interview, I look forward to asking the other hackers, Do you know where the money is coming from?

On Aaron Swartz

posted on 2013-01-13 12:36:00

I can't remember a death feeling this much like a personal attack. The best way I can describe the feeling is this: One of my heroes was slaughtered by my government for defending my beliefs. Of course, the sad reality is that Aaron took his own life, persecuted or not. As a disclaimer, I never knew him over the net or otherwise but I always looked up to him as one of our brightest lights. As written in another article, I have always aspired to be more like Aaron and can see myself winding up in his position, fighting his battles. That's probably why he is the most significant activist of this generation for me. To everyone else who is grieving, I love you. Hold together and we will create the better world that Aaron was so clearly fighting for.

EDIT: Initially, I had intended this post to explain in greater detail why Aaron's death has affected me as much as it has. I couldn't quite find the words but John Atkinson has done a beautiful job capturing my feelings on his blog. Please read it.

Recent Content