BASIC compiler

Equivalent figures for RiscBASIC are:

Using Virtual Risc PC:

Integer BASIC interpreted : 5549cs
Integer RiscBASIC compiled : 3058cs

Float BASIC interpreted : 7100cs
Float RiscBASIC compiled : 9908cs (uses FP Emulator)

I tried to hack the C program to using VFP¹, but I must have screwed something up. It never increments beyond the first 1/30 (or maybe LDF/STF vs VFP format issues?).

However given the speed that it takes getting there, my mostly-pulled-out-of-my-backside guesstimate is something in the order of 8-10cs. You know, if it had worked. ;-)

¹ Somewhat complicated by the fact that setting an FP register to zero, and adding one (or any constant?) to an FP register don’t appear to be valid operations…hmm…

nothing further done with ‘t’ set on the first line, comma after PRINT accum…

I repeat: it’s ANSI Basic. The idea was to compare different Basic dialects.
Nota: t is used on line 560

The second version is identical, only with all ‘%’ removed.

That’s exactly what I did.

Somewhat complicated by the fact that setting an FP register to zero, and adding one (or any constant?) to an FP register don’t appear to be valid operations…hmm…

Indeed. What instructions would you want to issue to implement these? You’d have to load the zero (as an integer) into a (single-precision) VFP register (FLDS), then convert it to FP (FSITOS or FSITOD); load the 1 (or other constant) into another VFP register, then convert it to FP. Then add the two registers. There are indeed no “set to zero” or “add constant” (integer or otherwise) instructions in the VFP instruction set. (Or at least, there weren’t in the original VFP instruction set that I documented. What if anything has been added to the set since I’ve no idea.)

I have run David Feugey’s tests from above on a few conveniently to hand platforms. VRPC and RPCEmu are on a 3.4GHz iMac.

               VRPC   RPCEmu RPCEmu RPCEmu  PRi3   Titanimm
               6.20   6.20   5.23   4.02    5.23   5.23

Integer BASIC  3445   7647   5400   7744    3132   2308
Float   BASIC  3518   7964   5784   8143    3195   2337

Integer ABC    1675   2015   1963   2001     877    800
Float   ABC    6324   7108   7168   7150    3317   3339

Your documentation matches mine (as you co wrote it!), but debugger and Zap expect UAL.

I did stack R0, MOV 1 into R0, VMOV S1, R0 then VADD.F32 S1,S0,S1 and finally unstack R0 and return.
Do I need to “convert” the integer 1 after loading it into S1? Doesn’t VMOV do this?

Yes, you do have to convert the integer to FP format before you can do anything with it. You also have to convert the zero – which will become +0.0 (which is different from -0.0 – you’d have to FNEGS it if you wanted -0.0 – not that I can imagine why you would!)

UAL? As in Unified Assembler Language? Doesn’t cover VFP at all, afaik – VFP was obsolete by the time UAL came out. But in principle it ought to be happy with VFP instructions anyway, why not?

I was fibbing (unintentionally…) – I didn’t write the VFP documentation at all. I know it fairly well, but it was written before my ARM days. Which bits I wrote and which I merely know well is sometimes hard to remember! But nothing before 1997 or after 2007 is me.

VRPC is fast. I’m curious to know if VRPC DL + ROS 4.02 is faster than RPCEmu + ROS 5.22

@Rick

I looked at your test program and decided it could be used to illustrate my point about gaining speed without using a compiler.

I ran the original on my ARMX6 and it took 2541 cs. I then worked on it to produce the program below and it took 675 cs. As far as I can tell it does an identical job, and if I print the accum% values from both as it runs they are the same. There are no guarantees, though, because I am not working from the original problem, so I may have to do lots of mea culpas when you point out the mistakes. ;-)

t%=TIME
accum% = 0
leftedge%   = -420
rightedge%  =  300
topedge%    =  300
bottomedge% = -300
stepx%      =  7
stepy%      =  15
maxiter%    =  200
FOR count%=0 TO 29
  FOR Y%=topedge% TO bottomedge%+1 STEP -stepy%
    FOR X%=leftedge% TO rightedge% -1 STEP stepx%
      thechar% = 32
      y% = 0
      x% = 0
      FOR i%=0 TO maxiter%-1
        u% = x% * x% DIV 200
        v% = y% * y% DIV 200
        IF (u% + v%) > 800 THEN
          thechar% = 48 + i%
          IF i% > 9 THEN thechar% = 64
          i%=maxiter% REM EXIT FOR i%
        ELSE
          y% = Y% + INT(x% * y% / 100) REM ??
          x% = X% + u% - v%
        ENDIF
      NEXT i%
      accum% += thechar%
    NEXT X%
  NEXT Y%
  IF count% = 0 THEN PRINT accum%
  PRINT count%;"/30"
