Lisp, the Universe and Everything

2019-12-13

Programming Algorithms: Dynamic Programming

This is a snippet of the "Dynamic Programming" chapter of the book.

This chapter opens the final part of the book entitled "Selected Algorithms". In it, we're going to apply the knowledge from the previous chapters in analyzing a selection of important problems that are mostly application-independent and find usages in many applied domains: optimization, synchronization, compression, and similar.

We will start with a single approach that is arguably the most powerful algorithmic technic in use. If we managed to reduce the problem to Dynamic Programming (DP), in most of the cases, we can consider it solved. The fact that we progressed so far in this book without mentioning DP is quite amazing. Actually, we could have already talked about it several times, especially in the previous chapter on strings, but I wanted to contain this topic to its own chapter so deliberately didn't start the exposition earlier. Indeed, strings are one of the domains where dynamic programming is used quite heavily, but the technic finds application in almost every area.

Also, DP is one of the first marketing terms in CS. When Bellman had invented, he wanted to use the then hyped term "programming" to promote his idea. This has, probably, caused more confusion over the years than benefit. In fact, a good although unsexy name for this technic сould be simply "filling the table" as the essence of the approach is an exhaustive evaluating of all variants with memoization of partial results (in a table) to avoid repetition of redundant computations. Obviously, it will have any benefits only when there are redundant computations, which is not the case, for example, with combinatorial optimization. To determine if a problem may be solved with DP we need to validate that it has the optimal substructure property:

A problem has optimal substructure if when we take its subproblem an optimal solution to the whole problem includes an optimal solution to this subproblem.

An example of the optimal substructure is the shortest path problem. If the shortest path from point A to point B passes through some point C and there are multiple paths from C to B, the one included in the shortest path A-B should be the shortest of them. In fact, the shortest path is an archetypical DP problem which we'll discuss later in this chapter. A counterexample is a Travelling Salesman Problem (TSP): if it had optimal substructure the subpath between any two nodes in the result path should have been the shortest possible path between these nodes. But it isn't true for all nodes because it can't be guaranteed that the edges of the path will form a cycle with all the other shortest paths.

Fibonacci Numbers

So, as we said, the essence of DP is filling a table. This table, though, may have a different number of dimensions for different problems. Let's start with a 1d case. What book on algorithms can omit discussing the Fibonacci numbers? Usually, they are used to illustrate recursion, yet they are also a great showcase for the power of memoization. Besides, recursion is, conceptually, also an integral part of DP.

A naive approach to calculating the `i`-th number will be directly coding the Fibonacci formula:

