Levelling up - 2: Use the debugger
Beware of bugs in the above code; I have only proved it correct, not tried it. (Donald Knuth)
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 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))) ) )
A little code analysis to warm up
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 functionrecurse
on the fly. During the execution offun
, the symbolrecurse
is bound to the function definitionfun
.
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.
Sources
Photo by Mathew Schwartz on Unsplash
software-lab.de/doc/tut.html
rosettacode.org/wiki/Factorial#PicoLisp