Повышаем уровень - 2. Работа с отладчиком

Перевод. Оригинал здесь

"Остерегайтесь ошибок в приведённом мной коде. Я только доказал, что он правильный, но не пробовал его запускать." (Дональд Кнут)

Это 13-я (и последняя) статья из цикла Введение в PicoLisp.

В этой статье будет рассмотрена работа со встроенным отладчиком PicoLisp. В PicoLisp есть два основных способа отлаживать функцию: трассировка и пошаговое выполнение.

• Трассировка означает, что в лог выводится информация каждый раз, когда происходит определённое событие. Например, вызов функции или выход из неё.
• Пошаговое выполнение - более тщательный способ отладки. Выполнение программы останавливается в определённой точке, и может быть продолжено шаг за шагом, чтобы вы могли контролировать каждое действие, которое производит функция.
• Наконец, есть ещё возможность писать тесты с помощью функции test.

Давайте начнём наши упражнения с отладки простой функции вычисления факториала. Она возвращает факториал числа (обычно обозначаемый восклицательным знаком !), например: 5! = 5*4*3*2*1. В абстрактной форме факториал выглядит так: N! = N * (N-1) * (N-2) * ... * (N-(N-1)).

Есть несколько способов реализовать функцию вычисления факториала. Мы выберем рекурсивный вариант. Рекурсивный означает, что функция во время выполнения вызывает сама себя. Посмотрите на пример ниже:

(de fact (N)
   (if (=0 N)
      1
      (* N (fact (dec N))) ) )

Отлаживать код, который вы не понимаете - трудная задача. Давайте посмотрим, что делает наша функция.

