Computer Science From Scratch Building Interpreters, Art, Emulators and ML in Python (David Kopec)（Z-Library）

Page 1

(This page has no text content)

Page 2

CONTENTS IN DETAIL ACKNOWLEDGMENTS INTRODUCTION Who This Book Is For What’s in the Book This Book’s Approach About the Code Corrections and Comments PART I: INTERPRETERS 1 THE SMALLEST POSSIBLE PROGRAMMING LANGUAGE What Is Brainfuck? What Makes a Language Turing-Complete? How Brainfuck Works The Structure of an Interpreter Implementing Brainfuck in Python Getting the Source File Writing the Interpreter Running the Interpreter Testing the Interpreter Real-World Applications Exercises Notes 2 WRITING A BASIC INTERPRETER Understanding NanoBASIC BASIC History NanoBASIC’s Paradigm, Syntax, and Semantics

Page 3

NanoBASIC Style and Minutiae An Example NanoBASIC Program Formalizing NanoBASIC’s Syntax The NanoBASIC Implementation The Tokenizer Nodes Errors The Parser The Runtime Running a Program Testing NanoBASIC Real-World Applications Exercises Notes PART II: COMPUTATIONAL ART 3 RETRO IMAGE PROCESSING What Is Dithering? Getting Started The Dithering Algorithm The MacPaint File Format Translating Bytes to Bits Implementing Run-Length Encoding Testing Run-Length Encoding Converting to MacBinary Putting It All Together The Results Real-World Applications Exercises Notes 4 A STOCHASTIC PAINTING ALGORITHM How It Works Command Line Options The SVG Format The Algorithm The Main Implementation Setup Utility Methods Trials Output The Results

Page 4

Real-World Applications Exercises Notes PART III: EMULATORS 5 BUILDING A CHIP-8 VIRTUAL MACHINE Virtual Machines The CHIP-8 Virtual Machine Registers and Memory Instructions The Implementation The Run Loop Command Line Arguments VM Setup and Helper Functions Graphics Instruction Execution Testing the VM Playing Games Real-World Applications Exercises Notes 6 EMULATING THE NES GAME CONSOLE About the NES The Hardware The Software Building the Emulator Planning the Structure Creating the Main Loop Emulating the Cartridge Emulating the CPU Understanding the PPU Implementing the PPU Testing the Emulator Playing Games Real-World Applications Exercises Notes

Page 5

PART IV: SUPER-SIMPLE MACHINE LEARNING 7 CLASSIFICATION WITH K-NEAREST NEIGHBORS The Rise of Machine Learning How KNN Works Implementing Classification with KNN Classifying Fish Classifying Handwritten Digits Real-World Applications Exercises Notes 8 REGRESSION WITH K-NEAREST NEIGHBORS How KNN Regression Works Implementing Regression with KNN Predicting Fish Weights Predicting the Rest of a Handwritten Digit Real-World Applications Exercises Notes AFTERWORD What We Did and What’s Next On Learning Computer Science Interpreters Computational Art Emulators Machine Learning APPENDIX: BITWISE OPERATIONS A Review of Binary Common Bitwise Operations Left Shift (<<) Right Shift (>>) OR (|) AND (&) XOR (^) Complement (~) INDEX

Page 6

COMPUTER SCIENCE FROM SCRATCH Building Interpreters, Art, Emulators, and ML in Python by David Kopec San Francisco

Page 7

COMPUTER SCIENCE FROM SCRATCH. Copyright © 2025 by David Kopec. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing 29 28 27 26 25    1 2 3 4 5 ISBN-13: 978-1-7185-0430-1 (print) ISBN-13: 978-1-7185-0431-8 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www.nostarch.com; info@nostarch.com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Jennifer Kepler Developmental Editor: Nathan Heidelberger Cover Illustrator: Josh Kemble Interior Design: Octopod Studios Technical Reviewer: Michael Kennedy Copyeditor: Audrey Doyle Proofreader: Céline Parent The following images are reproduced with permission: Figures 6-2, 6-4, 6-5, and 6-6 were created by user Damian Yerrick of nesdev.org. Figure 6-7 was created by user Persune of nesdev.org. All the information on nesdev.org is released into the public domain. Library of Congress Control Number: 2025016217 For customer service inquiries, please contact info@nostarch.com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch.com. For permission to translate this work: rights@nostarch.com. To report counterfeit copies or piracy: counterfeit@nostarch.com. The authorized representative in the EU for product safety and compliance is EU Compliance Partner, Pärnu mnt. 139b-14, 11317 Tallinn, Estonia, hello@eucompliancepartner.com, +3375690241. No Starch Press and the No Starch Press iron logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names

Page 8

only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark. The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

Page 9

To my mother, Sylvia, who has celebrated every win with me, and helped me with every loss.

Page 10

