Sat 29 Aug 2009
I've been transcoding a lot of Haskell to Scheme lately and one of the things that I found myself needing was a macro for dealing with Currying of functions in a way that handles partial and over-application cleanly.
I found a very elegant macro by Piet Delport that handles partial application, but that doesn't deal with the partial application of no arguments or that I'd like to also be able to say things like the following and have the extra arguments be passed along to the result.
(define-curried (id x) x) (id + 1 2 3) ;;=> 6
This of course, becomes more useful for more complicated definitions.
(define-curried (compose f g x) (f (g x))) (define-curried (const a _) a)
While I could manually associate the parentheses to the left and nest lambdas everywhere, Haskell code is rife with these sorts of applications. In the spirit of Scheme, since I couldn't find a macro on the internet that did what I want, I tried my hand at rolling my own.
;; curried lambda (define-syntax curried (syntax-rules () ((_ () body) (lambda args (if (null? args) body (apply body args)))) ((_ (arg) body) (letrec ((partial-application (lambda args (if (null? args) partial-application (let ((arg (car args)) (rest (cdr args))) (if (null? rest) body (apply body rest))))))) partial-application)) ((_ (arg args ...) body) (letrec ((partial-application (lambda all-args (if (null? all-args) partial-application (let ((arg (car all-args)) (rest (cdr all-args))) (let ((next (curried (args ...) body))) (if (null? rest) next (apply next rest)))))))) partial-application)))) ;; curried defines (define-syntax define-curried (syntax-rules () ((define-curried (name args ...) body) (define name (curried (args ...) body))) ((define-curried (name) body) (define name (curried () body))) ((define-curried name body) (define name body))))
While Scheme is not my usual programming language, I love the power of hygienic macros.
I welcome feedback.
[Edit: updated to change the base case for define-curried and added the if to the base case of curried to be more consistent with the other cases per the second comment below]
August 29th, 2009 at 1:27 pm
I don’t know if this is a concern, but the define-curried form isn’t quite right for suspended non-lambda value bindings. For instance, if you have (define-curried x 5), then it’s rather hard to get the 5 out. One option for the first case of the curried macro is to check that “body” evaluates to a procedure, and then apply it to whatever args you’re given (living with arity errors), while returning its normal form otherwise. One has to be careful to not evaluate “body” twice in case it’s the side effect that matters.
One option might be,
((_ () body)
(λ args (let ((r body))
(if (procedure? r)
(apply r args)
r))))
Then I can have something like,
(define-curried x (begin (printf “hi~n”) 5))
that does the right thing, afaict.
August 29th, 2009 at 3:24 pm
@Anthony:
Good point. I was trying to avoid discriminating, so I could just work parametrically, but a quick procedure? check isn’t such a high price to pay to handle the base case more gracefully.
I have two concerns with this proposed fix though.
By redefining (define-curried name body) to just use a define and migrating its current behavior to (define-curried (name) body) this obtains, perhaps a more pleasing result. Patching it thus:
((_ () body) (lambda args (if (null? args) body (apply body args))))yields a result that is identical to the handling of the other two cases in behavior.
Then (define-curried x 5) does the right thing, and just gives you 5.
and (define-curried (x) 5) gives you a nullary function that when invoked will give you back 5, but will try to pass any superfluous over-applied arguments to 5 and crash.
August 29th, 2009 at 8:27 pm
There is a curried lambda at http://programmingpraxis.com/standard-prelude.
August 29th, 2009 at 9:46 pm
@Phil:
Nice macro. =) While, alas, it doesn’t handle over or null application, it is really succinct!
August 29th, 2009 at 10:42 pm
Edward,
I like your fix; a definite improvement! Can you offer more detail on your parametricity concern, though? Like many others, I, too, have a toy monad library in my collection, but it’s not obvious to me how this situation with my proposed patch raises a problem in that area.
August 30th, 2009 at 2:13 pm
@Anthony:
It looks like my parametricity concern was a bit of a misapprehension. I wasn’t able to concoct a scenario where it led to a problem. ;)
If we ignore the existence of nullary functions the new version works really well, as would, I suppose, your fix.
August 31st, 2009 at 1:10 pm
Ed,
I noticed that one of the comments mentioned using a curried lambda. I think that having
a curried lambda instead of a curried define
makes much more sense, given that the define
is like let/letrec/ etc., but it is lambda that absorbs values.
… Dan
August 31st, 2009 at 2:01 pm
Hi Dan,
The code above provides both.
(define id (curried (x) x))
uses the lambda form (perhaps ‘curried’ should be renamed ‘curried-lambda’ ?)
On the other hand,
(define-curried (id x) x)
provides a definition with a curried argument list in the same fashion that (define (id x) x) desugars to (define id (lambda (x) x)) — a convenience that I seem to recall you don’t like using. ;)
June 7th, 2010 at 5:37 am
A cleaned version:
(define-syntax curried-lambda
(syntax-rules ()
((_ () exp exps …)
(lambda as
(cond ((null? as) exp exps …)
(else (apply (begin exp exps …) as)))))
((_ (arg args …) exp exps …)
(letrec ((papp (lambda as
(cond ((null? as) papp)
(else (let ((arg (car as)))
(apply (curried-lambda (args …) exp exps …) (cdr as))))))))
papp))))
March 3rd, 2011 at 12:14 pm
Thanks for sharing, I`ll come back and check one of the other posts you have written. See ya.