COMFY-6502: hosting at github

Mostly to support my own development on multiple computers, I’ve moved my Common Lisp port of COMFY-6502 to github. I chose the name cl-comfy-6502 for the repository, although the “cl” prefix is a bit ugly.

The current snapshot of COMFY-6502.

Monthly Boston Lisp Meeting: report

Thanks to François-René Rideau (fare) for organizing last night’s inaugural Monthly Boston Lisp Meeting (Note: future meetings will apparently happen on the fourth Monday of the month.)

I’m surprised I haven’t seen reports on Planet Lisp yet, but I had an enjoyable time. I certainly didn’t meet everyone there, but did get to meet nyef (who showed off some of his fearless adventuring into bare-metal Lisp) and Brad Parker, got to see Kent Pitman in person, and a few other notables, as well as numerous ITA Lispers. Discussion was wide-ranging (I heard only a fraction of the multiple conversations going on), and some of the most interesting stuff to me was discussion about the background of Dylan and Lispers at Apple in the 1990s.

There was at least one person taking pictures; I’m sure they’ll pop up somewhere in the blogosphere.

Looking forward to more great meetings in the future!

COMFY-6502: snapshot

Even though it is hardly a finished product, I’ve posted a snapshot of my current CL conversion of COMFY-6502 Not that I expect a huge pent-up demand for the code, but it might be slightly more interesting than the output examples. Thanks to Henry Baker for allowing the release.

The page also contains a link to the TODO file describing my next steps. (Most immediately, my attempt to include JMP elision was messy enough to convince me I need a different class to represent opcodes+arguments as a unit.)

COMFY-6502: a slight correction

After all the work to write a post showing off COMFY-6502’s ability to reproduce the Red Book tone routine, I made a slight mistake in translation. The code I presented differed ever-so-slightly from the Red Book routine in the case where the Y-register reached zero.

COMFY-6502: work in progress

As I’ve mentioned before, I’ve become intrigued by Baker’s COMFY assembler, and have been working on porting it to Common Lisp, and making it a bit more powerful in the link stage.

One metric to judge the success of this kind of “medium-level” language is how well it compiles compared to hand-written assembler code. For the 6502, there are a few examples of code created by wizards like Steve Wozniak, which you can find copies of around the web, the largest being the Apple II monitor, the Integer Basic interpreter, and some medium-sized ones like the Apple II 6502 step/trace, the mini-assembler, the floating-point “Wozpack,” and the Sweet-16 virtual machine.

This kind of code has a lot of quirks that make it hard to straight-forwardly translate: lots of shared “tail code”, branches known by the programmer to always be taken (to save a precious extra byte consumed by an unconditional JMP), and the classic “fake RTS trick”, pushing a return address picked from a table onto the stack, then using an RTS instead of a zero-page indirect JMP. Common in Woz’s code is a further shortening of the code by arranging the destination addresses to all be in the same 256-byte page, so the high-order byte is a constant. Some of these ideas will likely be possible with intelligent macros, combined with address labels and computation on those labels. I’m puzzling a bit over how to optimize the “same page” condition: whether to include a “link-time assert”, which will issue an error if the code is emitted so as to cross a page, or an even more intelligent “link-time computation” which, given the current available memory space, can choose a location that meets the constraints.

Quis custodiet ipsos…

I don’t know what this says about Lispers’ attitudes toward automated testing, or toward the RT test framework, but the commonly-distributed versions of the RT test framework did not pass their own self-tests.

The apparent cause is that the introduction of a hash-table and tail-pointer in rt.lisp to efficiently find tests by name and insert new tests at the end of the test list were not matched by the updating of the rt-test.lisp to consistently construct the miniature mock-up test suite. This diff for rt-test.lisp, introduces code to dynamically rebind those variables. The patch, in addition to one putting the self-tests into a separate package, has been applied to the HEAD of the CVS repository for GNU CLISP. Note that changing the package changes the names of the tests themselves, which requires editing the expected output in the tests.