NEXT count%
PRINT "end, after ";TIME-t%;"cs"
END

Here are things I did, some having a much bigger effect than others:

• Set Basic$Crunch
• Replace WHILE loops with an incrementing counter with FOR...NEXT loops
• Remove the assignment of global variables from inside a loop
• Replace accum% = accum% + thechar% with accum% += thechar%; this would be important elsewhere if WHILE loops had to be used
• Remove surplus parentheses
• Replace IF..ENDIF with single line IF if possible
• use DIV rather than / with integers if possible
• Rely on casting to integer rather than use INT if possible
• Analyse the logic to death – all the AND and OR have gone
• Spread the initial letters of varaibles

I’m curious to know if VRPC DL + ROS 4.02 is faster than RPCEmu + ROS 5.22

I have done a quick comparison on an elderly Windows 7 laptop.

              RPCEmu   VRPC DL
                5.23      4.02
Integer BASIC  11397     12595
Integer ABC     4448      3607

How’s that for a nice clear cut answer.

How’s that for a nice clear cut answer.

Um, 5.22 queried, 5.23 tested :)

How about RPCEmu with RO4.02 vs RPCEmu with RO5.23 vs VRPC DL with RO4.02
thus illustrating whether the speed change is down to differences between RPCEmu and VRPC DL or differences between RO4.02 and RO5.22

How about RPCEmu with RO4.02 vs RPCEmu with RO5.23 vs VRPC DL with RO4.02

And what about the new BBC Basic module on an old OS? Is it easy to extract/copy?
For me, the problem is here, as the compiled version runs at the same speed on RPCEmu, with both ROS 4.02 and ROS 5.22.

A modernisation pack for old OS would be great. I use a few ROS 5 components under ROS 3.11, and it’s very useful.
I just made this for disc components. I never tried to compile standalone versions of components present in ROM.

And what about the new BBC Basic module on an old OS? Is it easy to extract/copy?

They are in the PlingSystem download (ie Distribution of !System for use with pre-RISC OS 5 machines).
You need standalone versions, not ones extracted from a ROM.

Take care not to softload a Basic module more than once, unless you are sure nothing is running that is still using it.

For me, the problem is here, as the compiled version runs at the same speed on RPCEmu, with both ROS 4.02 and ROS 5.22.

I have added results for RPCEmu 4.02. (I don’t have OS5.22 to hand here, OS5.23 is my best offer.)

               RPCEmu  RPCEmu  VRPC DL
                5.23    4.02     4.02
Integer BASIC  11397   17463    12595
Integer ABC     4448    4356     3607

My take on this is the converse. That the compiled versions run at a similar speeds on RPCEmu seems reasonable as they are just machine code reflecting the speed of the emulator, which is the same in both cases. The difference in the BASIC results seems a bit large!

HTH.

@ Steve: It isn’t my program, it is David’s. All I did was tart it up a little and add ‘%’s. I have no idea what it is supposed to be doing – it looks like a lot of screen position (?) calculations for something that never happens…? I just picked upon it because it did a bigger spread of calculations than my example.

• Set Basic$Crunch

Something so easily forgotten. It is not set on my system. Hmmm, I thought I did that in the boot stuff? Must go look…

• Replace WHILE loops with an incrementing counter with FOR…NEXT loops

Otherwise known as “know your language”.

• Replace accum% = accum% + thechar% with accum% += thechar%; this would be important elsewhere if WHILE loops had to be used

Don’t they do the same thing?

• Remove surplus parentheses

That’ll be me. I believe that if there is any doubt as to how the calculation will be performed, add brackets. Operator precedence notwithstanding, just add brackets! ;-)

• Replace IF..ENDIF with single line IF if possible

Good call.

• use DIV rather than / with integers if possible

Back to “know your language”. I think David has mentioned it was a program written in “standard ANSI BASIC”, though thankfully he spared me the awfulness of the keyword “WEND”, as did Sophie. ENDWHILE is much nicer.

• Rely on casting to integer rather than use INT if possible

Again, maybe ANSI BASIC can’t do implied casting?

• Analyse the logic to death – all the AND and OR have gone

