Is there a function for auto currying in Elisp?

Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 144 bytes --]

Hi,

I've been looking for a function that would automatically curry its
argument, but couldn't find it.  Maybe I just missed it?

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[Philipp Stephani]

[-- Attachment #1: Type: text/plain, Size: 228 bytes --]

Nicolas Petton <nicolas@petton.fr> schrieb am Do., 21. Dez. 2017 um
16:06 Uhr:

> Hi,
>
> I've been looking for a function that would automatically curry its
> argument, but couldn't find it.  Maybe I just missed it?
>
>
apply?

[-- Attachment #2: Type: text/html, Size: 523 bytes --]

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 713 bytes --]

Philipp Stephani <p.stephani2@gmail.com> writes:

>> I've been looking for a function that would automatically curry its
>> argument, but couldn't find it.  Maybe I just missed it?
>>
> apply?

I'm looking for function that would curry arguments, as opposed to a
partial application.

For instance, it would transform a function that takes A B and C as
parameters into a closure like:

  (lambda (a)
    (lambda (b)
      (lambda (c)
        (funcall f a b c))))

(Meaningless) example:

  (let ((people '(((name . "Bob") (age . 21))
                  ((name . "John") (age . 32))))
        (get (curry #'alist-get)))
    ;; Retrieve all names
    (mapcar (funcall get 'name) people)) ;; => ("Bob" "John")


Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[Clément Pit-Claudel]

On 2017-12-21 11:13, Nicolas Petton wrote:
> Philipp Stephani <p.stephani2@gmail.com> writes:
> 
>>> I've been looking for a function that would automatically curry its
>>> argument, but couldn't find it.  Maybe I just missed it?
>>>
>> apply?
> 
> I'm looking for function that would curry arguments, as opposed to a
> partial application.
> 
> For instance, it would transform a function that takes A B and C as
> parameters into a closure like:
> 
>   (lambda (a)
>     (lambda (b)
>       (lambda (c)
>         (funcall f a b c))))
> 
> (Meaningless) example:
> 
>   (let ((people '(((name . "Bob") (age . 21))
>                   ((name . "John") (age . 32))))
>         (get (curry #'alist-get)))
>     ;; Retrieve all names
>     (mapcar (funcall get 'name) people)) ;; => ("Bob" "John")

apply-partially is the closest you'll get, I think.

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 241 bytes --]

Clément Pit-Claudel <cpitclaudel@gmail.com> writes:

> apply-partially is the closest you'll get, I think.

That's my thought as well, but it's not the same thing.  It may be worth
adding a new `curry' function then.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[Clément Pit-Claudel]

On 2017-12-21 11:56, Nicolas Petton wrote:
> Clément Pit-Claudel <cpitclaudel@gmail.com> writes:
> 
>> apply-partially is the closest you'll get, I think.
> 
> That's my thought as well, but it's not the same thing.  It may be worth
> adding a new `curry' function then.

It's tricky to know what exactly curry should do, though, because of &optional and &rest arguments.
Also, won't you need a funcall for each application of your curried function?

Clément.

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 329 bytes --]

Clément Pit-Claudel <cpitclaudel@gmail.com> writes:

> It's tricky to know what exactly curry should do, though, because of
> &optional and &rest arguments.

That's true.

> Also, won't you need a funcall for each application of your curried
> function?

Indeed, but that's not specific to currying.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[vlnx]

Nicolas Petton writes:
> I've been looking for a function that would automatically curry its
> argument, but couldn't find it.  Maybe I just missed it?

This may be what you are looking for:
#+BEGIN_SRC emacs-lisp
(defun funcall-list (funcs list)
  "Apply `funcall' of each FUNCS on LIST, recursively defined"
  (if (car funcs)
      (funcall-list (cdr funcs)
                    (funcall (car funcs) list))
    list))
#+END_SRC

Re: Is there a function for auto currying in Elisp?

[John Wiegley]

>>>>> "v" == vlnx  <vlnx@mail.com> writes:

v> Nicolas Petton writes:
>> I've been looking for a function that would automatically curry its
>> argument, but couldn't find it. Maybe I just missed it?

v> This may be what you are looking for:

v> #+BEGIN_SRC emacs-lisp
v> (defun funcall-list (funcs list)
v>   "Apply `funcall' of each FUNCS on LIST, recursively defined"
v>   (if (car funcs)
v>       (funcall-list (cdr funcs)
v>                     (funcall (car funcs) list))
v>     list))
v> #+END_SRC

Sometimes I also want:

(defun traverse (f x)
  "Visit all nodes within the sexp X, apply F to its leaves."
  (cond ((consp x)
         (cons (traverse f (car x))
               (traverse f (cdr x))))
        ((listp x)
         (mapcar (apply-partially #'traverse f) x))
        ((hash-table-p x)
         (maphash #'(lambda (key value)
                      (puthash key (traverse f value) x)) x))
        (t (funcall f x))))

Do we have a function already that visits every visitable "node" within a
sexp?

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Is there a function for auto currying in Elisp?

[Stefan Monnier]

> I've been looking for a function that would automatically curry its
> argument, but couldn't find it.  Maybe I just missed it?

I'm quite familiar with currying, but in the context of Elisp it's
rather tricky to give a good and reliable specification of what it
should do.  E.g. what should (curry #'apply) or (curry #'list) return?

So, I think we can't magically handle all cases.
Of course, we can do the easy cases:

    (defun curry (f n)
      (if (< n 2)
          f
        (lambda (x)
          (curry (apply-partially f x) (- n 1)))))

but ... I'm not sure we want to encourage this.
What's your use case(s)?


        Stefan

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 695 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> So, I think we can't magically handle all cases.

Definitely not for functions that take &rest params.

> Of course, we can do the easy cases:
>
>     (defun curry (f n)
>       (if (< n 2)
>           f
>         (lambda (x)
>           (curry (apply-partially f x) (- n 1)))))

That's exactly the implementation I was playing with yesterday :-)

> but ... I'm not sure we want to encourage this.

Why not?

> What's your use case(s)?

I don't have a specific use case right now, but I think that currying
can be very expressive and elegant, and fits extremely well with
functional programming, which Elisp is very capable of.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[Stefan Monnier]

>> Of course, we can do the easy cases:
>> 
>> (defun curry (f n)
>>   (if (< n 2)
>>       f
>>     (lambda (x)
>>       (curry (apply-partially f x) (- n 1)))))
> That's exactly the implementation I was playing with yesterday :-)
>> but ... I'm not sure we want to encourage this.
> Why not?

It's using a part of Elisp's implementation which is definitely not
very efficient.

If you're serious about using such a construct, you'd first want to make
it into a macro so it avoids the use of apply-partially which just adds
insult to injury.

>> What's your use case(s)?
> I don't have a specific use case right now, but I think that currying
> can be very expressive and elegant, and fits extremely well with
> functional programming, which Elisp is very capable of.

"Real" functional programming tends to use lots of small functions, so
it's important to optimize the implementation of function calls and
closure creations.  Elisp is not great at either of those:
- E.g. creating a closure with N free variables, in a straightforward
  implementation typically requires one allocation of an object of size
  N+1 words or so.  In Elisp, it requires allocation one 2 objects, one
  of size 6 (the `compiled-function`) and another of size N+M where M is
  the number of constants that appears within the function (and is
  typically larger than N).
- The above definition of `curry` eats a fair chunk of stack when you
  finally call the function: for a given N you end up with N nestings of
  `apply-partially`, each one eating some stack space.  If you use this
  heavily you're likely to want to bump the max stack depth.
- Of course, each nesting of `apply-partially` involves apply+&rest,
  hence conversion list<->vector which means allocation of `cons` cells
  (luckily those "vectors" are stack allocated so they cost a bit less).
- And of course, our implementation of function calls itself is not
  super efficient (several nested C function calls for each Elisp
  funcall, plus copying of arguments between different stacks), and all
  those lambda layerings exercise this weak spot of the language.

The Elisp style is evolving and those inefficiencies are more often
visible (e.g. cl-print's main bottleneck is the cost of apply+&rest in
my tests), so we can hope that someone will work on reducing them at
some point; and in general I do recommend to make your code clean and
correct first and foremost.  But keep in mind that Elisp's support for
functional programming is a bit lacking in efficiency.


        Stefan

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 1019 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> "Real" functional programming tends to use lots of small functions, so
> it's important to optimize the implementation of function calls and
> closure creations.  Elisp is not great at either of those:

I meant that Elisp (like most Lisps) is a good fit for functional
programming from the point of view of the semantics of the language and
the constructs it provides.

> The Elisp style is evolving and those inefficiencies are more often
> visible (e.g. cl-print's main bottleneck is the cost of apply+&rest in
> my tests), so we can hope that someone will work on reducing them at
> some point;

That'd be nice indeed, but one beautiful day we'll get Guile's VM
anyway!

> and in general I do recommend to make your code clean and
> correct first and foremost.  But keep in mind that Elisp's support for
> functional programming is a bit lacking in efficiency.

I've not yet hit any performance issue regarding fun calls or heavy use
of closures :)

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]

Re: Is there a function for auto currying in Elisp?

[John Wiegley]

>>>>> "NP" == Nicolas Petton <nicolas@petton.fr> writes:

NP> I've not yet hit any performance issue regarding fun calls or heavy use of
NP> closures :)

Isn't deep recursion pretty expensive in Elisp?

-- 
John Wiegley                  GPG fingerprint = 4710 CF98 AF9B 327B B80F
http://newartisans.com                          60E1 46C4 BD1A 7AC1 4BA2

Re: Is there a function for auto currying in Elisp?

[Nicolas Petton]

[-- Attachment #1: Type: text/plain, Size: 552 bytes --]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> If you're serious about using such a construct, you'd first want to make
> it into a macro so it avoids the use of apply-partially which just adds
> insult to injury.

The implementation can be made more efficient, but my question is
whether or not a `curry' function should be part of Elisp's arsenal.  I
think it should, the same way as we have `apply-partially'.

The fact that closures are expensive is a bit sad, but I don't think
that we should discourage users from using them.

Cheers,
Nico

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 487 bytes --]