Back in the early 1980’s, the Apple ][ computer was taking the personal computing world by storm, and Microsoft released a compiler for Applesoft BASIC. That compiler went by the name TASC: T<\/u>he A<\/u>pples<\/u>oft C<\/u>ompiler.<\/p>\n
TASC was written by one person in his dorm room while studying at MIT. Microsoft licensed the product and hired the author, who spent the summer at the Northup building\u00b9 polishing the code.<\/p>\n
As noted on page 61 of the manual<\/a>:<\/p>\n TASC is a \u201ctwo-pass\u201d compiler, since it compiles in two major steps. PASS0 simply picks up user inputs and sets up compilation parameters, so it is not really part of the actual compilation process. The Applesoft program TASC runs PASS0.<\/p>\n PASS0 and PASS1 chain to PASS1 and PASS2, respectively. All three passes were written largely in Applesoft, and TASC was used to compile itself.<\/p>\n<\/blockquote>\n Chaining<\/i><\/a> refers to a program instructing the system to replace the current program in memory with another program, but preserve the values of some or all variables. Chaining was a common technique when your program got too large to fit into memory all at once, so you broke it into multiple programs that each handed off control to each other.<\/p>\n Even if you hadn’t made it that deep into the manual, you could have figured out that TASC was used to compile itself because TASC used its own runtime library.<\/p>\n Chaining was not a feature native to Applesoft BASIC. It was one of a handful of language extension provided by TASC itself, through the use of magic comments that begin with an exclamation point. This meant that once TASC development reached the point that it required chaining, it could be run only in its compiled form. There was no way to bootstrap it from the interpreter.<\/p>\n As the author added features, he kept hitting the Apple ][‘s 48KB RAM limit and was forced to delete all the comments from the code, and when that wasn’t enough, he resorted to shortening all the important variable names to one character.<\/p>\n Such is the desperation of developing on a system with very tight memory constraints.<\/p>\n Everything was working smoothly, until the author returned to school for a semester. Upon returning to Microsoft, he found that he no longer understood the code. He had a sprawling compiler, with no comments, and unhelpful variable names.\u00b2<\/p>\n Yet somehow, he finished TASC, and it shipped.<\/p>\n If you dig through the TASC manual, you can find all sorts of wonderful implementation details.<\/p>\n All of the real work happened in pass 1. This performed code generation and left placeholders for references to other locations like branch targets or variables. Pass 2 consisted of resolving these references and patching up the code. Even though Pass 1 had all the smarts and Pass 2 was just doing clerical work, it was Pass 2 that took the most time because it was I\/O-bound, and floppy disks are not speed demons when it comes to random access. Pass 2 was I\/O-bound not only because of the need to patch the object code, but also because the table of line numbers was itself written to disk, there not being enough RAM to keep it in memory.<\/p>\n Pass 2 made a pass through the object code once for each variable, since the references to a variable were threaded through the object code as a linked list, similar to how 16-bit Windows threaded external references through the code instead of keeping a separate fixup table<\/a>. Your program has 100 variables? Then that’s 100 passes through the object code to update references to 100 variables.<\/p>\n When the code generator needed to access a variable, it didn’t do so directly. The 6502 was an 8-bit processor, so none of the variables fit into a register. You needed to call a function to transfer the variable’s value to or from a common staging area.\u00b3 Your traditional code generation went something like this:<\/p>\n To save four bytes at each call site, the address-loading is factored out, and each variable gets a dedicated entry point:<\/p>\n This is a net win if each variable is accessed several times, which is a pretty fair assumption.<\/p>\n To save code size further, the access function was itself parameterized on the type of access.<\/p>\n We are using the trick of jumping into the middle of an instruction<\/a> to provide multiple entry points to a common block of code. The author of TASC was very proud of this optimization.<\/p>\n Related reading<\/b>: Excuse me, has anybody seen the FOCAL interpreter<\/a>?<\/p>\n \u00b9 This is the same building that was next door to the restaurant that inspired an important variable name in the 16-bit Windows kernel<\/a>.<\/p>\n \u00b2 Also, Applesoft BASIC didn’t have local variables. All variables were global. That certainly didn’t help with understanding the code.<\/p>\n \u00b3 It has been said that when you write code for the 6502, you’re not so much writing code as you are writing microcode. The CPU itself has only three 8-bit registers (A, X, and Y), and only A can do arithmetic. Anything of more than ephemeral value must be stored in memory. The real working space was the zero page. For example, you might decide that one region of the zero page was the logical “accumulator”, and most of your time was spent transferring values into or out of that accumulator, interspersed with occasionally performing arithmetic on or testing the value in that accumulator.<\/p>\n Perhaps the most famous example of treating the 6502 as microcode is the SWEET16<\/a> interpreter, written by Steve Wozniak<\/a>, which emulated a 16-register 16-bit virtual processor in roughly 300 bytes of memory.<\/p>\n","protected":false},"excerpt":{"rendered":" The desperation of programming under tight memory constraints.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[2],"class_list":["post-106496","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-history"],"acf":[],"blog_post_summary":" The desperation of programming under tight memory constraints.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106496","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106496"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106496\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106496"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106496"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106496"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}\n
; BASIC code: X = A + B\r\n\r\n ; traditional code generation\r\n lda #address_of_a_lo\r\n ldy #address_of_a_hi\r\n call load_variable_to_accumulator\r\n\r\n lda #address_of_b_lo\r\n ldy #address_of_b_hi\r\n call load_variable_to_arg\r\n\r\n call add_arg_to_accumulator\r\n\r\n lda #address_of_x_lo\r\n ldy #address_of_x_hi\r\n call store_accumulator_to_variable\r\n<\/pre>\n
; revised code generation\r\n call load_variable_a_to_accumulator\r\n call load_variable_b_to_arg\r\n call add_arg_to_accumulator\r\n call store_accumulator_to_variable_x\r\n\r\n ...\r\n ; block of variable access functions\r\n\r\nload_variable_a_to_accumulator:\r\n lda #address_of_a_lo\r\n ldy #address_of_a_hi\r\n jmp load_variable_to_accumulator\r\n\r\nload_variable_b_to_arg:\r\n lda #address_of_b_lo\r\n ldy #address_of_b_hi\r\n jmp load_variable_to_arg\r\n\r\nstore_accumulator_to_variable_x:\r\n lda #address_of_x_lo\r\n ldy #address_of_x_hi\r\n jmp store_accumulator_to_variable\r\n<\/pre>\n
store_arg_to_variable_x:\r\n ldx #4\r\n .byte 0x2c ; swallow next two bytes\r\nload_variable_x_to_arg:\r\n ldx #3\r\n .byte 0x2c ; swallow next two bytes\r\nstore_accumulator_to_variable_x:\r\n ldx #2\r\n .byte 0x2c ; swallow next two bytes\r\nload_variable_x_to_accumulator:\r\n ldx #1\r\n lda #address_of_x_lo\r\n ldy #address_of_x_hi\r\n jmp do_something_with_variable ; uses value in X to decide what to do\r\n<\/pre>\n