[plt-scheme] Typed scheme and curry

On Dec 19, Carl Eastlund wrote:
> The "curry" function in Typed Scheme isn't just about writing curried
> functions, it's about converting uncurried functions to curried
> functions.  If you want to write a function in a curried style from
> the get-go, you can do it like this: [...]

[Note: this is a reply for Scott.]

Note that the basic problem that (the untyped) `curry' solves is
unrelated to the typed vs the untyped worlds -- it's the fact that
Scheme has variable arity functions, and therefore `curry' is
"guessing" how many levels of function calls are needed.  (I'll
describe what it's "type" would be below.)  (BTW, there is a plan to
change how `curry' works -- the result is still going to be
problematic for typed-scheme.)  In any case, when you say

  FWIW, strongly typed languages like Haskell and ML have curried
  functions.  The typing isn't very complicated at all.

you're right -- except that this has very little to do with the fact
that these langauges are strongly typed -- it's actually the fact that
they lack such varied arity functions.  (There is some relation
though: making a static type system work with varied arity functions
is more difficult, so staticaly typed languages will have one more
reason to go with a fixed-arity world.)

As for the type of `curry' -- the thing that it does, roughly speaking
is take a function and return a function that "accumulates" argument
until it satisfies the original function's arity.  So, for example,
given an input function with a type

  A B C -> D

it will return something that looks like this:

  (U (A -> (B -> (C -> D)))
     (A -> (B C -> D))
     (A B -> (C -> D))
     (A B C -> D))

But the curried functions also work with zero arguments -- they simply
return themselves, so the type should really be

  (Rec This1
    (U (-> This1)
       (A -> (Rec This2
               (U (-> This2)
                  (B -> (Rec This3
                          (U (-> This3)
                             (C -> D))))
                  (B C -> D))))
       (A B -> (Rec This4
                 (U (-> This4)
                    (C -> D))))
       (A B C -> D)))

There are some additional things that complicate this even more, for
example, PLT can have a variable arity function with a few fixed
arities, for example:

  > (procedure-arity (case-lambda [(a b) 2] [(a b c d) 4]))
  (2 4)

Currying this function, assuming its type is

  (U (A B -> R) (A B C D -> R))

returns something that looks roughly like

  (Rec This1
    (U (-> This1)
       (A -> (Rec This2
               (U (-> This2)
                  (B -> R)
                  (B C -> (Rec This3
                            (U (-> This3)
                               (D -> R)))))))
       (A B -> R)
       (A B C -> (Rec This4
                   (U (-> This4)
                      (D -> R))))))

and to make things even more fun, each of the original cases can have
its own type (which is why typed scheme has an arrow type for
case-lambda functions instead of using unions).

Anyway, take all of these things and try to put them into one type for
`curry', and you can see why it's such a mess.

Like I said above -- this is complicated in a way that can be
reflected on uses of curried functions, which is part of the reason
why it should (and planned to) be simplified.  But even a much
simplified version will have a complicated type -- for example, take
simple curry function that always produces a two-step result function,
and forbids applications without arguments.  Its type would begin like
this:

  (U ((A B -> C) -> (A -> (B -> C)))
     ((A B C -> D) -> (U (A -> (B C -> D))
                         (A B -> (C -> D))))
     ((A B C D -> E) -> (U (A -> (B C D -> E))
                           (A B -> (C D -> E))
                           (A B C -> (D -> E))))
     ...)

and don't forget about variable-arity functions, even if we say that
we deal with only a the single simplest case:

  (U ...
     ((A A A* -> B) -> (A A* -> (A A* -> B))))

So, if you read up to this point you can see why it's much easier for
statically-typed languages to restrict functions to having fixed
arity, then gain some of the flexibility back by using currying
as the default mode for multiple arguments, which basically makes all
functions be single-argument functions.  (You can, of course, mimic
functions with a different number of arguments by using tuples -- but
if you want to curry these functions you get into a similar mess.)

-- 
          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                  http://www.barzilay.org/                 Maze is Life!