Coloring Book
There's so much to say and I'm very aware of how much won't make it into this post. It will be far short of the platonic ideal of what this post Could_Be. So, I have to just be down with that and write what I have time for. (And if not, then it will just stay on my hard drive.) The title refers to register (graph) coloring, which is relevant to the subsequent post but not broached.
This quarter I've had some assembler homework. That's fine, I've been down here before and accept the limitations of this level. (Ie, don't expect to accomplish much without Dedicating_Yourself_To_It.) However, I'm really missing the ability to have variable names be part of the program rather than cordoned off into comments above or to the side of what's written. Plus, the dollarsign - which is the first character of any register name - is not a button I commonly press.
So, I decided that I need a register allocator. Or, more accurately, I need a tool that will serve as a symbol table that will replace variable names with registers. (Mind, to go too far is to implement a buggy, ill documented subset of a C compiler.) As I don't have long before this last homework is due, there's no time to make it at all fancy. In fact, if I'm not at mvp by 5 tomorrow, I'll have to drop the whole thing. 5pm is a bit arbitrary, but the weekend is my time to really work and this tool can't be a distraction. (I'm at minimum vomit inducing product, presently.)
As usual, it's best to show what I mean. So, first is some code with variable names, and then the intended output. I admit that the comments become a bit unwieldy. If it's obnoxious (or I'm using long names), I'll probably just put it above or below.
addi mask, _0, 255
sll shift_n, arg1, 3 # 8 * nibble num
sllv mask, mask, shift_n # 1s over specified byte
and char, mask, arg0 # extract charaddi $t0, $0, 255 # mask
sll $t1, $a1, 3 # shift_n, arg1; 8 * nibble num
sllv $t0, $t0, $t1 # mask, mask, shift_n; 1s over specified byte
and $t2, $t0, $a0 # har, mask, arg0; extract char
Unfortunately, I didn't think to start this project earlier in the quarter. I designed the algorithm to use on Tuesday, but was busy during the week and deferred implementation. It's unfortunate because this tool is the sort of urgently useful thing that would have helped me engage with the material in another class I'm taking, 'symbolic programming.' In practice, this has meant 'alternative programming paradigms.' We've been learning to use Common Lisp and, recently, Prolog. I would have liked to have built an allocator using either of the two.
However, I haven't been practicing with them much and don't feel comfortable enough with the requisite stateful transformations and file i/o. Again, I blame the urgency of my situation. However, during the summer, I'll have a lighter load and intend to revisit this project in their fashion. CLisp could certainly transform the instructions, but I blaunched at the list juggling that I would have to perform to move around these strings.
Prolog, initially, looked wildly unsuited. I refrained from considering it impossible, because its chapter in "Seven Languages in Seven Weeks" included an interview with a marine biologist who used it to make schedules. Oh, Prolog belongs to the logic paradigm. That means, essentially, inputting a 'database' of facts and rules before querying its interpreter about the relationships that are deducable.
I despaired of having it communicate sequence. Man. I'm supposed to frontload a lot of information to communicate these conclusions. I don't have time. Do I post or not? Recognizing that I wouldn't have time to make a prolog version permitted me to consider the problem from another angle. Specifically, rather than trying to give it the above, I could give prolog a db of information of how long the variables were in use, and let it associate the symbols with registers that way. Unfortunately, to do so would mean having another program analyze and extract that information for prolog. That's almost all the work already. But, if utility isn't the goal, it becomes a good practice using prolog.
Considering the above example, I might have the preprocessor produce something along the lines of
alive(mask, 1, 4). % form of: (symbol, first line, last line)
alive(shift_n, 2, 3 ). % this is a comment, by the way
assigned( X, t0 ) :- alive( X, 1, Y ), Y is < 5. % a rule
> assigned( mask, Prolog_chose ). %= in the interpreter =%
>>Prolog_chose = t0.
I've not figured out the actual rules to convince prolog to 'change' the constants within facts, if that's even possible. I may not need to, as prolog will probably just show me permutations of possible solutions. Still, it put this problem in the ballpark, so I'll have at it after finals. Looking at this, I see how it won't be comprehensible, even to me in several months. Like, what's the syntax of those rules and why can't prolog assign stuff? Oh well. If this is really wretched, I'll rewrite it or make an appendix type post later.
Failing the opportunity to beat my square intent into these spherical holes, I've turned to python to let me quickly make an allocator. I put it on github, because github understands polyglot projects. Bitbucket always asks what the primary language of the project is, which flies in the face of reimplementing the same program in different languages.
For the moment, the allocator really only handles triple arity operations best. I'll fix the rest tomorrow. And that's all I have time for. I'm going to bed. bed, bed, bed, bed, bed.