Arc Forumnew | comments | leaders | submitlogin
Implicit Currying Support For Arc
5 points by drcode 5942 days ago | 4 comments
Hey everyone- I've put together a simple (but comprehensive) implementation of implicit currying. The changes are fully compatible with all existing code. It does have one drawback: It will cut your performance by about 2/3rds. (ouch)

BTW, this design was partially inspired by rincewind's ideas in http://arclanguage.org/item?id=7788

The performance issues are due to extra checks required at function call time. Also, Mzscheme 3.x does not have a way to control function arity (4.x does) so I had to use an 'eval in the code in a trick to control arity.

This is the only implementation of implicit currying in a dynamically-typed language I have ever seen- Of course, that could just be because people who have thought about it decided it's a bad idea. I, however, disagree: I think it's quite useful in many common programming situations... but you'll want to judge its merits on your own.

Here are some examples of this feature in use:

  arc> (mem 5)
  #<procedure>
  arc> (= contains-five (mem 5))
  #<procedure>
  arc> (contains-five '(1 2 3))
  nil
  arc> (contains-five '(3 4 5))
  (5)
  arc> (map [mem 5 _] '((1 2 3) (3 4 5)))
  (nil (5))
  arc> (map (mem 5) '((1 2 3) (3 4 5)))
  (nil (5))
  arc> (map mem.5 '((1 2 3) (3 4 5)))
  (nil (5))
Since many arc commands have a variable arity, this implicit currying is useful only if you also have a way to constrain function arity. My implementation allows you to place a literal number in the function position and use that to constrain the arity when you want to curry a variable-arity function:

  arc> (= triple-plus (3 +))
  #<procedure>
  arc> (triple-plus 1 2 3)
  6
  arc> (triple-plus 1 2)
  #<procedure>
  arc> ((triple-plus 1 2) 3)
  6
  arc> (map (2.+ 1) '(100 200 300))
  (101 201 301)
As a final example, here I declare a function in full "point free style"- This is commonly used in Haskell. It roughly means that you're defining a function without explicitly referring to any arguments:

  arc> (= list-add-one (map1 (2.+ 1)))
  #<procedure>
  arc> (list-add-one '(100 200 300))
  (101 201 301)
...You've got to admit that the definition of "list-add-one" is extremely expressive. Note that I used map1 in the command, since it has the required fixed arity already. I could have, instead, used "2.map".

That gives you a rough idea of how implicit currying and how arity constraints work. Here are the changes you need to make in ac.scm to implement this feature:

  (define (genlst n)
          (if (zero? n)
              ()
              (cons (gensym) (genlst (- n 1)))))

  (define (procedure-reduce-arity fn x)
          (let ((gen (genlst x)))
            (eval `(lambda ,gen
                           (,fn ,@gen)))))

  (define (ar-apply fn args)
      (cond ((procedure? fn) (let ((x (procedure-arity fn)))
                                 (if (not (number? x))
                                     (apply fn args)
                                     (let ((y (length args)))
                                       (if (<= x y)
                                         (apply fn args)
                                         (procedure-reduce-arity (lambda lst
                                                                         (ar-apply fn (append args lst)))
                                                                 (- x y)))))))
          ((pair? fn) (list-ref fn (car args)))
          ((string? fn) (string-ref fn (car args)))
          ((hash-table? fn) (ar-nill (hash-table-get fn (car args) #f)))
          ((number? fn) (procedure-reduce-arity (car args) fn))
          (#t (err "Function call on inappropriate object" fn args))))

  (define (ac-call fn args env)
    (let ((macfn (ac-macro? fn)))
      (cond (macfn
             (ac-mac-call macfn args env))
            ((and (pair? fn) (eqv? (car fn) 'fn))
             `(,(ac fn env) ,@(map (lambda (x) (ac x env)) args)))
            (#t
             `(ar-apply ,(ac fn env)
                        (list ,@(map (lambda (x) (ac x env)) args)))))))


2 points by almkglor 5941 days ago | link

A technique I stumbled on while implementing a bunch of crazy tricks in arc-on-mzscheme (just to return to the principle of true axiomatic development) is to create fake scheme-side objects that act as Arc functions (you do have to change the 'disp and 'write functions, and probably handle errors yourself, so that the user doesn't know you're faking functions). Something like this:

  (define (composer fl fr)
    (vector 'composer fl fr))
  (define (composer? fn)
    (and (vector? fn) (eq? 'composer (vector-ref fn 0))))
  (define (composer-fl fn) (vector-ref fn 1))
  (define (composer-fr fn) (vector-ref fn 2))

  ; 'compose is now a reduction on '<base>compose
  (xdef '<base>compose composer)

  ; this is where the speedup comes from!
  (define (ar-funcall0 fn)
    (cond
      ((composer? fn)
        (let ((fl (composer-fl fn))
              (fr (composer-fr fn)))
          (ar-funcall1 fl (ar-funcall0 fr))))
      ...))

  ;etc. for ar-funcall1 to 4 and ar-apply.

-----

1 point by rincewind 5942 days ago | link

clickable link: http://arclanguage.org/item?id=7788

I wrapped the currying and arity with a macro in my code:

  (mac defc (name args . body)
    `(do (def ,name ,args ,@body)
         ,(errsafe:let arity (len args)
                 `(zap [curry ,arity _] ,name))))
Having to specify which functions are curried is not a problem for me, because I mostly use it for combinators, but this simple macro does not integrate with defm or pat-m (yet).

  (defc flip (fun a b)
     (fun b a))

  (defc times (n f)
     [do (repeat n (zap f _)) _])

  ((flip times cdr) 4 '(a b c d e)) 
  => (e)
  ;(flip times cdr) is nthcdr
these examples should work with drcodes currying too, just use def instead of defc.

-----

1 point by almkglor 5941 days ago | link

> but this simple macro does not integrate with defm or pat-m (yet).

It doesn't have to: the 'p-m modifier will adapt to it. All it needs is an args . body somewhere at the end of your macro's arg list - which you do have. p-m will then be able to adapt.

-----

1 point by rincewind 5941 days ago | link

All patterns would have to be of the same length, and ideally they should be ll(1) patterns, so they could dispatch on the first arg. Or should the pattern matching occur after the function got all of its arguments?

What I would really like to see is currying with partial function application and dispatch on every function argument, so that (my-curried-fun (annotate 'foo val)) is evaluated to a curried function for the type foo. Otherwise the (types|patterns) would have to be compared everytime this function is applied, which may be inefficient, e.g in

  (map (my-curried-fun (annotate 'foo val)) my-large-list)
This may be difficult to implement without a change in the interpreter or in p-m and curry/defc.

-----