Imagine learning the data schema formats of an application just by analyzing JavaScript Object Notation (JSON), Extensible Markup Language (XML), or comma-separated values (CSV) examples. By using shape inference algorithms, the “shape” of these examples can be inferred, and then described with the F# data and type system. The authors introduce the F# data language and their approach to analyze sample documents and create first-class structured data objects, “citizens,” in F#. Using F# data type providers, processing sample data, and inferring common preferred shapes, F# types can be generated and used by programmers. The papers shows typical real-world JSON services exhibiting some of the more complicated shapes, such as numerical versus string literals, nested collections, and even optional fields.

Their approach flips the typical known type processing into a new “types from data” approach. By exploring structured data, such as JSON nodes, the authors’ shape inference algorithm can recursively find common shapes of all the child nodes of the sample document. These are then defined in the F# language while being related to known preferred shape relations of JSON, XML, or CVS languages. The paper describes their common preferred shape function rules and maps them into an advanced type system. Numerous worked examples are shown that map back to their common shapes.

A formal type model based on the flyweight object-oriented (FOO) calculus forms the basis for their F# data integration approach. With great detail, the paper shows various challenges with example data. With this approach, the type providers create a strong typing model helping a program work with unknown real-world data. Without strong typing, or known schemas, applications usually substitute with lots of dynamic typing and exception handling. Also as schemas or examples change, the inference engine can be rerun to incorporate new knowledge.

The authors have connected two lines of research: (1) extending programming language type systems to accommodate external data services, and (2) inferring types for these same real-world data sources. This paper is also unique in that it describes the programming language theory behind concrete type providers. The paper also provides examples showing how their approach works, and correctness proofs that match their definition of what they can process with desired results. A formal model helps prove relative type safety.

With a rich F# user community, many examples have been processed, which increases information on the shape inference approaches. Information on F# is available online, and libraries to incorporate this process into popular languages are available.