Introduction to Programming Languages

Anthony A. Aaby

HTML Style Guide | To Do | Miscellenous (possible content) | Figures | Definitions

Short Table of Contents

Preface
  1. Introduction
  2. Syntax
  3. Semantics
  4. Translation
  5. Pragmatics
  6. Abstraction and Generalization
  7. Data and Data Structuring
  8. Logic Programming
  9. Functional Programming
  10. Imperative Programming
  11. Concurrent Programming
  12. Object-Oriented Programming
  13. Evaluation
Appendix
Stack machine
Unified Grammar
Logic
Bibliography
Definitions
Index

Supplementary Material

Code

Long Table of Contents

HTML Style Guide | To Do

Preface

Syntax, translation, semantics and pragmatics

1 Introduction
1.1 Data
1.2 Models of Computation
1.3 Syntax and Semantics
1.4 Pragmatics
1.5 Language Design Principles
1.6 Historical Perspectives and Further Reading
1.7 Exercises
2 Syntax
2.1 Context-free Grammars
2.1.1 Alphabets and Languages
2.1.2 Grammars and Languages
2.1.3 Abstract Syntax
2.1.4 Parsing
2.1.5 Table-driven and recursive descent parsing
2.2 Nondeterministic Pushdown Automata
2.2.1 Equivalence of pda and cfgs
2.3 Regular Expressions
2.4 Deterministic and Non-deterministic Finite State Machines
2.4.1 Equivalence of deterministic and non-deterministic fsa
2.4.2 Equivalence of fsa and regular expressions
2.4.3 Graphical Representation
2.4.4 Tabular Representation
2.4.5 Implementation of FSAs
2.5 Historical Perspectives and Further Reading
2.5.1 Backus-Naur Form
2.5.2 EBNF (extended BNF)
2.5.3 Language Descriptions
2.5.4 Parser (Compiler) Construction Tools
2.5.5 Formal Languages and Automata
2.6 Exercises
3 Semantics
3.1 Algebraic
3.2 Axiomatic
3.3 Denotational
3.4 Operational
3.5 Translation
3.6 Historical Perspectives and Further Reading
3.7 Exercises
4 Pragmatics
4.1 Syntax
4.2 Semantics
4.3 Bindings and Binding Times
4.4 Procedures and Functions
4.4.1 Parameters and Arguments
4.4.1.1 Eager vs Lazy Evaluation
4.4.1.2 Parameter Passing Mechanisms
4.5 Scope and Blocks
4.5.-- more to come
4.6 Safety
4.7 Historical Perspectives and Further Reading
4.8 Exercises

Models of Computation

5 Abstraction and Generalization
5.1 Abstraction
5.1.1 Binding
5.1.2 Encapsulation
5.2 Generalization
5.2.1 Substitution
5.3 Block Structure
5.3.1 Activation Records
5.4 Scope Rules
5.4.1 Dynamic Scope Rules
5.4.2 Static Scope Rules
5.5 Partitions
5.6 Environment
5.7 Modules
5.8 ADTs
5.9 Historical Perspectives and Further Reading
5.10 Exercises
6 Domains and Types
6.1 Elements of Domain Theory
6.1.1 Product Domain
6.1.2 Sum Domain
6.1.3 Function Domain
6.1.4 Power Domain
6.1.5 Recursively Defined Domain
6.2 Type Systems
6.2.1 Type Checking
6.2.2 Type Equivalence
6.2.2.1 Name Equivalence
6.2.2.2 Structural Equivalence
6.2.2 Type Inference
6.2.3 Type Declarations
6.2.4 Polymorphism
6.3 Type Completeness
6.4 Historical Perspectives and Further Reading
6.5 Exercises
7 Logic Programming
    Database query languages
      Relations and the Relational Algebra
      Datalog
    Quantifiers
    Appliation Areas
    Inference and Unification
    Syntax
      Facts, Predicates and Atoms
      Queries
    Semantics
      Operational Semantics
      A Simple Interpreter for Pure Prolog
      Declarative Semantics
      Denotational Semantics
    Pragmatics
      Logic Programming and Software Engineering
      The Logical Variable
      Incomplete Data Structures
      Arithmetic
    Iteration vs Recursion
    Backtracking
    Exceptions
    Logic Programming vs Functional Programming
    Prolog and Logic
      The Logic of Prolog
      The Illogic of Prolog
        Incompleteness
        Unfairness
        Unsoundness
        Negation
        Control Information
        Extralogical Features
        Multidirectionality
        Rule Order
    Historical Perspectives and Further Reading
    Exercises
8 Functional Programming
8.1 The Lambda Calculus
8.1.1 Operational Semantics
8.1.2 Denotational Semantics
8.1.3 Translation Semantics and Combinators
8.2 Scheme
8.3 ML
8.4 Haskell
8.5 Historical Perspectives and Further Reading
8.6 Exercises
9 Imperative Programming
9. Historal Perspectives and Further Reading
9. Exercises

Pragmatics

10 Concurrent Programming
10.1 The Concurrent Nature of Systems
10.2 The Nature of Concurrent Systems
10.3 Concurrency in Programming Languages
10.4 The Engineering of Concurrent Programs
10.5 Historical Perspectives and Further Reading
10.6 Exercises
11 Object-Oriented Programming
11.1 Subtypes (subranges)
11.2 Objects
11.3 Classes
11.4 Inheritance
11.5 Types and Classes
11.6 Examples
11.7 Historical Perspectives and Further Reading
11.8 Exercises
12 Translation
12.1 Attribute Grammars and Static Semantics
12.2 Parsing
12.3 Scanning
12.4 Symbol Table
12.5 Virtual Computers
12.6 Optimization
12.7 Code Generation
12.8 Peephole Optimization
12.9 Historical Perspectives and Further Reading
12.10 Exercises
13 Evaluation
13. Historical Perspectives and Further Reading
13. Exercises Appendix

Logic
Bibliography
Definitions
Index

Supplementary Material

Code
by Anthony A. Aaby Send comments to aabyan@wwc.edu