Jump to content

Photo

FastBasic - Beta version available

basic compiler interpreter

29 replies to this topic

#26 vitoco OFFLINE  

vitoco

    Moonsweeper

  • 320 posts

Posted Wed Oct 18, 2017 6:28 PM

I have 2 tenliners that were discarded because of the speed... too slow with turbo basic in the early prototype phase. I think that I could give them a chance here.

But I have another idea that I'd love to try from scratch in fast basic.

#27 dmsc OFFLINE  

dmsc

    Moonsweeper

  • Topic Starter
  • 473 posts
  • Location:Viņa del Mar, Chile

Posted Wed Oct 18, 2017 6:41 PM

Hi!
 

Amazing work ! Sure wish this was available 3 decades ago :)
 
How much free memory is now reported with Integer / compiled ? ~38,200 ?


No, the integer version reports 37662 bytes free. Most of the sise reductions have been in the parser and editor, the runtime is already pretty small, at 2153 bytes (this includes the full interpreter). The floating point runtime is larger at 3038 bytes, a lot of that is used by the math functions.
 

Having option of integer vs default float is obviously huge. But, what are your thoughts on rudimentary support of 8.8 fixed point ? Realistically, for majority of use cases, only add,sub, comparison is needed for 8.8 (e.g. no need for more complex mul/div/etc.). And it's almost as fast as integer.


Should not be that difficult, I think that the easiest is as an option to the cross-compiler. In fact, limiting the support to add/sub/mult/div and with a range from -128.0 to 127.99609375 (-$80.00 to $7F.FF) the current interpreter has all the necessary support. More work should be to implement trig and trascendental functions. But I wonder, is such a short range really worth? I think that 24.8 (or even 16.8 ) should be a lot more useful.

Remember that, as this is an interpreter, going with smaller numbers is not going to be much faster. And currently, the interpreter keeps the 16bit top-of-stack in the A/X registers (and the floating point top-of-stack in FR0), so all the operations are 16bit.

You can take a look at the sources, any help is welcomed :)

#28 dmsc OFFLINE  

dmsc

    Moonsweeper

  • Topic Starter
  • 473 posts
  • Location:Viņa del Mar, Chile

Posted Wed Oct 18, 2017 7:31 PM

Hi!
 

I have 2 tenliners that were discarded because of the speed... too slow with turbo basic in the early prototype phase. I think that I could give them a chance here.

But I have another idea that I'd love to try from scratch in fast basic.


Also, you can always add a new statement or function to make a game smaller.

A little tutorial on editing the compiler/interpreter: suppose that you want to add a new statement "FLIP", abbreviated "FL.", and that takes an integer argument:
  • Edit src/basic.syn:
    • At the "TOKENS" group, add a new token, named "TOK_FLIP".
    • At the PARSE_LINE_COMMAND block, add a new line like: "FLip" EXPR emit TOK_FLIP
    • This means: parse a word "FLIP" (or "FL.", or "FLI."), then an integer EXPRession, that would be pushed to the stack, and then emit code for the new token TOK_FLIP.
  • Edit src/interpreter.asm:
    • At the end, there is the same list of tokens that in the syntax file. Add also "TOK_FLIP" here, in the exact same position.
    • Add, before the "segment JUMPTAB" line, the assembly code for the token:
      .proc TOK_FLIP
        ; Here, A holds the low part and X the high part of the argument.
        ; And at the end, remove the value from the stack and continue with the interpreter.
        jmp pop_stack
      
This is all that is needed.

 

But, many simple statements don't really need any modification to the interpreter. For example, suppose that you want a new statement to write to CHBAS register (to select the character set address), like "CHBAS 120". This can trivially be compiled to "POKE $2E4, 120", so we can instruct the compiler to do just that:
  • Edit src/basic.syn:
    • At the PARSE_LINE_COMMAND block, add a new line like: "CHbas" emit TOK_NUM word CHBAS EXPR emit TOK_POKE
