Partial evaluation of event structures, occurrence nets, and event expressions
John D. McGregor, Jeffrey Blanchard Green · 1999
Partial evaluation is a technique for optimizing a program within the context of specific input to the program. It contrasts with traditional optimizing techniques in that it is not part of the compilation process, or more specifically part of the compiler. Consequently it is not associated with a specific target language of a compiler and is more general than compilation. The general goal of partial evaluation research is to produce a partial evaluator, or specializer, which accomplishes the task of specializing the program in the context of particular input. Past research has focussed on the partial evaluation of sequential computation and has produced specializers for functional languages, logic languages, and imperative languages. However little has been done with regards to concurrent computation. We focus here on exploring and producing partial evaluation techniques as applied to concurrent computation, specifically event structures. We build a mathematical foundation for establishing a correct partial evaluation of event structures. The mathematical machinery is also extended to a form of Petri nets equivalent to event structures, occurrence nets, and to a form of concurrent regular expressions called event expressions. We provide a definition for correctness of a specialization and an algorithm for the specialization of event structures. With that foundation, we prove the correctness of the specialization algorithm for event structures. We extend the algorithm to apply to occurrence nets and event expressions by composing it with invertible mappings from event structures to occurrence nets and event expressions. That composition provides a means to partially evaluate occurrence nets and event expressions. We prove the correctness of that composition. The work discussed in the previous paragraph is the core of the total work presented here. Additional work beyond that core is given. That work consists of extending the core to a more detailed model of events, to a more powerful mode of events, flow event structures, and to an implementation of the core providing an automated graphical means of exploring partial evaluation of event structures.