Concepts of Programming Languages:
                        AUnified Approach
                           Karl Abrahamson
                             August 2011
           2
                       Copyright (c) 2011 Karl Abrahamson.
                            Contents
                            I    Fundamental Concepts                                                                         17
                            1 Introduction to Programming Languages                                                            19
                            2 Language Classification                                                                           21
                                2.1     Imperative programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       21
                                2.2     Declarative programming . . . . . . . . . . . . . . . . . . . . . . . . . . . .        22
                                2.3     Language classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     23
                                2.4     Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          24
                                2.5     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  25
                                2.6     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    25
                            3 Encapsulation and Information Hiding                                                             27
                                3.1     Encapsulation and modification . . . . . . . . . . . . . . . . . . . . . . . . .        27
                                3.2     Some kinds of encapsulations . . . . . . . . . . . . . . . . . . . . . . . . . .       27
                                3.3     Intension and extension      . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
                                3.4     Language support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     28
                                3.5     Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          29
                                3.6     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  30
                            4 Implementation of Programming Languages                                                          31
                                4.1     Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    31
                                4.2     Linkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  31
                                4.3     Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   32
                                4.4     Comparison of compilers and interpreters        . . . . . . . . . . . . . . . . . . .  33
                                4.5     Hybrid implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       34
                                4.6     Libraries and run-time support . . . . . . . . . . . . . . . . . . . . . . . . .       35
                                4.7     Languages are not their implementations . . . . . . . . . . . . . . . . . . . .        35
                                4.8     Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          37
                                4.9     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  38
                                4.10    Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    39
                            II    Syntax and Semantics                                                                        41
                            5 Form and Function                                                                                43
                                5.1     The syntax of a language       . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
                                5.2     Form suggests function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     43
                                                                              3
                            4                                                                                      CONTENTS
                                5.3     Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          45
                                5.4     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  45
                                5.5     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    46
                            6 Describing Syntax and Structure                                                                  47
                                6.1     Describing the syntax of a language . . . . . . . . . . . . . . . . . . . . . . .      47
                                6.2     Lexical rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  47
                                6.3     Program structure and parse trees        . . . . . . . . . . . . . . . . . . . . . . . 49
                                6.4     Using grammars to indicate allowed trees        . . . . . . . . . . . . . . . . . . .  51
                                6.5     Commongrammatical forms . . . . . . . . . . . . . . . . . . . . . . . . . . .          52
                                6.6     Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    53
                                6.7     Syntax is not meaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      56
                                6.8     Extended BNF notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        56
                                6.9     Syntax diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      57
                                6.10    Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          59
                                6.11    Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  60
                                6.12    Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    62
                            7 Semantics                                                                                        63
                                7.1     Introduction to semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . .      63
                                7.2     Operational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      63
                                7.3     Denotational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     63
                                7.4     Axiomatic semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      64
                                7.5     Partial semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    64
                                7.6     Relational semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     65
                                7.7     Semantic black holes and infinite loops . . . . . . . . . . . . . . . . . . . . .       65
                                7.8     Resource limitations and semantics . . . . . . . . . . . . . . . . . . . . . . .       66
                                7.9     Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          66
                                7.10    Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  67
                                7.11    Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    68
                            III     Managing Information                                                                      69
                            8 Data and Data Representation                                                                     71
                                8.1     Programs and data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      71
                                8.2     Simple values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    71
                                8.3     Tuples and records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     72
                                8.4     Lists and arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   73
                                8.5     Sets   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
                                8.6     Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  77
                                8.7     Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   79
                                8.8     Tags and tagged values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     79
                                8.9     First class data items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   80
                                8.10    Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    81
                                8.11    Persistent and ephemeral data . . . . . . . . . . . . . . . . . . . . . . . . . .      81
                                8.12    Summary of terminology and concepts . . . . . . . . . . . . . . . . . . . . .          82
                                8.13    Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  83