The Artima Developer Community
Sponsored Link

Weblogs Forum
Musing about Closures

30 replies on 3 pages. Most recent reply: Oct 24, 2005 9:54 PM by Howard Lovatt

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 30 replies on 3 pages [ « | 1 2 3 | » ]
Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Musing about Closures Posted: Oct 3, 2005 10:45 AM
Reply to this message Reply
Advertisement
> Do you have any examples?

Nothing better than what you can find in any decent book on FP or in almost any article describing a combinator library. Functions that return functions are (about) as common in FP as are methods returning objects in OO. For particular educational examples, you could take a look at SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-12.html#%_sec_1.3.4 .

> How specifically is the auto-destructive closure I am proposing unable
> to achieve the same abstraction as a full closure?

It doesn't even come close. What you propose makes closures second-class objects. Consider, for example, implementing delay and force to simulate lazy evaluation as explained in most introductory books on (strict) funtional programming. See, for example, SICP: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.html#%_sec_Temp_449 . A delay essentially returns a closure.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Musing about Closures Posted: Oct 3, 2005 11:59 AM
Reply to this message Reply
> In a GC language, the programmer has no way of explicitly stating when
> the object is supposed to be killed, so everything is kept alive as long
> as the computer deems needed, removing the ability of the programmer to
> detect design flaws.

