Computational Artifacts (eBook)

Raymond Turner is an emeritus professor of the School of Computer Science and Electronic Engineering of the University of Essex. His research interests include theoretical computer science, mathematical logic, philosophical logic, philosophy of mathematics, and the philosophy of computer science.

Preface 5
Contents 8
Part I INTRODUCTION 15
Chapter 1: COMPUTER SCIENCE 18
1.1 Machines 18
1.2 Theoretical Computer Science 20
1.3 Programs and Programming 21
1.4 Computational Thinking 23
1.5 The Discipline 24
Chapter 2: TOWARDS A PHILOSOPHY OF COMPUTER SCIENCE 25
2.1 Semantics 25
2.2 Ontology 27
2.3 Methodology 28
2.4 Epistemology 29
2.5 Conclusion 30
Part II ONTOLOGY 32
Chapter 3: COMPUTATIONAL ARTIFACTS 35
3.1 Function and Structure 35
3.2 Design and Manufacture 36
3.3 Theories of Function 37
3.4 Computational Artifacts 38
Chapter 4: LOGIC MACHINES AS TECHNICAL ARTIFACTS 40
4.1 Function 40
4.2 Structure 42
4.3 Design 45
4.4 Correctness 46
4.5 Implementation 46
4.6 Logic Machines as Technical Artifacts 47
4.7 The Abstract-Concrete Interface 48
4.8 The von Neumann Computer as Artifact 48
4.9 High-Level Functional Notation 49
4.10 Conclusion 50
Chapter 5: THE ONTOLOGY OF PROGRAMS 51
5.1 The Functional Specification of Programs 52
5.2 Structure 56
5.3 Implementation 57
5.4 The Symbolic and the Physical 58
5.6 Programs as Technical Artifacts 60
Chapter 6: SOFTWARE SYSTEMS AS TECHNICAL ARTIFACTS 61
6.1 Requirements 61
6.2 Structure and Design 62
6.3 Implementation 63
6.4 Software Systems as Artifacts 64
6.5 Verification, Validation, and Malfunction 65
6.6 Conclusion 65
Part III SEMANTICS 66
Chapter 7: THE LANGUAGES OF COMPUTER SCIENCE 69
7.1 Varieties of Languages 69
7.2 Formal Languages 71
Chapter 8: PROGRAMMING LANGUAGES 73
8.1 Imperative Languages 74
8.2 Functional Languages 77
8.3 Logical Languages 79
8.4 Object Orientation 80
8.5 Concurrency and Nondeterminism 81
8.6 Theories of Representation and Computation 82
Chapter 9: SEMANTIC THEORIES 83
9.1 The Roles of Semantics 83
9.2 Normativity 85
9.3 Compositionality 86
9.4 Rigor 88
9.5 Conclusion 89
Chapter 10: FORMAL SEMANTICS 90
10.1 Vernacular Semantics 90
10.2 Operational Semantics 91
10.3 Denotational Semantics 95
10.4 Definitional Priority 96
10.5 Game-Theoretic Semantics 98
10.6 Programming Languages as Mathematical Theories 98
Chapter 11: SEMANTICS AND IMPLEMENTATION 100
11.1 Compilers, Interpreters, and Virtual Machines 100
11.2 Compilation and Semantic Interpretation 103
11.3 Semantics and Interpretation 104
11.4 Programming Languages as Technical Artifacts 108
Chapter 12: SPECIFICATION LANGUAGES 109
12.1 Typed Predicate Logic 109
12.2 The Logic of TPL 111
12.3 Definitions 112
12.4 Z and Set Theory 113
12.5 VDM and Three-Valued Logic 114
12.6 Types, Not Sets 115
12.7 Expressive Power 116
Part IV METHODOLOGY 117
Chapter 13: SOFTWARE SYSTEM METHODOLOGY 120
13.1 The Waterfall Method 121
13.2 The Spiral Method 121
13.3 The Agile Method 121
13.4 Methodology 122
Chapter 14: SPECIFICATION 124
14.1 Requirements Analysis as Modeling 124
14.2 Definition 125
14.3 Intention 126
14.4 Intentional Stance 127
14.5 Precision and Information 129
Chapter 15: THE PHILOSOPHY OF DESIGN 131
15.1 Correctness 132
15.2 Simplicity 132
15.3 Modularity 133
15.4 Formal Methods 133
Chapter 16: SIMPLICITY 135
16.1 Elegance 136
16.2 Parsimony 139
16.3 Justification 140
Chapter 17: MODULARITY 142
17.1 Encapsulation 143
17.2 Bundling 144
17.3 Information Hiding 145
17.4 Independence 146
17.5 Single Function 147
17.6 Cohesion and Coupling 148
17.7 Modularization 149
Chapter 18: FORMAL METHODS 151
18.1 Formal Specification 152
18.2 System Properties 153
18.3 Programming 153
18.4 Module Correctness 154
18.5 Transformational Programming 157
18.6 Constructive Programming 157
18.7 Limitations of Formal Methods 158
18.8 Programming as a Mathematical Activity 159
Chapter 19: THE DESIGN OF PROGRAMMING LANGUAGES 161
19.1 Simplicity 161
19.2 Elegance via Uniformity 162
19.3 Parsimony 164
19.4 The Defense of Simplicity 165
19.5 Expressive Power 165
Chapter 20: SEMANTICS AND DESIGN 168
20.1 The Principle of Correspondence 169
20.2 Type Completeness 171
20.3 The Principle of Abstraction 172
20.4 Programming Languages as Mathematical Theories 173
Chapter 21: DATA ABSTRACTION 174
21.1 The Traditional Account of Abstraction 175
21.2 The Way of Abstraction 176
21.3 Russell's Paradox 178
21.4 Data Abstraction 178
21.5 Principles of Abstraction 180
21.6 Implementation as a Basis for Abstraction 181
21.7 A Theory of Computational Abstraction 182
Part V EPISTEMOLOGY 183
Chapter 22: COMPUTABILITY 186
22.1 Mathematical Modeling 186
22.2 The Programming Language Approach 187
22.3 Invariance 188
22.4 The Machine Approach 189
22.5 Semantics and Turing Machines 189
22.6 Turing Machines as Technical Artifacts 191
22.7 Machines and Rules 191
Chapter 23: FEASIBLE COMPUTATIONS 193
23.1 Computational Complexity Theory 193
23.2 The Cobham-Edmonds Thesis 194
23.3 Quantum Computing and Feasibility 195
Chapter 24: VARIETIES OF CORRECTNESS 196
24.1 Digital Circuits 197
24.2 Programs 198
24.3 Software Systems 199
Chapter 25: PROGRAM CORRECTNESS 200
25.1 The Mathematical Challenge 200
25.2 The Mechanical Challenge 202
25.3 The Pragmatic Challenge 204
25.4 The Scientific Challenge 205
25.5 Proof and Principles of Program Design 206
Chapter 26: TYPES AND CORRECTNESS 208
26.1 Type Inference 209
26.2 Semantics 210
26.3 Implementation 211
26.4 Correctness 212
Chapter 27: THE SIMPLE MAPPING ACCOUNT 214
27.1 The Correctness of Electronic Devices 214
27.2 Simple Mapping Account 215
27.3 The Mathematical Case 217
27.4 Good and Bad Programs 218
Chapter 28: COMPUTATIONAL EXPLANATION 220
28.1 Technological Explanation 220
28.2 Mathematical Explanation 222
28.3 Structural Explanation 224
28.4 Conclusion 225
Chapter 29: INTENTION AND CORRECTNESS 226
29.1 The Standard Account 227
29.2 Definition and Intention 227
Chapter 30: RULE FOLLOWING AND CORRECTNESS 229
30.1 Computing and Programming 229
30.2 Rule Following 230
30.3 The Skeptical Paradox 231
30.4 The Skeptical Solution 232
30.5 Rules and Customs 232
30.6 Rule Following and Computer Science 233
Nomenclature 234
References 236
Index 246