Common Lisp, как работает трассировка при движении вниз - PullRequest
Новая
       21

Common Lisp, как работает трассировка при движении вниз

1 голос
/ 19 апреля 2020

Я не знаю, как объяснить это на topi c, поэтому сожалею о заголовке. 

(defun uniq (lst &optional ulst)
(if (endp lst)
    ulst
    (if (member (car lst) ulst)
        (uniq (cdr lst) ulst)
        (uniq (cdr lst) (append ulst (list (car lst))))
    )  
))

Процедура UNIQ берет список и удаляет все повторяющиеся элементы в списке, сохраняя только первое вхождение.

Когда я отслеживаю его, я получаю следующий результат: 

(UNIQ) * (uniq '(1 2 3 5 1 2 3 8 3))
  0: (UNIQ (1 2 3 5 1 2 3 8 3))
    1: (UNIQ (2 3 5 1 2 3 8 3) (1))
      2: (UNIQ (3 5 1 2 3 8 3) (1 2))
        3: (UNIQ (5 1 2 3 8 3) (1 2 3))
          4: (UNIQ (1 2 3 8 3) (1 2 3 5))
            5: (UNIQ (2 3 8 3) (1 2 3 5))
              6: (UNIQ (3 8 3) (1 2 3 5))
                7: (UNIQ (8 3) (1 2 3 5))
                  8: (UNIQ (3) (1 2 3 5 8))
                    9: (UNIQ NIL (1 2 3 5 8))
                    9: UNIQ returned (1 2 3 5 8)
                  8: UNIQ returned (1 2 3 5 8)
                7: UNIQ returned (1 2 3 5 8)
              6: UNIQ returned (1 2 3 5 8)
            5: UNIQ returned (1 2 3 5 8)
          4: UNIQ returned (1 2 3 5 8)
        3: UNIQ returned (1 2 3 5 8)
      2: UNIQ returned (1 2 3 5 8)
    1: UNIQ returned (1 2 3 5 8)
  0: UNIQ returned (1 2 3 5 8)
(1 2 3 5 8)

Я понимаю, что трассировка показывает мне процесс повторения, который я могу видеть результаты при переходе от 0 до 9. Однако то, что я не понимаю, это то, что происходит, когда оно идет вниз назад, что снова с 9 до 0. Когда я перешел с 0 на 9, программа, которую я дал, уже дала мне результат, я прав? Следовательно, какова цель спуска вниз, чем?

Ответы [ 2 ]

3 голосов
/ 19 апреля 2020

Следовательно, какова цель перехода вниз, чем?

Цель перехода вниз состоит в том, что все рекурсивные вызовы должны возвращаться.

Похоже, это не имеет смысла, потому что они возвращают одно и то же значение.

Мудрый человек однажды задал тот же вопрос, что и вы, и изобрел оптимизацию хвостовых вызовов, которая исключает все эти возвраты.

Напишите рекурсивную факториальную функцию (наиболее очевидным образом) и проследите, чтобы ; тогда вы увидите, что возвраты что-то делают: фактические составные умножения для вычисления факториала.

2 голосов
/ 20 апреля 2020

Просто добавлю к ответу Kaz: если вы попробуете это в реализации, которая имеет умеренно хороший компилятор, вы вполне можете найти это: 

> (trace uniq)
(uniq)

> (uniq '(1 2 3 5 1 2 3 8 3))
0 uniq > ...
  >> lst : (1 2 3 5 1 2 3 8 3)
0 uniq < ...
  << VALUE-0 : (1 2 3 5 8)
(1 2 3 5 8)

Мало того, что нет никаких раздражающих возвратов то же самое, рекурсивных вызовов нет вообще: все они оптимизированы для переходов.

Но если вы намеренно запрещаете компилятору делать что-то умное, добавив объявление notinline для uniq внутри его тела вы увидите все бесполезные звонки и возвраты.

...