Title: Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp
Author: Vsevolod Domkin
Publisher: Apress
Year: 2021
It is only about 5 months since I read and reviewed a good book on Lisp written by Michał “phoe” Herda. The present book is by Vsevolod Domkin and I purchased it two weeks ago. Coincidentally, Michał is the technical reviewer for this book.
In Chapter 1, the author starts off by touching upon about why algorithms are important, and why he chose Lisp as the language for describing algorithms in this book. While I might not agree with him as to why another language such as C++ or Java could not have been chosen, the fact remains that there is no other book that focusses on Algorithms in Lisp, and in that sense, this book is welcome indeed.
Chapter 2 touches upon the notion of algorithmic complexity. There is a good chance that readers of this book will already have a practical understanding of complexity theory, so this chapter can be conveniently skipped.
Chapter 3 is a 28-page crash course in Lisp. It is meant for those who have no background in the language so that they can understand the algorithms discussed in the subsequent chapters. The coverage is decent, but cannot be a substitute for a good book on Lisp basics. You can check this article for my personal recommendation for learning Lisp. The author makes a reference to his RUTILS library, which he uses in many places in his Lisp code, and shows how it can be imported into the Lisp environment. One thing I noticed is that the section on “Comments” does not mention the multiline comment enclosed within #| and |#.
Chapter 4 talks about the importance of Data structures and Algorithms. The author tries to drive home the point that choosing a good data structure is quite important as it lends itself automatically to an efficient algorithm. In passing, he also differentiates between call-by-value and call-by-reference in the context of passing a data structure as a function parameter. He concludes by implementing an efficient Union-Find algorithm.
Chapter 5 is the beginning of the discussion of various data structures. The most common of data structures is arrays, so this chapter delves into Arrays/Vectors, both fixed size and dynamic. Readers will find the discussion on “Why are arrays indexed from 0?” Interesting and informative. This chapter also discusses Searching and Sorting algorithms and concludes with a performance comparison of three sorting algorithms.
As a natural progression, the next chapter is on Linked lists. List being the fundamental data structure in Lisp, it is widely used in day-to-day development. Chapter 6 covers Lists in detail, including how to use them as Sets, and explains the Merge sort algorithm as applied to lists. Towards the end, the author presents a parallel version Merge sort using the Eager Future 2 library.
The next chapter is on Key-Values and the author presents interesting ideas on using KV data structure for memoization, a technique often used to speed up algorithms.
Chapter 8 provides a detailed look at Hash Tables – how they can be implemented, importance of hash functions, and the common operations on hash tables. The section on Perfect Hashing, including the CHM92 algorithm is an interesting read.
In Chapter 9, the author covers the ubiquitous Tree data structure. Different types of Trees namely, Binary Search Tree, Splay Tree, Red-Black Tree, AVL Tree, B-Tree, and even Heaps and Tries are all covered. The chapter ends with a brief discussion of the application of Trees for storing Spatial data.
The next chapter is about Graphs. Here too, the author takes care to cover the essentials of representing graphs and different algorithms, including Topological sorting, Minimum Spanning Tree (Kruskal, Prim) and Path finding algorithms (Dijkstra, A*) and Maximum Flow. The last section is a Page Rank algorithm implementation. Quite a decent coverage, I must say.
Chapter 11 is about Strings and String-related algorithms: Substring search (Knuth-Morris-Pratt, Boyer-Moore, Robin-Karp, and Aho-Corasick) and Regular Expressions (Thompson’s construction). As a practical application of String search, there is brief discussion on Plagiarism detection.
Chapter 12 is on Dynamic Programming. It begins with a simple example of memoization in the context of Fibonacci sequence computation and moves on to String segmentation and Text justification. The chapter concludes by showing how Back Propagation can be viewed as a DP problem.
In Chapter 13, the author talks about approximation algorithms that are used for calculations aimed at an “acceptable” result within certain constraints (usually time). Local search, Genetic algorithms, Branch and Bound, Gradient Descent, and Singular Value Decompositionare discussed in some detail. The last section touches upon Fourier transform and how it is effectively used in compression formats such as JPEG.
Chapter 14 is entirely devoted too Compression. Starting with the concept of Encoding, the author moves on to Lossless compression using Huffman coding and shows an example of its use in compressing and storing a large dictionary. There is also a brief discussion of the Deflate algorithm.
The last chapter, Chapter 15, is about Synchronization. After talking about low-level synchronisation primitives such as Compare and Swap, the discussion moves on to Mutual exclusion algorithms, Lock-free data structures, and Distributed algorithms. The last section in this chapter gives an overview of Persistent data structures.
That is a lot of complex topics bundled into a single book!
Who will benefit from this book? I do not expect programmers who are not familiar with Lisp to start reading this book, although there is a chapter that introduces Lisp. People who want to learn Lisp will most probably start with a book such as Peter Seibel’s “ Practical Common Lisp“ [2] or Peter Norvig’s “Paradigms of Artificial Intelligence Programming” [3]. You may also want to go through my detailed recommendation. In my opinion, this book will primarily help programmers who are familiar with Lisp to some extent and who are looking for material focussed on data structures and algorithms.
Possible improvements? Firstly, I feel that the author could have included pseudocode for the various algorithms (at least the major ones) before giving the Lisp implementation. The book by Jason Brownlee [1] is a great example of how this can be done. This would have increased the size of the book, but it would have certainly enhanced its value. Secondly, the author could have included a brief chapter (preferably after Chapter 2) explaining the different constructs from his RUTILS library, which he has used in the Lisp code. This would help those who have not looked at this library before, although an experienced Lisp developer can understand what is going on.
Minor limitations aside, this is a book worth having in your Lisp library. As far as I can recall, there is no single book on Lisp that covers various data structures and algorithms in such detail. I sincerely appreciate the author’s dedication and hard work.
Have a nice week!
Reference
[1]. Jason Brownlee, Clever Algorithms: Nature-Inspired Programming Recipes, 2012.
[2]. Peter Siebel, Practical Common Lisp, Apress, 2005.
[3]. Peter Nerving, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann,1992.
Thanks for the thorough review and suggestions!