About the Author David Kopec is an associate professor of computer science at Albright College. He joined academia in 2016 after working as a software developer, with a concentration in iOS app development. He’s the author of four previous technical books, including Classic Computer Science Problems in Python, which has been translated into eight languages and published around the world. An avid app developer and podcaster, Kopec lives with his wife and three children in Wyomissing, Pennsylvania. About the Technical Reviewer Michael Kennedy is well known in the Python space through his work at the Talk Python to Me and Python Bytes podcasts, which have covered important topics and news in the Python community for almost 10 years. He’s the founder of Talk Python Training, which offers many developer courses online, and is a Python Software Foundation Fellow. Kennedy is based in Portland, Oregon. When he’s not programming or enjoying time with his family, you might find him exploring the local mountains on his motorcycle.

Page 11

ACKNOWLEDGMENTS Most importantly, I would like to thank you, the reader, for purchasing this book. You probably could have found online tutorials for most of the topics in this book, but it’s unlikely they would have been as vetted, as cohesive, or as well put together. At least I think so, and that’s why I wrote this book. By purchasing it, you supported not only its development but also the continued existence of an industry that produces other books like it. Next, I would like to thank Champlain College, which provided me with a sabbatical after seven years of service. There are very few remaining industries that give people time off for the better part of a year to pursue their own work-related interests and pay them to do it. Sometimes something wonderful comes out of that time and space. Completing this book was my sabbatical project. I would like to thank my family who supported me in pursuing this project, especially my mom, Sylvia, and my wife, Rebecca. My kids, Daniel, Vera, and Lucille, are too young to really understand what it means to write a technical book, but I couldn’t have written it if Rebecca wasn’t taking care of them, so instead of thanking them, I’ll thank her a second time. I would like to thank No Starch Press for believing in this book. I came to them with a fully written draft manuscript, which is a bit unusual for a technical book, and they believed in its contents enough to put the resources

Page 12

into refining it for your consumption. In particular, I would like to thank Nathan Heidelberger, my developmental editor, who took the time to empathetically put himself in the shoes of the reader and found ways both large and small to improve the book. And, of course, I’d like to thank the rest of the team at No Starch Press who helped bring the book through development and production. I would also like to thank my technical reviewer, Michael Kennedy, for his good suggestions. Last but not least, I want to thank all of the folks who publicly reviewed my prior books. If you hadn’t reacted positively to my prior books and taken the time to record that, this book would never have had the fuel to take off. If you’re reading this, please take the time to review this book too!

Page 13

INTRODUCTION How does a programming language work? How is a simple computer organized? I’m the type of person who likes to learn new subjects from first principles, in a hands-on way. I want more than just high-level overviews. If you’re that type of learner too, then you’ve found the right resource. Through the seven Python projects in this book, you’ll build an understanding of some fundamental ideas from the realm of computer science.

Page 14

Who This Book Is For This book is for intermediate and advanced Python programmers. If you’re a beginning programmer, you should probably come back to this book at a later point. Throughout the text, I assume the reader knows the syntax and semantics of Python, is comfortable writing programs of moderate complexity, knows how to install Python libraries, and understands basic data structures like lists, sets, and dictionaries. While I do assume readers will have some programming experience, I don’t assume readers’ knowledge of computer science or advanced mathematics. This book is designed for those who either lack a formal computer science education or want to fill in some gaps in their knowledge. For example, if you have an interest in writing your own programming language but you never took a course on compilers, this book is a great starting point. If you want to write a video game console emulator, this book will show you how. It even has a very digestible introduction to machine learning. The exact projects in the book may not themselves be your end goal, but that’s not the point. Think of them as a means to unlock deeper knowledge about algorithmic thinking and how software works, and as a jumping-off point for your own explorations. What’s in the Book Each chapter constitutes one complete project, except for Chapters 7 and 8, which together make up one project. The seven projects in the book range from easy (the Brainfuck interpreter in Chapter 1) to difficult (the NES emulator in Chapter 6), but since all the source code is provided, you’ll never get stuck and be unable to proceed.

Page 15

Each project begins with some theory—just enough to understand what we’ll be implementing, without getting bogged down in the details—and then walks through the code. The chapters also include stories about how I personally got interested in the subject, a discussion of how the implemented algorithms or computational techniques are used in the real world, and challenges for the reader to extend the provided code. The book is divided into four parts. In Part I, we’ll explore the world of interpreters by creating implementations of two simple programming languages. Chapter 1: The Smallest Possible Programming Language Brainfuck is a minimal programming language often used for educational purposes because of its simplicity—the whole language consists of just eight characters. We’ll learn how a very simple interpreter works by implementing one that can run any Brainfuck program. We’ll also learn what it means for a language to be Turing-complete. Chapter 2: Writing a BASIC Interpreter The BASIC programming language and its pared-down dialect, Tiny BASIC, were popular during the PC revolution of the late 1970s. We’ll implement an interpreter for a slightly simplified variant of Tiny BASIC called NanoBASIC. Doing so will demonstrate the constituent parts of more sophisticated interpreters, including a tokenizer, parser, and runtime environment. In Part II, we’ll get into the vibrant world of computational art. Chapter 3: Retro Image Processing When display technology was simpler, dithering algorithms were necessary to adapt images for devices that used a limited color palette. We’ll implement a dithering algorithm capable of displaying modern color photos on

