Levelling up - 2: Use the debugger
Tags: picolisp, lisp, functional, debugger
Published: 2021-11-09 09:20:43

Welcome back to the last post of our "PicoLisp for Beginners" series!

Today we will cover how to use the built-in PicoLisp debugger. There are two major ways to debug a function: by **tracing** and by **single stepping**.

- Tracing means that we receive a **log entry** for each program's execution, for example when a function gets called or exits.

- **Single stepping**  is more granular than tracing. The execution is stopped at specific **breakpoints** and can be continued step by step, in order track closely what the function is doing.

- Finally, we can also write **tests** using the ``test`` function.

--------------------------------------------

### Example function: The recursive factorial function

Let's start with a simple example function: the **factorial function**. It returns the factorial of a number (usually expressed by ``!``), for example: ``5! = 5*4*3*2*1``. In abstract terms: ``N! = N * (N-1) * (N-2) * ... * (N-(N-1))``

There are [several ways](https://www.rosettacode.org/wiki/Factorial#PicoLisp) to implement this function, we choose the recursive one here. "Recursive" means that the function calls *itself* within in the function. Let's have a look:

```
(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )
```
<br>

**A little code analysis to warm up** <br>

It's hard to debug a function you don't understand. So let's concentrate and look at the code.

As you can see, the function takes an integer number ``N``. If ``N`` equals zero, the function returns ``1``. Otherwise, it returns ``N * (fact N-1)``. ``(fact N-1)`` again calls ``(N-1) * (fact N-2)``, and so on, until all factors are covered.

After the function has been called ``N+1``-times, we can return a value for the first time:  At ``(fact 0)``, the function returns ``1``. This value can be fed into ``(fact 1)``: the last line evaluates to ``1 * 1``. This value goes into ``(fact 2)`` and so on.

So basically, we once traverse the whole function down from ``N`` to ``0``, and then again up from ``0`` to ``N``. Or at least that's what we expect - let's see if we can confirm this in the debugger.

--------------------------------------------

### Tracing 

Let's save our factorial function to a script called "factorial.l" and load it into the REPL:

```
: (load "factorial.l")
-> fact
```

Let's confirm that it works:

```
: (fact 3)
-> 6
: (fact 8)
-> 40320
```

Now let's start **tracing** it using the ``trace`` function:

```
: (trace 'fact)
-> fact
```
*Note: Alternatively, you can also start the tracing mode for a script by typing ``pil "factorial.l" -"trace 'fact" +``.*

If we call it now again, ``trace`` will display the whole execution tree of ``fact``.

```
: (fact 3)
 fact : 3
  fact : 2
   fact : 1
    fact : 0
    fact = 1
   fact = 1
  fact = 2
 fact = 6
-> 6
```
The indentation level helps us to understand  at which level the function gets called, and at which level the value is returned. First we can see the call ``<function name> : <argument>``, later on we see the return value ``<function name> = <return value>``. As expected, we first call ``fact`` with decreasing values of ``N`` until we reach zero, and then we start to return the value from bottom up.


If you want to **stop** tracing a function, use ``untrace``:

```
: (untrace 'fact)
-> fact
```

-------------------------------------

Of course, it is also possible to trace functions within functions. Let's trace the multiplication function ``*`` instead:

```
: (trace '*)
-> *

: (fact 3)
 * : 1 1
 * = 1
 * : 2 1
 * = 2
 * : 3 2
 * = 6
-> 6
```

As expected, the multiplication is only executed ``N`` times - for each level where a value for ``N>0`` is returned.



--------------------------------------------

### Single-stepping

Single-stepping means that a function is stopped and executed step by step.  We can start the debugger by ``debug 'fun``:

```
: (load "factorial.l")
-> fact
: (debug 'fact)
-> fact
```
*Note: Just like for the tracing example, you can also start the debugging mode for a script by typing ``pil "factorial.l" -"debug 'fact" +``.*

As first step, let's have a look at the function that we want to debug. We can show the source code using the "pretty-print" ``pp`` function:

```
: (pp 'fact)
(de fact (N)
   (! if
      (=0 N)
      1
      (* N (fact (dec N))) ) )
```
As you can see, there is an **exclamation mark** in the second line. This is the symbol for the **breakpoint**. Per default, a breakpoint is inserted into each top-level expression per function (in case of our ``fact``-function, there is only one top-level function, which is the ``if``).

Now we have four possibilities:
- We can continue with the **next expression** if we press ``ENTER``
- We can inspect the **variables** by typing their symbol name
- We can recursively **step into** the subexpressions by ``(d)``
- We can **evaluate** an expression using ``(e)``.

Let's try. As expected, the debugger stops at the first line of the program.

```
: (fact 3)     
(if (=0 N) 1 (* N (fact (dec N))))
```
Let's inspect the value of ``N``:
```
! N
-> 3
```
Let's evaluate the whole expression:

```
! (e)
-> 6
```
The debugger reveals that ``(fact 3)`` is 6, which is correct. You can see that unlike the tracing function, the interpreter has already executed the script already once, therefore the final result is available.

Let's step into the subfunctions by ``(d)`` (it returns ``T`` if it was successful). Then let's press ``Enter`` to see the next expression, which should be ``(=0 N)``.
```
! (d)
-> T
(=0 N)
!
```
We expect ``(=0 N)`` to be ``NIL``, right?

```
! (e)
-> NIL
```
Let's go to the next subexpression by ``Enter``, and go two steps further down.

```
!                 # press ENTER
(* N (fact (dec N)))
! (d)
-> T
!                 # press ENTER
(fact (dec N))
! (d)
-> T
!                 # press ENTER
(dec N)
```
What do you expect as result of ``(dec N)``?

```
! N  
-> 3
! (e)
-> 2
```
Correct - the value of ``N`` is ``3``, so ``(dec N)`` should be ``2``. 

Now we should have reached the point where the recursion starts with ``(fact 2)``. If we press ``Enter``, we see that indeed it stops again and displays the ``if``-expression, this time with ``N =2``:

```
 (if (! =0 N) 1 (! * N (! fact (! dec N))))
! N
-> 2
```

As we can see from the breakpoint symbol ``!``, it is not needed to repeat the ``(d)`` steps. We have automatically created **breakpoints** when we went through it the first time. Just pressing ``Enter`` is enough. So let's step throught it until we reach ``(dec N)`` again, and inspect its value.

```
!                 # press ENTER
(=0 N)
!                 # press ENTER
(* N (! fact (! dec N)))
!                 # press ENTER
(fact (! dec N))
!                 # press ENTER
(dec N)
! (e)
-> 1
```

Since ``N`` is ``2``, ``(dec N)`` evaluates to ``1``. Correct!

---------------------------

To **stop debugging** the function, type ``unbug 'fact``. The breakpoints (``!``) will then be removed from the source code, and the function executes without breakpoints:

```
: (pp 'fact)
(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )
-> fact

: (fact 10)
-> 3628800
```



--------------------------------------------

### Testing

After you made sure your function does what it's supposed to do, you should write **tests**. You can do this using the ``test`` function, which takes two arguments: the correct value, and the program to be tested.

### Testing the ``test`` function

Let's add a few lines to our factorial script, and add a **wrong** result on purpose, to see what happens.

```
(test 5 (fact 3))
```
As expected, the script throws an error after we called it with ``pil factorial.l``:

```
((fact 3))
[factorial.l:8] 5 -- 'test' failed
? 
```
If we call it with ``(test 6 (fact 3))``, it runs without problems.

### Testing edge cases

The test function can also be used to verify **edge cases**. For example, our factorial function should't be defined for **negative** numbers. Factorial of 0 should be 1. Also, it should work for rather large numbers.

So, let's add some tests.

```
(test NIL (fact -3)
(test 1 (fact 0))
(test 87178291200 (fact 14))
```

Unfortunately, when we run the script, the script crashes. Why? Because it doesn't work for **negative numbers**. And why not? Because the exit condition will never be met, and ``(fact N)`` is called again and again with decreasing numbers until negative infinity.

Thanks to our test, we have caught this error, so let's modify our script now to return ``NIL`` if ``N`` is negative. We could simply wrap a ``(if (ge0 N) ...`` around our function, but that would be rather unelegant, because it would check the if-condition **each single time** the function is recursed. Let's try to find a better way.

### Excursion: The anonymous ``recurse`` function

It's not exactly on-topic, but since we're here to become better at PicoLisp, let's take the chance to learn a new function. PicoLisp allows to define an anonymous recursive function "on the fly" by using the ``recurse / recur`` functions. Let's check the docs:

> ``(recur fun) -> any``  
> ``(recurse ..) -> any``  
> Implements anonymous recursion, by defining the function ``recurse`` on the fly. During the execution of ``fun``, the symbol ``recurse`` is bound to the function definition ``fun``.

In other words, instead of the ``de`` construct to name a function, you can use ``recur``. When you then call ``recurse`` within ``recur``, it will jump back to it. This is the final script:

```
(de fact (N)
   (when (ge0 N)
      (recur (N)
         (if (=0 N)
            1
            (* N (recurse (dec N))) ) ) ) )
```

*If you don't fully understand now, don't worry. We will get used to this kind of construct by time.*

Now all tests are passing. Well done!

--------------------------------------------

With this we are closing the beginner's tutorials for PicoLisp. Congratulations!

The final factorial script can be downloaded [here](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/beginners-tutorial/factorial.l).

--------------------------------------------

### Sources

- Photo by <a href="https://unsplash.com/@cadop?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Mathew Schwartz</a> on <a href="https://unsplash.com/s/photos/bug?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>     
- https://software-lab.de/doc/tut.html  
- https://www.rosettacode.org/wiki/Factorial#PicoLisp