``````(defun naive-fib (i)
(assert (typep i '(integer 0)))
(if (< i 2) 1
(+ (naive-fib (- i 1))
(naive-fib (- i 2)))))
``````

However, applying it will result in an exponential growth of the number of computations: each call to `naive-fib` results in two more calls. So, the number of calls needed for the `n`-th number, with this approach, is `O(2^n)`.

``````> (time (naive-fib 40))
Evaluation took: 3.390 seconds of real time
165580141
> (time (naive-fib 42))
Evaluation took: 7.827 seconds of real time
433494437
``````

Yet, we can see here a direct manifestation of an optimal substructure property: the `i`-th number calculation uses the result of the `(1- i)`-th one. To utilize this recurrence, we'll need to store the previous results and reuse them. It may be achieved by changing the function call to the table access. Actually, from the point of view of math, tables and functions are, basically, the same thing.

``````(let ((fib (vec 1 1)))  ; our table will be an adjustable vector
(defun fib (i)
(when (< (length fib) i)
(vector-push-extend (fib (- i 1)) fib))
(+ (? fib (- i 1))
(? fib (- i 2)))))
``````

What we've done here is added a layer of memoization to our function that uses an array `fib` that is filled with the consecutive Fibonacci numbers. The array is hidden inside the closure of the `fib` procedure, so it will persist between the calls to it and accumulate the numbers as they are requested. There will also be no way to clear it, apart from redefining the function, as the closed over variables of this kind are not accessible outside of the function. The consecutive property is ensured by the arrangement of the recursive calls: the table is filled on the recursive ascent starting from the lowest yet unknown number. This approach guarantees that each Fibonacci number is calculated exactly once and reduces our dreaded `O(2^n)` running time to a mere `O(n)`!

Such a calculation is the simplest example of top-down DP that is performed using recursion. Despite its natural elegance, it suffers from a minor problem that may turn significant, in some cases: extra space consumption by each recursive call. It's not only `O(n)` in time, but also in space. The alternative strategy that gets rid of redundant space usage is called bottom-up DP and is based on loops instead of recursion. Switching to it is quite trivial, in this case:

``````(let ((fib (vec 1 1)))
(defun bottom-up-fib (i)
(let ((off (length fib)))
(adjust-array fib (1+ i) :fill-pointer t)
(dotimes (j (- (1+ i) off))
(let ((j (+ j off)))
(:= (aref fib j)
(+ (aref fib (- j 1))
(aref fib (- j 2)))))))
(aref fib i)))
> (time (bottom-up-fib 42))
Evaluation took: 0.000 seconds of real time
> (time (bottom-up-fib 4200))
Evaluation took: 0.004 seconds of real time
40512746637826407679504078155833145442086707013857032517543...  ; this number is a Lisp's bignum that has unlimited size
``````

Funny enough, a real-word-ready implementation of Fibonacci numbers ends up not using recursion at all...

More details about of the book may be found on its website.

2019-11-20

Programming Algorithms: Strings

This is a snippet of the "Srings" chapter of the book.

It may not be immediately obvious why the whole chapter is dedicated to strings. Aren't they just glorified arrays? There are several answers to these challenges:

• indeed, strings are not just arrays, or rather, not only arrays: in different contexts, other representations, such as trees or complex combinations of arrays, may be used. And, besides, there are additional properties that are important for strings even when they are represented as arrays
• there's a lot of string-specific algorithms that deserve their own chapter
• finally, strings play a significant role in almost every program, so they have specific handling: in the OS, standard library, and even, sometimes, your application framework

In the base case, a string is, indeed, an array. As we already know, this array may either store its length or be a 0-terminated security catastrophe, like in C (see buffer overflow). So, to iterate, strings should store their length. Netstrings are a notable take on the idea of the length-aware strings: it's a simple external format that serializes a string as a tuple of length and contents, separated by a colon and ending with a comma: `3:foo,` is the netsrting for the string `foo`.

More generally, a string is a sequence of characters. The characters themselves may be single bytes as well as fixed or variable-length byte sequences. The latter character encoding poses raises a challenging question of what to prefer, correctness or speed? With variable-length Unicode code points, the simplest and fastest string variant, a byte array, breaks, for it will incorrectly report its length (in bytes, not in characters) and fail to retrieve the character by index. Different language ecosystems address this issue differently, and the majority is, unfortunately, broken in one aspect or another. Overall, there may be two possible solution paths. The first one is to use a fixed-length representation and pad shorter characters to full length. Generally, such representation will be 32-bit UTF-32 resulting in up to 75% storage space waste for the most common 1-byte ASCII characters. The alternative approach will be to utilize a more advanced data-structure. The naive variant is a list, which implies an unacceptable slowdown of character access operation to `O(n)`. Yet, a balanced approach may combine minimal additional space requirements with acceptable speed. One of the solutions may be to utilize the classic bitmap trick: use a bit array indicating, for each byte, whether it's the start of a character (only a 12% overhead). Calculating the character position may be performed in a small number of steps with the help of an infamous, in close circles, operation — Population count aka Hamming weight. This hardware instruction calculates the number of 1-bits in an integer and is accessible via `logcount` Lisp standard library routine. Behind the scenes, it is also called for bit arrays if you invoke `count 1` on them. At least this is the case for SBCL:

``````CL-USER> (disassemble (lambda (x)
(declare (type (simple-array bit) x))
(count 1 x)))

; disassembly for (LAMBDA (X))
; Size: 267 bytes. Origin: #x100FC9FD1A
...
; DA2:       F3480FB8FA       POPCNT RDI, RDX
``````

The indexing function implementation may be quite tricky, but the general idea is to try to jump ahead `n` characters and calculate the popcount of the substring from the previous position to the current that will tell us the number of characters we have skipped. For the base case of a 1-byte string, we will get exactly where we wanted in just 1 jump and 1 popcount. However, if there were multibyte characters in the string, the first jump would have skipped less than `n` characters. If the difference is sufficiently small (say, below 10) we can just perform a quick linear scan of the remainder and find the position of the desired character. If it's larger than `n/2` we can jump ahead `n` characters again (this will repeat at most 3 times as the maximum byte-length of a character is 4), and if it's below `n/2` we can jump `n/2` characters. And if we overshoot we can reverse the direction of the next jump or search. You can see where it's heading: if at each step (or, at least, at each 4th step) we are constantly half dividing our numbers this means `O(log n)` complexity. That's the worst performance for this function we can get, and it will very efficiently handle the cases when the character length doesn't vary: be it 1 byte — just 2 operations, or 4 bytes — 8 ops.

Here is the prototype of the `char-index` operation implemented according to the described algorithm (without the implementation of the `mb-linear-char-index` that performs the final linear scan):

``````(defstruct (mb-string (:conc-name mbs-))
bytes
bitmap)

(defparameter *mb-threshold* 10)

(defun mb-char-index (string i)
(let ((off 0))
(loop
(with ((cnt (count 1 (mbs-bitmap string) :start off :end (+ off i))))
(diff (- i cnt)))
(cond
((= cnt i) (return (+ off i)))
((< diff *mb-threshold*) (return (mb-linear-char-index
string diff off)))
((< cnt (floor i 2)) (:+ off i)
(:- i cnt))
(t (:+ off (floor i 2))
(:- i cnt)))))))
``````

The `length` of such a string may be calculated by perfoming the popcount on the whole bitmap:

``````(defun mb-length (string)
(count 1 (mbs-bitmap string)))
``````

It's also worth taking into account that there exists a set of rules assembled under the umbrella of the Unicode collation algorithm that specifies how to order strings containing Unicode code-points.

More details about of the book may be found on its website.

2019-10-25

Programmatically Drawing Simple Graphviz Graphs

For my book, I had to draw a number of graphs. Obviously, I wanted to have a programmatic way to do that, and Graphviz is the goto-library for that. In Lisp, the interface to Graphviz is cl-dot, but, for me, it wasn't easy to figure out from the manual the "simple and easy" way to use it. I.e. I couldn't find a stupid beginner-level interface, so I had to code it myself. Here's the implementation that allows anyone with a REPL to send to Graphviz lists of edges and obtain graph images.

Generated images:

2019-10-24

Programming Algorithms: Graphs

This is a snippet of the "Graphs" chapter of the book.

Graphs have already been mentioned several times, in the book, in quite diverse contexts. Actually, if you are familiar with graphs you can spot opportunities to use them in quite different areas for problems that aren't explicitly formulated with graphs in mind. So, in this chapter, we'll discuss how to handle graphs to develop such intuition to some degree.

But first, let's list the most prominent examples of the direct graph applications, some of which we'll see here in action:

• pathfinding
• network analysis
• dependency analysis in planning, compilers, etc.
• various optimization problems
• distributing and optimizing computations
• knowledge representation and reasoning with it
• meaning representation in natural language processing

Graphs may be thought of as a generalization of trees: indeed, trees are, as we said earlier, connected directed acyclic graphs. But there's an important distinction in the patterns of the usage of graphs and trees. Graphs, much more frequently than trees, have weights associated with the edges, which adds a whole new dimension both to algorithms for processing them and to possible data that can be represented in the graph form. So, while the main application of trees is reflecting some hierarchy, for graphs, it is often more about determining connectedness and its magnitude, based on the weights.

Graph Representations

A graph is, basically, a set of nodes (called "vertices", `V`) and an enumeration of their pairs ("edges", `E`). The edges may be directed or undirected (i.e. bidirectional), and also weighted or unweighted. There are many ways that may be used to represent these sets, which have varied utility for different situations. Here are the most common ones:

• as a linked structure: `(defstruct node data links)` where `links` may be either a list of other `node`s, possibly, paired with weights, or a list of `edge` structures represented as `(defsturct edge source destination weight)`. For directed graphs, this representation will be similar to a singly-linked list but for undirected — to a heavier doubly-linked one
• as an adjacency matrix (`V x V`). This matrix is indexed by vertices and has zeroes when there's no connection between them and some nonzero number for the weight (1 — in case of unweighted graphs) when there is a connection. Undirected graphs have a symmetric adjacency matrix and so need to store only the abovediagonal half of it
• as an adjacency list that enumerates for each vertex the other vertices it's connected to and the weights of connections
• as an incidence matrix (`V x E`). This matrix is similar to the previous representation, but with much more wasted space. The adjacency list may be thought of as a sparse representation of the incidence matrix. The matrix representation may be more useful for hypergraphs (that have more than 2 vertices for each edge), though
• just as a list of edges

More details about of the book may be found on its website.

2019-09-28

Programming Algorithms: Trees

This is a snippet of the "Trees" chapter of the book.

Balancing a binary tree is the infamous interview problem that has all that folklore and debate associated with it. To tell you the truth, like the other 99% of programmers, I never had to perform this task for some work-related project. And not even due to the existence of ready-made libraries, but because self-balancing binary trees are, actually, pretty rarely used. But trees, in general, are ubiquitous even if you may not recognize their presence. The source code we operate with, at some stage of its life, is represented as a tree (a popular term here is Abstract Syntax Tree or AST, but the abstract variant is not the only one the compilers process). The directory structure of the file system is the tree. The object-oriented class hierarchy is likewise. And so on. So, returning to interview questions, trees indeed are a good area as they allow to cover a number of basic points: linked data structures, recursion, complexity. But there's a much better task, which I have encountered a lot in practice and also used quite successfully in the interview process: breadth-first tree traversal. We'll talk about it a bit later.

Similar to how hash-tables can be thought of as more sophisticated arrays (they are sometimes even called "associative arrays"), trees may be considered an expansion of linked lists. Although technically, a few specific trees are implemented not as a linked data structure but are based on arrays, the majority of trees are linked. Like hash-tables, some trees also allow for efficient access to the element by key, representing an alternative key-value implementation option.

Basically, a tree is a recursive data structure that consists of nodes. Each node may have zero or more children. If the node doesn't have a parent, it is called the root of the tree. And the constraint on trees is that the root is always single. Graphs may be considered a generalization of trees that don't impose this constraint, and we'll discuss them in a separate chapter. In graph terms, a tree is an acyclic directed single-component graph. Directed means that there's a one-way parent-child relation. And acyclic means that a child can't have a connection to the parent neither directly, nor through some other nodes (in the opposite case, what will be the parent and what — the child?) The recursive nature of trees manifests in the fact that if we extract an arbitrary node of the tree with all of its descendants, the resulting part will remain a tree. We can call it a subtree. Besides parent-child or, more generally, ancestor-descendant "vertical" relationships that apply to all the nodes in the tree, we can also talk about horizontal siblings — the set of nodes that have the same parent/ancestor.

Another important tree concept is the distinction between terminal (leaf) and nonterminal (branch) nodes. Leaf nodes don't have any children. In some trees, the data is stored only in the leaves with branch nodes serving to structure the tree in a certain manner. In other trees, the data is stored in all nodes without any distinction.

More details about of the book may be found on its website.

2019-09-11

Programming Algorithms: Hash-Tables

This is a snippet of the "Hash-Tables" chapter of the book.

Now, we can move on to studying advanced data structures which are built on top of the basic ones such as arrays and lists, but may exhibit distinct properties, have different use cases, and special algorithms. Many of them will combine the basic data structures to obtain new properties not accessible to the underlying structures. The first and most important of these advanced structures is, undoubtedly, the hash-table. However vast is the list of candidates to serve as key-values, hash-tables are the default choice for implementing them.

Also, hash-sets, in general, serve as the main representation for medium and large-sized sets as they ensure `O(1)` membership test, as well as optimal set-theoretic operations complexity. A simple version of a hash-set can be created using a normal hash-table with `t` for all values.

Implementation

The basic properties of hash-tables are average `O(1)` access and support for arbitrary keys. These features can be realized by storing the items in an array at indices determined by a specialized function that maps the keys in a pseudo-random way — hashes them. Technically, the keys should pertain to the domain that allows hashing, but, in practice, it is always possible to ensure either directly or by using an intermediate transformation. The choice of variants for the hash-function is rather big, but there are some limitations to keep in mind:

1. As the backing array has a limited number of cells (`n`), the function should produce values in the interval `[0, n)`. This limitation can be respected by a 2-step process: first, produce a number in an arbitrary range (for instance, a 32-bit integer) and then take the remainder of its division by `n`.
2. Ideally, the distribution of indices should be uniform, but similar keys should map to quite distinct indices. I.e. hashing should turn things which are close, into things which are distant. This way, even very small changes to the input will yield sweeping changes in the value of the hash. This property is called the "avalanche effect".

Dealing with Collisions

Even better would be if there were no collisions — situations when two or more keys are mapped to the same index. Is that, at all, possible? Theoretically, yes, but all the practical implementations that we have found so far are too slow and not feasible for a hash-table that is dynamically updated. However, such approaches may be used if the keyset is static and known beforehand. They will be covered in the discussion of perfect hash-tables.

For dynamic hash-tables, we have to accept that collisions are inevitable. The probability of collisions is governed by an interesting phenomenon called "The Birthday Paradox". Let's say, we have a group of people of some size, for instance, 20. What is the probability that two of them have birthdays on the same date? It may seem quite improbable, considering that there are 365 days in a year and we are talking just about a handful of people. But if you take into account that we need to examine each pair of people to learn about their possible birthday collision that will give us `(/ (* 20 19) 2)`, i.e. 190 pairs. We can calculate the exact probability by taking the complement to the probability that no one has a birthday collision, which is easier to reason about. The probability that two people don't share their birthday is `(/ (- 365 1) 365)`: there's only 1 chance in 365 that they do. For three people, we can use the chain rule and state that the probability that they don't have a birthday collision is a product of the probability that any two of them don't have it and that the third person also doesn't share a birthday with any of them. This results in `(* (/ 364 365) (/ (- 365 2) 365))`. The value `(- 365 2)` refers to the third person not having a birthday intersection with neither the first nor the second individually, and those are distinct, as we have already asserted in the first term. Continuing in such fashion, we can count the number for 20 persons:

``````(defun birthday-collision-prob (n)
(let ((rez 1))
(dotimes (i n)
(:* rez (/ (- 365 i) 365)))
;; don't forget that we want the complement
;; of the probability of no collisions,
;; hence (- 1.0 ...)
(- 1.0 rez)))

CL-USER> (birthday-collision-prob 20)
0.4114384
``````

So, among 20 people, there's already a 40% chance of observing a coinciding birthday. And this number grows quickly: it will become 50% at 23, 70% at 30, and 99.9% at just 70!

But why, on Earth, you could ask, have we started to discusss birthdays? Well, if you substitute keys for persons and the array size for the number of days in a year, you'll get the formula of the probability of at least one collision among the hashed keys in an array, provided the hash function produces perfectly uniform output. (It will be even higher if the distribution is non-uniform).

``````(defun hash-collision-prob (n size)
(let ((rez 1))
(dotimes (i n)
(:* rez (/ (- size i) size)))
(- 1.0 rez)))
``````

Let's say, we have 10 keys. What should be the array size to be safe against collisions?

``````CL-USER> (hash-collision-prob 10 10)
0.9996371
``````

99.9%. OK, we don't stand a chance to accidentally get a perfect layout. :( What if we double the array size?

``````CL-USER> (hash-collision-prob 10 20)
0.9345271
``````

93%. Still, pretty high.

``````CL-USER> (hash-collision-prob 10 100)
0.37184352
CL-USER> (hash-collision-prob 10 10000)
0.004491329
``````

So, if we were to use a 10k-element array to store 10 items the chance of a collision would fall below 1%. Not practical...

Note that the number depends on both arguments, so `(hash-collision-prob 10 100)` (0.37) is not the same as `(hash-collision-prob 20 200)` (0.63).

We did this exercise to completely abandon any hope of avoiding collisions and accept that they are inevitable. Such mind/coding experiments may be an effective smoke-test of our novel algorithmic ideas: before we go full-speed and implement them, it makes sense to perform some back-of-the-envelope feasibility calculations.

More details about of the book may be found on its website.

2019-08-30

Programming Algorithms: Key-Values

This is a snippet of the "Key-Values" chapter of the book.

To conclude the description of essential data structures, we need to discuss key-values (kvs), which are the broadest family of structures one can imagine. Unlike arrays and lists, kvs are not concrete structures. In fact, they span, at least in some capacity, all of the popular concrete ones, as well as some obscure.

The main feature of kvs is efficient access to the values by some kind of keys that they are associated with. In other words, each element of such data structure is a key-value pair that can be easily retrieved if we know the key, and, on the other hand, if we ask for the key that is not in the structure, the null result is also returned efficiently. By "efficiently", we usually mean `O(1)` or, at least, something sublinear (like `O(log n)`), although, for some cases, even `O(n)` retrieval time may be acceptable. See how broad this is! So, a lot of different structures may play the role of key-values.

By the way, there isn't even a single widely-adopted name for such structures. Besides key-values — which isn't such a popular term (I derived it from key-value stores) — in different languages, they are called maps, dictionaries, associative arrays, tables, objects and so on.

In a sense, these are the most basic and essential data structures. They are so essential that some dynamic languages — for example, Lua, explicitly, and JavaScript, without a lot of advertisement — rely on them as the core (sometimes sole) language's data structure. Moreover, key-values are used almost everywhere. Below is a list of some of the most popular scenarios:

• implementation of the object system in programming languages
• most of the key-value stores are, for the most part, glorified key-value structures
• internal tables in the operating system (running process table or file descriptor tables in the Linux kernel), programming language environment or application software
• all kinds of memoization and caching
• efficient implementation of sets
• ad hoc or predefined records for returning aggregated data from function calls
• representing various dictionaries (in language processing and beyond)

Considering such a wide spread, it may be surprising that, historically, the programming language community only gradually realized the usefulness of key-values. For instance, such languages as C and C++ don't have the built-in support for general kvs (if we don't count structs and arrays, which may be considered significantly limited versions). Lisp, on the contrary, was to some extent pioneering their recognition with the concepts of alists and plists, as well as being one of the first languages to have hash-table support in the standard.

