Functional programming : practice and theory / Bruce J. MacLennan.

CONTENIDO
Part 1 Practice 1
Chapter 1. Functions 3
1.1 Introduction 3
1.2 The World of Expressions and the World of Statements 5
1.3 Evaluation-Order Independence 7
1.4 Referential Transparency 11
1.5 Manifest Interfaces 13
1.6 Hoare's Principles of Structuring 14
1.7 Functions and Applicative Expressions 15
1.8 Function Definition 17
1.9 History of Functional Programming 23
1.10 Functional Programming Languages 26
1.11 The Structure of Functional Programs 32
Chapter 2. Applicative Languages 36
2.1 Language Frameworks 36
2.2 Atomic Data Types 38
2.3 Sequences 41
2.4 Exploration of Sequence Primitives 44
2.5 Engineering Specifications 49
2.6 Archtypes for Abstract Data Types 50
2.7 Syntax 52
2.8 Semantics 55
2.9 Pragmatics 61
2.10 The Problem of Infinite Sequences 62
Chapter 3. Applicative Sequence Processing 67
3.1 Goals 67
3.2 Element Selection 68
3.3 Catenation 73
3.4 Reductions 80
3.5 Mappings 84
3.6 Sequence Generation 87
3.7 Sequence Equality 91
3.8 Performance Analysis and Optimization 94
3.9 Tail Recursion and Iteration 101
3.10 Copying in Applicative Languages 112
Chapter 4. Applicative Set Processing 114
4.1 Archetypes and Prototypes 114
4.2 Archetype for Finite Sets 115
4.3 Applications of Finite Sets 127
4.4 Development of a Prototype for Finite Sets 129
4.5 Typing in Applicative Languages 133
4.6 Proof of Finite Set Prototype 138
4.7 Performance Analysis of Finite Set Prototype 143
4.8 Choice Functions and Multiple Representations 145
4.9 Archetype for Finite Functions 151
4.10 Applications of Finite Functions 157
4.11 Prototype for Finite Functions 159
Chapter 5. Applicative Tree Processing 162
5.1 Direct Products of Types 162
5.2 Direct Sums of Types 171
5.3 Recursively Defined Types 180
5.4 Formal Patterns and Equational Definitions 188
5.5 Arithmetic Expression Notations 194
5.6 Representing Arithmetic Expressions 196
5.7 Descriptions of Expression Representations 198
5.8 Tree-to-Postfix Conversion 200
5.9 Tree Evaluation 203
5.10 Unification 209
Chapter 6. Higher-Order Functions 221
6.1 Functional Mapping 221
6.2 Definition of Functional Programming 227
6.3 Functional Abstraction 228
6.4 Functional Abstraction and Mapping 236
6.5 Sections of Binary Operators 240
6.6 Currying 243
6.7 Filtering 246
6.8 Composition 250
6.9 Construction 254
6.10 Function-Level Definitions and Multilevel Functions 262
6.11 The Reduction Functionals 265
6.12 The Accumulation Functionals 272
6.13 Constant Functions 276
6.14 Conditional Construction 278
6.15 Functional Summation 282
6.16 Recursively Defined Functionals 288
Chapter 7. Infinite Data Structures 294
7.1 Introduction 294
7.2 Recursive Sets 294
7.3 Extension and Intension 298
7.4 An Application: Recognitive Grammars 302
7.5 Recursively Enumerable Sequences 310
7.6 Evaluation Order and the Recursive Definition of Data Structures 316
7.7 Delayed Evaluation and Streams 323
7.8 Interactive and Real-time Applications 334
Part 2 Theory 349
Chapter 8. Completeness of the Lambda Calculus 350
8.1 Introduction 350
8.2 Bound Identifiers 351
8.3 Syntax of the Lambda Calculus 357
8.4 Semantics of the Lambda Calculus 359
8.5 Normal Form 364
8.6 Multiple Parameters and Abbreviations 367
8.7 Typing in the Lambda Calculus 370
8.8 Booleans and Conditionals 371
8.9 Direct Product Types 374
8.10 Direct Sum Types and Sequences 377
8.11 Auxiliary Declarations 379
8.12 Recursive Declarations 383
8.13 Integers 391
Chapter 9. Consistency of the Lambda Calculus 398
9.1 History 398
9.2 Notation and Terminology 399
9.3 Reachability and Uniqueness of Normal Form 402
9.4 Walks 404
9.5 Walks Are Substitutive 405
9.6 Walks Have the Diamond Property 408
9.7 Reduction Has the Diamond Property 412
9.8 Introduction to the Halting Problem 414
9.9 Undecidability of the Halting Problem 417
Chapter 10. Abstract Calculi 421
10.1 Advantages and Disadvantages of Calculi 421
10.2 Definition of Calculi 423
10.3 Transformation Rules 424
10.4 Disadvantages of Concrete Calculi 425
10.5 Expression Trees 431
10.6 Abstract Syntax 433
10.7 Equations and Transformation Rules 435
10.8 The Abstract Lambda Calculus 438
10.9 The SKI Calculus 442
10.10 The Wang Algorithm for the Propositional Calculus 441
10.11 Computational Consistency 455
10.12 Implementation 463
Chapter 11. Universal Functions 471
11.1 The Utility of Universal Functions 471
11.2 Mechanical Reduction 473
11.3 Context 474
11.4 Free Identifiers 479
11.5 Automating Reduction 481
11.6 A Functional Program for Lambda Calculus Reduction 483
11.7 An Imperative Program for Lambda Calculus Reduction 488
11.8 Functional Language Interpreters 490
11.9 Representation of Contexts 490
11.10 Multiple-Argument Functions 492
11.11 Constants 495
11.12 Intrinsic Identifiers 499
11.13 Auxiliary Declarations 506
Chapter 12. Evaluation Order and Recursion 510
12.1 Pass-by-Value or Pass-by-Name? 510
12.2 Strict or Lenient Semantics? 514
12.3 Inheritance of Evaluation Order 515
12.4 Conditionals 517
12.5 Reetirsive Declarations with Normal-Order Languages 519
12.6 Recursive Declarations with Recursive Data Structures 520
12.7 Recursive Declarations with Delayed Expressions 521
12.8 Recursive Function Declarations with Imperative Features 523
12.9 Recursive Function Declarations with Y-Closures 525
12.10 Compound Recursive Function Declarations 531
12.11 Recursive Data Structures 537
Chapter 13. Whither Functional Programming? 541
References 544
Appendix A: The Functional Language (fi) 552
A1 Grammatical Notation 552
A2 Grammar 553
A3 ASCII Representation of (fi) 555
Appendix B: Collected Archetypes 557
B.1 Boolean Type 557
B.2 Integer Type 558
B.3 String Type 559
B.4 Sequence Types 559
B.5 Finite Set Types 560
B.6 Finite Function Types 561
B.7 Direct Product Types 562
B.8 Structure Declarations for Direct Products 562
B.9 Direct Sum Types 563
B.10 Structure Declarations for Direct Sums 564
B.11 Trivial Type 564
B.12 Map and Filter Functionals 565
B.13 Composition 565
B.14 Functional Construction 565
B.15 Reduction and Accumulation Functionals 566
B.16 Constant Construction 566
B.17 Conditional Construction 566
B.18 Functional Direct Sum and Alternation 567
B.19 Pretest Conditional 567
B.20 Recursive Set Types 567
B.21 Recursively Enumerable Sequence Types 568
B.22 Stream Types 568
Appendix C: Functional Programming in Scheme and LISP 569
C.1 General 569
C.2 Declarations 570
C.3 Applications and Abstractions 571
C.4 Booleans 571
C.5 Numbers 572
C.6 Strings 572
C.7 Sequences 572
C.8 Finite Sets 573
C.9 Finite Functions 574
C.10 Direct Products, Sums, and Structures 574
C.11 Streams 575
C.12 Functionals 575
Index of Notation 576
Index 579