One of the more quixotic themes in these notes is my ongoing attempt to introduce partial application to Scheme, whether that be through building up a DSL or writing less-than-universal helper functions, but both have proven unwieldy in their syntax and difficult to compose against idiomatic Lisp.
Without too much overhead, I just want to be able to write something like
foldr (liftA2 (:)) (Right []) [Right 1, Right 2, Right 3]
Right [1,2,3]
in Scheme without all those lambdas.
I'm still not there, but I'm getting closer.
(define-syntax λ (syntax-rules () ((_ . ω) (lambda . ω))))
(define-syntax ? (syntax-rules () ((_ . ω) (if . ω))))
(define-syntax ← (syntax-rules () ((_ . ω) (define . ω))))
(define-syntax ∃ (syntax-rules () ((_ . ω) (let* . ω))))
(← ⊂ cons) (← ↑ car) (← ↓ cdr) (← ∅ '()) (← ∀ map)
(← ($ f ω) (f ω))
I had previously assumed that it was not possible to break a Scheme function of the form
(f α β … ω)
into a fully-curried function
(λ (α) (λ (β) … (λ (ω) (f α β … ω))))
for an arbitrary number of arguments.
I believe this is still true at compile time, and for Scheme in general, but I didn't look into dialect-specific functions.
Chicken provides (procedure-information f), which can return a list of f's parameters at runtime.
(procedure-information ⊂)
(scheme#cons x y)
(← (add3 α β ω) (+ α β ω))
(procedure-information add3)
(add3 α β ω)
Folding across this list allows one to turn any function into a fully curried one. Observe the unevaluated symbolic output, where (curry▽) starts with the complete application of function f to its args, and then builds out surrounding closures, one parameter at a time.
(← (curry▽ f args) (foldr (λ (α Fα) `(λ (,α) ,Fα)) `(f ,@args) args))
(← (curry f) (curry▽ f (↓ (procedure-information f))))
(curry add3)
(λ (α) (λ (β) (λ (ω) (f α β ω))))
Then check out the real deal.
(← (curry▽ f args) (foldr (λ (α Fα) `(λ (,α) ,Fα)) `(,f ,@args) args))
(← (curry f) (eval (curry▽ f (↓ (procedure-information f)))))
(curry add3)
#<procedure (? α)>
((curry add3) 1)
#<procedure (? β)>
(((curry add3) 1) 2)
#<procedure (? ω)>
((((curry add3) 1) 2) 3)
6
This is useful for simple point-free operations that wish to omit their final argument
(∀ (((curry add3) 1) 2) '(1 2 3))
(4 5 6)
but we can do better.
(curry) still won't allow one to fold without a lambda, since folds require an eagerly-evaluated dyadic function.
(foldr (curry ⊂) ∅ '(1 2 3))
Error: bad argument count - received 2 but expected 1: #<procedure (? x)>
The curried cons operation expects nested application against the current list item, then another application against the accumulator, but foldr wants to perform one function application against both at once, hence the
(λ (x acc) …)
in every textbook example, rather than
(λ (x) (λ (acc) …))
Haskell just does the latter under the hood.
Ignore for a moment that one can just fold with ⊂ directly. This won't be the case when Either is in play. A curried function sometimes needs multiple arguments for its next application.
Enter (uncurry). This will return a lambda that accepts any number of args, and then applies the function f against all of them. It tells a partially-applied function to stop being lazy and just eagerly accept the rest of the values it requires.
(← (uncurry f) (λ args (foldl $ f args)))
(uncurry ((curry add3) 1))
#<procedure (? . args)>
(uncurry (((curry add3) 1) 2))
#<procedure (? . args)>
((uncurry ((curry add3) 1)) 2 3)
6
((uncurry (((curry add3) 1) 2)) 3)
6
These functions have the same output, but you can see the difference in where their laziness ends.
There are still too many parentheses compared to the Haskell example though. This can be mitigated by performing the same function application fold on the already-provided arguments. The following function (C) is the final, flexible currying syntax—terse enough to throw in wherever.
(← (C f . args) (uncurry (foldl $ (curry f) args)))
((C add3) 1 2 3)
6
((C add3 1) 2 3)
6
((C add3 1 2) 3)
6
Uncurrying doesn't even require all the remaining parameters. It just allows to you specify n arguments in one chunk. The function will go back to being lazy if there are still more to go.
(← (add4 α β γ ω) (+ α β γ ω))
((C add4 1) 2 3)
#<procedure (? ω)>
(((C add4 1) 2 3) 4)
10
((C add4 1) 2)
#<procedure (? γ)>
((((C add4 1) 2) 3) 4)
10
It was always possible to write
(foldr ⊂ ∅ '(1 2 3))
(1 2 3)
but now one can also write
(foldr (C ⊂) ∅ '(1 2 3))
(1 2 3)
Stupid. But you can also seamlessly chuck larger functions in there without a lambda.
(foldr (C add4 100 0) 0 '(1 2 3))
306
Also stupid. But if you refer once again to my Either implementation, then (sequence) no longer requires a lambda.
(← (sequence Fω) (foldr (C lift2 ⊂) (right ∅) Fω))
(sequence (list (right 1) (right 2) (right 3)))
(R (1 2 3))
This is almost identical to the Haskell at the top of the article. Of course this itself can now be point-free.
(← sequence (C foldr (C lift2 ⊂) (right ∅)))
God help us all.
(procedure-information) won't return parameter lists for compiled C functions like (+). So this is really only useful for messing with your own creations.