OSDev.org

I have split my assembler, Assiah, into a separate project from Thelema proper, and have made a separate Github repo for it. The intention is to have a (mostly) table-driven assembler, which should eventually support x86, x86-64 (which at this time I am considering a distinct ISA for design purposes), ARM, and MIPS, at the very least. I am focusing the majority of my work on the support for x86, for the simple reason that it and x86-64 are the most complicated ISAs I expect to support, and I expect that I might paint myself into a corner if I start with the easier ISAs; by tackling x86 now, I can anticipate the majority of the elaborations needed for the others.

However, I could use some assistance, or at the very least criticism and advice. The current design, which is written in R6RS Scheme, calls for a separate data file and register definition file for each of the supported iterations of the ISA - that is to say, there is a pair of files for the 8086, another for the 80186, the 80286, etc. The register file format consists of a series of lists, each containing a list of the register name(s) followed by the bit width of the register in bytes (this does mean that architectures which aren't aligned on multiples of bytes would be unsupported, but how many such architectures are still in use?) . For example, the file 'i8086.regs' reads as follows:

The allowance for register and instruction aliases is meant to allow for more readable code, though it also handles to case of operations with multiple mnemonics (e.g., the JZ and JE instructions on the x86) quite handily.

The format for instructions a good deal more complex; it again consists of a series of lists, each with three outer fields, the list of mnemonics, the list of the possible fields of the opcode, and a text description of the instruction. The fields section is itself a list consisting (in the case of the x86 ISA) of the four common opcode prefixes, the primary opcode (which I will describe shortly), the MOD-R/M type, an enum indicating whether the field can accept the LOCK prefix (and under what circumstances), and an enum indicating the minimum security ring of the instruction. The opcode field is itself broken down into the size of the opcode field, the opcode itself, and the sub-fields which select various conditions or states (it gets complicated - really complicated). A few examples would be:


As complex as this is, I am not sure that I have captured enough information about this ISA to make a truly table-driven assembler. I have repeatedly had to expand upon it already to handle edge cases I hadn't foreseen, and the absurd, irrational complexity of the x86 design and difficulty of following the manuals and the various (often contradictory) web pages documenting it means I could easily miss something important. Even now, I am uncertain enough about how to represent the multiplicity of argument formats that I am have not tried to add that information to the data files; I am hoping I won't need to do so explicitly.

Thus, against my better judgment, I am asking the good folks at this forum for three things: first, a review of the code and data, and of the data formats, to see if there is something I a have overlooked; two, advice on how best to represent the needed data; and third, assistance in entering the volumes of instruction data I am trying to cope with (most of my information is coming from http://ref.x86asm.net/, an excellent if somewhat opaque reference page to whom I am greatly indebted). I have barely scratched the surface at this point, and the outrageous number of instructions and variants thereof are threatening to drive me crazier than I already am. Can anyone give me some good advice on this matter?

I've always wondered if it wouldn't be easier to turn language definitions into simple logical operations (forgive me if I got the shifts/bitfield/values wrong):
The thing is mostly that having one huge struct that necessarily contains all possible information is bound to give issues for instruction sets which don't want to map to the scheme you designed for x86 - as it might look complicated, but there are complications in various other forms of assembly languages that don't look like anything you find in x86 and you more likely want to be provably sure you can handle any arbitrary case.

It is possible to define program semantics like that, though it isn't usually done for implementing language translators, and if you can come up with a feasible method you would be a candidate for a Turing Award. What you're describing sounds like a combination of axiomatic and operational semantics, with some aspects of attribute grammars perhaps. Axiomatic semantics are usually applied to theorem proving and program correctness, rather than translation; denotational semantics (including action semantics) are more often used for that purpose, though no really good notation for automating the process has ever come out of it.

It is a very important area, at least in research, but most undergraduate courses these days are too bogged down in covering the details of the languages being used to get to much theory.

<soapbox>
One of the reasons I favor Scheme as a basis for teaching programming is because the language is simple enough (even taking into account the expansions in R6RS, though the libraries can be a bit tough slogging) that it can be taught to a complete novice in a couple of hours, leaving plenty of room for learning how to apply it. I still think that Structure and Interpretation of Computer Programs is an excellent textbook, though it takes an extraordinary instructor to really make it work - the authors went a little too far in paring down what is already a very small language, and it can be difficult to connect the highly abstract textbook with actual programming practice.
</soapbox>

Valid point, and one I am acutely aware of, and quite concerned about.

I designed the record types such that the types for the specific instruction sets are sub-types of an abstract parent that would be the basis for the assembler - in theory. For example, the parent record types for instructions is:


The concrete forms are found in the x86.ss library file, which defines the format(s) specific to x86 instructions.

Unfortunately, record types (which were only introduced to the official library in R6RS) aren't classes, and don't support a lot of things one would expect coming from an OO background, such as function polymorphism (or generics in the Common Lisp sense, which is more or less the same thing). There are ways to handle this, that have the same basic effect, though they are more explicit and require some extra coding.

The point is, I am trying to keep the assembler's core more or less abstract, and use dispatch tables and such-like to direct the code through the concrete parts.

It's still a "simple" assembler, and unlike those terms seem to suggest, there's no formal verificaton involved at all here. Basically it defines a bunch of lexical to data structures conversions, as well as operations on how to map the resulting structure to an array of bytes. The assembler would just try the parse rules in order (because there are multiple encoding options for many instructions), convert the parse tree into an operation tree, then evaluate it to get the bytes. The assembler can easily make complaints in the order of "expected 'foo', found 'bar' near 'bar foo' " because it has a list of rules that indicate what could have been parsed next.

Basically, the definition has become a program written in a (turing-incomplete) functional programming language designed purely for notational efficiency, that the "assembler" subsequently interprets.

Such a file would look like a bunch of partial rules for the language intricacies, followed by the list of opcodes which do little other than defining the opcode and their primitive bytes, then running it through the previously defined patterns. Even for x86, you need very little corner cases once you have the basics laid out properly. The trick is to define a language that's expressive enough to perform all the steps a hand-written assembler would do, without making it fall back to a full blown programming language.



Thing is, I have personally pondered the subject before since I still have a use for an assembler for a target platform that lacks one altogether, and the obvious absence of anything that doesn't need 101 binaries for "supports all platforms" *cough*binutils*cough*.

I think that's exactly what I need to do, come to think of it. I'll need to consider the best way to do this for a bit before proceeding; but it is actually an excellent fit for the problem, especially since notational programming has always been the forte of Lisp (yes, I know, I need to lay off of the gratuitous language plugs, but here it really does make sense). I'm just surprised I didn't think of it earlier, it's the sort of thing that is obvious in hindsight I suppose. Thank you for the suggestion.

Lots of ideas blatantly stolen from Haskell, mind you

Hey, I'll take it, wherever it came from If you're going to steal from something, Haskell is as good as any and better than most..

OK, I have added a file x86.atmpl with a few experimental examples of my version of you template assembly definition idea. To get a feel for what I have in mind, here is the equivalent of your earlier example (with some elaborations):



I am thinking in terms of implementing it as an embedded language, using a combination of functions and macros, rather than interpreting it per se.

Mind you, the assembly language itself is going to be a bit unusual, as it will be written in s-expressions. For example, the following piece of my old MASM boot loader:


would be something like the following in the Assiah notation:


So, you might ask, why go to the trouble of reinventing the wheel? In this case, the answer is: macros. Lisp-style macrology is much more sophisticated than those typically found in assemblers, and the thing that makes this possible is the s-expression syntax. I intend to experiment with the ability to write a full-fledged language in macros, a la SNOBOL, with the goal of writing the Thelema compiler/interpreter entirely in macro expansions. Crazy? Maybe. But hey, it's my time to waste, and I might actually learn something along the way.