Crenshaw - Let's Build a Compiler

[barnacle]

I am making it up as I go along... probably I'll have to write a manual eventually. But it's without reference to any existing code (other than Dr Crenshaw's). I have computed goto and gosub, too, free of charge!

Neil

[John West]

Yes, classic Microsoft BASIC (from the 8 bit era) executed the body of FOR/NEXT loops at least once as well. With good reason: when GOTO is your main tool of flow control, there is no expectation of any structure. This works:

Code: Select all

10 for i = 1 to 10
20 if rnd(0) > 0.5 then 110
30 goto 80
40 rem here's a stray NEXT that doesn't belong to any loop
50 next
60 print "finished the wrong next!"
70 goto 130
80 next
90 print "first next finished"
100 goto 130
110 next
120 print "second next finished"
130 rem rest of the program

There is no way for the FOR to know which NEXT it should jump to - there are two that end the loop, and the first one after the FOR isn't part of it at all. You can also have one NEXT belonging to more than one FOR, and worse.
Later BASICs tamed the mess and introduced some structure. I don't have any experience with them, but I expect they've introduced rules about where you can GOTO to prevent things like this. If I was implementing a language now with no need for compatibility with the 1980s, that's what I'd do.

[drogon]

John West wrote:

Later BASICs tamed the mess and introduced some structure. I don't have any experience with them, but I expect they've introduced rules about where you can GOTO to prevent things like this. If I was implementing a language now with no need for compatibility with the 1980s, that's what I'd do.

I'm not convinced about the care over GOTO - it's hard in an interpreter to check for this sort of thing. Especially a line-numbered language which would let you GOTO between GOSUBs. Even with labels rather than line numbers the effort to check for GOTOing inside a FOR, etc. loop is not trivial and might not be worth the (computational) time and effort.

Even in some other languages it's not detected - GOTO in C to the middle of a loop - sure, just do it - and expect the unexpected. Same for GOTOing inside switch statements... Also see "Duff's Device" for an interesting example.

-Gordon

[barnacle]

To be honest, I've really only included goto because it feels as if it should be in a tiny basic. But I reckon you can write structured tiny basic

Neil

[BigEd]

I sometimes have a NEXT guarded by an IF (or even an ELSE) which makes a forward scan of the program text not quite workable. So, it's not just GOTO that's a problem, if you're determined to offer zero iterations as a possibility. There are reasons why that's not the usual way!

[barnacle]

Rats, if/endif is broken. It searches for the first 'endif', not a _matching_ endif, if the test is false.

Rethink required; I'll go and put some winter tyres on the car while I think about it.

Code: Select all

> list
   10 input q
   20 if q > 10
   30   print q
   40   if q > 20
   50     print "big"
   60     endif
   70   print "small"
   80   endif
   90 print "done"
  100 end
> run
? 3
endif at line 60
small
done
> run
? 15
15 
endif at line 60
small
done
> run
? 25
25 
big
small
done
>

Neil

[drogon]

barnacle wrote:

Rats, if/endif is broken. It searches for the first 'endif', not a _matching_ endif, if the test is false.

That's exactly the issue I have in my "big" Basic - there I brute-force search for the corresponding ENDIF by counting IFs (+1) and ENDIFs (-1) until the count is zero.. The code actually calls a routine called "findElse" which is really looking for an ELSE statement (on a separate line) but the up/down count still applies and will return upon the corresponding ELSE or ENDIF statement when the counter is zero.

Flow control can then continue at the ELSE as normal and falling into an ENDIF is OK and is simply ignored.

(So you can get ELSE for free as it were)

It's not perfect as if the Basic coder has forgotten an ELSE or ENDIF then things can become interesting. I can trap a named PROC or FN but can't detect a numbered GOSUB...

-Gordon

[barnacle]

That's the approach I've used, which seems to work on this small but perfectly formed programette...

Code: Select all

> list
   10 input q
   20 if q > 10
   30   print q
   40   if q > 20
   50     print "big"
   60     endif
   70   endif
   80 print "small"
  100 end
> run
? 5
endif at line 70
small
> run
? 15
15 
endif at line 60
small
> run
? 25
25 
big
small
> 

I leave trying to catch programmer's logic errors to them; that's why they get the big bucks, right? But this follows the same logic as the indentation in list, so it might give a hint there. Still playing with broken cases.

Neil

[BillG]

Some discussion of FOR loops in BASIC here:

viewtopic.php?f=2&t=6182

[barnacle]

Thanks, Bill. Some interesting thoughts, though the most significant observations are perhaps 'that all basics aren't the same' and 'so just document what it does'.

One point of difference is that mine uses a generic 'next' as the end of the for loop, irrespective of the variable. So I don't have to worry about a matching variable at 'next' but I do need to keep track of nested loops. If someone is going to do something silly like jumping into (or out of) a gosub, or the middle of for/next, then the result is going to be 'undefined'... documenting what it might do in every possible scenario is probably beyond my brain.

Annoyingly, I had a working nested for/next previously but I broke it when I changed from line numbers to line pointers as the location mechanism. For some reason, at the moment,

Code: Select all

			do
			{
				printf ("for loop: line %d\n", *(uint16_t *)where);
				where = execute(where);
				printf ("where = %p\n", where);
			}
			while (NULL != where);

doesn't like it when where is NULL, which rather defeats the object of the exercise. I can segfault, core dumped, with the best of 'em

Neil

[BillG]

barnacle wrote:

For some reason, at the moment,

Code: Select all

				printf ("for loop: line %d\n", *(uint16_t *)where);

doesn't like it when where is NULL, which rather defeats the object of the exercise. I can segfault, core dumped, with the best of 'em

You are trying to print a number at NULL...

[barnacle]

Yep, caught that one but thanks anyway!

[drogon]

barnacle wrote:

'that all basics aren't the same'

Very very true.

In the 80s (maybe late 70s too) we were all typing in programs from books, magazines, etc. adapting and changing them as we went for out particular dialect or system - and even then sometimes it really wasn't easy when you have graphics or sound...

With regard to FOR/NEXT... My TinyBasic does require the variable name, and it's matched against the top of the FOR stack which holds the (hopefully) matching variable name. This has the advantage in that it can detect incorrectly nested FOR loops at a slight speed disadvantage...

My other Basic does loops somewhat differently in that there is a common construct of CYCLE...REPEAT for all loop types - FOR, WHILE and UNTIL (with BREAK and CONTINUE) - the latter (WHILE/UNTIL) can be at the top of the loop or bottom. It was quite a lot of code to make it all work sensibly but an 8-bit micro wasn't my target then...

-Gordon

[barnacle]

Aha, resolved my nesting for issue... turned out that I was starting at the wrong line when I was calculating the matching next. I've also tested that I can have a do-nothing loop if the 'for' condition is greater than the 'to' condition, which is handy.

Code: Select all

> 10 for p = 1 to 3
> 20 print "hello "; p
> 30 next
> run
hello 1 
hello 2 
hello 3 
> 10 for p = 3 to 3
> run
hello 3 
> 10 for p = 4 to 3
> run
> 

Now to see if my find_pair() routine - it seeks the location of the matching pair of if/endif, for/next, and do/while - broke anything else...

Neil

[barnacle]

Well, do/while stretched my brain, but eventually:

Code: Select all

> list
   10 a = 0
   30 do
   35   b = 0
   40   do
   50     print a * 10 + b;
   60     b = b + 1
   70     while b < 10
   75   print
   80   a = a + 1
   90   while a < 10
  100 print "done"
> run
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39 
40 41 42 43 44 45 46 47 48 49 
50 51 52 53 54 55 56 57 58 59 
60 61 62 63 64 65 66 67 68 69 
70 71 72 73 74 75 76 77 78 79 
80 81 82 83 84 85 86 87 88 89 
90 91 92 93 94 95 96 97 98 99 
done
> 

It was tricky: the 'do' sits there looking all innocent, but it has to remember where _it_ is, where the start of the loop is, and where the first instruction after the 'while' is. 'While' returns either a null if the expression is true, or the address of the next line if it's time to escape.

This code still has a load of debugging comments, and needs some clearing up of no-longer required branches, but...

Code: Select all

char * do_do (char * where)
{
	/* Execute the 'do' clause by calling it recursively; it continues
	 * until the matching 'while' statement. That statement returns NULL
	 * if its comparison clause is true, indicating that the loop should
	 * continue, or the address of the line following 'while'
	 */
	
	char * loop_address;	// first line in the do loop
	char * cont_address;	// first line after the while
	char * while_address;	// the while line number
	
	where -= 4;
	//printf ("do at line %d\n", get_line(where));
	where = find_next_line (where);
	loop_address = where;
	while_address = find_pair (where, DO);
	cont_address = find_next_line (while_address);	// first line after while
	//printf ("cont = %d, loop = %d\n", 
	//	get_line(cont_address), get_line(loop_address));
	do
	{
		where = loop_address;
		do
		{
			// when we execute the while, we are returned a NULL if the
			// condition is true
			//printf("do: executing line %d\n", get_line(where));
			where = execute(where);
			if (NULL != where)
			{
				//printf("in do: next line %d\n", get_line(where));
				if (get_line(where) == get_line(cont_address))
				{
					//printf ("break\n");
					break;
				}
			}
			else
			{
				//printf ("inner done, pointing to %d\n", get_line(where));
			}
		}	
		while (NULL != where);
	}
	while (NULL == where);
	//while (get_line(where) < get_line(while_address));
	return where;
}

uint8_t * do_while (uint8_t * where)
{
	/* test a condition; if true, return the value zero 
	 * otherwise, return the address of the next line
	 */
	 if (compare())
	 {
		 //printf ("while is true\n");
		 return NULL;
	 }
	 else
	 {
		 //printf ("while is false\n");
		 return find_next_line (where - 4);
	 }
	return where;
}

Like the other loop constructs, it can call itself recursively to allow nesting.

Neil (that took far too long!)