This means:
  • parse a word "CHBAS" (or "CH.", etc.),
  • emit a token "TOK_NUM" (this pushes the following word to the stack),
  • emit the 16 bit value "CHBAS" (from "atari.inc" this is already defined as $2E4),
  • parse an integer EXPRession, that would be pushed to the stack,
  • emit the token TOK_POKE.
 

Note that the emitted code can be as complicated as you want, and the parser support subroutines to factorize common stuff, currently this is the parsing code for "SOUND":
  "SOund" EXPR emit TOK_USHL emit TOK_NUM word AUDF1 emit TOK_ADD "," EXPR "," EXPR_AB emit TOK_SHL8 emit TOK_ADD emit TOK_DPOKE emit TOK_NUM word AUDCTL emit TOK_0 emit TOK_POKE emit TOK_NUM word SKCTL emit TOK_BYTE emit 3 emit TOK_POKE
  "SOund" emit TOK_SOUND_OFF
The first line says:
  • parse a word "SOUND" (or "SO."),
  • parse one integer expression,
  • emit TOK_USHL token, this multiplies the expression by two,
  • emit TOK_NUM with the 16 bit value "AUDF1",
  • emit TOK_ADD, this adds the the last two values (AUDF1 and EXPR * 2),
  • parse a ","
  • parse one integer expression,
  • parse a ","
  • parse EXPR_AB. This is a subroutine that gets two integers and returns the first multiplied by 16 plus the second
  • emit TOK_SHL8, this multiplies the last expression by 256
  • emit TOK_ADD, this adds the last two expressions
  • emit TOK_DPOKE, this stores the 16 bit expression to the address before
  • and then simply emit the tokens TOK_NUM with value "AUDCTL", TOK_0, TOK_POKE, TOK_NUM with value "SKCTL", TOK_BYTE with value "3", TOK_POKE.
With that, the text "SOUND A, B, C, D" is translated to "DPOKE AUDF1 + A*2, B + (C*16+D)*256 : POKE AUDCTL, 0: POKE SKCTL, 3".

The parser will try the first line, if it can't match the input to that, all the emitted code is rolled back and the second line is tried.

#29 VladR OFFLINE  

VladR

    Stargunner

  • 1,564 posts
  • Location:Montana

Posted Wed Oct 18, 2017 7:43 PM

No, the integer version reports 37662 bytes free.

I see. I just simply took the difference between the previous&current one, and applied it to the compiled one (e.g. mixed apples with oranges :) )

Still, that's an impressive number. Do you happen to know the standard BASIC's free memory ?

 

 

the runtime is already pretty small, at 2153 bytes (this includes the full interpreter). The floating point runtime is larger at 3038 bytes, a lot of that is used by the math functions.

Now, that's crazy! 2 KB for an interpreter ! Can you still find your way around the code :) ? How many lines of comments per one line of code :) ?

 

 

 

In fact, limiting the support to add/sub/mult/div and with a range from -128.0 to 127.99609375 (-$80.00 to $7F.FF) the current interpreter has all the necessary support. More work should be to implement trig and trascendental functions. But I wonder, is such a short range really worth? I think that 24.8 (or even 16.8 ) should be a lot more useful.

Forget trig on fixed point. We would just use tables index by the FP.HiByte anyway.

It is, surprisingly, useful, even at such small range. I recently used 8.8 FP for the line equation - where the Hi byte just keeps the integer position for drawing and Lo byte is the fractional part (that gets added another FP Delta value in the loop). The runtime cost was basically the same as adding two 16-bit integers (which is, like, nothing compared to floats) - so this is a very fast alternative to floats.

Now, I'm sure your To-Do List has at least 20 items you want to work on, but I figured I'd ask, since you already got every other major feature implemented already :)

 

 

Remember that, as this is an interpreter, going with smaller numbers is not going to be much faster. And currently, the interpreter keeps the 16bit top-of-stack in the A/X registers (and the floating point top-of-stack in FR0), so all the operations are 16bit.

Oh, ok - now I get it. But, what about compiled code ? Do you still revert to 16-bit, even if the type is just 8-bit ?

 

 

