5 ms·

Jumping Back and Forth

145 points by pplonski86 7y ago

saagarjha 7y ago
Really like how the additions are formatted: "put this code here" is pretty nice. Plus your handwriting is really neat :) A couple of comments: > The right—or wrong depending on how you look at it—set of bytecode instructions could jump into the middle of a block, or from one scope into another. > The VM will happily execute that, even if the result leaves the stack in an unknown, inconsistent state. The JVM (mentioned earlier) prevents this by not offering the tools to do this, because its semantics ensure that the stack is always in a valid state. > Have you ever noticed that the ( after the if keyword doesn’t actually do anything useful? The language would be just as unambiguous and easy to parse without it, like: > if condition) print("looks weird"); > The closing ) is useful because it separates the condition expression from the body. Some languages use a then keyword instead. But the opening ( doesn’t do anything. It’s just there because unmatched parentheses look bad to us humans. Note that many modern languages drop the parentheses altogether. > That is, if you can get past Dijkstra’s insufferable faux-modest self-aggrandizing writing style…Ah, yet another one of my many discoveries. I couldn’t even be bothered to write it up until the clamoring masses begged me to. I know that a lot of people in computer science can be self-absorbed, and I'm all for more modesty, but I think Dijkstra is prolific enough to get a bit of a pass ;) > You have two computers with the same program running on the same exact same inputs—so totally deterministic. You pause one of them at an arbitrary point in its execution. What data would you need to send to the other computer to be able to stop it exactly as far along as the first one was? Just look at a modern scheduler and see what it saves whenever it context switches: that's your minimum set.
- frabert 7y ago
  > Just look at a modern scheduler and see what it saves whenever it context switches: that's your minimum set. I'd call that an upper bound on the size of the minimum set, one that is guaranteed to work with any kind of program. With more info on the executing program you could probably save less state and still keep the program running fine
  - nybble41 7y ago
    It's not an upper bound either since the data saved on context-switch doesn't include the contents of the stack or data segment or other global process state. It's not sufficient to save and restore only the thread context. One upper bound, mentioned in the article, would be the inputs fed to the program thus far and the total number of instructions executed. Another would be the current thread context plus all working memory and other process state, excluding any data which can be proven not to be accessed for the remainder of the program. Which of these is smaller would depend on the program and where it was stopped; at the beginning you just have a (small) counter and no inputs consumed, but then again you may have fed the program gigabytes of inputs and stopped it just before it returned a small amount of summary data.
- andreareina 7y ago
  Well I was going to say that if you were only concerned with stopping execution, you could just count the number of instructions executed but alas TFA mentions that already. I'm not familiar with modern schedulers but it seems to me that to continue execution from a stopping point you'd need to restore (and therefore save) at least the instruction and stack pointers, plus maybe a couple other pointers for stuff like the global and current environments. Obviously if you're operating a register machine you'd need to stash/restore the state of all the registers as well, IIRC x86 uses the stack for that.
- pjc50 7y ago
  > You have two computers with the same program running on the same exact same inputs—so totally deterministic. You pause one of them at an arbitrary point in its execution. What data would you need to send to the other computer to be able to stop it exactly as far along as the first one was? What Dijkstra is really getting at here is that there is an "approximate computer" in the programmer's head whenever they are reasoning about the program, and that minimising the amount of information that needs to be transferred into the programmer's head (and keeping it local, rather than scattered about the program!) helps hugely.
  - skybrian 7y ago
    I think he might also have been thinking about how to prove a program correct? To do that in imperative code, it might be useful to have some concept of a program location that's rigorous enough to represent mathematically.
boomlinde 7y ago
The illustrations remind me of Thinking Forth. The book seems to walk you through the implementation of a scripting language all the way from lexing through parsing (manual recursive descent parser, not parser generation), bytecode generation and VM. Seems like a nice read!
- new4thaccount 7y ago
  I assume the author is familiar with Brodie's work if so many of us are.
swirepe 7y ago
I'm a big fan of munificent's work
Twisol 7y ago
The bit at the end about `goto` and Dijkstra is wonderfully written -- I almost wish it were a separate post so I could point people at it directly. An interesting note about that, by the way -- there is a notion of a "loop-nesting forest" in the literature, which is basically a way of taking a flowgraph with cycles and deriving a tree of loops, essentially recovering the "original" lexical structure of the loops. This works best when the flowgraph is so-called "reducible", for which the definition is slightly technical (and I don't have an excellent intuition for it myself). The upshot is that a CFG is reducible if you only use the usual "structured" control flow operators. In the sense that you can recover lexical nesting from a reducible CFG, Dijkstra is right on the money: the dynamic behavior and the static behavior are in much closer correspondence. But once you add goto, you admit the possibility of irreducible CFGs, and it's no longer clear how to recover any hierarchical structure. (There are several types of loop-nesting forest out there, but they focus on recovering different aspects -- there's no perfect solution.)

145 points by pplonski86 7y ago

Really like how the additions are formatted: "put this code here" is pretty nice. Plus your handwriting is really neat :) A couple of comments: > The right—or wrong depending on how you look at it—set of bytecode instructions could jump into the middle of a block, or from one scope into another. > The VM will happily execute that, even if the result leaves the stack in an unknown, inconsistent state. The JVM (mentioned earlier) prevents this by not offering the tools to do this, because its semantics ensure that the stack is always in a valid state. > Have you ever noticed that the ( after the if keyword doesn’t actually do anything useful? The language would be just as unambiguous and easy to parse without it, like: > if condition) print("looks weird"); > The closing ) is useful because it separates the condition expression from the body. Some languages use a then keyword instead. But the opening ( doesn’t do anything. It’s just there because unmatched parentheses look bad to us humans. Note that many modern languages drop the parentheses altogether. > That is, if you can get past Dijkstra’s insufferable faux-modest self-aggrandizing writing style…Ah, yet another one of my many discoveries. I couldn’t even be bothered to write it up until the clamoring masses begged me to. I know that a lot of people in computer science can be self-absorbed, and I'm all for more modesty, but I think Dijkstra is prolific enough to get a bit of a pass ;) > You have two computers with the same program running on the same exact same inputs—so totally deterministic. You pause one of them at an arbitrary point in its execution. What data would you need to send to the other computer to be able to stop it exactly as far along as the first one was? Just look at a modern scheduler and see what it saves whenever it context switches: that's your minimum set.

frabert 7y ago
> Just look at a modern scheduler and see what it saves whenever it context switches: that's your minimum set. I'd call that an upper bound on the size of the minimum set, one that is guaranteed to work with any kind of program. With more info on the executing program you could probably save less state and still keep the program running fine
- nybble41 7y ago
  It's not an upper bound either since the data saved on context-switch doesn't include the contents of the stack or data segment or other global process state. It's not sufficient to save and restore only the thread context. One upper bound, mentioned in the article, would be the inputs fed to the program thus far and the total number of instructions executed. Another would be the current thread context plus all working memory and other process state, excluding any data which can be proven not to be accessed for the remainder of the program. Which of these is smaller would depend on the program and where it was stopped; at the beginning you just have a (small) counter and no inputs consumed, but then again you may have fed the program gigabytes of inputs and stopped it just before it returned a small amount of summary data.
andreareina 7y ago
Well I was going to say that if you were only concerned with stopping execution, you could just count the number of instructions executed but alas TFA mentions that already. I'm not familiar with modern schedulers but it seems to me that to continue execution from a stopping point you'd need to restore (and therefore save) at least the instruction and stack pointers, plus maybe a couple other pointers for stuff like the global and current environments. Obviously if you're operating a register machine you'd need to stash/restore the state of all the registers as well, IIRC x86 uses the stack for that.
pjc50 7y ago
> You have two computers with the same program running on the same exact same inputs—so totally deterministic. You pause one of them at an arbitrary point in its execution. What data would you need to send to the other computer to be able to stop it exactly as far along as the first one was? What Dijkstra is really getting at here is that there is an "approximate computer" in the programmer's head whenever they are reasoning about the program, and that minimising the amount of information that needs to be transferred into the programmer's head (and keeping it local, rather than scattered about the program!) helps hugely.
- skybrian 7y ago
  I think he might also have been thinking about how to prove a program correct? To do that in imperative code, it might be useful to have some concept of a program location that's rigorous enough to represent mathematically.

boomlinde 7y ago

The illustrations remind me of Thinking Forth. The book seems to walk you through the implementation of a scripting language all the way from lexing through parsing (manual recursive descent parser, not parser generation), bytecode generation and VM. Seems like a nice read!

new4thaccount 7y ago
I assume the author is familiar with Brodie's work if so many of us are.

swirepe 7y ago

I'm a big fan of munificent's work

Twisol 7y ago

The bit at the end about `goto` and Dijkstra is wonderfully written -- I almost wish it were a separate post so I could point people at it directly. An interesting note about that, by the way -- there is a notion of a "loop-nesting forest" in the literature, which is basically a way of taking a flowgraph with cycles and deriving a tree of loops, essentially recovering the "original" lexical structure of the loops. This works best when the flowgraph is so-called "reducible", for which the definition is slightly technical (and I don't have an excellent intuition for it myself). The upshot is that a CFG is reducible if you only use the usual "structured" control flow operators. In the sense that you can recover lexical nesting from a reducible CFG, Dijkstra is right on the money: the dynamic behavior and the static behavior are in much closer correspondence. But once you add goto, you admit the possibility of irreducible CFGs, and it's no longer clear how to recover any hierarchical structure. (There are several types of loop-nesting forest out there, but they focus on recovering different aspects -- there's no perfect solution.)