{"id":2377,"date":"2021-04-12T16:37:17","date_gmt":"2021-04-12T11:07:17","guid":{"rendered":"https:\/\/www.rangakrish.com\/?p=2377"},"modified":"2021-04-12T16:37:17","modified_gmt":"2021-04-12T11:07:17","slug":"book-review-programming-algorithms-in-lisp","status":"publish","type":"post","link":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/12\/book-review-programming-algorithms-in-lisp\/","title":{"rendered":"Book Review: Programming Algorithms in Lisp"},"content":{"rendered":"

Title:<\/strong><\/em><\/span> Programming Algorithms in Lisp: Writing Efficient Programs with Examples in ANSI Common Lisp<\/p>\n

Author:<\/strong><\/em><\/span> Vsevolod Domkin<\/p>\n

Publisher:<\/strong><\/em><\/span> Apress<\/p>\n

Year:<\/strong><\/em><\/span> 2021<\/p>\n

\"\"<\/a>It is only about 5 months since I read and reviewed<\/strong><\/em><\/a>\u00a0a good book on Lisp<\/strong><\/em> written by Micha\u0142 \u201cphoe\u201d Herda<\/strong><\/em>. The present book is by Vsevolod Domkin<\/strong><\/em>\u00a0and I purchased it two weeks ago.\u00a0<\/span>Coincidentally, Micha\u0142<\/strong><\/em> is the technical reviewer for this book.\u00a0<\/span><\/p>\n

In Chapter 1<\/strong><\/em>, the author starts off by touching upon about why algorithms are important, and why he chose Lisp<\/strong><\/em> 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<\/strong><\/em>, and in that sense, this book is welcome indeed.<\/p>\n

Chapter 2<\/strong><\/em> 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.<\/p>\n

Chapter 3<\/strong><\/em> is a 28-page crash course in Lisp<\/strong><\/em>. 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<\/strong><\/em> basics. You can check this article<\/strong><\/em><\/a>\u00a0for my personal recommendation for learning Lisp<\/strong><\/em>. The author makes a reference to his RUTILS<\/strong> library<\/strong><\/a><\/em>, which he uses in many places in his Lisp code, and shows how it can be imported into the Lisp<\/strong><\/em> environment. One thing I noticed is that the section on \u201cComments\u201d<\/strong><\/em> does not mention the multiline comment enclosed within #|<\/strong><\/em>\u00a0and |#<\/strong><\/em>.<\/p>\n

Chapter 4<\/strong><\/em> talks about the importance of Data structures<\/strong><\/em> and Algorithms<\/strong><\/em>. 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<\/strong><\/em> and call-by-reference<\/strong><\/em> in the context of passing a data structure as a function parameter. He concludes by implementing an efficient Union-Find<\/strong><\/em> algorithm.<\/p>\n

Chapter 5<\/strong><\/em> 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<\/strong><\/em>, both fixed size and dynamic. Readers will find the discussion on \u201cWhy are arrays indexed from 0?\u201d<\/strong><\/em> Interesting and informative. This chapter also discusses Searching<\/strong><\/em> and Sorting<\/strong><\/em> algorithms and concludes with a performance comparison of three sorting algorithms.<\/p>\n

As a natural progression, the next chapter is on Linked<\/strong> lists<\/strong><\/em>. List being the fundamental data structure in Lisp<\/strong><\/em>, it is widely used in day-to-day development. Chapter 6<\/strong><\/em> covers Lists in detail, including how to use them as Sets<\/strong><\/em>, and explains the Merge<\/strong><\/em> sort algorithm as applied to lists. Towards the end, the author presents a parallel version Merge<\/strong><\/em> sort using the Eager Future 2<\/strong><\/em><\/a>\u00a0library.<\/p>\n

The next chapter is on Key-Values<\/strong><\/em> and the author presents interesting ideas on using KV<\/strong><\/em> data structure for memoization<\/strong><\/em>, a technique often used to speed up algorithms.<\/p>\n

Chapter 8<\/strong><\/em> provides a detailed look at Hash Tables<\/strong><\/em> – how they can be implemented, importance of hash functions, and the common operations on hash tables. The section on Perfect Hashing<\/strong><\/em>, including the CHM92<\/strong><\/em> algorithm is an interesting read.<\/p>\n

In Chapter 9<\/strong><\/em>, the author covers the ubiquitous Tree<\/strong><\/em> data structure. Different types of Trees namely, Binary Search Tree<\/strong><\/em>, Splay Tree<\/strong><\/em>, Red-Black Tree<\/strong><\/em>, AVL Tree<\/strong><\/em>, B-Tree<\/em><\/strong>, and even Heaps<\/strong><\/em> and Tries<\/strong><\/em> are all covered. The chapter ends with a brief discussion of the application of Trees<\/strong><\/em> for storing Spatial<\/strong><\/em> data.<\/p>\n

The next chapter is about Graphs<\/strong><\/em>. Here too, the author takes care to cover the essentials of representing graphs and different algorithms, including Topological<\/strong><\/em> sorting, Minimum Spanning Tree (Kruskal, Prim)<\/strong><\/em> and Path finding algorithms (Dijkstra, A*)<\/strong><\/em> and Maximum Flow<\/strong><\/em>. The last section is a Page Rank<\/strong><\/em> algorithm implementation. Quite a decent coverage, I must say.<\/p>\n

Chapter 11<\/strong><\/em> is about Strings<\/strong><\/em> and String-related algorithms: Substring search (Knuth-Morris-Pratt, Boyer-Moore, Robin-Karp, and Aho-Corasick)<\/strong><\/em> and Regular Expressions (Thompson\u2019s construction)<\/strong><\/em>. As a practical application of String search, there is brief discussion on Plagiarism<\/strong> detection<\/strong><\/em>.<\/p>\n

Chapter 12<\/strong><\/em> is on Dynamic Programming<\/strong><\/em>. It begins with a simple example of memoization<\/strong><\/em> in the context of Fibonacci<\/strong><\/em> sequence computation and moves on to String segmentation<\/strong><\/em> and Text justification<\/strong><\/em>. The chapter concludes by showing how Back Propagation<\/strong><\/em> can be viewed as a DP problem.<\/p>\n

In Chapter 13<\/strong><\/em>, the author talks about approximation algorithms<\/strong><\/em> that are used for calculations aimed at an \u201cacceptable\u201d<\/strong><\/em> result within certain constraints (usually time). Local search, Genetic algorithms, Branch and Bound, Gradient Descent, <\/strong><\/em>and Singular Value Decomposition<\/strong><\/em>are discussed in some detail. The last section touches upon Fourier transform<\/strong><\/em> and how it is effectively used in compression formats such as JPEG<\/strong><\/em>.<\/p>\n

Chapter 14<\/strong><\/em> is entirely devoted too Compression<\/strong><\/em>. Starting with the concept of Encoding<\/strong><\/em>, the author moves on to Lossless<\/strong><\/em> compression using Huffman coding<\/strong><\/em> and shows an example of its use in compressing and storing a large dictionary. There is also a brief discussion of the Deflate<\/strong><\/em> algorithm.<\/p>\n

The last chapter, Chapter 15<\/strong><\/em>, is about Synchronization<\/strong><\/em>. After talking about low-level synchronisation primitives such as Compare and Swap<\/strong><\/em>, the discussion moves on to Mutual exclusion<\/strong><\/em> algorithms, Lock-free data structures, <\/strong><\/em>and Distributed algorithms<\/strong><\/em>. The last section in this chapter gives an overview of Persistent data structures<\/strong><\/em>.<\/p>\n

That is a lot of complex topics bundled into a single book!<\/p>\n

Who will benefit from this book? I do not expect programmers who are not familiar with Lisp<\/strong><\/em> to start reading this book, although there is a chapter that introduces Lisp<\/strong><\/em>. People who want to learn Lisp<\/strong><\/em> will most probably start with a book such as Peter Seibel\u2019s \u201c Practical Common Lisp\u201c<\/strong><\/em>\u00a0[2] or Peter Norvig\u2019s \u201cParadigms of Artificial Intelligence Programming\u201d <\/strong><\/em>[3]. You may also want to go through my detailed recommendation<\/strong><\/em><\/a>. In my opinion, this book will primarily help programmers who are familiar with Lisp<\/strong><\/em> to some extent and who are looking for material focussed on data structures and algorithms.\u00a0<\/span><\/p>\n

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<\/strong><\/em> implementation. The book by Jason Brownlee<\/strong><\/em> [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<\/strong><\/em> library, which he has used in the Lisp<\/strong><\/em> code. This would help those who have not looked at this library before, although an experienced Lisp<\/strong><\/em> developer can understand what is going on.\u00a0<\/span><\/p>\n

Minor limitations aside, this is a book worth having in your Lisp<\/strong><\/em> library. As far as I can recall, there is no single book on Lisp<\/strong><\/em> that covers various data structures and algorithms in such detail. I sincerely appreciate the author\u2019s dedication and hard work.\u00a0<\/span><\/p>\n

Have a nice week!<\/p>\n

Reference<\/h3>\n

[1]. Jason Brownlee, Clever Algorithms: Nature-Inspired Programming Recipes, 2012.<\/p>\n

[2]. Peter Siebel, Practical Common Lisp, Apress, 2005.<\/p>\n

[3]. Peter Nerving, Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp, Morgan Kaufmann,1992.<\/p>\n","protected":false},"excerpt":{"rendered":"

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\u00a0a good book on Lisp written by Micha\u0142 \u201cphoe\u201d Herda. The present book is by Vsevolod Domkin\u00a0and I purchased it two weeks ago.\u00a0Coincidentally, Micha\u0142 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[94,18],"tags":[275,274,19],"class_list":["post-2377","post","type-post","status-publish","format-standard","hentry","category-book-review","category-lisp","tag-algorithms","tag-data-structures","tag-lisp"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p9OLnF-Cl","jetpack-related-posts":[{"id":2736,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/03\/19\/book-review-introducing-blockchain-with-lisp\/","url_meta":{"origin":2377,"position":0},"title":"Book Review: Introducing Blockchain with Lisp","author":"admin","date":"March 19, 2022","format":false,"excerpt":"Title: Introducing Blockchain with Lisp: Implement and Extend Blockchains with the Racket Language Author: Boro Sitnikovski Publisher: Apress Year: 2021 Blockchains are a hot topic these days and interestingly, I am getting involved in a project that uses Blockchain. Languages such as C++, Java, Go and Node.js are commonly used\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2022\/03\/Blockchain-Book-300x251.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":190,"url":"https:\/\/www.rangakrish.com\/index.php\/2016\/03\/15\/book-review-common-lisp-recipes-by-edi-weitz\/","url_meta":{"origin":2377,"position":1},"title":"Book Review: Common Lisp Recipes – A Problem-Solution Approach","author":"admin","date":"March 15, 2016","format":false,"excerpt":"Last Saturday (March 12, 2016), I got my most eagerly awaited book from Amazon.com. Yes, I am talking about Common Lisp Recipes: A Problem-Solution Approach\u00a0authored by Dr.Edmund Weitz. Of course, if you have been programming in Lisp for a couple of years, you would have definitely heard of Dr.Edi Weitz,\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2383,"url":"https:\/\/www.rangakrish.com\/index.php\/2021\/04\/26\/lparallel-a-parallel-programming-library\/","url_meta":{"origin":2377,"position":2},"title":"lparallel: A Parallel Programming Library","author":"admin","date":"April 26, 2021","format":false,"excerpt":"You may recall that in the last article I had reviewed the book \"Algorithms in Lisp\"\u00a0by Vsevolod Domkin. There was a reference to the lparallel\u00a0library in Chapter 15 of the book. That immediately reminded me of the nice discussion of lparallel by Edi Weitz in Chapter 11 of his excellent\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"pmap: Parallel Map","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=350%2C200&ssl=1","width":350,"height":200,"srcset":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=350%2C200&ssl=1 1x, https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2021\/04\/pmap-300x208.jpg?resize=525%2C300&ssl=1 1.5x"},"classes":[]},{"id":2200,"url":"https:\/\/www.rangakrish.com\/index.php\/2020\/11\/08\/book-review-the-common-lisp-condition-system-beyond-exception-handling-with-control-flow-mechanisms\/","url_meta":{"origin":2377,"position":3},"title":"Book Review – The Common Lisp Condition System: Beyond Exception Handling with Control Flow Mechanisms.","author":"admin","date":"November 8, 2020","format":false,"excerpt":"Title: The Common Lisp Condition System: Beyond Exception Handling with Control Flow Mechanisms Author: Micha\u0142 \"phoe\" Herda Publisher: Apress Year: 2020 Unlike with other languages, it is rare to find new books being published on Lisp. The last book on Lisp, which I purchased was \u201cCommon Lisp Recipes\u201d\u00a0\u00a0by Edmund Weitz\u2026","rel":"","context":"In "Book Review"","block_context":{"text":"Book Review","link":"https:\/\/www.rangakrish.com\/index.php\/category\/book-review\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2020\/11\/Cover-page-209x300.png?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":3555,"url":"https:\/\/www.rangakrish.com\/index.php\/2024\/11\/22\/multiobjective-optimization-moo-in-lisp-and-prolog\/","url_meta":{"origin":2377,"position":4},"title":"Multiobjective Optimization (MOO) in Lisp and Prolog","author":"admin","date":"November 22, 2024","format":false,"excerpt":"Recently I came across a nice article\u00a0by Jose Crespo, where the author stresses that the future of programming revolves around the application of math concepts such as Functor, Monads, Folds, etc. In addition, he argues that familiarity with C\/C++ is essential in this modern AI age. The author goes through\u2026","rel":"","context":"In "C++"","block_context":{"text":"C++","link":"https:\/\/www.rangakrish.com\/index.php\/category\/c\/"},"img":{"alt_text":"Lisp Code for Pareto Front","src":"https:\/\/i0.wp.com\/www.rangakrish.com\/wp-content\/uploads\/2024\/11\/lisp-code-249x300.jpg?resize=350%2C200&ssl=1","width":350,"height":200},"classes":[]},{"id":2927,"url":"https:\/\/www.rangakrish.com\/index.php\/2022\/10\/20\/why-learn-lisp\/","url_meta":{"origin":2377,"position":5},"title":"Why Learn Lisp?","author":"admin","date":"October 20, 2022","format":false,"excerpt":"In the last article, I had shared my views on why programmers should learn Prolog, preferably as the first language. What language should one learn next? I strongly pitch for Lisp, to be precise, \u201cCommon Lisp\u201d. Lisp happens to be the second oldest (1958) programming language, only after Fortran (1957)!\u2026","rel":"","context":"In "LISP"","block_context":{"text":"LISP","link":"https:\/\/www.rangakrish.com\/index.php\/category\/lisp\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2377","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/comments?post=2377"}],"version-history":[{"count":0,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/posts\/2377\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/media?parent=2377"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/categories?post=2377"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rangakrish.com\/index.php\/wp-json\/wp\/v2\/tags?post=2377"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}