You can take a look at the sources, any help is welcomed :)

No, thanks :) Should I ever get to work on a Basic backend, I should rather go finish my VRBasic compiler for Jaguar (and include Blitter/GPU support finally) :D

 

And honestly, what else is there to implement in FastBasic anyway? At this point, the language looks pretty much final, you can even choose to compile rather then interpret. Perhaps some graphics / PMG libraries ? What's your top 5 features on the to-do list currently ?



#30 dmsc OFFLINE  

dmsc

    Moonsweeper

  • Topic Starter
  • 473 posts
  • Location:Viņa del Mar, Chile

Posted Wed Oct 18, 2017 8:34 PM

Hi!
 

I see. I just simply took the difference between the previous&current one, and applied it to the compiled one (e.g. mixed apples with oranges :) )
Still, that's an impressive number. Do you happen to know the standard BASIC's free memory ?


Atari BASIC, in an 800XL *without* DOS, reports 37902 bytes. With BW-DOS reports 31392 bytes. This is why I always used TurboBasicXL ;)
 

Now, that's crazy! 2 KB for an interpreter ! Can you still find your way around the code :) ? How many lines of comments per one line of code :) ?


I think that the interpreter is rather easy to follow, as each token code is fairly well separated from the rest. Some tokes fall through another, like ADD/SUB, where SUB simply negates the argument and falls to ADD:
TOK_SUB:
        jsr     neg_AX
        ; Fall through
.proc   TOK_ADD ; AX = (SP+) + AX
        clc
        adc     stack_l, y
        pha
        txa
        adc     stack_h, y
        tax
        pla
        jmp     next_ins_incsp
.endproc
This is a threaded interpreter, that means that each token jumps to the next one via a dispatch table (the "next_ins" call). As many tokens (like ADD) need the removal of one value from the stack, the jump to "next_ins_incsp" increment the stack before calling the next token.

To increase the speed (and reduce space), the dispatch code is in zeropage, and at dispatch time Y register already has the stack position.
 

Forget trig on fixed point. We would just use tables index by the FP.HiByte anyway.
It is, surprisingly, useful, even at such small range. I recently used 8.8 FP for the line equation - where the Hi byte just keeps the integer position for drawing and Lo byte is the fractional part (that gets added another FP Delta value in the loop). The runtime cost was basically the same as adding two 16-bit integers (which is, like, nothing compared to floats) - so this is a very fast alternative to floats.
Now, I'm sure your To-Do List has at least 20 items you want to work on, but I figured I'd ask, since you already got every other major feature implemented already :)
 
Oh, ok - now I get it. But, what about compiled code ? Do you still revert to 16-bit, even if the type is just 8-bit ?

There is no compiler yet ;) , the cross compiler generates the same byte-code than the IDE, the only difference is that the cross-compiler applies some optimizations (like constant folding and strength reduction) in the bytecode. But yes, a compiler to native 6502 code could optimize based on range, I think that a value-range pass could discover all small integer usages, like a FOR loop over less than 255 elements.

 
No, thanks :) Should I ever get to work on a Basic backend, I should rather go finish my VRBasic compiler for Jaguar (and include Blitter/GPU support finally) :D
 
And honestly, what else is there to implement in FastBasic anyway? At this point, the language looks pretty much final, you can even choose to compile rather then interpret. Perhaps some graphics / PMG libraries ? What's your top 5 features on the to-do list currently ?


My top missing feature (that I already began to implement) is usage of RAM under ROM in XL computers. Currently I have a version that reports 33039 bytes free, but I want to integrate a fast math package and move the interpreter under the ROM also. The most difficult part wold be the compilation from the IDE, as the runtime must be read from memory and written to disk, and that would not be possible directly.

Easier than that, I plan to change the code so that the cross-compiler can link only the used parts of the runtime, generating smaller binaries. And after that, perhaps working in a cross-compiler to 6502 code,





Also tagged with one or more of these keywords: basic, compiler, interpreter

0 user(s) are browsing this forum

0 members, 0 guests, 0 anonymous users