Porc: A backend for compiling Orc to sequential code#

Porc provides an intermediate language in which to eliminate unnecessary asynchrony in the program. It serves as part of the backend behind the Orctimizer.

Porc is designed for generating output in sequential languages like JavaScript or Java.

Porc is not novel#

The Porc backend does not have any notable novel elements. Instead it is a combination of other ideas. The research elements of Porc were the following:

  1. The Porc language.
  2. The optimization of the asynchronous Porc code.
  3. The runtime for the primitive asynchronous operations used by the generated code.
  4. The cooperative concurrent scheduler custom generated for the program to give each site a chance to run.
  5. The technique of adding yields at recursive calls to allow a chance for other code to run.
The similarities to prior work are discussed below.

1. The Porc language#

The Porc language is very similar to the F# code generated by its async support. The F# code also includes a set of context "registers" similar to P, H, C, and T in Orc. F# uses cont (successful continuation), econt (error continuation), ccont (cancellation continuation), and a cancellation token. F# does not provide halting detection or multiple results from the same call. However, it does allow parallel execution using a thread pool. In addition, adding the additional concurrent creatures would not fundamentally change the structure of the F# runtime.

Porc is specialized to Orc. So we cannot claim that Porc generalizes the previous ideas into a generally useful intermediate language.

2. The optimization of the asynchronous Porc code#

This is a simple continuation elimination process. At site calls, we simply convert them to direct calls and then inline the continuation if possible. For functions it is somewhat more complicated, but still just continuation elimination as discussed in many papers (such as, J. Hatcliff and O. Danvy, ���A generic account of continuation-passing styles,��� in POPL '94, 10.1145/174675.178053). The only other optimizations are simple inlining, eta-reduction, and similar. Overall, this is not novel.

In addition, C# and Scala async support convert an entire chain of continuations into a single state machine represented as an object. There do not appear to be able academic papers describing the state machine generation however it is described here: http://www.codeproject.com/Articles/535635/Async-Await-and-the-Generated-StateMachine and http://docs.scala-lang.org/sips/pending/async.html . The transformation has better performance in the straight line case and probably allows better optimization and code-size in all cases. Perhaps, even when there is real parallelism between different calls to the continuations.

3. The runtime for the primitive asynchronous operations used by the generated code.#

The runtime for Porc is extremely similar to the async library in F#. This includes the use of trampolining and the simplistic immediate calling of continuations. So, this is not novel.

4. The cooperative concurrent scheduler custom generated for the program to give each site a chance to run.#

Nothing similar to this appears in async work, but it is simple if you allow extra calls to site implementation even if they have no work to do. More complicated cases could be implemented using techniques from synchronous languages and circuit simulators (S. Edwards, ���Tutorial: Compiling concurrent languages for sequential processors,��� ACM Trans. Des. Autom. Electron., 10.1145/762488.762489). This is not novel.

5. The technique of adding yields at recursive calls to allow a chance for other code to run.#

This would be very similar to providing a new continuation at the end of each loop iteration (as is done for loops in C# async). We would simply trampoline through the scheduler occasionally at recursive calls or even from within site implementations. This could even work by calling the scheduler recursively (old UI programming style) if stack space is not a problem. So this is at least not interesting, and probably not novel either.

Plan#

This project is a dead end because the work does not appear to be novel. This plan is here for historical reasons.

  • ��� Check for work related to Porc (Concurrent intermediate languages)
  • ��� Develop motivation for Porc outside Orc
  • Develop examples of Orc code and its use in embedded programming
  • Compare resulting C code with hand-written.
  • Write paper which shows Porc as a technique for high-level programming on embedded systems (IoT)
    • Introduction/Motivation.
    • High-level concurrent programming in Orc.
    • Translating concurrency into asynchrony.
    • Compiling asynchronous code for embedded targets.
    • Code comparison against Lua and C.
    • Performance compared to Lua and C.
    • Related work.
    • Conclusion.

Deadlines: Sep 9 (CGO paper due), Nov 8 (CC paper due)

Add new attachment

Only authorized users are allowed to upload new attachments.
« This page (revision-5) was last changed on 28-Mar-2017 13:34 by Arthur Peters