More details about of the book may be found on its website.

2019-08-29

RUTILS 5.0 and Tutorial

RUTILS is my take on the Lisp "modernization" effort that adds the missing syntactic and data structure pieces, which became proven and well-established, in Lisp itself or in other languages. The programming field is constantly developing while the Lisp standard remains fixed so some additions, over time, are not only desirable but inevitable, if we don't want to lag behind. Thankfully, Lisp provides all the necessary means for implementing them and so, with some creativity, there's a way to have access to almost anything you want and need while retaining full backward compatibility (a lack of which is the most critical problem of some alternative solutions).

I, surely, understand that using such an extension remains a matter of taste and not every Lisper will like it. I didn't try to seriously promote it and was quite satisfied with the benefit that it provided to me and my teams' development. However, as I decided to use it for the "Programming Algorithms" book, it received some attention and a number of questions. From the direction of the discussions, I realized that the docs are lacking a critical part — the tutorial explaining how to effectively use the library. This text is intended to bridge that gap. I had to finish it before publishing the next chapter of the book, which I'll do on Friday.

So, today, version 5 of RUTILS is released alongside with the tutorial that aims to better explain its usage.

2019-08-19

This is a snippet of the "Lists" chapter of the book.

Linked data structures are in many ways the opposite of the contiguous ones that we have explored to some extent in the previous chapter using the example of arrays. In terms of complexity, they fail where those ones shine (first of all, at random access) — but prevail at scenarios when a repeated modification is necessary. In general, they are much more flexible and so allow the programmer to represent almost any kind of a data structure, although the ones that require such level of flexibility may not be too frequent. Usually, they are specialized trees or graphs.

