4 ms·

That’s amazing! Congrats. One question: why is var only supported for top level declarations? I’m not a compiler or programming language expert by any means, bu

by dimes 5y ago

That’s amazing! Congrats. One question: why is var only supported for top level declarations? I’m not a compiler or programming language expert by any means, but I thought the general approach was to define a grammar and write a parser for it. I’m curious how global and local declarations diverged so significantly.

dahfizz 5y ago
This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.
- Joker_vD 5y ago
  To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.
  - deleted 5y ago
    [deleted]
  - Someone 5y ago
    You ‘have’ to go back to the start of your function to fill in the correct size of the stack frame (An alternative is to make a stack frame for every variable or basic block. That’s a waste of cycles and code, especially on early machines) Again, the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways (yes, you can stream out your object code without going back and filling in branch offsets but that leads to slow, ugly code) I think the reason this _was_ done in old languages is that parsing and compiling were black arts when those languages were created. COBOL and FORTRAN didn’t use stack frames, Algol invented per-function stack frames and later loosened that to per-block ones. That’s what K&R C did, too. I don’t know which language invented the idea that you could lossen that further, but it might have been C++.
    - a1369209993 5y ago
      > You 'have' to go back to the start of your function to fill in the correct size of the stack frame foo: push ebp mov ebp esp sub esp .stacksz ; ... .stacksz = 0x14 leave ret > similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways Pretty much this. I'm with Joker_vD on this one; I don't see a problem here.
      - Someone 5y ago
        Neither do I. That’s why I wrote “the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else”. The above doesn’t solve the problem, though. It moves it to the assembler.
      - benhoyt 5y ago
        Thanks, that's a great idea -- not sure why I didn't think of that, as I am using the assembler to figure this out for if/else forward branches already (as the parent comment pointed out). I've added a paragraph to the article mentioning this comment. Thanks! Another approach I thought of is, instead of printing the output right away, append to a list of strings you'll output later, and patch it up yourself. But if we're using an assembler, we might as well get it to work for us. (The patching technique is commonly used for patching binary machine code.)
- makapuf 5y ago
  But here its only the var syntax that is not allowed, the newvar:=someexpression() is allowed, having the same effect of declaring a new local variable if I understand correctly? Edit: typo
  - yencabulator 5y ago
    I think it's just a case of keeping it simple. Basically, it looks like Mugo supports what Mugo consumes (and about two simple additions). Adding local `var` parsing likely would complicate the hand-crafted parser.
    - benhoyt 5y ago
      Yes, that's correct. I actually initially implemented local "var" parsing, but was never using it in the compiler, so I removed it to trim it down and keep things as simple as reasonably possible.

by dimes 5y ago

dahfizz 5y ago

This is a common simplification in compilers. Even C, until 1999, forced you to declare your variables at the top of the function before any code. Its not a limitation of the parser, but simply that having variable declarations anywhere makes the compiler more complex. Its harder to calculate stack space / stack pointers when the variables are declared all over the place.

Joker_vD 5y ago
To clarify why the stack usage calculation is hard when local variable declarations are allowed everywhere, consider compiling this example code: int a; if (...) { int b; int c; if (...) { int d; } else { int e; int f; } int g; } else { int h; } int i; Let's start assigning offsets to the variables, starting at offset 0. The "a" variable gets 0, "b" gets 1, "c" gets 2, "d" gets 3, "e" gets 4, "f" gets 5, "g" gets 6, "h" gets 7, and "i" gets offset 8, so we need to allocate 9 * sizeof(int) bytes on the stack for the local variables. Wait, there is no complication at all, so what's the problem? Well, the problem is unoptimal stack usage: at any point, only 5 ints at most are alive, so you can alias "b" with "h" and "i", and alias "d" with "e" and "g", and save 4 * sizeof(int) bytes of the stack. But to do this you need to track the nesting levels (so you could reset the current allocated offset back to the one used at the start of the block) -- and if you're writing a one-pass recursive-descent compiler, you get this for (almost) free anyway... huh. Did I miss something? It seems there is actually no complication at all, just unwillingness to implement such a feature.
- deleted 5y ago
  [deleted]
- Someone 5y ago
  You ‘have’ to go back to the start of your function to fill in the correct size of the stack frame (An alternative is to make a stack frame for every variable or basic block. That’s a waste of cycles and code, especially on early machines) Again, the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways (yes, you can stream out your object code without going back and filling in branch offsets but that leads to slow, ugly code) I think the reason this _was_ done in old languages is that parsing and compiling were black arts when those languages were created. COBOL and FORTRAN didn’t use stack frames, Algol invented per-function stack frames and later loosened that to per-block ones. That’s what K&R C did, too. I don’t know which language invented the idea that you could lossen that further, but it might have been C++.
  - a1369209993 5y ago
    > You 'have' to go back to the start of your function to fill in the correct size of the stack frame foo: push ebp mov ebp esp sub esp .stacksz ; ... .stacksz = 0x14 leave ret > similar to how you handle filling in the branch offsets in forward branches in if/then/else, and that’s something you have to do, anyways Pretty much this. I'm with Joker_vD on this one; I don't see a problem here.
    - Someone 5y ago
      Neither do I. That’s why I wrote “the solution to that shouldn’t stop you, as it is similar to how you handle filling in the branch offsets in forward branches in if/then/else”. The above doesn’t solve the problem, though. It moves it to the assembler.
    - benhoyt 5y ago
      Thanks, that's a great idea -- not sure why I didn't think of that, as I am using the assembler to figure this out for if/else forward branches already (as the parent comment pointed out). I've added a paragraph to the article mentioning this comment. Thanks! Another approach I thought of is, instead of printing the output right away, append to a list of strings you'll output later, and patch it up yourself. But if we're using an assembler, we might as well get it to work for us. (The patching technique is commonly used for patching binary machine code.)
makapuf 5y ago
But here its only the var syntax that is not allowed, the newvar:=someexpression() is allowed, having the same effect of declaring a new local variable if I understand correctly? Edit: typo
- yencabulator 5y ago
  I think it's just a case of keeping it simple. Basically, it looks like Mugo supports what Mugo consumes (and about two simple additions). Adding local `var` parsing likely would complicate the hand-crafted parser.
  - benhoyt 5y ago
    Yes, that's correct. I actually initially implemented local "var" parsing, but was never using it in the compiler, so I removed it to trim it down and keep things as simple as reasonably possible.