It “looked complicated” so I ignored the logic. ;-) But, yes, something I believe in is that if I am writing a function with a complex algorithm in it, I will often write it, test it, make sure it works, and then I’ll delete it and start again. The first stages are helping to get the code flow set up in my head, and the rewritten algorithm is probably not great (as my mathematical ability sucks) but is usually better than the first go.
The first time? I’m thinking in terms of what I want the program to do. The second time I’m thinking like a programmer so can optimise out expensive operations with bit shifting if possible, stuff like that.

• Spread the initial letters of variables

…and reduce them to single chracter values so there is less time spent looking up the variable.

Your result of 1/4 of the speed just by rewriting it is really impressive.
Now let’s compile that! :-P

I thought I’d have a crack at compiling Xeroid with ABC. Here are some of the issues uncovered during this experiment:

• ABC throws errors for a hex value expressed in lower case. test = &a3 causes a “Mistake” error. Somewhere else (SWI number?) it seemed to be a warning, but a Mistake error to give lower case hex as a parameter to a SWI.

• ABC does not understand GCOL r,g,b nor GCOL a,r,g,b.

• ABC cannot handle whole-array assignments, though to be fair, I didn’t realise BASIC could do this either… tz%() = -1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1

• Related, it can’t handle whole array operations px%() = px%() - slip

• ABC gives a list of unknown objects found (variables referred to that were not otherwise defined (actually – it was a debug routine marking reference to LOCAL variables outside of the function that they exist in)) and opens up a window. I guess it is to list them, or something, but the window is completely empty.

Somewhere along the way I messed something up and all I get on-screen is colour changes, no text or anything. I’m thinking I probably gave the wrong GCOL action as this looks like it is flood filling or something.

Notwithstanding, it builds a program that is about 66K long that does not work – Not enough memory (in heap) at line 0. That’ll be the twenty odd megabytes of DIM statements. Unfortunately ABC’s memory management absolutely cannot cope with this, so when I set the WimpSlot to 200MB, it still says that.

Okay, it’s an insane sized DIM, but still… ;-)

They are in the PlingSystem download (ie Distribution of !System for use with pre-RISC OS 5 machines).

Oups, sorry. I did not remember :)

Steve: It isn’t my program, it is David’s

It’s not mine. It’s a generic ANSI Basic benchmark. That’s why I left it (almost) ‘as is’. To be fair with other offers.

though thankfully he spared me the awfulness of the keyword “WEND”, as did Sophie

It was a WEND. I just change it (but I don’t remember why).

ABC gives a list of unknown objects found (variables referred to that were not otherwise defined (actually – it was a debug routine marking reference to LOCAL variables outside of the function that they exist in))

ABC cannot handle LOCAL variables, it assumes PRIVATE variables such that (i) if there is no global equivalent the following will say variable not found:

PRINT FNone
END
DEFFNone
LOCAL a%
a%=6
PRINT FNtwo
=1
:
DEFFNtwo
=a%+1
RUN
Variable not found at unspecified line (ABC)
7, 1 (BASIC)

If there is a global equivalent the following will use the wrong value:

a%=1000
PRINT FNone
END
DEFFNone
LOCAL a%
a%=6
PRINT FNtwo
=1
:
DEFFNtwo
=a%+1
RUN
1001,1 (ABC)
7,1 (BASIC)

It isn’t my program, it is David’s

I knew that, but I was just using it for my example.

Otherwise known as “know your language”.

That is what I am on about, I suppose. ;-)

ENDWHILE is much nicer.

Save us from WEND, but to have separate END keywords – not tokens – for structures seems awkward. Basalt will convert END <space> followed by PROC FN WHILE IF CASE to their correct tokens.

It “looked complicated” so I ignored the logic. ;-)

My other beef: “It’s the algorithm, stupid!”. I was surprised that eventually all that logic was superfluous. I got there in stages, reducing a bit at a time. I do not think “well, it works” is a sufficient reason for sticking with what you already have.

If I understand correctly, optimising compilers will sort out some of this excess, but that is not ABC.

Spread the initial letters of variables … and reduce them to single character values so there is less time spent looking up the variable.

That should really be left to a crunching program, of course. Using meaningful variable names is important.

ABC cannot handle whole-array assignments … it can’t handle whole array operations

That is a where I gave up on ABC so long ago. Writing loops to do the same did not compile to anything like the same speed.

though to be fair, I didn’t realise BASIC could do this either… tz%() = -1,-1,-1, -1,-1,-1,-1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1, -1,-1,-1

But that is still excessive, and can be replaced by tz%() = -1. ;-)

I’ve been having a bit of a play around with what the frontend for a BASIC compiler might look like – trying to see how much effort would be required to get to the point where you can get a syntax tree and start doing the interesting things like checking/resolving expression types or working out the possible program flows. I don’t expect it to go anywhere significant (I haven’t worked on it for the past few days, and I now have other things to do), but I figured it would be worth reporting my findings here.

