Являются ли (let) и (лямбда) эквивалентными в Common Lisp

Что ж, способ рассматривать let состоит в том, что это более синтаксически удобная форма конкретного использования lambda.

Чтобы прояснить некоторые обозначения, в Common Lisp несколько форм эквивалентны.

• (function (lambda (...) ...)) можно записать как #'(lambda (...) ...), так как #' — это макрос чтения.
• Тогда #'(lambda (...) ...) можно записать как (lambda (...) ...), поскольку lambda — это макрос, расширение которого равно (function (lambda (...) ...)).
• Наконец, (funcall (lambda (...) ...) ...), который эквивалентен (funcall (function (lambda (...) ...) ...) выше, может быть записан как ((lambda (...) ...) ...), как частный случай составной формы (см. 3.1.2.1.2.4).

Ничего из этого не нужно в Lisp-1, но в CL это необходимо.

Ниже я напишу ((lambda (...) ...) ...), а не неуклюжее (funcall #'(lambda (...) ...) ...), которое, как мне кажется, использует Грэм.

Итак, теперь важный момент:

(let ((x ...) ...) ...) полностью эквивалентен ((lambda (x ...) ...) ...).

Хотя в CL это не реализовано таким образом (let — это специальный оператор), вы можете думать о let, как если бы это был макрос, определенный в терминах lambda вот так. В частности, вот определение макроса allow, похожего на let (конечно, вы не можете переопределить let в CL, отсюда и такое название):

(defmacro allow (bindings &body decls/forms)
  `((lambda ,(mapcan (lambda (b)
                       (typecase b
                         (null '())     ;elide ()'s in binding list as special caee
                         (symbol (list b))
                         (cons
                          (unless (eql 2 (list-length b))
                            (error "mutant binding ~S" b))
                          (list (first b)))
                         (t
                          (error "what even is ~S" b))))
                     bindings)
      ,@decls/forms)
    ,@(mapcan (lambda (b)
                (typecase b
                  (null '())
                  (symbol (list 'nil))
                  (cons (list (second b)))
                  (t (error "what even is ~S" b))))
              bindings)))

А теперь, например, с помощью трассировщика макрорасширений:

> (allow ((x 1) (y 2)) (+ x y))
(allow ((x 1) (y 2)) (+ x y))
 -> ((lambda (x y) (+ x y)) 1 2)
3

Как я уже сказал, в CL let так не определяется, так как это специальный оператор, но может быть, и могут быть соответствующие определения let* и так далее. Вот определение allow*, которое есть let*:

(defmacro allow* (bindings &body decls/forms)
  (if (null (rest bindings))
      `(allow ,bindings ,@decls/forms)
    `(allow (,(first bindings))
       (allow* ,(rest bindings) ,@decls/forms))))

(И в этот момент я смеюсь над людьми, которые говорят «макросы с рекурсивным раскрытием баааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааааа с макросами".)

Так что с точки зрения семантики языка вообще никакой разницы нет: (let (...) ...) полностью эквивалентно ((lambda (...) ...) ...). В частности, поскольку любая программа, включающая let, может быть тривиально переписана в программу, использующую только lambda, а lambda является чисто функциональной конструкцией, то let также является чисто функциональной конструкцией.

Тогда есть два различия в практическом плане.

Читаемость. Это важно. Программы — это не просто способ заставить машину что-то сделать: это способ сообщить о ваших намерениях другим людям. Почти для всех (и я думаю, наверное, для всех) легче читать код, который говорит на английском языке

пусть x будет ..., а теперь ... вещи, связанные с x ...

Вместо чего-то, что чрезвычайно сложно даже написать на естественном языке, но может быть

х будет иметь значение здесь и сейчас... вещи, связанные с х..., и значение равно...

И это еще хуже, если сравнивать

пусть х будет... и у будет..., а теперь...

с действительно ужасным

х и у будут иметь значения здесь и сейчас..., вещи, связанные с х и у..., а значения... и...

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

Если бы вы встретили текст на естественном языке, написанный таким образом, вы бы его поправили, потому что это ужасно. Что ж, let именно это и делает: превращает трудночитаемую lambda форму в гораздо более понятную, где начальные значения находятся рядом с переменными.

Возможна историческая простота реализации. Возможно, я думаю, что когда-то компилятору было проще, если let рассматривался как частный случай, а не как просто макрос, который расширяется в форму lambda. Я не уверен в этом, тем более, что я почти уверен, что читал где-то, но сейчас не могу найти, что let возник как макрос, но это кажется правдоподобным в качестве причины того, что let является специальным оператором в CL. Конечно, мне трудно представить, что компилятор не мог увидеть ((lambda (...) ...) ...) и скомпилировать эту форму каким-то оптимальным образом (т.е. вообще не скомпилировать функцию), даже очень давно, когда компиляторы были сделаны из грязи и гусиный жир.

Я думаю, что сегодня безопасно игнорировать эту вторую причину.

Много моментов, чтобы ответить на ваши вопросы:

Первый,

В информатике говорят, что операция, функция или выражение иметь побочный эффект, если он изменяет некоторые значения переменной состояния вне его местная среда -- Википедия

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

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

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

Здесь важно знать, почему вы хотите заниматься функциональным программированием:

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

Я бы также добавил важные вещи, такие как ленивая оценка и сокращение графа (что должно привести к автоматической оптимизации):

Ленивая оценка не оценивает аргументы функции, если только их значения необходимы для оценки самого вызова функции.

Обычная стратегия реализации ленивых вычислений в функциональных языки — графовое сокращение. Ленивая оценка используется по умолчанию на нескольких чистых функциональных языках, включая Miranda, Clean и Хаскелл. -- Википедия

Common Lisp может выполнять ленивые вычисления, но с использованием такой структуры, как CLAZY.

С функциональным программированием параллелизм легко, потому что эта парадигма избегает изменяемого состояния.

Итак, чтобы вернуться к вашему случаю, обе реализации group используют локальные переменные (аргумент вашей лямбды является локальной переменной, когда вы ее вызываете). Оба используют хвостовую рекурсию, что хорошо и устраняет зависимость от емкости стека вызовов.

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

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

Я бы сказал, что это очень личный вкус. Поскольку сам let в большинстве случаев реализуется lambda. lambda аргументы являются локальными переменными, как и let.

(let ((a 1))
  a)

;; is equivalent to:
((lambda (a) 
   a)
 1)
 

Я думаю, что это становится довольно интересным, если вы используете let*, так как теперь вы можете последовательно использовать сохраненные и переименованные промежуточные значения. Напротив, вложенные лямбды были бы очень громоздкими и трудными для понимания. Потому что, как вы видите, ввод для лямбды происходит в самом конце лямбда-вызова...

Мне нравится использовать let особенно при изменении переменной или переменных используя setf над процедурой или циклом.

(let ((result '()))
  (loop for i in '(1 3 7 11)
        do (setf result (cons i result)))
  result)
;;=> (11 7 3 1)

Конечно, этот случай — очень глупый пример (и его можно было бы выразить намного короче без использования let), но процедура, используемая для setfing, может быть намного сложнее.

Этот глупый пример можно было бы выразить как lambda - tail-call рекурсивно (я буду использовать defun для имени lambda):

(defun myfun (lst &optional (acc '()))
  (cond ((null lst) acc)
        (t (myfun (cdr lst) (cons (car lst) acc)))))

(myfun '(1 3 7 11))
;;=> (11 7 3 1)

Я думаю, что let менее многословен и полезен, особенно когда у вас есть несколько таких переменных, которые будут мутировать.

Вероятно, когда переменная, содержащая результаты, должна быть заметной, лучше использовать выражение let, в то время как если процедура должна быть более подчеркнута - и ее можно использовать повторно - тогда следует использовать lambda или defun, что дает процедуре имя.

Но, конечно, вы можете обернуть выражение lambda/defun вокруг выражения let, чтобы дать процедуре имя...