Можно ли реализовать автокаррирование для языков семейства Lisp?

В Scheme можно каррировать функцию, используя процедуру curry:

(define (add x y)
  (+ x y))

(add 1 2)           ; non-curried procedure call
(curry add)         ; curried procedure, expects two arguments
((curry add) 1)     ; curried procedure, expects one argument
(((curry add) 1) 2) ; curried procedure call

Из документации Racket:

[curry] возвращает процедуру, которая является каррированной версией proc. Когда результирующая процедура применяется впервые, если ей не задано максимальное количество аргументов, которое она может принять, результатом является процедура, принимающая дополнительные аргументы.

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

(define-syntax define-curried
    (syntax-rules ()
      ((_ (f . a) body ...)
       (define f (curry (lambda a (begin body ...)))))))

Теперь будет каррировано следующее определение add:

(define-curried (add a b)
  (+ a b))

add
> #<procedure:curried>

(add 1)
> #<procedure:curried>

((add 1) 2)
> 3

(add 1 2)
> 3

Это возможно, но не просто, если вы хотите получить полезный результат.

• Если вам нужен язык, который всегда делает простое каррирование, то реализация проста. Вы просто конвертируете каждое приложение с более чем одним входом во вложенное приложение, и то же самое для функций с более чем одним аргументом. Благодаря языковым возможностям Racket это очень простое упражнение. (В других lisps вы можете получить аналогичный эффект с помощью некоторого макроса вокруг кода, где вы хотите его использовать.)

  (Между прочим, у меня есть язык поверх Racket, который делает именно это. Он получает всю привлекательность языков с автоматическим карри, но он не предназначен для практического использования.)

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

• Другой вариант — просто проверить каждое приложение. Другими словами, вы включаете каждый

  (f x y z)
  

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

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

(+ 1 2 3)

Как бы вы решили, следует ли называть это как есть или его следует перевести на ((+ 1 2) 3)? Кажется, здесь есть простой ответ, но как насчет этого? (переведите на свой любимый шепелявый диалект)

(define foo (lambda xs (lambda ys (list xs ys))))

В этом случае вы можете разделить (foo 1 2 3) несколькими способами. Еще одна проблема заключается в том, что вы делаете с чем-то вроде:

(list +)

Здесь у вас есть + в качестве выражения, но вы можете решить, что это то же самое, что применять его к нулевым входам, которые соответствуют арности +s, но тогда как написать выражение, которое оценивает функцию сложения? (Примечание: ML и Haskell «решают» это, не имея нулевых функций...)

Некоторые из этих проблем можно решить, решив, что каждое «настоящее» приложение должно иметь скобки для него, поэтому + сам по себе никогда не будет применяться. Но это теряет большую часть привлекательности языка с автоматическим каррированием, и у вас все еще есть проблемы, которые нужно решить...

Короткий ответ — да, хотя и не легко.

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

Как заметил Алекс В., в поваренной книге Common Lisp приводится пример "карри" функция для Common Lisp. Конкретный пример приведен ниже на этой странице:

(declaim (ftype (function (function &rest t) function) curry)
         (inline curry)) ;; optional
(defun curry (function &rest args)
  (lambda (&rest more-args)
    (apply function (append args more-args))))

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

(defun auto-curry (function num-args)
  (lambda (&rest args)
    (if (>= (length args) num-args)
        (apply function args)
        (auto-curry (apply (curry #'curry function) args)
                    (- num-args (length args))))))

Хотя вроде работает:

* (auto-curry #'+ 3)
#<CLOSURE (LAMBDA (&REST ARGS)) {1002F78EB9}>

* (funcall (auto-curry #'+ 3) 1)
#<CLOSURE (LAMBDA (&REST ARGS)) {1002F7A689}>

* (funcall (funcall (funcall (auto-curry #'+ 3) 1) 2) 5)
8

* (funcall (funcall (auto-curry #'+ 3) 3 4) 7)
14

Примитивная (не обрабатывает полные списки лямбда должным образом, только простые списки параметров) версия некоторого сахара синтаксиса макроса по сравнению с приведенным выше:

(defmacro defun-auto-curry (fn-name (&rest args) &body body)
  (let ((currying-args (gensym)))
    `(defun ,fn-name (&rest ,currying-args)
       (apply (auto-curry (lambda (,@args) ,@body)
                          ,(length args))
              ,currying-args))))

Кажется, работает, хотя необходимость funcall все еще раздражает:

* (defun-auto-curry auto-curry-+ (x y z)
    (+ x y z))
AUTO-CURRY-+

* (funcall (auto-curry-+ 1) 2 3)
6

* (auto-curry-+ 1)
#<CLOSURE (LAMBDA (&REST ARGS)) {1002B0DE29}>

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

Вы могли бы, например. перевести каждый вызов пользовательской функции (f a b c ... z) в (...(((f a) b) c)... z) и каждый вызов (define (f a b c ... z) ...) в (define f (lambda(a) (lambda(b) (lambda(c) (... (lambda(z) ...) ...))))) поверх схемы, чтобы иметь схему автоматического каррирования (это, конечно, запретило бы функции varargs).

Вам также нужно будет определить свои собственные примитивы, превратив функции varargs, например, например. (+) в двоичные файлы и переводят свои приложения на использование fold, например. (+ 1 2 3 4) ==> (fold (+) (list 1 2 3 4) 0) или что-то в этом роде - или, возможно, просто делает такие вызовы как (+ 1 2 3 4) незаконными в вашем новом языке, ожидая, что его пользователь сам напишет fold форм.

Вот что я имел в виду под "определением... семантики для вашего языка".

Загрузчик может быть таким же простым, как обернуть содержимое файла в вызов макроса, который вам затем придется реализовать в соответствии с вашим вопросом.

В Lisp уже есть функциональное каррирование:

* (defun adder (n)
    (lambda (x) (+ x n)))
ADDER

http://cl-cookbook.sourceforge.net/functions.html

Вот что я читал о макросах Lisp: https://web.archive.org/web/20060109115926/http://www.apl.jhu.edu/~hall/Lisp-Notes/Macros.html

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