Page 16

the black-and-white screen of an original Macintosh. Then, we’ll convert the dithered images to a format compatible with the classic MacPaint application, using the run-length encoding compression algorithm in the process. The images we output can be displayed on actual 1980s Macintosh hardware. Chapter 4: A Stochastic Painting Algorithm Can a relatively simple algorithm create sophisticated abstract art? We’ll use a stochastic technique to generate “impressions” of existing images by matching random shapes to the underlying image, and we’ll see how a hill-climbing algorithm can help optimize the results. Part III is all about emulators—programs that allow one type of computer to pretend to be another type of computer. Chapter 5: Building a CHIP-8 Virtual Machine  CHIP-8 is a virtual machine (VM) specification that was originally used for developing video games in the 1970s. Building a CHIP-8 VM is often considered the best first step into the world of emulation: it’s relatively simple but still involves all the steps necessary to create an emulator. Our CHIP-8 VM will be capable of playing all the CHIP-8 games that ran on machines in the 1970s. Chapter 6: Emulating the NES Game Console The NES was one of the best-selling video game consoles of all time. We’ll create an emulator that can play real NES games. It will have no sound, be rather slow, and not be completely accurate or universally compatible, but it will still be a great way to learn not just about emulators but also about how computers work at a low level. Finally, Part IV is a very gentle introduction to the world of machine learning using the k-nearest neighbors

Page 17

(KNN) algorithm. Chapter 7: Classification with K-Nearest Neighbors We’ll learn KNN, perhaps the simplest algorithm in machine learning (ML), and use it as a gateway to understand some introductory ML topics. We’ll use KNN to classify fish as well as images of handwritten digits. Amazingly, it will complete the latter task with 98 percent accuracy. Chapter 8: Regression with K-Nearest Neighbors  We’ll take KNN to the next level by using it not just to classify items into categories but also to predict unknown attributes of data points. In the chapter finale, we’ll use it to predict the missing pixels from an image of a digit that the user draws. Beyond the main chapters, the afterword features some suggested resources for learning more about the topics in this book, and the appendix covers the basics of low-level bit manipulation in Python, an essential component of several projects. This Book’s Approach I try to keep my books as succinct as possible. I value your time. I use a tutorial-like, code-centric format to teach, and where possible, I let the code speak for itself. This is not a textbook. You’ll find some theory, especially at the beginning of each chapter, but it will never be too long before we get to some code. There’s just enough information to help you understand how each of the projects works, and enough pointers so that you know where to look next if you want to dive deeper into any of the covered topics. I’m not claiming to be an expert on interpreters, computational art, emulators, or machine learning. That may sound weird coming from the author of a book on

Page 18

those topics, but it’s true. I’m not an expert; I’m a teacher. I’ve worked as a software developer, and I’ve worked as computer science faculty at a teaching college. My claim is that I’m able to write clean code and explain that code to you in an exceptionally comprehensible manner. And since I’m not an expert, I won’t be talking down to you. I’ll be treating you like my peer as we go on this journey together. This is the guide I wish I had as I tried doing projects in these areas on my own. About the Code All the source code in this book is available on the companion GitHub repository at https://github.com /davecom/ComputerScienceFromScratch. The code was created and tested against Python versions 3.12 and 3.13. Because some type hint–related features of Python 3.12 are utilized, some of the code won’t work with earlier versions of Python (but will likely work with any new version of Python in the foreseeable future). However, if you remove the type hints, the vast majority of the code will work with Python version 3.10 and later. I’ve used Python type hints (or “type annotations”) throughout the source code because I believe they increase readability by telling you a function’s parameter and return types without you needing to scrutinize the code or the comments. If you don’t like them, you can ignore them; they don’t change anything about how the code works. I’ve tried not to overuse type hints, as some find them to be too verbose. For example, I rarely use them within function bodies, but I do use them in every function signature. I type-checked all the source code against the contemporary version of Pyright at the time of the book’s writing. Several of the projects in this book use external libraries. You should have Pygame, NumPy, and Pillow installed in the virtual environment you create for the

Page 19

book’s source code or in your system Python interpreter. For most readers, installing them should be as simple as running pip install pygame, numpy, pillow. A requirements.txt file that pip can use is included in the book’s source code repository. Corrections and Comments The book’s GitHub repository is a great place to open an issue if you think you found a mistake. You’re also welcome to reach out to me by email at csfromscratch@oaksnow.com or via X @davekopec. I welcome your feedback, both positive and negative. If you enjoy the book, please also consider leaving a review on Amazon or wherever you purchased it.

Page 20

PART I INTERPRETERS