James W. Stelly - Racket Programming the Fun Way: From Strings to Turing Machines

From Strings to Turing Machines

by James W. Stelly

San Francisco

RACKET PROGRAMMING THE FUN WAY. Copyright 2021 by James W. Stelly.

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.

ISBN-13: 978-1-7185-0082-2 (print)
ISBN-13: 978-1-7185-0083-9 (ebook)

Publisher: William Pollock
Executive Editor: Barbara Yien
Production Editor: Dapinder Dosanjh
Developmental Editor: Alex Freed
Interior Design: Octopod Studios
Cover Illustration: Gina Redman
Technical Reviewer: Matthew Flatt
Copyeditor: Chris Cartwright
Proofreader: Emelie Battaglia

For information on distribution, translations, or bulk sales, please contact No Starch Press, Inc. directly:
No Starch Press, Inc.
245 8th Street, San Francisco, CA 94103
phone: 415.863.9900; fax: 415.863.9950;
www.nostarch.com

Library of Congress Cataloging-in-Publication Data

Names: Stelly, James W., author.
Title: Racket programming the fun way: from strings to turing machines / by James W. Stelly.
Description: San Francisco : No Starch Press, [2021]. | Includes
bibliographical references and index.
Identifiers: LCCN 2020022884 (print) | LCCN 2020022885 (ebook) | ISBN
9781718500822 | ISBN 9781718500839 (ebook) | ISBN 1718500822
Subjects: LCSH: Racket (Computer program language) | LISP (Computer program
language) | Computer programming.
Classification: LCC QA76.73.R33 S 2020 (print) | LCC QA76.73.R33 (ebook)
| DDC 005.13/3dc23
LC record available at https://lccn.loc.gov/2020022884
LC ebook record available at https://lccn.loc.gov/2020022885

No Starch Press and the No Starch Press 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 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.

I dedicate this book to my mom and dad who patiently (and at times not so patiently) endured my many childhood pranks.

About the Author

James W. Stelly has been dabbling with computers as both a hobbyist and professional for over four decades. He has degrees in both computer science and mathematics from the University of Houston. As a hobbyist, his projects include robotics using Arduino and Raspberry Pi along with numerous explorations of programming languages ranging from machine language to C++ (and many others). His day job (now part time since retirement) is developing a line of business applications primarily aimed at record keeping and data management.

About the Technical Reviewer

Matthew Flatt is a professor in the School of Computing at the University of Utah, where he works on extensible programming languages, run-time systems, and applications of functional programming. He is one of the developers of the Racket programming language and a co-author of the introductory programming textbook How to Design Programs.

CONTENTS IN DETAIL

RACKET BASICS

ARITHMETIC AND OTHER NUMERICAL PARAPHERNALIA

FUNCTION FUNDAMENTALS

PLOTTING, DRAWING, AND A BIT OF SET THEORY

GUI: GETTING USERS INTERESTED

DATA

SEARCHING FOR ANSWERS

LOGIC PROGRAMMING

COMPUTING MACHINES

TRAC: THE RACKET ALGEBRAIC CALCULATOR

A
NUMBER BASES

B
SPECIAL SYMBOLS

ACKNOWLEDGMENTS

First, let me thank the folks responsible for Racket. They have created a truly remarkable piece of software. The care and effort that went into producing it has to be incalculable.

I would like to extend my deepest gratitude and thanks to my editors at No Starch, Alex Freed and Athabasca Witschi, as well as my technical reviewer, Matthew Flatt. They made literally dozens of helpful suggestions for improvements as well as corrections. Any remaining flaws are entirely of my own making.

Finally, let me thank my wife for her patience. Her view of me was primarily of the back of my head while I was working on this book.

INTRODUCTION

In this book we explore using Racket (a language descended from the Scheme family of programming languageswhich in turn descended from Lisp) and DrRacket, a graphical environment that allows us to make the most of all the features of Racket. One of the attractive features of this ecosystem is that its equipped with a plethora of libraries that cover a wide range of disciplines. The developers describe Racket as a system that has batteries included. This makes it an ideal platform for the interactive investigation of various topics in computer science and mathematics.

Given Rackets Lisp pedigree, we would be remiss to omit functional programming, so we will definitely explore it in this text. Racket is no one-trick pony though, so we will also explore imperative, object oriented, and logic programming along the way. Also on the computer science front, we will look at various abstract computing machines, data structures, and a number of search algorithms as related to solving some problems in recreational mathematics. We will finish the book by building our own calculator, which will entail lexical analysis using regular expressions, defining the grammar using extended BackusNaur form (EBNF), and building a recursive descent parser.

Racket

Racket features extensive and well-written documentation, which includes Quick: An Introduction to Racket with Pictures, the introductory Racket Guide, and the thorough Racket Reference. Various other toolkits and environments also have separate documentation. Within DrRacket these items can be accessed through the Help menu.

Racket is available for a wide variety of platforms: Windows, Linux, macOS, and Unix. It can be downloaded from the Racket website via the link https://download.racket-lang.org/. Once downloaded, installation simply entails running the downloaded executable on Windows, .dmg file on macOS, or shell script on Linux. At the time of writing, the current version is 7.8. Examples in the book will run on any version 7.0 or later. They will likely run on earlier versions as well, but since the current version is freely available there is really no need to do so. When the DrRacket environment is first launched, the user will be prompted to select a Racket language variant. The examples in this book all use the first option in the pop-up dialog box (that is, the one that says The Racket Language).