Just like arrays, lists in Lisp may be created both with a literal syntax for constants and by calling a function — `make-list` — that creates a list of a certain size filled with `nil` elements. Besides, there's a handy `list` utility that is used to create lists with the specified content (the analog of `vec`).

``````CL-USER> '("hello" world 111)
("hello" WORLD 111)
CL-USER> (make-list 3)
(NIL NIL NIL)
CL-USER> (list "hello" 'world 111)
("hello" WORLD 111)
``````

An empty list is represented as `()` and, interestingly, in Lisp, it is also a synonym of logical falsehood (`nil`). This property is used very often, and we'll have a chance to see that.

If we were to introduce our own lists, which may be quite a common scenario in case the built-in ones' capabilities do not suit us, we'd need to define the structure "node", and our list would be built as a chain of such nodes. We might have wanted to store the list head and, possibly, tail, as well as other properties like size. All in all, it would look like the following:

``````(defstruct list-cell
data
next)

(defstruct our-own-list
(head nil :type (or list-cell null))
(tail nil :type (or list-cell null)))

CL-USER> (let ((tail (make-list-cell :data "world")))
(make-our-own-list
:data "hello"
:next tail)
:tail tail))
#S(OUR-OWN-LIST
:DATA "hello"
:NEXT #S(LIST-CELL :DATA "world" :NEXT NIL))
:TAIL #S(LIST-CELL :DATA "world" :NEXT NIL))
``````

More details about of the book may be found on its website.

2019-08-12

Programming Algorithms: Arrays

This is a snippet of the "Arrays" chapter of the book.

Arrays are, alongside structs, the most basic data structure and, at the same time, the default choice for implementing algorithms. A one-dimensional array that is also called a "vector" is a contiguous structure consisting of the elements of the same type. One of the ways to create such arrays, in Lisp, is this:

``````CL-USER> (make-array 3)
#(0 0 0)
``````

The printed result is the literal array representation. It happens that the array is shown to hold 0's, but that's implementation-dependent. Additional specifics can be set during array initialization: for instance, the `:element-type`, `:initial-element`, and even full contents:

