Closures vs. Currying
Rob Hoelz
What's the difference, if any, between a closure and a function
returned through a curried function?
Thanks!
--
-Rob Hoelz
Steve Schafer
>What's the difference, if any, between a closure and a function
>returned through a curried function?
There are a handful of different but related definitions of "closure"
floating around. I will talk about some of those later, but first, the
simplest, most basic definition is:
closure: an expression containing no free variables
(See http://en.wikipedia.org/wiki/Free_variable for an excellent
definition of free variables.)
One way to think of a closure (or closed expression) is that it is
"closed off" from influence by the outside world.
Thus,
2
is a closure, as is
3 + 5
On the other hand,
x + 19
is not a closure, because it contains a free variable, x.
We can close an open expression (an openure?) by embedding it in an
environment that supplies values for the free variables:
x + 19
where x = 42
And while x + 19 is not a closure, the following lambda expression (in
this case, a function of one argument) is:
\x -> x + 19
But this:
\x -> x * y
is once again not a closure, because it contains a free variable, y.
For later reference, let's call this unclosed function f:
f = \x -> x * y
By now it should be clear how currying is involved in a process that may
be used to close an open expression. First, we wrap the expression to be
closed inside a suitable lambda expression:
g = \y -> (\x -> x * y)
Then we supply a value to the outer lambda expression:
f' = g 37
And f' is thus a closed version of f--unlike f, its value relies on
nothing besides its argument(s).
So, to answer your question, currying is a _part_ of a process for
creating a closure, but it's only a part. The concept of a closure is
more general than currying.
(The above can be extended in an obvious way to expressions containing
more than one free variable.)
Now, for some of the other (mis)definitions of closure:
1) To some people, expressions that make no reference at all to free
variables aren't closures (although they are certainly closed!); a
closure has to be an expression containing free variables which is in
turn embedded in an environment that supplies values for those free
variables; the closure is thus expression + environment.
I prefer to instead think of expressions like 2 + 3 as "degenerate" or
"trivial" closures. You can supply an environment if you want, but its
contents don't matter.
2) Some people refer to the unclosed expressions themselves (e.g., the
function f above) as closures (you can see examples of this at
http://en.wikipedia.org/wiki/Closure_%28computer_science%29 and
http://www.haskell.org/haskellwiki/Closure).
This I believe is completely wrong. If anything, expressions such as f
are "potential closures." They may be closed by providing a suitable
environment to supply values for the free variables, but they aren't
closed yet.
3) Even worse, outside of the functional programming community,
"closure" is sometimes used as a synonym for either "anonymous function"
or "first-class function" or both.
Steve Schafer
Fenestra Technologies Corp.
http://www.fenestra.com/
Joachim Durchholz
>
> closure: an expression containing no free variables
>
> variables aren't closures (although they are certainly closed!); a
> closure has to be an expression containing free variables which is in
> turn embedded in an environment that supplies values for those free
> variables; the closure is thus expression + environment.
I don't think that the latter definition is actually used by many people.
A closure is constructed from an expression by providing values for any
free variables in the expression.
I.e.
5
2 + 5
fac 20
are already self-contained at the source level, so the run-time system
need not do anything particularly interesting to set up closures to
represent these expressions.
For
x + 5
on the other hand, the run-time system must look what 'x' is in the
current context, and combine its findings with some representation of
x + 5
to create a closure. E.g. if x has a value of 2 when the closure is
created, then the result will be
2 + 5
(most languages will also immediately evalute this and simply give back
a value of 5).
Another example: if x is a pointer to the mutable variable y (let me
borrow C notation for that and say &x for this construct), then the
resulting closure would be
&x + 5
A closure can be evaluated to give you a result. In some languages the
evaluation step is explicit, in others it is implicit when the closure
is assigned to a variable.
At the semantic level, almost everything is a closure in most
programming languages. An "openure" would be
x + 5
which would fill in whatever the local definition of x is (since
evaluation may happen very far from the point of the source code that
the closure was created from, this can result in, erm, "interesting and
colorful" effects; the strategy of using the local context is called
"shallow binding" and almost nonexistent in modern languages, so every
expression automatically results in a closure, whether currying is
present or not).
Regards,
Jo
Joachim Durchholz
> What's the difference, if any, between a closure and a function
> returned through a curried function?
Executive summary: having closures is just the way you'd expect things
to work.
Currying isn't.
Long answer:
Currying is mostly a syntactic device: if a function
foo x y z a b c ...
returns
(some complicated expression) z a b c ...
you can leave out all parameters from z onwards. The special thing about
currying is that the definition
foo x y = (some complicated expression)
will work for two, three, four or any other number of parameters. I.e.
if (some complicated expression) returns a function of twenty parameters
if x is a function of twenty-one parameters, then the result of (foo x
y) will be a function of twenty parameters.
A closure is a (possibly not yet evaluated) expression where all
variable names have been filled with (things that will evaluate to) values.
In most languages, everything is a closure, so the term is usually used
for things that may be unevaluated.
The notable exception is Lisp, where you have values, closures, and
unclosed expressions; there, a closure is a thing that must be evaluated
to give a value, and an unclosed expression is like a closure but it
will additionally take a name from the context for a value - i.e. if you
pass an expression like 'x + 5' around as an unclosed expression in
Lisp, evaluating it will take whatever variable happens to have the name
'x' at the point where evaluation is requested.
In a lazy language like Haskell, open expressions aren't very useful
because you don't (want to) know where exactly a subexpression is evaluated.
In strict languages, it is possible to have open expressions, but almost
no language implements them. (I know only Lisp and Tcl. You can also
fake them in any language with introspection that gives access to the
name-value pairs of the caller.)
Regards,
Jo
eschnett
> Hello,
>
> What's the difference, if any, between a closure and a function
> returned through a curried function?
Consider a funciton
f x y = x + y
Then the call "f x" returns a function, namely
\y -> x + y
If, on the other hand, you have a closure
\a -> (something depending on a and b)
then you can instead define a function
f b a -> (something depending on a and b)
and replace the closure by "f b".
In this sense, closures and curried functions are related. However,
conceptually, I think of a closure as an "object" which exists at run
time, while a curried function is only a convenient sugar.
Andreas Rossberg
>
> What's the difference, if any, between a closure and a function
> returned through a curried function?
A closure is the (low-level) representation of a function value
(technically, a closure is defined as a pair of an expression and an
environment). Hence, a partially applied curried function "returns a
closure". But of course, that is only one particular use of a function
value, so closures appear in other places as well.
--
Andreas Rossberg, ross...@ps.uni-sb.de
mulki...@gmail.com
> In a lazy language like Haskell, open expressions aren't very useful
> because you don't (want to) know where exactly a subexpression is evaluated.
Ah, but GHC supports something called implicit parameters, which is the
exact, strictly functional analogue to Lisp's special variables. They
are still bound lexically, of course (anything else wouldn't make any
sense in Haskell, right?), but in a funny way.
Matthias
Joachim Durchholz
As far as I understood implicit parameters, they are essentially a kind
of globals.
Open expressions are a quite different beast.
They depend on the call chain at run-time, not on lexical nesting. If an
open expression is evaluated and has a free variable named 'i', that
variable will be bound to whatever is the innermost 'i' in the call chain.
Imagine scenarios where the call chain has recursion - you can only
access the innermost 'i'.
Imagine a local variable named 'i', somewhere up five levels in the call
chain. (That's the scenario that scares me most.)
The problem with open expressions is that static analysis of what one of
the open variables in it will get bound to requires a full-system
analysis. I.e. they breach modularity.
I'm not 100% sure that they are always evil, though I suspect that it is
the case.
For globals, I'd say they are kind-of evil: you can control them if
there is a small, tightly-controlled number of them.
And sometimes there is simply no way around them.
I see no such redeeming features in open expressions.
Regards,
Jo
Joachim Durchholz
> In this sense, closures and curried functions are related. However,
> conceptually, I think of a closure as an "object" which exists at run
> time, while a curried function is only a convenient sugar.
I have been told that curried functions are more than that.
As far as I understand the issue, defining a function
foo x = bar x
is equivalent to defining an infinite series of functions:
foo x = bar x
foo x y = (bar x) y
foo x y z = ((bar x) y) z
etc.
You might say "OK, but the arity (parameter count) of foo is still
nailed down by bar, and then it's still just syntactic sugar". For this
example, you're right, but let's define this one:
foo x y = x y
Now the arity of foo depends on the arity of x, which is a parameter and
not locally known anymore! If x is a function of two parameters, this
will be
foo x y z = (x y) z
For higher-arity parameters for x, we get an infinite series of
foo x y z a = ((x y) z) a
foo x y z a b = (((x y) z) a) b
...
and *that* cannot be (easily) mapped to tuple-style parameter passing;
you'd need some kind of dependent type schemes to handle that.
On the other hand, currying is just a very special case of dependent
types. And I suspect is indeed just syntactic sugar in most cases.
(Somebody might want to count instances in the standard libraries though.)
Regards,
Jo
Ivan Jager
> eschnett schrieb:
>> In this sense, closures and curried functions are related. However,
>> conceptually, I think of a closure as an "object" which exists at run
>> time, while a curried function is only a convenient sugar.
>
> I have been told that curried functions are more than that.
>
> As far as I understand the issue, defining a function
>
> foo x = bar x
>
> is equivalent to defining an infinite series of functions:
>
> foo x = bar x
> foo x y = (bar x) y
> foo x y z = ((bar x) y) z
>
> etc.
I don't think that's at all related to currying. It is more related to
foo x being equal to bar x and using a reasonble definition of
equivalence. :)
So, since you can substitute bar x anywhere you see foo x, you
automagically get the equalities you mentioned, as well as things like
foo = bar
1 + foo x = 1 + bar x
2 + foo x = 2 + bar x
etc.
foo x / 2 = bar x / 2
etc.
any expression you can think of involving foo = the same expression
with bar substituted for foo.
eschnett: I never thought the syntactic sugar was what made something a
curried function. The way I see it, (fun f x y -> f(x,y)) is no more
curried than (fun f -> fun x -> fun y -> f(x,y)). I'm not sure where if
anywhere the line should be drawn between a curried function, and a
function that returns another function. One reasonable place I think would
be to say it is a curried function if it has no side effect until it has
been applied at lest twice.
In this C program, is there a curried function?
int foo(int a)
{
return a*a;
}
int (*curried(double d))(int)
{
return foo;
}
int main()
{
printf("%d\n", curried(1.1)(5) ); /* <- look here in particular */
return 0;
}
> You might say "OK, but the arity (parameter count) of foo is still nailed
> down by bar, and then it's still just syntactic sugar". For this example,
> you're right, but let's define this one:
>
> foo x y = x y
foo : ('a -> 'b) -> 'a -> 'b
> Now the arity of foo depends on the arity of x, which is a parameter and not
> locally known anymore! If x is a function of two parameters, this will be
>
> foo x y z = (x y) z
>
> For higher-arity parameters for x, we get an infinite series of
>
> foo x y z a = ((x y) z) a
> foo x y z a b = (((x y) z) a) b
> ...
>
> and *that* cannot be (easily) mapped to tuple-style parameter passing; you'd
> need some kind of dependent type schemes to handle that.
Huh? With your definition at the top you also got the equivalent of
infinite series of
foo x (y,z) = x(y,z)
foo x (y,z,a) = x(y,z,a)
foo x (y,z,a,b) = x(y,z,a,b)
...
What do you need dependent types for?
> On the other hand, currying is just a very special case of dependent types.
Inasmuch as anything not involving dependent types is a special case of
dependent types?
Marlene Miller
> What's the difference, if any, between a closure and a function
> returned through a curried function?
((lambda (a b c)
(lambda (x) (+ x a b c)))
2 3 4)
((((lambda (a)
(lambda (b)
(lambda (c)
(lambda (x) (+ x a b c)))))
2)
3)
4)
The value of these two expressions is an object that knows (1) the text
describing the computation to be performed: the parameter x and the body (+
x a b c) and (2) the meanings of the free variables referenced in the text:
the bindings of the free variables a, b and c to 2, 3, and 4 respectively.
I put these two expressions into my EoPL evaluator. (I simplified the body:
(+ x a)).The structure of the environment is a little different.
#(struct:closure
(x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp x) #(struct:var-exp a)))
#(struct:extend-env-record
(a b c) (2 3 4)
#(struct:empty-env-record)))
#(struct:closure
(x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp x) #(struct:var-exp a)))
#(struct:extend-env-record
(c) (4)
#(struct:extend-env-record
(b) (3)
#(struct:extend-env-record
(a) (2)
#(struct:empty-env-record)))))
Marlene Miller
> (lambda (x) (+ x a b c)))
> 2 3 4)
>
> ((((lambda (a)
> (lambda (b)
> (lambda (c)
> (lambda (x) (+ x a b c)))))
> 2)
> 3)
> 4)
Actually, the syntax is not Scheme, but evaluates the same way, except + is
a binary operator. Every time a procedure is applied, the environment
(bindings) is extended. That's why the environments are different.
(proc (a,b,c) proc (x) +(x,+(a,+(b,c))) 2 3 4)
#(struct:closure
(x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp a)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp b)
#(struct:var-exp c)))))))
#(struct:extend-env-record
(a b c) (2 3 4)
#(struct:empty-env-record)))
(((proc (a) proc (b) proc (c) proc (x) +(x,+(a,+(b,c))) 2) 3) 4)
#(struct:closure
(x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp x)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp a)
#(struct:primapp-exp
#(struct:add-prim)
(#(struct:var-exp b)
#(struct:var-exp c)))))))
Joachim Durchholz
> On Thu, 18 Jan 2007, Joachim Durchholz wrote:
>
>> As far as I understand the issue, defining a function
>>
>> foo x = bar x
>>
>> is equivalent to defining an infinite series of functions:
>>
>> foo x = bar x
>> foo x y = (bar x) y
>> foo x y z = ((bar x) y) z
>>
>> etc.
>
>
> foo : ('a -> 'b) -> 'a -> 'b
>
>> Now the arity of foo depends on the arity of x, which is a parameter
>> and not locally known anymore! If x is a function of two parameters,
>> this will be
>>
>> foo x y z = (x y) z
>>
>> For higher-arity parameters for x, we get an infinite series of
>>
>> foo x y z a = ((x y) z) a
>> foo x y z a b = (((x y) z) a) b
>> ...
>>
>> and *that* cannot be (easily) mapped to tuple-style parameter passing;
>> you'd need some kind of dependent type schemes to handle that.
>
> Huh? With your definition at the top you also got the equivalent of
> infinite series of
>
> foo x (y,z) = x(y,z)
> foo x (y,z,a) = x(y,z,a)
> foo x (y,z,a,b) = x(y,z,a,b)
> ...
Yes, but these parameter tuples aren't broken up, so this is simply
polymorphism.
With currying, you can easily split off a number of parameters from the
front of the parameter tuple.
> What do you need dependent types for?
To establish the correspondences between the full tuple and the
remaining tuple after the first few parameters have been split off.
I.e. if parameters are forced to be tuples, we'd have
foo x (y z a b c ...) = x (y z) (a b c ...)
and establishing that the (a b c ...) tuple is type-equivalent to
(y z a b c ...) "minus the first two elements"
isn't exactly the kind of type inference that HM provides. (I have used
the term "dependent types" in the sense of "anything that establishes
depencencies between types beyond what HM provides"; this may not be the
canonical definition for the term "dependent type". My apologies; I
didn't take the time to properly word this aspect.)
Regards,
Jo