Introducing a Tinkerer's Assembler for the 6502/65c02/65816

[scotws]

So after getting that all working in Python, I decided to get a bit more serious and rewrite it in something compiled that will allow parallel assembly. After recoiling in horror from what would be required in C and C++, a dead end with Clojure, and taking into my account my deep-seated phobia of all things Java, I settled on Go (https://golang.org/). Now I'm working my way through the most very excellent book The Go Programming Language by Alan Donovan and Brian Kernighan (yes, that Kernighan), and can report that concurrency is pretty much as easy as advertised in the language.

It will be a while before I have something usable to show, but we'll get there.

[BigEd]

Will watch developments with interest! I'm interested in what you mean by parallel assembly - assembling several files in parallel? Or running a GUI or progress report in parallel?

[scotws]

Nothing as fancy - I don''t even think that Go has a default GUI at this point. But I have an eight-core CPU (Devil's Canyon), and I don't see any reason why you shouldn't be able to do at least the simple translations (say, "NOP" to $EA) in concurrently (I shouldn't have said "parallel" - https://blog.golang.org/concurrency-is-not-parallelism and all that). It could turn out that it's not even worth the effort, but at least I'll have learned Go by the time I'm done .

[whartung]

scotws wrote:

So after getting that all working in Python, I decided to get a bit more serious and rewrite it in something compiled that will allow parallel assembly. After recoiling in horror from what would be required in C and C++, a dead end with Clojure, and taking into my account my deep-seated phobia of all things Java, I settled on Go (https://golang.org/). Now I'm working my way through the most very excellent book The Go Programming Language by Alan Donovan and Brian Kernighan (yes, that Kernighan), and can report that concurrency is pretty much as easy as advertised in the language.

Why do you need parallel assembly? What does that mean for you use case?

I haven't spent enough time looking in to Go, but I find i attractive (I'm a Java wonk myself). A friend of mine just wrote a nice server in Go, he was pretty happy with it. I like that it comes with a first class project structure and build environment instead of leaving you to fend for yourself or at the whims of others.

[scotws]

whartung wrote:

Why do you need parallel assembly? What does that mean for you use case?

Oh, I don't need it at all - the Python version of Tinkasm is so fast for the small file sizes we have that I don't think it doesn't make any practical difference. There is just a part of me that is annoyed that I have eight cores and they aren't all being used (normally four of them run BOINC if the system load is low enough). There are some parts of the assembly process that can be done at the same time - in parallel, concurrently, whatever - so I want to see if that's possible within the simple structure of a multi-pass system.

So far, Go is lots of fun. Of course, after Python, everything seems too complicated, but concurrency is not.

[BigEd]

My limited experience with Occam tells me that it could be quite liberating to build a program out of communicating processes - go has the same model. You can build pipelines or more complex networks. It's a bit like the promise of object orientation: you break down your solution into little bits with simple interfaces which do encapsulated pieces of work. It has the added (incidental) advantage of making solutions which might be more amenable to parallelisation. In many ways it makes software more like hardware, and should fit well with someone who is sometimes writing in HLLs and sometimes in HDLs.

[scotws]

BigEd wrote:

You can build pipelines or more complex networks.

Exactly. For example, in one of my experiments, I've created a pipeline where one function deletes empty lines:

Code: Select all

// Remove empty lines
func p_empty(in <-chan string, out chan<- string) {
        for l := range in {
                if strings.TrimSpace(l) == "" {
                        continue
                }
                out <- l
        }
        close(out)
}

(That's a lowercase "L", not a "one"), font here makes it hard to tell.) What this does is not pass on any empty lines. The function is called like this:

Code: Select all

        // PASS EMPTY - Remove empty lines
        c2 := make(chan string, bsize)
        go p_empty(c1, c2)

(c1 is the channel that leads to this point, bsize is the buffer size) The "go" makes the function concurrent. That's all it takes.

[whartung]

Yea, the latest Java can do things like this easily. I've not done much with it in my work.

The idiom is attractive. You simply write little processors for "independent" queues and mailboxes. It really is pretty much a required aspect of distributed systems. But you'd be surprised how difficult these can be to debug later, especially if you start running in to race conditions.

It never really occurred to me that I was needing some parallel capability in my assembler. I think trivially I could break mine up in to 4 units: file reading -> (stream of lines) -> lexing -> (stream of tokens) -> parsing -> (stream of instructions) -> resolution (my second pass) which creates the overall image. This is then written out, but you can't write until the image is complete. (This is fact may not be true as I won't necessarily have all of the symbols recognized before the second pass starts.)

Of course, at a high level, you can get this behavior "for free" on a Unix system: cat file.asm | lex | parse | createImage > file.hex.

The issue inevitably becomes whether it's worth the extra complexity for the (typically) marginal improvements. When it's worth it, it's worth it, of course.

[BigEd]

One of the ideas behind CSP (which is what both Occam and go use for concurrency) is that you don't get race conditions. You can, however, get deadlock. Possibly - I'm not sure - you can get livelock too.
("There are several tools out there (FDR2, Jeremy Martin's deadlock-checker) for doing checks on properties like deadlock and livelock on CSP process networks."
- http://lambda-the-ultimate.org/node/1723
)
Edit: then again, I see there's a tool for detecting race conditions...
https://blog.golang.org/race-detector

[scotws]

I've had some deadlock during the experiments, which usually means I've forgotten to close the channel after everything is done. Freaked me out the first time because everything I'd read about deadlock up till then involved horrible, catastrophic consequences .

I don't really think it will be worth the effort for in this case if you look at the time involved because the files are rather small, and this is a machine that will do 4 GHz and has SSDs. I could probably do it in bash and it would be that much slower. But it has already been worth it for the learning experience. My only real gripe is that Go doesn't have a "native" GUI of any sort, which would have been nice.

[whartung]

I still need to read the nano-pass paper, but the kestrel computing github.io link seems to be dead.

I'm at the point of needing to add macros to my assembler. Curious how you might be approaching it for yours.

At the same time I need to add things like IF etc. (macros aren't completely pointless without conditional assembly, but…almost).

And along with conditional assembly I need to add "local" labels.

It's been a thought exercise to now, and I think I finally have an approach.

I contemplated just trying to use something like m4(1) from Unix, but I just don't like it. It might be fine for simple macros, but not for conditional assembly, as it has no insight into the values of things like labels and what not. So, in the end I need to tear in to my assembler, and may as well put macros in to it.

Right now, as I mentioned before, take the raw text, as a list of lines, and run them through my lexer which produces a blob of tokens.

I thought about adding a macro expansion phase between the lex phase and parse phase. But macro expansion requires both.

So, the expansion will happen during the parse phase.

During macro definitions, I will just capture the tokens found between the .macro and .endmacro directive, along with a header detailing the macro definition.

Macro expansions will happen inline. When I encounter a macro invocation, I'll capture the argument list. Then I'll literally "print" the tokens captured during macro expansion in to text, do the parameter substitution, run the lexer on them, then feed them in to the parsers token stream.

Currently, the parser is simply iterating on the token collection passed to it. Instead, I'll add a stack of token collections for the parser to get it's next token from, and then each nested macro expansion will just stuff it's expanded tokens collection on to the stack.

The clever part of my plan is I'll just be using the assembler directives to do the work. In many ways, save the actual detection for expansion, the parser does not have a "macro runtime". The macro expands in to instructions to the assembler, just like normal. Things like parameters and such

So, for this crude example something like this:

Code: Select all

.MACRO INCR addr, inc
    .IF %0 = 2 ;; inc is optional, %0 is number of args, check if we have 2 args
        CLC
        LDA addr
        ADC #inc
        STA addr
        BCC done
        INC addr + 1
    .ELSE
        INC addr
        BNE DONE
        INC addr +1
    .ENDIF
DONE
.ENDM

During expansion: INCR mylabel, 2 expands to:

Code: Select all

%0 = 2 ;; number of arguments
%1 = mylabel
%2 = 2
    .IF %0 = 2
        CLC
        LDA mylabel
        ADC #2
        STA mylabel
        BCC done
        INC mylabel + 1
    .ELSE
        INC mylabel
        BNE DONE
        INC mylabel +1
    .ENDIF
DONE

The parser needs to already know about things like .IF etc. So, the macro expansion is basically "stupid" and "literal", leaving the heavy lifting to the parser itself.

Mind this is only partially thought out.

But that's my plan so far. See how it pans out.

[BigEd]

Funny how m4 could have been the best thing ever, but the hideous quoting rules puts almost everyone right off.
I've often considered using cpp (the C preprocessor) as a macro facility, but it's not very strong and multiline macros are a pain.

[whartung]

Right, exactly.

m4 falls squarely in the "exactly what you asked for, and not what you wanted".

Like I said, since I have to implement conditional compilation anyway, I may as well address macros in some way. Hopefully I don't have to rewrite my expression evaluator. I want to, just not now. I don't think I do, at least with this design.

Speaking of IF, I don't think it's untoward to have the IF expression have to use references that are already resolved?

For example, I don't think it's wrong to have this illegal:

Code: Select all

HERE
    .IF THERE - HERE > 10
        .DW 100
    .ELSE
        .DW 200
    .ENDIF
THERE

Having that fail because THERE is undefined shouldn't be a problem, anyone else run in to things like this?

[GARTHWILSON]

Make sure you consider what could happen with multiple passes, and phase errors. For example, depending on default values, the condition may not be met the first time through, so one thing gets assembled. On the second pass, if the assembled code pushes it past the number to meet the condition, the other set gets assembled, which may be short enough to again not meet the condition. Since there's a change, it will try a third pass, and again change, and the cycle repeats endlessly.

[BigEd]

Is it worth having a pseudovariable to let the macro know the pass number?