MDV Software Reclamation

[bwinkel67]

For anyone looking through the the CL source, I was perusing my old code for the BASIC interpreter and what I do in the present is slightly different from what I did almost 30 years ago. I've mastered the split between lexical analysis and parsing a bit better now. If you take a peek in the PARSEcmds() function you see that I first call getcmd() to grab the top level token (which inevitable will be a keyword) and then do a string equality for each potential parse (i.e. is it a "for" or an "if" etc...). When I'm in a specific parse (say for a "for" loop) I then call, in context, either getvar() or getsym() or getkey() since a "for" first has a variable followed by and equal "=" sign, etc... It's the last function, i.e. getkey(), that could be confusing because in reality getcmd() and getkey() kind of do the same thing. The getkey() function does optimize a bit since it is not returning the keyword but taking it in as parameter and checking that it is there as expected (so it eats the characters from the input but doesn't need to store and return them).

When I currently write a parser I create a generic getToken() function (and I camel case all of my variable and function names :-/) and it returns the next token (either a keyword, symbol, variable) and then it gets parsed it in context. The CL prototype was my first crack at writing an interpreter and I recall I had a lot of fun doing this, especially on the QL while I was awaiting to save up the almost $2000+ to by my first color Macintosh (yup, they were pricey then). With my old code, I really only don't like the fact that I have both getcmd() and getkey(), both kind of doing the same thing, since a command is a keyword and vice versa, but otherwise I'm ok with it since it does optimize it a bit. What really should happen is that a getToken() function ought to grab each token, then actually tokenize it into a numeric value (lookup table), and finally we do a integer comparison when we parse and not a string equality (which is costly) -- at least for a recursive descent parser such as this. If you use a tool such as lex/yacc then you parse and execute separately and build and internal parse tree (also pretty fun if you've never done it).

Of course I never even wrote the context-free grammar for my language. That's the first thing one ought to do before writing the parser. I guess I kind of knew what I wanted, a sort of cross between ZX81 BASIC and SuperBASIC. I think for fun I'll try and create the grammar to see what it looks like because it will be easier to determine how to change the parser if a grammar is associated with it (esp since I may want to convert it to pure ZX81 BASIC for creating a simulator). I usually create a BNF formatted one which has odd syntax since it uses "<" and ">" for its non-terminals (confusing in the post mid-90's web word where that syntax was usurped by HTML tags -- BNF came from the 60's). My grammar starts out something like:

<CL-BASIC> ::= <code>
<code> ::= <statement> | <statement> <code>
<statement> ::= <linenum> <basic-stmt>
<statement> ::= <shell-stmt>
...

Might require a little thought with the difference of line numbered vs non-line numbered stuff since BASIC can also occur without line numbers and commands can have them.

[stevepoole]

Hi Bwinkel67,

Your code (listed in post 6.23pm) is not random. Renumber it to 1000 and merge it to the end of my code (listed in post 8.49pm)
Then enter the following lines :

10 WINDOW 256,256,256,0
20 CLS: SCALE 256,0,0: seed=get_R$
30 for x=1 to 256
40 for y=1 to 256
50 ink 0: circle myrand/256, myrand/256,1: REMark your random integer.
60 xx=rand_int(65536)/256
70 yy=rand_int(65536)/256
80 ink 4: circle xx,yy,1: REmark my random integer.
90end for yy: end for xx: pause: stop

Enter 'start' then run, and lookat the scatter diagram of the output of your code..... (the black ink !! ).
Regards,
Steve.

[bwinkel67]

Steve,

This was your code:

Code: Select all

240 ::::::::::::::::::::::::::
250 DEFine FuNction r(d)
260 LOCal k: REMark random generator:
270 REMark IF d<0 OR d>65537: STOP
280 c=8421: g=65537
290 k=d*c+1: k=k-(INT(k/g)*g)
300 RETurn INT(k)
310 END DEFine
320 ::::

...and I just rewrote it to:

Code: Select all

50 DEFine FuNction myRand
60   seed = (seed * 8421 + 1)
70   seed = seed - INT(seed / 65537) * 65537
80   RETurn seed
90 END DEFine 

Lines 280 and 290 in yours is just line 60 and 70 in mine. You pass in the seed in line 340 and normalize (i.e. q=r(q): RETurn q/65537) but most random number generators you can call without a seed as they just keep it global, though they do normalize so I could just change my line 80 to RETurn seed/65537 to get a value between 0 and 1. The two usual function calls are rand() and srand(seed) but on occasion the call is parameterized so it can do some normalization -- i.e. rand(1,10) might return a number between 1 and 10.

I tested it, skipping every 128 sequences, starting at whatever seed, and I didn't see any patterns (I plotted 512 points). It's tough finding a good multiplier for a small 16 bit cycle so that's why I asked where you came up with 8421.

Here is my test code:

Code: Select all

5 MODE 4: PRINT #0, "Seed (1-65537)? ";: INPUT #0, seed
10 WINDOW #1, 344, 128, 35, 35: SCALE #1, 128, 0, 0: BORDER #1, 1, 7: PAPER #1, 0: INK #1, 7
15 WINDOW #2, 256, 10, 35, 164: PAPER #2, 0: INK #2, 7
20 FOR i = 1 TO 512
25   FOR j = 1 TO 128: skip = myRand
30   pt = myRand: INK #1, 4: CIRCLE #1, i/2, pt/512, 1
35   PRINT #2, i, pt, i/2, pt/512
40 END FOR i
45 STOP
50 DEFine FuNction myRand
60   seed = (seed * 8421 + 1)
70   seed = seed - INT(seed / 65537) * 65537
80   RETurn seed
90 END DEFine 

And here is the plot it created.

Then using your scatter plot...rewritten for my output:

Code: Select all

5 MODE 4: PRINT #0, "Seed (1-65537)? ";: INPUT #0, seed
10 WINDOW #1, 344, 128, 35, 35: SCALE #1, 128, 0, 0: BORDER #1, 1, 7: PAPER #1, 0: INK #1, 7
15 WINDOW #2, 256, 10, 35, 164: PAPER #2, 0: INK #2, 7
20 FOR i = 1 TO 512
25   x = myRand: y = myRand
30   INK #1, 4: CIRCLE #1, x/256, y/512, 1
35   PRINT #2, i, x/256, y/512
40 END FOR i
45 STOP
50 DEFine FuNction myRand
60   seed = (seed * 8421 + 1)
70   seed = seed - INT(seed / 65537) * 65537
80   RETurn seed
90 END DEFine 

Similarly distributed:

[stevepoole]

Hi again bwinkel67,

Thanks for a great reply, and a great code simplification !

You said < It's tough finding a good multiplier for a small 16 bit cycle so that's why I asked where you came up with 8421. >

In his book 'Algorithms', Robert Sedgewick said " PASCAL for i=2 to n: a(i)=(a(i-1)*b+1) mod m ", where b is 'xx21' ( x being even).

It occurred to me that b could be '8421' , (powers of two) ,which when tested gave good results.

Ideally one would attempt to extend b as 32 16 8 4 2 1, but this can't be done even in HEX$ , as F=15... pity !

Good luck with your project.
Steve.

[stevepoole]

Hi Bwinkel67,

I took your word about the scatter diagrams, but on testing your code (box 3), output is just a straight row of dots !

My scatter code and diagram is Ok, even though on QPC2 there is a slight pixel mismatch due to the aspect ratio.

I am toying with the idea of using '16 8 4 2 1' multiplier, by solving the program in 'MODULO 17' , where it would write as 'G8421' ......
However I would have to look for a 'modulo 17' program. I seem to remember Dilwyn wrote such code ?

Regards,
Steve.

[bwinkel67]

Hi Steve,

I will say that the scale command made absolutely little sense to me. For a 128 high by 256 wide screen, scaling it 100% meant the width had to be 344 when the ratio of 128 to 100 is should really give 328. So I'm not surprised that QPC might have done it differently. I ran mine on QLAY2 which gave me those plots.

As for a good number, look earlier in this thread for a good 31 bit one (16807 multiplier with 2^31-1 divisor). That one was created by a former mentor/professor of mine and I use it now in my own classroom. Pretty decent one I think and its cycle is 2 billion.

[stevepoole]

Hi bwinkel67,

You wrote : << The one I use in my class room is: i = ( i * 16807 + 1 ) % 2^31-1. The magic prime number is 16807 as it relates to 2^31-1 (i.e. 2147483647). >>

Have you tried this with a scatter diagram ? I get reaaly big numbers...such as 7.579186E8 ! So SCALE is a problem....

Steve.

[stevepoole]

Hi again Bwinkel67,
Using your magic numbers, I get a scatter diagram that overwrites itself. (That is, most values get repeated often).
This does not happen much with my magic numbers, where points are scattered widespread.....
Steve.

100 n=2^31 -1 : s=2^32 -1 : scale s,0,0
110 window 256,256,256,0 : cls : over -1 : seed=n
120 for x=1 to 128
130 for y=1 to 128
140 ink 7 : point myrand,myrand
150 end for y : end for x
160 pause 50: goto 120
:
170 define fn myrand
180 seed=(seed*16807+1)
190 seed=seed-int(seed/n)*n
200 return seed
210 end def

[bwinkel67]

Hi Steve,

I can take a look at it sometime this week when I get some time. I'm guessing it's a combination of either the scale command and/or the fact the cycle is 2 billion. What's the biggest number SuperBASIC can store?

With regard of the scatter plot, if you look at the utah.edu link I posted in the first post of this entire thread you can see the scatter plot for 16807 so it is a good multiplier (I believe it is from a paper on random number generators in ACM). Still, repeating that plot on the QL sounds like an interesting exercise and I'll and help get it plotted.

[stevepoole]

Hi again Bwinkel67,

The biggest integer number SuperBasic can store accurately is '9999999999', coded as 1E10.
But SuperBasic floating point numbers can be 1E-616 to 1E617, but only accurate to 10 digits.....
All superbasic calculations default to floats, so your myrand goes out of range.

In myrand, I find tha maximum seed value can be 7.218552E13, clearly an approximate float value.
The QL processor cannot do better than 2^32, ie: 4.294967E9 anyway !

So my '8421' value is best for the QL and its emulators.
QPC2 runs on my 64 bit laptop, but is not optimised for 64 bit basic...

Best Wishes,
Steve.