Software Languages: Syntax, Semantics, and Metaprogramming

✍ Scribed by Ralf Lämmel

• Publisher: Springer
• Year: 2018
• Tongue: English
• Leaves: 448
• Edition: 1st ed. 2018
• Category: Library

✦ Synopsis

This book identifies, defines and illustrates the fundamental concepts and engineering techniques relevant to applications of software languages in software development. It presents software languages primarily from a software engineering perspective, i.e., it addresses how to parse, analyze, transform, generate, format, and otherwise process software artifacts in different software languages, as they appear in software development. To this end, it covers a wide range of software languages – most notably programming languages, domain-specific languages, modeling languages, exchange formats, and specifically also language definition languages. Further, different languages are leveraged to illustrate software language engineering concepts and techniques. The functional programming language Haskell dominates the book, while the mainstream programming languages Python and Java are additionally used for illustration.

By doing this, the book collects and organizes scattered knowledge from software language engineering, focusing on application areas such as software analysis (software reverse engineering), software transformation (software re-engineering), software composition (modularity), and domain-specific languages. It is designed as a textbook for independent study as well as for bachelor’s (advanced level) or master’s university courses in Computer Science. An additional website provides complementary material, for example, lecture slides and videos.

This book is a valuable resource for anyone wanting to understand the fundamental concepts and important engineering principles underlying software languages, allowing them to acquire much of the operational intelligence needed for dealing with software languages in software development practice. This is an important skill set for software engineers, as languages are increasingly permeating software development.

✦ Table of Contents

