3

I am attempting to determine the best way to handle actions that must occur in passes. Many of these actions use objects that were created in a previous pass. The solution I have come up with is to implement a computation builder.

let actions =
    passHandler {
        let myObject = pass1Action()

        do! waitForPass2

        pass2Action myObject
    }

In this code waitForPass2 would cause the continuation to be placed into a priority queue which will cause it to be executed in the second pass. However, this solution seems a bit like a hack to me. I would use a more functional approach, but the library I am using is not functional and would likely be too much effort to wrap. Is there a better solution to this?

Note: I attempted to keep the question generic, but here are some specifics in case it helps. This is for the emit phase of a compiler written using Mono.Cecil. Different phases are needed to separate the creation and usage of TypeDefinition and MethodDefinition objects.

MI3Guy
  • 250
  • 1
  • 6

1 Answers1

1

This answer is roughly in the context of your current approach rather than some alternate totally different approach.

First, your solution has some problems as it appears. Your solution would make more sense if pass 1 was concurrent with pass 2, rather than a sequential series of passes. Instead, consider what would happen if you ran actions twice sequentially, i.e. combined them sequentially in a larger computation expression: first pass1Action would execute, then it would stop waiting for pass 2. When pass 2 came, pass2Action would execute, then the second instance of pass1Action would execute, then it would stop waiting for pass 2 to come again (which presumably it never will(?)).

Essentially, the problem is you are treating pass 2 actions as being synchronously callable from pass 1 which doesn't make sense: pass 2 actions can't return values to pass 1. Calling a later pass from an earlier pass should be viewed as a non-returning asynchronous call.

You can correct this and simplify your implementation (via not needing to use continuations) by using the Writer or Output monad. Basically, you add an operation runInNextPass (or even runInPass which takes which pass to target as a parameter). Your code then looks like the following:

let actions =
    passHandler {
        let myObject = pass1Action()
        runInNextPass pass2Action
    }

runInNextPass is then just tell or a slight variant thereof from the article. Executing the computation as a whole would just be running it as normal, getting a Writer value out, then running the output value. This works well if you only want to run exactly N passes for a known (but possibly only at runtime) number of passes: just repeat the pattern of running N times. (In its N=2 form, this is a handy pattern when you want to run some code that needs an initialization phase to happen before a "real" execution phase.) However, just by changing the monoid we're using (see the article), we can get a couple different effects.

The scenario above corresponds to having the output of the Writer monad, i.e. the monoid, being either the side-effecting actions (or an IO monad) represented as functions of type () -> () or the Writer monad itself. Each layer of Writer type constructors corresponds to an extra pass. So Writer<() -> (), 'a> represents a 2-pass system, Writer<Writer<() -> (), ()>,a> represents a 3-pass system and so forth. In this case, the number of passes would be statically enforced, you couldn't use a pass 2 operation (type Writer<() -> (), ()>) in pass 3 (operations of type () -> ()). If you want a not-statically-known number of passes, then you make the recursive type type Pass<'a> = NextPass of Writer<Pass (), 'a> | FinalPass of () -> 'a. If F# supported higher-kinded polymorphism, you could write something like

type GPass<'f, 'a> = NextPass of Writer<'f<GPass<'f, 'a>>
                   | FinalPass of () -> 'a

The benefit of this is that we can change which monoid we are using. For example, when 'f is Option, then we can have a sequence of passes that run until no later passes are requested. When 'f is a variant of Map you can have passes that are labeled so your "parse" pass could directly request work to be done in the "optimization" pass without having to know how many passes are in-between. In this approach though, you may want to pass around information on which passes have already been run (possibly by adding a Reader or Environment monad aspect), because there is nothing stopping the "optimization" pass from requesting work to be done in the "parse" pass.

Derek Elkins left SE
  • 6,591
  • 2
  • 13
  • 21
  • I see what you mean about the issue. I had primarily intended to use the computation expression to avoid having to package up data to pass to the next pass, but that sounds like it will cause too may problems. I like the idea of using a writer monad. – MI3Guy Feb 10 '16 at 23:39
  • It sounded like you know of some alternate solutions. I'd be willing to consider them as well if you think it would be an improvement. – MI3Guy Feb 10 '16 at 23:40
  • The way you have it written suggests some undesirable coupling between the passes. The correctness of the overall compiler will depend on not only each pass being correct, but each pass correctly requesting work for later passes. To test the correctness of a pass, you have to not only verify the output but also what actions are requested; and the input to a pass is not only the AST but what work was requested by previous passes. – Derek Elkins left SE Feb 11 '16 at 14:30
  • An alternative approach might be something like a [nanopass](http://andykeep.com/pubs/np-preprint.pdf) approach, but the general idea is to keep any needed context explicitly represented in the intermediate languages. Conceptually, at least, you could serialize any intermediate and then in a different run load it into the compiler and continue. Of course, there is no need to actually do this or even support doing this, but it provides a stringent definition of what it means to keep all context in the ASTs of the intermediate languages. (Actually supporting it also simplifies testing.) – Derek Elkins left SE Feb 11 '16 at 14:32
  • Well, there is not a huge amount of data that has to be passed between passes. I just thought it would be more elegant to flatten it out with a computation expression. – MI3Guy Feb 12 '16 at 23:41
  • @MI3Guy The approach you've taken certainly isn't unreasonable. I just wanted to illustrate another point in the design space, and some of the forces that lead to it. – Derek Elkins left SE Feb 13 '16 at 00:37