Investigate removing context_flags (and Symbol_table) from global state

[seantalts]

Right now in Semantic_check.ml we have two global objects that get modified and passed around a lot: context_flags and the Symbol_table. I think the ways in which we use these typically involve modifying them for the execution of some function and then resetting them back to their original state after the function has executed. It looks like it might be less messy with these two just passed in to the function calls in question and having them return a new pair that we can update with if need be (seems rare). I'm not sure this is the case but we can use this issue to track an investigation into this possibility - maybe some highlighting some places where it's messy vs. clean in each approach and attempting to estimate the net effect of each.

[VMatthijs]

Do you mean that we would rewrite the code in a purely functional style, i.e. passing around the Symbol_table and context_flags in a state-passing-style, rather than doing imperative updates on them? That's definitely a possibility. In that case we'd want to replace the hash table in the Symbol_table with a Map.

I originally chose an imperative style here precisely because I felt the data structures get modified relatively infrequently, so it seemed a bit much to always be passing them around, but that could've been the wrong decision. A functional style would certainly be more explicit, but also more wordy.

[bob-carpenter]

On Jan 11, 2019, at 7:34 AM, Matthijs Vákár ***@***.***> wrote: Do you mean that we would rewrite the code in a purely functional style, i.e. passing around the Symbol_table and context_flags in a state-passing-style, rather than doing imperative updates on them? That's definitely a possibility. In that case we'd want to replace the hash table in the Symbol_table with a Map.

I like this idea. I find this kind of structure cleaner than a global where feasible, especially in terms of the automatic cleanup. But can we make it performant enough? We need random access to that symbol table.

I originally chose an imperative style here precisely because I felt the data structures get modified relatively infrequently, so it seemed a bit much to always be passing them around, but that could've been the wrong decision. A functional style would certainly be more explicit, but also more wordy.

I wouldn't worry so much about wordiness. All the arguments like this can be encapsulated into a single bigger contextual object to cut down on the number of arguments passed around.

[seantalts]

Yep that's all right, and yep I think one effect of this would probably be replacing the Hashtbl with a Map. Maps should have performant-enough (logarithmic with a large base) random access. I might expect it to have lower constant overhead than a Hashtbl at our scales, but if it wasn't performant we could always switch back to Hashtbl for the O(1) access and still change the access patterns around it to be more functional. To be clear it's not that I always prefer functional style, but this pattern we see here seems like it really screams out for something closer to a context manager pattern than the current one where almost every invocation has lines before and after setting and then unsetting the flags. It's not good to leave that kind of code laying around as it's really fragile - easy to forget to set or unset something.

[VMatthijs]

Yep that's all right, and yep I think one effect of this would probably be replacing the Hashtbl with a Map. Maps should have performant-enough (logarithmic with a large base) random access. I might expect it to have lower constant overhead than a Hashtbl at our scales, but if it wasn't performant we could always switch back to Hashtbl for the O(1) access and still change the access patterns around it to be more functional.

Agreed. I think it's fine to do this sort of thing in a purely functional way with a Map. People do it both ways, it seems. See for instance Andrew Appel's Modern Compiler Implementation book. He sketches both the imperative way with a Hashtbl that I've followed here and the purely functional way with a Map. I am still not sure I see why the functional way would be preferable though. The Symbol table is barely updated, except for vardecls and scope. To be clear: I also don't see a reason why the imperative way is superior. I simply chose it because it seemed like the state was not modified very much so could be left implicit.

To be clear it's not that I always prefer functional style, but this pattern we see here seems like it really screams out for something closer to a context manager pattern than the current one where almost every invocation has lines before and after setting and then unsetting the flags. It's not good to leave that kind of code laying around as it's really fragile - easy to forget to set or unset something.

Do you mean for the context_flags here? I can see that a functional state-passing-style would work nicely for these in_bladibla flags. Not sure I see why it would be better for the Symbol table though. Could you maybe point to some places in the code where you think a functional style would be advantageous?

[seantalts]

So I haven't seen it the other way and maybe it gets so ugly as to not be worth it, but I think it should just mean passing a thing around to most functions.

Here's an example snippet:

      let _ = Symbol_table.set_read_only vm uid.name in
      let _ = context_flags.in_loop <- true in
      let us = semantic_check_statement s in
      let _ = context_flags.in_loop <- false in
      let _ = Symbol_table.end_scope vm in

