Concepts of Programming Languages:
                        AUnified Approach
                           Karl Abrahamson
                             August 2016
           2
                       Copyright (c) 2016 Karl Abrahamson.
                            Contents
                            1 Introduction to Programming Languages                                                            11
                                1.1     Programming languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        11
                                1.2     Languages, libraries and implementations . . . . . . . . . . . . . . . . . . .         12
                                1.3     General families of languages . . . . . . . . . . . . . . . . . . . . . . . . . .      12
                                1.4     Encapsulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     13
                                        1.4.1    Modules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     14
                                        1.4.2    Namespaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      15
                                        1.4.3    Intension and extension . . . . . . . . . . . . . . . . . . . . . . . . .     15
                                        1.4.4    Language support . . . . . . . . . . . . . . . . . . . . . . . . . . . .      16
                                1.5     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  17
                                1.6     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    17
                            2 Some Programming Languages                                                                       19
                                2.1     Fortran    . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
                                2.2     Algol 60 and its descendants . . . . . . . . . . . . . . . . . . . . . . . . . . .     20
                                2.3     C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  20
                                2.4     Object-oriented languages . . . . . . . . . . . . . . . . . . . . . . . . . . . .      21
                                2.5     Functional languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     21
                                2.6     Prolog and its descendants . . . . . . . . . . . . . . . . . . . . . . . . . . . .     22
                                2.7     Cinnameg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     22
                                2.8     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    23
                            3 Syntax                                                                                           25
                                3.1     Form and function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      25
                                3.2     Describing syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    27
                                        3.2.1    Lexical rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   27
                                        3.2.2    Program structure and parse trees . . . . . . . . . . . . . . . . . . .       29
                                        3.2.3    Using grammars to indicate allowed trees . . . . . . . . . . . . . . .        29
                                        3.2.4    Commongrammatical forms . . . . . . . . . . . . . . . . . . . . . .           32
                                        3.2.5    Ambiguity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     33
                                        3.2.6    Syntax is not meaning . . . . . . . . . . . . . . . . . . . . . . . . . .     36
                                        3.2.7    Extended BNF notation . . . . . . . . . . . . . . . . . . . . . . . . .       36
                                        3.2.8    Syntax diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     37
                                3.3     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  39
                                3.4     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    41
                                                                              3
                             4                                                                                       CONTENTS
                             4 Data and Data Representation                                                                     43
                                4.1     Programs and data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .        43
                                4.2     Simple values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      43
                                4.3     Tuples and records . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       44
                                4.4     Lists and arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     45
                                4.5     Sets   . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   48
                                4.6     Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    48
                                4.7     Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     50
                                4.8     First class data items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     51
                                4.9     Persistent and ephemeral data . . . . . . . . . . . . . . . . . . . . . . . . . .        51
                                4.10    Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    52
                                4.11    Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      56
                             5 Imperative Programming                                                                           57
                                5.1     Statements, variables and assignment . . . . . . . . . . . . . . . . . . . . . .         57
                                5.2     Control: early approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . .        57
                                5.3     Structured programming constructs . . . . . . . . . . . . . . . . . . . . . . .          60
                                5.4     Variations on choice     . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   62
                                5.5     Variations on loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      63
                                5.6     Procedural programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         65
                                        5.6.1    Information flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . .       66
                                        5.6.2    Syntactic approaches to parameter passing . . . . . . . . . . . . . .           68
                                        5.6.3    Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     69
                                5.7     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    69
                                5.8     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      71
                             6 Variables and Scope                                                                              73
                                6.1     Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      73
                                6.2     Variables as data items . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      76
                                6.3     Expression context: lvalue and rvalue . . . . . . . . . . . . . . . . . . . . . .        77
                                        6.3.1    Extending context to collections . . . . . . . . . . . . . . . . . . . .        78
                                6.4     Parameter passing modes . . . . . . . . . . . . . . . . . . . . . . . . . . . .          79
                                        6.4.1    Call-by-value . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     79
                                        6.4.2    Call-by-reference . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     80
                                        6.4.3    Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    81
                                        6.4.4    Copying in and out . . . . . . . . . . . . . . . . . . . . . . . . . . .        81
                                        6.4.5    Mechanism and intent . . . . . . . . . . . . . . . . . . . . . . . . . .        82
                                6.5     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    82
                             7 Implementation of Programming Languages                                                          85
                                7.1     Compilers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      85
                                7.2     Linkers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    85
                                7.3     Interpreters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .     86
                                7.4     Comparison of compilers and interpreters          . . . . . . . . . . . . . . . . . . .  87
                                7.5     Hybrid implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . .         88
                                7.6     Languages are not their implementations . . . . . . . . . . . . . . . . . . . .          88
                                7.7     Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .    89
                                7.8     Bibliographic notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .      90