closure
Author Message
closure

Reading sicp, section 2.2, it states that

The ability to create pairs whose elements
are pairs is the essence of list structures importance
as a representational tool. 'We refer to this ability
as the closure property of cons'

Could someone explain this idea of closure please.
sicp seems to assume its well understood already.

Is it important? If so why, & how might it be useful?

TIA, DaveP

Sun, 07 Apr 2002 03:00:00 GMT
closure

Quote:

> Could someone explain this idea of closure please.  sicp seems to
> assume its well understood already.

I don't think SICP assumes it is already understood, as they spend a
lot of time explaining it. A lot of chapter 2 is about closures, and I
find the picture-language example to be quite illustrating. If you

--
Frode Vatvedt Fjeld

Sun, 07 Apr 2002 03:00:00 GMT
closure
On Wed, 20 Oct 1999 21:44:08 +0100, "Dave Pawson"

Quote:

>Could someone explain this idea of closure please.
>sicp seems to assume its well understood already.

The idea of closure is straightforward. Assuming some kind of
transformation operation, closure simply means that the set of
possible operands and the set of possible outcomes of performing the
operation are the same set.

For example, the set of integers is closed under the operation of
addition: Adding any two integers results in a value which is another
integer. The set of integers is _not_ closed under the operation of
division, however, since dividing one integer by another may not
result in an integer. The set of non-zero rational numbers _is_ closed
under division.

-Steve

Sun, 07 Apr 2002 03:00:00 GMT
closure

Quote:

>Reading sicp, section 2.2, it states that

>The ability to create pairs whose elements
>are pairs is the essence of list structures importance
>as a representational tool. 'We refer to this ability
>as the closure property of cons'

>Could someone explain this idea of closure please.

In other words, anything that cons can return, it can also accept as
input. For example:

(cons (cons a b) (cons c d))

The results of the two inner conses are guaranteed to be valid arguments to
the outer cons.

As for applicability of this to list structures, consider that any list
is basically a series of nested pairs, as in these examples:

