Composing Programs

Description

Welcome to Composing Programs, a free online introduction to programming and computer science. In the tradition of SICP, this text focuses on methods for abstraction, programming paradigms, and techniques for managing the complexity of large programs. These concepts are illustrated primarily using the Python 3 programming language. Table of Contents Chapter 1: Building Abstractions with Functions 1.1 Getting Started 1.1.1 Programming in Python 1.1.2 Installing Python 3 1.1.3 Interactive Sessions 1.1.4 First Example 1.1.5 Errors 1.2 Elements of Programming 1.2.1 Expressions 1.2.2 Call Expressions 1.2.3 Importing Library Functions 1.2.4 Names and the Environment 1.2.5 Evaluating Nested Expressions 1.2.6 The Non-Pure Print Function 1.3 Defining New Functions 1.3.1 Environments 1.3.2 Calling User-Defined Functions 1.3.3 Example: Calling a User-Defined Function 1.3.4 Local Names 1.3.5 Choosing Names 1.3.6 Functions as Abstractions 1.3.7 Operators 1.4 Designing Functions 1.4.1 Documentation 1.4.2 Default Argument Values 1.5 Control 1.5.1 Statements 1.5.2 Compound Statements 1.5.3 Defining Functions II: Local Assignment 1.5.4 Conditional Statements 1.5.5 Iteration 1.5.6 Testing 1.6 Higher-Order Functions 1.6.1 Functions as Arguments 1.6.2 Functions as General Methods 1.6.3 Defining Functions III: Nested Definitions 1.6.4 Functions as Returned Values 1.6.5 Example: Newton's Method 1.6.6 Currying 1.6.7 Lambda Expressions 1.6.8 Abstractions and First-Class Functions 1.6.9 Function Decorators 1.7 Recursive Functions 1.7.1 The Anatomy of Recursive Functions 1.7.2 Mutual Recursion 1.7.3 Printing in Recursive Functions 1.7.4 Tree Recursion 1.7.5 Example: Partitions Chapter 2: Building Abstractions with Data 2.1 Introduction 2.1.1 Native Data Types 2.2 Data Abstraction 2.2.1 Example: Rational Numbers 2.2.2 Pairs 2.2.3 Abstraction Barriers 2.2.4 The Properties of Data 2.3 Sequences 2.3.1 Lists 2.3.2 Sequence Iteration 2.3.3 Sequence Processing 2.3.4 Sequence Abstraction 2.3.5 Strings 2.3.6 Trees 2.3.7 Linked Lists 2.4 Mutable Data 2.4.1 The Object Metaphor 2.4.2 Sequence Objects 2.4.3 Dictionaries 2.4.4 Local State 2.4.5 The Benefits of Non-Local Assignment 2.4.6 The Cost of Non-Local Assignment 2.4.7 Implementing Lists and Dictionaries 2.4.8 Dispatch Dictionaries 2.4.9 Propagating Constraints 2.5 Object-Oriented Programming 2.5.1 Objects and Classes 2.5.2 Defining Classes 2.5.3 Message Passing and Dot Expressions 2.5.4 Class Attributes 2.5.5 Inheritance 2.5.6 Using Inheritance 2.5.7 Multiple Inheritance 2.5.8 The Role of Objects 2.6 Implementing Classes and Objects 2.6.1 Instances 2.6.2 Classes 2.6.3 Using Implemented Objects 2.7 Object Abstraction 2.7.1 String Conversion 2.7.2 Special Methods 2.7.3 Multiple Representations 2.7.4 Generic Functions 2.8 Efficiency 2.8.1 Measuring Efficiency 2.8.2 Memoization 2.8.3 Orders of Growth 2.8.4 Example: Exponentiation 2.8.5 Growth Categories 2.9 Recursive Objects 2.9.1 Linked List Class 2.9.2 Tree Class 2.9.3 Sets Chapter 3: Interpreting Computer Programs 3.1 Introduction 3.1.1 Programming Languages 3.2 Functional Programming 3.2.1 Expressions 3.2.2 Definitions 3.2.3 Compound values 3.2.4 Symbolic Data 3.2.5 Turtle graphics 3.3 Exceptions 3.3.1 Exception Objects 3.4 Interpreters for Languages with Combination 3.4.1 A Scheme-Syntax Calculator 3.4.2 Expression Trees 3.4.3 Parsing Expressions 3.4.4 Calculator Evaluation 3.5 Interpreters for Languages with Abstraction 3.5.1 Structure 3.5.2 Environments 3.5.3 Data as Programs Chapter 4: Data Processing 4.1 Introduction 4.2 Implicit Sequences 4.2.1 Iterators 4.2.2 Iterables 4.2.3 Built-in Iterators 4.2.4 For Statements 4.2.5 Generators and Yield Statements 4.2.6 Iterable Interface 4.2.7 Creating Iterables with Yield 4.2.8 Iterator Interface 4.2.9 Streams 4.2.10 Python Streams 4.3 Declarative Programming 4.3.1 Tables 4.3.2 Select Statements 4.3.3 Joins 4.3.4 Interpreting SQL 4.3.5 Recursive Select Statements 4.3.6 Aggregation and Grouping 4.4 Logic Programming 4.4.1 Facts and Queries 4.4.2 Recursive Facts 4.5 Unification 4.5.1 Pattern Matching 4.5.2 Representing Facts and Queries 4.5.3 The Unification Algorithm 4.5.4 Proofs 4.5.5 Search 4.6 Distributed Computing 4.6.1 Messages 4.6.2 Client/Server Architecture 4.6.3 Peer-to-Peer Systems 4.7 Distributed Data Processing 4.7.1 MapReduce 4.7.2 Local Implementation 4.7.3 Distributed Implementation 4.8 Parallel Computing 4.8.1 Parallelism in Python 4.8.2 The Problem with Shared State 4.8.3 When No Synchronization is Necessary 4.8.4 Synchronized Data Structures 4.8.5 Locks 4.8.6 Barriers 4.8.7 Message Passing 4.8.8 Synchronization Pitfalls 4.8.9 Conclusion Main Related Sites About Composing Programs