Optim(L): Generating Lazy APIs from DAGs of Actions

We introduce a DSL (Domain Specific Language) that can declaratively specify random access formats (i.e., formats that include offsets or require out of order parsing, e.g., zip, ICC, and PDF); our DSL can be compiled to a stateful, imperative module that provides an API (Application Programming Interface) for the on-demand or incremental parsing of the format.

Our DSL is composed by layering two distinct DSLs: the first is Optim(L), which describes DAGs (Directed Acyclic Graphs) of
computations in some computation language L.  The second---the language L---can be any language defined as a commutative monad.  When Optim(L) is instantiated to language L, the nodes represent L computations and the edges represent dependencies between them.

While there are other uses for Optim(L), we have instantiated it to a commutative parser combinator language.  This gives us a declarative way to describe random access formats, while allowing for the compilation to stateful APIs for on-demand parsing.

Dr. Mark Tullsen is a Research Engineer at Galois, Inc. where, for two decades, he has been been applying his interests in programming languages, domain specific languages, functional programming, lightweight formal methods, and software security.  He earned a Ph.D. from Yale in Computer Science and a B.S. from U.C. Berkeley in Electrical Engineering and Computer Science.