(list a b c d) == (cons a (cons b (cons c (cons d '()))))

(list (list a b) c d) == (cons (cons a (cons b '()))
(cons c (cons d '())))

So the ability to build lists, especially nested lists, is directly related
to the closure property of cons.

Craig

Sun, 07 Apr 2002 03:00:00 GMT
closure

Quote:
> Reading sicp, section 2.2, it states that

> The ability to create pairs whose elements
> are pairs is the essence of list structures importance
> as a representational tool. 'We refer to this ability
> as the closure property of cons'

> Could someone explain this idea of closure please.
> sicp seems to assume its well understood already.

Others on this thread have given a good explanation of the kind of closure
the authors are talking about here.  However, be sure you read the
footnote at the bottom of the page where you read that paragraph.

I'm sure, if you stick around here, you will see references to something
called
a "closure" (usually in the context of a procedure or continuation, IIRC).
As the SICP
authors point out in the footnote, this kind of "closure" is totally
unrelated to the
mathematical concept just discussed.  I'd hate for you to get confused by
the two
different uses of the term.

(I know *I'd* better not try to explain anything about the other kind of
closure, but

David Albertz

Sun, 07 Apr 2002 03:00:00 GMT
closure

Quote:
> >Could someone explain this idea of closure please.

> In other words, anything that cons can return, it can also accept as
> input. For example:

>     (cons (cons a b) (cons c d))

> The results of the two inner conses are guaranteed to be valid arguments
to
> the outer cons.

> As for applicability of this to list structures, consider that any list
> is basically a series of nested pairs, as in these examples:

>     (list a b c d) == (cons a (cons b (cons c (cons d '()))))

>     (list (list a b) c d) == (cons (cons a (cons b '()))
>                                    (cons c (cons d '())))

> So the ability to build lists, especially nested lists, is directly
related
> to the closure property of cons.

Yep, again clear.
Hence he goes on to start to make statements
about using lists for data structure models,
since closure is applicable here?

Is that the point of it...?
He's done same for scheme, as a 'first class lang',
now hes doing same for lists in terms of a data model?

Regards, DaveP

Mon, 08 Apr 2002 03:00:00 GMT
closure

Quote:
> The idea of closure is straightforward. Assuming some kind of
> transformation operation, closure simply means that the set of
> possible operands and the set of possible outcomes of performing the
> operation are the same set.

> For example, the set of integers is closed under the operation of
> addition: Adding any two integers results in a value which is another
> integer. The set of integers is _not_ closed under the operation of
> division, however, since dividing one integer by another may not
> result in an integer. The set of non-zero rational numbers _is_ closed
> under division.

Thanks Steve, the second para does make sense.

regards, DaveP

Mon, 08 Apr 2002 03:00:00 GMT
closure

Steve Schafer  wrote

Quote:
> The idea of closure is straightforward. Assuming some kind of
> transformation operation, closure simply means that the set of
> possible operands and the set of possible outcomes of performing the
> operation are the same set.

Hang on.
'Scuse the inexact language please, I'm no mathematician.

with tranform T operating on a set of integers,
after the tranform I still have a set of integers?

with tranfrom T operating on a representation of foobars,
after the transform I still have foobars?

*if* thats the idea, why the hell call it closure
({*filter*}y mathematicians I suppose <grin/>),

If I could 'undo' the transform (or perform an inverse
transform) and still get foobars out at the end,
then thats a reasonable use of the term closure,
I'd be closing the loop (ish).

'Lack of mutation' of operands, is that the idea?

<steve>the set of integers is closed under the operation of addition</steve>
Yes, that does make sense.
Something being 'closed' i.e. it doesn't jump out of its box
(doesn't mutate) after being subject to the transform.

thanks Steve. Now I do get it.
.... Put it away for some time when I find a use for
that particular piece of knowledge....

regards, DaveP

Quote:

> For example, the set of integers is closed under the operation of
> addition: Adding any two integers results in a value which is another
> integer. The set of integers is _not_ closed under the operation of
> division, however, since dividing one integer by another may not
> result in an integer. The set of non-zero rational numbers _is_ closed
> under division.

> -Steve

Mon, 08 Apr 2002 03:00:00 GMT
closure

Quote:

> > The idea of closure is straightforward. Assuming some kind of
> > transformation operation, closure simply means that the set of
> > possible operands and the set of possible outcomes of performing the
> > operation are the same set.

> > For example, the set of integers is closed under the operation of
> > addition: Adding any two integers results in a value which is another
> > integer. The set of integers is _not_ closed under the operation of
> > division, however, since dividing one integer by another may not
> > result in an integer. The set of non-zero rational numbers _is_ closed
> > under division.

> Thanks Steve, the second para does make sense.

Hmm.  The term "closure" is heavily overloaded.  It's been a while
since I last looked at SICP, but my gut feeling is that the "closure"
it talks about is not the one described by the above.  If I am wrong
least two (very different) kinds of closures mentioned in the book.
Without an accompanying explanation, I find this unlikely.

Matthias

--

Kyoto University, Research Institute for Mathematical Sciences
(remove underscores in mail address; they are there to fight spam)

Tue, 09 Apr 2002 03:00:00 GMT
closure

Quote:

> > > The idea of closure is straightforward. Assuming some kind of
> > > transformation operation, closure simply means that the set of
> > > possible operands and the set of possible outcomes of performing the
> > > operation are the same set.

> > > For example, the set of integers is closed under the operation of
> > > addition: Adding any two integers results in a value which is another
> > > integer. The set of integers is _not_ closed under the operation of
> > > division, however, since dividing one integer by another may not
> > > result in an integer. The set of non-zero rational numbers _is_ closed
> > > under division.

> > Thanks Steve, the second para does make sense.

> > I'll read on in SICP, and study your first one.

> Hmm.  The term "closure" is heavily overloaded.  It's been a while
> since I last looked at SICP, but my gut feeling is that the "closure"
> it talks about is not the one described by the above.

No, it is.

Quote:
>  If I am wrong
> least two (very different) kinds of closures mentioned in the book.
> Without an accompanying explanation, I find this unlikely.

Your memory is failing you ;-). Although SICP deals a lot with the
"other" closures, it doesn't actually call them that. This meaning of
closure is only mentioned once, in a footnote, on page 98 (in my
edition anyway).

"The Lisp community also (unfortunately) uses the word closure to
describe a totally unrelated concept: A closure is an implementation
technique for representing procedures with free variables. We do not
use the word "closure" in this second sense in this book."

Regards,
Michael

Tue, 09 Apr 2002 03:00:00 GMT
closure

Quote:

> .... Put it away for some time when I find a use for
> that particular piece of knowledge....

And wouldn't you just know it.
Browsing 24 hours later, I came across

At http://db.cis.upenn.edu/XML-QL/
<quote>StruQL queries are also compositional, i.e., a StruQL query accepts a
graph as input and produces a graph as output. This means the results of a
query can be provided as input to another StruQL query. </quote>
I.e. the operands are graphs, the transform is a query, the object produced
by the transform is also a graph!

Who said learning was wasted <grin/>

DaveP

Tue, 09 Apr 2002 03:00:00 GMT
closure
On Thu, 21 Oct 1999 19:24:50 +0100, "Dave Pawson"

Quote:

>*if* thats the idea, why the hell call it closure

Why not? The set _is_ closed under the operation T. There is no way to
"escape" the set by performing the operation on any of the members of
the set, so it's closed.

Quote:
>If I could 'undo' the transform (or perform an inverse
>transform) and still get foobars out at the end,
>then thats a reasonable use of the term closure,
>I'd be closing the loop (ish).

You're sort of (but not quite) heading off in the direction of group
theory with that. The notion of closure refers to the _single_
operation T. There may not even exist an inverse operation. For
example, if the operation is "multiply by zero," then the set of
integers is indeed closed under that operation, since the result of
the operation T is always zero, which is indeed an integer. But there
is no inverse operation that you could apply to the result (zero) and
retrieve the original operand.

Quote:
>'Lack of mutation' of operands, is that the idea?

Well, I don't think I'd use that particular phrase, but I think you
have the right idea.

You have a set of marbles, in various colors, say red, green, and
blue. The number of marbles in the set is not fixed; the only thing
that matters is that the set consists of marbles and nothing else, and
each marble is red, green, or blue.

You also have a black box (representing the operation). You drop
marbles in the 'IN' slot in the box, and stuff comes out the 'OUT'
slot. If what comes out of the 'OUT' slot is occasionally a yellow
marble, then you don't have closure. If what comes out of the 'OUT'
slot is a ham sandwich, then you don't have closure. You only have
closure if the stuff that comes out of the 'OUT' slot can be added
back to the original set of marbles without changing the defining
characteristics of that set.

-Steve

Tue, 09 Apr 2002 03:00:00 GMT
closure

Quote:

>*if* thats the idea, why the hell call it closure
>({*filter*}y mathematicians I suppose <grin/>),

Mathematicians refer to a set S being closed under a function f when f(x)
is in S whenever x is in S.  The term comes from the idea of a closed room
containing all the elements of S -- you don't need to get out of the room
to find the results of the functions.  From this you get "closure" as the
name of the property that this set+function have.

Be careful when trying to apply ordinary definitions to mathematical
terms.  In normal language, "group" and "set" are pretty much synonymous,
but in mathematics a group is a very special kind of set.

--