Одно из известных преимуществ Лиспа над другими языками программирования состоит в том, что в Лиспе проще, чем где бы то ни было, реализуются различные новые механизмы, появляющиеся в современных языках программирования. Причин тому несколько: это и гомоиконность Лиспа (единая форма представления программ и данных) и уникальная по своим возможностям система макро. В общем, Лисп не зря называют «программируемым языком программирования».
В этой небольшой заметке мы рассмотрим, как можно реализовать в Лиспе такие, весьма популярные ныне программные механизмы, как частичное применение и каррирование функций. При этом я буду использовать свою реализацию Homelisp (это чистый интерпретатор Лиспа с некоторыми дополнительными возможностями).
Вероятно, использование частичного применения в Common Lisp будет не очень простым (в связи с тем, что для вызова вычисляемого функционального объекта нужно использовать funcall/apply); в Scheme дело должно обстоять проще. В ближайшее время я планирую опубликовать новую версию HomeLisp, в котором для вызова вычисляемого функционального объекта не требуется funcall/apply. В тех случаях, когда поведение кода отличается, я буду это подчёркивать.
Частичное применение и каррирование — это строгие математические операции. Но мы рассмотрим их «на пальцах», без обращения к лямбда-исчислению и комбинаторной логике.
Частичное применение функции f — это получение из функции f новой функции f', которая уже приняла заданные аргументы, и готова принять остальные. Для чего нужно частичное применение? Например, для того, чтобы из функции можно было вернуть функциональное значение.
Рассмотрим частичное применение на простом примере. Пусть функция f задана формулой:
f(x,y,z)=x+y**2+z**3
тогда частичное применение этой функции с аргументами x=1 и y=2 должно породить функцию:
f'(z) = 1+4+z**3 = 5+z**3
В языке Хаскелл частичное применение ничего не стоит программисту:
Однако, в Лиспе такая попытка приведет к неудаче:
Конечно, в Лиспе существует механизм создания функций с любым числом аргументов (конструкция &rest); можно создать функцию, которая будет принимать два или три (или десять) параметров:
Но важно понимать разницу: эта функция обрабатывает все параметры и возвращает результат вычисления, тогда как частичное применение дает в результате новую функцию, которая «готова продолжить вычисления».
Посмотрим, как можно реализовать на Лиспе механизм частичного применения функции. И поможет нам в этом… да-да, аппарат анонимных функций (lambda). Некоторые программисты думают, что анонимные функции нужны только для экономии имен (мол, их место во всяких stream-map-filter-reduce для того, чтобы выполнить короткое действие над элементом последовательности). На самом же деле анонимные функции способны на гораздо большее, в чем мы сейчас и убедимся.
Начнем с того, что рассмотрим, как функция может вернуть другую функцию как результат. В Лиспе это очень просто:
Как видим, функция возвращает замыкание, в котором значение свободной переменной x зафиксировано (равно 5). Результат функции можно вызвать как функцию. Для этого в Common Lisp и HomeLisp (с редакцией ядра <= 13.53) придется использовать funcall:
Теперь понятно, как можно действовать, если мы хотим взять функцию f от n аргументов и одно значение x, а в результате получить функцию от (n-1) аргумента. Обозначим список формальных параметров нашей функции через plist. Тогда все, что нужно сделать, это построить вот такое лямбда-выражение:
Идея очень проста: мы строим лямбда-выражение, в теле которого просто вызываем исходную функцию на списке параметров, в котором голова заменена на значение х.
Значит, для частичного применения функции нужно на базе этой функции построить лямбда-выражение, у которого аргументов будет на единицу меньше, а аргумент, заданный при частичном применении, будет «учтен» во внутреннем вызове нашей функции в теле лямбда-выражения.
Как это реализовать? Несложно… В HomeLisp есть функция getd, которая обеспечивает доступ к определяющему выражению функции или макро:
Как видим, getd возвращает определяющее выражение функции, в котором «вместо» лямбда находится специальный атом EXPR. Мы можем взять список параметров нашей функции (второй элемент результата) и построить лямбда-выражение, параметрами которого будет хвост исходного списка параметров, а в теле лямбда-выражения мы вызовем исходную функцию с полным списком параметров.
Из приведенного кода легко понять, что plist — это исходный список функции f, которую мы хотим применить частично. rlist — исходный список без первого элемента, а clist — полный список параметров, в котором первый элемент заменен на значение x. Конкретно, для функции g, приведенной выше plist = (x y z), rlist=(y z), а clist=(a y z). Проверим теперь, как работает частичное применение:
Можно убедиться, что это именно то, что и планировалось: part-apply вернула новую функцию, с числом аргументов, на единицу меньшим. Если эту новую функцию вызвать с параметрами y и z, то результат будет в точности такой же, как и вызов исходной функции g с тремя аргументами: 111 y и z:
Ниже я (для краткости) не буду указывать funcall. В следующем ядре HomeLisp будет изменена схема вычисления функций — станет доступным «схемный» синтаксис.
Пойдем дальше. Теперь возникнет естественное желание повторно применить результат повторного применения. Это оказывается уже совсем простым делом — ведь результат частичного применения — это лямбда-выражение, а оно устроено почти идентично с результатом, который возвращает getd. Список параметров лямбда-выражения — это второй элемент списка. Все эти соображения позволяют построить окончательное решение поставленной задачи:
Здесь добавлен анализ первого параметра: если это атом, то он должен «представлять» функцию (типа EXPR); если первый параметр не является ни «правильным» атомом, ни лямбда-выражением, то возбуждается состояние ошибки. Код, разумеется, можно было бы еще подсократить, две почти идентичные ветви оставлены для наглядности. Посмотрим теперь, на что способна эта функция:
Теперь займемся каррированием. Каррированная функция, принимая недостаточное число аргументов, возвращает функцию, способную обработать остальные. Главное предназначение каррирования — это как раз обеспечение частичного применения. Мы зашли с другого конца: рассмотрим теперь, как можно реализовать каррирование, если имеется частичное применение.
Пусть дана функция g нескольких аргументов. Мы построим ее каррированный вариант под другим именем !g. Суть построения будет такой: функция !g будет примать неопределенное число аргументов. После вызова она должна проверить количество переданных аргументов. Если это количество равно количеству аргументов исходной функции g, то следует из передать на вход g. Если количество аргументов больше, чем способна принять g, то следует возбудить состояние ошибки. А вот если количество аргументов меньше, чем у функции g, то… да-да — нужно выполнить последовательное частичное применение. Результат этого применения вернуть.
В данном случае удобно использовать макро. Код с комментариями приведен ниже:
Здесь следует прокомментировать построение нового имени функции. Для этого используются функции HomeLisp explode, которая из атома строит список составляющих его символов, и implode, которая сжимает символы списка в один, порождая новый атом.
Проверим теперь наш макро в «деле»:
Каррирование у нас выполнено без дополнительного контроля. И мы не реализовали каррирования лямбда-выражение. При желании все это можно сделать…
Вот так можно без большого напряжения сил реализовать в Лиспе частичное применение функций и каррирование. Лисп — замечательный язык!
Спасибо за внимание.
В этой небольшой заметке мы рассмотрим, как можно реализовать в Лиспе такие, весьма популярные ныне программные механизмы, как частичное применение и каррирование функций. При этом я буду использовать свою реализацию Homelisp (это чистый интерпретатор Лиспа с некоторыми дополнительными возможностями).
Вероятно, использование частичного применения в Common Lisp будет не очень простым (в связи с тем, что для вызова вычисляемого функционального объекта нужно использовать funcall/apply); в Scheme дело должно обстоять проще. В ближайшее время я планирую опубликовать новую версию HomeLisp, в котором для вызова вычисляемого функционального объекта не требуется funcall/apply. В тех случаях, когда поведение кода отличается, я буду это подчёркивать.
Частичное применение и каррирование — это строгие математические операции. Но мы рассмотрим их «на пальцах», без обращения к лямбда-исчислению и комбинаторной логике.
Частичное применение функции f — это получение из функции f новой функции f', которая уже приняла заданные аргументы, и готова принять остальные. Для чего нужно частичное применение? Например, для того, чтобы из функции можно было вернуть функциональное значение.
Рассмотрим частичное применение на простом примере. Пусть функция f задана формулой:
f(x,y,z)=x+y**2+z**3
тогда частичное применение этой функции с аргументами x=1 и y=2 должно породить функцию:
f'(z) = 1+4+z**3 = 5+z**3
В языке Хаскелл частичное применение ничего не стоит программисту:
Prelude> f x y z = x+y**2+z**3 -- задаем функцию
f :: Floating a => a -> a -> a -> a
Prelude> f 1 2 3 -- проверим...
32.0 -- верно!
it :: Floating a => a
Prelude> f' = f 1 2 -- частично применяем её при x=1 y=2 и сохраняем новую функцию f'
f' :: Floating a => a -> a
Prelude> f' 3 -- функция f' принимает один аргумент
32.0 -- и даёт верный результат
it :: Floating a => a
Однако, в Лиспе такая попытка приведет к неудаче:
(defun f (x y z) (+ x (* y y) (* z z z))) ;; Определяем функцию
==> F
(f 1 2 3) ;; Проверяем работоспособность
==> 32 ;; Верно
(f 1 2) ;; Пробуем задать не все аргументы...
PairLis: Слишком мало фактических параметров
Функция: F
Формальные параметры: (X Y Z)
Фактические параметры: (1 2)
==> ERRSTATE
Конечно, в Лиспе существует механизм создания функций с любым числом аргументов (конструкция &rest); можно создать функцию, которая будет принимать два или три (или десять) параметров:
(defun s (&rest x) ;; неопределенное к-во параметров собирается в список x
(apply '+ x)) ;; и этот список суммируется
==> S
(s 1 2) ;; два параметра
==> 3
(s 1 2 3) ;; три параметра
==> 6
Но важно понимать разницу: эта функция обрабатывает все параметры и возвращает результат вычисления, тогда как частичное применение дает в результате новую функцию, которая «готова продолжить вычисления».
Посмотрим, как можно реализовать на Лиспе механизм частичного применения функции. И поможет нам в этом… да-да, аппарат анонимных функций (lambda). Некоторые программисты думают, что анонимные функции нужны только для экономии имен (мол, их место во всяких stream-map-filter-reduce для того, чтобы выполнить короткое действие над элементом последовательности). На самом же деле анонимные функции способны на гораздо большее, в чем мы сейчас и убедимся.
Начнем с того, что рассмотрим, как функция может вернуть другую функцию как результат. В Лиспе это очень просто:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Как видим, функция возвращает замыкание, в котором значение свободной переменной x зафиксировано (равно 5). Результат функции можно вызвать как функцию. Для этого в Common Lisp и HomeLisp (с редакцией ядра <= 13.53) придется использовать funcall:
(funcall (func-gen 5) 7)
==> 54
Теперь понятно, как можно действовать, если мы хотим взять функцию f от n аргументов и одно значение x, а в результате получить функцию от (n-1) аргумента. Обозначим список формальных параметров нашей функции через plist. Тогда все, что нужно сделать, это построить вот такое лямбда-выражение:
(lambda (хвост-plist) (apply f (cons x хвост-plist)))
Идея очень проста: мы строим лямбда-выражение, в теле которого просто вызываем исходную функцию на списке параметров, в котором голова заменена на значение х.
Значит, для частичного применения функции нужно на базе этой функции построить лямбда-выражение, у которого аргументов будет на единицу меньше, а аргумент, заданный при частичном применении, будет «учтен» во внутреннем вызове нашей функции в теле лямбда-выражения.
Как это реализовать? Несложно… В HomeLisp есть функция getd, которая обеспечивает доступ к определяющему выражению функции или макро:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
Как видим, getd возвращает определяющее выражение функции, в котором «вместо» лямбда находится специальный атом EXPR. Мы можем взять список параметров нашей функции (второй элемент результата) и построить лямбда-выражение, параметрами которого будет хвост исходного списка параметров, а в теле лямбда-выражения мы вызовем исходную функцию с полным списком параметров.
(defun part-apply (f a)
(let* ((plist (cadr (getd f))) ;; исходный список параметров
(rlist (cdr plist)) ;; список параметров без первого
(clist (cons a rlist))) ;; список для вызова с заданным a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
Из приведенного кода легко понять, что plist — это исходный список функции f, которую мы хотим применить частично. rlist — исходный список без первого элемента, а clist — полный список параметров, в котором первый элемент заменен на значение x. Конкретно, для функции g, приведенной выше plist = (x y z), rlist=(y z), а clist=(a y z). Проверим теперь, как работает частичное применение:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Можно убедиться, что это именно то, что и планировалось: part-apply вернула новую функцию, с числом аргументов, на единицу меньшим. Если эту новую функцию вызвать с параметрами y и z, то результат будет в точности такой же, как и вызов исходной функции g с тремя аргументами: 111 y и z:
(g 111 1 2)
==> 444 ;; исходный результат
(funcall (part-apply 'g 111) 1 2) ;; вызов "по-коммон-лисповски"
==> 444
((part-apply 'g 111) 1 2) ;; вызов "по-схемному"
==> 444
Ниже я (для краткости) не буду указывать funcall. В следующем ядре HomeLisp будет изменена схема вычисления функций — станет доступным «схемный» синтаксис.
Пойдем дальше. Теперь возникнет естественное желание повторно применить результат повторного применения. Это оказывается уже совсем простым делом — ведь результат частичного применения — это лямбда-выражение, а оно устроено почти идентично с результатом, который возвращает getd. Список параметров лямбда-выражения — это второй элемент списка. Все эти соображения позволяют построить окончательное решение поставленной задачи:
(defun part-apply (f a)
(cond ((and (atom f) (member 'expr (proplist f))) ;; *** функция ***
(let* ((plist (cadr (getd f))) ;; исходный список параметров
(rlist (cdr plist)) ;; список параметров без первого
(clist (cons a rlist))) ;; список для вызова с заданным a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
((eq 'lambda (car f)) ;; *** лямбда-выражение ***
(let* ((plist (cadr f)) ;; исходный список параметров
(rlist (cdr plist)) ;; список параметров без первого
(clist (cons x rlist))) ;; список для вызова с заданным x
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
(t (raiseerror "part-apply: неверен функциональный аргумент"))))
Здесь добавлен анализ первого параметра: если это атом, то он должен «представлять» функцию (типа EXPR); если первый параметр не является ни «правильным» атомом, ни лямбда-выражением, то возбуждается состояние ошибки. Код, разумеется, можно было бы еще подсократить, две почти идентичные ветви оставлены для наглядности. Посмотрим теперь, на что способна эта функция:
(part-apply (part-apply 'g 1) 2) ;; двукратное применение возвращает функцию одного аргумента
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
((part-apply (part-apply 'g 1) 2) 3) ;; ее можно вызвать и получить верный результат
==> 9
(part-apply (part-apply (part-apply 'g 111) 1) 2) ;; трехкратное применение возвратит безаргументную функцию
==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))
((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ее тоже можно вызвать...
==> 444
(setq u (part-apply 'g 111)) ;; результат частичного применения можно присвоить переменной
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
;; Создана глобальная переменная U
(part-apply u 1) ;; частичное применение можно продолжить
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))
((part-apply u 1) 2) ;; а можно вызвать
==> 444
Теперь займемся каррированием. Каррированная функция, принимая недостаточное число аргументов, возвращает функцию, способную обработать остальные. Главное предназначение каррирования — это как раз обеспечение частичного применения. Мы зашли с другого конца: рассмотрим теперь, как можно реализовать каррирование, если имеется частичное применение.
Пусть дана функция g нескольких аргументов. Мы построим ее каррированный вариант под другим именем !g. Суть построения будет такой: функция !g будет примать неопределенное число аргументов. После вызова она должна проверить количество переданных аргументов. Если это количество равно количеству аргументов исходной функции g, то следует из передать на вход g. Если количество аргументов больше, чем способна принять g, то следует возбудить состояние ошибки. А вот если количество аргументов меньше, чем у функции g, то… да-да — нужно выполнить последовательное частичное применение. Результат этого применения вернуть.
В данном случае удобно использовать макро. Код с комментариями приведен ниже:
(defmacro curry (f)
(let* ((parmlist (cadr (getd f))) ;; список параметров f
(body (cddr (getd f))) ;; тело функции f
(lp (length parmlist)) ;; длина списка параметров f
(cf (implode (cons '! (explode f))))) ;; новое имя для результата каррирования
`(defun ,cf (&rest x)
(let ((lx (length x))) ;; длина актуального списка параметров
(cond ((= lx ,lp) ;; полное применение
(let ((e `(lambda ,parmlist ,@body)))
(apply e x)))
((> lx ,lp) ;; параметров слишком много
(raiseerror "curry: Слишком много фактических параметров"))
(t (let ((tmp nil)) ;; здесь будет результат
(iter (for a in x) ;; частично применяем заданные параметры
(setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))
tmp)))))))
Здесь следует прокомментировать построение нового имени функции. Для этого используются функции HomeLisp explode, которая из атома строит список составляющих его символов, и implode, которая сжимает символы списка в один, порождая новый атом.
Проверим теперь наш макро в «деле»:
(curry g) ;; каррируем g
==> !G ;; каррированный вариант
(!g 1 2 3) ;; при обычном вызове
==> 9 ;; ведет себя как g
(!g 1 2) ;; если аргументов недостаточно - вернет функцию для обработки остальных
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
;; Можно сразу и вычислить результат:
((!g 1 2) 3) ;; остался один аргумент
==> 9
((!g 1) 2 3) ;; осталось два аргумента
==> 9
(!g 1 2 3 4) ;; лишние аргументы вызовут ошибку
curry: Слишком много фактических параметров
==> ERRSTATE
Каррирование у нас выполнено без дополнительного контроля. И мы не реализовали каррирования лямбда-выражение. При желании все это можно сделать…
Вот так можно без большого напряжения сил реализовать в Лиспе частичное применение функций и каррирование. Лисп — замечательный язык!
Спасибо за внимание.