Возможно ли реализовать автоматическое каррирование на Lisp -семейных языках?

Ответ 1

В схеме можно выполнить функцию с помощью процедуры 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

Ответ 2

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

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

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

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

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

  (f x y z)
  

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

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

(+ 1 2 3)

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

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

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

(list +)

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

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

Ответ 3

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

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

Ответ 4

Lisp уже имеет функциональное Currying:

* (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

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

Ответ 5

Как отметил Алекс W, общая Lisp Поваренная книга дает пример функции "curry" для 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}>

Ответ 6

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

Вы можете, например, перевести каждый вызов функции пользователя (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) ...) ...))))) поверх Схемы, чтобы иметь схему автоматического currying (что, конечно, запрещает функции varargs).

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

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

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