This requires the programmer to remember to "unset" things on the way out and has no type-system checking of these properties. Generally speaking, we want to prevent the programmer from doing stupid stuff by accident. If we pass a record containing the symbol table and flags around, we know that we won't forget to "unset" something; and permanent modification becomes much more apparent as you must now use the output of a function to assign to the state at a given scope. @bob-carpenter got anything off the top of your head to add here?

[bob-carpenter]

On Jan 21, 2019, at 5:32 PM, seantalts ***@***.***> wrote: ... @bob-carpenter got anything off the top of your head to add here?

Nope. I think that sums up the pros and cons of immutability in passing containers around to subprograms that add to them, then restore. I very much like this pattern---it's familiar from my years coding in Prolog. We did it the imperative way in Spirit Qi, of course.

[VMatthijs]

Agreed. A functional state-passing-style would be very natural for all these in_... flags for precisely the reason you mention. Generally, I guess a functional style would be a bit safer as it forces you to be more explicit about your intent. There isn't the option of "leaving the state as is" (or doing so accidentally), you always have to explicitly choose which state to pass on. It also makes the flow of information more explicit. On the other hand, it would make the code a bit harder to read, the win for the symbol table wouldn't be as clear, and it is work to refactor.

I am totally happy with one of you doing this refactor or if you think it's a high priority change and you'd like me to do it, I can do it myself. Personally, I have the sense there might be more pressing aspects of this project, however, that are essential for getting a working compiler, that my time might be better spent on at the moment. (Am I right in thinking that we'd still want to swap out the compiler ASAP subject to the constraint that the new compiler is at least as maintainable as the old one?) I am a little bit worried about getting side-tracked on trying to get every aspect of the compiler to be perfect and therefore holding up the parts of the project which are currently paused until the compiler is swapped out.

[bob-carpenter]

Yes, we want to swap out compiler ASAP, because lots of things are stacked up behind it on our virtual PERT chart. These kinds of things are all technical debt decisions---we have it one way, know a better way, and have to decide if it's worth paying down some of our technical debt proactively. We can talk about this in the meeting! - Bob

…

On Jan 22, 2019, at 8:48 AM, Matthijs Vákár ***@***.***> wrote: Agreed. A functional state-passing-style would be very natural for all these in_... flags for precisely the reason you mention. Generally, I guess a functional style would be a bit safer as it forces you to be more explicit about your intent. There isn't the option of "leaving the state as is" (or doing so accidentally), you always have to explicitly choose which state to pass on. It also makes the flow of information more explicit. On the other hand, it would make the code a bit harder to read and it is work to refactor. I am totally happy with one of you doing this refactor or if you think it's a high priority change and you'd like me to do it, I can do it myself. Personally, I have the sense there might be more pressing aspects of this project, however, that are essential for getting a working compiler, that my time might be better spent on at the moment. (Am I right in thinking that we'd still want to swap out the compiler ASAP subject to the constraint that the new compiler is at least as maintainable as the old one?) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub, or mute the thread.

[seantalts]

Agreed with your points about perfectionism and managing technical debt - we have 3 months left on the original lower bound of 6 months estimated for the project, but I want to try to move more quickly and start bringing others on board (maybe we should write up a little blog post pitching the project - why it will be great for Stan, why it's fun to work on, good places to start contributing).

I think this issue is a good learning experience for you to learn the tradeoffs and get a feel for the craftsmanship side of software engineering.

[VMatthijs]

@bob-carpenter redid the context_flags in a functional style and I think it's great. Now, there's the question of whether we'd also like to do the symbol table that way. I don't think the win would be as big there. For instance, you'd have to write your code in actual state-passing-style, making the checks return a pair of an AST-node and a symbol table. Note that threading through the state everywhere would mean converting a lot of maps over lists of statements into folds.

[palmerlao]

If people are still interested in making the symbol table manipulation pure, does this seem like a good issue for a relative newcomer to the codebase to hack on? Seems

• isolated, so not too much context transfer necessary
• in a different area than the pretty printer
• wants to be done before the initial release

[seantalts]

Yeah, still interested in trying it out at least! There's some chance this is a bad idea so once you get something that kind of illustrates the pros and cons maybe pop back up here to the issue and we can take a look at it together?