Уменьшить или явную рекурсию?

Недавно я начал читать через Пола Грэма На Lisp с другом, и мы поняли, что у нас очень разные мнения о сокращении: я думаю, что он выражает определенную рекурсивную форму очень четко и кратко; он предпочитает явно выписывать рекурсию.

Я подозреваю, что мы в любом случае правы в некотором контексте и ошибаемся в другом, но мы не знаем, где находится эта строка. Когда вы выбираете одну форму над другой, и что вы думаете о ее выборе?

Чтобы быть понятным, что я подразумеваю под сокращением против явной рекурсии, здесь одна и та же функция реализована дважды:

(defun my-remove-if (pred lst)
    (fold (lambda (left right)
                  (if (funcall pred left) 
                      right 
                      (cons left right)))
          lst :from-end t))

(defun my-remove-if (pred lst)
    (if lst
        (if (funcall pred (car lst))
            (my-remove-if pred (cdr lst))
            (cons (car lst) (my-remove-if pred (cdr lst))))
        '()))

Я боюсь, что начал работу с Schemer (теперь мы Racketeers?), поэтому, пожалуйста, дайте мне знать, если я испортил синтаксис Common Lisp. Надеемся, что это будет ясно, даже если код неверен.

Ответ 1

Если у вас есть выбор, вы всегда должны выразить свое вычислительное намерение в самых абстрактных условиях. Это позволяет читателю понять ваши намерения, и это упрощает компилятор для оптимизации вашего кода. В вашем примере, когда компилятор тривиально знает, что вы делаете операцию сложения, поскольку вы его именовали, он также тривиально знает, что он может распараллелить операции листа. Компилятор будет намного сложнее понять, когда вы пишете операции с крайне низким уровнем.

Ответ 2

В Common Lisp предпочитаются функции более высокого порядка для обхода структуры данных, фильтрации и других связанных операций над рекурсией. Это также видно из многих предоставленных функций, таких как REDUCE, REMOVE-IF, MAP и других.

Рекурсия хвоста: a) не поддерживается стандартом; b) может быть вызвана по-разному с различными компиляторами CL; c) использование хвостовой рекурсии может иметь побочные эффекты для сгенерированного машинного кода для окружающего кода.

Часто для некоторых структур данных многие из этих выше операций выполняются с помощью LOOP или ITERATE и предоставляются как функция более высокого порядка. Существует тенденция предпочитать новые языковые расширения (например, LOOP и ITERATE) для итеративного кода с использованием рекурсии для итерации.

(defun my-remove-if (pred list)
   (loop for item in list
         unless (funcall pred item)
         collect item))

Вот также версия, которая использует функцию Common Lisp REDUCE:

(defun my-remove-if (pred list)
  (reduce (lambda (left right)
            (if (funcall pred left) 
                right 
              (cons left right)))
          list
          :from-end t
          :initial-value nil))

Ответ 3

Я возьму немного субъективный вопрос и даю очень субъективный ответ, поскольку Ира уже дала совершенно прагматичный и логичный ответ.: -)

Я знаю, что явное описание вещей явно ценится в некоторых кругах (ребята Python делают его частью своего "дзэн" ), но даже когда я писал Python, я его никогда не понимал. Я хочу писать на самом высоком уровне, все время. Когда я хочу явно писать вещи, я использую язык ассемблера. Точка использования компьютера (и HLL) заключается в том, чтобы заставить его сделать это для меня!

Для вашего примера my-remove-if, сокращение выглядит для меня отлично (кроме схемных измов вроде fold и lst:-)). Я знаком с концепцией сокращения, поэтому все, что мне нужно понять, это выяснить ваш f(x,y) -> z. Для явного варианта мне пришлось подумать об этом на секунду: я должен сам выяснить цикл. Рекурсия не самая сложная концепция, но я думаю, что это сложнее, чем "функция двух аргументов".

Мне также не нужна повторная целая строка - (my-remove-if pred (cdr lst)). Мне кажется, что мне нравится Lisp отчасти потому, что я абсолютно беспощаден в DRY, а Lisp позволяет мне быть сухим по осям, которого нет на других языках. (Вы можете добавить еще один LET вверху, чтобы избежать этого, но затем это более продолжительное и сложное, что, я думаю, является еще одной причиной, чтобы предпочесть сокращение, хотя на данный момент я могу просто рационализировать.)

Я думаю, что, возможно, контексты, в которых ребятам Python, по крайней мере, не понравилась неявная функциональность, были:

когда никто не может ожидать догадываться о поведении (например, frobnicate("hello, world", True) - что означает True?) или:
случаи, когда разумно изменить неявное поведение (например, когда аргумент True перемещается или удаляется или заменяется чем-то другим, поскольку в большинстве динамических языков нет ошибки времени компиляции)

Но reduce в Lisp терпит неудачу в обоих этих критериях: это хорошо понятная абстракция, которую все знают, и это не изменится, по крайней мере, ни на какой временной шкале, о которой я забочусь.

Теперь я абсолютно уверен, что есть некоторые случаи, когда мне было бы легче читать явный вызов функции, но я думаю, что вам нужно быть довольно творческим, чтобы придумать их. Я не могу думать ни о чем, потому что reduce и mapcar и друзья действительно хорошие абстракции.