I've only asked this a million times, but here goes nothing: Why do you think that GC precludes explicit management of resources? (The fact is that it doesn't.)

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Musing about Closures Posted: Oct 3, 2005 12:12 PM
Reply to this message Reply
> > In a GC language, the programmer has no way of
> explicitly stating when
> > the object is supposed to be killed, so everything is
> kept alive as long
> > as the computer deems needed, removing the ability of
> the programmer to
> > detect design flaws.
>
> I've only asked this a million times, but here goes
> nothing: Why do you think that GC precludes explicit
> management of resources?
(The fact is that it doesn't.)

Calm down. Of course I know it doesn't. Rephrase the above the be "in a GC language such as Java without facilities for explicit object destruction ..." if it makes you happy.

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Musing about Closures Posted: Oct 3, 2005 12:28 PM
Reply to this message Reply
> > Do you have any examples?
>
> Functions that return functions are (about) as
> common in FP as are methods returning objects in OO.

There is some confusion here, I am definitely allowing functions to return functions. For the record, I am not completely ignorant of the functional paradigm.

> > How specifically is the auto-destructive closure I am
> proposing unable
> > to achieve the same abstraction as a full closure?
>
> It doesn't even come close. What you propose makes
> closures second-class objects. Consider, for example,
> implementing delay and force to
> simulate lazy evaluation as explained in most introductory
> books on (strict) funtional programming. See, for example,
> SICP:
> http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-24.htm
> l#%_sec_Temp_449 . A delay essentially
> returns a closure.

There is no reduction in expressiveness AFAICT.

{
  def f() : int { return 42; }
  def delay(function f) { return f; }
  def force(function f) { return f(); }
  write_int(force(delay(f)));
}


Perhaps you are referring specifically to the memo-proc implementation:

(define (memo-proc proc)
  (let ((already-run? false) (result false))
    (lambda ()
      (if (not already-run?)
          (begin (set! result (proc))
                 (set! already-run? true)
                 result)
          result))))


But I am confused here because this is not an example of strict functional programming as you seemed to indicate because there is a variable declaration and an assignment.

However, I can see that this implementation is not possible as a closure under my proposal.

The same effect can be achieved using OOP as follows:

class memo_proc {
  public {
    _init(function f) {
      mf = f;
      mb = false;
    }
    _call(list l) {
      if (!mb) {
        mo = mf(l);
      }
      return mo;
    }
  }
  fields {
    object mo;
    function mf;
    bool b;
  }
}
 
def f() : int { 
  return 42; 
}
def g(function f1, function f2) : int { 
  return f1() + f2(); 
}
 
memo_proc mp(f);
g(mp, mp);


So you are correct in that there are limitations on the expressiveness of the short-lived closures that I am proposing. They can however be easily compensated for by using OO techniques. I believe though that saying "it doesn't even come close", is an exaggeration.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Musing about Closures Posted: Oct 3, 2005 12:53 PM
Reply to this message Reply
> Calm down.

[I made the question bold because you've ignored it previously. I'm (and was) perfectly calm, thank you. ;-]

> Of course I know it doesn't. Rephrase the above the be "in a
> GC language such as Java without facilities for explicit object
> destruction ..." if it makes you happy.

If you want to make something new you should better look beyond mainstream languages like Java. Perhaps this wasn't what you had in mind, but naively augmenting Java with something like delete (or destructors) would be a mistake, because then you would have dangling references (and/or expensive run-time checking). I recommend that you look at things like Monads (Haskell), uniqueness typing (Clean), linear types, and substructural type systems, which allow you to express resource management correctly.

Vesa Karvonen

Posts: 116
Nickname: vkarvone
Registered: Jun, 2004

Re: Musing about Closures Posted: Oct 3, 2005 1:57 PM
Reply to this message Reply
> I am not completely ignorant of the functional paradigm.

If you knew as much about the theory of OO and had as much practical experience in OO programming as you do in FP, then how would you characterize your level of OO knowledge?

> There is no reduction in expressiveness AFAICT.

In strict FP languages you can treat promises as first-class objects. In particular, you can (and do) return promises from functions. More generally, a function can return a closure. In fact, it is extremely simple and commonplace to write functions that create functions in FP languages. For example, parsing combinators are functions that you call to create parsers. Implementing parsing combinators with proper closures is very simple. I'm sure you can implement something similar without proper closures, but I would be surprised if it wasn't much more complicated.

> But I am confused here because this is not an example of strict
> functional programming as you seemed to indicate because there is a
> variable declaration and an assignment.

Perhaps you are confusing pure and strict.

> They can however be easily compensated for by using OO techniques.

Depends on the model of OO you are referring to and what you mean when you say easily. The point about closures is the fact they capture the environment in which they were created. If you need to explicitly copy the environment, then I would say that you are not really simulating closures.

> I believe though that saying "it doesn't even come close", is an exaggeration.

There is clear and tangible difference between first-class and second-class object. It is not a matter of belief.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Musing about Closures Posted: Oct 5, 2005 2:47 AM
Reply to this message Reply
There are many variations on the closure theme, e.g. delegates in C#, continuations in Ruby?, and inner classes in Java and BETA. My personal favourite is inner classes because:

1. They can declare more than one method
2. They can declare fields
3. They can extend abstract classes or interfaces

For Herron they may make an attractive alternative since the variable assigned to the instance of the inner class has a definite scope.

Slightly off topic. The next version of Java, which you can now download alpha versions of, includes automatic stack allocation. IE even though you say x = new Point( 1, 2 ) the runtime might decide to allocate it on the stack instead. If Point had int fields x and y it would put two ints on the stack and directly manipulate these instead of going through a reference to the object.

This type of runtime optimization is ideal, the programmer can get all the advantages of stack allocation without the hassels.

Marcin Kowalczyk

Posts: 40
Nickname: qrczak
Registered: Oct, 2004

Re: Musing about Closures Posted: Oct 6, 2005 6:21 AM
Reply to this message Reply
> My personal favourite is inner classes

They are too heavy, too verbose. Closures done right look very simple.

Even C# is constantly changing its syntax to make writing closures easier: first by allowing "anonymous delegates", then by lambda expressions in LINQ (http://msdn.microsoft.com/netframework/future/linq/default.aspx?pull=/library/en-us/dndotnet/html/linqprojectovw.asp).

Convenient closures are much easier to design with GC and with either dynamic typing or Hindley-Milner style typing. Type inference in C# is getting scary.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Musing about Closures Posted: Oct 7, 2005 2:06 AM
Reply to this message Reply
> They are too heavy, too verbose. Closures done right look
> very simple.

I don't think there is much to choose re. weight of closures vs. inner classes, see:

http://java.sun.com/docs/white/delegates.html

Which discusses delegates, but the same comments apply. In all cases you need heap allocation and garbage collection. Therefore there is no advantage in closures over inner classes from an execution point of view. See below from syntax point of view.

> Even C# is constantly changing its syntax to make writing
> closures easier: first by allowing "anonymous delegates",
> then by lambda expressions in LINQ

Sure the Java style syntax is longer than typical closure syntax, but there is no reason why you couldn't have shorter syntax if you thought that important. I don't find it a big deal the extra syntax, possibly because I use an IDE. See below for shorter syntax suggestion.

> Convenient closures are much easier to design with GC and
> with either dynamic typing or Hindley-Milner style typing.
> Type inference in C# is getting scary.

Hindley-Milner is a scheme for type inference, C#'s and Java's are just other schemes.

Below is a set of suggestions for a shorter syntax for inner classes:

1. Make the new keyword optional.

EG instead of:

String s = new String();


Allow:

String s = String();



2. For methods and classes make the curly braces optional if there is only one statement. IE like for, if, etc.

EG instead of:

class IntWrapper {
public int i;
}


Allow:

class IntWrapper public int i;



And instead of:

public String toString() {
return "Hello";
}


Allow:

public String toString() return "Hello";



3. If a class needs to only implement a single method that is defined in either an abstract class of an interface, then allow the method qualifiers, return type and name and the arguments types to be omitted.

EG instead of:

class MyAction implements ActionListener {
public void actionPerformed( ActionEvent notUsed ) {
textArea.append( textField.getText() );
}
}


Allow (only using simplification 3, see below for an example using all 3 rules):

class MyAction implements ActionListener {
( notUsed ) {
textArea.append( textField.getText() );
}
}




Now an example of combining all three rules, instead of:

textField.addActionListner( new ActionListener() {
public void actionPerformed( ActionEvent notUsed ) {
textArea.append( textField.getText() );
}
});


Allow (using all 3 simplifications):

textField.addActionListner( ActionListener() ( notUsed ) textArea.append( textField.getText() ); );

This would seem to satisfy people wanting short syntax and would be backwards compatable.

Marcin Kowalczyk

Posts: 40
Nickname: qrczak
Registered: Oct, 2004

Re: Musing about Closures Posted: Oct 7, 2005 1:50 PM
Reply to this message Reply
> I don't think there is much to choose re. weight of
> closures vs. inner classes, see:
>
> http://java.sun.com/docs/white/delegates.html

I rarely agree with Microsoft, but this time I had to:
http://msdn.microsoft.com/vjsharp/productinfo/visualj/visualj6/technical/articles/general/truth/default.aspx

> In all cases you need heap allocation and garbage collection.

Besides being heavy syntactically, an inner class yields a separate class file after the source is compiled. This doesn't seem to scale to code which uses closures as often as monadic programming in Haskell, which corresponds to one closure per statement (except the last statement of a block).

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Musing about Closures Posted: Oct 9, 2005 11:06 PM
Reply to this message Reply
In C# they still use a seperate class, e.g. the last section of your reference takes a shot as Gosling saying that they don't use an inner class but a seperate class! There is a difference though, the class they generate is explicit like in Java it is generated on the fly by the runtime, but it is still a class to be loaded.

A further example from the C# version 2 spec. is:

class Test
{
   int x;
 
   void F() {
      int y = 123;
      for (int i = 0; i < 10; i++) {
         int z = i * 2;
         D d = delegate { Console.WriteLine(x + y + z); };
      }
   }
}


Which they say their compiler translates to:

class Test
{
   void F() {
      __locals1 = new __Locals1();
      __locals1.__this = this;
      __locals1.y = 123;
      for (int i = 0; i < 10; i++) {
         __locals2 = new __Locals2();
         __locals2.__locals1 = __locals1;
         __locals2.z = i * 2;
         D d = new D(__locals2.__Method1);
      }
   }
 
   class __Locals1
   {
      public Test __this;
      public int y;
   }
 
   class __Locals2
   {
      public __Locals1 __locals1;
      public int z;
 
      public void __Method1() {
         Console.WriteLine(__locals1.__this.x + __locals1.y + z);
      }
   }
}


This looks to me almost identical to what Java would do with inner classes!

Also Haskel does indeed generate a new class for each function, take a look at the Peyton-Jones book (which is on Miranda - the predessesor language).

Therefore I think, other than syntactic sugar, the inner class is the better construct since it:

1. Allows abstract classes to be extended
2. Allows fields to be defined
3. Allows more than one method

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Musing about Closures Posted: Oct 10, 2005 3:23 AM
Reply to this message Reply
I thought that relying on two non-independent assessments of delegates and innerclasses, one from Sun the other from MS, was a bit dodgy so I wrote a quick benchmark.

package innerclasses;
 
public class Main {
    
    interface Timeable< R > { public R time(); }
    
    static < R > void timeOnce( final Timeable< R > t ) {
        System.gc();
        System.gc();
        final long start = System.currentTimeMillis();
        final R r = t.time();
        final long finish = System.currentTimeMillis();
        System.out.println( "time taken = " + (finish - start) + " ms" + ", result = " + r );
    }
    
    static < R > void time( final Timeable< R > t ) {
        System.out.println( t );
        System.out.print( "run 1: " );
        timeOnce( t );
        System.out.print( "run 2: " );
        timeOnce( t );
    }
    
    static final long times = 1000000000;  /* times round loop for timing */
    
    static class LongHolder { long v; }
    
    void inc( final LongHolder l ) { l.v++; } // delegate method
    
    interface Inner { void inc(); } // adaptor interface to give the method a name
    
    public static void main( final String[] notUsed ) {
        time( new Timeable< Long >() {
            public String toString() { return "Delegate - as optimum as possible since method names match"; }
            public Long time() {
                final Main delegate = new Main(); // delegate method name not needed in this example since it matches already - see comment below
                final LongHolder l = new LongHolder();
                l.v = 0L;
                for ( long count = 1; count < times; count++ ) delegate.inc( l ); // in a real delegate call the name would not have to be the same - just the signature
                return l.v;
            }
        } );
        time( new Timeable< Long >() {
            public String toString() { return "Inner class"; }
            public Long time() {
                final LongHolder l = new LongHolder();
                l.v = 0L;
                final Inner inner = new Inner() { public void inc() { l.v++; } }; // inner class
                for ( long count = 1; count < times; count++ ) inner.inc();
                return l.v;
            }
        } );
        time( new Timeable< Long >() {
            public String toString() { return "No delegate or inner class, but still heap allocation"; }
            public Long time() {
                final LongHolder l = new LongHolder();
                l.v = 0L;
                for ( long count = 1; count < times; count++ ) l.v++;
                return l.v;
            }
        } );
        time( new Timeable< Long >() {
            public String toString() { return "No delegate, no inner class, and no heap allocation - baseline comparison"; }
            public Long time() {
                long l = 0L;
                for ( long count = 1; count < times; count++ ) l++;
                return l;
            }
        } );
    }
    
}


That gave the following:


Delegate - as optimum as possible since method names match
run 1: time taken = 10656 ms, result = 999999999
run 2: time taken = 6439 ms, result = 999999999
Inner class
run 1: time taken = 8072 ms, result = 999999999
run 2: time taken = 5678 ms, result = 999999999
No delegate or inner class, but still heap allocation
run 1: time taken = 5668 ms, result = 999999999
run 2: time taken = 6479 ms, result = 999999999
No delegate, no inner class, and no heap allocation - baseline comparison
run 1: time taken = 4857 ms, result = 999999999
run 2: time taken = 4857 ms, result = 999999999


Which as you can see gives much the same result for all cases. Therefore I side with Sun; there is no significant difference in execution time between a delegate and an inner class, or for that matter an inner class and directly coding. My guess is the Sun server JVM, the one I used, inlines the code in all cases - hence no difference.

The only slight difference in the above test is when heap allocation is avoided, the last test. The next version of Java, 6, has escape analysis that will stack allocate where possible, so presumably all tests using J6 would be the same.

Paul de Vrieze

Posts: 9
Nickname: pauldv
Registered: Oct, 2005

Re: Musing about Closures Posted: Oct 17, 2005 11:24 AM
Reply to this message Reply
What about treating a closure as an implicit lambda function that has as parameters those out-of-scope variables that are used inside. Standard function/lambda function semantics would then apply while offering some semantic sugar.

Howard Lovatt

Posts: 321
Nickname: hlovatt
Registered: Mar, 2003

Re: Musing about Closures Posted: Oct 18, 2005 1:50 AM
Reply to this message Reply
@Paul de Vrieze

What you are suggesting is the first example given in the post immediately above yours, except that the function is named (Java doesn't do annonymous functions). IE l is passed in as an argument.

Patrick O'Grady

Posts: 1
Nickname: patricko
Registered: May, 2003

Re: Musing about Closures Posted: Oct 24, 2005 1:19 PM
Reply to this message Reply
I've used closures quite a bit in embedded C++ systems-- where real time requirements really force us to create stack variables whenever possible. It's always frustrating that closure methods need to be created at the global or class level: Java does much better with it's anonymous inner classes in that the code which will execute is much closer to the application code which it affects. Putting the closure routine directly inside the code which uses it greatly reduces complexity later on.

It seems to me that you really have two different kinds of closures--local and non-local. Local closures promise that they won't be used past any immediate function calls (with a corollary that the associated function pointers won't be stored anywhere except the stack), and in exchange, they get the neat benefit of being able to talk to local variables above them on the stack. Non-local closures can live past the current function call; so the compiler or interpreter can generate syntax errors if the code tries to access local variables. Then, if a routine promises not to use a closure pointer past it's own execution, it can label the closure parameter appropriately:

Suppose:

class MyClass
{ ...
// visitor only used in this iterator
unsigned forEach(local int visitor(unsigned x)) ;
// handler is called by a background thread
unsigned onEvent(int handler(unsigned x)) ;
} ;


And application code which is something like this:

unsigned y = 0 ;
local int f(unsigned x) =
{ y += x ;
return 0 ;
}
MyClass myClass ;
myClass.forEach(f) ;

If I try to call "myClass.onEvent(f);", I'll get a syntax error because onEvent's closure isn't local. Non-local closures can work in any case where a local one is allowed.

I also like an idea of anonymous functions (lambda-like?):

myClass.forEach(
{ // do whatever is called by forEach
});

but I don't know how parameters would be passed in. Something to think about.

The trick here is that the programmer needs to explicitly grant this special local behavior--as a part of the method's contract. As long as I promise to keep to the rules, I'll really appreciate being able to keep my local variables DRY--and avoid the much heavier operation of concocting new objects.

Hope that helps!

Flat View: This topic has 30 replies on 3 pages [ « | 1  2  3 | » ]
Topic: Lua and HeronScript Previous Topic   Next Topic Topic: Back to Generics: Contravariance and Erasure


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2017 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us