!!! The Orctimizer: An optimizer for high-level concurrent programs

Modern languages have made huge strides to alleviate the difficulties of managing concurrency.
These languages provide facilities such as cooperative concurrent programming support (often called asynchronous programming) and futures.
However, in most cases the programmer needs to choose when to apply these tools and when not to based on performance and semantics.
This forces two intermixed programming styles: concurrent (often future-based) and traditional sequential.

The Orctimizer optimizes the concurrency in the program to eliminate unnecessary futures and other concurrency constructs.
It is implemented as an optimization phase in a compiler.
This allows the programmer to use futures anywhere they may be needed, and rely on the compiler to eliminate futures that are not needed based on its analysis of the program.
The optimizations in this paper are applicable to many languages with futures, such as ~JavaScript, but are particularly applicable to language with implicit future creation and forcing.

A prototype implementation of the Orctimizer is available on [the Orctimizer branch of the Orc git repository|https://github.com/orc-lang/orc/tree/Orctimizer].
There is a discussion of Orctimizer design choices and optimizations and analyses in OrctimizerDesignDocumentation.

!! Backend

The current backend for the Orctimizer compiler stack is [Porc]. 
However, future work on the backend may avoid Porc and replace it with a direct [Truffle|https://github.com/graalvm/truffle]-based interpreter of Orctimizer code.
We could also consider writing a Truffle interpreter for Porc; however, a Truffle-based Orctimizer interpreter is likely to be able to speculatively modify itself better.

! [Truffle|https://github.com/graalvm/truffle]

Truffle has many advantages.
For instance, it automatically supports profile-based specialization and even function cloning when profiles do not match.

However, Truffle may not have fully mature thread support.
This could result in problems with multiple threads executing the same code and perhaps degrade performance when different threads result in different profiles or the like.
Truffle is at least thread-safe, so the concurrency of Orc will not be a correctness problem.

! Older notes on this subject

Adrian wrote some early notes on this subject that are saved in CompileToJvm. 
They may provide inspiration or perspective.

!! Plan

The plan for the Orctimizer and refinement paper.

* Develop Orctimizer type system

* Write motivation (MCU, ~JavaScript)
* Write prose description of Orctimizer

* Implement [Porc] C/~JavaScript backend for MCU/Web motivation

* Implement Orctimizer with as good a Porc backend as I can
* Measure secondary metrics
* Compare performance with itself
* Compare performance with Scala
* Write evaluation section

* Define exactly what I need to prove
* Write correctness section
* Write high-level manual proof sketches
* Build Coq framework for proving refinements
* Prove Orctimizer refinements

* Write paper which shows the Orctimizater as an intermediate language for translating pervasively concurrent code for mostly sequential execution.
** Introduction/Motivation. Novelty.
** Pervasively concurrent programming for modern day problems.
** Eliminating pervasive concurrency automatically.
** Correctness and refinement.
** Performance evaluation (secondary metrics and actual performance).
** Related work.
** Conclusion.

Deadline: Nov 15 (PLDI paper due)

! Schedule

|| Task [1] || Start date [2] || Finish date [2] || People
| Draft [Orctimizer] long-form paper | Tue, Jun 21 | Fri, Jul 8 | Arthur
| PLDI paper due | Tue, Nov 15 | Tue, Nov 15 |
| PLDI rebuttal period | Thu, Jan 26, 2017 | Sat, Jan 28, 2017 | Arthur
| PLDI author notification | Mon, Feb 13, 2017 | Mon, Feb 13, 2017 |
| CONCUR abstract due (approx.) | Apr 11, 2017 | Apr 11, 2017
| CONCUR paper due (approx.) | Apr 18, 2017 | Apr 18, 2017

[#1] While sorting by date works, there is no way to return to the original order other than reloading the page. 

[#2] When editing make sure that ''every'' cell in the date columns is a date (in some format, it's pretty flexible) or sorting will be lexical. The current convention is that header rows should have the earliest start date from their children and the latest end date that requires active work (other than going to the conference. The idea is that we will be able to pretty much forget about it other than the conference itself.