``````CL-USER> (make-array 3 :element-type 'list :initial-element nil)
#(NIL NIL NIL)
CL-USER> (make-array 3 :initial-contents '(1.0 2.0 3.0))
#(1.0 2.0 3.0)
``````

If you read back such an array you'll get a new copy with the same contents:

``````CL-USER> #(1.0 2.0 3.0)
#(1.0 2.0 3.0)
``````

It is worth noting that the element type restriction is, in fact, not a limitation the default type is `T`[1]. In this case, the array will just hold pointers to its elements that can be of arbitrary type. If we specify a more precise type, however, the compiler might be able to optimize storage and access by putting the elements in memory directly in the array space. This is, mainly, useful for numeric arrays, but it makes multiple orders of magnitude difference for them for several reasons, including the existence of vector CPU instructions that operate on such arrays.

The arrays we have created are mutable, i.e. we can change their contents, although we cannot resize them. The main operator to access array elements is `aref`. You will see it in those pieces of code, in this chapter, where we care about performance.

``````CL-USER> (let ((vec (make-array 3 :initial-contents '(1.0 2.0 3.0))))
(print (aref vec 0))
(print (? vec 1))
(:= (aref vec 2) 4.0))
(print (? vec 2))
(aref vec 3))
1.0
2.0
4.0
; Evaluation aborted on #<SIMPLE-TYPE-ERROR expected-type: (MOD 3) datum: 3>
``````

In Lisp, array access beyond its boundary, as expected, causes an error.

It is also possible to create constant arrays using the literal notation `#()`. These constants can, actually, be changed in some environments, but don't expect anything nice to come out of such abuse — and the compiler will warn you of that:

``````CL-USER> (let ((vec #(1.0 2.0 3.0)))
(:= (aref vec 2) nil)
(print vec))
; caught WARNING:
;   Destructive function (SETF AREF) called on constant data.
;     The ANSI Standard, Special Operator QUOTE
;     The ANSI Standard, Section 3.2.2.3
;
; compilation unit finished
;   caught 1 WARNING condition

#(1.0 2.0 NIL)
``````

RUTILS provides more options to easily create arrays with a shorthand notation:

``````CL-USER> #v(1 2 3)
#(1 2 3)
CL-USER> (vec 1 2 3)
#(1 2 3)
``````

Although the results seem identical they aren't. The first version creates a mutable analog of `#(1 2 3)`, and the second also makes it adjustable (we'll discuss adjustable or dynamic arrays next).

More details about of the book may be found on its website.

2019-08-05

Programming Algorithms: Data Structures

The next several chapters will be describing the basic data structures that every programming language provides, their usage, and the most important algorithms relevant to them. And we'll start with the notion of a data-structure and tuples or structs that are the most primitive and essential one. Here is a snippet from this chapter.

Data Structures vs Algorithms

Let's start with a somewhat abstract question: what's more important, algorithms or data structures?

From one point of view, algorithms are the essence of many programs, while data structures may seem secondary. Besides, although a majority of algorithms rely on certain features of particular data structures, not all do. Good examples of the data-structure-relying algorithms are heapsort, search using BSTs, and union-find. And of the second type: the sieve of Erastophenes and consistent hashing.

At the same time, some seasoned developers state that when the right data structure is found, the algorithm will almost write itself. Linus Torvalds, the creator of Linux, is quoted saying:

A somewhat less poignant version of the same idea is formulated in the Art of Unix Programming by Eric S. Raymond as the "Rule of Representation":

Fold knowledge into data so program logic can be stupid and robust.

Even the simplest procedural logic is hard for humans to verify, but quite complex data structures are fairly easy to model and reason about. To see this, compare the expressiveness and explanatory power of a diagram of (say) a fifty-node pointer tree with a flowchart of a fifty-line program. Or, compare an array initializer expressing a conversion table with an equivalent switch statement. The difference in transparency and clarity is dramatic.

Data is more tractable than program logic. It follows that where you see a choice between complexity in data structures and complexity in code, choose the former. More: in evolving a design, you should actively seek ways to shift complexity from code to data.

Data structures are more static than algorithms. Surely, most of them allow change of their contents over time, but there are certain invariants that always hold. This allows reasoning by simple induction: consider only two (or at least a small number of) cases, the base one(s) and the general. In other words, data structures remove, in the main, the notion of time from consideration, and change over time is one of the major causes of program complexity. In other words, data structures are declarative, while most of the algorithms are imperative. The advantage of the declarative approach is that you don't have to imagine (trace) the flow of time through it.

So, this book, like most other books on the subject, is organized around data structures. The majority of the chapters present a particular structure, its properties and interface, and explain the algorithms, associated with it, showing its real-world use cases. Yet, some important algorithms don't require a particular data structure, so there are also several chapters dedicated exclusively to them.

2019-07-29

Programming Algorithms: A Crash Course in Lisp

The introductory post for this book, unexpectedly, received quite a lot of attention, which is nice since it prompted some questions, and one of them I planned to address in this chapter.

I expect that there will be two main audiences, for this book:

• people who’d like to advance in algorithms and writing efficient programs — the major group
• lispers, either accomplished or aspiring who also happen to be interested in algorithms

This introductory chapter is, primarily, for the first group. After reading it, the rest of the book’s Lisp code should become understandable to you. Besides, you’ll know the basics to run Lisp and experiment with it if will you so desire.

For the lispers, I have one comment and one remark. You might be interested to read this part just to understand my approach of utilizing the language throughout the book. Also, you’ll find my stance regarding the question that was voiced several times in the comments: whether it’s justified to use some 3rd-party extensions and to what extent or should the author vigilantly stick to only the tools provided by the standard.

The Core of Lisp

To effortlessly understand Lisp, you’ll have to forget, for a moment, any concepts of how programming languages should work that you might have acquired from your prior experience in coding. Lisp is simpler; and when people bring their Java, C or Python approaches to programming with it, first of all, the results are suboptimal in terms of code quality (simplicity, clarity, and beauty), and, what’s more important, there’s much less satisfaction from the process, not to mention very few insights and little new knowledge gained.

It is much easier to explain Lisp if we begin from a blank slate. In essence, all there is to it is just an evaluation rule: Lisp programs consist of forms that are evaluated by the compiler. There are 3+2 ways how that can happen:

• self-evaluation: all literal constants (like `1`, `"hello"`, etc.) are evaluated to themselves. These literal objects can be either built-in primitive types (`1`) or data structures (`"hello"`)
• symbol evaluation: separate symbols are evaluated as names of variables, functions, types or classes depending on the context. The default is variable evaluation, i.e. if we encounter a symbol `foo` the compiler will substitute in its place the current value associated with this variable (more on this a little bit later)
• expression evaluation: compound expressions are formed by grouping symbols and literal objects with parenthesis. The following form `(oper 1 foo)` is considered a “functional” expression: the operator name is situated in the first position (head), and its arguments, if any, in the subsequent positions (rest). There are 3 ways to evaluate a functional expression:
• there are 25 special operators that are defined in lower-level code and may be considered something like axioms of the language: they are pre-defined, always present, and immutable. Those are the building blocks, on top of which all else is constructed, and they include the sequential `block` operator, the conditional expression `if`, and the unconditional jump `go`, to name a few. If `oper` is the name of a special operator, the low-level code for this operator that deals with the arguments in its own unique way is executed
• there’s also ordinary function evaluation: if `oper` is a function name, first, all the arguments are evaluated with the same evaluation rule, and then the function is called with the obtained values
• finally, there’s macro evaluation. Macros provide a way to change the evaluation rule for a particular form. If `oper` names a macro, its code is substituted instead of our expression and then evaluated. Macros are a major topic in Lisp, and they are used to build a large part of the language, as well as provide an accessible way, for the users, to extend it. However, they are orthogonal to the subject of this book and won’t be discussed in further detail here. You can delve deeper into macros in such books as On Lisp or Let Over Lambda

It’s important to note that, in Lisp, there’s no distinction between statements and expressions, no special keywords, no operator precedence rules, and other similar arbitrary stuff you can stumble upon in other languages. Everything is uniform; everything is an expression in a sense that it will be evaluated and return some value.

A Code Example

To sum up, let’s consider an example of the evaluation of a Lisp form. The following one implements the famous binary search algorithm (that we’ll discuss in more detail in one of the following chapters):

``````(when (> (length vec) 0)
(let ((beg 0)
(end (length vec)))
(do ()
((= beg end))
(let ((mid (floor (+ beg end) 2)))
(if (> (? vec mid) val)
(:= beg (1+ mid))
(:= end mid))))
(values beg
(? vec beg)
(= (? vec beg) val))))
``````

It is a compound form. In it, the so-called top-level form is `when`, which is a macro for a one-clause conditional expression: an `if` with only the true-branch. First, it evaluates the expression `(> (length vec) 0)`, which is an ordinary function for a logical operator `>` applied to two args: the result of obtaining the `length` of the contents of the variable `vec` and a constant `0`. If the evaluation returns true, i.e. the length of `vec` is greater than `0`, the rest of the form is evaluated in the same manner. The result of the evaluation, if nothing exceptional happens, is either false (which is called `nil`, in Lisp) or 3 values returned from the last form `(values ...)`. `?` is the generic access operator, which abstracts over different ways to query data structures by key. In this case, it retrieves the item from `vec` at the index of the second argument. Below we’ll talk about other operators shown here.

But first I need to say a few words abut `RUTILS`. It is a 3rd-party library that provides a number of extensions to the standard Lisp syntax and its basic operators. The reason for its existence is that Lisp standard is not going to change ever, and, as eveything in this world, it has its flaws. Besides, our understanding of what’s elegant and efficient code evolves over time. The great advantage of the Lisp standard, however, which counteracts the issue of its immutability, is that its authors had put into it multiple ways to modify and evolve the language at almost all levels starting from even the basic syntax. And this addresses our ultimate need, after all: we’re not so interested in changing the standard as we’re in changing the language. So, `RUTILS` is one of the ways of evolving Lisp and its purpose is to make programming in it more accessible without compromising the principles of the language. So, in this book, I will use some basic extensions from `RUTILS` and will explain them as needed. Surely, using 3rd-party tools is the question of preference and taste and might not be approved by some of the Lisp old-times, but no worries, in your code, you’ll be able to easily swap them for your favorite alternatives.

The REPL

Lisp programs are supposed to be run not only in a one-off fashion of simple scripts, but also as live systems that operate over long periods of time experiencing change not only of their data but also code. This general way of interaction with a program is called Read-Eval-Print-Loop (REPL), which literally means that the Lisp compiler `read`s a form, `eval`uates it with the aforementioned rule, `print`s the results back to the user, and `loop`s over.

REPL is the default way to interact with a Lisp program, and it is very similar to the Unix shell. When you run your Lisp (for example, by entering `sbcl` at the shell) you’ll drop into the REPL. We’ll preceede all REPL-based code interactions in the book with a REPL prompt (`CL-USER>` or similar). Here’s an example one:

``````CL-USER> (print "Hello world")
"Hello world"
"Hello world"
``````

A curious reader may be asking why `"Hello world"` is printed twice. It’s a proof that everything is an expression in Lisp. :) The `print` “statement”, unlike in most other languages, not only prints its argument to the console (or other output stream), but also returns it as is. This comes very handy when debugging, as you can wrap almost any form in a `print` not changing the flow of the program.

Obviously, if the interaction is not necessary, just the read-eval part may remain. But, what’s more important, Lisp provides a way to customize every stage of the process:

• at the `read` stage special syntax (“syntax sugar”) may be introduced via a mechanism called reader macros
• ordinary macros are a way to customize the `eval` stage
• the `print` stage is conceptually the simplest one, and there’s also a standard way to customize object printing via the Common Lisp Object System’s (CLOS) `print-object` function
• and the `loop` stage can be replaced by any desired program logic

Basic Expressions

The structural programming paradigm states that all programs can be expressed in terms of 3 basic constructs: sequential execution, branching, and looping. Let’s see how these operators are expressed in Lisp.

Sequential Execution

The simplest program flow is sequential execution. In all imperative languages, it is what is assumed to happen if you put several forms in a row and evaluate the resulting code block. Like this:

``````CL-USER> (print "hello") (+ 2 2)
"hello"
4
``````

The value returned by the last expression is returned as the value of the whole sequence.

Here, the REPL-interaction forms an implicit unit of sequential code. However, there are many cases when we need to explicitly delimit such units. This can be done with the `block` operator:

``````CL-USER> (block test
(print "hello")
(+ 2 2))
"hello"
4
``````

Such block has a name (in this example: `test`). This allows to prematurely end its execution by using an operator `return-from`:

``````CL-USER> (block test
(return-from test 0)
(print "hello")
(+ 2 2))
0
``````

A shorthand `return` is used to exit from blocks with a `nil` name (which are implicit in most of the looping constructs we’ll see further):

``````CL-USER> (block nil
(return 0)
(print "hello")
(+ 2 2))
0
``````

Finally, if we don’t even plan to ever prematurely return from a block, we can use the `progn` operator that doesn’t require a name:

``````CL-USER> (progn
(print "hello")
(+ 2 2))
"hello"
4
``````

Branching

Conditional expressions calculate the value of their first form and, depending on it, execute one of several alternative code paths. The basic conditional expression is `if`:

``````CL-USER> (if nil
(print "hello")
(print "world"))
"world"
"world"
``````

As we’ve seen, `nil` is used to represent logical falsity, in Lisp. All other values are considered logically true, including the symbol `T` or `t` which directly has the meaning of truth.

And when we need to do several things at once, in one of the conditional branches, it’s one of the cases when we need to use `progn` or `block`:

``````CL-USER> (if (+ 2 2)
(progn
(print "hello")
4)
(print "world"))
"hello"
4
``````

However, often we don’t need both branches of the expressions, i.e. we don’t care what will happen if our condition doesn’t hold (or holds). This is such a common case that there are special expressions for it in Lisp — `when` and `unless`:

``````CL-USER> (when (+ 2 2)
(print "hello")
4)
"world"
4
CL-USER> (unless (+ 2 2)
(print "hello")
4)
NIL
``````

As you see, it’s also handy because you don’t have to explicitly wrap the sequential forms in a `progn`.

One other standard conditional expression is `cond`, which is used when we want to evaluate several conditions in a row:

``````CL-USER> (cond
((typep 4 'string)
(print "hello"))
((> 4 2)
(print "world")
nil)
(t
(print "can't get here")))
"world"
NIL
``````

The `t` case is a catch-all that will trigger if none of the previous conditions worked (as its condition is always true). The above code is equivalent to the following:

``````(if (typep 4 'string)
(print "hello")
(if (> 4 2)
(progn
(print "world")
nil)
(print "can't get here")))
``````

There are many more conditional expressions in Lisp, and it’s very easy to define your own with macros (it’s actually, how `when`, `unless`, and `cond` are defined), and when there arises a need to use a special one, we’ll discuss its implementation.

Looping

Like with branching, Lisp has a rich set of looping constructs, and it’s also easy to define new ones when necessary. This approach is different from the mainstream languages, that usually have a small number of such statements and, sometimes, provide an extension mechanism via polymorphism. And it’s even considered to be a virtue justified by the idea that it’s less confusing for the beginners. It makes sense to a degree. Still, in Lisp, both generic and custom approaches manage to coexist and complement each other. Yet, the tradition of defining custom control constructs is very strong. Why? One justification for this is the parallel to human languages: indeed, `when` and `unless`, as well as `dotimes` and `loop` are either directly words from the human language or are derived from natural language expressions. Our mother tongues are not so primitive and dry. The other reason is because you can™. I.e. it’s so much easier to define custom syntactic extensions in Lisp than in other languages that sometimes it’s just impossible to resist. :) And in many use cases they make the code much more simple and clear.

Anyway, for a complete beginner, actually, you have to know the same number of iteration constructs as in any other language. The simplest one is `dotimes` that iterates the counter variable a given number of times (from 0 to `(- times 1)`) and executes the body on each iteration. It is analogous to `for (int i = 0; i < times; i++)` loops found in C-like languages.

``````CL-USER> (dotimes (i 3)
(print i))
0
1
2
NIL
``````

The return value is `nil` by default, although it may be specified in the loop header.

The most versatile (and low-level) looping construct, on the other hand, is `do`:

``````CL-USER> (do ((i 0 (1+ i))
((> i 1) i)
(print (pair i prompt))
(terpri))
foo

(0 "foo")
bar

(1 "bar")

2
``````

`do` iterates a number of variables (zero or more) that are defined in the first part (here, `i` and `prompt`) until the termination condition in the second part is satisfied (here, `(> i 1)`), and as with `dotimes` (and other do-style macros) executes its body — rest of the forms (here, `print` and `terpri`, which is a shorthand for printing a newline). `read-line` reads from standard input until newline is encountered and `1+` returns the current value of `i` increased by 1.

All do-style macros (and there’s quite a number of them, both built-in and provided from external libraries: `dolist`, `dotree`, `do-register-groups`, `dolines` etc.) have an optional return value. In `do` it follows the termination condition, here — just return the final value of `i`.

Besides do-style iteration, there’s also a substantially different beast in CL ecosystem — the infamous `loop` macro. It is very versatile, although somewhat unlispy in terms of syntax and with a few surprising behaviors. But elaborating on it is beyond the scope of this book, especially since there’s an excellent introduction to `loop` in Peter Seibel’s "LOOP for Black Belts".

Many languages provide a generic looping construct that is able to iterate an arbitrary sequence, a generator and other similar-behaving things — usually, some variant of `foreach`. We’ll return to such constructs after speaking about sequences in more detail.

And there’s also an alternative iteration philosophy: the functional one, which is based on higher-order functions (`map`, `reduce` and similar) — we’ll cover it in more detail in the following chapters, also.

Procedures and Variables

We have covered the 3 pillars of structural programming, but one essential, in fact, the most essential, construct still remains — variables and procedures.

What if I told you that you can perform the same computation many times, but changing some parameters… OK, OK, pathetic joke. So, procedures are the simplest way to reuse computations, and procedures accept arguments, which allows to pass values into their bodies. A procedure, in Lisp, is called `lambda`. You can define one like this: `(lambda (x y) (+ x y))`. When used, such procedure — also often called a function, although it’s quite different from what we consider a mathematical function — and, in this case, it’s called an anonymous function as it doesn’t have any name — will produce the sum of its inputs:

``````CL-USER> ((lambda (x y) (+ x y)) 2 2)
4
``````

It is quite cumbersome to refer to procedures by their full code signature, and an obvious solution is to assign names to them. A common way to do that in Lisp is via the `defun` macro:

``````CL-USER> (defun add2 (x y) (+ x y))
4
``````

The arguments of a procedure are examples of variables. Variables are used to name memory cells whose contents are used more than once and may be changed in the process. They serve different purposes:

• to pass data into procedures
• as temporary placeholders for some varying data in code blocks (like loop counters)
• as a way to store computation results for further reuse
• to define program configuration parameters (like the OS environment variables, which can also be thought of as arguments to the main function of our program)
• to refer to global objects that should be accessible from anywhere in the program (like `*standard-output*` stream)
• and more

Can we live without variables? Theoretically, well, maybe. At least, there’s the so-called point-free style of programming that strongly discourages the use of variables. But, as they say, don’t try this at home (at least, until you know perfectly well what you’re doing :) Can we replace variables with constants, or single-assignment variables, i.e. variables that can’t change over time? Such approach is promoted by the so called purely functional languages. To a certain degree, yes. But, from the point of view of algorithms development, it makes life a lot harder by complicating many optimizations if not totally outruling them.

So, how to define variables in Lisp? You’ve already seen some of the variants: procedural arguments and `let`-bindings. Such variables are called local or lexical, in Lisp parlance. That’s because they are only accessible locally throughout the execution of the code block, in which they are defined. `let` is a general way to introduce such local variables, which is `lambda` in disguise (a thin layer of syntax sugar over it):

``````CL-USER> (let ((x 2))
(+ x x))
4
CL-USER> ((lambda (x) (+ x x))
2)
4
``````

While with `lambda` you can create a procedure in one place, possibly, assign it to a variable (that’s what, in essence, `defun` does), and then apply many times in various places, with `let` you define a procedure and immediately call it, leaving no way to store it and re-apply again afterwards. That’s even more anonymous than an anonymous function! Also, it requires no overhead, from the compiler. But the mechanism is the same.

Creating variables via `let` is called binding, because they are immediately assigned (bound with) values. It is possible to bind several variables at once:

``````CL-USER> (let ((x 2)
(y 2))
(+ x y))
4
``````

However, often we want to define a row of variables with next ones using the previous ones’ values. It is cumbersome to do with `let`, because you need nesting (as procedural arguments are assigned independently):

``````(let ((len (length list)))
(let ((mid (floor len 2)))
(let ((left-part (subseq list 0 mid))
(right-part (subseq list mid)))
...)))
``````

To simplify this use case, there’s `let*`:

``````(let* ((len (length list))
(mid (floor len 2))
(left-part (subseq list 0 mid))
(right-part (subseq list mid)))
...)
``````

However, there are many other ways to define variables: bind multiple values at once; perform the so called “destructuring” binding when the contents of a data structure (usually, a list) are assigned to several variables, first element to the first variable, second to the second, and so on; access the slots of a certain structure etc. For such use cases, there’s `with` binding from RUTILS, which works like `let*` with extra powers. Here’s a very simple example:

``````(with ((len (length list))
(mid rem (floor len 2))
;; this group produces a list of 2 sublists
;; that are bound to left-part and right-part
;; and ; character starts a comment in lisp
((left-part right-part) (group mid list)))
...
``````

In the code throughout this book, you’ll only see these two binding constructs: `let` for trivial and parallel bindings and `with` for all the rest.

As we said, variables may not only be defined, or they’d be called “constants”, instead, but also modified. To alter the variable’s value we’ll use `:=` from RUTILS (it is an abbreviation of the standard `psetf` macro):

``````CL-USER> (let ((x 2))
(print (+ x x))
(:= x 4)
(+ x x))
4
8
``````

Modification, generally, is a dangerous construct as it can create unexpected action-at-a-distance effects, when changing the value of a variable in one place of the code effects the execution of a different part that uses the same variable. This, however, can’t happen with lexical variables: each `let` creates its own scope that shields the previous values from modification (just like passing arguments to a procedure call and modifying them within the call doesn’t alter those values, in the calling code):

``````CL-USER> (let ((x 2))
(print (+ x x))
(let ((x 4))
(print (+ x x)))
(print (+ x x)))
4
8
4
``````

Obviously, when you have two `let`s in different places using the same variable name they don’t affect each other and these two variables are, actually, totally distinct.

Yet, sometimes it is useful to modify a variable in one place and see the effect in another. The variables, which have such behavior, are called global or dynamic (and also special, in Lisp jargon). They have several important purposes. One is defining important configuration parameters that need to be accessible anywhere. The other is referencing general-purpose singleton objects like the standard streams or the state of the random number generator. Yet another is pointing to some context that can be altered in certain places subject to the needs of a particular procedure (for instance, the `*package*` global variable determines in what package we operate — `CL-USER` in all previous examples). More advanced uses for global variables also exist. The common way to define a global variable is with `defparameter`, which specifies its initial value:

``````(defparameter *connection* nil
"A default connection object.")  ; this is a docstring describing the variable
``````

Global variables, in Lisp, usually have so-called “earmuffs” around their names to remind the user of what they are dealing with. Due to their action-at-a-distance feature, it is not the safest programming language feature, and even a “global variables considered harmful” mantra exists. Lisp is, however, not one of those squeamish languages, and it finds many uses for special variables. By the way, they are called “special” due to a special feature, which greatly broadens the possibilities for their sane usage: if bound in `let` they act as lexical variables, i.e. the previous value is preserved and restored upon leaving the body of a `let`:

``````CL-USER> (defparameter *temp* 1)
*TEMP*
CL-USER> (print *temp*)
1
CL-USER> (progn
(let ((*temp* 2))
(print *temp*)
(:= *temp* 4)
(print *temp*))
*temp*)
2
4
1
``````

Procedures in Lisp are first-class objects. This means the one you can assign to a variable, as well as inspect and redefine at run-time, and, consequently, do many other useful things with. The RUTILS function `call`[1] will call a procedure passed to it as an argument:

``````CL-USER> (call 'add2 2 2)
4
CL-USER> (let ((add2 (lambda (x y) (+ x y))))
4
``````

In fact, defining a function with `defun` also creates a global variable, although in the function namespace. Functions, types, classes — all of these objects are usually defined as global. Though, for functions there’s a way to define them locally with `flet`:

``````CL-USER> (foo 1)
;; ERROR: The function COMMON-LISP-USER::FOO is undefined.
CL-USER> (flet ((foo (x) (1+ x)))
(foo 1))
2
CL-USER> (foo 1)
;; ERROR: The function COMMON-LISP-USER::FOO is undefined.
``````

Finally, there’s one more syntax we need to know: how to put comments in the code. Only losers don’t comment their code, and comments will be used extensively, throughout this book, to explain some parts of the code examples, inside of them. Comments, in Lisp, start with a `;` character and end at the end of a line. So, the following snippet is a comment: `; this is a comment`. There’s also a common style of commenting, when short comments that follow the current line of code start with a single `;`, longer comments for a certain code block precede it, occupy the whole line or a number of lines and start with `;;`, comments for code section that include several Lisp top-level forms (global definitions) start with `;;;` and also occupy whole lines. Besides, each global definition can have a special comment-like string, called the “docstring”, that is intended to describe its purpose and usage, and that can be queried programmatically. To put it all together, this is how different comments may look like:

``````;;; Some code section

(defun this ()
"This has a curious docstring."
...)

(defun that ()
...
;; this is an interesting block don't you find?
(block interesting
(print "hello")))  ; it prints hello
``````

Getting Started

I strongly encourage you to play around with the code presented in the following chapters of the book. Try to improve it, find issues with it, and come up with fixes, measure and trace everything. This will not only help you master some Lisp, but also understand much deeper the descriptions of the discussed algorithms and data structures, their pitfalls and corner cases. Doing that is, in fact, quite easy. All you need is install some Lisp (preferrably, SBCL or CCL), add Quicklisp, and, with its help, RUTILS.

As I said above, the usual way to work with Lisp is interacting with its REPL. Running the REPL is fairly straightforward. On my Mint Linux I’d run the following commands:

``````\$ apt-get install sbcl rlwrap
...
\$ rlwrap sbcl
...
* (print "hello world")

"hello world"
"hello world"
*
``````

`*` is the Lisp raw prompt. It’s, basically, the same as `CL-USER>` prompt you’ll see in SLIME. You can also run a Lisp script file: `sbcl --script hello.lisp`. If it contains just a single `(print "hello world")` line we’ll see the “hello world” phrase printed to the console.

This is a working, but not the most convenient setup. A much more advanced environment is SLIME that works inside Emacs (a similar project for vim is called SLIMV). There exists a number of other solutions: some Lisp implementations provide and IDE, some IDEs and editors provide integration.

After getting into the REPL, you’ll have to issue the following commands:

``````* (ql:quickload :rutilsx)
* (use-package :rutilsx)
``````

Well, that’s enough Lisp you’ll need to know, to start. We’ll get acquainted with other Lisp concepts as they will become needed for the next chapters of this book. Yet, you’re all set to read and write Lisp programs. They may seem unfamiliar, at first, but as you overcome the initial bump and get used to their paranthesised prefix surface syntax, I promise that you’ll be able to recognize and appreciate their clarity and conciseness.

So, as they say in Lisp land, happy hacking!

Footnotes:

[1] `call` is the RUTILS abbreviation of the standard `funcall`. It was surely fun to be able to call a function from a variable back in the 60’s, but now it has become so much more common that there’s no need for the prefix ;)

2019-07-22

"Programming Algorithms" Book

Drago — a nice example of a real-world binary tree

This was the first post about my book on algorithms and Lisp. Writing it, actually, started several years ago, but as I experience a constant shortage of quality time to devote to such side activities, short periods of writing alternated with long pauses. Now, I'm, finally, at the stage when I can start publishing it. But I intend to do that, first, gradually in this blog and then put the final version — hopefully, improved and polished thanks to the comments of the first readers — on Leanpub. The book will be freely available with a CC BY-NC-ND license.

Here is a snippet from the introduction chapter. A more elaborate description of the book may be found on its website.

Why Algorithms Matter

In our industry, currently, there seems to prevail a certain misunderstanding of the importance of algorithms for the working programmer. There's often a disconnect between the algorithmic questions posed at the job interviews and the everyday essence of the same job. That's why opinions are voiced that you, actually, don't have to know CS to be successful in the software developer's job. That's true, you don't, but you'd better do if you want to be in the notorious top 10% programmers. For several reasons. One is that, actually, you can find room for algorithms almost at every corner of your work — provided you are aware of their existence. To put it simply, the fact that you don't know a more efficient or elegant solution to a particular programming problem doesn't make your code less crappy. The current trend in software development is that, although the hardware becomes more performant, the software becomes slower faster. There are two reasons for that, in my humble opinion:

1. Most of the application programmers don't know the inner workings of the underlying platforms. And the number of platform layers keeps increasing.
2. Most of the programmers also don't know enough algorithms and algorithmic development technics to squeeze the most from their code. And often this means a loss of one or more orders of magnitude of performance.

In the book, I'll address, primarily, the second issue but will also try to touch on the first whenever possible.

Besides, learning the art of solving difficult algorithmic problems trains the brain and makes it more apt to solving various other problems, in the course of your day-to-day work.

Finally, you will be speaking the same lingua franca as other advanced programmers — the tongue that transcends the mundane differences of particular programming languages. And you'll gain a more detached view of those differences, freeing your mind from the dictate of a particular set of choices exhibiting in any one of them.

One of the reasons for this gap of understanding of the value of algorithms, probably, originates from how they are usually presented in the computer science curriculum. First, it is often done in a rather theoretical or "mathematical" way with rigorous proofs and lack of connection to the real world™. Second, the audience is usually freshmen or sophomores who don't have a lot of practical programming experience and thus can't appreciate and relate how this knowledge may be applied to their own programming challenges (because they didn't have those yet) — rather, most of them are still at the level of struggling to learn well their first programming language and, in their understanding of computing, are very much tied to its choices and idiosyncrasies.

In this book, the emphasis is made on the demonstration of the use of the described data structures and algorithms in various areas of computer programming. Moreover, I anticipate that the self-selected audience will comprise programmers with some experience in the field. This makes a significant difference in the set of topics that are relevant and how they can be conveyed. Another thing that helps a lot is when the programmer has a good command of more than one programming language, especially, if the languages are from different paradigms: static and dynamic, object-oriented and functional. These factors allow bridging the gap between "theoretical" algorithms and practical coding, making the topic accessible, interesting, and inspiring.

This is one answer to a possible question: why write another book on algorithms? Indeed, there are several good textbooks and online courses on the topic, of which I'd recommend the most Steven Skienna's The Algorithm Design Manual. Yet, as I said, this book is not at all academic in presentation of the material, which is a norm for other textbooks. Except for simple arithmetic, it contains almost no "math" or proofs. And, although proper attention is devoted to algorithm complexity, it doesn't deal with theories of complexity or computation and similar scientific topics. Besides, all the algorithms and data structures come with some example practical use cases. Last, but not least, there's no book on algorithms in Lisp, and, in my opinion, it's a great topic to introduce the language. The next chapter will provide a crash course to grasp the basic ideas, and then we'll discuss various Lisp programming approaches alongside the algorithms they will be used to implement.

This is an introductory book, not a bible of algorithms. It will draw a comprehensive picture and cover all topics necessary for further advancement of your algorithms knowledge. However, it won't go too deep into the advanced topics, such as persistent or probabilistic data structures, advanced tree, graph, and optimization algorithms, as well as algorithms for particular fields, such as Machine Learning, Cryptography or Computational Geometry. All of those fields require (and usually have) separate books of their own.