Copyright and Attribution
Copyright for Code
Artwork Credits
Preface
Welcome to the Software Languages Book!
The Notion of a Software Language
Software Language Engineering (SLE)
A Particular SLE Book
Complementary Online Material
Structure of the Preface
Audience Targeted by this Book
Background Assumed by this Book
Required Knowledge
Optional Knowledge
Characteristics of this Book
Outline of this Book
Trails Offered by this Book
Trail “An Introduction to Metaprogramming”
Trail “A Primer on Programming Language Theory”
Trail “Metaprogramming in Haskell”
Trail “Software Language Engineering”
Exercises in the Book
Acknowledgments
Contents
List of Recipes
Acronyms
Fabricated languages
Other acronyms
Chapter 1: The Notion of a Software Language
1.1 Examples of Software Languages
1.1.1 Real-World Software Languages
1.1.2 Fabricated Software Languages
1.1.2.1 BNL: A Language of Binary Numbers
1.1.2.2 BTL: An Expression Language
1.1.2.3 BL: A Language for Buddy Relationships
1.1.2.4 BFPL: A Functional Programming Language
1.1.2.5 BIPL: An Imperative Programming Language
1.1.2.6 FSML: A Language for Finite State Machines
1.1.2.7 BGL: A Language for Context-Free Grammars
1.2 Classification of Software Languages
1.2.1 Classification by Paradigm
1.2.2 Classification by Type System
1.2.3 Classification by Purpose
1.2.4 Classification by Generality or Specificity
1.2.5 Classification by Representation
1.2.6 Classification by Notation
1.2.7 Classification by Degree of Declarativeness
1.3 The Lifecycle of Software Languages
1.3.1 Language Definition
1.3.2 Language Implementation
1.3.2.1 Compilation versus Interpretation
1.3.2.2 Architecture of a Compiler
1.3.2.3 Classification of Language Processors
1.3.2.4 Metaprogramming Systems
1.3.2.5 Language Workbenches
1.3.3 Language Evolution
1.4 Software Languages in Software Engineering
1.4.1 Software Re-Engineering
1.4.2 Software Reverse Engineering
1.4.3 Software Analysis
1.4.4 Technological Spaces
1.4.5 Model-Driven Engineering
Summary and outline
References
Chapter 2: A Story of a Domain-Specific Language
2.1 Language Concepts
2.2 Internal DSL
2.2.1 Baseline Object Model
2.2.2 Fluent API
2.2.3 Interpretation
2.2.4 Well-Formedness
2.3 External DSL
2.3.1 Syntax Definition
2.3.2 Syntax Checking
2.3.3 Parsing
2.4 DSL Services
2.4.1 Interchange Format
2.4.2 Code Generation
2.4.3 Visualization
Summary and outline
References
Chapter 3: Foundations of Tree- and Graph-Based Abstract Syntax
3.1 Tree-Based Abstract Syntax
3.1.1 Trees versus Terms
3.1.2 A Basic Signature Notation
3.1.3 Abstract Syntax Trees
3.1.4 An Extended Signature Notation
3.1.5 Illustrative Examples of Signatures
3.1.5.1 Syntax of Simple Expressions
3.1.5.2 Syntax of Simple Imperative Programs
3.1.5.3 Syntax of Simple Functional Programs
3.1.5.4 Syntax of Finite State Machines
3.1.6 Languages as Sets of Terms
3.1.7 Conformance to a Signature
3.2 Graph-Based Abstract Syntax
3.2.1 Trees versus Graphs
3.2.2 Languages as Sets of Graphs
3.2.3 A Metamodeling Notation
3.2.4 Conformance to a Metamodel
3.2.5 Illustrative Examples of Metamodels
3.2.5.1 Syntax of Finite State Machines
3.2.5.2 Syntax of Simple Functional Programs
3.3 Context Conditions
3.4 The Metametalevel
3.4.1 The Signature of Signatures
3.4.2 The Signature of Metamodels
3.4.3 The Metamodel of Metamodels
Summary and outline
References
Chapter 4: Representation of Object Programs in Metaprograms
4.1 Representation Options
4.1.1 Untyped Representation
4.1.2 Universal Representation
4.1.3 Typeful Representation
4.1.3.1 Algebraic Data Type-Based Representation
4.1.3.2 Object-Based Representation
4.1.3.3 Reference Relationships
4.1.3.4 Smart Constructors
4.1.4 Interchange Formats
4.1.4.1 JSON Representation
4.1.4.2 XML Representation
4.2 Conformance Checking
4.2.1 Language-Specific Conformance Checking
4.2.2 Generic Conformance Checking
4.2.3 Schema-Based Conformance Checking
4.3 Serialization
4.4 AST-to-ASG Mapping
Summary and outline
References
Chapter 5: A Suite of Metaprogramming Scenarios
5.1 Interpretation
5.1.1 Basics of Interpretation
5.1.2 Interpretation with Stores
5.1.3 Interpretation with Environments
5.1.4 Stepwise Interpretation
5.2 Compilation
5.2.1 Architecture of a Compiler
5.2.2 Translation to Assembly Code
5.2.3 Translation to Machine Code
5.3 Analysis
5.3.1 Type Checking
5.3.2 Well-Formedness Checking
5.3.3 Fact Extraction
5.4 Transformation
5.4.1 Optimization
5.4.2 Refactoring
5.5 Composition
Summary and outline
References
Chapter 6: Foundations of Textual Concrete Syntax
6.1 Textual Concrete Syntax
6.1.1 A Basic Grammar Notation
6.1.2 Derivation of Strings
6.1.3 An Extended Grammar Notation
6.1.4 Illustrative Examples of Grammars
6.1.4.1 Syntax of Simple Expressions
6.1.4.2 Syntax of Simple Imperative Programs
6.1.4.3 Syntax of Simple Functional Programs
6.1.4.4 Syntax of Finite State Machines
6.2 Concrete versus Abstract Syntax
6.3 Languages as Sets of Strings
6.3.1 Context-Free Grammars
6.3.2 The Language Generated by a Grammar
6.3.3 Well-Formed Grammars
6.3.4 The Notion of Acceptance
6.4 Languages as Sets of Trees
6.4.1 Concrete Syntax Trees
6.4.2 The Notion of Parsing
6.4.3 Ambiguous Grammars
6.5 Lexical Syntax
6.6 The Metametalevel
6.6.1 The Signature of Grammars
6.6.2 The Signature of Concrete Syntax Trees
6.6.3 The Grammar of Grammars
6.6.4 The Grammar of Signatures
6.6.5 The Grammar of Metamodels
Summary and outline
References
Chapter 7: Implementation of Textual Concrete Syntax
7.1 Representations and Mappings
7.2 Parsing
7.2.1 Basic Parsing Algorithms
7.2.1.1 Top-Down Acceptance
7.2.1.2 Bottom-Up Acceptance
7.2.1.3 Top-Down Parsing
7.2.1.4 Bottom-Up Parsing
7.2.2 Recursive Descent Parsing
7.2.3 Parser Generation
7.2.4 Parser Combinators
7.3 Abstraction
7.3.1 Recursive Descent Parsing
7.3.2 Semantic Actions
7.3.3 Parser Combinators
7.3.4 Text-to-Model
7.4 Formatting
7.4.1 Pretty Printing Combinators
7.4.2 Template Processing
7.5 Concrete Object Syntax
7.5.1 Quotation
7.5.2 Antiquotation
Summary and outline
References
Chapter 8: A Primer on Operational Semantics
8.1 Big-step Operational Semantics
8.1.1 Metavariables
8.1.2 Judgments
8.1.3 Inference Rules
8.1.4 Derivation Trees
8.1.5 Big-Step Style Interpreters
8.1.5.1 Aspects of Implementation
8.1.5.2 Explicit Model of Failure
8.1.5.3 Rule-by-Rule Mapping
8.1.6 More Examples of Big-Step Style
8.1.6.1 Semantics of Simple Imperative Programs
8.1.6.2 Semantics of Simple Functional Programs
8.2 Small-Step Operational Semantics
8.2.1 Big- versus Small-Step Judgments
8.2.2 Normal Form
8.2.3 Derivation Sequences
8.2.4 Small-Step Style Interpreters
8.2.5 More Examples of Small-Step Style
8.2.5.1 Semantics of Simple Imperative Programs
8.2.5.2 Semantics of Simple Functional Programs
8.2.5.3 Semantics of Finite State Machines
Summary and outline
References
Chapter 9: A Primer on Type Systems
9.1 Types
9.2 Typing Judgments
9.3 Typing Rules
9.4 Typing Derivations
9.5 Type Safety
9.6 Type Checking
9.7 More Examples of Type Systems
9.7.1 Well-Typedness of Simple Imperative Programs
9.7.2 Well-Typedness of Simple Functional Programs
9.7.3 Well-Formedness of Finite State Machines
Summary and outline
References
Chapter 10: An Excursion into the Lambda Calculus
10.1 The Untyped Lambda Calculus
10.1.1 Syntax
10.1.2 Semantics
10.1.3 Substitution
10.1.4 Predefined Values and Operations
10.1.5 Fixed-Point Computation
10.1.6 Interpretation
10.1.7 Turing Completeness
10.2 The Simply Typed Lambda Calculus
10.2.1 Syntax
10.2.2 Semantics
10.2.3 Type System
10.2.4 Type Checking
10.2.5 Type Erasure
10.3 System F
10.3.1 Syntax
10.3.2 Semantics
10.3.3 Type System
10.3.4 Type Erasure
10.4 Type-System Extensions
10.4.1 Records and Variants
10.4.2 Structural Type Equivalence
10.4.3 Structural Subtyping
10.4.4 Nominal Typing
Summary and outline
References
Chapter 11: An Ode to Compositionality
11.1 Compositionality
11.2 Direct Style
11.2.1 Semantic Domains
11.2.2 Semantic Functions
11.2.3 Semantic Combinators
11.2.4 Fixed-Point Semantics
11.2.5 Direct-Style Interpreters
11.3 Continuation Style
11.3.1 Continuations
11.3.2 Continuation-Style Interpreters
11.3.3 Semantics of Gotos
Summary and outline
References
Chapter 12: A Suite of Metaprogramming Techniques
12.1 Term Rewriting
12.1.1 Rewrite Rules
12.1.2 Encoding Rewrite Rules
12.1.3 Normalization
12.1.4 Strategic Programming
12.1.5 Rewriting-Related concerns
12.1.5.1 Other Traversal Idioms
12.1.5.2 Concrete Object Syntax
12.1.5.3 Graph Rewriting and Model Transformation
12.1.5.4 Origin Tracking
12.1.5.5 Layout Preservation
12.2 Attribute Grammars
12.2.1 The Basic Attribute Grammar Formalism
12.2.2 Attribute Evaluation
12.2.3 Attribute Grammars as Functional Programs
12.2.4 Attribute Grammars with Conditions
12.2.5 Semantic Actions with Attributes
12.3 Multi-Stage Programming
12.3.1 Inlining as an Optimization Scenario
12.3.2 Quasi-Quotation and Splicing
12.3.3 More Typeful Staging
12.4 Partial Evaluation
12.4.1 The Notion of a Residual Program
12.4.2 Interpretation with Inlining
12.4.3 Interpreter with Memoization
12.5 Abstract Interpretation
12.5.1 Sign Detection as an Optimization Scenario
12.5.2 Semantic Algebras
12.5.3 Concrete Domains
12.5.4 Abstract Domains
12.5.5 Examples of Abstract Interpreters
12.5.5.1 A Type-Checking Interpreter
12.5.5.2 A Sign-Detection Interpreter
Summary and outline
References
Postface
The importance of Software Language Engineering
Software Languages: Key Concepts
Omissions in This Book
Complementary Textbooks
Software Languages in Academia
Feedback Appreciated
References
Index