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


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

sqrty(-4)

2.0

Python also has a one-legged if

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


foo(-3)

x is negative

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

(let ((x -4))
  (+ 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

(let ((x -3))
  (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 must 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()

<Figure size 640x480 with 1 Axes>

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. We call this kind of iteration generatice iteration.

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(3001)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[35], line 1
----> 1 sum_n(3001)

Cell In[34], line 5, in sum_n(n, acc)
      3     return acc
      4 else:
----> 5     return sum_n(n - 1, n + acc)

Cell In[34], line 5, in sum_n(n, acc)
      3     return acc
      4 else:
----> 5     return sum_n(n - 1, n + acc)

    [... skipping similar frames: sum_n at line 5 (2975 times)]

Cell In[34], line 5, in sum_n(n, acc)
      3     return acc
      4 else:
----> 5     return sum_n(n - 1, n + acc)

RecursionError: maximum recursion depth exceeded

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

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 and encourages you to do so.

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 (n)
  (if (zerop n)
      0
      (+ n (sum-n (1- n)))))

(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))))

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.

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

Recursion over lists, natural numbers and trees
- Lists
  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. It only makes senst to apply first and rest to a list that was made by cons. Applying them to nil just gives nil.
```
(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 ())))
```
  So when we ask ourselves what is a list? We say it's either
  - the empty list '() or nil. It satisfies null
```
(null '()) =>  T
(null nil) =>  T
(null t) =>  NIL
(null 1) =>  NIL
```
  - a list with something in it, thus made (directly or indirectly) using cons. It satisfies consp
```
(consp nil) =>  false
(consp (cons 1 2)) =>  true
(consp (list 1 2 3 4)) =>  true
```
    Note that a proper lisp is made with a number of occurrences of cons and terminated by nil
```
(list 1 2 3 4) ≡ (cons 1 (cons 2 (cons 3 (cons 4 nil))))
```
  An improper list (sometimes called a dotted list) is terminated by anything but nil.
```
(cons 1 2)) =>  (1 . 2)
```
  In this section we will work only with proper lists.
  
  With all of this 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)
  ...)
```
  Before we go any further, let us write down our expectations of how my-length should work. Later we will learn how to write structured unit tests but for now let's just write some Lisp expressions that we expect to be true.
```
(and (= 0 (my-length ()))
     (= 1 (my-length (list 9)))
     (= 2 (my-length (list 9 8)))
     (= 3 (my-length (list 9 8 7))))
```
  After we have prepared our definition of my-length, we can run the above expression and expect it to return true.
  
  Returning to our template, 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)
         ... (first ns) ...
         ... (my-length (rest ns)) ...)))
```
  Applying my-length to (rest ns) is such a natural thing to do, we call this the natural recursion.
  
  We ask ourselves what are they types of these expressions? ns is a list of numbers so (first ns) must be a number. And we expect my-length to return a number so (my-length (rest ns)) must be a number. But which number is it? It is the length of ns after taking one element away from it. So if we add 1 to it we get the length of ns, which is what we want!
```
(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. This makes sense since we don't actually care what is in the list, just how many things are there.
  
  Does it work? Try it out by evaluating our test expression. 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.
- Natural numbers
  These are the natural numbers (ℕ), also known as the counting numbers
```
0, 1, 2, 3, ...
```
  Similarly to lists, we could say that a natural number is either
  - 0, which satisfies zerop, or
```
(zerop 0) => t
(zerop 3) => nil
```
    - a positive number, which satisfies plusp
```
(plusp 0) => nil
(plusp 3) => t
```
  In fact the axiomatic basis for arithmetic on the natural numbers, called the Peano axioms, define the natural numbers in this way.
  - 0 is a natural number.
  - For every natural number n, its successor s(n) is a natural number.
  - There are no other natural numbers.
  If we have a number n and we are sure that it satisfies (plusp n) then we can take its predecessor (and be sure that the predecessor is a natural number).
```
(defvar n 3)

(plusp n) ; => t

(1- n) ; => 2
```
  Note that we cannot do this if n=0 since its predecessor is no longe a natural number.
  
  Let's define a function that takes a natural number n and sums all natural numbers up to and including n.
```
(defun sum-to (n)
  ...)
```
  As previously, let us write an expression that expresses our expectations about sum-to.
```
(defun test-sum-to ()
  (and (= 0 (sum-to 0))
       (= 1 (sum-to 1))
       (= 3 (sum-to 2))
       (= 6 (sum-to 3))))
```
  Now, returning to the template, what can n be? It can be either zero or positive. Let's distinguish.
```
(defun sum-to (n)
  (cond ((zerop n) ...)
        ((plusp n) ...)))
```
  If n is zero then we know that the result should be zero.
```
(defun sum-to (n)
  (cond ((zerop n) 0)
        ((plusp n) ...)))
```
  And if n is positive then we know that we can take its predecessor.
```
(defun sum-to (n)
  (cond ((zerop n) 0)
        ((plusp n) ... (1- n) ...)))
```
  Furthermore we know that the predecessor (1- n) is a natural number so it is something that we can give to the function sum-to
```
(defun sum-to (n)
  (cond ((zerop n) 0)
       ((plusp n) ... (sum-to (1- n)) ...)))
```
  Again, this is the natural recursion.
  
  What would the value of (sum-to (1- n)) be? Well it's just the sum of all natural numbers up to n-1. And if we know that then all we need to do is add n to it to get the result we want.
```
(defun sum-to (n)
  (cond ((zerop n) 0)
        ((plusp n) (+ n (sum-to (1- n))))))
```
  We check our test expression and see that it holds.
  
  Now use this method to write functions to
  1. Sum all the squares of numbers up to and including n
  2. Sum all odd numbers up to and including n. (You can use the function oddp)
  3. Common Lisp has the functions oddp and evenp but let's write our own. Call them myoddp and myevenp. The functions should depend on each other by calling on each other. This is called mutual recursion.
- Binary trees
  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. Just like we did with myoddp and myevenp.
  
  The defstruct statement actually defines five new functions for us!
  - A constructor function make-node
  - Three accessor functions node-value, node-left and node-right, one for each of the three slots of the structure
  - A predicate to recognise a node called node-p
```
(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)
  ...)
```
```
(and (= 0 (sum-bt ()))
     (= 3 (sum-bt (make-node :value 3)))
     (= 9 (sum-bt (make-node :left (make-node :value 2)
                             :value 3
                             :right (make-node :value 4)))))
```
  Returning to our template, 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. The structure has three accessors.
```
(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 use natural recursion and 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 can quickly define the function.
  
  Write the function invert-bt that takes a binary tree and returns the binary tree that is its mirror image through a vertical axis.
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))

You can collect values into a list.

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

Or into a vector

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

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 13 by 2) => 1 3 5 7 9 11 13
(for i from 1 below 13 by 2) => 1 3 5 7 9 11
(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 "control-flow.org" using #'read-line)
      (summing (length line)))

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

You can do mapping.

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

You can do filtering and accumulation.

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

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))

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.