In this short note, we will look at how you can implement in Lisp such now very popular software mechanisms as partial application and currying of functions. In doing so, I will use my Homelisp implementation (this is a pure Lisp interpreter with some additional features).
Using partial application in Common Lisp is likely to be a little tricky (since funcall / apply must be used to invoke a computed function object); in Scheme it should be easier. I plan to post a new version of HomeLisp soon, which does not require funcall / apply to call a computed function object. In cases where the behavior of the code is different, I will emphasize this.
Partial application and currying are strict mathematical operations. But we will consider them "on the fingers", without resorting to lambda calculus and combinatorial logic.
A partial application of the function f is to get from the function f a new function f 'that has already taken the given arguments and is ready to accept the rest. What is partial application for? For example, so that a functional value can be returned from a function.
Let's consider a partial application with a simple example. Let the function f be given by the formula:
f (x, y, z) = x + y ** 2 + z ** 3
then partial application of this function with arguments x = 1 and y = 2 should generate the function:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
In Haskell, partial application costs the programmer nothing:
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
However, in Lisp this attempt will fail:
(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
Of course, Lisp has a mechanism for creating functions with any number of arguments (the & rest construct); you can create a function that will take two or three (or ten) parameters:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
But it is important to understand the difference: this function processes all parameters and returns the result of the calculation, while partial application results in a new function that is “ready to continue the calculation”.
Let's see how we can implement a partial function application mechanism in Lisp. And it will help us with this ... yes, the apparatus of anonymous functions (lambda). Some programmers think that anonymous functions are needed only to save names (they say, their place in any stream-map-filter-reduce in order to perform a short action on a sequence element). In fact, anonymous functions are capable of much more, which we will now see.
Let's start by looking at how a function can return another function as a result. In Lisp, it's very simple:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
As you can see, the function returns a closure in which the value of the free variable x is fixed (equal to 5). The result of a function can be called as a function. To do this, in Common Lisp and HomeLisp (with kernel revision <= 13.53), you will have to use funcall:
(funcall (func-gen 5) 7)
==> 54
Now it is clear how we can proceed if we want to take a function f from n arguments and one value of x, and as a result get a function from (n-1) arguments. Let's denote the list of formal parameters of our function by plist. Then all you have to do is build a lambda expression like this:
(lambda (-plist) (apply f (cons x -plist)))
The idea is very simple: we build a lambda expression, in the body of which we simply call the original function on the parameter list, in which the head is replaced with the value of x.
This means that for partial application of the function, you need to build a lambda expression based on this function, which will have one fewer arguments, and the argument specified during partial application will be "taken into account" in the internal call of our function in the body of the lambda expression.
How to implement this? Easy ... HomeLisp has a getd function that provides access to a function's defining expression or macro:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
As you can see, getd returns the defining expression of the function, in which "instead of" the lambda there is a special EXPR atom. We can take the parameter list of our function (the second element of the result) and construct a lambda expression, the parameters of which will be the tail of the original parameter list, and in the body of the lambda expression we will call the original function with the complete list of parameters.
(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)))))
It is easy to understand from the above code that plist is the original list of the function f that we want to partially apply. rlist is the original list without the first element, and clist is the complete list of parameters, with the first element replaced with x. Specifically, for the function g above, plist = (xyz), rlist = (yz), and clist = (ayz). Now let's check how partial application works:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
You can make sure that this is exactly what was planned: part-apply returned a new function, with one less number of arguments. If this new function is called with parameters y and z, the result is exactly the same as calling the original function g with three arguments: 111 y and z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Below I (for brevity) will not specify funcall. In the next core of HomeLisp, the scheme for calculating functions will be changed - the "scheme" syntax will become available.
Let's go further. There will now be a natural urge to reapply the reapplication result. This turns out to be quite simple - after all, the result of partial application is a lambda expression, and it is structured almost identical to the result returned by getd. The parameter list of the lambda expression is the second item in the list. All these considerations allow us to build the final solution to the problem:
(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: "))))
Here the analysis of the first parameter is added: if it is an atom, then it must "represent" a function (of type EXPR); if the first parameter is neither a "valid" atom or a lambda expression, then an error condition is raised. The code, of course, could be further shortened, two almost identical branches are left for clarity. Now let's see what this function is capable of:
(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
Now let's do currying. A curried function, accepting an insufficient number of arguments, returns a function that can handle the rest. The main purpose of currying is to provide partial application. We went from the other end: now let's look at how currying can be implemented if there is a partial application.
Let a function g of several arguments be given. We will build a curried version of it under a different name! G. The essence of the construction will be as follows: the function! G will take an indefinite number of arguments. After the call, it must check the number of arguments passed. If this number is equal to the number of arguments of the original function g, then from should be passed to the input g. If there are more arguments than g can accept, then an error condition should be raised. But if the number of arguments is less than that of the function g, then ... yes, yes - you need to perform a sequential partial application. Return the result of this application.
In this case, it is convenient to use a macro. The code with comments is below:
(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)))))))
It is worth commenting on the construction of the new function name here. To do this, use the HomeLisp explode functions, which builds a list of its constituent symbols from an atom, and implode, which compresses the list symbols into one, creating a new atom.
Now let's check our macro in action:
(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
Currying was done without additional control. And we haven't implemented currying lambda expression. If you wish, you can do all this ...
This is how you can implement partial function application and currying in Lisp without much effort. Lisp is a wonderful language!
Thank you for attention.