The next 700 data description languages

ABSTRACT

In the spirit of Landin, we present a calculus of dependent types to serve as the semantic foundation for a family of languages called data description languages. Such languages, which include pads, datascript, and packettypes, are designed to facilitate programming with ad hoc data, ie, data not in well-behaved relational or xml formats. In the calculus, each type describes the physical layout and semantic properties of a data source. In the semantics, we interpret types simultaneously as the in-memory representation of the data described and as parsers for the data source. The parsing functions are robust, automatically detecting and recording errors in the data stream without halting parsing. We show the parsers are type-correct, returning data whose type matches the simple-type interpretation of the specification. We also prove the parsers are "error-correct," accurately reporting the number of physical and semantic errors that occur in the returned data. We use the calculus to describe the features of various data description languages, and we discuss how we have used the calculus to improve PADS.

REFERENCES

• 1: Godmar Back, DataScript - A Specification and Scripting Language for Binary Data, The ACM SIGPLAN/SIGSOFT Conference on Generative Programming and Component Engineering, p.66-77, October 06-08, 2002
• 2: A. Birman and J. D. Ullman. Parsing algorithms with backtrack. Information and Control, 23(1), Aug. 1973.
• 3: W. Burge. Recursive Programming Techniques. Addison Wesley, 1975.
• 4: D. Eger. Bit level types. www-2.cs.cmu.edu/~eger/.
• 5: M. F. Fernández, J. Siméon, B. Choi, A. Marian, and G. Sur. Implementing XQuery 1.0: The Galax experience. In VLDB, pages 1077--1080. ACM Press, 2003.
• 6: Kathleen Fisher , Robert Gruber, PADS: a domain-specific language for processing ad hoc data, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 7: Bryan Ford, Packrat parsing:: simple, powerful, lazy, linear time, functional pearl, Proceedings of the seventh ACM SIGPLAN international conference on Functional programming, p.36-47, October 04-06, 2002, Pittsburgh, PA, USA
• 8: Bryan Ford, Parsing expression grammars: a recognition-based syntactic foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.111-122, January 14-16, 2004, Venice, Italy
• 9: Gene Ontology Project. www.geneontology.org.
• 10: R. Grimm. Practical packrat parsing. Technical Report TR2004-854, New York University, Mar. 2004.
• 11: P. Gustafsson and K. Sagonas. Adaptive pattern matching on binary data. In ESOP, pages 124--139. Springer, Mar. 2004.
• 12: R. Harper. Programming Languages: Theory and Practice. Unpublished, 2005. www-2.cs.cmu.edu/~rwh/.
• 13: Graham Hutton , Erik Meijer, Monadic parsing in Haskell, Journal of Functional Programming, v.8 n.4, p.437-444, July 1998 [doi>10.1017/S0956796898003050]
• 14: Atshushi Igarashi , Benjamin Pierce , Philip Wadler, Featherwieght Java: a minimal core calculus for Java and GJ, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.132-146, November 01-05, 1999, Denver, Colorado, United States
• 15: B. Krishnamurthy and J. Rexford. Web Protocols and Practice. Addison Wesley, 2001.
• 16: P. J. Landin, The next 700 programming languages, Communications of the ACM, v.9 n.3, p.157-166, March 1966 [doi>10.1145/365230.365257]
• 17: Peter J. McCann , Satish Chandra, Packet types: abstract specification of network protocol messages, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.321-333, August 28-September 01, 2000, Stockholm, Sweden
• 18: Tree formats. Workshop on molecular evolution. workshop.molecularevolution.org/resources/fileformats/tree_formats.php.
• 19: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 20: C. Wikström and T. Rogvall. Protocol programming in Erlang using binaries. In Erlang/OTP User Conference, Oct. 1999.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Languages, Theory

Keywords:
data description language, dependent types, domain-specific languages