Эквивалентны (let) и (лямбда) в Common Lisp
Я читаю «О Лиспе» Пола Грэма, пытаясь лучше понять функциональный стиль программирования. В главе 3 он упоминает, что функциональные программы «работают, возвращая значения», а не выполняя побочные эффекты. Я не совсем понимаю последствия этого утверждения для манипулирования и представления промежуточных результатов процедуры. Если функциональная программа возвращает значение, она фиксирует его, используя эквивалент использования(lambda)функция?
Вот пример, показывающий определение функции с использованием лямбда-функции для получения промежуточного результата. принимает список и число и подразделяет элементы списка наkгруппы по размеруn.
(defun group (src n acc)
(funcall
#'(lambda (back)
(cond
((consp back)
(group back n (cons (subseq src 0 n) acc)))
(t
(reverse (cons src acc)))))
(nthcdr n src)))
Последняя строка функции захватывает задний раздел списка, принимая . Затем этот результат передается в качестве аргумента лямбда-функции, которая решает, как обрабатыватьsrcобусловлено аргументом. Это чисто функциональный код и не имеет побочных эффектов. С другой стороны, я мог бы определить следующим образом:
(defun group (src n acc)
(let ((back (nthcdr n src)))
(cond ((consp back)
(group back n (cons (subseq src 0 n) acc)))
(t
(reverse (cons src acc))))))
где мы используем для первой привязки переменнойbackк(nthcdr n src). Я не уверен, насколько функциональна эта версия(group)это потому что(let)привязывает переменные к значениям императивным образом.
3 ответа
Что ж, следует учитывать, что это более синтаксически удобная форма конкретного использования .
Чтобы прояснить некоторые обозначения, в Common Lisp несколько форм эквивалентны.
- можно записать так: с тех пор
#'это макрос чтения. -
#'(lambda (...) ...)тогда можно записать как(lambda (...) ...), поскольку это макрос, расширение которого(function (lambda (...) ...)). - Окончательно
(funcall (lambda (...) ...) ...), что эквивалентно(funcall (function (lambda (...) ...) ...)сверху, можно записать как , как частный случай составной формы (см. 3.1.2.1.2.4).
Ничего из этого не требуется в Lisp-1, но в CL это необходимо.
Ниже я буду писать, а не коряво(funcall #'(lambda (...) ...) ...)Я думаю, что Грэм, вероятно, использует это.
Итак, теперь важный момент:
(let ((x ...) ...) ...)полностью эквивалентно
((lambda (x ...) ...) ...).
Хотя в CL это не реализовано таким образом (это специальный оператор), вы можете думать, что это макрос, определенный следующим образом. В частности, вот определение макроса под названиемallowчто-то вроде (конечно, вы не можете переопределить себя в 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 это не определено так, поскольку это специальный оператор, но это может быть , и могут быть соответствующие определения и так далее. Вот определение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 (...) ...)полностью эквивалентен . В частности, поскольку любая программа, включающая в себя, может быть тривиально переписана в программу, использующую только , и является чисто функциональной конструкцией, то она также является чисто функциональной конструкцией.
В практическом плане есть два различия.
Читабельность. Это важно. Программы — это не просто способ приказать машине что-то сделать: это способ сообщить о ваших намерениях другим людям . Почти всем (и я думаю, что, наверное, даже всем) легче читать код, который говорит на английском языке:
пусть x будет..., а теперь... вещи, связанные с x ...
Вместо того, что чрезвычайно сложно даже написать на естественном языке, но можно было бы
x будет иметь значение здесь и сейчас... вещи, связанные с x ..., и это значение...
И это еще хуже , если сравнивать
пусть х будет... и у будет..., а теперь...
с действительно ужасным
x и y будут иметь значения здесь, и сейчас..., вещи, связанные с x и y ..., и значения будут... и...
Это просто ужасный способ записи чего-либо: значения сильно отделены от связанных переменных, нет указания, какое значение принадлежит какой переменной, когда вы наконец их достигаете, и, наконец, существует последовательная зависимость, которую людям обычно труднее понять. разобрать.
Если бы вы встретили текст на естественном языке, написанный таким образом, вы бы его исправили, потому что это ужасно. Ну, вот что делает: превращает трудночитаемую форму в гораздо более понятную, где начальные значения находятся рядом с переменными.
Возможная историческая простота реализации. Возможно, я думаю, что когда-то компилятору было проще, если его рассматривали как особый случай, а не просто как макрос, который расширяется вlambdaформа. Я не уверен в этом, тем более, что я вполне уверен, что читал где-то, но сейчас не могу найти, что оно возникло как макрос, но это кажется правдоподобным как причина того, чтоletявляется специальным оператором в CL. Конечно, мне трудно представить, что компилятор не мог увидеть((lambda (...) ...) ...)и скомпилировать эту форму каким-то оптимальным способом (т.е. вообще не компилировать функцию), даже очень давно, когда компиляторы были сделаны из грязи и гусиного жира.
Я думаю, сегодня можно смело игнорировать эту вторую причину.
Много пунктов, чтобы ответить на ваши вопросы:
Первый,
В информатике говорят, что операция, функция или выражение имеют побочный эффект, если они изменяют некоторые значения переменных состояния за пределами локальной среды — Википедия.
Таким образом, наличие локальных переменных для обработки входных данных не означает, что вы не занимаетесь функциональным программированием. Что важно, так это детерминированный характер разрабатываемых вами функций: для любого набора входных данных функции всегда должны возвращать один и тот же результат, соответствующий входным данным.
Когда вы хотите исключить любое использование локального состояния, вы пытаетесь выполнить чисто функциональное программирование :
Чисто функциональное программирование — подмножество функционального программирования, в котором все функции рассматриваются как детерминированные математические функции или чистые функции. Когда чистая функция вызывается с некоторыми заданными аргументами, она всегда будет возвращать один и тот же результат, и на нее не могут повлиять какие-либо изменяемые состояния или другие побочные эффекты. --
Здесь важно знать, почему вы хотите заниматься функциональным программированием:
Сторонники чисто функционального программирования утверждают, что, ограничивая побочные эффекты, программы могут иметь меньше ошибок, их легче отлаживать и тестировать, а также они больше подходят для формальной проверки. -- .
Я бы также добавил такие важные вещи, как отложенное вычисление и сокращение графиков (что должно привести к автоматической оптимизации):
Отложенная оценка не оценивает аргументы функции, если только их значения не требуются для оценки самого вызова функции.
Обычная стратегия реализации ленивых вычислений в функциональных языках — сокращение графа . Отложенное вычисление используется по умолчанию в нескольких чисто функциональных языках, включая Miranda, Clean и Haskell. -- ВикипедияВикипедияВикипедия
Common Lisp может выполнять ленивые вычисления, но с использованием такой структуры, как CLAZY.
При функциональном программировании параллелизм упрощается , поскольку эта парадигма позволяет избежать изменяемого состояния.
Возвращаясь к вашему случаю, обаgroupреализация использует локальные переменные (аргумент вашей лямбды является локальной переменной, когда вы ее вызываете). Оба используют хвостовую рекурсию, что хорошо и устраняет зависимость от емкости стека вызовов.
Проблема в том, что локальная переменная в обеих реализациях неявно зависит от ограничений системы, с которой они работают, потому чтоbackможет быть весьма большим.
Если вы заранее знаете максимальный размер вводимых данных и что они могут полностью храниться в памяти, то использовать эти реализации не составит труда. Но если ваши входные данные представляют собой несколько эксабайт данных, вам лучше использовать потоки и генераторы и уменьшить локальное состояние до целого числа (количества элементов в текущей группе, которую вы создаете) вместо того, чтобы хранить целые последовательности и подпоследовательности. Таким образом, вы можете распределить нагрузку и обеспечить параллелизм благодаря функциональному программированию.
Я бы сказал, что это во многом личный вкус. Поскольку сам по себе в основном так или иначе реализуется . аргументы являются локальными переменными, как и одна из них.
(let ((a 1))
a)
;; is equivalent to:
((lambda (a)
a)
1)
Я думаю, это станет довольно интересно, если вы воспользуетесьlet*, поскольку теперь можно последовательно использовать сохраненные и переименованные промежуточные значения. Вложенные лямбды, напротив, были бы очень громоздкими и трудными для понимания. Потому что, как вы видите, входные данные для лямбды приходят в самом конце вызова лямбды...
Мне особенно нравится использовать его при изменении переменной или переменных, используя процедуру или цикл.
(let ((result '()))
(loop for i in '(1 3 7 11)
do (setf result (cons i result)))
result)
;;=> (11 7 3 1)
Конечно, этот случай — очень глупый пример (и его можно было бы выразить гораздо более кратко, не используя ), но процедура, которая используется дляsetfЭто может быть гораздо сложнее.
Этот глупый пример можно было бы выразить как рекурсивный вызов хвоста (я буду использовать его для обозначения ):
(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)
Я думаю, что это менее многословно и полезно, особенно когда у вас есть несколько таких переменных, которые будут изменены.
Вероятно, когда переменная, содержащая результаты, должна быть заметной, лучше использовать выражение, а если процедура должна быть более выделенной и допускающей повторное использование, тогда следует использовать или , что дает процедуре имя.
Но, конечно, вы могли бы обернутьlambda/defunвокругletвыражение, дающее процедуре имя...