Control Flow in Python and Lisp

Let's look at control flow in Python and in Lisp. By control flow we understand the order in which statements and expressions are executed. In imperative programming, control flow is explicit while in declarative programming and logic programming it is implicit.

Sequencing

In Python statements are executed one after another.

def foo(n):
    x = n + 1
    y = x + 2
    z = 3 + 4

In Lisp the most common sequencing operator is progn. It evaluates each of its arguments in turn and then returns the value(s) of the last one.

(progn (+ 3 4)
       (+ 5 6)
       (+ 7 8))

At high optimization settings a Lisp compiler might notice that the first two subexpressions are superfluous and remove them. However there are some cases where subexpressions have side-effects.

(progn (print (+ 3 4))
       (print (+ 5 6))
       (+ 7 8))

Many forms have an implicit progn, for example defun

(defun foo (n)
  (+ 3 n)
  (+ 5 n)
  (+ 7 n))

As well as progn, there are prog1 and prog2 which return the value of their first and second subexpression, respectively.

Conditionals

if

In Python conditional branching is done with the if statement

from math import sqrt

if x < 0:
    return sqrt(-x)
else:
    return sqrt(x)

  Cell In[2], line 4
    return sqrt(-x)
    ^
SyntaxError: 'return' outside function

Python also has a one-legged if

if x < 0:
    print("x is negative")

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[3], line 1
----> 1 if x < 0:
      2     print("x is negative")

NameError: name 'x' is not defined

In Lisp if is not a statement but an expression: it returns a value

(+ 3 (if (< x 0)
         (sqrt (- x))
         (sqrt x)))

If can be used in a one-legged way in Lisp but it is not recommended. For that purpose there is when. For the other leg there is unless

(if (< x 0)
    (print "x is negative"))

(when (< x 0)
  (print "x is negative"))

(unless (>= x 0)
  (print "x is negative"))

cond

For multi-branch conditionals in Python we have to use of an explicit if … elif … elif … else construct. Here's a Python function that used to be familiar to AUC students.

def auc_grade(percentage):
    """Takes a percentage and returns a letter grade following the
    AUC grading criteria."""
    if percentage >= 90:
        return "A+"
    elif percentage >= 82.5:
        return "A"
    elif percentage >= 77.5:
        return "A-"
    elif percentage >= 72.5:
        return "B+"
    elif percentage >= 69:
        return "B"
    elif percentage >= 66.5:
        return "B-"
    elif percentage >= 63.5:
        return "C+"
    elif percentage >= 58.5:
        return "C"
    elif percentage >= 55:
        return "C-"
    elif percentage >= 53:
        return "D+"
    elif percentage >= 51:
        return "D"
    elif percentage >= 45:
        return "D-"
    else:
        return "F"

In Lisp we have the cond construct. Each clause consists of a test followed by a number of forms. If no test is triggered, then cond returns nil.

(defun auc-grade (p)
  (cond ((>= p 90 )  "A+")
        ((>= p 82.5) "A")
        ((>= p 77.5) "A-")
        ((>= p 72.5) "B+")
        ((>= p 69)   "B")
        ((>= p 66.5) "B-")
        ((>= p 63.5) "C+")
        ((>= p 58.5) "C")
        ((>= p 55)   "C-")
        ((>= p 53)   "D+")
        ((>= p 51)   "D")
        ((>= p 45)   "D-")
        (t           "F")))

If you macroexpand the cond form, you can see it expands into a "staircase" of if statements.

The forms following the test are wrapped in an implicit progn if there is more than one.

(defun auc-grade (p)
  (cond ((>= p 90 )  (print "Well done") "A+")
        ((>= p 82.5) "A")
        ((>= p 77.5) "A-")
        ((>= p 72.5) "B+")
        ((>= p 69)   "B")
        ((>= p 66.5) "B-")
        ((>= p 63.5) "C+")
        ((>= p 58.5) "C")
        ((>= p 55)   "C-")
        ((>= p 53)   "D+")
        ((>= p 51)   "D")
        ((>= p 45)   "D-")
        (t           (print "Ouch!") "F")))

