From posting-system@google.com Wed May 28 22:45:24 2003 Date: Wed, 28 May 2003 15:45:19 -0700 From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.functional Subject: Closures without assignment References: <3ED320DC.3050302@info.unicaen.fr> <3ED475D6.6080309@info.unicaen.fr> Message-ID: <7eb8ac3e.0305281445.39a6cce8@posting.google.com> Status: OR > >Can you give an example of something (in a pure functional language) > >that can be done with closures [sic!] but not without them? > There is nothing that cannot be done without first-class functions [sic!] I'm afraid there is a misunderstanding: closures are not synonymous with first-class functions! In lambda-calculus, abstractions are first class: we can apply abstractions to abstractions and get abstractions as the result. There are no closures -- only substitutions. Granted, doing substitutions is expensive [*], therefore, it makes sense to delay them and execute by need. Thus environment was invented as a list of pending substitutions. Now, when we pass an abstraction around, we also need to pass the list of substitutions that should be performed but weren't -- we need to enclose the environment. The environment is merely a _lazy_ substitution, an optimization technique. Incidentally, even if we delay substitutions, we don't necessarily need closures. We need to be careful to force the pending substitutions when we return or accept a functional object. Thus a partial application of a function is equivalent to a partial specialization. In a byte-compiled or just-in-time compiled language, this may be a valid strategy. Closures are a big deal in a non-pure language, because mutable closed-over lexical variables can model an encapsulated mutable state. That's how Scheme has started. Closures with mutable variables turned out to model actors. [*] One reason substitutions are expensive is because we may substitute in terms we will later discard. The main reason however is that naively doing n substitutions on a term t requires n traversal and rebuilding of the term. Normalization by evaluation can greatly help out in speed (and often eliminate the traversals). Furthermore, many systems (such as ACL2) "bundle" substitutions. From posting-system@google.com Thu May 29 23:40:00 2003 Date: Thu, 29 May 2003 16:39:58 -0700 From: oleg@pobox.com (oleg@pobox.com) Newsgroups: comp.lang.functional Subject: Re: Closures without assignment References: <3ED320DC.3050302@info.unicaen.fr> <3ED475D6.6080309@info.unicaen.fr> <7eb8ac3e.0305281445.39a6cce8@posting.google.com> <265d96ac.0305290717.31801891@posting.google.com> Message-ID: <7eb8ac3e.0305291539.2639f083@posting.google.com> Status: OR wildgoose@operamail.com (David Basil Wildgoose) wrote in message news:<265d96ac.0305290717.31801891@posting.google.com>... > I believed that closures captured their environment at the moment of > creation, and thus were unaffected by changes in state that have > occurred between their creation and their evaluation. > > Is this correct? I'm afraid not exactly. I'd like to remark first that 'environment' and 'state' are not synonymous. In some languages, environment binds names to values. In some other languages, environment binds names to locations (which are then bound to values). Each or both these mappings can be said to constitute a state. In most languages, the state can be changed -- ether by mutating the name-value binding or by altering the contents of a location. A closure 'captures' the environment in the sense of capturing the _reference_ to the corresponding environment frame. If the environment frame remains accessible to us through another reference -- or if we can access locations through another binding, we can affect the closure. Generally, a closure does not capture the state. ; A closure sees mutations of a binding in the captured environment frame (define a 1) ; adda is a closure that captures the binding of a (define adda (lambda (y) (+ a y))) (display (adda 2)) (newline) ; prints 3 (define a-old a) ; mutate the binding: a will be bound to a new location that contains the ; value 2 (set! a 2) (display (eq? a a-old)) (newline) ; prints #f: location changed (display (adda 2)) (newline) ; prints 4 ; A closure sees mutations of a value (or, mutation of a map from ; a location to a value) ; A closure maker. The return result is a closure that captures ; the binding of x to the second argument of curry2 (define (curry2 f x) (lambda (y) (f x y))) (define cell list) (define cell-ref car) (define cell-set! set-car!) (define b (cell 1)) (define (radd u v) (+ (cell-ref u) (cell-ref v))) ; addb is a closure. The binding of x is invisible to us. ; However, the inaccessible name x is bound to a location that is ; accessible to us, through another binding 'b'. In fact, 'x' and 'b' ; are aliases. Changes made to the location are visible to both bindings. (define addb (curry2 radd b)) (display (addb (cell 2))) (newline) ; prints 3 ; Mutate the location pointed out by 'b'. The binding of 'b' ; remains the same, the contents of the location changes. (define b-old b) (cell-set! b 2) (display (eq? b b-old)) (newline) ; prints #t: location stays the same (display (addb (cell 2))) (newline) ; prints 4