Note how powerful and convenient the dynamic binding feature of Lisp (optional, as it should be, in Common Lisp) can be: while running the individual tests, the test procedure can effortlessly construct a sandbox in which to test out the features of the test suite, without destroying the suite of tests that is being sequenced through, and automatically restoring the state of the outer test suite as each test completes, even if the inner test throws an unexpected error—all with essentially no special effort on the part of the original programmer (except, as we see, to identify all of the state that needs to be shadowed.)

Genera and Packages

As I alluded to in an earlier post, Symbolics Genera takes a slightly different approach to packages than most current environments (such as SLIME under Emacs).

Part of that is because, unlike GNU Emacs today, the editor and all its intelligence is running inside the Lisp environment; another part is due to Genera supporting multiple dialects of Lisp, each slightly compatible with the other.

One consequence is that Zmacs pays close attention to the “file attributes line” in your Lisp source files. (That’s the line at the beginning of the file which contains the marker “-*-“). Other Lisp environments use a heuristic, like looking for the first IN-PACKAGE form.

A chicken-and-egg problem arises when loading a file that expects to be read in a particular package. What if the package doesn’t exist? Well, it isn’t possible to use that package to read the file. But the package itself is defined in a file.

For me this caused a bit of confusion, because if you try to load a file with a non-existent package defined in the attributes, and you have not given Genera permission to create the package, it complains that “<package name> is not meaningful as a package name in <Lisp dialect>”.

You can press Resume to allow it to be created, and then the problem goes away until you try to bootstrap again without the package existing.

The answer is found in the documentation section “Specifying Packages in Programs.” If the package attribute is enclosed in parentheses, it is automatically created if it does not exist. Furthermore, you can include one package name, or a list of package names, as the second element of the list in order to specify packages which this package uses.

The other way to approach this is to create a system definition file which defines the packages up front.

(Another aspect that made me more confused is that the package name was “6502”, which if in the package attribute without quotes will read as an integer, which cannot designate a package. I had to muck around a bit trying double-quotes and vertical-bar escapes, in an effort to make the problem go away, before I realized the “not meaningful” was not referring to violating some non-existent rule about package names. From time to time, I would create the package and not realize that made the message go away.)

Learning Genera, bit by bit…

Having hacked on the COMFY code for a while in Emacs Lisp, I got the itch to move it over to my MacIvory, which has been waiting for real work to do. I’ve crafted some tests in the Emacs Lisp using elk-test (trying to add heirarchical suites-of-suites along the way), and wanted to port them to one of the Common Lisp test frameworks (I’m thinking of checking out Stefil, LIFT, and rt, which I’ve used briefly). While copying the files, I ran into a few issues.

1. I couldn’t figure out an automatic way to handle line-ending issues in the text files. I ended up locating the file on the Mac OS side in the file browser, Mouse-R clicking to Edit the file, then M-%, C-q [LINE key] [Return] C-q [Return] [Return] ! in Zmacs, then saving to a file on the Ivory file system. (I like the offer to create non-existent directories on a save.) There is probably a Copy File(s) command I could have used to move them en masse, and I should have been able to code up a quick conversion routine or Zmacs keyboard macro, but it worked.
2. Trying to compile the RT framework, I think I had been misled by my experience in the Genera Development Tutorial. The Common-Lisp mode apparently is Common Lisp the Language, 2d ed. What I was looking for is ANSI-Common-Lisp. The confusion cause all sorts of problems with DEFPACKAGE, and the presence of FUTURE-COMMON-LISP made me even more confused. An e-mail on the SLUG list apparently explains the various Common-Lisp strategies on Genera.

[UPDATE: the old link to the e-mail broke, but gmane.org still has it.]

Baker’s COMFY: a few notes

I’ve been working a bit with Baker’s COMFY-6502 code; a few notes of what I have learned so far.

First, a couple of tiny bugs in the genbrc; the code miscounts the size of the branch instructions, meaning that (- l 2) should be a (+ l 2) and so on. I found it handy to enumerate each clause of the cond. Each clause handles a particular case, such as when the “lose” continuation can be reached by a short branch instruction, while the “win” continuation is far enough away to require an absolute jump.

