Pattern-Level Programming with Asteroid

ABSTRACT John Backus identified value-level (object-level) programming languages as programming languages that combine various values to form other values until the final result values are obtained. Virtually all our classic programming languages today including C, C++, and Java belong into this category. Here we identify pattern-level (term-level) programming languages that combine various patterns to form other patterns until the final result patterns are obtained. New patterns are constructed from existing ones by the application of pattern-to-pattern functions exploiting pattern matching and constructors. First-order logic programming languages such as Prolog, OBJ, and Maude belong into this category. Our insight that pattern-level and value-level programming gives rise to a patternvalue duality is used as the foundation of the design of a new programming language called Asteroid. Hallmarks of this new programming language design are the developer’s ability to explicitly control the interpretation or model of expression terms and the notion of ‘patterns as first class citizens’. In addition to a complete implementation of pattern-level programming Asteroid also supports an object-oriented style of programming based on prototypes and also subject to pattern matching. KEYWORDS Pattern matching, semantics, programming language desig