A disassembler and Fare’s vision

I closed the last blog article with the remark that testing dasm3.py was hairy. This is owed to the fact that I tested dasm3.py against DEBUG.EXE, in itself a messy and inconsistent program that injects its own irritations into the infamously contrived 8086 architecture. dasm3.py is now a google-code project and can be found at http://code.google.com/p/dasm3/.

The scope and ambition of dasm3.py is modest, but I believe that I lived up to an important vision of Tunes celebrity François-René (“Fare”) Rideau that he expressed here. An important quote:

Literate Programming, and D.E. Knuth‘s attempts with WEB and C/WEB (see this interview of D.E. Knuth http://www.clbooks.com/nbb/knuth.html) are actually ways to pass more information about programs. To pass information that programming languages themselves don’t/can’t/can’t-efficiently pass, through well-organized human-readable documentation. This is A GOOD THING, because there will ALWAYS be things that humans can (already) express that machines cannot express (yet). But this is NOT THE PANACEA, because there ARE things that the machines ACTUALLY COULD express with high-level languages, that pure literate programming over low-level languages require the human to not only to write, but to check, when a computer is much better suited to check them. Knuth completely ignores the meta-capabilities of computers.

[Emphasis in the original]

The operative verbs here are “express” and “check”. Fare’s vision is that better programming languages

• can express and pass more meaning than current programming languages, thereby making their inner workings more transparent
• facilitate proof of their correct functioning by formal methods

dasm3.py is written in the conventional programming python, so I had to provide

• several wiki-pages for explaining how the program works, in order to instruct interested parties in text (as Fare suggests with “literate programming”)
• an extra computer program to verify dasm3.py’s output

In other words, since Fare’s vision of a sufficiently futuristic programming language is not here (“yet”), I had to go that extra mile and make a wiki- and test-prosthesis for dasm3.py. dasm3.py is not a literate program, but this is a superficial formality. Michael Heyeck, dasm3.py’s original author, did a good job in providing the literature for his program. I supplemented what I was missing when building on his work, in the hope that future programmers interested in dasm3.py don’t have to duplicate my head-scratching, experiments and research. For demonstrating dasm3.py’s correctness, I had to resort to old-fashioned test programs and explain how the tests work and why I believe they are convincing. (As for the lack of “literacy” of Michael Heyeck’s and my programming: I believe that literate programming is extremely hard for most cases; a wiki is much more fun and easy and almost as good. I will defend this thesis in a future blog article.)

The desired (but subtle) connection between literate programming and correctness did not escape Chris Lee, author of Literate Programming — Propaganda and Tools:

From a purist standpoint, a program could be considered a publishable-quality document that argues mathematically for its own correctness. A different approach is that a program could be a document that teaches programming to the reader through its own example. A more casual approach to literate programming would be that a program should be documented at least well enough that someone could maintain the code properly and make informed changes in a reasonable amount of time without direct help from the author.

What could Fare’s future look like?

In contrast to some other 8086 disassemblers on the internet, dasm3.py is largely data-driven. Most of dasm3.py’s reflection of the 8086′s instruction set is in the opcode sheet. It could be even more data-driven, thereby making much of the dispatching, if-elif ladders and many of the sets of mnemonics and opcodes obsolete. This introduction of extra columns and values into the opcode table would expand the scope of a conventional opcode sheet, but it would work out nicely and make the actual code more compact. Note that, like all “data formats”, an opcode table is an elementary form of a domain-specific language.

The smart authors of the New Jersey machine code toolkit have built a spiritual empire on this idea and developed a generic framework for implementing all sorts of assemblers and disassemblers for arbitrary CPUs. What would delight Fare is the newer experimental version programmed in ML — a language for expressing mathematical proofs. I have only a vague understanding how this magic works; I only skimmed the papers — that material is way out of my league. The overview of the project is exciting though, and I take it as evidence that the task of reflecting instruction sets one way or the other is an interesting field and a productive fruit fly for testing and developing ideas on domain-specific languages, and can, by extension, even show the way to sufficiently “high-level” languages that Fare had in mind.

Have you ever invented a domain-specific language? Do you like the 8086 instruction set architecture? Have you ever written a literate program?

Yet another 8086 disassembler pet project

Disclosure: I’m a so-so programmer. This can’t stop me, of course. In search of a pet project that

• has the Tunes nature
• but is modest in scope and amateur-friendly

… I found this stimulating passage:

Another important feature of Tunes is reflexivity. Consider the DOS emulator on Linux (or any such system) to start with: it “reflects” DOS under Linux, through the use of the Intel 386 Virtual mode. Now is Linux capable of running a Linux emulator, in other words of reflecting itself? It isn’t, because the Intel 386 Virtual mode is only capable of virtualizing (reflecting) real mode. It would be possible, however, to use a roundabout way, by writing an Intel 386 emulator, that is, reflecting the Intel chip under Linux, and then running Linux on that virtual Intel chip [...]

[David Madore's http://www.madore.org/~david/computers/tunes.html.]

The prospect of writing an i386 emulator excited me pretty good. How hard can that be? In Common Lisp?

I blew a night over failed attempts to organize opcodes and had to reduce my ambition:

• start with the 8086 (no protected mode, 20bits)
• write an opcode decoder first, make sure that it works before turning to simulation
• look how the smart people have done this (i.e. find source code)

The last point, looking at other people’s source code, was the hardest. As Joel Spolsky observes, reading [understanding] source code is harder than writing it.

I could not find an 8086 opcode decoder written in Common Lisp, but it became clear that writing a disassembler was the way to go. After going that extra mile for attaching a “disassembly backend”, you can make sure that your decoder works by comparing the disassembly output to that of a trust-worthy other disassembler.

Smart people have written all sorts of disassemblers.

The first was the vintage program DEBUG.EXE (ca. 1980, still included in 32-bit Windows Vista distros). This 16-bit living fossil sports an interactive disassembler, to aid debugging. You type in an address or a small address range, and DEBUG.EXE shows you “source code”, i.e. disassembly of the raw bytes at, let’s say 18EF:0201 – 18EF:0240. This was Microsoft’s idea of an IDE in 1980, when Funky Town ruled the earth. A distinctive feature of DEBUG.EXE is its primitivity. It disassembles with the relentless stupor of a steam engine on tracks, even data. Invalid instructions cause a hick-up in form of “???”, but can’t seriously derail DEBUG.EXE.

All this is in contrast to static disassembly, for which the disassembler slurps, disassembles and dumps an entire program at once. This makes possible all sorts of analyses and conclusions about how the binary code is structured and behaves. In its most elaborate form, such a disassembler can identify procedures, identify and name symbolic labels, generate hyperlinked Web-pages of assembly source code, etc. An example for a good static open source disassembler is ndisasm, a utility in the Netwide Assembler project (http://www.nasm.us). ndisasm can disassemble 32-bit and 64-bit opcodes, but also 16-bit.

It does not discover labels or do anything fancy, however. [For an example of what a fancy disassembler can do, look at this Z80-disassembly, a 10,000 line bouncer -- note the clickable labels].

I considered both DEBUG.EXE and ndisasm as totally trustworthy.

• DEBUG.EXE due to its respectable length of service, plus I never heard complaints about it
• ndisasm, because it is part of a successful open source project

Both disassemblers can serve as good yard-sticks for how well other disassemblers work.

In terms of enlightenment for underground disassembler constructors, however, they are not very useful, because they are not easily accessible:

• DEBUG.EXE is a closed source program
• ndisasm is big and scary

Working with other people’s source code is hard enough, because other people’s source code is only marginally more comprehensible than raw opcodes. Many more industrial-strength disassemblers exist, but, like DEBUG.EXE and ndisasm, they are either too closed or too big for impatient hobbyists like me who
want to steal and code code code.

I found a handful of pet 8086 disassemblers, in various programming languages:

• disasm.asm is programmed in TASM 3.0 (no TASM, could not compile it)
• disasm.c sort of works, but dies with a segfault half-way into a random bytes file
• disasm.pas is programmed in TurboPascal; it can process a 64k random bytes file without dying
• dasm3.py is programmed in python, can process a 64k random bytes file without dying, and comes with links and an explanation how the program works and how data is organized (jackpot!)

Of all those, Michael Heyeck’s dasm3′.py clearly is the choice for the inquisitive tinkerer:

• dasm3.py comes with explanations of how the program works
• the author wrote it, because he needed it (retro-gaming)
• python is fun and easy
• did I mention that dasm3.py comes with explanations of how the program works?

Marius Gedminas’ disasm.asm is an impressive tour de force, but precisely for this reason not exactly a teaching aid if you want to find out what the domain is all about – the 8086 instruction set and opcodes. Reverse engineering an assembly language program in order to duplicate its function with a Common Lisp program is most certainly the scenic route here, but I preferred a less manly approach.

Marius Gedminas is also the author of disasm.pas, a smart disassembler that can mark unreachable code as data. disasm.pas follows jumps, calls and rets. With its 600 lines of TurboPascal code it is almost as compact as Michael Heyeck’s 300 lines of python in dasm3.py.

disasm.c consumes 1000 lines of code, but that’s about all I know about it. It seems to sort of work, but a segfault is a bad omen. There is no documentation whatsoever, but superficial browsing revealed that the author Kestutis Rutkauskas knew what he was doing in terms of C (despite an unusual coding convention).

So dasm3.py was an easy choice. For enlightenment I picked the most compact program, written in the softest, most dynamic language, the one that came with detailed instructions on how to understand that program. All this in the name of enlightenment, of course, to make stealing easy for the epic hobbyist. It is also the only disassembler on the pet project market that can process .EXE files.

Note that any disassembler, no matter how simple, has the Tunes nature. Disassembly is a very elementary form of reflection, you can’t go any deeper than that. A disassembler is the most basic (and hardest) form of recovering meaning from code. In Tunes, reflection makes the meaning of code accessible to compilers and programs and run-time, what facilitates insane optimizations and water-tight security. However, not only compilers and programs can benefit from access to code meaning. Programmers, too, can work insanely fast when they understand the code, i.e. if they have a mental map of their work. Michael Heyeck’s blog posts give you the fast track to his world of python disassembly:

• Part 1
• Part 2
• Part 3
• Odds and ends

[If you are interested in 8086 assembly, don't miss 8086 Opcode Redundancies I and II.]

The only fly in the ointment was lack of demonstration that dasm3.py works as advertised, so at first I didn’t know if it could serve as a reliable decoder foundation for my “own” homegrown 8086 emulator. Did dasm3.py work for all the edge cases which made my little head spin when I tinkered with my Common Lisp implementation?

As it turned out, dasm3.py worked almost perfectly out of the box. However, getting it into the box was quite an instructive pet project in its own right for a so-so programmer like me. It is a hairy problem, as I will illustrate in the next installments. [Tip of the hat to Michael Heyeck, for patient support.]

Does your pet project have the Tunes nature? Can you demonstrate that it works?

Better computing pipe-dreams with Tunes

the ambition
Tunes is a revolutionary, better way of computing, what includes programming. Unfortunately, Tunes is pure vaporware. It exists only in rough sketches in the minds of the participants in the Tunes programme. It is not remarkable that this discussion happened, it is remarkable that the participants tried to organized it, systematized it, and eloquently wrote about it — all in the hope to turn their shared pipe-dream into reality. We all have pipe-dreams and discussion over the ultimate way of doing computing and, more importantly, programming. “Pipe-dream” suggests that such discourse is fueled by daydreaming and illegal intoxicants, but this is not necessarily so. Many people prefer such conversations of radically better ways of computing over lunch, over the one or other beer, or at a first date.

So there are many such collaborative pipe-dreams like the one at tunes.org going on, right now, as we speak,
but in contrast to those, Tunes.org is

• documented more diligently
• with the aim of systematization
• unboring, if you fit the fringe
• in good taste

The Tunes people are not cranks. They are computer scientists with a bold ambition. Many brought their academic life to the platform.

How does the ultimate way of computing and programming look like? The short answer is: we don’t know, because nobody had an opportunity to actually try it. There are many clues, however, and excellent results
of countless experiments do exist. The Tunes lists many of them. The following portals are perhaps the most
pornographic for computer futurists:

• operating systems: http://tunes.org/cliki/operating_20systems.html
• programming languages: http://tunes.org/cliki/programming_20languages.html
• reflection http://tunes.org/cliki/methods_20of_20reflection.html

Commonplace is the observation that humanity is constantly frustrated with computers, because

• things are not automated enough
• it is hard to get mental model of how things work
• bugs
• changing fashions
• lack of integration
• spam, reboots and bot-nets

Perhaps you can name more.

The Tunes people’s critique of today’s computing includes

• user interfaces
• programming languages
• unix and programming
• security

As a programmer, you know that the status quo is the result of the survival of the fittest, and what “fittest” means here is this:

• the biggest crap (x86 ISA)
• the most byzantine committee-standards (CORBA)
• bloated programs (OpenOffice.org)
• the wheel of reinvention (porting from COBOL to Turbo Pascal to dBase III to C++ to Java)
• or worse, the curse of backward compatibility (again, x86 ISA, legacy apps without source code)

As a programmer, you have opinions on how to fix this pile of coprolithic electronics and programming, of course, and you discuss them with other programmers. And why not? It is an excellent conversation topic, and becomes even more so when aided by alcohol. (For first dates not so much, by the way.)

The Tunes people have fleshed out many exciting and original theses, including:

• kernels are a bad idea altogether
• computer programs must be proofs of their own correctness
• orthogonal persistence makes you happy
• put the garbage collector into the kernel (that does not actually even exist)

The only unoriginal “concept” in Tunes is SPEED. Speed is unoriginal, because raw execution speed is the fetish requirement for all futuristic computing programmes. Nobody knows how truly good computing looks like, but everybody is sure it’d better ran darn fast.

In a word: Tunes is most interesting, and was an inspiration for many a blown night, often to the detriment of other, more productive activities like matching socks or sleeping.

As an implementation, Tunes has not much to show for. Among the millions of futuristic computing programmes, however, Tunes is almost a generation ahead of the competition — 16 years and counting. Nowhere else on the web can you read such an energetic, informed and thoughtful discussion of how to provide for all of society’s revolutionary computing needs. Nowhere else have you such a treasure trove of links that sex you up pretty good if you are a(n) armchair computer progressive. This material can bring life into any discussion on the final OS revolution, the ultimate victory of sense and sensibility. Since the Tunes agenda is vast, here’s the reader’s digest version to bring you up to connoisseur level quickly.

orthogonal persistence
There is no virtual memory in Tunes. The computer treats your entire magnetic memory as RAM. If you turn on your computer, it loads its precise persisted state from memory.

virtual machines
The Tunes programme obsesses over virtual machines, because they are attractive pipe-dreams in their own right. Virtual machines relieve the programmer from the burden of cretinous architectures. It is where hardware, operating systems and programming languages are joined at the hip. The Forth programming language is featured prominently in Tunes, because it demonstrates this point beautifully, in very economical ways. After all, Forth abstracts away hardware and can be hardware, it serves as an operating system and a programming language. Java is known to cover exactly the same terrains and can be used in exactly the same way. However, Java is not even remotely as simple, comprehensible and economical as Forth. And not as powerful.

Lisp
Lisp is not universally liked at Tunes, but all of the participants agree that it is better than most existing programming languages, and that it might be a good foundation for the revolution, before something better can be constructed. Other exotic programming language are frequently discussed, like Joy, Maude and Slate.

reflection and the anti-kernel
The central topic in Tunes is _reflection_, ultimately a programming topic. Tunes programs know a lot about themselves and their components. From this virtue come good things, like insanely optimal optimizations and elimination of kernel technology. Those Tunes programs are supposed to run darn fast, after all. The virtue of introspection has many shapes and faces in Tunes. It is closely related to meta-programming
(program generation) and domain-specific languages. The desire for reflective programs explains the Tunes people’s crush on exotic programming languages like Lisp, Forth and Maude.

• Forth is a reflective language, despite the fact that it is extremely low-level.
• Lisp is not known for reflexivity today, although it is easy to add reflective features. The Lisp machine, for example, was the most reflective platform ever, where all components – down to a single button or the caption on it – were accessible and reprogrammable at run-time, with a click of the mouse. Tunes people like the Lisp machine a lot. Tunes celebrity Francois-Rene Rideau even bought one for himself in 2000 and blogged about it: Buying a Lisp machine in Y2K.
• Maude is an obscure language, here is an overview in wikipedia: http://en.wikipedia.org/wiki/Maude_system. Based on reflection and metaprogramming — it definitely has the Tunes nature. Part of the vision is to write a reflective kernel in something like a better Maude.

Based on these desires – orthogonal persistence, no kernel and ultra-high-level programming – David Madore explains that working with Tunes will resemble working with a HP28-48 programmable calculator, albeit on a much grander scale.

As you see, Tunes is not about a conventional revolutionary computing future. It is decidedly not about new micro-kernel technology, but about new programming languages technology. An example of what Tunes is not can be found behind this link, describing an early attempt to ground Tunes in a a run-off-the-mill computing revolution: http://lists.tunes.org/archives/tunes/1994-October/000001.html.

PIOS, as it was called, wanted to build a better unix, but the initiative was short-lived:

• high-performance
• microkernel
• application-centric

Tunes is very different, that is, more interesting.

If this brief overview of Tunes has made you horny, the best starting point is David Madore’s accessible and lightly written primer: http://www.madore.org/~david/computers/tunes.html.

Less accessible, but eloquently and amusingly written, is ‘Trotskyist Tunes‘.

The deepest and most serious explanation is François-René Rideau’soriginal Tunes manifesto.

And Tunes comes with a FAQ and a mailing list archive, of course.

How do your pipe-dreams of the computing revolution look like? Do your fantasies have the Tunes nature?