Second, genbrc, genbr, and compile all provide the address of the resulting “continuation” as the return value. This is perhaps clear when one traces out all the recursion, but it isn’t explicitly mentioned. One interesting case is genbrc when the “win” and “lose” branch destinations are the same: one could simply emit an unconditional branch to that destination, and return the address of that branch but actually returning the destination works just as well. (In the emit routine, if the continuation does not happen to be the next instruction, the unconditional branch is, after all, emitted, moving the continuation to the front of the instruction stream, ready for the non-branching instruction to be emitted just in front of it.)

As for “upgrades” to the package, I have been focused up to this point on moving the knowledge of 6502 opcodes and addressing modes from magic decimal numbers to symbolic processing. Instead of simply emitting a decimal opcode, I have been changing the code to emit symbolic opcodes, such as (ADC ABSOLUTE), with routines to reduce these symbolic forms to the appropriate opcode, including checking for invalid opcodes. Baker’s original code will happily emit opcodes with addressing modes not supported by the chip. Currently, the compiler emits these symbolic codes into the code vector, awaiting a processing step to convert them to the decimal equivalent. Ideally, one would detect invalid addressing modes in the compilation stage, not the post-processing stage.

Some other changes I am contemplating are allowing for symbolic jump destinations, so that object code can be relocated and external labels could be used to relax the restrictions of the current scheme, which requires manually sequencing compilation and storing of addresses.

Baker’s COMFY for the PIC?

I encountered Henry G. Baker’s COMFY compiler a couple years ago. (Baker’s site contains a text article, a TeX format article, and an Emacs Lisp implementation. The ACM published the two articles COMFY theory and COMFY-65) COMFY is not a very high-level language, in the conventional sense, but is an attempt to provide a clean but simple set of control structures on top of conventional machine code. Baker calls it ‘medium-level.’

The resulting compiler is very small; its main task in life is to automate the generation of branch instructions, which is one of the tedious parts of tightly optimizing assembly programs. Yet it allows as well for arbitrary Lisp-style macros.

I found the concept intriguing, but I found the article and the compiler code itself rather obscure. Part of the obscurity is the unconventional names for the 6502 operations, unconventional notation for the addressing modes, and decimal numbers for opcodes (because Emacs Lisp does not accept other radixes). Another is that the implementation is lean-and-mean, emitting code bytes directly into a destination vector—the only output to look at is a vector filled with decimal numbers. The manipulations on the 6502 opcodes take advantage of the low-level bit patterns without explanation. Finally, it uses the term ‘continuation’, which, no matter how many times I think I understand it, scares me, probably because it introduces a highly abstract term into an area like assembly programming which is relentlessly concrete.

I’ve been learning about it by going through the code, restructuring a bit as I go. I’m beginning to be impressed by the subtlety of the code. One thing that is just dawning on me is that the return values of the code-emitting functions is as important as the side-effect. (To those of you chuckling, you see how far I have yet to go.) Lisp can hide that from you when it “looks imperative.”

My longer term goal is to see if the same technique can be fruitful even within the more restrictive limits of the PIC. In order to get there, I’m going to have to gain confidence that I understand the formal concept of the ‘win’ and ‘lose’ continuations, which means, I think, having to come up with legible examples that compile to 6502 code, and use that to firm up my understanding of the compiler. Finally, I’ll try to code the ‘genbrc’ routine for PIC branches.

For the “legible examples” part, I think I will try to break the lean-and-mean single-pass direct-to-binary compiler into a “compile to a vector or list with symbolic 6502 mnemonics” followed by a very simple 6502 assembly pass. A similar enhancement might accumulate a relocation table to allow more flexible linking. (I’m still not used to the idea that the code is emitted starting in high memory and working down.) I’ve begun abstracting out the addressing mode bit manipulations, and probably will add error-checking to make sure invalid opcodes are not generated by mistake.

One thing that I think that will have to go in the PIC version is the shallow binding mentioned in the TeX column, but not in the text version; without a stack, I’m not sure where to save anything. I’m also just a bit worried that the PIC has so many idiosyncracies (e.g., register pages controlled by special flags, instead of a uniform zero-page) that even a medium-level language doesn’t help much.

(I should mention in passing Frode Vatvedt Fjeld’s nifty little Lisp code to generate PIC instructions from the bit chart.)

[UPDATE: I should also mention a COMFY-based assember for x86, implemented in Scheme, called `Sassy’, although I have never tried to use it.]