BASIC-PLUS inline operators, do they actually make sense?

Question

Of the features that were not copied from BASIC-PLUS to MS BASIC only one seems to be a good idea, and I'm not sure it really is. I'd like to hear from people that have opened the guts of MS BASIC to comment.

For those of you who have not heard of it, BASIC-PLUS was a version of BASIC for the PDP-11 machines that ran under the time-sharing RSTS/E OS. It was copied almost verbatim as the original Altair BASIC. A few features were left out of MS, but anyone familiar with an 8-bit BASIC will be right at home in BASIC-PLUS.

Of the features left out were functions for working with matrices. For instance, if you DIM A(10,10) and then at some point do A = A + 1, it would add one to every item, or if you had another matrix you could A = A + B. Very interesting, but ultimately not something I would personally put into the very core of the language, this seems esoteric enough for day-to-day use that functions would seem to be perfectly adequate. Likewise, the CHANGE command just seems like a waste, it avoids a single loop.

BUT, the one that I'm curious about is the ability to put branch- and loop-like operators inline with other code. For instance...

10 A = A + 1 UNTIL A = 10

Now this is a silly example, but it illustrates the basic idea. You could place IF, FOR, UNTIL, WHILE or UNLESS at the end of any line of code and it would replace the commands. For instance, the example above is equivalent to:

10 IF A = 10 GOTO 40
20 A = A + 1
30 GOTO 10

At first glance, it would see there is little in this addition from a code perspective. Yes, writing it all on one line makes it run faster because it interprets line-at-a-time, but of course you could also...

10 IF A = 10 GOTO 20 : A = A + 1 : GOTO 10

I suspect that would run exactly as fast? At least if it caches the line number for the GOTO.

But perhaps I am missing some sort of additional advantage to this style?

Answer 1

I honestly don't remember these structures when I ran BASIC-PLUS on RSTS/E, so I never used them.

I did, however, use them pretty heavily when I moved to BASIC-PLUS on the VAX. I loved BASIC-PLUS on the VAX. We used it mostly with its first class integration with RMS. My singular complaint at the time was its reliance on line numbers for ON ERROR GOTO, even though line numbers were optional. I'm sure if I tweaked my technique, I could have alleviated that a bit, but it certainly didn't feel idiomatic to me at the time, so it ended up a bit of a mixed mess.

We used to call BASIC-PLUS "BAS-CAL-TRAN" because of it being a BASIC with the structured elements of Pascal as well as features of FORTRAN (notably the COMMON blocks).

It was not uncommon for me to used structures like:

SUM = SUM + A(I) UNLESS A(I) < 0 FOR I = 1 TO 10

It was not a large leap for me to find this really readable. I think when read aloud it's more "english like" than the alternative.

I can't speak to what implementation advantage these offer. They, arguably, complicate the compiler (which means a slower and/or larger compiler, both resources which were quite limited at the time). That suggest someone simply liked the syntax better to make it worth supporting. Perhaps there was a tangible runtime boost to make it worthwhile.

You don't find these syntaxes in MS-BASIC simply because MS-BASIC (most BASICs) are running an interpreted stream of tokens. You can visualize each statement being executed directly. For example, when NEXT I is executed in a "normal" BASIC, the interpreter honestly doesn't know when it starts if there's even a FOR statement in effect, much less that it's using I. At execution, the NEXT I is evaluated in situ, and goes hunting.

Now, clearly, when you have something like:

SUM = SUM + I FOR I = 1 to 10

The SUM statement can't be evaluated until the FOR statement is evaluated (in order to properly populate I), but with a MS-BASIC like interpreter, it simply "doesn't know" that the FOR is coming. Supporting such a syntax certainly complicates the runtime.

