Challenge for 2011: functions

[wtd]

After a quick chat with Tony, I'm posing this challenge for compsci.ca members in 2011: simply, come to grips with the following assertion.

Functions can only take one argument.

[apython1992]

Hmmm, I haven't started yet with learning functional programming (so excuse my ignorance here ) but assuming functions have the same behaviour, is it something like a single array of arguments is passed in (and thus one overall argument) and thereafter individual parameters are accessed by simply indexing the array? Or is it more complex than this?

[bbi5291]

The challenge isn't so much how to write code using functions that only take one argument (yes, it is true that you could just stuff all the arguments in an array), but rather how to conceive that a function, even when it appears to be taking two or more arguments, can be deconstructed so that it only takes one at a time.

Besides, what about the function that you use to create the array? Isn't that, in a sense, taking multiple arguments?

[Tony]

Arrays work with fixed-width elements only, but arguments could be primitives, objects, or other functions.

[apython1992]

Oh yeah, I know that the challenge isn't about how to write that code, I was just guessing that maybe internally that's how the arguments are dealt with - a single array of objects, for example. But now that you mention that about deconstructing the function to take only one argument...

I'm thinking that functions that take multiple arguments can be written as something like a chain of functions that each take one argument. So for example, instead of having a single function that takes two integers and returns the sum, such as

f(x, y) = x + y

you could have functions nested together, for example

f(x,y) = g(f(x),y) = x + y

where first, x is inputted and f(x) would just return x. This means that really only one argument is dealt with at a time, because f(x) must be evaluated before calling g(f(x),y). Thus, because x has a value, g really only takes one value in, y. So basically, f(2) would return 2, which means g(y) is now defined as 2 + y. Is this correct?

[bbi5291]

You're on the right track, but the following notation may be more appropriate: f(x,y) = (g(x))(y), to emphasize the fact that the output of g(x) is itself a function, which is then applied to y.

[apython1992]

I see...so upon calling g(x), instead of just returning x, it would return a new function that is defined as x + y (x now being a value), taking y now as its only argument?
So step by step it would look something like:

f(5, 13) = [g(5)](13)
= 5 + 13
= 18

[Shanethe13]

Apython, you are exactly right, and the term for what you just described is currying, named after none other than Haskell Curry!

Time for a crash course in Haskell to demonstrate!

Haskell function declarations have two parts, a type signature, and a binding. The binding is where stuff actually happens (or rather doesn't happen depending on your philosophy), but it is the type signature which tells you exactly what it is that a function does.

For example, a function that adds two numbers might be described as:

add :: (Integer a) => a -> a -> a
add x y = x + y

This reads that the function, add, takes two arguments of type Integer, and returns a third value of type Integer.

However, there's a catch! Functions only take one argument, and so while this type signature describes what is happening, it isn't entirely accurate. Rather, it should be rewritten as this:

add :: (Integer a) => a -> (a -> a)

Whereas the first signature made it seem like the function accepted two arguments, and returned a third integer, this one shows what is really happening: the function, add, accepts an integer, and returns a second function which accepts an integer, returning the final answer.

If we called the function like this:

add 5 7

We are actually doing:

(add 5) 7

Where (add 5) evaluates to a function which accepts one parameter and adds five to it.

You seemed to grasp the concept from your last post, so none of this should be new to you. I just thought I'd type up a more formal explanation while waiting in this airport

[apython1992]

Good stuff! I do understand the concept, but my next question is: why? Is it necessary for computers to take this route? If so, why?

[Shanethe13]

apython1992 @ Wed Mar 09, 2011 11:04 pm wrote:

Good stuff! I do understand the concept, but my next question is: why? Is it necessary for computers to take this route? If so, why?

I don't have a good answer for you off of the top of my head, but it is extremely useful for higher-order functions. Without giving a concrete example, I can just say that currying is normally used to dynamically create functions, which can then be used as building blocks to make more functions. You can do some really interesting stuff by partially applying a function, then using the result to map over a list.

Wtb or Bbi might be able to explain the purpose to you a bit better, I'm nowhere near fluent in this stuff.

[Tony]

Because in Math, when you want to completely understand a system and be able to do various proofs on it, it's often advantageous to have everything build out of as few basic blocks as possible.

functions with n arguments == function with exactly one argument * currying transformation.

http://en.wikipedia.org/wiki/Currying#Mathematical_view

Quote:

In theoretical computer science, currying provides a way to study functions with multiple arguments in very simple theoretical models such as the lambda calculus in which functions only take a single argument.

[bbi5291]

This may only be tangentially related, but an interesting note is that math doesn't even really have a notation for functions of multiple variables. I mean, it seems as though you can write the type of, say, a real-valued function of a single real variable as f : R -> R, and the type of a real-valued function of two real variables as f : R^2 -> R, but R^2 actually represents the Cartesian product of R with itself, that is, the set of pairs of reals, so that f(x,y) should really be thought of as f((x,y)), where (x,y) is the independent variable. (Also, in Haskell, there is a function "curry" that takes a function on pairs and converts it into an equivalent curried function, i.e. a f : R^2 -> R would become f : R -> (f : R -> R), and "uncurry" that accomplishes the opposite transformation.)

[apython1992]

Very neat. So when wtd says that functions can only take one argument, does this mean that in computation, functions are always internally broken down this way? Or is this currying only used for lambda functions?

[Tony]

Not _always_. For example, in assembly there are no arguments at all. You just jmp to a location and read from some registers. Conceptually that's a function call.

[DtY]

apython1992 @ Thu Mar 10, 2011 9:51 am wrote:

Very neat. So when wtd says that functions can only take one argument, does this mean that in computation, functions are always internally broken down this way? Or is this currying only used for lambda functions?

Haskell functions are; syntactically at least. I doubt that a good compiler like GHC would actually compile the functions like that except when you're currying them. Only allowing single argumented functions is useful (for the reasons described above), but it would be pretty inefficient to have to construct a new lambda function every time you call a multi?rgument function.