Как видите, она принимает целое число, N. Если число равно нулю, то функция возвращает 1. Иначе она возвращает * N (fact (dec N). (fact N-1) вновь вызывает нашу функцию вычисления факториала: (N-1) * (fact N-2). То есть каждый раз функция вызывается с числом, меньшим на единицу, пока не дойдёт до нуля.

Когда функция доходит до 0, она возвращает 1. Единица передается в функцию (fact 2), и так далее.

Получается, сначала функция вызывается со всеми аргументами от N до 0, а затем происходит вычисление в обратном порядке - от 0 до N. Давайте убедимся в этом с помощою отладчика.

Давайте сохраним нашу функцию в файл "factorial.l", и затем загрузим его в REPL:

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

Убедимся, что она работает:

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

Теперь давайте начнём трассировку функции fact:

: (trace 'fact)
-> fact

Примечание: в качестве альтернативы, вы можете сразу же начать трассировку функции fact, выполнив в терминале команду pil "factorial.l" -"trace 'fact" +.

Если мы вызовем функцию fact снова, то trace покажет нам все этапы выполнения функции:

: (fact 3)
 fact : 3
  fact : 2
   fact : 1
    fact : 0
    fact = 1
   fact = 1
  fact = 2
 fact = 6
-> 6

Отступы помогают нам понять, на каком уровне вызывается функция и значение какого уровня вызова возвращается. Сначала мы видим конструкцию вида <function name>{=html} : ``<argument>{=html}, затем вида <function name>{=html} = ``<return value>{=html}. Как говорилось выше, сначала функция вызывается с постепенно уменьшающимися значениями N, а затем начинает возвращать значения в обратном порядке.

Для того, чтобы остановить трассировку функции, используйте команду untrace:

: (untrace 'fact)
-> fact

Безусловно, можно подвергать трассировке и вложенные функции. Давайте вместо функции fact подвергнем трассировке функцию умножения, *:

: (trace '*)
-> *

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

Как говорилось, умножение вызывается только N раз, для всех случаев, кода N > 0.

Пошаговое выполнение означает, что функция останавливается и её выполнение продолжается шаг за шагом. Мы можем начать отладку функции командой debug 'fun:

: (load "factorial.l")
-> fact
: (debug 'fact)
-> fact

Примечание: Так же, как и с трассировкой, вы можете начать отладку с помощью команды в терминале: pil "factorial.l" -"debug 'fact" +.

Давайте сначала взглянем на код функции, которую собираемся отлаживать. Используем для этого встроенную функцию pp, "красивной печати":

: (pp 'fact)
(de fact (N)
   (! if
      (=0 N)
      1
      (* N (fact (dec N))) ) )

На второй строке вы видите восклицательный знак после скобки. Это символ точки останова (breakpoint). По умолчанию такая точка останова вставляется в каждое выражение верхнего уровня отлаживаемой функции. В нашем случае такое выражение одно - функция if.

С включённым режимом отладки мы можем:

• Продолжить выполнение до следующей точки останова, нажав ENTER.
• Проверить значение переменных, введя имя их символа.
• Рекурсивно входить в подвыражения, выполняя команду (d).
• Можем вычислить значение текущего выражения с помощью команды (e).

Давайте попробуем. Как говорилось, отладчик остановится на первой строке функции:

: (fact 3)     
(if (=0 N) 1 (* N (fact (dec N))))
!

Давайте проверим, чему равно значение N:

! N
-> 3

Давайте вычислим функцию целиком на этом этапе:

! (e)
-> 6

Отладчик сообщает, что (fact 3) вычисляется в 6, что является правильным результатом. В отличие от функции trace, которая на данном этапе показала бы следующий вызов fact, мы можем сразу вычислить конечный результат того выражения, где сейчас находится точка останова.

Давайте перейдём в подвыражение командой (d) (она вернёт T в случае успеха). Затем нажмём ENTER, чтобы увидеть следующее выражение, которым должно быть (=0 N).

! (d)
-> T
(=0 N)
!

Мы предполагаем, что выражение (=0 N) вычислится в NIL, верно?

! (e)
-> NIL

Нажимая ENTER, мы будем переходить к следующим подвыражениям:

!                 # нажмите ENTER
(* N (fact (dec N)))
! (d)             # введите (d)
-> T
!                 # нажмите ENTER
(fact (dec N))
! (d)             # введите (d)
-> T
!                 # нажмите ENTER
(dec N)

Во что вычисляется выражение (dec N)?

! N  
-> 3
! (e)
-> 2

Всё верно, N у нас пока равно 3, поэтому (dec N) вычислится в 2.

Мы достигли точки, когда у нас стартует рекурсия: (fact 2). Если сейчас нажать ENTER, мы увидим, что отладчик вновь остановится на функции if с новым значением N, равным 2:

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

Вводя команду (d), мы добавляли новые точки останова. Теперь нет необходимости вводить эту команду заново - точки останова уже заданы, и мы можем поэтапно пройти по нашей функции, просто нажимая ENTER. Давайте дойдём до (dec N) и проверим, во что оно вычисляется:

!                 # нажмите ENTER
(=0 N)
!                 # нажмите ENTER
(* N (! fact (! dec N)))
!                 # нажмите ENTER
(fact (! dec N))
!                 # нажмите ENTER
(dec N)
! (e)
-> 1

Поскольку N на данном этапе равно 2, (dec N) вычисляется в 1. Отлично!

Чтобы остановить отладку, введите команду (unbug 'fact). Точки останова будут удалены из кода и функция будет выполняться без остановок:

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

: (fact 10)
-> 3628800

После того, как вы убедились, что функция работает как нужно, вы возможно захотите написать тесты. Для этого можно воспользоваться функцией test, которая принимает два аргумента: правильный результат и функцию, которую нужно протестировать.

Давайте добавим в конец нашей программы, вычисляющей факториал, строку (test (fact 3)). Теперь, если мы попробуем выполнить программу командой pil factorial.l, она выдаст ошибку:

((fact 3))
[factorial.l:8] 5 -- 'test' failed
?

Если же мы напишем (test 6 (fact 3)), то программа выполнится без ошибок.

Функцию test можно использовать также для проверки пограничных случаев. Например, функция факрориала не должна работать с отрицательными числами, факториал 0 должен быть равен 1, также она должна работать с большими числами.

Давайте добавим несколько тестов:

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

Если мы теперь попытаемся выполнить программу, она завершится с ошибкой сегментирования. Почему? Потому что она не работает с отрицательными числами. Почему же она с ними не работает? Потому что условие выхода никогда не выполняется - от отрицательного числа отнимается единица за единицей и N стремится к минус-бесконечности.

Спасибо нашим тестам за то, что мы выявили эту ошибку. Давайте изменим нашу функцию так, чтобы она выдавала NIL при отрицательных N. Мы могли бы окружить главный цикл условием (if (ge0 N) ...), но это выглядит некрасиво и, кроме того, условие будет проверяться на каждом вызове функции. Давайте попробуем найти решение лучше.

Этот раздел не связан напрямую с темой статьи, но раз мы всё равно изучаем PicoLisp, почему бы не обогатить наши знания ещё парочкой новых функций? PicoLisp позволяет определять анонимные рекурсивные функции "на лету", с помощью функций recurse / recur. Давайте взглянем на документацию:

(recur fun) -> any
(recurse ..) -> any
Реализуют анонимную рекурсию, определяя функцию recurse "на лету". Во время выполнения функции fun симпол recurse связывается с определением функции fun.

Не слишком понятное объяснение. Посмотрите, как выглядит наша функция с использованием recur/recurse:

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

Мы заменили de fact на recur, рекурсивный вызов fact - на recurse, обернув снаружи эту конструкцию в условие, которое требуется проверить однократно в начале работы функции. Теперь происходит рекурсивный вызов не всей функции fact, а только участка от recur до recurse - анонимной рекурсивной функции.

Не беспокойтесь, если сейчас вам принцип создания анонимной рекурсии не совсем понятен - мы вернёмся к нему более подробно в будущих статьях.

Теперь все тесты проходят успешно. Отличная работа!

Этой статьёй мы завершаем цикл Введение в PicoLisp. Примите наши поздравления, вы прошли довольно длинный путь!

Полный исходный текст функции факториала вы можете скачать по ссылке.