On Programmer Archaeology
Brit Butler
2012-08-06
(use arrow keys or PgUp/PgDown to move slides)
I've become known by the wrong name...
and it's my own fault.
Just a lisper?
Ideas > Tools
"Tools are only worthwhile in the service of ideas."
A Programmer Archaeologist
"Over thousands of years, the machine memories have been filled with programs that can help. But like Brent says, many of those programs are lies, all of them are buggy, and only the top-level ones are precisely appropriate for our needs."
Sound familiar?
The Inherent Complexity in Software
At 50 lines/page, Storyville is 185k or *10* 370-page books.
No one knows how to solve it. Especially me.
Though historically we've tried a number of things ...
Every program is part of some other program and rarely fits.
-- Alan Perlis, Epigrams on Programming
My definition of Programmer Archaeology
Know Your Damn History
Let's mine history! ... at JSConf?
- Dan Ingalls - The Lively Kernel
'Well, this is how it should work, right?' - David Nolen - Logic Programming and Unification
Another example: @bigthingist used mark+sweep GC algos to manage retail fashion site.
In many ways, this is equivalent to knowing and having an interest in CS...but the lens of archaeology is more fun. :)
Revenge of the Smalltalkers?
Why didn't old tech win if it was so great?
Alan Kay - Programming and Scaling talk, Dr. Dobbs interview, etc
"...But nowadays people are reinventing the flat tire."
A broken record. Crank or genius? Why keep saying it?
Lisp and Smalltalk failed for a reason, presumably.
Alright, proof is in the pudding. What's he building?
Steps for the Reinvention of Computing, VPRI
5 year project funded by the NSF.
First thought: What a pretentious jerk!
Second thought: Well...what are their results?
An entire OS+Office Suite in 20,000 lines of code. W.T.F.
Even if it isn't backwards compatible with /anything/ ... ... HOW?!?
Metaprogramming, the Compiler as a Service pattern
OMETA - Technology from the 60s!!!
[extended with Inheritance and PEGs]
Parsing as a weapon: Compiler as parser series in lieu of IR.
- Used it to write:
- TCP/IP in 200 lines. Just parse the ASCII art in the RFC!
- A complete 2.5D graphics stack in 500 lines.
See appendices of 2007 STEPS report for further examples.
[Like OMETA->JS in 75 lines and Prolog->JS in 100 lines.]
Burn the Libraries
'We should burn all libraries and allow to remain only that which everyone knows by heart' - Hugo Ball
Interview question: 'Write as much of jQuery as possible in 45 minutes from scratch.'
The antithesis of using past solutions.
Why not?
- @fat noticed that people don't know jQuery by heart. If we have to rewrite, we're all screwed.
- Programming libraries are functional. They DO stuff in the real world. You can't execute books.
- We need code as literature:
What's the lesson?
Tests define 'satisfactory code'. By using them, we are less trapped in the past.
My Open Source Talk makes it clear how this would help promote competition and diversity.
MustacheJS has a specs repo in JSON.
... but it's not quite clear how to apply this to the 6502.
And it wasn't my goal to. :)
Enter cl-6502
Let's emulate one.....with Lisp!
BUT WHY?!?
Goals: Definition
- Extensible - Easy to arbitrarily toggle logging of reads/writes to memory, or branching opcodes, or...
- Concise - NOT CODE GOLF. Dense but elegant. The minimal executable spec.
- Performant - Able to comfortably run at least 2 emulated CPUs/core on modern hardware.
- Correct - Implements the 6502 faithfully enough to run Mega Man 2, Super Mario Bros 3, etc.
Goals: Status
- Extensible, Concise? Check.
- Extensible - All opcodes are methods. CLOS makes arbitrary wrappers (think decorators or defadvice) trivial.
- Concise - Py65: 2091 SLOC. cl-6502: 879 SLOC.
- Correct - Py65: ~8000 SLOC. cl-6502: ~200 SLOC.
- Lots of manual testing, no large programs. - Performant - ZERO profiling, ZERO optimization.
Currently runs 2x the speed of the NES on a single core.
Correct, Performant? Verdict still out, outlook positive.
* - All SLOC figures courtesy of sloccount.
Why Lisp? (or, a few good points)
- My favorite tool. Never found a better way to stay in flow than Emacs+SBCL+SLIME.
- Universal syntax is still (for now) the one true path to a metaprogramming culture.
- It's truly agnostic which enabled me to grow with the language. Procedural, OO, FP, Logic, Dataflow, whatever!
- It's the fucking playdoh of PLs. Mold the language, mold the program.
A Culture of Metaprogramming
Still fairly unique to Lisp culturally...because metaprogramming and source transformation is usually INSANE AND FROUGHT WITH DANGER.
Non-paren alternatives in Dynamic and Static langs exist: Template Haskell, Camlp4, Dylan, Factor, Io
- It is the language's responsibility to give you:
- More structure than strings.
- Distinct compilation phases.
Thus far, no parens == no culture of metaprogramming.
Fear not, I will explain macro usage carefully.
On emulators, portability, and methods of emulation
It's basically a VM, duh. Simulate hardware and run a program inside the simulated hardware.
Portability thinking seems to be: Write it in C. After all, C compilers are ported everywhere.
- Interpreted
- Dynamic Recompilation
- Static Recompilation
I stayed with interpretation for simplicity's sake. Crawl, then walk. For a great overview, see this paper.
Enter the 6502
- What comprises this thing? Data
- Accumulator, X, Y - general purpose 8-bit registers
- Program Counter - 16-bit register allowing for 64k addressable memory
- Stack Pointer, Status Register - special purpose 8-bit registers
- What runs on this thing? Code
- 56 "opcodes" (read: functions/primitives)
- 155 "instructions" (read: opcode variants for different addressing modes)
Addressing Modes, or Pointers redux
None of this "Declare a variable" nonsense.
6502 has 13 addressing modes. No instruction supports every mode. Indirect mode only used by one instruction.
- Arg == Byte
- No args - Implied, Accumulator
- One arg - Immediate, Zero-page, Zero-page{x,y}, Indirect{x,y}, Relative
- Two args - Absolute, Absolute{x,y}, Indirect
Some opcodes use address, some use byte at address.
Get ready to poop your pampers
The following code has been rated GH-MA*
* - [Github Mature]
- For gratuitous use of parentheses.
- And screwing around with EVAL-WHEN with its weak phase separation.
An executable spec, or Enter defopcode
Remember when I said I'll Explain?
A Defopcode Aside
- A simple tweak to defopcode and opcodes return compiled closures instead of executing directly.
- Not that it would give a big speedup.
- Too much learning+engineering for a JIT compiler right now.
- Fast interpreters are possible!
On dispatch strategies
Which method goes with this byte in the array?
- Opcodes take a CPU, figure out their addressing mode, modify its state and return it.
- Store an array of methods, indexed by opcode. Opcode takes no args. `find-method` makes this annoying.
- Have a giant switch/case statement. Totally unacceptable. What is this, C? :)
Wound up doing dispatch via opcodes just like a switch/case interpreter...
But using Lisp's EQL-specialized methods! \o/
On Assembly and Disassembly
Once you have an opcodes array full of metadata, disassembly is *trivial*.
Assembly is more involved even though I was lazy and didn't write a proper parser, just regexes. Still not so bad.
2-pass assembler. First sets labels, second resolves uses.
Supports labels, constants, comments. Here's a small example.
Interesting hurdles
Decimal mode - Dodged that bullet. Not in the NES! ;)
Sadly, no language can make decimal mode pretty.
Status bits - Sort of ad-hoc and messy. No defaults for you!
Relative addressing - Oh God, Oh God.
Emulator hurdles
Truthfully, CPU emulation isn't so bad. Whole systems are what's complicated.
- A few reasons...
- Concurrency+Synchronization for performance reasons. Graphics card in one thread, everything else in another, overhead keeping them 'in step' with each other.
- Documentation doesn't exist in many cases. Reversing may be necessary.
- In the case of the NES, the memory map is ... kinda nuts.
- ...and a number of cartridges had custom hardware. SNES was even worse! :P
What's next?
- famiclom - Emulate the rest of the NES
- qeng-ho - Serve it via a REST API
- pham-nuwen - Make a nice frontend for it
Emulation as a Service!
Maybe build crazy dev tools on top a la Frodo Redpill.
No promises! ;)
The Dichotomy at the Bottom
Biologists vs Logicians
Late-bound metaprogramming vs Static verification
- Gerald Sussman, Building Robust Systems: an essay
- Leslie Lamport, The Future of Computing: Logic or Biology
- Jonathan Edwards, Informality sans Mysticism
On Abstraction
Civilization advances by extending the number of important operations which we can perform without thinking about them.
- Alfred North Whitehead
We are living now, not in the delicious intoxication induced by the early successes of science, but in a rather grisly morning-after, [where we have]... improved the means for achieving deteriorated ends.
- Aldous Huxley
There must be a middle place between abstraction and childishness where one can talk seriously about serious things.
Czeslaw Milosz, Second Space