3 ms·

Interesting. When I read the title, I thought "flattening ASTs" would refer to eliminating control structures (ifs and loops) and converting those to a flat lis

by jmmv 3y ago

Interesting. When I read the title, I thought "flattening ASTs" would refer to eliminating control structures (ifs and loops) and converting those to a flat list of instructions with jumps (gotos) between them. And the reason I thought that is because I used this term, "flattening ASTs", when implementing "bytecode compilation" for EndBASIC (see https://jmmv.dev/2022/11/endbasic-bytecode.html https://jmmv.dev/2022/11/endbasic-bytecode.html). This kind of flattening had the nice side-effect of unlocking the ability to implement GOTO as well as the ability to more-accurately capture and handle "interrupts" in the language executor. Anyhow, I'll have to keep this article in mind when I end up implementing flattening for expression evaluation as well, which I haven't gotten around to yet :P

Joker_vD 3y ago
AFAIK, many BASIC implementations worked in-place: each input line was replaced by its tokenization, then by the bytecode, then the labels would be resolved. Consequently, printing the program listing was not a matter of simple "print all earlier input lines" (those are gone), it involved actual pretty-printing. In fact, replacing the program text with its tokenization as the first compilation step was a very popular strategy back in the day, due to memory constraints. IIRC the early IBM FORTRAN compilers, being quite large (they performed quite a lot of optimizations), would not even fit into the core memory together with the source code of any reasonably useful program. So they were instead written as a series of passes (about fifty or so, I believe) each of which took the output of the previous pass and transformed it into the input for the next one; the tokenizer was quite tiny but it freed lot of space (text is quite redundant) so the next passes had room for the auxiliary structures and could themselves be larger, too.
- jmmv 3y ago
  Right, thanks. That’s more than I knew about how the old interpreters worked, although I suspected something along these lines. This explains why I have had so much trouble representing the language as an AST, and I tried to cover this in this other post: https://jmmv.dev/2023/01/endbasic-parsing-difficulties.html https://jmmv.dev/2023/01/endbasic-parsing-difficulties.html

by jmmv 3y ago

Joker_vD 3y ago

AFAIK, many BASIC implementations worked in-place: each input line was replaced by its tokenization, then by the bytecode, then the labels would be resolved. Consequently, printing the program listing was not a matter of simple "print all earlier input lines" (those are gone), it involved actual pretty-printing. In fact, replacing the program text with its tokenization as the first compilation step was a very popular strategy back in the day, due to memory constraints. IIRC the early IBM FORTRAN compilers, being quite large (they performed quite a lot of optimizations), would not even fit into the core memory together with the source code of any reasonably useful program. So they were instead written as a series of passes (about fifty or so, I believe) each of which took the output of the previous pass and transformed it into the input for the next one; the tokenizer was quite tiny but it freed lot of space (text is quite redundant) so the next passes had room for the auxiliary structures and could themselves be larger, too.

jmmv 3y ago
Right, thanks. That’s more than I knew about how the old interpreters worked, although I suspected something along these lines. This explains why I have had so much trouble representing the language as an AST, and I tried to cover this in this other post: https://jmmv.dev/2023/01/endbasic-parsing-difficulties.html https://jmmv.dev/2023/01/endbasic-parsing-difficulties.html