VAX BASIC-PLUS was compiled (i.e. there was a compile phase, whether it was compiled to machine code, I can't say). BASIC-PLUS on RSTS/E, when I used it, was not compiled. At least, I never compiled it. It ran like MS-BASIC. Type in commands, hit "RUN", rinse, repeat. Obviously, when lines are parsed, the parser could internally rewrite:

SUM = SUM + I FOR I = 1 TO 10

as:

FOR I = 1 TO 10:SUM = SUM + I: NEXT I

If it wanted to (if that's, indeed, how it was done).

But I have no memory of RUN taking any extraordinary amount of time to start up (as if it's running through the program and pre-compiling it, or anything like that). And we tended to write some large programs in BASIC on RSTS/E (we were always running out of memory).

One feature of MS-BASIC was simply that the when you typed LIST, it was as much a "decompiler" as anything. When a line of code is entered in MS-BASIC, it is tokenized (for example PRINT is store as some number, vs the text P R I N T), and this representation is what it stored in memory. This saved memory. When you typed LIST, it would see the token for PRINT, and then dump out the text on the screen.

Now, rewriting the BASIC code from the alternate syntax to the "normal" syntax, internally, you can see that can sort of mess up a LIST implementation like in MS-BASIC.

So, I don't know how on RSTS/E BASIC-PLUS manifested these statements internally. But, either way, clearly BASIC-PLUS was a more sophisticated environment, and more complicated runtime. It helps not being limited to 8K of ROM. Even still, historically, this syntax style never really made it in to the MS style systems. It wasn't brought forward to VB, for example (which essentially had "unlimited" resources in terms of compiler and runtime complexity, especially compared to a PDP-11).

Addendum:

To highlight on @dirkt comment, and to expand on this answer.

I did some exploration, fired up RSTS on SimH, and poked around. Dug through some manuals to get a crash course in BASIC-PLUS I/O and TECO to write a crude hex dump program.

The key outcome, as Dirk mentioned, is that BP is compiled. Not in to machine code, but in to a "p-code", apparently known as "push/pop" code. Stack "machines" were reasonably popular in the day, with the UCSD-P system probably being the most well known.

The distinction between a compiled language, and what the MS-BASIC model implements is important. The MS-BASIC model is, essentially, a parse tree and an interpreter. In BP, the language is compiled in to an actual machine language of its own, even if it's a p-machine. That means that the p-code is un-related to actual source code.

In MS-BASIC, the parsed, tokenized form is essentially a 1:1 relationship with the what the interpreter actually executes, albeit in abbreviated form. In MS-BASIC, for example, were you to do something like: A = 1 + 2, there's no opportunity for the language processor to convert that in to simply: A = 3 through constant folding. It doesn't have that opportunity because of the requirement that the intermediate form represents the original source code.

In a compiled language the compile does have opportunity to do these things, as the goal is semantic equivalence rather than strict interpretation. Now, I can't say whether BP performed anything like this kind of optimization, but rather it has an opportunity to if it chooses to do so.

To the point of the statement modifiers, S = S + I IF I > 0 is, while not impossible, certainly more difficult to implement in the MS-BASIC model, since in that model it interprets the stream of tokens as it sees them, with little "global" knowledge. Whereas the compiler model of BP can readily rewrite those types of statement in to an internal canonical form, that is the compiled appropriately.

Consider this program:

10 PRINT FNA(2)
20 DEF FNA(X)=X*3

If BASIC-PLUS, this is a legal program (much to my surprise), as COMPILING (which happens when the lines are entered) the DEF FNA is, apparently, enough to register the function properly with the run time system. In contrast, in MS-BASIC this program causes an error on line 10, because the DEF FNA has not yet been EVALUATED. One can quibble about the "right" or "wrong" of either of these.

Now, the motivations behind the use of the statement modifiers are still not clear. I'm of the opinion that they're simply syntax sugar. While they offer a potentially more compact form at a source code level, it's not really clear to me that it's enough to complicate the runtime in order to support it. Whatever memory savings in source code is balanced by runtime costs in the compiler, which is also memory bound. The BP runtime system consumed 32K of the 64K available to user processes. If they were truly interested in memory conservation, then adopting a model similar to MS-BASIC would have lead to higher gains. Keeping the source separate from the compiled binary certainly had an impact on overall memory consumption.

As to performance, at a gut level I think that the BP system would perform better than the MS-BASIC style interpreter. Simply because since its an actual compiler, it doesn't have to suffer many of the runtime constraints of an MS style interpreter, including things like scanning for line numbers and labels. At compile time, it can Just Know. Mind, that doesn't mean that it actually does. It still has to deal with the interactive nature of the system, and ad hoc editing.

If I had GOTO 10 someplace in my code, and it was magically pointed to "line 10", what happens when I delete line 10? what happens when I add a line 5? Perhaps it maintains a lookup table of line numbers. There are all sort of things it can do.

It seems to me, however, that the BP runtime is focused on runtime performance in balance with memory consumption (thus the p-code). But at the same time, it may simply have not occurred to the creators to do what the MS-BASIC implementors did in terms of an implementation model.

It would be interesting to know of any other interactive BASIC systems the were implemented similar to BP vs the MS model. It would also be interesting to learn where the inspiration behind the MS model. Did they come upon it on their own, implement something they had seen before? Maybe a new question for the forum.

Addendum 2:

To clarify for @MauryMarkowitz.

We distinguish between p-code and tokenization. P-code is "just like" machine code, it's just machine code for an ideal, pseudo machine rather than a specific CPU. It's notable as typically, especially on the older architectures, to be more compact than actual machine code.

Tokenization is basically a step past parsing. Reducing commands to internal "tokens", or ids (like the text "PRINT" to the value 123. Converting numeric source strings to binary, etc. Languages have, typically several phases of processing. The first two are commonly converting the text in to tokens (this phase is called "lexing", lexicographic analysis), then parsing.

Lexing converts raw text in to higher level constructs (i.e. tokens), then the parse phase works off of tokens instead of raw text.

For example, given a string:

IF "BOB" 123 FOR THEN

That's could lex into <IF-KEYWORD>, <STRING>, <NUMBER> <FOR-KEYWORD>, <THEN-KEYWORD>. The lexer can identify all of these, it's up to the parser to enforce actual syntax.

MS-BASIC tends to do both when a line of code is entered. It lexes the string in to tokens, then it parses for syntax correctness. At the end, you end up with a stream of tokens, in fact you have the same string of tokens you started with. But now, at the end of the process, you "know" that the token list is syntactically correct. This can be sent to an evaluator without the need for it to do any extra error checking (beyond simple corruption).

At the end, this tokenized form is NOT "compiled code". It's an intermediate state for use by the evaluator.

P-code is "compiled code".

Consider this example: (using contrived elements)

A = 1 + 2 * B

As a token stream, this looks like: <VAR-A> <ASSIGN> <NUMBER-1> <PLUS> <NUMBER-2> <MULTIPLY> <VAR-B>.

This is what is sent to the evaluator.

In a P-code, it will look something like this:

PUSH 2
PUSH <VAR-B>
MULTIPLY
PUSH 1
ADD
STORE A

This is a simple stack machine. Like an HP calculator.

A key thing to note is how different the equation looks. In the token stream, it's still roughly in "algebraic" form. The evaluator still needs to deal with issues of operator precedence, among other things.

In the second form, the compiler has already dealt with that and created instruction stream appropriately. The compiler can actually rewrite the source code in to a form more suitable for it's efficient execution.

Using our IF-MODIFIER, as @Dirkt mentioned:

A = A + 1 IF A > 0

The token stream is: <VAR-A> <ASSIGN> <VAR-A> <PLUS> <NUMBER-1> <IF-KEYWORD> <VAR-A> <GREATER-THAN> <NUMBER-0>

Taken at face value, an evaluator does not have enough information properly evaluate this. The compiler gets to process it as whole, and can rewrite it, into something like this:

  PUSH <VAR-A>
  PUSH 0
  COMPARE
  BRANCH-LESS-THAN-EQUAL LBL1
  PUSH A
  PUSH 1
  ADD
  STORE A
LBL1:

You'll notice, again, this looks nothing like the source code or the token stream.

This is a key distinction between a tokenized stream and a compiled representation. There's nothing stopping MS-BASIC from going the compile to p-code route, it just turns out that the tokenized representation has memory savings over the compiled version. You get a "running program" for little more than the memory cost of the source code, vs the compiled version where you have to maintain both the source code and the compiled artifact.

This is notable for an interactive environment, obviously not an issue for a normal "compiled" system. But RSTS BP is an interactive system with a compiler, which makes it stand out in the world of BASICs.

Answer 2

As for "branch and loop like in-line operators are a waste, because they can be emulated with mutiple lines": It's important to remember that on machines like the PDP-11, a user was restricted to 64 KB or less, and it wasn't particularly fast. And if you have a larger scientific program that needs lots of memory for matrices and arrays, you'll notice the difference. So everything that can make it a bit faster, needs less space and saves explicit loops (which are slow) helps. That holds for matrix addition as well.

Also, in-line conditional and loops also appear in other languages, historical and modern, from ARM machine code to PERL

Other languages like MUMPS that very also developed for the PDP-11 also have in-line conditionals (called "postconditionals" because they appear after the command word), so it's nothing unusual.

Edit

I did a little research and reverse engineering, and here are the results. First, a bit of history (do look at the entries with more recent or future dates, they are quite funny. But I assume the old entries are accurate):

Enter the cavalry - a small specialised software house called Evans Griffith and Hart that had already established itself as a “star” with the worlds first LISP compiler. (The founders, like Ken Olsen, had also been at MIT.)

Computerworld article, dated 05-Aug-70, describes an “IL” compiler written by Tom Evans.

Dave Knight suggests that EG&H should contact Hank Spencer as it seemed likely that Digital would contract out a project to “implement the BASIC Editor/Compiler for a PDP-11 Multi-user BASIC”.

[...]

The original idea had been for EG&H to write the BASIC PLUS lexical analyser and create the “push pop” code. A Digital employee would have handled the actual execution of a program, ie what happened after you typed RUN.

[...]

In reality, EG&H were left to do everything-and Tim Hart (the H bit of EG&H) wrote the majority of the code and finished it during January 1971. The run only system was abandoned.

And in fact, the RSTS/E BASIC PLUS as provided by the RSTS/E prebuilt system on the simh software website does compile BASIC to a "push pop code", or, in other words, and intermediate byte code for a stack-based virtual machine similar to UCSD p-Code (and probably many others). This can be easily seen by using COMPILE and extracting or dumping the resulting .BAC file with the rstsflx extractor form simtools. For example, the line

40 K=I+2.5+J

is compiled to

a3 ff 72    ; push float var I
78 41 20    ; push float const 2.5
80          ; add
a3 ff 6a    ; push float var J
80          ; add
a6 ff 7a    ; store float var K
0a          ; end of line
00          ; nop (to pad to even addresses)

Actually, COMPILE dumps part of the work space, including besides the byte code the read buffer for entered lines, the buffer for file versions, line number tables and probably other stuff. New compiled code is added at the end; old code is kept (and probably garbage collected at some time)

So code is compiled to byte code either when entered or when read from file, and RUN executes the compiled byte code.

This is confirmed by the RSTS-11 SYSTEM USER'S GUIDE, page 2-15:

Normally, RSTS-11 accepts each line of the user program as it is entered and, if the line is syntacically correct, translates the line into a form understood by the RSTS-11 Run Time System. (The BASIC-PLUS Compiler produces an intermediate code which is then interpreted by the RSTS-11 Run Time System into a form executable on the PDP-11 computer). As the program is edited, only those lines which are changed are recompiled (i.e., translated).

[...]

Once a program is completely deveeoped and debugged, it may be desirable to avoid the time-consuming practice of compiling the program every time it is brought into memory. For this reason, the COMPILE command has been provided. COMPILE permits the user to save an image of his compiled program, rather than (or in addition to) the source text of the program.

So an IF-inline operator looks like this in bytecode:

100 IF I>5 THEN J=6

a3 ff 72    ; push float var I
78 41 a0    ; push float const 5
92          ; compare: greater
58 00 00    ; conditional jump
78 41 c0    ; push float const 6
a6 6a ff    ; store float var J
0a 00

The post-condition form is nearly indentical:

110 J=6 IF I>=5

a3 ff 72    ; push float var I
78 41 a0    ; push float const 5
92          ; compare: greater
d8 00 06    ; conditional jump
78 41 c0    ; push float const 6
a6 6a ff    ; store float var J
0a 00

The only difference is the conditional jump; I haven't found out yet why there are two, and why the latter form seems to include the size of the THEN-branch.

Now a multi-line version of this with GOTO would take up quite a few more bytes (both in bytecode, and in the additional bytes needed for the line number table entries). It also would be slower, because the lines would have to be looked up in the line number table, which points to the byte code. (Without this indirection, it wouldn't be possible to recompile just single lines as they are entered).

So inline operators do make sense: They are smaller and faster.

Answer 3

Later versions of BBC BASIC (V and VI on the Acorn Archimedes/RiscPC) have structured-programming constructs which, syntactically, look a lot like some of your examples. For example, the following is legal:

WHILE A <> 10 : A += 1 : ENDWHILE

However, a construct like A += 1 WHILE A <> 10 would potentially be faster than the above while-loop. This is because BASIC interpreters - that word is crucial - must first work out what to do, statement by statement, immediately before actually doing it. Although my while-loop is on a single line, it consists of three distinct statements which must be re-parsed on every iteration.

(BBC BASIC uses a tokenised representation of the program, and a lookup table in the interpreter, which makes it quite a lot faster than most interpreters - but it is still an interpreter.)

BBC BASIC For Windows does support whole-array operations using a limited set of operators. This facility is not available on the Acorn versions.

More relevant, I think, is the code size limitations that Microsoft BASIC had to contend with. BBC BASIC V had a 32-bit RISC CPU to work with, and the generous memory sizes that went with it. BBC BASIC II had to squeeze all its facilities into a 16KB ROM and an 8-bit 6502. Microsoft BASIC was typically supplied on an 8KB ROM - either that, or it had to be loaded from disk or tape into an already constrained RAM array.

Compared to that, a 64KB, 16-bit PDP-11 would have been pure luxury, and would certainly have allowed a more generous feature set.

Answer 4

This is a very wishy-washy answer, mostly from the realm of languages I know a little but not a lot, but similar syntax survives today in Python e.g.

result = value1 if applicable(value1) else default

Which is conceptually similar to collection-creation syntax like:

evens_only = [value for value in source_array if iseven(value)]
doubles_mapping = {value : 2*value for value in source_array}
... etc

That do some specific types of loops-on-the-right.

You could also argue that the ternary in C is the same train-of-thought on assignments — result = applicable(value1) ? value1 : default.

The benefit in each case is that it gives the fact of the assignment the dominant syntactic position. So you read it as "I'm definitely going to assign something, I just need to pick what". A more traditional if/else would have to repeat the fact of the assignment and might even inadvertently omit or distort it.

So I'd argue that it is can be a stylistic advantage.

As to performance in a BASIC interpreter, one can imagine that forcing the statement that is the subject of the loop to be a single atom might allow an intermediate representation to be kept as a hard-coded special case. But that's probably about it.

Answer 5

One reason for the unusual syntax was to save memory (as dirkt mentions), the same reason you see the source code of the commonly-used system programs with the combination of backslash statement separators and ampersand continuation markers:

1150    PRINT "Options for 'Confirm:' are:" &
        \ PRINT " ?     This help message" &
        \ PRINT " Y     Log me out" &
        \ PRINT " N     Don't log me out" &

Each of the above PRINT statements could have been on separate line numbers, such as 1151, 1152, 1153, but each line number required an additional entry in the interpreter's line-number table. Each entry occupied memory that could have instead been given to more code of the program.

These savings seems absurd now, but it was important then. The available address space for BASIC-PLUS programs was limited (as was physical memory, an independent problem). The interpreter had to run in the RSTS/E operating system's concept of a "run-time system", and this limited the amount of code available to a BASIC-PLUS program.

Some of the OP's cited unusual syntax comes from the memory that comes from fewer line numbers. Also a concern was security: a mischievous user could start someone else's program at a given line number instead of the beginning, but that was not possible if there was not a line number.

Sometimes, using the style of set comprehensions was a stylistic choice, although not used often. Modern programming's emphasis on readability was less important in the days of BASIC-PLUS, size more.

Speed could not be the highest priority of a coder using an interpreted language like BASIC-PLUS. Anyone wanting speedy BASIC (or memory management via overlays) would use BASIC-PLUS-2.