View on GitHub

abstractions-in-python

Programming Abstractions in Python

Luca de Alfaro

Copyright 2019-21, Luca de Alfaro. License: CC BY-NC

Introduction

This is the online textbook Programming Abstractions in Python, written for the class by the same name at the University of California, Santa Cruz.

The idea of the book, and of the class, consists in teaching students to think about software in terms of objects that have primitive operations. When confronted with a new problem to solve, one should consider what are the objects that are useful for representing the problem, and what operations can be defined on those objects that solve the problem. The operations on objects are often best understood as mathematical operations on the set of objects: considering the properties of the operations leads to cleaner, and more general, solutions.

The book is articulated into five parts:

In the course of the book, we will provide simple implementations of well-known problems. Among other things, we will reimplement the machine-learning framework PyTorch, albeit in a simplified pure-Python setting; we will reimplement the core of Pandas, and we will write Sudoku and Boolean SAT solvers. All these implementations will be concise, minimalistic, and yet powerful, and we hope that they can serve as illustration of how to approach non-trivial software and algorithmic problems.

The book chapters consist in Jupyter notebooks. Jupyter notebooks allow literate programming: one can write, in the same place and properly interleaved, both the text and mathematics that explains the high-level concepts, and their implementations into code. The notebooks provided here form the book. In these notebooks, exercises appear in two forms: as suggestions, and as holes where code is missing, for students to fill in. Separately, upon request, are available also teacher versions of the notebooks, where all the code holes have been filled, so that the whole notebook can be run during a classroom lecture. To request these notebooks, email the author at dealfaro@alumni.stanford.edu.

The author is much indebted to Philippe Bossut for inspiration about the approach, and to Massimo Di Pierro for his many suggestions on topics to cover and methods.

Chapters

We provide each chapter as a link to a notebook hosted in Google Colab. For this to work, you might have to visit the Colab home page prior to clicking on the links here.

Part I: Methods

Part II: Structures

Part III: From Symbolic Expressions to Machine Learning

Part IV: Graphs and Dynamic Algorithms