• The frontend was going to be built using flex & bison, in order to try and avoid too much wheel reinvention. There’d also be the possibility of using the bison grammar to produce a formal specification of BASIC’s grammar.
• However the RISC OS ports of flex/bison/m4 (as currently available from riscos.info) seem a bit dangerous – they managed to crash my Iyonix twice, one time resulting in a broken directory. So at some point I’m probably going to try running them on something with a more disposable filesystem and see if I can get some useful debug output. flex’s header generation is also broken (m4 complains about a temporary file being already open)
• Initially I was trying to write the lexer to work with tokenised BASIC (which certainly makes detecting tokens easy), but I later realised that plain text is a much better way to go – flex isn’t really designed for binary files, and with plain text the compiler won’t be held back by some of the limitations of the tokenised format (line count, line length, no UTF8 support, etc.). For tokenised files it’s pretty straightforward to have an extra preprocessing step which converts to plain text, and doing it this way would also allow you to support different tokenisation schemes.
• The flex & bison combo isn’t very flexible when it comes to context-specific tokens. E.g. for REM and * you need to ignore the usual tokenisation rules and just return everything up until the end of the line as-is. Flex can kind of deal with this by having different ‘start conditions’, but having flex switch start conditions by itself isn’t sensible (you’d have to teach flex about the grammar), and to switch start condition from within bison you need to jump through a few hoops, using mid-rule actions to set and restore the flex state.
• flex & bison are rather crusty old tools. As soon as I started trying to work on a grammar for expressions (coping with different data types) I realised that the default language of C wasn’t going to cut it – there’d be too many unions flying around for me to be able to keep my sanity. Luckily they do support generating C++ code, but I haven’t got round to converting my test code to C++ yet.
• But if/when I do continue I was planning on trying to build a (very simple) BASIC to C compiler which just supports a couple of statements (simple forms of INPUT and PRINT?) and simple expressions – a foundation upon which to build the more interesting things (flow control, complex expressions, DATA, etc.). All the other random statements and functions in the language (graphics, sound, file IO, etc.) can be left until last!

I’ve also discovered some interesting things about BASIC, such as ‘.’ being a valid floating point number.

I was planning on trying to build a (very simple) BASIC to C compiler

I’m sure there was mention of a BASIC to C converter a few months ago! Using Lau? I can’t now find the topic.

There’s a BASIC to Lua converter (written in Lua), but no BASIC to C converters that I’m aware of. And really I was only planning on using C as a simple stepping stone to get a working compiler – if the project was to take off then I’d expect it would need to interface with either gcc or llvm in order to allow for constructs which C doesn’t really support (but I don’t yet fully understand BASIC’s flow control, so maybe C will be fine)

Unless I have overlooked it, I have not seen any mention on this thread of Martin Carradus’s BBC BASIC to Acornsoft C translator, nor of APDL’s BASIC to C translator. Has anyone any knowledge of these?

I’ve been having a bit of a play around with what the frontend for a BASIC compiler might look like

…uh, it was a thought exercise, not a serious proposition! ;-)

they managed to crash my Iyonix twice, one time resulting in a broken directory.

That’s worrisome, in several respects.

Initially I was trying to write the lexer to work with tokenised BASIC

The “compiler” I didn’t write a decade and a half ago used tokenised code. I considered parsing text, but I decided it would just be a lot simpler if I left that to BASIC and worked with the result.

and doing it this way would also allow you to support different tokenisation schemes.

Mmm, BBC era vs RISC OS era; and everything Acorn vs BBfW.

I’ve also discovered some interesting things about BASIC, such as ‘.’ being a valid floating point number.

That’s… strange. I guess Sophie has optimised out the need to specify superfluous zeros.
Still, “a+=.<<.” (which is valid BASIC!) reads like a geek Koan.

I will point you also at some more legitimate BASIC just to highlight that, EVAL aside, there is a worrying amount of flexibility in the language (from the point of view of attempting to compile it). This thread has enough complaints about ABC (possibly justified, if the LOCAL behaviour is correct) to suggest that you’re going to fall foul of somebody’s pet “feature”…what do you mean {obscure behaviour that is likely a bug in BASIC} doesn’t work anymore! whinge! whinge! whinge!

but no BASIC to C converters that I’m aware of.

The Google-fu is weak. Twenty seconds found this: http://www.martinkd.freeuk.com/
[edit: it’s the one Gavin mentioned, but by URL instead of name]