case

Lisp also has a case statement. Here is an example adapted from CLHS.

(dolist (k '(1 2 3 :four #\v () t 'other))
  (format t "~6S ~6S~%" k
          (case k
            (1          'clause1)
            ((2 3)      'clause2)
            ((:four #\v) 'clause4)
            (nil         'no-keys-so-never-seen)
            ((nil)       'nilslot)
            ((t)         'tslot)
            (otherwise   'others))))

As well as case, there are ccase and ecase. They signal a correctable and a non-correctable error respectively if no normal clause matches. Again, an example from CLHS.

(defun decode (x)
  (ccase x
    ((i un) 1)
    ((ii dos) 2)
    ((iii tres) 3)
    ((iv cuatro) 4)))

(decode 'iiii)

Recursion and Iteration

Any general purpose programming language much facilitate repeating an operation on or for looping over structures or a sequence of values. Let's first look at Python.

Iteration in Python

Python's for statement is usually used to iterate over a structure, such as a list or set, or sequence of values, for example expressed as a range.

for x in [1, 2, 4]:
    print(x * x)

for x in {1, 2, 4}:
    print(x * x)

for x in range(1, 7, 2):
    print(x * x)

We can make further iterables using generator expressions.

squares = (x * x for x in range(4))

for s in squares:
    print(s)

More generally we can make generators using the yield statement.

def squares_from(n):
    yield n * n
    n += 1
    yield n * n
    n += 1
    yield n * n


for s in squares_from(5):
    print(s)

25
36
49

This allows us to go even further and make infinite generators. Note that we have to be careful how we iterate over such a generator.

def squares_from(n):
    while True:
        yield n * n
        n += 1


for s in squares_from(5):
    if s > 100:
        break
    print(s)

Pace such cases, we can say that usually Python's for statement is for iterating over structures when we know their size before starting the iteration. For this reason we call it structural iteration.

More generally, for full Turing completeness, we need a kind of iteration which is not merely structural but which depends on an arbitrary Boolean expression. In Python we use the while statement.

Here is an example of using a while loop for generatively finding a root of the function \(sin(1/x)\) using Newton's method.

from numpy import linspace, sin, cos
import matplotlib.pyplot as plt

plt.style.use("classic")


def f(x):
    return sin(1 / x)


def df(x):
    return -cos(1 / x) / x**2


def newton(x, epsilon = 1e-3):
    while abs(f(x)) > epsilon:
        x = x - f(x) / df(x)
        print(f"{x:12.4f} {f(x):012.10f}")
    return x


xs = linspace(0.01, 0.1, 100)
plt.plot(xs, f(xs))
plt.savefig("sineinv.png")
# plt.show()

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[9], line 1
----> 1 from numpy import linspace, sin, cos
      2 import matplotlib.pyplot as plt
      4 plt.style.use("classic")

ModuleNotFoundError: No module named 'numpy'

The important thing to note here is that we do not generally know in advance how many times we will loop through the while. We will usually have an argument about convergence and termination that gives us confidence that it will indeed stop and hopefully within a reasonable time.

Recursion in Python

Now how about recursion in Python. We can write recursive functions like this. It's not the most efficient way to add up the first n integers but bear with me.

def sum_n(n, acc=0):
    if n == 0:
        return acc
    else:
        return sum_n(n - 1, n + acc)

This works fine for "reasonable" values of n but it gets to a point where Python throws in the towel.

sum_n(1001)

Python has a limit to how deeply you may make recursive calls. By default it is 1000.

import sys

print(sys.getrecursionlimit())

We can set it to be a higher value but there is always going to be a limit. Python thinks that if you make that many recursive calls, you can't possible mean to do so. You must be in an infinite loop and Python should protect you from yourself.

So although you can do shallow recursion in Python, Python does not lend itself to this style of programming. It is at heart a language that prefers that you use iteration.

Recursion in Lisp

Now how about Lisp? Lisp does lend itself to recursion. It provides a welcoming environment for you to use recursion provided you do so with care.

(defun sum-n-acc (n &optional (acc 0))
  (declare (optimize (speed 3))
           (fixnum n acc))
  (if (zerop n)
      acc
      (sum-n-acc (1- n) (+ n acc))))

(defun sum-n (n)
  (if (zerop n)
      0
      (+ n (sum-n (1- n)))))

Here there is no recursion limit but we do have to encourage our Lisp compiler to compile this code efficiently. When we do so, the sbcl compiler performs Tail Call Optimization (TCO). This effectively eliminates the cost of the recursive function calls and makes recursion as efficient as iteration.

We can see this by using the tracer and by disassembling the compiled function.

Python does not perform TCO but

Most modern Common Lisp Implementations perform TCO but it didn't arrive to Python until 2025!

Recursion over lists and trees
How can you make a list? There are many ways but they all boil down to two. You can make an empty list with nil or () or you can cons something onto an existing list. Here are some examples. Let's consider lists of integers.
```
()
(cons 3 ())
(cons 4 '(5 6 7))
(cons 8 (cons 9 ()))
```
We say that the type list has two constructors nil and (). Corresponding to each constructor are accessors which access the values which had been given to the constructor. The nil constructor takes no values and as such has no accessors. The cons constructor takes two values, a number and a list of numbers and, as such, has two accessors known as first and rest or alternatively as car and cdr. First and rest can only be applied to a list that was made by cons. Applying them to nil will lead to an error.
```
(first (cons 3 ()))
(first (cons 4 '(5 6 7)))
(first (cons 8 (cons 9 ())))

(rest (cons 3 ()))
(rest (cons 4 '(5 6 7)))
(rest (cons 8 (cons 9 ())))
```
With that in mind, let's now write a recursive function that operates on a list of numbers. The function length exists already but let's write our own version.

We begin with a template
```
(defun my-length (ns)
  ...)
```
Now ns is a list of numbers so what can it be? It can be either nil or a cons. Let's distinguish.
```
(defun my-length (ns)
  (cond ((null ns) ...)
        ((consp ns) ...)))
```
If the list is null then the length must be zero.
```
(defun my-length (ns)
  (cond ((null ns) 0)
        ((consp ns) ...)))
```
If the list is a cons then we must be able to access its values.
```
(defun my-length (ns)
  (cond ((null ns) 0)
        ((consp ns)
         ... (first ns) ...
         ... (rest ns) ...)))
```
Now we remind ourselves what the types are of those two values. The value (first ns) must be a number. The value (rest ns) must be a list of numbers. Since it is a list of numbers it is something that we can give as input to my-length. Let's do that.
```
(defun my-length (ns)
  (cond ((null ns) 0)
        ((consp ns)
         (1+ (my-length (rest ns))))))
```
Now we ask ourselves what value does (my-length (rest ns)) return? We describe it in words: "It returns the length of the rest of the list ns." But if we know the length of the rest of the list, then the length of the list ns must be one more. We write that down.
```
(defun my-length (ns)
  (cond ((null ns) 0)
        ((consp ns) (+ 1 (my-length (rest ns)))))
```
Note that we have discarded the value (first ns). We don't need it.

Does it work? Try it out. Yes it does. It is a recursive function on lists.

Try for yourself to use this method to write these functions on lists of numbers:
1. Find the largest number in the list.
2. Find the sum of all numbers in the list.
3. Return the list with elements which are double those of the input list.
Now we turn our attention to binary trees. We haven't yet talked about data abstraction but let's have a look at how we can define new data structures in Lisp.
```
(deftype bt () '(or node null))

(defstruct node
  (value  nil :type fixnum)
  (left   nil :type bt)
  (right  nil :type bt))
```
This defines two things. It defines
- a binary tree to be either nil or a node
-a new data structure called node which has three slots. This defines for us one constructor, three accessors and one predicate.

Note also how the two definitions are mutually recursive; each of them refers to the other. This means that any function we write which takes a bt will need to refer to a node and vice versa.
```
(make-node :value 3)

(node-value (make-node :value 3))

(make-node :left (make-node :value 2)
           :value 3
           :right (make-node :value 4))

(node-left (make-node :left (make-node :value 2)
                      :value 3
                      :right (make-node :value 4)))

(node-value (node-left (make-node :left (make-node :value 2)
                                  :value 3
                                  :right (make-node :value 4))))

(node-p (make-node :left (make-node :value 2)
                   :value 3
                   :right (make-node :value 4)))
```
Let's write a recursive function which adds up all the numbers in a binary tree. We begin with a template.
```
(defun sum-bt (bt)
  ...)
```
What can bt be? We refer to our definition. It is either nil or a node. Let's distinguish.
```
(defun sum-bt (bt)
  (cond ((null bt) ...)
        ((node-p bt) ...)))
```
If bt is null then the sum must be zero.
```
(defun sum-bt (bt)
  (cond ((null bt) 0)
        ((node-p bt) ...)))
```
If bt is a node then we can access its values.
```
(defun sum-bt (bt)
  (cond ((null bt) 0)
        ((node-p bt)
         ... (node-left bt)...
         ... (node-value bt)...
         ... (node-right bt)...
         )))
```
The types of these values are binary tree, integer and binary tree. Since two of these values are binary tree, we can apply our function sum-bt to them.
```
(defun sum-bt (bt)
  (cond ((null bt) 0)
        ((node-p bt)
         ... (sum-bt (node-left bt))...
         ... (node-value bt)...
         ... (sum-bt (node-right bt))...
         )))
```
Now let's ask ourselves what the result is of (sum-bt (node-left bt))? It is the sum of all of the nodes in the left child of bt. We also have the sum of all of the nodes in the right child of bt. And (node-value bt) is the number at this node. If we add up those three values, we're done!
```
(defun sum-bt (bt)
  (cond ((null bt) 0)
        ((node-p bt)
         (+ (sum-bt (node-left bt))
            (node-value bt)
            (sum-bt (node-right bt))))))
```
A few years ago there was a discussion on Hacker News. Someone applied for a job at Google and one of the questions he was asked was to "invert a binary tree". He didn't even know what that was. There was outrage because it turned out that he had written a piece of open-source software that was apparently used by 90% of engineers at Google.

Whatever you may think of the discussion, if you apply the approach we sketch above you quickly get the function.
Recursion over s-expressions
An s-expression is any lisp expression that satisfies either atom or consp. In other words all atomic values and all values constructed by cons. An example of an s-expression is:
```
(1 2 3 (a b c) "def" 3.141592 ((((99)))))
```
1. Write some more examples of s-expressions.
2. Write a function sexp-p which determines whether a Lisp value is an s-expression.
3. Write a function which takes an s-expression and returns a list of all numbers occurring in it.

Iteration in Lisp

So how about iteration in Lisp? The Lisp language has a selection of operators but I recommend that you use one unified approach that is provided by a library. So let's use quicklisp to load it.

(ql:quickload :iterate)

(use-package :iterate)

The first of these loads the iterate library into your running Lisp image (first downloading it if necessary). The second gives us access to the exported functionality of the library.

Let's first look at a couple of uses which parallel Python's for statement.

(iter (for n in '(1 2 3 4))
      (print n))

1 2 3 4

You can collect values into a list.

(iter (for n in '(1 2 3 4))
      (collect (* n n)))

(1 4 9 16)

Or into a vector

(iter (for n in '(1 2 3 4))
      (collect (* n n) result-type 'vector))

#(1 4 9 16)

You can generate sequences of numbers in many ways.

(for i upfrom 0) => 0 1 2 ...
(for i from 5) => 5 6 7 ...    ; either from or upfrom is okay
(for i downfrom 0) => 0 -1 -2 ...
(for i from 1 to 3) => 1 2 3
(for i from 1 below 3) => 1 2
(for i from 1 to 3 by 2) => 1 3
(for i from 1 below 3 by 2) => 1
(for i from 5 downto 3) => 5 4 3

You can iterate over vectors.

(iter (for i in-vector #(2 3 4 5))
      (summing i))

Or over the lines (or chars or bytes) of a file.

(iter (for line in-file "lisp-control-flow.org" using #'read-line)
      (summing (length line)))

21968

(iter (for char in-file "lisp-control-flow.org" using #'read-char)
      (count char))

You can do mapping.

(iter (for x in '(1 2 3 4))
      (collect (* x x)))

(1 4 9 16)

You can do filtering and accumulation.

(iter (for i below 100)
      (when (evenp i)
        (sum i)))

2450

You can deconstruct values

(iter (for (a b c) in '((1 2 3) (4 5 6) (7 8 9) (10 11 12)))
      (when (evenp a)
        (sum b)))

And you can do complex combinations.

(let ((ns (iter (for i below 100)
                (collect (random 1000)))))
  (iter (for i in ns)
        (counting (evenp i) into evens)
        (counting (oddp i) into odds)
        (summing i into total)
        (maximizing i into max)
        (minimizing i into min)
        (finally (format t "Min: ~a~%Max: ~a~%Total: ~a~%Evens: ~a~%Odds: ~a~%"
                         min max total evens odds))))

Furthermore, iterate can be extended by adding new clauses. This example defines a specific reduction where the initial value gets divided in turn by each of the values in the list.

(defmacro dividing-by (num &key initial-value)
  `(reducing ,num by #'/ initial-value ,initial-value))

(iter (for i in '(5 5 2))
      (dividing-by i :initial-value 100))

Other iteration forms

In Lisp code you will also see dotimes and dolist for iterating over counting numbers and lists.

(dotimes (i 4) (print i))
(dolist (x '(do re me)) (print x))

0 1 2 3 DO RE ME NIL

There is also a more general form of iteration called do. Here is an example.

There are two variables to iterate over, x and y.
Each variable has an initialization expression: x has 100 and y has 0.
Each variable has an update expression: x gets decremented while y gets incremented.
There is an end test, in this case when y becomes greater than x.
There is a return expression, in this case a list containing x and=y=

(do ((x 100 (1- x))
     (y 0   (1+ y)))
    ((> y x) (list x y)))

(49 51)

Loop
Loop is a general looping facility to which an entire chapter in the Common Lisp HyperSpec is dedicated. Peter Seibel also dedicates the chapter LOOP for Black Belts to it in his book Practical Common Lisp. Here's an example from that chapter.
```
(loop for i from 1 to 100
      if (evenp i)
        minimize i into min-even and
      maximize i into max-even and
      unless (zerop (mod i 4))
        sum i into even-not-fours-total
      end
      and sum i into even-total
      else
        minimize i into min-odd and
      maximize i into max-odd and
      when (zerop (mod i 5))
        sum i into fives-total
      end
      and sum i into odd-total
      do (update-analysis min-even
                          max-even
                          min-odd
                          max-odd
                          even-total
                          odd-total
                          fives-total
                          even-not-fours-total))
```
As you can see, loop provides a mini-language for defining looping and iteration. However the mini-language is not at all lisp-like. In response to this Jonathan Amsterdam wrote the Iterate package which is similar to loop but does have a lisp-like mini-language, extends the Loop functionality in several ways and is (macro) extensible. He describes his motivation in Don't Loop, Iterate

Opinions vary on the pros and cons of using loop and iterate. Comparisons of the two can be found here and in Loop v Iterate. And while I'm not quite a knee-jerk anti-loopist, I am firmly in the iterate camp so we'll be using it throughout. Once you become familiar with iterate, you will find that you can readily read code you might find which contains loop expressions.

You can find some examples of using iterate (and indeed loop and others) in the chapter on iteration in the CL Cookbook.